Cấu trúc của các chuỗi phổ biến dựa trên các chuỗi đóng và chuỗi sinh

1) là lớp (con mức 2) chứa các chuỗi tạo ra từ phép bổ sung các chuỗi con của σ୧ vào chuỗi sinh γ୨ của nó. Khi đó, giữa ℱ𝒮൫σ୧, γ୨൯ và ℱ𝒮(σ୧, γ୫) vẫn có thể có phần giao chung trùng lặp (tức là, ℱ𝒮൫σ୧, γ୨൯ ∩ ℱ𝒮(σ୧, γ୫) ≠ ∅ ) với m ≠ j , γ୫ ∈ Gen(σ୧) . Với γ୨ ∈ Gen(σ୧), ∀𝛼 ∈ ℱ𝑟𝑒𝒮, định nghĩa điều kiện tỉa GenPrun như sau: GenPrun൫α, σ୧, γ୨൯ ≝ (∃γ୩ ∈ Gen(σ୧) | k < j, α ⊒ γ୩ ). (12) Gọi ℱ𝒮∗൫σ୧, γ୨൯ ≝ ቄ𝛼 ∈ ℱ𝒮∗(σ୧) ቚ α ⊒ γ୨ ∧ not ቀGenPrun൫α, σ୧, γ୨൯ቁቅ (13) là tập các chuỗi tạo ra từ chuỗi sinh γ୨. Khi đó, ℱ𝒮∗൫σ୧, γ୨൯ ∩ ℱ𝒮∗(σ୧, γ୫) = ∅ (với m ≠ j, γ୫ ∈ Gen(σ୧)) và ൛ℱ𝒮∗൫σ୧, γ୨൯, γ௝ ∈ Gen(σ୧)ൟ tạo ra một phân hoạch của ℱ𝒮∗(σ୧): ℱ𝒮∗(σ୧) = ∑ ℱ𝒮∗൫σ୧, γ୨൯ஓౠ∈ୋୣ୬(஢౟) . (14) Ví dụ 6. Ta xét quá trình phục hồi từng lớp con ℱ𝒮∗(σ୧), i=1,2,3. Xem minh họa trong Hình 3.  Vì σଵ và σଶ chỉ có một chuỗi sinh nên quá trình phục hồi ℱ𝒮∗(σଵ) và ℱ𝒮∗(σଶ) không tạo ra trùng lặp (kiểu 3). KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 25  Xét quá trình phục hồi các chuỗi thuộc lớp con ℱ𝒮∗(σଷ). Vì |Gen(σଷ)| = 3, nên quá trình phục hồi sẽ tạo ra các trùng lặp. Để thuận tiện, đặt σ = σଷ = 〈(ACE)A(AF)〉.  Đầu tiên, ta có, ℱ𝒮(σ, γଵ = 〈AAA〉) = {〈AAA〉, α = 〈AA(AF)〉, 〈(AC)AA〉, 〈(AC)A(AF)〉, 〈(AE)A(A)〉, 〈(AE)A(AF)〉, 〈(ACE)AA〉, 〈(ACE)A(AF〉} và ℱ𝒮∗(σ, γଵ) = ℱ𝒮(σ, γଵ).  Tiếp theo, FS൫σ,γ2=〈AAF〉൯={〈AAF〉, α=〈AA(AF)〉, 〈(AC)AF〉,〈(AC)A(AF)〉, 〈(AE)AF〉, 〈(AE)A(AF)〉, 〈(ACE)AF〉, 〈(ACE)A(AF)〉}. Dễ thấy rằng αtrong ℱ𝒮(σ, γଶ) đã xuất hiện trong ℱ𝒮(σ, γଵ) bởi vì bổ sung A vào đầu sự kiện cuối cùng của γଶ cũng chính là bổ sung F vào sau sự kiện cuối cùng của γଵ (tạo ra cùng α). Nếu sử dụng GenPrun trên γଵ khi thực hiện phép bổ sung vào γଶ, ta đã loại bỏ (sớm) được α vì α ⊒ γଵ. Tương tự ta cũng loại sớm được các chuỗi 〈(AC)A(AF)〉, 〈(EC)A(AF)〉và 〈(ACE)A(AF)〉. Khi đó, ℱ𝒮∗(σ, γଶ) = {〈AAF〉, 〈(AC)AF〉, 〈(AE)A(AF)〉, 〈(ACE)AF〉} và ℱ𝒮∗(σ, γଵ) ∩ ℱ𝒮∗(σ, γଶ) = ∅. Như vậy, 4 sự trùng lặp (kiểu 3) giữa các lớp con mức 2 cũng bị loại bỏ!  Sau đó, ℱ𝒮(σ, γଷ = 〈EAA〉) = 〈EAA〉, 〈EA(AF)〉, βଵ = 〈(EA)AA〉, βଶ = 〈(EA)A(AF)〉, 〈(EC)AA〉, 〈(EC)A(AF)〉, βଷ = 〈(EAC)AA〉, βସ = 〈(EAC)A(AF)〉}. Bốn chuỗi β୩, k = 1,4തതതത không vượt qua GenPrun(α, σ, γଷ) vì β୩ ⊒ γଵ. Do đó, ℱ𝒮∗(σ, γଷ) {〈EAA〉, 〈EA(AF)〉, 〈(EC)AA〉, 〈(EC)A(AF)〉}.  Cuối cùng, ℱ𝒮(σ, γସ = 〈EAF〉) = {δଵ = 〈EAF〉, δଶ = 〈EA(AF)〉, δଷ = 〈(EA)AF〉, δସ = 〈(EA)A(AF)〉, δହ = 〈(EC)AF〉, δ଺ = 〈(EC)A(AF)〉, δ଻ = 〈(EAC)AF〉, δ଼ = 〈(EAC)A(AF)〉}. Sáu chuỗi δସ, δ଼ (chứa γଵ); δଷ, δ଻ (chứa γଶ); δଶ, δ଺ (chứa γଷ) không vượt qua GenPrun(α, σ, γସ) nên chúng bị loại. Cho nên, ℱ𝒮∗(σ, γଷ) = {δଵ, δହ}. 3.3. Phân hoạch mịn tập các chuỗi phổ biến Sau khi loại bỏ được các trùng lặp (kiểu 2 và 3), ta có được một phân hoạch mịn (so với phân hoạch thô dựa trên (4)) tập ℱ𝑟𝑒𝒮 các chuỗi phổ biến. Thật vậy, từ (4), (10) và (14) ta có: ℱ𝑟𝑒𝒮 = ∑ ∑ ∑ ℱ𝒮∗൫σ௜ , γ௝൯ஓౠ∈ୋୣ୬(஢౟)ఙ೔∈େ୪୭(𝓉𝓈)𝓉𝓈∈𝒯𝒮 . (15) Điều đó có nghĩa là, ൛ℱ𝒮∗൫σ௜ , γ௝൯, 𝓉𝓈 ∈ 𝒯𝒮, 𝜎௜ ∈ Clo(𝓉𝓈), γ୨ ∈ Gen(σ୧)ൟ tạo ra một phân hoạch mịn của ℱ𝑟𝑒𝒮. Dựa vào nó, ta có thể phục hồi nhanh tất cả các chuỗi phổ biến chỉ dựa vào lớp ℱ𝒞𝑙𝑜𝒮 các chuỗi phổ biến đóng và lớp ℱ𝒢𝑒𝑛𝒮 các chuỗi sinh phổ biến mà không cần quét lại CSDL. KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 26 Ví dụ 7. Như vậy là dựa vào tất cả 3 chuỗi phổ biến đóng σଵ , σଶ và σଷ (của Clo(𝓉𝓈ଶ)); tất cả 5 chuỗi sinh phổ biến γ, γଵ, γଶ, γଷ, γସ (của Gen(σ୧), i=1,2,3); và (15) ta đã phục hồi 27 chuỗi thuộc lớp tương đương ℱ𝒮(𝓉𝓈ଶ). Trong quá trình phục hồi ta đã tỉa sớm được 16 (=2+4+4+6, xem Ví dụ 5 và 6) chuỗi trùng lặp, đạt tỉ lệ 80% (16/(27-(3+4)))! Với cách làm tương tự, ta tiếp tục phục hồi 1049 chuỗi thuộc lớp tương đương ℱ𝒮(𝓉𝓈ଵ) và 48 chuỗi thuộc các lớp tương đương ℱ𝒮(𝓉𝓈௞), k = 3,6തതതത. Khi đó, ta thu được |ℱ𝑟𝑒𝒮| = 1124 từ |ℱ𝒞𝑙𝑜𝒮| = 16 chuỗi phổ biến đóng và |ℱ𝒢𝑒𝑛𝒮| = 20 chuỗi sinh phổ biến mà không cần quét lại CSDL! 4. KẾT LUẬN Báo cáo này đề xuất một tiếp cận dựa trên phân hoạch để phục hồi tất các chuỗi phổ biến từ các chuỗi phổ biến đóng và các chuỗi sinh phổ biến. Trước hết, tập tất cả các chuỗi phổ biến được phân hoạch (thô) thành các lớp tương đương, mỗi lớp chứa các chuỗi cùng xuất hiện trong một tập chuỗi đầu vào, do đó, có cùng độ hỗ trợ. Quá trình phục hồi chuỗi dựa trên phân hoạch này có hai ưu điểm: (1) tiết kiệm được tính toán và lưu trữ trùng lặp độ hỗ trợ của các chuỗi, (2) loại bỏ được sự trùng lặp trong quá trình phục hồi các chuỗi từ các lớp tương đương khác nhau. Không mất tổng quát, ta chỉ cần xét việc phục hồi độc lập các chuỗi phổ biến trong mỗi lớp tương đương dựa vào thông tin cốt lõi là các chuỗi đóng và chuỗi sinh trong lớp. Để tạo ra một chuỗi phổ biến trong lớp ta chỉ cần bổ sung một cách phù hợp các chuỗi con của các chuỗi đóng thêm vào các chuỗi sinh. Đáng tiếc là, quá trình này vẫn tạo ra các chuỗi trùng lặp. Vì vậy, tiếp theo ta cần hiểu rõ cấu trúc bên trong của mỗi lớp. Mỗi lớp chuỗi phổ biến tương đương tiếp tục được phân hoạch thành các lớp con (mức 1) dựa vào các chuỗi đóng trong lớp và điều kiện tỉa CloPrun. Khi đó, quá trình phục hồi các chuỗi trong mỗi lớp con là độc lập (không trùng lặp với các lớp con khác). Tuy nhiên, tiến trình tạo ra các chuỗi trong một lớp con vẫn chứa trùng lặp. Nguyên nhân là chuỗi đóng đại diện cho lớp con có nhiều chuỗi sinh và việc bổ sung các chuỗi con khác nhau vào các chuỗi sinh khác nhau có thể tạo ra cùng chuỗi kết quả. Để loại bỏ sớm các trùng lặp kiểu này, mỗi lớp con mức 1 lại tiếp tục được phân hoạch thành các lớp con (mức 2) dựa vào các chuỗi sinh của lớp và điều kiện tỉa GenPrun. Cuối cùng, ta thu được một phân hoạch mịn hơn của tập tất cả các chuỗi phổ biến. Liệu rằng có còn xảy ra trùng lặp trong quá trình phục hồi mỗi lớp con mức 2 hay không? Nếu có thì cách khắc phục là gì? Trong các nghiên cứu tiếp theo, chúng tôi sẽ cố gắng tìm các câu trả lời cho chúng. LỜI CẢM ƠN Nhóm tác giả gửi lời cảm ơn đến Trường Đại học Đà lạt đã tài trợ kinh phí, tạo điều kiện cho nghiên cứu trong khuôn khổ đề tài nghiên cứu khoa học cấp trường năm 2018. TÀI LIỆU THAM KHẢO Agrawal, R., Srikant, R. (1995). Mining sequential patterns. Proceedings of the eleventh international conference on data engineering, washington, dc, 3–14. KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 27 Ayres, J., Flannick, J., Gehrke, J., Yiu, T. (2002). Sequential pattern mining using a bitmap representation. Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’02, New York, NY, 429–435. Birkhoff, G. (1967). Lattice theory, 3rd edition. American mathematical society, providence, ri. Dương, V.H., Trương, C.T., Lê, H.B. (2018). Efficient algorithms for simultaneously mining concise representations of sequential patterns based on extended pruning conditions. International journal engineering applications of artificial intelligence 67, 197-210. Gomariz, A., Campos, M., Marin, R., & Goethals, B. (2013). ClaSP: An Efficient Algorithm for Mining Frequent Closed Sequences. Proceedings of 17th Pacific- Asia Conference, PAKDD '13, Gold Coast, Australia, pp.50–61. Han, J., & Kamber M. (2000). Data Mining Concepts and Techniques. Morgan Kanufmann. Lê, H.B., Dương, V.H., Trương, C.T., & Philip, F.V. (2017). FCloSM, FGenSM: Two Efficient Algorithms for Mining Frequent Closed and Generator Sequences using the Local Pruning Strategy. International Journal of Knowledge and Information Systems (KAIS) 53(1), 71-107. Pei, J., Han, J., Mortazavi-Asl, B., Wang, J., Pinto, H., Chen, Q., Dayal, U., & Hsu, M. (2004). Mining sequential patterns by pattern-growth: the PrefixSpan approach. Journal IEEE Transactions on Knowledge and Data Engineering 16(11), 1424– 1440. Philip, F.V., Gomariz, A., Campos, M., & Thomas, R. (2014a). Fast Vertical Mining of Sequential Patterns Using Co-occurrence Information. Proceedings of 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD '2014, 40–52. Philip, F.V., Gomariz, A., Šebek, M., & Hlosta, M. (2014b). VGEN: Fast Vertical Mining of Sequential Generator Patterns. Proceedings of 16th International Conference on Data Warehousing and Knowledge Discovery, DWKD'14, Munich, Germany, 476-488. Wang, J., Han, J., Chun, L. (2007). Frequent closed sequence mining without candidate maintenance. IEEE Trans. Knowledge and Data Eng. 19(8), 1042-1056. Yan, X., Han, J., Afshar, R. (2003). CloSpan: Mining closed sequential patterns in large datasets. Proceedings of the 2003 SIAM International Conference on Data Mining, 166–177. Zaki, M.J. (2001). SPADE: An efficient algorithm for mining frequent sequences. Machine Learning 42(1), 31–60.