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

Chia sẻ: Vương Tâm Lăng | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

13
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết này chỉ ra cấu trúc của các chuỗi phổ biến dựa trên các chuỗi phổ biến đóng và các chuỗi sinh phổ biến. Dựa trên cấu trúc này, ta có thể phục hồi tất cả 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 mà không cần quét lại cơ sở dữ liệu. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 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 Tô Lan Nhia, Trần Ngọc Anha*, Dương Văn Hảia, Trương Chí Tína a Khoa Toán - Tin học, Trường Đại học Đà Lạt, Lâm Đồng, Việt Nam * Tác giả liên hệ: Email: anhtndalat@gmail.com Tóm tắt Bài toán khai thác các chuỗi phổ biến từ các cơ sở dữ liệu có nhiều ứng dụng trong thực tiễn như thương mại, truyền thông, kinh tế, v.v. Khó khăn lớn nhất của bài toán là không gian tìm kiếm và lực lượng của tập các chuỗi phổ biến thường rất lớn (đặc biệt trên các cơ sở dữ liệu lớn với các ngưỡng phổ biến tối thiểu bé). Các thuật toán khai thác chúng thường tiêu tốn quá nhiều thời gian và bộ nhớ. Ngoài ra, người sử dụng khó khăn trong việc hiểu và quản lý số lượng quá lớn tập này. Gần đây, một số tác giả đã đề xuất việc khai thác các chuỗi phổ biến đóng và các chuỗi sinh phổ biến với số lượng thường bé hơn hẳn so với số lượng các chuỗi phổ biến. Các tác giả đã chỉ ra rằng, từ chúng, ta có thể thu được tất cả các chuỗi phổ biến khác, tuy nhiên, chưa có một thuật toán tương ứng nào được đề xuất. Bài bào này chỉ ra cấu trúc của các chuỗi phổ biến dựa trên các chuỗi phổ biến đóng và các chuỗi sinh phổ biến. Dựa trên cấu trúc này, ta có thể phục hồi tất cả 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 mà không cần quét lại cơ sở dữ liệu. Quá trình phục hồi này có thể tạo ra nhiều chuỗi trùng lặp, do đó, ta phải tốn bộ nhớ để lưu trữ và mất thời gian kiểm tra để loại bỏ chúng. Để khắc phục khó khăn này, báo cáo đề xuất hai điều kiện để tỉa sớm các chuỗi phổ biến trùng lặp trong quá trình phục hồi. Từ khóa: Khai thác chuỗi phổ biến; chuỗi phổ biến đóng; chuỗi sinh phổ biến. 15
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 STRUCTURE OF FREQUENT SEQUENCES BASED ON FREQUENT CLOSED SEQUENCES AND FREQUENT GENERATORS Tô Lan Nhia, Tran Ngọc Anha*, Duong Van Haia, Truong Chi Tina a The Faculty of Mathematics and Computer Science, Dalat University, Lamdong, Vietnam * Corresponding author: Email: anhtndalat@gmail.com Abstract Frequent sequence mining from database has many real applications such as communication, business, economic, etc. The main difficulty of the problem is that the search space and the cardinality of the set of frequent sequences are often enormous (especially on big databases with small minimum support thresholds). The proposed algorithms for mining them consume much memory and time. Furthermore, it is hard to the users for understanding and processing the result. Recently, some authors propose the mining of frequent closed sequences and generators of which the cardinalities are usually smaller than that of frequent sequences. They also show that, based on them, we can recover all remaining frequent sequences. However, there is no algorithm for doing that. The paper gives the structure of frequent sequences based on frequent closed sequences and frequent generators. Thanks to the structure, all frequent sequences can be recovered without accessing the database. Since the recovery can make many duplications, it needs to save and check to eliminate them. To overcome this drawback, the paper proposes two pruning conditions and uses them to early prune duplications in the progress of recovering frequent sequences. Keywords: Frequent sequence mining; frequent closed sequence; generator. 16
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 1. GIỚI THIỆU Khai thác dữ liệu là tiến trình rút trích các thông tin hoặc mẫu hữu ích (tường minh, không tầm thường, chưa được biết trước đây) từ các nguồn dữ liệu lớn (như: các cơ sở dữ liệu, các kho dữ liệu) thu thập được từ các ngành khoa học, kinh doanh và kỹ thuật. Khai thác dữ liệu là một phần cơ bản trong quá trình khám phá tri thức từ dữ liệu. Quá trình này thường chứa ba bước (Han và Kamber, 2000). Ở bước đầu tiên, dữ liệu được xử lý thô qua các công đoạn sau: làm sạch dữ liệu, tích hợp dữ liệu, chọn các đặc trưng hữu ích, rút gọn số biến/số chiều dữ liệu, biến đổi/rời rạc hóa dữ liệu. Sau đó, các thuật toán khai thác dữ liệu được áp dụng để rút trích ra các thông tin, tri thức tiềm ẩn. Kết quả khai thác được đánh giá ở bước hậu xử lý dựa trên yêu cầu của người sử dụng hoặc tri thức biết trước. Nếu kết quả không phù hợp, ta cần lặp lại quá trình. Khai thác chuỗi phổ biến (Agrawal và Srikant, 1995) là một bài toán khó, đóng vai trò quan trọng trong khai thác dữ liệu và có nhiều ứng dụng rộng rãi trong truyền thông, thương mại, v.v. Đã có nhiều thuật toán được đề xuất để khai thác các chuỗi phổ biến từ các cơ sở dữ liệu. Thuật toán PrefixSpan (Pei và ctg, 2004) sử dụng định dạng dữ liệu theo chiều ngang, tiếp cận phát triển mẫu và các cơ sở dữ liệu chiếu. Các thuật toán SPADE (Zaki, 2001), SPAM (Ayres và ctg, 2002) sử dụng định dạng theo chiều dọc và cấu trúc bitmap. Những cải tiến của chúng như CM-SPADE, CM-SPAM (Philip và ctg, 2014a) sử dụng thông tin đồng xuất hiện của các cặp thuộc tính phổ biến để tỉa sớm các chuỗi cha không phổ biến. Điểm chung của các thuật toán đã đề cập ở trên là khai thác các chuỗi phổ biến trực tiếp từ cơ sở dữ liệu. Tuy nhiên, trên các cơ sở dữ liệu lớn, đặc biệt với các ngưỡng hỗ trợ tối thiểu bé, không gian tìm kiếm và lực lượng của tập các chuỗi phổ biến (ký hiệu là ℱ𝑟𝑒𝒮) quá lớn. Do đó, các thuật toán tiêu tốn quá nhiều bộ nhớ và chạy rất lâu trước khi cho ra kết quả. Một tiếp cận gần đây hướng về việc tìm tập các chuỗi phổ biến tối đại (ký hiệu là ℱℳ𝑎𝑥𝒮) và sử dụng nó để tìm các chuỗi phổ biến. Chúng không chỉ cho phép rút gọn việc tính toán và lưu trữ mà còn giúp phân tích kết quả dễ dàng hơn. Các chuỗi phổ biến tối đại (mọi chuỗi cha thật sự của một chuỗi phổ biến tối đại đều không là chuỗi phổ biến) với số lượng bé hơn nhiều có thể xác định được lớp tất cả các chuỗi phổ biến (nhờ tính chất Apriori: mọi tập con của một chuỗi phổ biến cũng là một chuỗi phổ biến với độ hỗ trợ lớn hơn hoặc bằng nó). Tuy nhiên, vì có nhiều chuỗi phổ biến có thể được khai thác trùng lặp (từ các chuỗi phổ biến tối đại khác nhau) và đánh mất thông tin về độ hỗ trợ nên ℱℳ𝑎𝑥𝒮 không phù hợp cho việc tìm ℱ𝑟𝑒𝒮. Xuất phát từ lý thuyết dàn (Birkhoff, 1967), các nghiên cứu gần đây tập trung vào nghiên cứu các chuỗi phổ biến đóng. Một chuỗi là phổ biến đóng nếu không có chuỗi phổ biến cha nào có cùng độ hỗ trợ. Nhờ đặc tính này, với một số lượng vừa phải, không quá nhỏ như số các chuỗi phổ biến tối đại (thiếu thông tin cốt yếu về độ hỗ trợ), cũng không quá lớn như số các chuỗi phổ biến (thông tin về độ hỗ trợ bị lưu trữ trùng lặp), tập các chuỗi phổ biến đóng (ký hiệu là ℱ𝒞𝑙𝑜𝒮) rất phù hợp với việc khai thác chuỗi phổ biến. Từ một chuỗi phổ biến đóng, ta có thể dẫn ra một nhóm các chuỗi phổ biến con khác có cùng độ hỗ trợ, nói cách khác từ ℱ𝒞𝑙𝑜𝒮 ta có thể dẫn ra ℱ𝑟𝑒𝒮. Các thuật toán tiêu biểu tìm ℱ𝒞𝑙𝑜𝒮 là Clospan (Yan, Han & Afshar, 2003), BIDE (Wang, Han & Chun, 2007), 17
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 ClaSP (Gomariz và ctg, 2013), CM-ClaSP (Philip và ctg, 2014) và FCloSM (Lê và ctg, 2017). Có thể xem tập các chuỗi phổ biến đóng là một biểu diễn đặc thích hợp (đã so sánh với ℱℳ𝑎𝑥𝒮) cho tập các chuỗi phổ biến. Trong nhiều nghiên cứu gần đây, các tác giả rất quan tâm đến tập ℱ𝒢𝑒𝑛𝒮 các chuỗi phổ biến mà mỗi trong chúng không có chuỗi phổ biến con nào có cùng độ hỗ trợ. Một chuỗi phổ biến như thế được gọi là một chuỗi sinh phổ biến. Hai thuật toán tiêu biểu tìm ℱ𝒢𝑒𝑛𝒮 là VGEN (Philip và ctg, 2014b) và FGenSM (Lê và ctg, 2017). Với lực lượng thường rất nhỏ so với lực lượng của ℱ𝑟𝑒𝒮, việc khai thác ℱ𝒢𝑒𝑛𝒮 và ℱ𝒞𝑙𝑜𝒮 thường diễn ra nhanh chóng và ít tốn bộ nhớ. Một thuật toán hiệu quả tìm đồng thời cả hai tập này được đề xuất gần đây là FGenCloSM (Dương, Trương và Lê, 2018). Một khi đã tìm được chúng, ta có thể biết được ℱ𝑟𝑒𝒮. Câu hỏi đặt ra là, làm thế nào xác định (phục hồi) tất cả các chuỗi phổ biến thuộc ℱ𝑟𝑒𝒮 từ ℱ𝒢𝑒𝑛𝒮 và ℱ𝒞𝑙𝑜𝒮 mà không phải quét lại các cơ sở dữ liệu? Để trả lời câu hỏi này, chúng ta cần biết cấu trúc của các chuỗi phổ biến dựa trên các chuỗi phổ biến đóng và các chuỗi sinh phổ biến. Đây cũng chính là mục tiêu của báo cáo này. Trong quá trình phục hồi, ta có thể sinh trùng lặp các chuỗi phổ biến, do đó, ta phải tốn bộ nhớ để lưu trữ và mất thời gian kiểm tra để loại bỏ chúng. Để vượt qua, báo cáo đề xuất hai điều kiện để tỉa sớm các trùng lặp trong quá trình phục hồi. Phần còn lại của báo cáo gồm ba mục. Ở mục 2, sau khi nhắc lại vài khái niệm cơ sở, báo cáo đưa ra một quan hệ tương đương trên các chuỗi phổ biến và sử dụng nó để phân hoạch tập tất cả các chuỗi phổ biến ℱ𝑟𝑒𝒮 thành các lớp tương đương. Mục 3 đưa ra cấu trúc mỗi lớp tương đương các chuỗi phổ biến dựa vào các chuỗi đóng và các chuỗi sinh trong lớp. Nhờ cấu trúc này, ta hạn chế được đáng kể các trùng lặp xảy ra trong quá trình phục hồi 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. Mục cuối cùng là kết luận. 2. PHÂN HOẠCH TẬP CÁC CHUỖI PHỔ BIẾN THÀNH CÁC LỚP TƯƠNG ĐƯƠNG 2.1. Một số khái niệm và ký hiệu Gọi ℐ = {i , i , … , i } là tập m các thuộc tính phân biệt. Một tập con của ℐ được gọi là một sự kiện. Sự kiện có nhiều hơn một thuộc tính được viết trong cặp dấu ( ) và không có phân cách giữa các thuộc tính. Với sự kiện chỉ có một thuộc tính, đơn giản ta chỉ viết thuộc tính đó. Không mất tổng quát, giả sử rằng các thuộc tính trong một sự kiện được sắp tăng dần theo thứ tự từ điển. Một danh sách có thứ tự p sự kiện (p là một số nguyên dương) được viết liền nhau trong cặp dấu 〈 〉 gọi là một chuỗi. Dữ liệu đầu vào là một cơ sở dữ liệu 𝒟 = {t , t , … , t } chứa n giao dịch, mỗi giao dịch mô tả một chuỗi (gọi là chuỗi đầu vào). Ta sử dụng ký hiệu ⊑ để định nghĩa quan hệ thứ tự chứa trong trên tập tất cả các chuỗi như sau: 18
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 α⊑β ∃p ∈ 𝒩 ∗ , 1 ⩽ j < j < ⋯ < j ⩽ q e ⊆ e , ∀k = 1, … , p. Khi đó, ta gọi β là chuỗi cha của α và ký hiệu: α ⊏ β (α ⊑ β ∧ α  β). Gọi ts(α) ≝ {𝑡 ∊ 𝒟 | 𝑡 ⊒ α} là tập tất cả các chuỗi đầu vào chứa α. Số lượng các chuỗi đầu vào chứa α được gọi là độ hỗ trợ của α, ký hiệu là: support(α) ≝ |ts(α)|1. Nếu độ hỗ trợ của α lớn hơn hoặc bằng một ngưỡng hỗ trợ tối thiểu msup cho trước, thì α được gọi là chuỗi phổ biến. Tập tất cả các chuỗi phổ biến được định nghĩa và ký hiệu: ℱ𝑟𝑒𝒮 ≝ {α | support(α) ≥ msup}. Ví dụ 1. Cho CSDL 𝒟 trong Bảng 1, với ℐ = {A, B, C, D, E, F, G, H} và msup là 2 2 . Chuỗi β = 〈D(AC)A〉 là chuỗi phổ biến vì ts(β) = {t , t , t } và support(β) = |ts(β)| = 3 ≥ msup. Bảng 1. CSDL 𝓓𝟏 Định danh Chuỗi đầu vào t1 t2 t3 T4 Chuỗi σ được gọi là chuỗi đóng nếu không tồn tại chuỗi cha có cùng độ hỗ trợ với nó: ∄β ⊐ σ | suppport(σ) = support(β). Tập các chuỗi đóng được ký hiệu là 𝒞𝑙𝑜𝒮. Cho trước chuỗi α, ta gọi Clo(α) ≝ {σ ∈ 𝒞𝒮 | (σ ⊒ α ∧ support(σ) = support(α))} là tập các chuỗi phổ biến đóng chứa (hay của) α và có cùng độ hỗ trợ với α. Với chuỗi α bất kỳ, có thể có nhiều chuỗi đóng tối tiểu (theo quan hệ thứ tự ⊑) cùng chứa α, tức là |Clo(α)| ⩾ 1. Hơn nữa, Clo(σ) = {σ} ⇔ σ ∈ 𝒞𝑙𝑜𝒮. Chuỗi γ được gọi là chuỗi sinh nếu không tồn tại chuỗi con có cùng độ hỗ trợ, ∄α ⊏ γ | support(γ) = support(α). Cho trước chuỗi α, ta gọi en(α) ≝ {γ ⊑ α | support(γ) = support(α)} là tập các chuỗi sinh chứa trong (hay của) α và có cùng độ hỗ trợ với α. 1 Ký hiệu |X| dùng để chỉ lực số phần tử của tập hợp X. 2 Từ nay về sau ta luôn xét CSDL 𝒟 với msup là 2. 19
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 Ví dụ 2. Chuỗi phổ biến β cho trong Ví dụ 1 là chuỗi đóng của α = 〈DA〉 vì ∄γ | (γ ⊐ β ∧ support(γ) = 3) và chuỗi δ = 〈𝐷〉 là một chuỗi sinh của α vì ∄δ′ | (δ′ ⊏ δ ∧ support(δ′) = support(δ)) . Do msup = 2 , support(δ) = support(α) = support(β) = 3, nên δ là chuỗi sinh phổ biến. Khi đó, Clo(β) = Gen(δ) = 1. Ngoài ra, ta cũng có Clo(δ) = {β, 〈D(AF)〉} và Gen(〈D(AC)(AF)〉) = {〈DAF〉, 〈DCF〉}. Gọi ℱ𝒞𝑙𝑜𝒮 và ℱ𝒢𝑒𝑛𝒮 lần lượt là tập tất cả các chuỗi phổ biến đóng và tập tất cả các chuỗi sinh phổ biến. Trong nhiều CSDL, tỉ lệ của tổng |ℱ𝒞𝑙𝑜𝒮| và |ℱ𝒢𝑒𝑛𝒮| so với |ℱ𝑟𝑒𝒮| thường rất nhỏ, chẳng hạn trên 𝒟 với |ℱ𝒞𝑙𝑜𝒮| = 16 , |ℱ𝒢𝑒𝑛𝒮| = 20 và |ℱ𝑟𝑒𝒮| = 1124, tỉ lệ này khoảng 3.2%. Tuy nhiên, từ chúng, ta có thể thu được tất cả các chuỗi phổ biến khác mà không cần quét lại cơ sở dữ liệu. Trước hết, ta xét một quan hệ tương đương trên tập các chuỗi, sau đó sử dụng nó để phân hoạch tập ℱ𝑟𝑒𝒮 thành các lớp tương đương. 2.2. Quan hệ tương đương trên tập các chuỗi Quan hệ hai ngôi ~ trên tập các chuỗi, được định nghĩa như sau: Với hai chuỗi α, β ta có: α ~ β ts(α) = ts(β). Dễ thấy rằng ~ là một quan hệ tương đương. Khi đó, nó phân hoạch một tập các chuỗi thành các lớp tương đương. Lớp tương đương chứa 𝛼 được ký hiệu là [𝛼], [𝛼] ≝ {𝛽 | ts(β) = ts(α)}. (1) Trong mỗi lớp tương đương, độ hỗ trợ được bảo toàn, tức là: α ~ β ⟹ support(α) = support(β), ∀β ∈ [𝛼]. 2.3. Phân hoạch tập các chuỗi phổ biến thành các lớp tương đương Từ quan hệ tương đương ~ , ta phân hoạch tập tất cả các chuỗi phổ biến ℱ𝑟𝑒𝒮 thành các lớp tương đương. Không mất tổng quát, ta chỉ cần xét mỗi lớp tương đương một cách độc lập. Vì chúng rời nhau, nên quá trình xác định các chuỗi phổ biến thuộc ℱ𝑟𝑒𝒮 sẽ không bị trùng lặp từ lớp này sang lớp kia (kiểu trùng lặp 1). Hơn nữa, ta còn giảm được đáng kể việc tính toán và lưu trữ trùng lặp các độ hỗ trợ trong cùng lớp. Đây cũng chính là cơ sở cho các thuật toán song song hiệu quả khai thác tập các chuỗi phổ biến trong môi trường song song và phân tán. Trước hết, gọi 𝒯𝒮 ≝ {ts(σ) | σ ∈ ℱ𝒞𝑙𝑜𝒮}. (2) Khi đó, với mỗi 𝓉𝓈 ∈ 𝒯𝒮, gọi ℱ𝒮(𝓉𝓈) ≝ {α ∈ ℱ𝑟𝑒𝒮 | ts(α) = 𝓉𝓈}. (3) là lớp tương đương có đại diện là 𝓉𝓈 3. Vì ~ là quan hệ tương đương, nên ta có: 3 Ta gọi tắt “lớp tương đương có đại diện là 𝓉𝓈” là “lớp tương đương 𝓉𝓈”. 20
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 ℱ𝑟𝑒𝒮 = 4 ∑𝓉𝓈∈𝒯𝒮 ℱ𝒮(𝓉𝓈). (4) Nghĩa là, {ℱ𝒮(𝓉𝓈), 𝓉𝓈 ∈ 𝒯𝒮} tạo ra một phân hoạch (thô) của ℱ𝑟𝑒𝒮. Một phân hoạch mịn hơn của ℱ𝑟𝑒𝒮 sẽ được chỉ ra trong Mục 3.3. Ví dụ 3. Ta có |ℱ𝑟𝑒𝒮| = 1124 chuỗi phổ biến và 𝒯𝒮 5= 𝓉𝓈 , k = 1,6 , trong đó: 𝓉𝓈 = {t , t }, 𝓉𝓈 = {t , t , t }, 𝓉𝓈 = {t , t }, 𝓉𝓈 = {t , t , t , t }, 𝓉𝓈 = {t , t } và 𝓉𝓈 = {t , t , t }. Khi đó, ℱ𝑟𝑒𝒮 được phân hoạch thành 6 lớp tương đương như trong Hình 1. Hình 1. Phân hoạch thô tập 𝓕𝒓𝒆𝓢 ứng với 𝓓𝟏 khi 𝐦𝐬𝐮𝐩 là 2 Lớp tương đương [α] đại diện bởi ts(α) chứa các chuỗi tối đại thuộc Clo(α) và các chuỗi tối tiểu thuộc Gen(α) (theo quan hệ thứ tự ⊑) là các chuỗi đã biết thuộc ℱ𝒞𝑙𝑜𝒮 và ℱ𝒢𝑒𝑛𝒮 tương ứng. Các chuỗi còn lại (thuộc ℱ𝑟𝑒𝒮) trong mỗi lớp chính là các chuỗi đứng sau các chuỗi sinh và đứng trước các chuỗi đóng (theo ⊑). Vì vậy, nếu biết các chuỗi đóng và chuỗi sinh của một lớp, ta hoàn toàn có thể xác định tất cả các chuỗi còn lại của nó. Nói cách khác, ta có thể phục hồi lớp ℱ𝑟𝑒𝒮 tất cả các chuỗi phổ biến từ ℱ𝒞𝑙𝑜𝒮 và ℱ𝒢𝑒𝑛𝒮 mà không cần quét lại cơ sở dữ liệu. Để sinh ra các chuỗi phổ biến còn lại trong cùng lớp, ta chỉ cần bổ sung thêm các chuỗi con của chuỗi đóng vào các chuỗi sinh. Quá trình phục hồi theo cách này có thể tạo ra các chuỗi phổ biến trùng lặp (trong cùng lớp), do đó, ta phải tốn bộ nhớ để lưu trữ và mất thời gian kiểm tra để loại bỏ chúng. 3. CẤU TRÚC CỦA LỚP TƯƠNG ĐƯƠNG CÁC CHUỖI PHỔ BIẾN Không mất tính tổng quát, trong phần này ta luôn xét lớp tương đương 𝓉𝓈, 𝓉𝓈 ∈ 𝒯𝒮. Gọi Clo(𝓉𝓈) ≝ {σ ∈ ℱ𝒞𝑙𝑜𝒮 | ts(σ) = 𝓉𝓈} (5) 4 Ký hiệu Σ biểu thị phép hợp của các tập rời nhau. 5 Từ nay về sau ta luôn sử dụng giá trị này của 𝒯𝒮. 21
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 là tập các chuỗi đóng trong ℱ𝒮(𝓉𝓈). Một nguyên nhân dẫn đến trùng lặp trong quá trình phục hồi các chuỗi phổ biến trong lớp tương đương 𝓉𝓈 là: nó có thể chứa nhiều chuỗi đóng (|Clo(𝓉𝓈)| ⩾ 1) và chứa các chuỗi là chuỗi sinh đồng thời của các chuỗi đóng đó (kiểu trùng lặp 2). Để loại bỏ trùng lặp kiểu này, ta chia nhỏ lớp tương đương các chuỗi phổ biến thành các lớp con (mức 1) dựa vào các chuỗi đóng trong lớp. Điều kiện tỉa CloPrun được đề xuất và áp dụng để khử bỏ sự trùng lặp giữa các lớp con. Khó khăn và cách giải quyết tương tự cũng được áp dụng để khử bỏ sự trùng lặp (kiểu 3) với GenPrun khi phục hồi các chuỗi trong mỗi lớp con mức 1. 3.1. Phân hoạch lớp tương đương các chuỗi phổ biến thành các lớp con mức 1 dựa vào các chuỗi đóng Vì |Clo(𝓉𝓈)| ⩾ 1, ta chia nhỏ lớp tương đương ℱ𝒮(𝓉𝓈) thành các lớp con mức 1. Mỗi lớp con là một tập tất cả các chuỗi phổ biến của ℱ𝒮(𝓉𝓈) chứa trong một chuỗi đóng cùng thuộc ℱ𝒮(𝓉𝓈), ℱ𝒮(𝓉𝓈) = ⋃ ∊ (𝓉𝓈) ℱ𝒮(σ ), (6) với, ℱ𝒮(σ ) ≝ {α ∈ [σ ] | α ⊑ σ } = {α ⊑ σ | ts(α) = ts(σ ) = 𝓉𝓈}, σ ∈ Clo(𝓉𝓈) (7) Có thể thấy rằng {ℱ𝒮(σ ), σ ∊ Clo(𝓉𝓈)} không là một phân hoạch của ℱ𝒮(𝓉𝓈). Tức là có thể tồn tại một chuỗi phổ biến α của ℱ𝒮(𝓉𝓈) thuộc cả lớp con ℱ𝒮(σ ) lẫn lớp con ℱ𝒮(σ ) với 𝑖 ≠ 𝑗, σ , σ ∊ Clo(𝓉𝓈). Như vậy, quá trình phục hồi các chuỗi phổ biến thuộc ℱ𝒮(𝓉𝓈) dựa vào (7) có thể sinh ra các chuỗi trùng lặp. Ví dụ 4 sẽ chỉ ra điều đó. Ví dụ 4. Xét lớp tương đương ứng với 𝓉𝓈 = {t , t , t } . Ta có Clo(𝓉𝓈 ) = {σ , σ , σ } , với σ = 〈𝐷(𝐴𝐶)A〉 , σ = 〈𝐷(𝐴𝐹)〉 , σ = 〈(𝐴𝐶𝐸)𝐴(AF)〉 , 𝐺𝑒𝑛(σ ) = 𝐺𝑒𝑛(σ ) = {γ = 〈D〉} , 𝐺𝑒𝑛(σ ) = {γ = 〈AAA〉, γ = 〈AAF〉, γ = 〈EAA〉, γ = 6 〈EAF〉} .  Cấu trúc lớp tương đương ứng với 𝓉𝓈 được chỉ ra trong Hình 2. Xét chuỗi sinh γ của σ và σ .  Trước hết, ta xét phép bổ sung các chuỗi con của σ vào γ. Khi đó, ta có ℱ𝒮(σ ) = {α | γ ⊑ α ⊑ σ }{〈D〉, 〈DA〉, 〈DC〉, 〈D(AC)〉, 〈DAA〉, 〈DCA〉, 〈D(AC)A〉} . Bây giờ, xét tiếp phép bổ sung các chuỗi con của σ cũng vào γ, ta có ℱ𝒮(σ ) = {〈𝐷〉, 〈𝐷𝐴〉, 〈𝐷𝐹〉, 〈𝐷(𝐴𝐹)〉}. Nhận xét rằng 〈𝐷〉 và 〈𝐷𝐴〉 xuất hiện trong cả ℱ𝒮(σ )lẫn ℱ𝒮(σ ). Khi đó ℱ𝒮(σ ) ∩ ℱ𝒮(σ ) = {〈𝐷〉, 〈𝐷𝐴〉} ≠ ∅, nghĩa là {ℱ𝒮(σ ), ℱ𝒮(σ ), ℱ𝒮(σ )} không là một phân hoạch của ℱ𝒮(𝓉𝓈 ). Sự trùng lặp này xuất hiện vì 〈𝐷〉 đồng thời là chuỗi sinh của σ và σ . Để loại bỏ trùng lặp kiểu 2 này, ta chỉ cần kiểm tra các chuỗi được tạo ra trong quá trình 6 Thông tin này được sử dụng trong các Ví dụ 5, 6. 22
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 bổ sung các chuỗi con của σ vào γ có chứa trong σ hay không? Nếu có, chuỗi đó bị loại. Hình 2. Phân hoạch lớp tương đương 𝓕𝓢(𝓽𝓼𝟐 ). Để khử trùng lặp, ta sử dụng điều kiện tỉa CloPrun được định nghĩa như sau: ∀σ ∈ Clo(𝓉𝓈), ∀α ∈ ℱ𝑟𝑒𝒮: CloPrun(α, σ ) ≝ (∃σ ∈ Clo(𝓉𝓈 ) | k < i, α ⊑ σ ). (8) Gọi ℱ𝒮 ∗ (σ ) ≝ α ∈ ℱ𝒮(σ ) not CloPrun(α, σ ) . (9) Dễ thấy rằng, ℱ𝒮 ∗ (σ ) ⊆ ℱ𝒮(σ ) , ℱ𝒮 ∗ (σ ) ∩ ℱ𝒮 ∗ σ = ∅ (với 𝑖 ≠ 𝑗 , σ ∈ Clo(𝓉𝓈)) và {ℱ𝒮 ∗ (σ ), σ ∈ Clo(𝓉𝓈)} tạo ra một phân hoạch của ℱ𝒮(𝓉𝓈): ∗ ℱ𝒮(𝓉𝓈) = ∑ ∊ (𝓉𝓈) ℱ𝒮 (σ ). (10) Ví dụ 5. Dễ dàng ta có, ℱ𝒮 ∗ (σ ) = ℱ𝒮(σ ) . Trong tập ℱ𝒮(σ ) , hai chuỗi 〈𝐷〉, 〈𝐷𝐴〉 không vượt qua được CloPrun tại σ nên bị loại. Do đó, ℱ𝒮 ∗ (σ ) = {〈𝐷𝐹〉, 〈𝐷(𝐴𝐹)〉}. Với σ , vì γ ⋢ σ và γ ⋢ σ , ∀γ ∈ Gen(σ ) , do đó, không có sự trùng lặp giữa ℱ𝒮(σ ) với ℱ𝒮(σ ) và ℱ𝒮(σ ). Khi đó, ℱ𝒮 ∗ (𝜎 ) = ℱ𝒮(σ ). Như vậy, 2 sự trùng lặp (kiểu 2) giữa các lớp con mức 1 bị loại bỏ bởi điều kiện tỉa CloPrun (xem Hình 2)! 3.2. Phân hoạch lớp con mức 1 thành các lớp con mức 2 dựa vào các chuỗi sinh Không mất tổng quát, bây giờ ta xét quá trình phục hồi lớp con mức 1 có đại diện là 𝓉𝓈 và chuỗi đóng σ (σ ∈ Clo(𝓉𝓈)), tức là ℱ𝒮 ∗ (σ ). Giả sử rằng chuỗi đóng σ có nhiều hơn một chuỗi sinh (|Gen(σ )| > 1), gọi γ và γ là hai chuỗi sinh của nó (γ , γ ∈ Gen(σ )). Việc bổ sung hai chuỗi con khác nhau của σ vào γ và γ hoàn toàn có thể tạo ra cùng một chuỗi kết quả. Do đó, quá trình phục hồi lớp con mức 1, ℱ𝒮 ∗ (σ ), vẫn có thể sinh ra trùng lặp (kiểu trùng lặp 3)! Xem minh họa trong Hình 3. 23
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 Hình 3. Phân hoạch mịn lớp tương đương 𝓕𝓢(𝓽𝓼𝟐 ) Hình thức hơn, nếu ký hiệu ℱ𝒮 σ , γ = 𝛼 ∊ ℱ𝒮 ∗ (σ ) | 𝛼 ⊒ 𝛾 = 𝛼 | 𝛾 ⊑ 𝛼 ⊑ 𝜎 (11) 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). 24
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018  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. 25
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 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. 26
KỶ YẾU HỘI NGHỊ KHOA HỌC THƯỜNG NIÊN TRƯỜNG ĐẠI HỌC ĐÀ LẠT NĂM 2018 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. 27