Chương 1 tập trung giới thiệu bài toán cần giải quyết cũng như hướng tiếp cận của đề tài. Bài toán khai phá luật kết hợp không phải là bài toán mới trong khai phá dữ liệu, tuy nhiên đây là lĩnh vực có nhiều ứng dụng trong thực tế và đang được rất nhiều nhà nghiên cứu quan tâm, đề xuất các thuật toán để giải quyết. Khi áp dụng mô hình luật kết hợp vào dạng dữ liệu đặc thù là dữ liệu web thì việc lựa chọn một thuật toán khai phá dữ liệu phù hợp là yếu tố vô cùng quan trọng. Trong chương 2, tác giả sẽ tập trung trình bày sơ bộ một số các kỹ thuật khai phá luật kết hợp đã được phát triển và các vấn đề gặp phải khi áp dụng với dữ liệu web log.
NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 CHƯƠNG 2: LUẬT KẾT HỢP VÀ CÁC KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP 2. Khái niệm về luật kết hợp và tập phổ biến Cho một tập mục I = {i1, i2,…, in}, mỗi phần tử thuộc I được gọi là một mục (item). Đôi khi mục còn được gọi là thuộc tính và I cũng được gọi là tập các thuộc tính. Mỗi tập con trong I được gọi là một một tập mục (itemset), số lượng các phần tử trong một tập mục được gọi là độ dài hay kích thước của một tập mục.
Cho một cơ sở dữ liệu giao dịch D = {t1, t2,…, tm}, trong đó mỗi ti là một giao dịch và là một tập con của I. Thường thì số lượng các giao dịch (lực lượng của tập D ký hiệu là |D| hay card(D)) là rất lớn. Cho , Y là hai tập mục (hai tập con của I). Luật kết hợp (association rule) được ký hiệu là Y, trong đó và Y là hai tập không giao nhau, thể hiện mối ràng buộc của tập mục Y theo tập mục theo nghĩa sự xuất hiện của sẽ kéo theo sự xuất hiện của Y ra sao trong các giao dịch.
Tập mục được gọi là xuất hiện trong giao dịch t nếu như là tập con của t. Độ hỗ trợ của một tập mục (ký hiệu là sup( )) được định nghĩa là tỷ lệ các giao dịch trong D có chứa : sup(X) = C(X)/|D| (2.1) Trong đó C( ) số lượng các giao dịch trong CSDL giao dịch D mà có chứa. Giá trị của luật kết hợp Y được thể hiện thông qua hai độ đo là độ hỗ trợ sup( Y) và độ tin cậy conf( Y). Độ hỗ trợ supp( Y) là tỷ lệ các giao dịch có chứa U Y trong tập D: sup( Y) = P( ∪ Y) = C(X ∪ Y)/|D| (2.2) Trong đó ký hiệu C( ∪ Y) là số lượng các giao dịch có chứa U Y.
Độ tin cậy conf( Y) là tỷ lệ các tập giao dịch có chứa U Y so với các tập giao dịch có chứa : conf( Y) = P(Y| ) = C( ∪ Y)/C( ) = sup( Y)/sup( ) (2.3) Trong đó ký hiệu C( ) số lượng các giao dịch có chứa. Từ định nghĩa ta thấy 0 ≤ sup( Y) ≤ 1 và 0 ≤ conf( Y) ≤ 1. Theo quan niệm xác suất, độ hỗ trợ là xác suất xuất hiện tập mục ∪ Y, còn độ tin cậy là xác suất có điều kiện xuất hiện Y khi đã xuất hiện. Luật kết hợp Y được coi là một tri thức (mẫu có giá trị) hay còn gọi là luật kết hợp mạnh (strong association rules) nếu xảy ra đồng thời sup( Y) ≥ minsup NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 và conf( Y) ≥ minconf.
Trong đó minsup và minconf là hai giá trị ngưỡng cho trước. Một tập mục có độ hỗ trợ vượt qua ngưỡng minsup được gọi là tập phổ biến (frequent itemset). Luật kết hợp trong dữ liệu sử dụng web Sau khi dữ liệu truy cập web đã được tiền xử lý, xác định rõ dữ liệu tương ứng với từng người dùng và từng phiên truy cập thì một trong những vấn đề thực tiễn đặt ra là những trang web (hay những tập tin tài nguyên) nào thường được truy cập cùng với nhau. Về cơ bản, một khi đã phân định được các phiên truy cập, ta có thể áp dụng mô hình luật kết hợp vào dữ liệu thu được.
Mỗi trang web hay tập tin được truy cập đóng vai trò là một mục, một phiên truy cập được xem là một giao dịch. Dữ liệu truy cập web lúc này được xem là một cơ sở dữ liệu giao dịch và có thể sử dụng các thuật toán khai phá luật kết hợp. Các luật kết hợp có thể được sử dụng để liên kết những trang thường được truy cập cùng với nhau trong một phiên truy cập. Trong ngữ cảnh của khai phá sử dụng web thì các luật kết hợp chỉ ra tập hợp các trang web thường được truy cập cùng với nhau với độ hỗ trợ lớn hơn một ngưỡng quy định trước.
Các trang web này không nhất thiết phải được kết nối với nhau thông qua các siêu liên kết (hyperlink). Việc sử dụng các giải thuật khai phá luật kết hợp có thể giúp phát hiện ra mối tương quan giữa những người dùng đã viếng thăm các trang web khác nhau. Khai phá luật kết hợp có thể coi là quá trình tìm ra các mẫu phổ biến (frequent patterns) từ các tập mục nằm trong cơ sở dữ liệu giao dịch. Ý tưởng về khai phá luật kết hợp bắt nguồn từ bài toán Phân tích giỏ hàng ở siêu thị nhằm tìm ra những mặt hàng nào thường được mua cùng với nhau.
Trong ngữ cảnh của khai phá web thì khai phá luật kết hợp là nhằm tìm ra những trang web có quan hệ với nhau, được truy cập cùng với nhau với một xác suất nhất định nào đó. Các luật kết hợp trong khai phá sử dụng web thường có dạng: Nếu một người truy cập vào website của CNN thì có 60% khả năng người này cũng sẽ truy cập trang ABC News trong tháng đó 2. Một số nghiên cứu về khai phá luật kết hợp Khai phá luật kết hợp hay các tập phổ biến là một trong những kỹ thuật khai phá dữ liệu được sử dụng rộng rãi. Giải thuật khai phá luật kết hợp đầu tiên được đề xuất bởi Agrawal và các cộng sự [4, 5] nhằm giải quyết bài toán phân tích giỏ hàng ở siêu thị (market basket analysis).
Từ đó cho tới nay, rất nhiều giải thuật NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 16 khác nhau đã được phát triển và khai phá luật kết hợp vẫn là một lĩnh vực thu hút sự quan tâm của nhiều nhà nghiên cứu. Khai phá luật kết hợp từ dữ liệu sử dụng web có liên quan trực tiếp đến các trang (hay tập tin) thường được truy cập cùng với nhau trong một phiên truy cập. Phát biểu trong ngữ cảnh của khai phá sử dụng web thì các luật kết hợp chỉ ra tập các trang được truy cập cùng với nhau với độ hỗ trợ lớn hơn một giá trị ngưỡng nào đó. Agrawal và các cộng sự đã đưa ra giải thuật AIS (xem [4 ).
Giải thuật này tạo ra các tập ứng viên trực tiếp trong mỗi lần duyệt qua cơ sở dữ liệu giao dịch. Các tập phổ biến từ lần duyệt trước đó được kiểm tra xem có xuất hiện trong giao dịch hiện thời hay không. Giải thuật này chưa thực sự hiệu quả vì nó tạo ra quá nhiều các tập ứng viên. Điều này dẫn tới việc tăng dung lượng bộ nhớ sử dụng trong khi giải thuật lại yêu cầu phải duyệt qua cơ sở dữ liệu giao dịch nhiều lần và sinh ra những luật chỉ có một mục tham gia.
Chính Agrawal và các cộng sự cũng đã phát triển các phiên bản khác nhau của giải thuật Apriori như là: Apriori, AprioriTid và AprioriHybrid (xem [5 ). Các giải thuật Apriori và AprioriTid sinh các tập mục dựa trên những tập phổ biến được tìm thấy ở lần duyệt trước đó mà không cần phải xét tới các giao dịch. Giải thuật AprioriTid được phát triển dựa trên giải thuật Apriori bằng cách sử dụng cơ sở dữ liệu ngay trong lần duyệt đầu tiên. Quá trình đếm trong các lần duyệt tiếp theo có thể được thực hiện bằng các sử dụng các mã được tạo ra từ lần duyệt đầu tiên có kích thước nhỏ hơn nhiều so với cơ sở dữ liệu gốc.
Nhờ đó, hiệu năng xử lý của giải thuật này nhanh gấp 3 lần giải thuật AIS. Phát triển một bước nữa, Agrawal đề xuất giải thuật AprioriHybrid. Giải thuật AprioriHybrid được thực hiên dựa trên nguyên tắc: những bước duyệt ban đầu sẽ sử dụng giải thuật Apriori và ở những bước duyệt sau đó sẽ chuyển sang dùng giải thuật AprioriTid nếu kích thước của tập ứng viên có thể lưu trữ vừa trong bộ nhớ. Mặc dù có nhiều phiên bản khác nhau của giải thuật Apriori được phát triển, vấn đề với các giải thuật Apriori đó là chúng tạo ra quá nhiều các tập ứng viên có độ dài 2 không phải là tập phổ biến.
Một giải thuật Băm và cắt tỉa trực tiếp (DHP–Direct Hashing and Prunning) [8 đã được phát triển có tác dụng làm giảm kích thước của các tập ứng viên bằng cách lọc bỏ khỏi bảng băm các tập mục có độ hỗ trợ không vượt quá ngưỡng minsup. Nhờ khả năng lọc bỏ rất ưu việt mà giải thuật DHP tỏ ra hiệu quả hơn nhiều so với giải thuật Apriori (trong một số trường NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 17 hợp, với cùng một bộ dữ liệu vào, khi DHP đã thực thi xong thì Apriori mới đang ở lần duyệt thứ 2). Khả năng mở rộng (scalability) là yếu tố vô cùng quan trọng trong khai phá dữ liệu. Các giải thuật cần có khả năng mở rộng để đáp ứng với sự gia tăng nhanh chóng của dữ liệu.
Eui-Hong và các cộng sự cố gắng tạo ra khả năng mở rộng đối với sự phân bố dữ liệu và phân bố các ứng viên bằng cách sử dụng giải thuật phân bố dữ liệu thông minh (IDD-Intelligent Data Distribution) và giải thuật phân bố hỗn hợp (HD-Hybrid Distribution) (xem [6 ). Giải thuật IDD giúp giải quyết vấn đề quá tải trong trao đổi dữ liệu và tính toán thừa bằng cách sử dụng bộ nhớ gộp để phân đoạn các ứng viên và di chuyển dữ liệu một cách hiệu quả. Giải thuật HD được cải tiến từ IDD bằng cách sử dụng kỹ thuật phân đoạn động các ứng viên để duy trì tốt cân bằng tải trong xử lý.