Các thuật toán theo cấu trúc dàn kết hợp cấu trúc utiity-list [13]

CƠ SỞ LÝ THUYẾT

CHƯƠNG 3 ĐÁNH GIÁ CÁC THUẬT TOÁN

3.3. Các thuật toán theo cấu trúc dàn kết hợp cấu trúc utiity-list [13]

Các thuật toán này được thực hiện chủ yếu bằng hướng tìm kiếm theo chiều sâu đồng thời mở rộng các item của một itemset. Đây cũng là cấu trúc cây theo lớp tương đương nhưng mỗi lớp được xây dựng tựa tìm kiếm theo chiều sâu. Các hình dưới đây minh họa việc xây dựng cây.

4 Bx123456710

254

Cx2457910 376

Ax39 407

Dx1 527

BCx9 144

BDx{}

254

{}x12345678910

ADx1 349 CDx1

318 Item

Diffset

TWU

BAx9 144

CAx3 308

CADx1 250 BCAx{}

144

BCDx{}

144

BCADx{}

144

BADx{}

144

Hình 3.8: Minh họa cách mở rộng itemset từ các item.

 {a}

{a, b}

{a, b, c} {a, b, d} {a, b, e}

{a, b, c, d} {a, b, d, e}

{a, b, c, d, e}

 {a}

{a, b}

{a, b, c} {a, b, d} {a, b, e}

{a, b, c, d} {a, b, d, e}

{a, c}

...

 {a}

{a, b}

{a, b, c} {a, b, d} {a, b, e}

{a, b, c, d} {a, b, d, e}

{a, c}

…

{a, d} {a, e}

{b} …

{b, c} …

… … …

{a, b, c, d, e}

Thành phần quan trọng nhất là utility-list chứa các thông tin cần thiết của một itemset. Danh sách đó nhƣ trong bảng 3.3

Bảng 3.3: Một thành phần trong danh sách utility-list Trans. util rutil

T1 38 20

T3 38 30

T2 2 0

Một thành phần trong danh sách utility-list gồm ba cột:

- Cột một là danh sách các giao tác chứa itemset - Cột hai là độ có ích của itemset trong các giao tác đó

- Cột ba là độ có ích còn lại, nghĩa là độ có ích của các item xuất hiện sau itemset trong giao tác đó. Độ có ích còn lại là một khái niệm cải tiến đáng kể trong các thuật toán HUI-Miner và FHM. Nhờ có khái niệm này chúng ta dễ dàng có bổ đề “nếu tổng tất cả độ có ích và độ có ích còn lại trong utility-list của X nhỏ hơn một ngưỡng cho trước thì bất cứ mở rộng X‟ đều không vượt qua ngƣỡng”

Tiếp theo là phép kết giữa hai itemset, phép kết này có độ phức tạp cao

Utility list of {a} Utility list of {d} Utility list of {a, d}

Trans. Util Rutil Trans. Util Rutil Trans. Util Rutil

T0 5 20 T0 6 3 T0 11 3

T2 5 3 join T1 3 5 T2 7 0

T3 10 12 T2 2 0

u({a}) = 20$ u({d}) = 11$ u({a, d}) = 18$

Hình 3.9: Minh họa phép kết

Trong phép kết giữa 2 tập mục, đầu tiên lấy phần giao tác chung xuất hiện trên cột 1, tiếp theo tính độ có ích trong cột 2 (đối với các tập mục không tồn tại tiền

tố thì đơn giản cộng giá trị có ích của hai tập mục, còn các tập mục tồn tại tiền tố thì cộng giá trị 2 tập mục rồi trừ cho phần có ích chung), cuối cùng là tính độ có ích còn lại bằng cách lấy phần nhỏ.

3.3.1. Thuật toán Hui-Miner [13]

Input: P.UL, the utility-list of itemset P, initially empty;

ULs, the set of utility-lists of all P’ 1-extensions;

minutil, the minimum utility threshold.

Output: all the high utility itemsets with P as prefix.

1 foreach utility-list X in Uls do

2 if SUM(X.iutils) ≥ minutil then

3 output the extension associated with X;

4 end

5 if SUM(X.iutils)+SUM(X.rutils) ≥ minutil then

6 exULs = NULL;

7 foreach utility-list Y after X in Uls do 8 exULs= exULs +Construct(P.UL, X, Y );

9 end

10 HUI-Miner(X, exULs, minutil);

11 end

12 end

Hình 3.10: Thuật toán Hui-Miner Thuật toán: Construct

Input: P.UL, the utility-list of itemset P;

Px.UL, the utility-list of itemset Px;

Py.UL, the utility-list of itemset Py.

Output: Pxy.UL, the utility-list of itemset Pxy.

1 Pxy.UL = NULL;

2 foreach element Ex ∈ Px.ULdo

3 if∃Ey∈Py.Ul and Ex.tid==Ey.tid then 4 if P.UL is not empty then

5 search such element E ∈P.UL that

E.tid ==Ex.tid;

6 Exy =<Ex.tid, Ex.iutil +Ey.iutil -E.iutil,Ey.rutil >;

7 else

8 Exy =<Ex.tid, Ex.iutil +Ey.iutil, Ey.rutil >;

