Luận văn Khai phá mẫu dãy lợi ích cao với khoảng cách thời gian

nó cũng là dãy không thường xuyên. Tuy nhiên, trong khai phá mẫu dãy lợi ích cao, tính chất này không còn đúng nữa. Một mẫu dãy có thể không là mẫu dãy lợi ích cao nhưng mẫu dãy cha của nó vẫn có thể là mẫu dãy lợi ích cao. Bài toán khai phá mẫu dãy lợi ích cao lần đầu tiên được đề xuất bởi Ahmed và cộng sự [27]. Ahmed định nghĩa hai loại lợi ích của một mục: lợi ích trong (thể hiện số lượng của mục) và lợi ích ngoài (thể hiện độ quan trọng của mục). Hai thuật toán cũng được đề xuất: UtilityLevel (UL) sử dụng phương pháp tiếp cận Apriori và UtilitySpan (US) sử dụng phương pháp tăng trưởng mẫu dãy dựa trên thuật toán PrefixSpan [6]. Trong công trình của Ahmed, lợi ích của một mẫu dãy được tính bằng tổng của các lần xuất hiện của mẫu dãy đó trong dãy dữ liệu. Cách tính này khiến các mẫu dãy tìm ra có thể thể hiện hành vi mua sắm liên tục của một khách hàng hơn là hành vi chung của các khách hàng khác nhau. Để tránh tính huống như vậy và cũng để đơn giản hóa hàm tính lợi ích, các nghiên cứu sau này sử dụng cách tính lợi ích cao là giá trị lớn nhất trong các lần xuất hiện của mẫu dãy. 23 Năm 2012, Yin và cộng sự đề xuất một framework để khai phá lợi ích cao và giới thiệu thuật toán Uspan [30]. Thuật toán Uspan sử dụng ngưỡng cận trên SWU (sequence weight utility) để tỉa ứng viên và 2 cấu trúc dữ liệu LQS-tree và ma trận lợi ích (Utility Matrix) để biểu diễn dữ liệu. Vào năm 2014, Lan và cộng sự đề xuất thuật toán PHUS [29], một thuật toán dựa trên PrefixSpan. Thuật toán PHUS cũng sử dụng SWU làm ngưỡng cận trên để tỉa ứng viên và cấu trúc bảng lợi ích thời gian để biểu diễn dữ liệu. Ngoài ra còn có một số thuật toán khác cũng được đề xuất để tăng hiệu năng giải thuật như HuspExt [28], HUS-Span [32] hoặc tìm kiếm Top-k mẫu dãy lợi ích cao như TKHUS- Span [32], TUS [33] . Các phần tiếp theo sẽ trình bày bài toán HUSP và các thuật toán US, UL [27] cũng như PHUS [29] làm cơ sở cho các thuật toán trong chương 3. 2.2. Bài toán khai phá mẫu dãy lợi ích cao Bài toán khai phá mẫu dãy lợi ích cao có mục tiêu là tìm ra tất cả các mẫu dãy lợi ích cao trong CSDL dãy định lượng (QSDB). ID Dãy dữ liệu với lợi ích trong Lợi ích S1 130 S2 85 S3 74 S4 180 S5 67 S6 207 Bảng 2.1 Cơ sở dữ liệu dãy định lượng QSDB 24 Mục Lợi ích ngoài a 5 b 7 c 3 d 10 e 6 f 8 g 9 Bảng 2.2 Bảng lợi ích ngoài Một CSDL dãy định lượng được định nghĩa như sau. Giả sử 𝐴 = {𝑎1, 𝑎2, , 𝑎𝑀} là tập hợp tất cả các mục xuất hiện duy nhất trong một QSDB. Một tập con X⊆ 𝐴 được gọi là một tập mục. Không giảm tổng quát, ta giả sử tất cả các mục trong một tập mục được sắp xếp theo thứ tự từ điển. Một dãy S là một danh sách có thứ tự của các tập mục, mỗi tập mục xuất hiện trong dãy được gọi là một thành phần của dãy. Độ dài của dãy S là số mục xuất hiện trong S. Cơ sở dữ liệu định lượng QSDB là một danh sách các dãy Si, mỗi dãy Si trong QSDB được gọi là một dãy dữ liệu đầu vào. Si có thể biểu diễn chuỗi các giao dịch của một khách hàng trong một siêu thị. Bảng 2.1 là một ví dụ về CSDL định lượng với lợi ích trong. Bảng 2.2 là bảng lợi ích ngoài của các mục trong QSDB. Định nghĩa 2.1. Lợi ích trong và lợi ích ngoài Trong một QSDB, mỗi mục a được gán một giá trị thực dương 𝑝 ∈ 𝑅+ thể hiện mức độ quan trọng của mục đó gọi là lợi ích ngoài. Một số nguyên dương 25 q được gán với mỗi lần xuất hiện của mục a trong QSDB thể hiện số lượng của a tại lần xuất hiện đó. Ví dụ trong CSDL tại Bảng 2.1, q(b,S1) = 6 và p(b) = 7. Trong một dãy dữ liệu Si, một mục có thể xuất hiện nhiều lần với nhiều giá trị lợi ích trong khác nhau. Khi đó, lợi ích của mục đó trong dãy dữ liệu Si sẽ được tính bằng lợi ích lớn nhất trong các lần xuất hiện của mục đó trong dãy. Ví dụ, trong bảng Bảng 2.1, mục a xuất hiện 3 lần trong dãy S1 với các giá trị lợi ích trong lần lượt là 3, 2 và 5. Khi đó, lợi ích trong q(a,S1) = 5. Định nghĩa 2.2. Lợi ích của một mục trong dãy Lợi ích của một mục aj trong dãy Si ký hiệu là su(aj, Si) và được tính bằng công thức: su(aj, Si) = q(aj, Si) * p(aj). Vì mục aj có thể xuất hiện nhiều lần trong dãy Si nên ở đây lợi ích của mục aj được tính bằng giá trị lớn nhất của các lợi ích của mục aj trong Si. Ví dụ 2: trong dãy S1, mục a xuất hiện 3 lần, lợi ích của mục a trong S1 được tính bằng giá trị của lần xuất hiện lớn nhất. Do đó, lợi ích của a trong S1 là 5*5=25. Định nghĩa 2.3. Lợi ích của một mẫu dãy trong dãy dữ liệu đầu vào Cho 𝛼 = 〈𝑋1, 𝑋2, , 𝑋𝑛〉 là một mẫu dãy có độ dài n, với 𝛼  𝑆𝑖. Lợi ích của một mẫu dãy α trong Si , ký hiệu su(α, Si), được tính bằng công thức: 𝑠𝑢(α, 𝑆𝑖) = max { ∑ 𝑠𝑢(𝑎𝑗 , 𝑆𝑖) 𝑎𝑗∈𝛼 , ∀𝛼 ∈ 𝑆𝑖} (2.1) Ví dụ 3: mẫu dãy có 4 lần xuất hiện trong S1, lần lượt là a[3]d[2], a[3]d[1], a[2]d[1], a[5]d[1]. Giá trị lợi ích của chúng lần lượt là 3*5+2*10=35 và 3*5+1*10=25; 2*5+1*10= 30; 5*5+1*10=35. Vậy lợi ích của mẫu dãy 〈a,d〉 trong S1 là 𝑠𝑢(𝑎𝑑, 𝑆1) = 35. 26 Cần lưu ý là cách tính lợi ích của Ahmed và cộng sự [27] đề xuất có khác biệt: nếu mẫu dãy đó xuất hiện nhiều lần phân biệt trong 1 dãy đầu vào thì lợi ích của mẫu dãy đó bằng tổng các lần xuất hiện của mẫu dãy. Nếu mẫu dãy xuất hiện nhiều lần nhưng các lần xuất hiện đan xen nhau (có nhiều hơn 1 phần tử trùng nhau giữa 2 lần xuất hiện) thì lợi ích mẫu dãy bằng tổng lợi ích của các lần xuất hiện lớn nhất. Ví dụ: mẫu dãy trong S1 có 4 lần xuất hiện, trong đó các lần xuất hiện a[3]d[2] và a[3]d[1] đan xen nhau, a[2]d[1] và a[5]d[1] cũng đan xen. Lợi ích của sẽ tính bằng tổng lợi ích của các lần xuất hiện lớn nhất trong các lần đan xen. Trong trường hợp này su() = 3*5+2*10 + 5*3+1*10 = 60. Cách tính này khá phức tạp do phải xác định được các lần xuất hiện của mẫu dãy là phân biệt hay đan xen nhau. Và cũng như đã phân tích ở trên, cách tính này không phù hợp trong thực tế, do vậy các nghiên cứu về sau đều sử dụng cách tính lợi ích dựa vào giá trị lớn nhất. Định nghĩa 2.4. Lợi ích của một dãy đầu vào Lợi ích của một dãy đầu vào Si được tính bằng tổng tất cả các lợi ích của các mục trong dãy Si, nghĩa là bằng: 𝑠𝑢(𝑆𝑖) = ∑ 𝑠𝑢(𝑎𝑗 ,𝑆𝑖) 𝑎𝑗∈𝑆𝑖 (2.2) Định nghĩa 2.5. Lợi ích của một mẫu dãy trong CSDL Lợi ích của một mẫu dãy α trong toàn bộ CSDL QSDB ký hiệu là su(α, QSDB) được tính bằng công thức: 𝑠𝑢(α, 𝑄𝑆𝐷𝐵) = ∑ 𝑠𝑢(𝛼, 𝑆𝑖) 𝑆𝑖∈𝑄𝑆𝐷𝐵 (2.3) 27 Định nghĩa 2.6. Lợi ích của một CSDL định lượng Lợi ích của một CSDL định lượng QSDB là tổng các lợi ích của các dãy đầu vào Si trong QSDB và được định nghĩa bởi công thức: 𝑠𝑢(𝑄𝑆𝐷𝐵) = ∑ 𝑠𝑢(𝑆𝑖) 𝑆𝑖∈𝑄𝑆𝐷𝐵 (2.4) Định nghĩa 2.7. Mẫu dãy lợi ích cao Giả sử có một CSDL định lượng QSDB và một ngưỡng lợi ích tối thiểu minUtil, mỗi mục a trong QSDB được gán một giá trị lợi ích trong q và lợi ích ngoài p. Một mẫu dãy α được gọi là mẫu dãy lợi ích cao nếu lợi ích của α trong QSDB lớn hơn hoặc bằng minUtil, nghĩa là: 𝑠𝑢(α, 𝑄𝑆𝐷𝐵) ≥ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 Ví dụ, với QSDB trong Bảng 2.1 và minUtil = 200, mẫu dãy là một mẫu dãy lợi ích cao vì su(a(bd)a) = 221. Vấn đề thách thức nhất trong khai phá mẫu dãy lợi ích cao là độ đo lợi ích không có tính đóng xuống. Nghĩa là mẫu dãy con của một mẫu dãy lợi ích cao chưa chắc đã là mẫu dãy lợi ích cao. Trở lại ví dụ trên, mẫu dãy a không phải là một mẫu dãy lợi ích cao vì su(a) = 100 <221 nhưng mẫu dãy cha của nó là a(bd)a lại là mẫu dãy lợi ích cao. Vì vậy tính chất đóng xuống không được thỏa mãn. Để duy trì tính chất đóng xuống, Ahmed và cộng sự đã định nghĩa một độ đo gọi là sequence-weighted utility (SWU). Định nghĩa 2.8. Giá trị SWU của một mẫu dãy Sequence-weighted utility (SWU) của một mẫu dãy α trong QSDB là tổng tất cả các lợi ích của các mẫu dãy đầu vào có chứa α trong QSDB. Nghĩa là: 28 𝑠𝑤𝑢(𝛼) = ∑ 𝑠𝑢(𝑆𝑖) 𝛼𝑆𝑖 ∧ 𝑆𝑖∈𝑄𝑆𝐷𝐵 (2.5) Giá trị swu đóng vai trò là ngưỡng cận trên của hàm lợi ích và sử dụng để tỉa bớt ứng viên trong không gian tìm kiếm. Định nghĩa 2.9. Mẫu dãy ứng viên lợi ích cao Một mẫu dãy α được gọi là mẫu dãy ứng viên lợi ích cao nếu giá trị swu của nó lớn hơn ngưỡng hỗ trợ tối thiểu. Nghĩa là 𝑠𝑤𝑢(𝛼) ≥ 𝑚𝑖𝑛𝑈𝑡𝑖𝑙 (2.6) Độ đo swu thỏa mãn tính chất đóng xuống, nghĩa là nếu 1 mẫu dãy α là mẫu dãy ứng viên thì tất cả các mẫu dãy con của nó cũng phải là mẫu dãy ứng viên. Swu được sử dụng để tỉa bớt không gian tìm kiếm trong các thuật toán khai phá mẫu dãy lợi ích cao. Nếu một mẫu dãy có swu nhỏ hơn minUtil thì ta có thể loại bỏ nó cùng tất cả các mẫu dãy cha của nó khỏi không gian tìm kiếm. 2.3. Thuật toán UL, US Để giải quyết bài toán khai phá mẫu dãy lợi ích cao, Ahdmed [27] và cộng sự đề xuất hai thuật toán UtilityLevel (UL) dựa trên Apriori và UtilitySpan (US) dựa trên phương pháp tăng trưởng mẫu dãy của thuật toán PrefixSpan. 2.3.1. Thuật toán UL: Thuật toán UL sử dụng phương pháp sinh mẫu dãy ứng viên theo tiếp cận Apriori. UL bao gồm 2 pha: đầu tiên, UL sinh các mẫu dãy rồi kiểm tra xem có mẫu dãy nào là ứng viên lợi ích cao không (có giá trị swu lớn hơn hoặc bằng minUtil), sau đó tiếp tục sinh ra các mẫu ứng viên khác. Trong pha thứ 2, UL tính lại lợi ích thực của các mẫu ứng viên lợi ích cao tìm được trong pha 1 để tìm ra các mẫu lợi ích cao thực sự. Thuật toán UL mô tả như sau: 29 Input: Một CSDL dãy định lượng QSDB, ngưỡng lợi ích tối thiểu minUtil Output: Tập các mẫu dãy lợi ích cao Start 1. Gọi C1 là tập các mẫu dãy 1 ứng viên phần tử. 2. Gọi F1 là tập các mẫu dãy ứng viên lợi ích cao 1 phần tử 3. Gọi L là tập tất cả các mẫu dãy ứng viên lợi ích cao: 𝐿 = ⋃ 𝐹𝑘 𝑘 4. Quét QSDB để tính giá trị swu của tất cả các mẫu dãy a trong QSDB. 5. If (swu(a) ≥ minUtil) then 𝐹1 = 𝐹1 ∪ a End if 6. for (k=2, Fk-1 ≠ NULL, k++) Sinh các mẫu dãy độ dài k, nạp vào Ck Quét QSDB để tính swu của các mẫu dãy α trong Ck. If (swu(a) ≥ minUtil) then 𝐹𝑘 = 𝐹𝑘 ∪ 𝛼 End if 𝐿 = 𝐿 ∪ 𝐹𝑘 End for 7. Quét QSDB lần nữa để tính lợi ích thực sự và tìm ra các mẫu dãy lợi ích cao. End. 30 Độ phức tạp thuật toán UL: Thuật toán UL dùng phương pháp sinh ứng viên kiểu Apriori nên độ phức tạp của UL cũng giống với Apriori là độ phức tạp hàm mũ O(2N) trong đó N là tổng số mục trong CSDL. Ví dụ minh họa thuật toán UL: Cho CSDL dãy định lượng QSDB như trong Bảng 2.1 và ngưỡng lợi ích minUtil = 230. Thuật toán UL thực hiện như sau: Đầu tiên quét QSDB để tính giá trị swu của tất cả các mục trong QSDB. Các giá trị này lần lượt là: Swu(a) = 602, swu(b) = 676, swu(c) = 226, swu(d) = 743, swu(e) = 546, swu(f) = 271, swu(g) = 67 Mục c và g có swu lần lượt là 226 và 67 nhỏ hơn minUtil nên , không là mẫu dãy ứng viên lợi ích cao. Do vậy, theo tính chất đóng xuống, các mẫu dãy cha của c và g cũng không là ứng viên lợi ích cao. Nên c, g bị loại. Tập các mẫu dãy ứng viên lợi ích cao 1 phần tử là {a, b, d, e, f} Tiếp tục sinh các ứng viên độ dài 2 từ các mẫu dãy ứng viên lợi ích cao 1 phần tử bằng cách ghép các ứng viên 1 phần tử với nhau. Một số mẫu dãy ứng viên 2 phần tử là: , , , , , , , , , , , , , , , Quét CSDL QSDB để tính giá trị swu của các mẫu dãy ứng viên 2 phần tử và tìm ra các mẫu dãy là ứng viên lợi ích cao (có swu > minUtil). Một số ứng viên không xuất hiện trong QSDB thì sẽ bị loại luôn (ví dụ , ...). Các mẫu dãy ứng viên lợi ích cao 2 phần tử là: : 310, :517, :602, : 387, :310, :387 Các mẫu dãy này lại được sử dụng để sinh các ứng viên 3 phần tử. CSDL QSDB được quét lần nữa để tính swu của các ứng viên và tìm ra các ứng viên lợi ích cao. Quá trình như vậy tiếp tục diễn ra đến khi không tìm thấy ứng viên nào nữa. 31 Quá trình sinh ứng viên của thuật toán UL được minh họa trong Bảng 2.3. Level Mẫu dãy ứng viên Mẫu dãy ứng viên lợi ích cao và giá trị swu của chúng 1 a, b, c, d, e, f, g a: 602, b: 676, d: 743, e: 546, f: 271 2 aa, ab, ad, ae, af ba, bb, bd, be, bf ... (ab), (ad), (ae), (af) (bd), (be), (bf) .. aa: 310, ab: 517, ad: 602, ae: 387, ba: 310, bb: 387, bd: 496, be: 461, da: 517, db: 387, dd: 337, de: 387, ea: 292, eb: 292, ed: 292, (ab): 602, (bd): 310 3 aaa, aab, aad, aae, a(ab), aba, abb . (ab)a, (ab)b, (ab)d, (ab)e . aba: 310, abe: 387, ada: 310, adb: 387, ade: 387, a(ab): 310, a(bd): 310, bbe: 387, dad: 337, dae: 387, dbe: 387, d(ab): 387, ead: 292, ebd: 292, e(ab): 292, (ab)d: 422, (ab)e: 387, (bd)a: 310 4 adbe, a(bd)a, d(ab)e, e(ab)d adbe: 387, a(bd)a: 310, d(ab)e: 387, e(ab)d: 292 Bảng 2.3 Sinh mẫu dãy ứng viên trong thuật toán UL Sau khi tất cả các ứng viên mẫu dãy lợi ích cao được tìm thấy, quét QSDB lần nữa, tính giá trị lợi ích su của từng ứng viên và tìm ra các mẫu dãy lợi ích cao thực sự. Các mẫu dãy lợi ích cao tìm được là: ={: 239, : 238, : 231, : 250} 32 2.3.2. Thuật toán US: Thuật toán UL sử dụng phương pháp sinh ứng viên kiểu Apriori nên cũng có những nhược điểm của phương pháp Apriori: - UL sinh ra các mẫu ứng viên không tồn tại trong QSDB - UL phải quét CSDL nhiều lần. Như trong ví dụ trên, UL sinh ra các ứng viên không tồn tại trong QSDB như: , , ,UL cũng mất 5 lần quét CSDL để tính swu của các ứng viên. Một cách tổng quát, để tạo ra ứng viên độ dài N thì UL cần N+1 lần quét CSDL. Thuật toán US được phát triển để giải quyết các nhược điểm đó. US là thuật toán được phát triển dựa trên phương pháp tăng trưởng mẫu dãy của thuật toán PrefixSpan. US cũng bao gồm 2 pha như UL: pha 1 sinh ứng viên, pha 2 tính lại lợi ích và tìm ra mẫu dãy lợi ích cao thật sự. Sự khác biệt đến từ giải thuật sinh ứng viên trong pha 1. Đầu tiên, US quét QSDB để tìm ra các mẫu dãy ứng viên lợi ích cao 1 phần tử. Sau đó, US xây dựng các CSDL chiếu của các mẫu dãy ứng viên lợi ích cao 1 phần tử. Tiếp theo, US thực hiện thủ tục đệ quy sinh các ứng viên với độ dài tăng dần theo phương pháp PrefixSpan. Thuật toán US mô tả như sau: Input: CSDL dãy định lượng QSDB, ngưỡng lợi ích tối thiểu minUtil Output: Tập tất cả các mẫu dãy lợi ích cao Start 1. Đặt L là tập tất cả các mẫu dãy ứng viên lợi ích cao 2. L = NULL 3. Gọi thủ tục US(NULL, 0, QSDB) 33 4. Quét QSDB lần cuối để tính lợi ích của các mẫu dãy trong L và tìm ra các mẫu dãy lợi ích cao. End Thủ tục US: Procedure US(α, len, QSDB|α) Input: α là một mẫu dãy ứng viên lợi ích cao, len là độ dài của α, QSDB|α là CSDL chiếu với tiền tố α, nếu α = NULL thì QSDB|α = QSDB Output: Các mẫu dãy ứng viên lợi ích cao với tiền tố α Start 1. Quét QSDB|α lần 1 để tìm ra các mẫu dãy ứng viên lợi ích cao β sao cho: a. β có thể nối với α để tạo thành ứng viên lợi ích cao b. β có thể nhóm vào với phần tử cuối cùng của α để tạo thành một ứng viên lợi ích cao 2. Với mỗi ứng viên lợi ích cao β - Ghép β với α để tạo thành mẫu dãy ứng viên lợi ích cao α’ - L = L ⋃ 𝛼’ - Xây dựng CSDL chiếu của α’, ký hiệu QSDB|α’ - Gọi thủ tục US(α’, len+1, QSDB|α’) End Procedure Ví dụ minh họa thuật toán US Giả sử có CSDL dãy định lượng QSDB như trong Bảng 2.1 và ngưỡng lợi ích tối thiểu minUtil = 230. Đầu tiên, US quét QSDB lần 1 để tính giá trị swu của các mục trong QSDB và tìm các mẫu dãy ứng viên lợi ích cao 1 phần tử. Các giá trị này lần lượt là: 34 Swu(a) = 602, swu(b) = 676, swu(c) = 226, swu(d) = 743, swu(e) = 546, swu(f) = 271, swu(g) = 67 Mục c,g bị loại vì swu nhỏ hơn minUtil. Tiếp theo lần lượt xây dựng các CSDL chiếu của từng mục ứng viên lợi ích cao. Tiền tố Cơ sở dữ liệu chiếu Ứng viên lợi ích cao và giá trị swu của chúng a (abd)fad: 130, (_b)d: 85, (bd)(ab)e: 180, (_b)dbe: 207 a:602, aa: 310, ab: 517, (ab): 602, ad: 602, ae: 387, a(ab): 310, aba: 310, a(bd): 310, abe: 387, a(bd)a: 310, (ab)d: 422, (ab)e: 387, ada: 410, adb: 387, ade: 387, adbe: 387 b (_d)fad: 130, d: 85, (de): 74, (_d)(ab)e: 180, dbe: 207 b: 676, ba: 310, bb: 387, bd: 496, (bd): 310, be: 461, bbe: 387, (bd)a: 310 d fad: 130, (_e): 74, (ab)e: 180, (_f): 67, e(ab)dbe: 207 d: 743, da: 517, db: 387, de: 387, dd: 337, dad: 337, d(ab): 387, dae: 387, d(ab)e: 387, dbe: 387 e (ab)d: 85, (ab)dbe: 207 e: 546, ea: 292, eb: 292, ed: 292, e(ab): 292, ead: 292, e(ab)d: 292, ebd: 292 f ad: 130, b(de): 74 f: 271 Bảng 2.4 Sinh mẫu dãy ứng viên trong thuật toán US 35 CSDL chiếu ứng với các tiền tố a, b, d, e, f thể hiện trong Bảng 2.4. Trong CSDL chiếu của tiền tố a, mục (_b) thể hiện phần hậu tố của a có thể nhóm với a để tạo thành mẫu dãy . Quét QSDB|a để tính giá trị swu của các mục trong QSDB|a. Ta có giá trị swu của các mục là a: 310, b: 517, _b: 602, d: 602, e: 387, f: 130. Mục f có swu < 230 nên không thể ghép với tiền tố a để tạo thành mẫu dãy ứng viên lợi ích cao. Ghép các mục còn lại với tiền tố a của chúng ta được các mẫu ứng viên lợi ích cao mới lần lượt là , , , , . Thực hiện sinh ứng viên theo phương pháp tăng trưởng mẫu dãy, tiếp tục xây dựng các CSDL chiếu ứng với các tiền tố , , , , . CSDL chiếu với tiền tố aa bao gồm các dãy: {(_bd)fad: 130, (_b)e: 180}. Quét CSDL này để tính swu của các mục trong nó, ta có a: 310, b: 180, d: 130, _d: 310, e: 387, f: 130. Chỉ có mục a có swu > minUtil, do vậy sau bước này chỉ sinh được một ứng viên lợi ích cao là . Quá trình lặp lại tương tự như vậy với các mẫu dãy khác, ta có kết quả là các ứng viên mẫu dãy lợi ích cao như trong Bảng 2.4 Sau khi tìm được tất cả các ứng viên mẫu dãy lợi ích cao, thuật toán US quét CSDL lần nữa để tính giá trị lợi ích thực sự của các ứng viên này. Kết quả cuối cùng giống như thuật toán UL là các mẫu dãy lợi ích cao gồm: {: 239, : 238, : 231, : 250} 2.4. Thuật toán PHUS Thuật toán UL và US của Ahmed đã có thể tìm ra được các mẫu dãy lợi ích cao trong CSDL dãy định lượng. Thuật toán UL dựa trên phương pháp tiếp cận Apriori sinh ứng viên và quét CSDL để kiểm tra. Phương pháp này có nhược điểm là sinh ra các ứng viên không tồn tại và phải quét CSDL nhiều lần. Thuật toán US đã khắc phục được 2 nhược điểm này bằng cách sử dụng phương pháp 36 tăng trưởng mẫu dãy của thuật toán PrefixSpan. Tuy nhiên, 2 thuật toán này vẫn là các thuật toán 2 pha: pha 1 tìm ứng viên mẫu dãy lợi ích cao và pha 2 tính lại lợi ích của các ứng viên để tìm mẫu dãy lợi ích cao thực sự. Ngoài ra, như đã phân tích ở trên, cách tính lợi ích cao của Ahmed đưa ra khá phức tạp và không phù hợp trong thực tế. Nhóm của Lan và cộng sự đã đề xuất thuật toán PHUS [29] để cải tiến thuật toán US của Ahmed. Trong công trình của mình, Lan đề xuất cách tính lợi ích dùng hàm lớn nhất (như mô tả trong phần 2.2 của luận văn này). Thuật toán PHUS vẫn sử dụng giá trị swu làm ngưỡng cận trên để tỉa bớt ứng viên trong không gian tìm kiếm. Ngoài ra, nhóm cũng đề xuất 1 số cải tiến cho thuật toán PHUS: - Thiết kế một cấu trúc bảng gọi là bảng lợi ích để duy trì ngưỡng cận trên và lợi ích thực của các mẫu dãy trong quá trình sinh mẫu dãy. Nhờ vậy không cần thêm 1 pha quét lại CSDL để tính lợi ích thực của mẫu dãy. - Giảm dần ngưỡng cận trên bằng cách tính lại lợi ích dãy đầu vào mỗi khi có một mục bị loại. - Thêm một bảng chỉ mục để tăng tốc tìm kiếm các mẫu dãy liên quan. Phần sau đây mô tả thuật toán PHUS và các cấu trúc dữ liệu sử dụng trong thuật toán. 2.4.1. Bảng lợi ích: Bảng lợi ích dùng để lưu và lấy ra các thông tin liên quan tới mẫu dãy trong khi khai phá. Mỗi dòng trong bảng lợi ích bao gồm 3 trường: mẫu dãy a, ngưỡng cận trên swu(a) và lợi ích thực của mẫu dãy su(a). Nhờ vậy, thuật toán PHUS có thể lấy được giá trị swu và su cùng 1 lúc trong quá trình khai phá. Nên PHUS 37 chỉ cần 1 pha thay vì 2 pha như các thuật toán UL, US. Bảng 2.5 là bảng lợi ích của các mẫu dãy 1 phần tử trong CSDL QSDB tại Bảng 2.1 ở trên. Ví dụ: mẫu dãy xuất hiện trong các dãy S1, S2, S4, S6; giá trị swu của là: swu()=130+85+180+207 = 602. Giá trị lợi ích của theo định nghĩa 2.5 là su() =100. Mẫu dãy swu su 602 100 676 203 226 30 743 120 546 90 271 48 67 18 Bảng 2.5 Bảng lợi ích của các mẫu dãy 1 phần tử trong QSDB 2.4.2. Bảng chỉ mục: Bảng chỉ mục được sử dụng để lưu vị trí của các mẫu dãy ứng viên lợi ích cao trong CSDL QSDB, giúp tăng tốc tìm kiếm các mẫu dãy trong quá trình xây dựng các CSDL chiếu. Bảng chỉ mục gồm nhiều dòng, mỗi dòng gồm 2 trường: mẫu dãy ứng viên và vị trí xuất hiện đầu tiên của nó trong CSDL. Lưu ý là bảng chỉ mục chỉ được sử dụng để lưu vị trí của các mẫu dãy 1 phần tử trong CSDL. Bảng chỉ mục của QSDB trong ví dụ ở trên được thể hiện trong Bảng 2.6. 38 Mẫu dãy 1 phần tử Vị trí (1,1), (2,2), (4,1), (6,3) (1,2), (2,2), (3,2), (4,3), (6,5) (1,2), (2,3), (3,3), (4,2), (6,1) (2,1), (3,3), (4,4), (6,2) (1,3), (3,1), (5,1) Bảng 2.6 Bảng chỉ mục Bảng chỉ mục bao gồm 5 dòng, mỗi dòng là một mẫu dãy ứng viên lợi ích cao và vị trí của nó. Mẫu dãy có vị trí là (1,1), (2,2), (4,1), (6,3) nghĩa là xuất hiện lần đầu trong dãy S1 trong tập mục đầu tiên, dãy S2 trong tập mục thứ 2, dãy S4 trong tập mục đầu và dãy S6 trong tập mục thứ 3. Các dòng khác trong bảng chỉ mục cũng được mô tả như vậy. Mô tả của thuật toán PHUS như sau: Input: CSDL dãy định lượng QSDB, ngưỡng lợi ích tối thiểu minUtil Output: Tập tất cả các mẫu dãy lợi ích cao HUS 1. Với mỗi dãy Si trong QSDB, thực hiện các bước sau: a. Tính giá trị lợi ích của mỗi mục aj trong Si b. Tính giá trị lợi ích của mẫu dãy Si 2. Với mỗi mục aj trong QSDB, thực hiện các bước: a. Tính ngưỡng cận trên swu của từng mục aj, nếu swu(aj) ≥ minUtil thì đưa aj vào tập các mẫu dãy ứng viên lợi ích cao 1 phần tử C1 b. Tính lợi ích thực su của aj, nếu su(aj) ≥ minUtil thì đưa aj vào HUS 3. Đặt r=1, r là độ dài của mẫu dãy ứng viên đang xét 39 4. Với mỗi dãy Si trong QSDB, thực hiện các bước: a. Lấy ra 1 mục aj trong Si b. Nếu aj xuất hiện trong C1 (nghĩa là aj là một ứng viên) thì giữ nguyên aj trong Si, nếu không thì loại aj khỏi Si c. Nếu số mục trong dãy Si nhỏ hơn r+1 thì loại bỏ dãy Si khỏi QSDB, không thì giữ nguyên Si 5. Xây dựng bảng chỉ mục cho mỗi mẫu dãy trong C1 6. Với mỗi mẫu dãy α trong C1, thực hiện các bước : a. Duyệt bảng chỉ mục và xây dựng CSDL chiếu QSDB|α, CSDL này bao gồm các dãy có chứa α trong QSDB b. Tính lợi ích của các mẫu dãy Sm trong QSDB|α c. Gọi thủ tục Finding-HUS(α, QSDB|α, r) để tìm các mẫu dãy lợi ích cao với tiền tố α và đưa vào tập HUS 7. Kết quả tập HUS là tập các mẫu dãy lợi ích cao trong QSDB. Thủ tục Finding-HUS(α, QSDB|α, r): Input: mẫu dãy ứng viên α, độ dài r của α, CSDL chiếu QSDB|α của α Output : tập các mẫu dãy lợi ích cao tiền tố α 1. Với mỗi dãy Sm trong QSDB|α, thực hiện các bước sau: a. Lấy ra các mục i đứng ngay sau tiền tố α trong Sm b. Sinh mẫu dãy α’ bằng cách ghép tiền tố α với mục i c. Tính lợi ích su và ngưỡng cận trên swu của α’, đưa các giá trị này vào bảng lợi ích 2. Duyệt bảng lợi ích, với mỗi mẫu dãy α’ trong bảng lợi ích, thực hiện các bước sau : a. Nếu swu(α’) ≥ minUtil, đưa α’ vào tập ứng viên Cr+1 b. Nếu su(α’) ≥ minUtil, đưa α’ vào tập HUS 3. Với mỗi dãy Sm trong QSDB|α, thực hiện các bước sau: 40 a. Loại bỏ các mục trong Sm mà không xuất hiện trong tập ứng viên Cr+1 b. Kiểm tra xem số mục trong Sm có nhỏ hơn r+2 không, nếu có thì loại bỏ dãy Sm 4. Với mỗi mẫu dãy ứng viên α’ trong tập ứng viên Cr+1, thực hiện các bước : a. Xây dựng CSDL chiếu của α’, ký hiệu QSDB|α’ bao gồm các dãy trong QSDB|α có chứa α’ b. Tính lại lợi ích của các mẫu dãy trong QSDB|α’ c. Tìm tất cả các mẫu dãy lợi ích cao với tiền tố α’ bằng cách gọi thủ tục Finding-HUS(α’, QSDB|α’, r+1) và đưa vào tập HUS Ví dụ minh họa thuật toán PHUS: Giả sử có một CSDL dãy định lượng QSDB như trong Bảng 2.1 và các giá trị lợi ích ngoài của các mục được thể hiện trong Bảng 2.2. Ngưỡng lợi ích tối thiểu minUtil = 230. Thuật toán PHUS được thực hiện như sau : Với mỗi dãy Si trong QSDB, thực hiện tính lợi ích của từng mục trong Si và lợi ích tổng của dãy Si. Kết quả của bước này được thể hiện trong 2 bảng dưới đây. Bảng 2.7 thể hiện lợi ích của các mục trong từng dãy. Bảng 2.8 là lợi ích của từng dãy trong QSDB. 41 Mục Lợi ích của mục trong dãy S1 S2 S3 S4 S5 S6 a 25 10 30 35 b 42 35 21 49 56 c 12 3 15 d 20 10 10 40 10 30 e 18 24 30 18 f 8 16 24 g 18 Bảng 2.7 Lợi ích của từng mục dữ liệu trong từng dãy Si Dãy dữ liệu Lợi ích S1 130 S2 85 S3 74 S4 180 S5 67 S6 207 Bảng 2.8 Lợi ích của các dãy Si Với mỗi mục tìm được ở trên, tính ngưỡng cận trên swu và lợi ích thực su của từng mục, kết quả lưu trong bảng lợi ích như Bảng 2.5. Mục c và g có cận trên nhỏ hơn minUtil nên bị loại. Các mục còn lại được đưa vào tập ứng viên 1 phần tử C1. Không mục nào có lợi ích thực lớn hơn minUtil nên tập mục lợi ích cao 𝐻𝑈𝑆 = ∅ 42 Sau khi đã biết mục c, g không là ứng viên lợi ích cao,