CHƯƠNG 1: CƠ SỞ LÝ THUYẾT CỦA NGHIÊN CỨU 1. Giới thiệu chương Web Log là một cơ sở dữ liệu lớn và có giá trị cao vì có chức năng ghi nhận lịch sử hành vi truy cập Web của nhiều người dùng, hiển thị bằng các địa chỉ IP cụ thể truy cập các liên kết trên Web tại một mốc thời gian xác định. Web Log được cài đặt tại Server và tự động ghi dấu tất cả sự kiện xảy ra khi bất kỳ ai đó có hành vi truy cập vào trang Web được theo dõi. Công việc này diễn ra liên tục, thường xuyên, một công ty được thành lập và ngày càng phát triển thì nhật ký Web Log có thể xem như là Big Data của họ.
Vì vậy, việc khám phá được các tri thức có ý nghĩa từ cơ sở dữ liệu khổng lồ này để có thêm cơ sở xác định chính xác nhu cầu của khách hàng thông qua xu hướng hành vi phổ biến của họ thể hiện từ lịch sử truy cập các liên kết Web để tìm kiếm, xem thông tin là một lĩnh vực khá mới mẻ và đang thu hút được nhiều sự quan tâm từ các tổ chức có Website kinh doanh. Cơ sở lý thuyết liên quan đến khai phá dữ liệu tuần tự Web Log Dựa vào tập dữ liệu Web Log thu thập được, đề tài tìm hiểu các thuật toán hỗ trợ khai phá các tri thức có ý nghĩa từ chúng. Đầu vào của các thuật toán này đều là một tập dữ liệu chứa các item (các liên kết) đặt cách nhau bởi khoảng trắng (ví dụ: thuật toán Apriori) hoặc kí hiệu khác (ví dụ -1 trong thuật toán RuleGrowth) và được sắp xếp theo thứ tự (thời gian hoặc giảm dần), với điều kiện là các item này không được lặp lại trong cùng một dòng. Khai phá các luật phổ biến (Mining Frequent Itemsets) sử dụng thuật toán Apriori (Agrawal & Srikant, 1993).
Đầu vào của thuật toán này là một transaction database và tham số minsup (có giá trị từ 0 đến 100 %) do người dùng truyền vào. Đầu ra của thuật toán là nhóm các frequent itemsets (phải lớn hơn hoặc bằng minsup). Như vậy, trong tập kết quả trả về, mỗi itemset được chú thích bằng giá trị support, giá trị này thể hiện tổng số lần xuất hiện của itemset này trong bộ dữ liệu ban đầu. Thuật toán Apriori được đánh giá là thuật toán đơn giản và dễ sử dụng, tuy nhiên vấn đề là nó khá chậm và tiêu tốn nhiều bộ nhớ.
Phiên bản Apriori_with_hash_tree cho tốc độ cải thiện hơn trong một vài trường hợp (gấp hai lần so với phiên bản thường) nhưng lại tốn nhiều bộ nhớ hơn. Và một vấn đề khác quan trọng hơn là thuật toán này bị hạn chế khả năng dự báo vì chỉ hỗ trợ tính toán số lần xuất hiện của các tập luật, mỗi luật gồm một hoặc nhiều item có xuất hiện trong cơ sở dữ liệu ban đầu mà không quan tâm đến mối quan hệ giữa các item với nhau. 10 Khai phá các luật tuần tự (sequential rules) từ cơ sở dữ liệu tuần tự (sequence databases). Có khá nhiều những thuật toán hỗ trợ việc khai phá các tập luật tuần tự và chúng được chia thành hai nhánh chính: - Thứ nhất là các thuật toán hỗ trợ việc khai phá các tập luật tuần tự xuất hiện trong một dãy (chuỗi) đơn lẻ của nhiều sự kiện, phương pháp được biết đến nhiều nhất chính là Mannila et al [2].
Các thuật toán khác có thể kể đến nữa là Hamilton & Karimi [5], Hsieh et al [6] và Deogun & Jiang [7]. - Nhánh thứ hai gồm các thuật toán hỗ trợ khai phá những tập luật trong một tập nhiều dãy (chuỗi), gồm hai nhánh phụ: (1) Các thuật toán hỗ trợ khai phá các luật xuất hiện thường xuyên trong dãy (chuỗi), không quan tâm luật đó xuất hiện trong một dãy (chuỗi) hay nhiều dãy (chuỗi), ví dụ là thuật toán Harms et al [8]. Không giống các thuật toán khác, mục tiêu của thuật toán này không phải để khám phá các tập luật xuất hiện thường xuyên trong các dãy (chuỗi) mà là tìm ra các tập luật phổ biến trên nhiều dãy (chuỗi). Ví dụ như hệ thống e-learning sử dụng CTS để dự báo hành vi của người học kế tiếp nhằm giao tiếp tốt hơn.
Nhóm này hiện tại được biết đến có bốn thuật toán hỗ trợ gồm Lo et al. Đầu vào của thuật toán CMRules là một sequence database và hai tham số minsup (có giá trị từ 0 đến 100%), minconf do người dùng truyền vào. Đầu ra của thuật toán là các luật tuần tự (sequential rules) có độ hỗ trợ (support) và độ tin cậy (confidence) cao hơn hai giá trị minsup và minconf truyền vào ban đầu. Ưu điểm của các sequential rule dạng X⇒Y là thể hiện được mối quan hệ tuần tự giữa hai item khác biệt và không sắp xếp theo thứ tự.
Ngoài ra, đề tài cũng ghi nhận lại những nghiên cứu khác có liên quan đến chủ đề phân tích hành vi người dùng thông qua việc khai phá tập dữ liệu Web Log. Bảng dưới đây liệt kê danh sách các công trình nghiên cứu có liên quan: STT Tài liệu Tác giả Thuật toán Kết quả đạt được sử dụng 1 An Approach Preeti + Apriori + Cài đặt thử nghiệm trên for Customer Sharma và máy cục bộ localhost dung Behavior Sanjay ngôn ngữ JSP (Jave Server Analysis Using Kumar Page) Web Mining + Chưa có những đánh giá cụ thể sau khi xác định các 11 tập luật thu được để đánh giá hành vi khách hàng khi viếng thăm các liên kết trên Website. 2 An application Claudia + FP- + Trình bày tương đối chi for clickstream Elena Growth tiết những mối liên quan analysis DINUCĂ + Luật kết giữa các liên kết và xác hợp định độ tin cậy và độ hỗ (Agraval và trợ của các luật được tìm Srikant, thấy từ các Web log file 1994) thực tế. Joshila Đề xuất: Web log and Grace, + Các lý thuyết về Web Web user V.
inWeb Mining Dhinaharan + Một số phương pháp Nagamalai phân tích mẫu phục vụ cho khám phá hành vi người dùng. + Không đưa ra các thực nghiệm cụ thể. 4 Applying Web- Lajos Izsó, + Nghiên cứu về số lần và Mining Péter Tóth thời gian viếng thăm trang Methods for Web để xác định mức độ Analysis of học sinh quan tâm đến nội Student dung các khóa học. Behaviour in VLE Courses Bảng 3.
Bảng thống kê các công trình nghiên cứu có liên quan đến phân tích hành vi người dùng bằng khai phá dữ liệu Web Log 1. Cơ sở lý thuyết chứng minh thuật toán RuleGrowth sử dụng trong đề tài tốt hơn những thuật toán khác Luận điểm 1: thuật toán RuleGrowth tốt hơn thuật toán CMRules và CMDeo [1,3] - CMRules và CMDeo là hai thuật toán đều hỗ trợ khai phá các luật tuần tự, trong đó CMRules dựa trên khai phá luật kết hợp (association rule) cho nên 12 nó có thể cho ra cả hai luật sequential lẫn association cùng một lúc, còn CMDeo dựa trên Apriori để khai phá các luật tuần tự. - Hạn chế chung của cả hai thuật toán CMRules và CMDeo là chúng sử dụng phương pháp «generate candidate-and-test», có nghĩa là tạo ứng viên và kiểm thử. Vấn đề của cách tiếp cận này là nó thường phát sinh một số lượng lớn các luật ứng viên mà phần lớn thì không hợp lệ và không xuất hiện trong cơ sở dữ liệu.
Như vậy, các thuật toán này tốn nhiều thời gian để tách rời các luật hợp lệ khỏi các luật không hợp lệ. - Thuật toán RuleGrowth tránh vấn đề của việc tạo ứng viên này bằng cách thay thế dựa trên một cách tiếp cận “tăng trưởng mẫu” (pattern-growth). RuleGrowth đầu tiên tìm các luật có kích cỡ 1*1 và sau đó tăng trưởng đệ quy chúng bằng cách duyệt các chuỗi trình tự chứa chúng để tìm những phần tử đơn lẻ mà có thể mở rộng các phần bên trái hay bên phải của các luật này. Chiến lược này bảo đảm rằng chỉ có các luật xuất hiện trong cơ sở dữ liệu được xem xét như là các luật hợp lệ tiềm năng bởi thuật toán.
Luận điểm 2: thuật toán CMRules và CMDeo tốt hơn những thuật toán khác. Ngoài ra, các thuật toán Harms et al [8] và Gas et al [10] cũng không được sử dụng vì chúng không hỗ trợ khai phá các luật phổ biến từ nhiều chuỗi (several sequences). - Tính tới thời điểm hiện tại mà các tác giả nghiên cứu thì chỉ có các thuật toán Lo et al. [9], Pitman and Zanker [13] and Zhao et al.
[11,12] là có thể khai phá các luật tuần tự phổ biến trên nhiều chuỗi. Các luật tuần tự có dạng X⇒Y, trong đó X và Y là các mẫu tuần tự (sequential patterns - ordered lists of itemsets). Tuy nhiên, dạng này có hạn chế bởi vì chúng quan tâm đến sự sắp xếp các thành phần (elements) của X hoặc Y. Mục tiêu của CTS đề ra là chỉ cần biết cái gì gây ra các sự kiện, mà không cần quan tâm đến mối liên hệ về thứ tự của các nguyên nhân và các sự kiện.
Vì vậy cũng không sử dụng các thuật toán như Lo et al., Pitman and Zanker or Zhao et al mà thay vào đó các tác giả định nghĩa một hình thức tổng quát hơn của luật tuần tự X⇒Y là các item trong phần bên trái và bên phải của mỗi luật đều không cần sắp xếp thứ tự và gọi đây là thuật toán RuleGrowth. Kết luận chương Các tài liệu nói trên đều có chung mục tiêu là phân tích các tập tin Web Log, sau đó khai thác chúng để tìm ra mối liên quan giữa các liên kết và xác định độ tin cậy, độ hỗ trợ của các tập luật được tìm thấy để xác định hành vi của người sử dụng Web nhằm mục tiêu phục vụ cho kinh doanh hoặc cho lĩnh vực giáo dục. Tuy nhiên, các thuật toán mà các nghiên cứu trên áp dụng đã khá cũ như Apriori (Agrawal & Srikant, 1993) và có những hạn chế nhất định như thuật toán Apriori chạy khá chậm và tiêu tốn nhiều bộ nhớ, các phiên bản cập nhật của thuật toán cũng gặp phải nhiều hạn chế khác như đã phân tích ở các mục 1. Vì vậy, đề tài tập trung tìm hiểu một thuật toán mới và vượt trội hơn các thuật toán khác – đó là RuleGrowth.
Ngoài ra, RuleGrowth còn phù hợp với mục đích nghiên cứu của đề tài là nhằm tìm được các tập luật tuần tự phổ biến trên nhiều dãy (chuỗi) thông qua cơ sở dữ liệu Web Log. Trong lĩnh vực này, RuleGrowth đặc biệt hiệu quả hơn các thuật toán khác khi giúp gia tăng các tập luật hợp lệ trong kết quả trả về cũng là một trong những lý do mà tác giả đề tài quan tâm và muốn tìm hiểu thuật toán này.
