Chương 1 CƠ SỞ LÝ THUYẾT Trong chương này, NCS trình bày các khái niệm cơ bản về luật kết hợp, luật kết hợp định lượng, logic mờ, luật kết hợp mờ và các nghiên cứu liên quan đến luật kết hợp mờ. Từ đó, xác định các vấn đề còn tồn tại cần giải quyết trong chương 2.1 Luật kết hợp 1.1 Các khái niệm cơ bản về luật kết hợp [56] Định nghĩa 1.1 Cơ sở dữ liệu giao tác: Giả sử 𝐼 = {𝑖1 , 𝑖2 , … , 𝑖𝑚 } là tập các mục. 𝐷 = {𝑇1 , 𝑇2 , … , 𝑇𝑛 } là một tập các giao tác, được gọi là cơ sở dữ liệu giao tác, trong đó mỗi giao tác t trong D có dạng (tid, X) trong đó, mỗi giao tác t có định danh tid và tập mục t-itemset, 𝑡 = (𝑡𝑖𝑑, 𝑡 − 𝑖𝑡𝑒𝑚𝑠𝑒𝑡 ); X được gọi là tập mục itemset nếu 𝑋 ⊆ 𝐼. Ví dụ: CSDL giao tác D được mô tả như bảng sau Bảng 1.1: Cơ sở dữ liệu giao tác Tid Items T1 Bánh mì, Sữa T2 Bánh mì, Tã, Bia, Trứng T3 Sữa, Tã, Bia, Nước ngọt T4 Bánh mì, Sữa, Tã, Bia T5 Bánh mì, Sữa, Tã, Nước ngọt Bảng 1.1 biểu diễn cơ sở dữ liệu giao tác, trong đó tập 𝐼 = {𝐵𝑎́ 𝑛ℎ 𝑚𝑖̀, 𝑆ư ̃ 𝑎, 𝑇𝑎̃, 𝐵𝑖𝑎, 𝑇𝑟ứ 𝑛𝑔, 𝑁ướ 𝑐 𝑛𝑔𝑜̣𝑡 } là tập mục tên các mặt hàng (hay gọi là mục) và 5 giao tác.
Mỗi giao tác biểu diễn danh sách các mặt hàng đã mua. Ví dụ, giao tác T1 có chứa các mục {𝐵𝑎́ 𝑛ℎ 𝑚𝑖̀, 𝑆ữ𝑎}.2: Độ hỗ trợ của tập mục Độ hỗ trợ của một tập mục X trong cơ sở dữ liệu giao tác D ký hiệu là sup (X) là số giao dịch chứa tập mục X, được tính bởi công thức sau: 𝑠𝑢𝑝(𝑋 ) = |𝑡| 𝑋 ⊆ 𝑡, 𝑡 ∈ 𝐷 | (1.| là số giao tác. Ví dụ: trong CSDL ở bảng 1.1, độ hỗ trợ của tập mục {𝐵𝑖𝑎, 𝑇𝑎̃, 𝑆ữ𝑎} là 2 vì có hai giao tác chứa 3 mục trên.3: Tập mục phổ biến Một tập mục X có trong cơ sở dữ liệu giao tác D được gọi là phổ biến nếu độ hỗ trợ của nó (𝑠𝑢𝑝(𝑋 )) lớn hơn hoặc bằng ngưỡng độ hỗ trợ tối thiểu (minsup) cho trước do người dùng định nghĩa. Vì vậy, độ hỗ trợ được xem là tần suất xuất hiện đồng thời của các mục.4: Luật kết hợp Một luật kết hợp là một mệnh đề kéo theo có dạng X →Y, trong đó X và Y là các tập mục thoả mãn điều kiện: 𝑋 ⊆ 𝐼, 𝑌 ⊆ 𝐼 và 𝑋⋂ 𝑌 = ∅.
Đối với luật kết hợp X → Y, X được gọi là tiền đề, Y được gọi là kết quả của luật.5 : Độ hỗ trợ của một luật Cho luật kết hợp 𝑟 = 𝑋 → 𝑌, độ hỗ trợ của luật r ký hiệu là sup(r) là tỉ số giữa số lượng các giao tác T ⊆ D có chứa cả tập mục X và tập mục Y với tổng số giao tác trong D được xác định như sau: |{𝑇 ∈ 𝐷 |𝑇 ⊃ 𝑋 ∪ 𝑌}| 𝑠𝑢𝑝(𝑟) = (1.6 Độ tin cậy của một luật Cho luật kết hợp 𝑟 = 𝑋 → 𝑌, độ tin cậy của luật r ký hiệu là conf(r) là tỉ số giữa số lượng các giao tác T ⊆ D có chứa cả tập mục X và tập mục Y với tổng số giao tác trong D chứa tập mục X, được xác định như sau: |{𝑇 ∈ 𝐷 |𝑇 ⊃ 𝑋 ∪ 𝑌}| 𝑠𝑢𝑝(𝑋 ∪ 𝑌) 𝑐𝑜̣𝑛𝑓(𝑟) = = (1.3) |{𝑇 ∈ 𝐷 |𝑇 ⊃ 𝑋 }| 𝑠𝑢𝑝(𝑋 ) Ví dụ: Xem xét một luật {𝐷𝑖𝑎𝑝𝑒𝑟𝑠, 𝑀𝑖𝑙𝑘} → {𝐵𝑒𝑒𝑟}. Vì độ hỗ trợ của tập mục 2 {𝐵𝑒𝑒𝑟, 𝐷𝑖𝑎𝑝𝑒𝑟𝑠, 𝑀𝑖𝑙𝑘} là 2 và tổng số giao tác là 5, do đó độ hỗ trợ của luật là = 5 0. Độ tin cậy của luật thu được bởi tỉ số giữa độ hỗ trợ của {𝐵𝑒𝑒𝑟, 𝐷𝑖𝑎𝑝𝑒𝑟𝑠, 𝑀𝑖𝑙𝑘} 22 và độ hỗ trợ của {𝐷𝑖𝑎𝑝𝑒𝑟𝑠, 𝑀𝑖𝑙𝑘}. Vì có 3 giao tác chứa {𝐷𝑖𝑎𝑝𝑒𝑟𝑠, 𝑀𝑖𝑙𝑘} nên độ hỗ 2 trợ của luật sẽ là = 0.7: Luật kết hợp mạnh Cho luật kết hợp 𝑟 = 𝑋 → 𝑌, nếu luật r thỏa mãn cả hai ngưỡng là độ hỗ trợ tối thiểu (minsup) và độ tin cậy tối thiểu (minconf) được gọi là luật kết hợp mạnh, tức là: 𝑠𝑢𝑝(𝑟 = 𝑋 → 𝑌) = 𝑃(𝑋 ∪ 𝑌) ≥ 𝑚𝑖𝑛𝑠𝑢𝑝 𝑠𝑢𝑝(𝑋 ∪ 𝑌) 𝑐𝑜̣𝑛𝑓(𝑟 = 𝑋 → 𝑌) = 𝑃(𝑋 ∪ 𝑌) = ≥ 𝑚𝑖𝑛𝑐𝑜̣𝑛𝑓 𝑠𝑢𝑝(𝑋 ) Ví dụ: Xem xét CSDL trong bảng 1.1, luật kết hợp {𝐷𝑖𝑎𝑝𝑒𝑟𝑠, 𝑀𝑖𝑙𝑘} → {𝐵𝑒𝑒𝑟} có nghĩa là trong cùng một giao dịch, nếu mặt hàng Diapers và Milk được mua thì mặt hàng Beer cũng được mua.
Phát biểu bài toán: Bài toán luật kết hợp được phát biểu như sau [49]: Cho một cơ sở dữ liệu giao tác D, độ hỗ trợ tối thiểu minsup, độ tin cậy tối thiểu minconf. Hãy tìm tất cả các luật kết hợp có dạng 𝑋 → 𝑌 thỏa mãn độ hỗ trợ 𝑠𝑢𝑝(𝑋∪𝑌) 𝑠𝑢𝑝(𝑋 ∪ 𝑌) ≥ 𝑚𝑖𝑛𝑠𝑢𝑝 và độ tin cậy 𝑐𝑜̣𝑛𝑓 (𝑋 → 𝑌) = ≥ 𝑚𝑖𝑛𝑐𝑜̣𝑛𝑓 𝑠𝑢𝑝(𝑋) Hầu hết các thuật toán khai phá luật kết hợp đều theo hướng chia bài toán thành hai pha cụ thể: − Pha 1: Tìm tất cả các tập mục phổ biến từ cơ sở dữ liệu, tức là tìm tất cả tập mục có độ hỗ trợ lớn hơn hoặc bằng độ hỗ trợ tối thiểu (𝑠𝑢𝑝(𝑋 ) ≥ 𝑚𝑖𝑛𝑠𝑢𝑝). − Pha 2: Sinh tất cả các luật có độ tin cậy từ tập mục phổ biến đã tìm thấy ở pha thứ 1. Nếu X là tập mục phổ biến, thì luật sinh ra từ X có dạng 𝐴 → 𝐵 trong đó 𝐵 ⊂ 𝑋, và 𝐴 = 𝑋 − 𝐵 nếu độ tin cậy của luật 𝐴 → 𝐵 có độ tin cậy lớn hơn độ tin cậy tối thiểu cho trước minconf.2 Luật kết hợp trong cơ sở dữ liệu nhị phân Luật kết hợp nhị phân đề cập đến các luật cổ điển trong bài toán phân tích giỏ hàng.
Ở đây các sản phẩm có thể có trong giao dịch hoặc không, chỉ tạo ra các giá trị kiểu boolean (được biểu diễn bằng 1 và 0). Do đó, mọi mục trong giao dịch có thể 23 được xác định là một thuộc tính nhị phân với miền [0,1]. Mô hình được định nghĩa trong [56] như sau: Cho 𝐼 = {𝑖1 , 𝑖2 , … , 𝑖𝑚 } là một tập các thuộc tính nhị phân, gọi là các mục. Cho T là cơ sở dữ liệu giao dịch.
Mỗi giao dịch t được biểu diễn như là vecto nhị phân với 𝑡[𝑘 ] = 1 nếu giao dịch t có chứa mục 𝑖𝑘 và 𝑡 [𝑘 ] = 0 nếu ngược lại. Cho X là một tập mục chứa trong I, ta nói một giao dịch t thỏa mãn X nếu mọi mục trong X, 𝑖𝑘 ∈ 𝑋, 𝑡[𝑘 ] = 1.2: Ví dụ về cơ sở dữ liệu nhị phân Tid A B C D E 1 1 0 1 1 1 2 1 1 1 0 0 3 0 1 1 0 0 4 1 1 1 0 1 5 1 0 1 1 0 6 0 1 1 1 0 Bảng 1.2 mô tả cơ sở dữ liệu nhị phân, CSDL bao gồm sáu giao tác và năm mục được ký hiệu là A - E. Trong ví dụ này, giao dịch TID =1 có các mục A, C, D, E nên các mục này nhận giá trị 1, còn các mục B không có trong CSDL nên B nhận giá trị 0. Bài toán khai phá luật kết hợp nhị phân tập trung chủ yếu ở giai đoạn khai phá tập mục phổ biến, vì đây là giai đoạn phức tạp, đòi hỏi nhiều chi phí về thời gian và tính toán.
Hai thuật toán điển hình trong khai phá tập mục phổ biến là thuật toán Apriori [5] và FP-growth [57]. Thuật toán Apriori tiêu biểu cho phương pháp sinh ra các tập mục ứng viên rồi duyệt cơ sở dữ liệu kiểm tra độ hỗ trợ của chúng, thuật toán FP-Growth đại diện cho phương pháp không sinh ra các tập mục ứng viên mà nén cơ sở dữ liệu theo cấu trúc cây.3 Luật kết hợp trong cơ sở dữ liệu định lượng Theo dạng luật kết hợp nhị phân này thì các mục chỉ được quan tâm là có hay không xuất hiện trong cơ sở dữ liệu giao tác chứ không quan tâm về mức độ hay tần xuất xuất hiện. Trong thực tế, cơ sở dữ liệu không chỉ chứa các thuộc tính nhị phân 24 mà còn chứa các thuộc tính định lượng và phân loại mà không thể khai phá bằng kỹ thuật cổ điển. Việc khai phá các luật trong loại dữ liệu như vậy có thể được gọi là bài toán luật kết hợp định lượng [29].
Chiến lược khai phá luật kết hợp định lượng được thực hiện bằng cách chuyển đổi các thuộc tính có giá trị định lượng sang giá trị nhị phân. Trong phương pháp này, mỗi giá trị định lượng/phân loại có dạng 〈𝑎𝑡𝑡𝑟𝑖𝑏𝑢𝑡𝑒, 𝑣𝑎𝑙𝑢𝑒〉 được ánh xạ sang giá trị nhị phân. Sau đó, các kỹ thuật khai phá luật kết hợp nhị phân được thực hiện để tìm luật. Tuy nhiên, khi miền giá trị của thuộc tính là quá lớn hoặc liên tục thì phương pháp này không hiệu quả [58].
Rời rạc hóa các thuộc tính liên tục thành các khoảng thời gian khác nhau là một cách phổ biến để giải quyết vấn đề này. Sau khi rời rạc hóa, các thuộc tính được coi là thuộc tính phân loại [59]. Chẳng hạn, một thuộc tính x có giá trị từ 20 đến 100 có thể được chia thành các khoảng (20–30, 30–40,…, 90–100). Nếu một giá trị là 62, thì khoảng (60–70) trở thành 1 và khoảng còn lại các khoảng vẫn là 0.
Vấn đề chính của sự rời rạc hóa các giá trị là mất thông tin và kết quả kém [61]. Ngoài ra, hiệu quả phụ thuộc vào các khoảng xác định, trong khi việc xác định các khoảng thích hợp là khó [62]. Trong khai phá luật kết hợp định lượng, các thuộc tính có thể là định lượng và phân loại.2 Tổng quan về Logic mờ 1.1 Tập mờ Lý thuyết tập mờ được Zadeh đưa ra vào năm 1965 [22] và rất phù hợp để xử lý các giá trị định lượng và biểu diễn ý nghĩa ngôn ngữ. Biểu diễn ngôn ngữ là phổ biến và dễ hiểu hơn đối với con người.
Một biến ngôn ngữ là một biến có giá trị của nó là tập các thuật ngữ mờ được biểu diễn bằng ngôn ngữ tự nhiên và được xác định bởi các hàm thành viên [63]. Cho một tập vũ trụ U với các phần tử ký hiệu bởi 𝑢 , 𝑈 = {𝑥}. Một tập mờ 𝐴̃ trên U là tập được đặc trưng bởi một hàm 𝜇𝐴 (𝑢) mà nó liên kết mỗi phần tử 𝑢 ∈ 𝑈 với một số thực trong đoạn [0,1].4) 25 Trong đó 𝜇𝐴 (𝑢) là một ánh xạ từ U vào [0,1] và được gọi là hàm thành viên của tập mờ 𝐴̃.