Khai thác luật tuần tự có ràng buộc ITEMSET dựa trên tập mẫu thỏa ràng buộc

185 KHAI THÁC LUẬT TUẦN TỰ CÓ RÀNG BUỘC ITEMSET DỰA TRÊN TẬP MẪU THỎA RÀNG BUỘC Văn Thị Thiên Trang Khoa Công nghệ Thông tin, trường Đại học Công nghệ Tp. Hồ Chí Minh, Việt Nam TÓM TẮT Trong bài báo này, chúng tôi phát biểu bài toán khai thác luật tuần tự với ràng buộc Itemset ở vế trái của luật và đề xuất hai thuật toán MSRIC_R và MSRIC_P để giải quyết bài toán này. Trong đó, MSRIC_R thực hiện đưa ràng buộc vào giai đoạn sinh luật từ tập mẫu tìm được, còn MSRIC_P thực hiện ở giai đoạn tìm mẫu trước. Kết quả thực nghiệm cho thấy MSRIC_P hiệu quả hơn. In this paper, we state the problem of mining sequential rules with itemset contraint in the pre-condition of the rule and propose two algorithms, named MSRIC_R and MSRIC_P, to solve this problem. MSRIC_R algorithm puts the constraints into the rule generating process, and MSRIC_P puts into the pattern mining process. The experimental results show that MSRIC_P is more efficient than the other in all cases examined in this work. Key words: Sequential rule, constraint, sequential pattern, prefix-tree, sequence database. 1. GIỚI THIỆU Luật tuần tự được sinh từ mẫu tuần tự, nó biểu diễn mối quan hệ giữa hai loạt sự kiện, loạt sự kiện này sẽ xảy ra sau loạt sự kiện kia. Một luật khai thác được sẽ biểu diễn dưới dạng   , nghĩa là nếu X có mặt trong một chuỗi bất kỳ của cơ sở dữ liệu (CSDL) thì với một độ tin cậy cao có thể khẳng định Y cũng xuất hiện trong chuỗi đó theo sau X. Nó được ứng dụng trong việc dò lỗi, phát hiện xâm nhập và bẫy lỗi, trong lĩnh vực y dược, thương mại điện tử. Tùy thuộc vào từng lĩnh vực ứng dụng, nhu cầu khai thác luật tuần tự cũng khác nhau. Nếu khai thác trả về tập đầy đủ các luật tuần tự thì tốn nhiều thời gian và bộ nhớ. Một số nghiên cứu tiến hành khai thác luật tuần tự không dư thừa nhằm tìm ra những luật tổng quát nhất, thu gọn số lượng tập luật khai thác được. Tuy nhiên, nếu khai thác theo yêu cầu người dùng thì luật tuần tự tổng quát và luật tuần tự không dư thừa không đáp ứng được. Do đó, trong bài báo này, chúng tôi đề xuất bài toán khai thác luật tuần tự có ràng buộc. Ràng buộc đại diện cho yêu cầu và mối quan tâm của người dùng. Vì luật có dạng left  right, ràng buộc có thể xảy ra ở vế trái hoặc vế phải hoặc cả hai. Trong nghiên cứu này, chúng tôi tìm hiểu ràng buộc trên vế trái, đó là vế trái phải chứa một trong số các itemset do người dùng chỉ ra. Ví dụ, trong lĩnh vực y học, chuyên gia cần biết nếu bệnh nhân ung thư có các triệu chứng {đau ngực, ho, nổi hạch} thì triệu chứng phổ biến ở giai đoạn tiếp theo là gì, từ đó đưa ra các chẩn đoán và điều trị phù hợp. Khi đó, bài toán đặt ra là cần tìm những luật mà vế trái có chứa tập {đau ngực, ho, nổi hạch}. Có hai hướng giải quyết bài toán này: 1. Đưa ràng buộc vào sau quá trình khai thác: Tìm ra tập luật đầy đủ, sau đó kiểm tra ràng buộc trên từng luật để chọn ra các luật thỏa ràng buộc; 2. Đưa ràng buộc vào trong quá trình khai thác: Chỉ tìm những luật thỏa ràng buộc ngay trong quá trình khai thác. 186 Ta thấy hướng giải quyết thứ nhất tốn thời gian và bộ nhớ hơn vì phương pháp này phải tìm tập mẫu đầy đủ và tập luật đầy đủ nên đòi hỏi nhiều thời gian và bộ nhớ. Hơn nữa, nó phải tốn thêm thời gian kiểm tra ràng buộc cho từng luật trong tập luật đầy đủ tìm được. Hướng giải quyết thứ hai là đưa ràng buộc vào ngay trong quá trình khai thác, có thể đưa ràng buộc vào giai đoạn sinh luật hoặc giai đoạn tìm mẫu. Như vậy, để giải quyết bài toán khai thác luật với ràng buộc Itemset ở vế trái, chúng tôi thực hiện đưa ràng buộc vào ngay trong quá trình khai thác, trên cả hai cách đưa ràng buộc vào giai đoạn tìm mẫu và giai đoạn sinh luật. Từ đó, đối chiếu so sánh và đưa ra phương pháp tối ưu. 2. CÁC ĐỊNH NGHĨA VÀ PHÁT BIỂU BÀI TOÁN Cho tập I = {i1, i2, , im} gồm m phần tử còn gọi là các item. Itemset: Một itemset là một tập không có thứ tự khác rỗng, gồm các item thuộc tập I, ký hiệu là (i1, i2, , ik ) với mỗi ij (1  j  k) là một item. Chuỗi: Một chuỗi (sequence) là một danh sách có thứ tự các itemset. Chuỗi S được ký hiệu là s1 s2 sn với mỗi si (1  i  n) là một itemset. Chiều dài của chuỗi là tổng số item có trong chuỗi. Chuỗi có chiều dài k còn được gọi là k-sequence. Chuỗi con: Chuỗi Sa = a1 a2 an được gọi là chuỗi con của chuỗi Sb =b1 b2 bm ký hiệu Sa  Sb, nếu tồn tại các số nguyên 1  j1 < j2 < < jn  m sao cho a1  bj1, a2  bj2, , an  bjn. Cơ sở dữ liệu chuỗi: Cơ sở dữ liệu chuỗi SDB là một tập hợp các chuỗi dữ liệu có dạng (sid, s), trong đó sid là định danh của chuỗi và s là chuỗi các itemset. Độ phổ biến: Độ phổ biến (support) của một mẫu p là số lượng chuỗi trong CSDL chuỗi SDB có chứa p, ký hiệu ( ) |* |  +|. Mẫu tuần tự: Cho trước một ngưỡng phổ biến tối thiểu (minSup) do người dùng qui định, minSup  0, 1. Một mẫu p được gọi là phổ biến nếu sup(p)  minSup, khi đó p được gọi là mẫu tuần tự. Như vậy, mẫu tuần tự là một chuỗi con phổ biến tìm được trong CSDL. Tiền tố hoàn toàn, hậu tố. Chuỗi Sa = a1 a2 an được gọi là tiền tố hoàn toàn của chuỗi Sb =b1 b2 bm (n < m), nếu và chỉ nếu ai = bi với mọi 1  i  n. Kí hiệu: Sa » Sb Sau khi loại bỏ phần tiền tố hoàn toàn Sb trên chuỗi Sa, phần chuỗi còn lại được gọi là hậu tố của Sa. Từ định nghĩa chuỗi con, ta có tiền tố Sa  Sb. Từ định nghĩa ta thấy rằng nếu một chuỗi có kích thước k sẽ có (k-1) tiền tố hoàn toàn. Ví dụ, chuỗi A(BC)D có 3 tiền tố là A, AB và A(BC) nhưng chỉ có 2 tiền tố hoàn toàn là A và A(BC). Do đó, (BC)D là hậu tố đối với A và D là hậu tố đối với A(BC). Luật tuần tự biểu diễn mối quan hệ giữa hai loạt sự kiện xảy ra tuần tự, biểu thị dưới dạng XY (sup, conf), trong đó X là loạt sự kiện xảy ra trước, Y là loạt sự kiện xảy ra sau, sup là giá trị độ phổ biến và conf là giá trị độ tin cậy của luật. Từ mẫu tuần tự đã có, luật tuần tự r được xây dựng bằng cách tách mẫu tuần tự ra làm hai phần: phần tiền tố X và phần hậu tố Y (nối tiền tố với hậu tố: X++Y, ta được mẫu tuần tự như ban đầu). Độ phổ biến và độ tin cậy của luật được xác định như sau: Độ phổ biến: sup(r) = sup(X++Y)  100%. Độ tin cậy: conf(r) = sup(X++Y) / sup(X)  100%. Độ phổ biến của một luật bằng số chuỗi trong CSDL có chứa mẫu tuần tự tạo nên luật. Độ tin cậy của luật bằng với khả năng chuỗi trong CSDL có chứa tiền tố của luật dẫn đến chứa hậu tố của luật. 187 Với mỗi mẫu tuần tự kích thước k, có thể tạo ra (k-1) luật vì mẫu tuần tự kích thước k sẽ có (k-1) tiền tố. Ví dụ, với mẫu tuần tự (A)(BC)(D) có kích thước là 3, có thể tạo ra 2 luật là (A)(BC)(D), (A)(BC)(D). Bài toán khai thác luật tuần tự với ràng buộc itemset: Mẫu thỏa ràng buộc: Mẫu a1 a2 an được coi là chứa itemset c nếu i  [1, n] sao cho c  ai. Luật thỏa ràng buộc: Cho một ràng buộc c, và luật r = a1 a2 an  b1 b2 bm, nếu vế trái luật a1 a2 an có chứa itemset c thì r được gọi là luật thỏa-c. Cho CSDL SDB, tập itemset ràng buộc ℂ = {c1, c2... ck}, ngưỡng phổ biến tối thiểu minSup và ngưỡng tin cậy tối thiểu minConf do người dùng chỉ ra. Bài toán khai thác luật tuần tự với ràng buộc itemset là đi tìm tất cả các luật thỏa mãn các ngưỡng minSup và minConf, trong đó vế trái của luật có chứa bất kỳ itemset nào của tập ℂ. R = {r: XY| sup(r)  minSup conf(r)  minConf i: 1  i  k, X  ci, ci  ℂ}. 3. CÁC NGHIÊN CỨU LIÊN QUAN Phương pháp khai thác tập luật tuần tự đầy đủ đầu tiên được đề xuất bởi Spiliopoulou [[1]]. Sau đó được khái quát thành thuật toán Full bởi Lo và đồng sự, thuật toán này cố gắng tìm tất cả các luật từ các mẫu tuần tự khai thác được. Khi sinh luật từ một mẫu tuần tự, độ tin cậy của luật phụ thuộc vào độ phổ biến của tiền tố. Do đó, với mỗi tiền tố của một mẫu tuần tự, ta phải lấy được độ phổ biến của tiền tố. Thuật toán Full xác định độ phổ biến của tiền tố bằng cách duyệt toàn bộ tập mẫu tuần tự nên tốn nhiều thời gian. Một số thuật toán cải tiến thuật toán Full như MSR_PreTree [[4]], IMSR_PreTree [[5]] bằng cách sử dụng đặc điểm của cấu trúc cây tiền tố. Dựa trên cây tiền tố, các thuật toán này sẽ tạo ra các luật đáng tin cậy từ mẫu tuần tự mà không cần duyệt lại tập mẫu tuần tự nhiều lần. Trong bài báo này, chúng tôi cũng áp dụng cấu trúc dữ liệu cây tiền tố để sinh các luật thỏa ràng buộc itemset. 4. PHƢƠNG PHÁP ĐỀ XUẤT Để giải quyết bài toán khai thác luật tuần tự với ràng buộc itemset ở vế trái luật, bài báo đề xuất hai thuật toán có tên MSRIC-R và MSRIC-P, sử dụng cấu trúc cây tiền tố để lưu tập mẫu tuần tự phổ biến tìm được và tiến hành sinh luật trực tiếp từ cây này. Cả hai thuật toán đều thực hiện đưa ràng buộc vào trong quá trình khai thác. Với MSRIC-R đưa ràng buộc vào giai đoạn sinh luật, MSRIC-P đưa ràng buộc vào giai đoạn tìm mẫu. 4.1. Cấu trúc cây tiền tố Cây tiền tố là một cây có thứ tự, trong đó quan hệ giữa nút cha với nút con tương ứng là quan hệ giữa chuỗi con và chuỗi cha. Cây tiền tố được xây dựng như sau: nút gốc được gán nhãn là một chuỗi rỗng , mỗi nút ở mức k được gán nhãn là một mẫu độ dài k. Mở rộng các mẫu độ dài k bằng cách thêm vào 1 item phổ biến ta được các nút cho mức (k + 1) tiếp theo. Có hai cách mở rộng: mở rộng sequence (item được thêm vào mẫu đóng vai trò là một itemset mới) và mở rộng itemset (item được thêm vào itemset cuối của mẫu). Tính chất cây tiền tố: Mẫu X tại nút bất kỳ (trừ nút gốc) là tiền tố của tất cả các mẫu nằm trên các cây con có gốc là các nút đã mở rộng sequence của X [[4]]. Các mẫu này có dạng X a1 a2 am (với ai là các itemset). 188 4.2. Thuật toán MSRIC-R Thuật toán MSRIC-R đưa ràng buộc vào giai đoạn sinh luật dựa trên ý tưởng chính sau: một mẫu X trên cây là tiền tố hoàn toàn của tất cả các mẫu nằm trên các cây con có gốc là những nút mở rộng sequence của X; vì vậy, tiến hành sinh luật từ tất cả các mẫu X a1 a2 am (m > 0) nằm trên những cây con này với vế trái luật là X. Khi đó, luật sinh được có dạng X  a1 a2 am. Lưu ý rằng, luật tạo ra phải thỏa ràng buộc itemset ở vế trái, do đó phải kiểm tra mẫu X có chứa itemset ràng buộc không. Để tránh phải kiểm tra ràng buộc cho mọi mẫu ở vế trái luật, chúng tôi đề xuất mệnh đề sau. Mệnh đề 1 (Kiểm tra ràng buộc trên luật). Lấy X là một mẫu trên cây tiền tố, Y là nút mở rộng của X, ST(Y) là cây con có gốc tại Y. Nếu X chứa itemset c thì mẫu P cũng chứa itemset c, P  ST(Y). Chứng minh: Vì Y là nút mở rộng của X nên theo định nghĩa mở rộng mẫu ta có X  Y. P  ST(Y), Y  P (theo cách xây dựng cây tiền tố). Do đó, X  P (1). Theo giả thiết, X chứa itemset c tức i  [1, size(X)], c  xi  X (2). Từ (1) và (2) ta có P chứa c. Dựa vào mệnh 1, thuật toán MSRIC-R có thể sinh luật trực tiếp từ các mẫu và bỏ qua bước kiểm tra ràng buộc cho một số lượng lớn các luật. Mã giả của thuật toán được trình bày ở Bảng 1. Trước hết, thuật toán tìm tập tất cả các mẫu tuần tự, áp dụng phương pháp vector bit động và cấu trúc cây tiền tố. Kết quả là tập các mẫu tuần tự được lưu trữ trên cây tiền tố (dòng 2). Tại mức 1 của cây tiền tố, với mỗi cây con gốc tại atom, sinh luật tuần tự ứng với từng cây con bằng cách gọi thủ tục MINE-RULE-CHECK (dòng 3 - 4) như sau: Lấy X là mẫu tại nút gốc root, nếu X có chứa một trong số itemset ràng buộc thì luật có vế trái là X sẽ thỏa ràng buộc. Do đó, thuật toán sinh các luật với vế trái là X, từ các mẫu trên các cây con mở rộng sequence của X vì các mẫu này đều có tiền tố hoàn toàn là X bằng cách gọi thủ tục GENERATE-RULES (dòng 7). Tất cả các nút mở rộng của nút gốc root hiện thời sẽ trở thành tiền tố của những cây con ở mức kế tiếp, vì vậy gọi đệ quy thủ tục này với từng nút con của root, bao gồm nút con mở rộng sequence và itemset (dòng 9 -16). Tuy nhiên, theo Mệnh đề 1, nếu X chứa itemset ràng buộc thì mọi mẫu thuộc cây con mở rộng từ X cũng vậy. Do đó, khi gọi đệ quy thủ tục ta không cần kiểm tra ràng buộc nữa. Thủ tục MINE-RULE tương tự thủ tục MINE-RULE-CHECK, và chỉ khác ở chỗ bỏ qua bước kiểm tra ràng buộc. Quá trình đệ quy này được lặp lại cho đến mức cuối cùng của cây. Bảng 1. Thuật toán MSRIC-R. Thuật toán MSRIC-R 1. Duyệt CSDL chuỗi tìm F1 và tìm itemset phổ biến trong ℂ ; 2. Phát triễn mẫu từ F1, tìm FP = Tất cả các mẫu có support  minSup, lưu trữ trên cây tiền tố; 3. For each node atom at level 1 in FP do 4. MINE-RULE-CHECK(atom); MINE-RULE-CHECK(root): 5. Lấy Seq-Set = Mở rộng sequence của nút root; Lấy Items-Set = Mở rộng itemset của nút root; 6. If (X = mẫu tại root có chứa itemset c  ℂ ) then 7. For each node nseq in Seq-set do 8. Gọi thủ tục GENERATE-RULES(X, ST(nseq)); 9. Gọi thủ tục MINE-RULE(nseq); 10. For each node nitem in Items-Set do 11. Gọi thủ tục MINE-RULE(nitem); 12. If (X không thỏa ràng buộc c nào, c  ℂ ) then 13. For each node nseq in Seq-set do 189 14. Gọi thủ tục MINE-RULE-CHECK(nseq); 15. For each node nitem in Items-Set do 16. Gọi thủ tục MINE-RULE-CHECK(nitem); GENERATE-RULES(X, ST(nseq)) 1. For each pattern p in ST(nseq) do 2. Tạo luật r = X  Y, với X++Y = p; 3. If (sup(p)/sup(X)  minConf) then R = R  {r}; 4. Else Dừng sinh luật với mọi nút con mở rộng từ p; 4.3. Thuật toán MSRIC-P Thuật toán MSRIC-P đưa ràng buộc vào trong quá trình khai thác, tuy nhiên đưa ở giai đoạn khai thác mẫu. Thuật toán MSRIC-P sẽ sinh trực tiếp ra mọi luật thỏa ràng buộc ngay lập tức từ tập mẫu thỏa ràng buộc tìm được, mà không cần phải kiểm tra ràng buộc trên luật như thuật toán MSRIC-R. Mệnh đề 2 (Sinh luật thỏa ràng buộc). Lấy X là một mẫu trên cây tiền tố chứa tập mẫu FCP, Seq-T(X) là các cây con có gốc là các nút mở rộng sequence của X. Luật tạo ra từ mẫu p  Seq-T(X) với vế trái là tiền tố X là luật thỏa-c. Chứng minh: Theo giả thiết vì X  FCP nên X là mẫu thỏa-c với c  ℂ = {c1, c2... cn}. Mặt khác, p  Seq-T(X) nên ta có X » p. Suy ra p có dạng X a1 a2 am, m > 0, ai là itemset. Vậy ta tạo được luật r từ p với vế trái là tiền tố X có dạng X  a1 a2 am. Vì X là mẫu thỏa-c nên theo ta có r là luật thỏa-c. Bảng 2. Thuật toán MSRIC-P. Thuật toán MSRIC-P Đầu vào: SDB, ℂ = {c1, c2 ..., ck}, minSup, minConf. Đầu ra: CR = {r: X  Y| sup(r)  minSup conf(r)  minConf k: 1  k  n, X  ck, ck  ℂ }. 1. Duyệt CSDL chuỗi, tìm itemset trong ℂ phổ biến và tìm FCP = Tất cả các mẫu thỏa ràng buộc ℂ có support  minSup, lưu trữ trên cây tiền tố, sử dụng thuật toán MSPIC-DBV; 2. For each atom in FCP do 3. CR = CR  Gọi thủ tục MINE-RULE(atom); Thuật toán MSRIC-P cũng thực hiện sinh luật theo cách thức của MSRIC-R, đó là một mẫu X trên cây là tiền tố hoàn toàn của tất cả các mẫu nằm trên các cây con Seq-T(X); vì vậy, thực hiện sinh luật từ tất cả các mẫu p = X a1 a2 am  Seq-T(X), với vế trái luật là X. Khi đó, luật r tạo ra từ p có dạng X  a1 a2 am. Vì mẫu X  FCP nên theo Mệnh đề 2 ta có r là luật thỏa-c. Do đó, thuật toán MSRIC-P sinh được ngay tập luật thỏa ràng buộc mà không cần thực hiện giai đoạn kiểm tra ràng buộc cho tập luật sinh được như phương pháp đưa ràng buộc vào sau, và cũng không kiểm tra ràng buộc cho mỗi luật tạo ra như MSRIC- R. Thuật toán MSRIC-P được trình bày ở Bảng 2 gồm hai giai đoạn: 1. Tìm tập FCP gồm các mẫu tuần tự phổ biến thỏa ràng buộc itemset từ CSDL, lưu trên cấu trúc cây tiền tố [[3]]. 2. Sinh các luật r đáng tin cậy thỏa ràng buộc từ tập mẫu FCP. 190 5. KẾT QUẢ THỰC NGHIỆM 5.1. Dữ liệu thực nghiệm Chúng tôi tiến hành thực nghiệm trên CSDL tổng hợp C20T50S20I10N1kD100k. Vì tập itemset ràng buộc ℂ do người dùng đưa ra, để thực nghiệm tập ℂ được phát sinh ngẫu nhiên. Độ chọn lọc của ràng buộc là tỉ lệ (%) itemset được chọn để sinh tập ℂ. Kí hiệu là selectivity. Thực nghiệm so sánh thời gian thực hiện của các thuật toán: MSRIC-B (đưa ràng buộc vào sau quá trình khai thác), MSRIC-R và MSRIC-P với sự thay đổi giá trị của minSup, minConf và selectivity. 5.2. Phân tích kết quả Về hiệu quả Thực nghiệm so sánh khai thác luật tuần tự đầy đủ (không có ràng buộc) với luật có ràng buộc Itemset ở vế trái. Kết quả thực nghiệm cho thấy CR  R với ℂ  . Điều này là dĩ nhiên vì khai thác có ràng buộc chỉ trả về tập luật thỏa các ràng buộc mà người dùng yêu cầu. Về thời gian (1) Selectivity thay đổi. (2) minSup thay đổi. (3) minConf thay đổi Hình 1. So sánh thời gian khai thác luật của các thuật toán trên CSDL C20T50S20I10N1kD100k Các kết quả thực nghiệm chứng tỏ việc đưa ràng buộc vào trong quá trình khai thác hiệu quả hơn so với đưa vào sau. Hơn nữa, thời gian khai thác khi đưa ràng buộc vào giai đoạn khai thác mẫu vượt trội hơn nhiều so với đưa vào giai đoạn sinh luật. 5. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN Trong bài báo này, chúng tôi đề xuất phương pháp khai thác luật tuần tự với ràng buộc itemset ở vế trái một cách hiệu quả bằng cách đưa ràng buộc vào quá trình khai thác, với hai thuật toán MSRIC-R và MSRIC-P. Trong đó, MSRIC-P thực hiện đưa ràng buộc vào giai đoạn tìm mẫu hiệu quả hơn, chứng tỏ nên sử dụng tập mẫu thỏa ràng buộc ngay từ đầu để sinh luật có ràng buộc. Hướng phát triển tiếp theo sẽ tiến hành nghiên cứu bổ sung thêm ràng buộc tập itemset cha, ràng buộc trên vế phải của luật. 191 TÀI LIỆU THAM KHẢO [1] M. Spiliopoulou (1999), Managing Interesting Rules in Sequence Mining, Proceedings of European Conference on Principles of Data Mining and Knowledge Discovery, , pp. 554-560. [2] T. M. Thai, L. Bac, V. Bay & T.P. Hong (2016), Mining non-redundant sequential rules with dynamic bit vectors and pruning techniques, Appl. Intell. 45(2), pp. 333-342. [3] V. Trang, V. Bay, & L. Bac (2018), Mining sequential patterns with itemset constraints, Knowledge and Information Systems 57(2), pp. 311-330. [4] V. Trang, V. Bay & L. Bac (2011), Minning sequential rules based on prefix-tree, New Challenges for Intelligent Information and Database Systems. Springer Berlin Heidelberg, pp. 147-156. [5] V. Trang, V. Bay, & L. Bac (2014), IMSR_PreTree: an improved algorithm for mining sequential rules based on the prefix-tree, Vietnam Journal Computer Science 1(2), pp. 97-105.