9 end

10 append Exy to Pxy.UL;

11 end

12 end

13 return Pxy.UL;

Hình 3.11: Thủ tục Construct

Để giảm chi phí cho phép kết, thuật toán FHM sử dụng bảng EUCS.

Bảng 3.4: Minh họa bảng EUCS

B C A D

C 144

A 144 308

D 254 318 349

3.3.2. Thuật toán FHM [14]

Input: D: a transaction database, minutil: a user-specified threshold Output: the set of high-utility itemsets

1. Scan D to calculate the TWU of single items;

2. I*  each item I such that twu(i)  minutil;

3. Let be the total order of TWU ascending values on I*;

4. Scan D to built the utility-list of each item i  I* and built the EUCS structure

5. Search (, I*, minutil, EUCS);

Hình 3.12: Thuật toán FHM

Giải thuật trước tiên quét CSDL để tính TWU cho mỗi item. Sau đó, giải thuật nhận ra tập I* của tất cả các item có TWU không nhỏ hơn minutil (các item khác đƣợc bỏ đi vì chúng không phải là thành phần của các tập có lợi ích cao theo tính chất 2.3). Giá trị TWU của các item sau đó đƣợc sử dụng để thiết lập 1 thứ tự toàn phần trên các mục, đây là thứ tự tăng dần của các TWU. Lần quét CSDL thứ hai đƣợc tiến hành. Trong suốt quá trình quét CSDL này, các item trong giao dịch đƣợc sắp xếp lại theo thứ tự toàn phần , danh sách lợi ích của mỗi mục i I* đƣợc xây dựng và cấu trúc đó đƣợc đặt tên là EUCS. Cấu trúc mới này đƣợc định nghĩa nhƣ 1 bộ 3 có dạng (a, b, c)  I* x I* x R. Bộ 3 (a, b, c) chỉ ra rằng twu({a,b}) = c. EUCS có thể đƣợc triển khai nhƣ ma trận 3 chiều đƣợc mô tả trong bảng 3.4 hoặc nhƣ 1 bảng băm với các bộ có dạng (a, b, c) sao cho c 0 đƣợc giữ lại. Sau khi xây dựng EUCS, giải thuật tìm kiếm theo chiều sâu bắt đầu gọi thủ tục đệ quy Search với tập mục rỗng , tập các mục đơn I*, minutil và cấu trúc EUCS.

Input: P: an itemset, ExtensionsOfP: a set of extensions of P, the minutil Threshold, the EUCS structure

Ouput: the set of high-utility itemsets 1. foreach itemset Px ExtensionsOfP do

2. if sum (Px.utilitylist.iutils)  minutil then

3. output Px;

4. end

5. if sum(Px.utilitylist.iutils) + Sum(Px.utilitylist.rutils)  minutil then

6. ExtensionsOfP  

7. foreach itemset Py  ExtensionsOfP such that y x do 8. if (x,y,c)  EUCS such that c  minutil then

9. Pxy Px Py

10. Pxy.utilitylist  construct(P, Px, Py);

11. ExtensionsOfPx ExtensionsOfPx Pxy;

12. end

13. end

14. Search (Px, ExtensionsOfPx, minutil);

15. end

16. end

Hình 3.13: Thủ tục Search Giải thuật thủ tục Search nhận đầu vào là:

(1) Tập mục P,

(2) Mở rộng của P có dạng Pz nghĩa là Pz thu được trước đó bằng việc thêm 1 item z vào P,

(3) Minutil và (4) EUCS.

Thủ tục search thực hiện nhƣ sau: Với mỗi mở rộng Px của P, nếu tổng giá trị iutil của utility-list của Px không nhỏ hơn minutil, thì Px là tập mục lợi ích cao và xuất ra. Nếu tổng của giá trị của Iutil và Rutil trong danh sách lợi ích của Px không nhỏ hơn minutil thì điều đó có nghĩa là mở rộng của Px nên đƣợc khám phá. Điều này đƣợc thực hiện bằng việc gộp Px với tất cả các mở rộng Py của P sao cho y x để tạo nên dạng mở rộng Pxy chứa |Px| +1 mục. Danh sách lợi ích của Pxy đƣợc xây dựng nhƣ giải thuật HUI-Miner bằng việc gọi thủ tục Construct để kết danh sách lợi ích của P, Px và Py. Thủ tục này cũng giống với HUI-Miner [13]. Sau đó, 1 lời gọi đệ quy gọi thủ tục Search để hoàn thành việc tính toán lợi ích của Pxy và khám phá các tập mở rộng của nó. Vì thủ tục Search bắt đầu từ các mục đơn, nó khám phá đệ quy không gian tìm kiếm của các tập mục bằng việc thêm vào các mục đơn và nó chỉ cắt giảm không gian tìm kiếm dựa vào bổ đề 2.1. Nhờ có bảng EUCS nên không gian tìm kiếm giảm đi. Ví dụ: theo bảng 1.1 và 1.2, đối với thuật toán Hui-Miner, không gian tìm kiếm là 10 itemset, trong lúc đó đối với thuật toán FHM, không gian tìm kiếm là 8 itemset..