Đặt vấn đề: Bài toán giỏ mua hàng trong siêu thị. Giả định chúng ta có rất nhiều mặt hàng, ví dụ như “bánh mì”, “sữa”,…(coi là tính chất hoặc trường). Khách hàng khi đi siêu thị sẽ bỏ vào giỏ mua hàng của họ một số mặt hàng nào đó, và chúng ta muốn tìm hiểu các khách hàng thường mua các mặt hàng nào đồng thời, chúng ta không cần biết khách hàng cụ thể là ai. Nhà quản lý dùng những thông tin này để điều chỉnh việc nhập hàng về siêu thị, hay đơn giản là để bố trí sắp xếp các mặt hàng gần nhau, hoặc bán các mặt hàng đó theo một gói hàng, giúp cho khắc đỡ mất công tìm kiếm.
Khai phá luật kết hợp được mô tả như sự tương quan của các sự kiện, những sự kiện xuất hiện thường xuyên một cách đồng thời. Nhiệm vụ chính của khai phá luật kết hợp là phát 4 hiện ra các tập con cùng xuất hiện trong một khối lượng giao dịch lớn của một cơ sở dữ liệu cho trước. Định nghĩa 1: Cho I = {i1 ,i2 ,… ,in} là tập hợp của m tính chất riêng biệt. Giả sử D là cơ sở dữ liệu (CSDL), với các bản ghi chứa một tập con T của các tính chất và có thể coi như , các bản ghi đều có chỉ số riêng.
Một luật kết hợp là một mệnh đề kéo theo có dạng XY, trong đó X, Y I, thỏa mãn điều kiện XY=. Các tập hợp X và Y được gọi là các tập hợp tính chất (itemset). Tập X gọi là mệnh đề điều kiện hay còn gọi là nguyên nhân (phần bên trái), tập Y gọi là mệnh đề kết quả của luật tương ứng hay còn gọi là hệ quả (phần bên phải). Transaction ID List of Item_IDs T100 I1, I2, I5 Itemsets T200 I2, I4 Item: I4 {I1, I2, I5}, {I2} T300 I2, I3 T400 I1, I2, I4 T500 I1, I3 Transaction: T800 T600 I2, I3 T700 I1, I3 T800 I1, I2, I3, I5 T900 I1, I2, I3 Hình 1.
1 Minh họa định nghĩa Item, Itemset, Transaction Item (phần tử): Các phần tử, mẫu, đối tượng đang được quan tâm. I = {i1 ,i2 , … ,in} tập tất cả m phần tử có thể có trong tập dữ liệu. Itemset (tập phần tử): Là tập hợp các Items. Một itemset có k items được gọi là k- Itemset.
Liên hệ với một tập T gồm các phần tử được giao dịch. Ví dụ: trong siêu thị, ta có tập các mục I = {Sữa, Bánh mì, Bơ, Gạo} và một cơ sở dữ liệu chứa các mục (tại mỗi giao tác, giá trị 1 là có mục, giá trị 0 là không có) như sau: 5 Bảng 1. 1 Dữ liệu mua hàng ở siêu thị Transaction ID Sữa Bánh mì Bơ Gạo 1 1 1 1 0 2 0 0 1 0 3 1 0 0 1 4 1 1 1 0 5 0 1 0 0 Dựa trên ví dụ này, ta có thể suy ra luật {Sữa, Bánh mì} {Bơ}, có nghĩa là khi khách hàng mua sữa và bánh mì thì người đó cũng sẽ có khả năng cao mua bơ.3 Các khái niệm về luật kết hợp Để chọn ra các luật có ích từ tập các luật có thể có, ta cần ràng buộc những số đo đảm bảo ý nghĩa. Hai ràng buộc được xem là quan trọng nhất, đó là giá trị độ hỗ trợ (Support) [2] và độ tin cậy (Confident).
Để minh họa cho các khái niệm, ta lấy ví dụ CSDL với các giao dịch sau. 2 CSDL với các giao dịch TID (Mã giao dịch) Itemset (tập các hạng mục) 1 A,B,E 2 B,D 3 B,C 4 A,B,D 5 A,C 6 B,C 7 A,C 8 A,B,C,E 9 A,B,C 6 Hạng mục (item): mặt hàng A = apple, B = bread, C = cereal, D = donuts, E = eggs. Tập các hạng mục (itemset): danh sách các hạng mục trong giỏ hàng như {A,B,C,D,E}. Mẫu phổ biến (frequent item): là mẫu xuất hiện thường xuyên trong tập dữ liệu như {A,C} xuất hiện khá nhiều trong các giao dịch.
Tập k-hạng mục (k-itemset): ví dụ danh sách sản phẩm (1-itemset) như {A,B,C}, danh sách cặp sản phẩm đi kèm (2-itemset) như {{A,B},{A,C}}, danh sách 3 sản phẩm đi kèm (3-itemset) như {{A,B,C},{A,C,E}}. Tập mục phổ biến (frequent itemset): là tập các hạng mục S (itemset) thỏa mãn độ phổ biến tối thiểu (minsupp – do người dùng xác định như 40% hoặc xuất hiện 5 lần). Nếu Supp(S) >= minsupp thì S là tập phổ biến. Sẽ được giới thiệu chi tiết hơn ở phần bên dưới.
Độ hỗ trợ (tên tiếng anh là support) của một tập mục X [2] được định nghĩa là tỷ lệ các giao tác có chứa tập mục này trong cơ sở dữ liệu với tổng số các giao tác. Là độ đo tần số xuất hiện của các phần tử/tập phần tử. Ví dụ, tập mục {milk, bread, butter} có độ phổ biến là 2/5 = 0.4 hay 40% số giao tác. Định nghĩa 2: Độ hỗ trợ của một tập hợp X trong cơ sở dữ liệu D là tỷ số giữa các bản ghi T D có chứa tập X và tổng số bản ghi trong D [2] (hay là phần trăm của các bản ghi trong D có chứa tập hợp X), ký hiệu là support(X) hay supp(X).
|{TD: YX}| Supp(X) = |D| Ta có: 0 ≤ Supp(X) ≤ 1 với mọi tập mục X. Định nghĩa 3: Độ hỗ trợ của một luật kết hợp XY [2] là tỷ lệ giữa số lượng các bản ghi chứa tập hợp X Y, so với tổng số các bản ghi trong D - Ký hiệu supp(XY). Như vậy, độ hỗ trợ mang ý nghĩa thống kê của luật. Định nghĩa 4: Độ đo đo tần số xuất hiện của một tập phần tử trong điều kiện xuất hiện của một tập phần tử khác.
Độ tin cậy của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi của tập hợp chứa X Y, so với tổng số các bản ghi chứa X. Ta có thêm định nghĩa khác để hiểu rõ hơn về độ tin cậy : Định nghĩa 5: Độ tin cậy của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi trong D chứa XY với số bản ghi trong D có chứa tập hợp X. Ký hiệu độ tin cậy của một luật là Conf(r). Nhận xét: Supp(XY)=P(XY) Conf (XY) = P(Y/X)=supp(XY)/supp(X) Nói rằng độ tin cậy của một luật X=>Y là 90%, có nghĩa là có tới 90% số bản ghi chứa X chứa luôn cả Y.
Hay nói theo ngôn ngữ xác suất là: “ Xác suất có điều kiện để sảy ra sự kiện Y đạt 90%”. Điều kiện ở đây chính là: “Xảy ra sự kiện X”.3 Tập mục phổ biến (Frequent itemset) Định nghĩa 6: Tập hợp X được gọi là tập mục phổ biến (Frenquent itemset) nếu có supp(X) minsup, với minsup là ngưỡng độ hỗ trợ cho trước. Kí hiệu các tập này là FI. Định nghĩa 7: Một tập mục X được gọi là đóng (closed) nếu không có tập cha nào của X có cùng độ hỗ trợ với nó, tức là không tồn tại một tập mục X’ nào mà X’X và t(X) = t(X’) 8 (với t(X) và t(X’) tương ứng là tập các giao chứa tập mục X và X’).
Ký hiệu tập phổ biến đóng là FCI. Khai phá luật kết hợp là công việc phát hiện ra (tìm ra, khám phá, phát hiện) các luật kết hợp thỏa mãn các ngưỡng độ hỗ trợ () và ngưỡng độ tin cậy () cho trước. Bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ, hay như người ta thường nói, việc giải bài toán trải qua hai pha: Pha 1: Tìm tất cả các tập phổ biến (tìm FI) trong CSDL T. Pha 2: Sử dụng tập FI tìm được ở pha 1 để sinh ra các luật tin cậy (interesting rules).
Ý tưởng chung là nếu gọi ABCD và AB là các tập mục phổ biến, thì chúng ta có thể xác định luật AB →CD với tỷ lệ độ tin cậy: supp(ABCD) conf = 𝑠𝑢𝑝𝑝(𝐴𝐵) Nếu conf minconf thì luật được giữ lại (và thỏa mãn độ hỗ trợ tối thiểu vì ABCD là phổ biến).4 Các công trình nghiên cứu Khai phá luật kết hợp là một kỹ thuật quan trọng trong lĩnh vực khai phá dữ liệu. Mục tiêu khai phá là phát hiện những mối liên hệ giữa các giá trị dữ liệu trong các dữ liệu giao dịch. Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân hay còn gọi là mô hình cơ bản (Agrawal et al., 1993) [1], phân tích dữ liệu giao dịch, phát hiện các mối liên hệ giữa các tập mục hàng hoá đã bán được tại các siêu thị. Từ đó, doanh nghiệp có kế hoạch bố trí, sắp xếp, kinh doanh hợp lý, đồng thời tổ chức sắp xếp các quầy gần nhau để có doanh thu trong các phiên giao dịch là lớn nhất.
Bài toán khai phá luật kết hợp là bài toán khai phá các luật kết hợp có độ hỗ trợ (support) cũng như độ tin cậy (confidence) lớn hơn hoặc bằng một ngưỡng hỗ trợ tối thiểu (minsup) và ngưỡng tin cậy tối thiểu (minconf). Các thuật toán được đề xuất để khai phá luật kết hợp bao gồm 2 giai đoạn [1] [3]: (Agrawal et al. Giai đoạn 1: Tìm tất cả các tập mục phổ biến từ dữ liệu giao dịch thoả minsupp. Giai đoạn 2: Sinh các luật tin cậy kết hợp từ tập mục phổ biến tìm thấy ở giai đoạn thứ nhất.
9 Giai đoạn thứ nhất chiếm hầu hết thời gian cho quá trình khai phá luật kết hợp. Giá trị ngưỡng phổ biến tối thiểu minsup là yếu tố quan trọng trong quá trình rút gọn không gian tìm kiếm cũng như giới hạn các luật sinh trong giai đoạn thứ hai. Các thuật toán khai phá luật kết hợp truyền thống chỉ dùng một giá trị ngưỡng hỗ trợ tối thiểu ‘minsupp’ với ngầm định là các mục hàng có cùng tính chất và tần số trong dữ liệu, điều này không thực tế. Trong kinh doanh bán lẻ, thông thường các mặt hàng thiết yếu, hàng tiêu dùng và các sản phẩm giá rẻ được mua nhiều hơn, trong khi các mặt hàng xa xỉ và các sản phẩm giá trị cao lại ít được mua.
Nếu chọn minsupp quá cao thì các mặt hàng được khai phá thông thường có giá thành thấp và mang lại lợi nhuận không cao cho doanh nghiệp. Ngược lại, nếu chọn minsupp quá thấp thì các mặt hàng được khai phá quá lớn, điều này làm cho doanh nghiệp khó khăn khi ra quyết định kinh doanh. Vì vậy, Liu et al. (1999) đã mở rộng bài toán khai phá luật kết hợp với nhiều ngưỡng phổ biến tối thiểu (mỗi mục hàng có một ngưỡng phổ biến tối thiểu riêng) tương ứng mỗi mục hàng khác nhau có tính chất khác nhau và tần số giao dịch khác nhau.