Luận văn Nghiên cứu khai phá top - K mẫu dãy thường xuyên trọng số với khoảng cách thời gian

- Với mỗi dãy α với tiền tố , support (α) trên S = support (α) trên S|α - Kích thước của CSDL điều kiện với tiền tố  không vượt quá S Thuật toán PrefixSpan Đầu vào : - CSDL dãy : S, - Ngưỡng hỗ trợ : min_sup, Đầu ra: Tập các mẫu dãy thường xuyên L 21 Thủ tục PrefixSpan (α,l,S|α ) Tham số: - α là một dãy thường xuyên - l là độ dài của dãy α - S|α là CSDL điều kiện với tiền tố α. S là trường hợp α =  Bắt đầu: (1). Duyệt S|α, đếm độ hỗ trợ của mỗi mục và tìm các mục thường xuyên  sao cho: Với mỗi : (a)  có thể được ghép làm thành phần cuối cùng của α để tạo thành một mẫu dãy thường xuyên hoặc (b) có thể được nối vào với α để tạo thành một mẫu dãy thường xuyên - Kiểm tra các tập mục ứng viên  trong Ck để tìm mẫu dãy thường xuyên có trọng số chuẩn hóa thỏa mãn tính chất support()*NW()  wmin_sup, nạp vào L (2). Lặp với mỗi mẫu dãy thường xuyên  - Ghép  với α để tạo thành một mẫu dãy α’ và đầu ra là α’ (3). Lặp với mỗi α’ - Xây dựng CSDL điều kiện với tiền tố α’ là S|α’ . - Thực hiện đệ quy thủ tục PrefixSpan(α’,l+1,S|α’) Kết thúc. 22 Ví dụ thuật toán PrefixSpan Cho một CSDL dãy SDB như Bảng 1.4, giá trị minsup =2. Khi đó việc khai phá các mẫu dãy thường xuyên trong CSDL dãy S theo phương pháp PrefixSpan được thực hiện theo các bước như sau: Bảng 1.4. Cơ sở dữ liệu dãy SDB ví dụ thuật toán PrefixSpan SID Dãy dữ liệu 1 2 3 4 Bước 1: Tìm các dãy thường xuyên có độ dài 1 Duyệt CSDL dãy SDB lần đầu tiên để tìm tất cả các mẫu dãy thường xuyên có độ dài 1, đếm độ hỗ trợ của mỗi mục. Khi đó ta có các giá trị độ hỗ trợ của mỗi mục tương ứng như sau: : 4, : 4, : 4, :3, : 3, : 3, Kiểm tra độ hỗ trợ mỗi mục với giá trị minsup =2. Ta có tập L: L = , , , , , Bước 2: Chia không gian tìm kiếm Toàn bộ các mẫu dãy thường xuyên được khai phá trong các phân vùng gồm 6 vùng tương ứng với 6 tiền tố như sau: (1) Mẫu dãy với tiền tố (2) Mẫu dãy với tiền tố (3) Mẫu dãy với tiền tố (4) Mẫu dãy với tiền tố (5) Mẫu dãy với tiền tố (6) Mẫu dãy với tiền tố Bước 3: Khai phá các mẫu dãy thường xuyên Các tập con mẫu dãy thường xuyên được khai phá bằng cách xây dựng các CSDL điều kiện tương ứng với các tiền tố, và khai phá chúng bằng phương 23 pháp đệ quy. Các bước thực hiện như sau: A. Tìm các các mẫu dãy thường xuyên với tiền tố Trong một dãy có chứa , chỉ có các dãy bắt đầu bằng sự xuất hiện đầu tiên của nên được lựa chọn. Ví dụ, trong chuỗi , chỉ có dãy được lựa chọn, tương tự với dãy , chỉ có dãy (~ d) c (bc) (ae) bc> được lựa chọn. Khi đó, CSDL điều kiện với tiền tố bao gồm 4 dãy sau Bảng 1.5. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 2 3 4 Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ liệu của nó tương ứng là a: 2, b: 4, c: 4, d: 2, e:1, f: 2, (~b): 2, (~c): 0 , (~d): 1, (~ e): 0 và (~ f): 1. Kiểm tra độ hỗ trợ mỗi mục với giá trị minsup=2. Khi đó, ta có các mục dữ liệu bị tỉa là e, (~c), (~d), (~e), (~f). Các mục dữ liệu được phát hiện là a,b,c,d,f,(~b) L = L  {, , , , , } Theo tính chất đệ quy, các mẫu dãy thường xuyên với tiền tố sẽ tiếp tục được chia thành 6 vùng tương ứng với 6 tiền tố gồm: (1) Mẫu dãy với tiền tố (2) Mẫu dãy với tiền tố (3) Mẫu dãy với tiền tố (4) Mẫu dãy với tiền tố 24 (5) Mẫu dãy với tiền tố (6) Mẫu dãy với tiền tố A.1. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố . Khi đó Bảng 1.6. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 2 Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ liệu của nó là a:1, c:1, d:1, f:1, (~b):1, (~e): 1. Kiểm tra độ hỗ trợ mỗi mục với giá trị minsup = 2. Khi đó, không có dãy thường xuyên với tiền tố được phát hiện. Dừng thực hiện đối với tiền tố A.2. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố . Khi đó: Bảng 1.7. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 2 3 Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ liệu của nó là a:2, c:2, d:1, e:1,f:1, (~c):2. Kiểm tra độ hỗ trợ mỗi mục với giá trị minsup = 2. Các mục dữ liệu được phát hiện là: a, c, (~c) L = L  {, , } Theo tính chất đệ quy, mẫu dãy thường xuyên với tiền tố sẽ tiếp tục được chia thành 3 vùng tương ứng với tiền tố gồm: (1) Mẫu dãy với tiền tố 25 (2) Mẫu dãy với tiền tố (3) Mẫu dãy với tiền tố A.2.1. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố . Khi đó CSDL điều kiện với tiền tố là Bảng 1.8. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 2 Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ liệu của nó là c:1, d:1, f:1, (~c):1, (~e):1. Kiểm tra độ hỗ trợ mỗi mục với giá trị minsup = 2. Khi đó, không có dãy thường xuyên với tiền tố được phát hiện. Dừng thực hiện đối với tiền tố . A.2.2. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố . Khi đó CSDL điều kiện với tiền tố là {}. Không có dãy thường xuyên với tiền tố được phát hiện. Dừng thực hiện đối với tiền tố A.2.3. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố . Khi đó CSDL điều kiện với tiền tố là Bảng 1.9. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 2 Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ liệu của nó là a:2,c:1, d:1,e:1, f:1. Kiểm tra độ hỗ trợ mỗi mục với giá trị minsup=2. Các mục dữ liệu được phát hiện là: a 26 L = L  { } Theo tính chất đệ quy, mẫu dãy thường xuyên với tiền tố sẽ tiếp tục được chia thành 1 vùng tương ứng với tiền tố gồm: (1) Mẫu dãy với tiền tố A.2.3.1. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố . Khi đó CSDL điều kiện với tiền tố là {}. Không có dãy thường xuyên với tiền tố được phát hiện. Dừng thực hiện đối với tiền tố / A.3. Đối với mẫu dãy với tiền tố tương tự , , , <(ab), ta xây dựng CSDL điều kiện với tiền tố tương ứng và thực hiện khai phá mẫu dãy thường xuyên tương tự như các bước A.1 và bước A.2 B. Tìm tương tự đối với các mẫu dãy thường xuyên với tiền tố , , , , Đối với mẫu dãy với tiền tố ,,,,, ta xây dựng các CSDL điều kiện với các tiền tố tương ứng. Cách khai phá mẫu dãy thường xuyên với mỗi tiền tố tương ứng cũng thực hiện tương tự như bước A, và thực hiện khai phá theo phương pháp đệ quy. Bước 4: Kết quả là các mẫu dãy thường xuyên trong CSDL dãy S Các mẫu dãy thường xuyên được khai phá lần lượt trong quá trình đệ quy đối với từng tiền tố. Bảng 1.10. Kết quả mẫu dãy thường xuyên theo thuật toán PrefixSpan Tiền tố (Prefix) CSDL điều kiện theo tiền tố Mẫu dãy thường xuyên , , , , ,, , , , , 27 Tiền tố (Prefix) CSDL điều kiện theo tiền tố Mẫu dãy thường xuyên , , , , , , , , , , , , , 28 Tiền tố (Prefix) CSDL điều kiện theo tiền tố Mẫu dãy thường xuyên , , Nhận xét thuật toán PrefĩxSpan: Thuật toán PrefixSpan [9]: Giải thuật dựa trên phương pháp phát triển mẫu dãy, phát triển những mẫu dãy dài từ những mẫu dãy có độ dài ngắn hơn đã có, đồng thời kết hợp với phương pháp chia nhỏ không gian tìm kiếm theo tiền tố. Thuật toán phát triển mẫu dãy không cần phát sinh thêm ứng viên giống như giải thuật AprioriAll [6]. Mặt khác thực hiện phép chiếu CSDL theo tiền tố nên không gian tìm kiếm giảm đáng kể. Nhờ vậy tiết kiệm bộ nhớ và việc thực hiện đếm độ hỗ trợ được nhanh hơn. 29 CHƯƠNG 2. TOP-K MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI KHOẢNG CÁCH THỜI GIAN 2.1. GIỚI THIỆU Mục tiêu của khai phá mẫu thường xuyên [6, 7, 8] là tìm ra các mẫu dãy xuất hiện nhiều lần trong 1 CSDL dãy. Tuy nhiên, các mẫu dãy thường xuyên không thể hiện được mức độ quan trọng của từng mục dữ liệu. Do đó, bài toán khai phá mẫu dãy thường xuyên có trọng số ra đời để giải quyết vấn đề về mức độ quan trọng của các mục. Một số thuật toán có thể kể tới là [19, 23, 24, 25, 17, 26, 27]. Trong các thuật toán này, không chỉ tần xuất mà mức độ quan trọng của các mục trong mẫu dãy cũng được tính tới. Để thể hiện mức độ quan trọng của các mục, mỗi mục được gán 1 giá trị thực dương (thường là trong khoảng 0-1). Tập các giá trị này được lưu vào 1 bảng gọi là bảng trọng số. Do trong các mẫu dãy có trọng số, độ hỗ trợ không còn tính phản đơn điệu nên trong các thuật toán khai phá mẫu dãy với trọng số, để duy trì tính phản đơn điệu, giá trị support*maxW được sử dụng làm cận trên của các mẫu dãy có trọng số. Một vấn đề khác của các mẫu dãy thường xuyên là không chứa thông tin về thời gian của các giao dịch. Tuy nhiên, dữ liệu trong thực tế thường có loại thông tin này. Ví dụ: dữ liệu mua sắm có thời gian của các giao dịch mua hàng, dữ liệu duyệt web lưu thời gian của các lần truy cập Khai phá mẫu dãy thường xuyên sử dụng một ngưỡng tối thiểu để tìm ra các mẫu dãy có giá trị. Ngưỡng này được đặt bởi người sử dụng như một giá trị đầu vào. Tuy nhiên, không dễ để chọn 1 ngưỡng phù hợp, nếu đặt ngưỡng quá cao sẽ tìm được ít mẫu dãy có giá trị, nếu đặt ngưỡng quá thấp sẽ dẫn tới quá nhiều mẫu dãy được tìm ra. Vì vậy, bài toán top-k ra đời để giải quyết vấn đề này. Trong bài toán top-k [28, 29, 30, 31, 32, 33], người sử dụng không cần phải đặt ngưỡng tối thiểu mà chỉ cần đưa vào giá trị k. Ngưỡng tối thiểu sẽ được tăng dần cho tới khi tìm ra được k mẫu dãy có giá trị nhất. 30 2.2. BÀI TOÁN KHAI PHÁ MẪU DÃY THƯỜNG XUYÊN CÓ TRỌNG SỐ 2.2.1. Các thuật ngữ mô tả bài toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa Cho I = {i1, i2, , in} là tập hợp các mục dữ liệu. Mỗi mục ij  I được gán một trọng số wj, j = 1,.....,n. Một dãy Sm là một danh sách được sắp xếp theo thứ tự của các mục dữ liệu {s1, s2, , sm} với sj  I là một tập mục được gọi là thành phần của dãy. Khi đó, S = {s1, s2, , sm} và sj có dạng (i1i2 ik) và it là một mục dữ liệu. Một dãy S bị loại nếu chỉ có duy nhất một mục dữ liệu. Một mục dữ liệu chỉ xuất hiện 1 lần trong 1 thành phần của một dãy sj, nhưng có thể xuất hiện nhiều lần trong các thành phần của một dãy S. Kích thước |S| của một dãy là số lượng của các thành phần trong dãy S. Độ dài l(S) của dãy là tổng số mục dữ liệu trong dãy S. Một cơ sở dữ liệu dãy S = {S1, S2, , Sn} là một tập các bộ dữ liệu (sid,Sk) với sid là định danh của một dãy và Sk là một dãy dữ liệu. Định nghĩa 5. Độ hỗ trợ của một dãy: Độ hỗ trợ của dãy Sa trong cơ sở dữ liệu dãy S là số lượng các bản ghi trong S có chứa dãy Sa Định nghĩa 6. Trọng số chuẩn hóa của dãy: Cho I = {i1, i2, , in} là tập hợp các mục dữ liệu. Mỗi mục ij  I được gán một trọng số wj, j = 1,.....,n. Khi đó trọng số chuẩn hóa của một dãy  = được tính bằng công thức 𝑁𝑊() = 1 𝑛 ∑ 𝑤𝑗 𝑖𝑗 ∈  Định nghĩa 7. Độ hỗ trợ với trọng số chuẩn hóa của dãy: Ta gọi đại lượng NWsupport() của dãy  là độ hỗ trợ với trọng số chuẩn hóa của dãy  𝑁𝑊𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝛼) = 𝑁𝑊(𝛼) ∗ 𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝛼) = ( 1 𝑛 ∑ 𝑤𝑗 𝑖𝑗 ∈𝛼 ) ∗ 𝑆𝐶(𝛼) 31 Định nghĩa 8. Mẫu dãy thường xuyên với trọng số chuẩn hóa: Cho một CSDL dãy S, một ngưỡng hỗ trợ tối thiểu wmin_sup. Một dãy α được gọi là mẫu dãy thường xuyên với trọng số chuẩn hóa nếu thỏa mãn tính chất. NWSupport(α)  wmin_sup Khi đó, bài toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa sử dụng CSDL điều kiện theo tiền tố được phát biểu như sau: • Cho CSDL dãy S, mỗi mục ij ⊆ I được gán một trọng số wj , ngưỡng hỗ trợ tối thiểu wmin_sup. Tìm tất cả các mẫu dãy thường xuyên với trọng số chuẩn hóa trong S, tức là tìm tập L : L = {Sa ⊆ S | NWsupport(Sa )  wmin_sup} • Mẫu dãy thường xuyên với trọng số chuẩn hóa không thỏa mãn tính chất phản đơn điệu, nghĩa là tập con của một mẫu dãy thường xuyên với trọng số chuẩn hóa không nhất thiết phải là mẫu dãy thường xuyên với trọng số chuẩn hóa. 2.2.2. CSDL điều kiện trong khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa Thuật toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa WPrefixSpan [34] trong đó cách tiếp cận chính là đẩy các ràng buộc trọng số và độ hỗ trợ trong thuật toán khai phá mẫu dãy và đảm bảo tính chất phản đơn điệu. Để tránh phải thực hiện kiểm tra tất cả khả năng kết hợp của một dãy các ứng viên tiềm năng, ta có thể thay thế các thứ tự của các mục dữ liệu trong từng thành phần trong dãy. Khi đó, các mục trong một thành phần của một dãy có thể được liệt kê theo 1 trật tự mà không mất tính tổng quát, ta có thể giả định rằng thứ tự này luôn luôn được liệt kê theo thứ tự bảng chữ cái. Ví dụ như dãy thay vì . Với quy ước như vậy, sự biểu hiện của một dãy là duy nhất. Nếu ta theo thứ tự của các tiền tố của một dãy và CSDL điều kiện của tiền tố đó chỉ có các hậu tố của một dãy, thì ta có thể kiểm tra các dãy con theo thứ 32 tự sắp xếp trên và CSDL điều kiện theo tiền tố đó. Định nghĩa 9. Mẫu dãy ứng viên: Cho một ngưỡng hỗ trợ tối thiểu wmin_sup. Một dãy α được gọi là dãy ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa nếu thỏa mãn tính chất Support(α) * MaxW  wmin_sup Với MaxW là giá trị lớn nhất của trọng số trong các mục trong S. Mẫu dãy ứng viên được xây dựng nhằm mục đích tỉa bớt không gian tìm kiếm mà vẫn đảm bảo tính phản đơn điệu trong khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa. 2.2.3. Ví dụ khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa sử dụng CSDL điều kiện theo tiền tố Cho một CSDL dãy S như Bảng 2.1, giá trị các trọng số của các mục dữ liệu như Bảng 2.2, giá trị wmin_sup = 2. Khi đó việc khai phá các mẫu dãy thường xuyên với trọng số chuẩn hóa trong CSDL dãy S theo phương pháp WPrefixSpan [34] được thực hiện theo các bước như sau: Bảng 2.1. Cơ sở dữ liệu dãy S Bảng 2.2. Giá trị trọng số của các mục dữ liệu Dãy dữ liệu Tên mục Trọng số a 0.9 b 0.75 c 0.8 d 0.85 e 0.75 f 0.7 g 0.85 h 0.8 33 Bước 1: Tìm các ứng viên của mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 1 Duyệt CSDL dãy S lần đầu tiên để tìm tất cả các ứng viên của mẫu dãy thường xuyên có trọng số chuẩn hóa có độ dài 1, đếm độ hỗ trợ của mỗi mục. Một mục có độ dài 1 có thể không phải là một mẫu dãy thường xuyên có trọng số chuẩn hóa nhưng có thể kết hợp với các mục khác có độ hỗ trợ lớn hơn hoặc trọng số lớn hơn để trở thành mẫu dãy thường xuyên có trọng số trong các mẫu có độ dài lớn hơn. Khi đó ta có các giá trị độ hỗ trợ của mỗi mục như sau: : 6, : 6, : 6, : 5, : 4, : 3, : 2, : 1 Giá trị trọng số là (a: 0,9 ; b: 0,75 ; c: 0,8 ; d: 0,85 ; e: 0,75 ; f: 0,7 ; g: 0,85 ; h: 0,8) Giá trị MaxW = 0.9 Kiểm tra theo Định nghĩa 9, loại mục g và h do giá trị: support(g)*MaxW = 2*0.9=1.8 < wmin_sup và support(h)*MaxW = 1*0.9=0.9 < wmin_sup Khi đó, ta có các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 1 là C1 = , , , , , Kiểm tra theo Định nghĩa 8 với các ứng viên, Khi đó, ta có các mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 1 là: NWsupport(a) = 6*0,9 = 5,4 NWsupport(b) = 6*0,75 = 4,5 NWsupport(c) = 6*0,8 = 4,8 NWsupport(d) = 5*0,85 = 4,25 NWsupport(e) = 4*0,75 = 3 NWsupport(f) = 3*0,7 = 2,1 Ta có: L = , , , , , Bước 2: Chia không gian tìm kiếm Toàn bộ các ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa được khai phá trong các phân vùng gồm 6 vùng tương ứng với 6 tiền tố gồm: 34 (1) Mẫu dãy với tiền tố (2) Mẫu dãy với tiền tố (3) Mẫu dãy với tiền tố (4) Mẫu dãy với tiền tố (5) Mẫu dãy với tiền tố (6) Mẫu dãy với tiền tố Bước 3: Khai phá các tập con ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa Các tập con ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa được khai phá bằng cách xây dựng các CSDL điều kiện tương ứng với các tiền tố, và khai phá chúng bằng phương pháp đệ quy. Các bước thực hiện như sau: A. Tìm các ứng viên và các mẫu dãy thường xuyên với trọng số chuẩn hóa với tiền tố Trong một dãy có chứa , chỉ có các dãy bắt đầu bằng sự xuất hiện đầu tiên của nên được lựa chọn. Ví dụ, trong chuỗi , chỉ có dãy được lựa chọn, tương tự với dãy , chỉ có dãy (~ d) c (bc) (ae) bc> được lựa chọn. Khi đó, CSDL điều kiện với tiền tố bao gồm 6 dãy sau: Bảng 2.3. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 2 3 4 5 6 Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ liệu của nó là a: 4, b: 6, c: 6, d: 4, e: 2, f: 2, (~b): 4, (~d): 1 , (~ e): 1 và (~ f): 1. Kiểm tra theo Định nghĩa 9, tìm các mẫu ứng viên có độ dài 2 với tiền tố 35 support(a)*MaxW = 4*0.9 = 3.6 support(b)*MaxW = 6*0.9 = 5.4 support(c)*MaxW = 6*0.9 = 5.4 support(d)*MaxW = 4*0.9 = 3.6 support(e)*MaxW = 2*0.9 = 1.8 support(f)*MaxW = 2*0.9 = 1.8 support((~b))*MaxW = 4*0.9 = 3.6 support((~d))*MaxW =1*0.9= 0.9 support((~e))*MaxW = 1*0.9 = 0.9 support((~f))*MaxW =1*0.9= 0.9 Khi đó, ta có các mục dữ liệu bị tỉa là , , , , . Các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 2 với tiền tố là C2 = , , , , Kiểm tra theo Định nghĩa 8 với các ứng viên trong C2 , Khi đó, ta có các mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 2 với tiền tố là: NWsupport(aa) = 4*(0,9+0,9)/2 = 5,4 NWsupport(ab) = 6*(0,9+0,75)/2 = 4,95 NWsupport(ac) = 6*(0,9+0,8)/2 = 5,1 NWsupport(ad) = 4*(0,9+0,85)/2 = 3,5 NWsupport((ab)) = 4*(0,9+0,9+0,75)/3 = 3,4 L = L  {, , , , } Theo tính chất đệ quy, các ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa với tiền tố sẽ tiếp tục được chia thành 5 vùng tương ứng với 5 tiền tố gồm: (1) Mẫu dãy với tiền tố (2) Mẫu dãy với tiền tố (3) Mẫu dãy với tiền tố (4) Mẫu dãy với tiền tố (5) Mẫu dãy với tiền tố A.1. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với 36 tiền tố với các mục dữ liệu trong tập ứng viên trong C2 . Khi đó Bảng 2.4. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 2 3 4 Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ liệu của nó là a: 1, b: 2, c: 4, d: 2, (~b): 3, (~c): 1. Kiểm tra theo Định nghĩa 9, tìm các mẫu ứng viên có độ dài 3 với tiền tố support(a)*MaxW = 1*0.9=0.9 support(b)*MaxW = 2*0.9=1.8 support(c)*MaxW = 4*0.9 = 3.6 support(d)*MaxW = 2*0.9 = 1.8 support((~b))*MaxW = 3*0.9 = 2.7 support((~c))*MaxW = 1*0.9 = 0.9 Khi đó, ta có các mục dữ liệu bị tỉa là , , , Các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 3 với tiền tố là C3 = , Kiểm tra theo Định nghĩa 8 với các ứng viên trong C3 , Khi đó, ta có các mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 3 với tiền tố là: NWsupport(aac) = 4*(0,9+0,9+0,8)/3 = 3,46 NWsupport(a(ab)) = 3*(0,9+0,9+0,75)/3 = 2,55 L = L  {, } Theo tính chất đệ quy, các ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa với tiền tố sẽ tiếp tục được chia thành 2 vùng tương ứng với 2 tiền tố gồm: 37 (1) Mẫu dãy với tiền tố (2) Mẫu dãy với tiền tố A.1.1. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố với các mục dữ liệu trong tập ứng viên trong C3 . Khi đó CSDL điều kiện với tiền tố chỉ có 1 dãy là c. A.1.2. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố với các mục dữ liệu trong tập ứng viên trong C3 . Khi đó CSDL điều kiện với tiền tố có các dãy là Bảng 2.5. Cơ sở dữ liệu điều kiện với tiền tố SID Dãy dữ liệu 1 2 3 Bằng cách quét CSDL điều kiện với tiền tố , độ hỗ trợ của các mục dữ liệu của nó là a: 1, b: 1, c: 3, (~d): 1, (~c): 1. Kiểm tra theo Định nghĩa 9, tìm các mẫu ứng viên có độ dài 4 với tiền tố support(a)*MaxW = 1*0.9 = 0.9 support(b)*MaxW = 1*0.9 = 0.9 support(c)*MaxW = 3*0.9 = 2.7 support((~d))*MaxW = 1*0.9 = 0.9 support((~c))*MaxW = 1*0.9 = 0.9 Khi đó, ta có các mục dữ liệu bị tỉa là , , , Các ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 4 với tiền tố là C4 = Kiểm tra theo Định nghĩa 8 với các ứng viên trong C4 , Khi đó, ta có các mẫu dãy thường xuyên với trọng số chuẩn hóa có độ dài 4 với tiền tố là: 38 NWsupport(a(ab)c) = 3*(0,9+0,9+0,75+0,8)/4 = 2,51 L = L  {} Theo tính chất đệ quy, các ứng viên và mẫu dãy thường xuyên với trọng số chuẩn hóa với tiền tố sẽ tiếp tục được chia thành 1 vùng tương ứng với 1 tiền tố gồm: (1) Mẫu dãy với tiền tố A.1.2.1. Đối với mẫu dãy với tiền tố , ta xây dựng CSDL điều kiện với tiền tố với các mục dữ liệu trong tập ứng viên trong C4 . Khi đó CSDL điều kiện với tiền tố chỉ có 1 dãy là . A.2. Đối với mẫu dãy với tiền tố , tiền tố , tiền tố , tiền tố , ta xây dựng CSDL điều kiện với các tiền tố tương ứng với các mục dữ liệu trong tập ứng viên trong C2 . Cách khai phá mẫu dãy thường xuyên có trọng số chuẩn hóa với mỗi tiền tố tương ứng cũng thực hiện tương tự như bước A.1. B. Tìm tương tự với các ứng viên và các mẫu dãy thường xuyên với trọng số chuẩn hóa với tiền tố ,,,, Đối với mẫu dãy với tiền tố ,,,,, ta xây dựng các CSDL điều kiện với các tiền tố tương ứng với các mục dữ liệu trong tập ứng viên trong C1. Cách khai phá mẫu dãy thường xuyên có trọng số chuẩn hóa với mỗi tiền tố tương ứng cũng thực hiện tương tự như bước A, và thực hiện đệ khai phá theo phương pháp đệ quy. Bước 4: Kết quả là các mẫu dãy thường xuyên với trọng số chuẩn hóa trong CSDL dãy S Các mẫu dãy thường xuyên có trọng số chuẩn hóa được khai phá lần lượt trong quá trình đệ quy đối với từng tiền tố. Trong phương pháp khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa này, kết quả sẽ ít hơn các mẫu dãy thường xuyên khi không gắn thêm yếu tố trọng số của các mục dữ liệu. 39 2.2.4. Thuật toán khai phá mẫu dãy thường xuyên với trọng số chuẩn hóa sử dụng CSDL điều kiện theo tiền tố (WPrefixSpan) - Đầu vào : (1) CSDL dãy : S, (2) Ngưỡng hỗ trợ : wmin_sup, (3) Trọng số của các mục: wi, - Đầu ra: Tập các mẫu dãy thường xuyên với trọng số chuẩn hóa L Thuật toán WPrefixSpan Bắt đầu 1. Duyệt CSDL S lần đầu, tính độ hỗ trợ và tìm các mục ứng viên có kích thước 1 thỏa mãn tính chất: Một tập mục P là tập mục ứng viên nếu thỏa mãn điều kiện 1.1, P sẽ được nạp vào Ck Điều kiện 1.1: support (P)* MaxW  wmin_sup 2. Kiểm tra các tập mục ứng ứng viên trong Ck để tìm mẫu dãy thường xuyên có trọng số chuẩn hóa thỏa mãn tính chất support(P)*NW(P)  wmin_sup, nạp vào L 3. Lặp với mỗi mục trọng số chuẩn hóa P, trong CSDL dãy S Thực hiện hàm đệ quy WPrefixSpan(,l,S|P) Kết thúc lặp Kết thúc 40 Thủ tục WPrefixSpan (α,l,S|α ) Tham số: (1) α là một dãy ứng viên với trọng số chuẩn hóa thỏa điều kiện 1.1 (2) l là độ dài của α (3) S|α là CSDL điều kiện với tiền tố α. S là trường hợp α =  Bắt đầu: 1. Duyệt S|α, đếm độ hỗ trợ của mỗi mục và tìm các mục ứng viên trọng số chuẩn hóa  trong các dãy. Một mục ứng viên trọng số chuẩn hóa  thỏa mãn tính chất 1.1, nạp vào Ck Điều kiện 1.1: support ()* MaxW  wmin_sup - Với mỗi  trong Ck : (a)  có thể được ghép làm thành phần cuối cùng của α để tạo thành ứng viên cho một mẫu dãy thường xuyên với trọng số chuẩn hóa hoặc (b) có thể được nối vào với α để tạo thành ứng viên cho một mẫu dãy thường xuyên với trọng số chuẩn hóa - Kiểm tra các tập mục ứng viên  trong Ck để tìm mẫu dãy thường xuyên có trọng số chuẩn hóa thỏa mãn tính chất support()*NW()  wmin_sup, nạp vào L 2. Lặp với mỗi ứng viên mẫu dãy thường xuyên với trọng số chuẩn hóa  - Ghép  với α để tạo thành ứng viên một mẫu dãy thường xuyên α’ và đầu ra là α’ 3. Lặp với mỗi α’ - Xây dựng CSDL điều kiện với tiền tố α’ là S|α’ . - Thực hiện đệ quy thủ tục WPrefixSpan(α’,l+1,S|α’) Kết thúc. 41 2.3. BÀI TOÁN MẪU DÃY THƯỜNG XUYÊN TRỌNG SỐ VỚI KHOẢNG CÁCH THỜI GIAN Phần này trình bày thuật toán WIPrefixSpan [35] khai phá mẫu dãy thường xuyên trọng số với khoảng cách thời gian. Thuật toán WIPrefixSpan [35] không chỉ quan tâm tới trọng số của các mục trong CSDL mà còn cả khoảng cách thời gian giữa các tập mục. 2.3.1. Mô tả bài toán Cho I = {i1, i2, , in} là tập hợp các mục dữ liệu. Mỗi mục ij  I được gán một trọng số wj, j = 1,.....,n. Một dãy Sm là một danh sách được sắp xếp theo thứ tự của các mục dữ liệu dạng { (t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,m,sm)} với sj  I trong đó (1 ≤ j ≤ m) là một tập mục được gọi là thành phần của dãy và sj có dạng (i1i2 ik) và it là một mục dữ liệu thuộc I , và t, là khoảng cách thời gian giữa dãy s và s. Một dãy Sm bị loại nếu chỉ có duy nhất một mục dữ liệu it  I . Một mục dữ liệu chỉ xuất hiện 1 lần trong thành phần của một dãy sj, nhưng có thể xuất hiện nhiều lần trong các thành phần của một dãy Sm. Kích thước |Sm| của một dãy là số lượng của các thành phần trong dãy Sm. Độ dài l(Sm) của dãy là tổng số mục dữ liệu trong dãy Sm. Một cơ sở dữ liệu dãy S = {S1, S2, , Sn} là một tập các bộ dữ liệu (sid,Sk) với sid là định danh của một dãy và Sk là một dãy dữ liệu có dạng {(t1,1,s1), (t1,2,s2), (t1,3,s3),..., (t1,m,sm)}. Định nghĩa 1. (Dãy dữ liệu có khoả