Chương 1: Tổng quan về luật kết hợp và mẫu chuỗi, luật chuỗi chung. Chương này trình bày các khái niệm, phương pháp phát hiện các luật kết hợp, mẫu chuỗi, luật chuỗi chung của các nghiên cứu trước đó. Từ đó xác định những các khoảng trống nghiên cứu và xác định vấn đề cụ thể trong luận án. Chương 2: Phát hiện luật kết hợp có tính đến khoảng cách thời gian trong các CSDL định lượng có yếu tố thời gian.
Chương này đề xuất vấn đề và thuật toán phát hiện các luật kết hợp có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL định lượng có yếu tố thời gian. Tính đúng đắn và đầy đủ của thuật toán, việc thực nghiệm thuật toán trên tập dữ liệu thực, ý nghĩa của các luật kết hợp phát hiện được và so sánh với những nghiên cứu trước đó cũng được trình bày trong Chương. Chương 3: Phát hiện mẫu chuỗi có tính đến khoảng cách thời gian trong các CSDL chuỗi định lượng có yếu tố thời gian. Chương này đề xuất vấn đề và thuật toán phát hiện mẫu chuỗi có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian.
Tính đúng đắn và tính đầy đủ, độ phức tạp tính toán của thuật toán được đề xuất, việc thực nghiệm thuật toán trên tập dữ liệu thực, ý nghĩa 17 của các mẫu chuỗi phát hiện được và so sánh với những nghiên cứu liên quan trước đó cũng được trình bày trong Chương. Chương 4: Phát hiện luật chuỗi chung có tính đến khoảng cách thời gian trong các CSDL chuỗi định lượng có yếu tố thời gian. Chương này đề xuất vấn đề và thuật toán phát hiện luật chuỗi chung có tính đến khoảng cách thời gian xảy ra giữa các giao dịch trong các CSDL chuỗi định lượng có yếu tố thời gian. Tính đúng đắn và tính đầy đủ, độ phức tạp tính toán của thuật toán, việc thực nghiệm thuật toán trên tập dữ liệu thực, ý nghĩa của các luật chuỗi chung phát hiện được và so sánh với luật chuỗi chung được phát hiện bởi các thuật toán trước đó cũng được trình bày trong Chương.
Phần kết luận: Trình bày một số kết luận về ý nghĩa, đóng góp của luận án và định hướng nghiên cứu trong tương lai. TỔNG QUAN VỀ LUẬT KẾT HỢP VÀ MẪU CHUỖI, LUẬT CHUỖI CHUNG Chương này trình bày tổng quan những vấn đề liên quan đến phát hiện các luật kết hợp và các mẫu chuỗi, luật chuỗi chung trong các CSDL giao dịch/định lượng không có hoặc có yếu tố thời gian. Chương này cũng chỉ ra các khoảng trống chưa được giải quyết để từ đó xác định vấn đề nghiên cứu của luận án. Luật kết hợp 1.
Phát hiện luật kết hợp trong các CSDL giao dịch Định nghĩa 1.1 CSDL giao dịch [2]: Giả sử I = {i1, i2, … , i𝑛} là tập các mục, D = {𝑇1, 𝑇2, … , 𝑇𝑚} là tập các giao dịch, 𝑇j (1jm) là tập các mục thỏa mãn 𝑇j I, 𝑇j i𝑘 biểu diễn mục i𝑘 xuất hiện trong giao dịch 𝑇j (hay tương ứng i𝑘 nhận giá trị 1 nếu xuất hiện trong giao dịch này), nói cách. Khi đó, D được gọi là CSDL giao dịch. Ví dụ về CSDL giao dịch được mô tả như Bảng 1. Ví dụ về CSDL giao dịch TID Mặt hàng đƣợc mua 1 ab 2 bc 3 de 4 abc 5 b Bảng 1.1 biểu diễn CSDL giao dịch, trong đó I={a, b, c, d, e} là tập tên các mặt hàng (hay là mục) và 5 giao dịch.
Mỗi giao dịch biểu diễn danh sách các mặt hàng được mua. Chẳng hạn, giao dịch đầu tiên có các mặt hàng a và b được mua.2 Luật kết hợp [1]: Giả sử X là tập mục, giao dịch T được gọi là chứa X khi và chỉ khi XT. Luật kết hợp là luật có dạng X Y với XI, YI và XY=. Trong đó X được gọi là tiền đề, Y là hệ quả của luật.3 Độ hỗ trợ và độ tin cậy của luật kết hợp [1] Độ hỗ trợ (support) của tập mục X là tỉ lệ số giao dịch trong D chứa X, kí hiệu là sup(X) |{𝑇| 𝑇 ∈ 𝐷 𝖠 X ≤ 𝑇}| 𝑠𝑢𝑝(X) = (1.1) |𝐷| Độ hỗ trợ của luật X → 𝑌 là tỉ lệ số giao dịch trong D chứa XY, kí hiệu là 𝑠𝑢𝑝(X → 𝑌) 𝑠𝑢𝑝(X 𝖴 𝑌) 𝑠𝑢𝑝(X → 𝑌) = (1.3) 𝑠𝑢𝑝(X) Ví dụ: Xét CSDL trong Bảng 1.1, luật kết hợp {b, c} → {a} có nghĩa “Trong cùng một giao dịch, nếu mặt hàng b và c được mua thì mặt hàng a cũng sẽ được mua”.
Luật này có độ hỗ trợ là 1/5=20% (tức là có 1 giao dịch chứa luật trong tổng số 5 giao dịch của CSDL) và độ tin cậy của luật là 1/2=50% (có 1 giao dịch cả b, c, a được mua và 2 giao dịch cả b và c được mua) Việc phát hiện các luật kết hợp thường được chia làm 2 giai đoạn [1], [74]: Giai đoạn 1: Tìm tất cả các tập phổ biến trong CSDL, ở đó các tập phổ biến là các tập có độ hỗ trợ không nhỏ hơn độ hỗ trợ cực tiểu (hay ngưỡng hỗ trợ) cho trước; 20 Giai đoạn 2: Sinh ra các luật kết hợp có độ tin cậy không nhỏ hơn độ tin cậy cực tiểu (hay ngưỡng tin cậy) cho trước từ các tập phổ biến đã tìm được ở giai đoạn 1. Trong hai giai đoạn trên thì giai đoạn 1 là phức tạp, đòi hỏi nhiều chi phí về thời gian và tính toán. Ở giai đoạn 2, các luật kết hợp được sinh ra từ các tập phổ biến tìm được là khá đơn giản nên đa phần các thuật toán phát hiện luật kết hợp chỉ tập trung vào giải quyết giai đoạn 1, tức là tập trung vào việc tìm các tập phổ biến. Các thuật toán phát hiện luật kết hợp được chia thành hai nhóm dựa vào phương pháp duyệt không gian tìm kiếm, đó là các phương pháp duyệt theo chiều rộng (Breadth First Search - BFS) và duyệt theo chiều sâu (Depth First Search - DFS).
Duyệt theo chiều rộng là phương pháp duyệt tất cả các tập ứng cử viên có k-1 mục trước khi xét đến các tập ứng cử viên có k mục. Các thuật toán thực hiện theo cách tiếp cận này gồm: APRIORI [2], PARTITION [3], A-CLOSE [4], A-CLOSE+ [5], DIC [13],. Duyệt theo chiều sâu là phương pháp duyệt xong các tập ứng cử viên liên quan với một tập mục phổ biến rồi mới chuyển sang xem xét đối với tập phổ biến cùng kích thước khác. Các thuật toán thực hiện theo cách tiếp cận này là: CLOSE [6], CLOSET [7], CLOSET+ [8], CHARM [9], FP-GROWTH [14], ECLAT [12], CFPMINE [15].
APRIORI [2] là thuật toán đầu tiên phát hiện luật kết hợp trong CSDL giao dịch. Thuật toán này được phát triển theo cách tiếp cận duyệt theo chiều rộng với việc sinh ra các tập ứng cử viên độ dài k bằng cách kết hợp hai tập phổ biến độ dài k-1. Thuật toán APRIORI được xếp vào tốp 10 thuật toán khai phá dữ liệu điển hình nhất [75], thuật toán được mô tả cơ bản như trong Thuật toán 1. Thuật toán Apriori input: T: Tập các giao dịch c: Độ hỗ trợ cực tiểu output: Tập các tập phổ biến Apriori{ 1.
𝐿1 {large 1-itemsets}; //các tập phổ biến độ dài 1 2. 𝐶𝑘 Apriori-gen(𝐿𝑘−1); //Sinh tập ứng cử viên độ dài k, 𝐶𝑘 5. for transactions t T do { 6. 𝐷𝑡 {c 𝐶𝑘 | c t}; //mọi ứng viên chứa trong t 7.
for each c 𝐷𝑡 do 8. } Trong Thuật toán 1.1, T là tập các giao dịch, kết quả trả lại là các tập phổ biến có độ hỗ trợ thỏa mãn độ hỗ trợ cực tiểu c Đến nay, đã có nhiều nghiên cứu phát hiện các luật kết hợp trong CSDL giao dịch và được ứng dụng trong thực tiễn như trong thị trường bán lẻ [76], [77], thị trường chứng khoán [78]–[80], y tế [81], [82],. Phát hiện luật kết hợp trong các CSDL định lượng Định nghĩa 1.4 CSDL định lượng [24]: Giả sử I = {i1, i2, … , i𝑛} là tập các thuộc tính, D = {𝑇1, 𝑇2, … , 𝑇𝑚} là tập các giao dịch, 𝑇j (1jm) là tập các thuộc tính thỏa mãn 𝑇j I, các giá trị 𝑇j(i𝑘) tương ứng với thuộc tính i𝑘 (1kn) trong giao dịch 𝑇j (1jm) nhận giá trị là số hoặc phân loại. Khi đó, D được gọi là CSDL định lượng.2 mô tả ví dụ về một CSDL định lượng.
Ví dụ về CSDL định lượng TID Mặt hàng đƣợc mua (kèm số lƣợng) 1 (a,10) (b,2) 2 (b,1) (c,1) 3 (d,4) (e,6) 4 (a,1) (b,4) (c,5) 5 (b,3) Trong ví dụ này, các mục trở thành các thuộc tính nhận giá trị số biểu diễn số lượng các mặt hàng được mua. Chẳng hạn, tại giao dịch đầu tiên (TID=1), mặt hàng a được mua với số lượng là 10, b được mua với số lượng là 2. Để phát hiện các luật kết hợp trong các CSDL định lượng người ta thường sử dụng hai cách tiếp cận giải quyết như sau: Thứ nhất: Rời rạc hóa các thuộc tính định lượng để chuyển CSDL định lượng ban đầu thành CSDL giao dịch rồi sử dụng các thuật toán đã có về phát hiện luật kết hợp trong các CSDL giao dịch để phát hiện luật kết hợp trong CSDL đã chuyển đổi [20]–[23]. Chẳng hạn, trong nghiên cứu [20], mỗi thuộc tính định lượng được phân hoạch thành các đoạn khác nhau sau đó ánh xạ các giá trị của thuộc tính đó vào các đoạn tương ứng, các đoạn này được đánh thứ tự bằng các số nguyên liên tiếp.
Sau đó phát hiện các tập phổ biến dựa trên các đoạn thu được. Cuối cùng các luật kết hợp được phát hiện dựa trên các tập phổ biến. Cách tiếp cận này có nhược điểm là xảy ra hiện tượng không tự nhiên, “sắc nét” tại các điểm giáp ranh giữa các khoảng chia [83] dẫn đến không phản ánh đúng tính chất của dữ liệu. Chẳng hạn, xét thuộc tính tuổi, nếu chia độ tuổi thành 3 loại: “Trẻ” (dưới 30 tuổi), “Trung niên” (30 đến 59 tuổi), “Già” (từ 60 tuổi) thì một người ở độ tuổi 59 sẽ được gọi là “Trung niên” nhưng người ở độ tuổi 60 lại thuộc nhóm “Già” mặc dù khoảng chênh lệch tuổi chỉ là 1 tuổi trong khi 23 người 30 tuổi và người 59 tuổi đều cùng là “Trung niên” với khoảng chênh lệch về tuổi là 29.
Thứ hai: Sử dụng lý thuyết tập mờ [84], [85] để chuyển các thuộc tính định lượng thành các thuật ngữ ngôn ngữ (linguistic terms) nhận giá trị tập mờ (gọi tắt là thuộc tính mờ). CSDL được chuyển đổi khi đó được gọi là CSDL mờ. Sau đó phát hiện các luật kết hợp trong CSDL mờ và các luật được phát hiện khi đó được gọi là luật kết hợp mờ [24]–[29].