Khai phá tập mục thường xuyên cổ phần cao trong cơ sở dữ liệu lớn

KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN cổ PHÂN CAO
TRONG Cơ SỞ DỮ LIỆU LỚN
VŨ ĐỨC THI1, NGUYỄN HUY ĐỨC2
1 Viện Công nghệ thông tin, Viện Khoa học và Công nghệ Việt Nam
2Khoa Thông tin - Máy tính, Trường Cao đẳng Sư phạm Trung ương
Abstract. Itemsets share has been proposed to evaluate the significance of itemsets for mining association rules in databases. The Fast Share Measure (FSM) algorithm is one of the best algorithms to discover all share-frequent itemsets efficiently. However, FSM is fast only when dealing with small datasets. In this paper, we shall propose a revised version of FSM, called the Advanced FSM (AFSM) algorithm. AFSM prune the candidates more efficiently than FSM and therefore can improve the performance significantly.
Tóm tắt. Khai phá tập mục thường xuyên cổ phần cao (Share-Frequent Itemset) là một mờ rộng của bài toán khai phá tập mục thường xuyên, đã được các tác giả đề xuất với mục đích đánh giá ý nghĩa của các tập mục trong khai phá luật kết hợp. Thuật toán FSM ( Fast Share Measure) là một trong các thuật toán tốt để khai phá hiệu quả các tập mục thường xuyên cổ phần cao. Trong báo cáo này, chúng tôi đề xuất một cải tiến của thuật toán FSM. Việc cải tiến được thực hiện thông qua một chiến lược tỉa hiệu quả hơn các tập mục ứng viên, nhờ đó giảm bớt được thời gian thực hiện thuật toán khai phá.
MỞ ĐẦU
Bài toán cơ bản (hay còn gọi là bài toán nhị phân) khai phá luật kết hợp do Agrawal, T.Imielinski và A. N. Swami đề xuất và nghiên cứu lần đầu tiên vào năm 1993 [4], mục tiêu của bài toán là phát hiện các tập mục thường xuyên, từ đó tạo các luật kết hợp. Trong mô hình của bài toán nhị phân này, giá trị của mỗi mục dữ liệu trong một giao tác là 0 hoặc 1. Bài toán cơ bản khai phá luật kết hợp có nhiều ứng dụng, tuy vậy do tập mục thường xuyên chỉ mang ngữ nghĩa thống kê nên nó chỉ đáp ứng được phần nào nhu cầu ứng dụng thực tiln.
Nhằm khắc phục hạn chế của bài toán cơ bản khai phá luật kết hợp, nhiều nhà nghiên cứu đã mở rộng bài toán theo nhiều hướng khác nhau. Năm 1997, Hilderman và các cộng sự đã đề xuất bài toán khai phá tập mục thường xuyên cổ phần cao [7]. Trong mô hình khai phá tập mục thường xuyên cổ phần cao, giá trị của mục dữ liệu trong giao tác là một số, số đó có thể là số nguyên (như số lượng đã bán của mặt hàng) hoặc số thực (như số tiền lãi được khi bán mặt hàng đó), cổ phần (hay đóng góp) của một tập mục là số đo tỷ lệ đóng góp của tập mục trong cơ sở dữ liệu. Khai phá tập mục cổ phần cao là khám phá tất cả các tập mục có cổ phần không nhỏ hơn ngưỡng quy định bởi người sử dụng.
Trong bài toán cơ bản, các thuật toán khám phá được xây dựng theo phương pháp tìm kiếm từng bước. Cơ sở của các thuật toán là tính chất Apriori của tập mục thường xuyên (hay còn gọi là tính chất phản đơn điệu - Anti monotone). Trong mô hình khai phá tập mục cổ phần cao, tính chất này không còn đúng nữa. Vì vậy việc rút gọn không gian tìm kiếm không thể thực hiện được như đối với khai phá tập mục thường xuyên. Trong [5-11], các tác giả đã đề nghị một số thuật toán khám phá tập mục thường xuyên cổ phần cao như các thuật toán ZP, ZSP, SIP, FSM,.... Thuật toán FSM [6] là một thuật toán nhanh cho phép khám phá tất cả các tập mục thường xuyên cổ phần cao. Thuật tỉa mà thuật toán này áp dụng có khả năng thu gọn phần nào tập mục ứng viên, tuy vậy có những nhược điểm nên hiệu quả không cao.
Bài báo này trình bày một thuật toán hiệu quả khám phá tất cả các tập mục thường xuyên cổ phần cao trong cơ sở dữ liệu lớn: thuật toán AFSM. Thuật toán AFSM được xây dựng dựa trên ý tưởng của thuật toán FSM, nhưng việc tỉa các tập mục ứng viên được thực hiện thông qua một hàm tới hạn mới hiệu quả hơn. Thuật toán AFSM còn hiệu quả hơn thuật toán FSM nhờ cải tiến việc kết nối và tỉa các tập mục ứng viên. Nội dung tiếp theo của bài báo gồm: Phần 2 nêu một số định nghĩa, thuật ngữ và phát biểu bài toán khai phá tập mục thường xuyên cổ phần cao. Phần 3 tóm tắt nội dung và nêu những nhược điểm của thuật toán FSM. Phần 4 trình bày thuật toán mới AFSM. Phần 5 đánh giá thuật toán và kết luận dựa trên việc phân tích thuật toán và các thử nghiệm.
BÀI TOÁN KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN cổ PHAN CAO
Trước hết ta nêu định nghĩa của một số thuật ngữ ([6]).
Cho tập các mục (item) I = {AA25 Một giao tác (transaction) T là một tập con của 7, T c I. Cơ sở dữ liệu là một tập các giao tác DB = {T1,T2,	Mỗi giao tác
được gán một định danh TID. Một tập mục con X CT. gồm k mục phân biệt được gọi là một k - tập mục. Giao tác T gọi là chứa tập mục X nếu X CT:
Ta ký hiệu mu(íp, Tq) là giá trị của mục ip trong giao tác Tq. Tổng giá trị các mục trong giao tác Tq gọi là giá trị của giao tác, ký hiệu là tmv(Tq), tức là tmv(Tq) =	Tq).
Tổng các giá trị của các mục dữ liệu trong cơ sở dữ liệu DB ký hiệu là Tmv,
Tmv= V mv(h»Tq)-
TqEDBipETq
Tương tự, với cơ sở dữ liệu con db c DB, Tmv(db) = XpqEdb^ipeTqmv(ipi Tq).
Ví dụ, cho cơ sở dữ liệu Bảng 2.1, có mu(D, TOI) = 1, mv(C) T03) = 3, tmu(TOl) = 6, tmu(T03) = 10, Tmv[DB} = 47.
Bảng 2.1. Cơ sở dữ liệu ví dụ
TID
A
B
c
D
E
F
G
H
tmv
T01
1
1
1
1
1
1
6
T02
4
3
1
2
10
T03
4
3
3
10
T04
4
1
2
2
9
T05
3
1
2
6
T06
3
2
1
6
imv
12
9
10
6
4
4
1
1
47
Ký hiệu dbx là tập các giao tác chứa tập mục X, tức dbx = {Tq/X C Tq, Tq e DB}.
Định nghĩa 2.1. Cho giao tác Tq chứa tập mục X. Giá trị của tập mục X tại Tq, ký hiệu imv(x, Tq), là tổng giá trị của các mục ip trong Tq thuộc X, ímu(x, Tợ) =	mv(ip, Tq).
xeTq, iptx
Định nghĩa 2.2. Cho tập mục X, dbx là tập các giao tác chứa X. Giá trị của tập mục X, ký hiệu Zmu(x), là tổng giá trị của tập mục X tại các giao tác trong dbx, tức là
lmv(x) = imv(x, Tq) = E E mv(iP) Tq).
TqEdbx	TqEdbx ỉp^x
Định nghĩa 2.3. cổ phần (đóng góp) của tập mục X, ký hiệu là SH(X) là tỉ số giữa giá trị của tập mục X và tổng giá trị của tất cả các mục trong cơ sở dữ liệu, tức là SHÍXỶ1™^—-•
Tmv
SH(X) cho biết trong tổng giá trị của tất cả các mục trong cơ sở dữ liệu thì giá trị của tập X chiếm bao nhiêu phần trăm. Ví dụ, với CSDL các giao tác bán hàng, SH(X) = 25% tức là trong số lượng hàng đã bán được thì số lượng các mặt hàng trong X chiếm 25%.
Định nghĩa 2.4. Cho ngưỡng cổ phần minShare s% và tập mục X, X được gọi là tập mục thường xuyên cổ phần cao nếu SH(X) > minShare.
Ví dụ, xét cơ sở dữ liệu các giao tác cho trong Bảng 2.1 và minShare = 30%. Bảng 2.2 cho giá trị của các mục và giá trị cổ phần của chúng.
Bảng 2.2. Giá trị và cổ phần của các mục trong CSDL trên Bảng 2.1
Mục dữ liệu
M}
{B}
{C}
{D}
{E}
{E}
{ơ}
{H}
Tổng số
12
9
10
6
4
4
1
1
47
SH(ip)
25,5%
19,1%
21,3%
12,8%
8,5%
8,5%
2,1%
2,1%
100%
Xét X = {B, ơ, £>}, giá trị của tập mục X là
/mu(x) = ww(x, T01) + ww(x, T04) + ww(x, T06) = 3 + 7 + 6 = 16.
SH(X) = lmvỢO)/Tmv = 16/47 = 0.340 > 30%.
Do đó, X = {s, ơ, D] là tập mục thường xuyên cổ phần cao. Tập tất cả các tập mục thường xuyên cổ phần cao của cơ sở dữ liệu Bảng 2.1 được cho trong Bảng 2.3.
Bảng 2.3. Các tập mục thường xuyên cổ phần cao của CSDL Bảng 2.1
Tập mục thường xuyên cổ phần cao
ịA,C}
{B,D}
{A,C,E}
{B,C,D}
lmv(X)
16
15
18
16
SH(X)
34,0%
31,9%
38,3%
34,0%
Định nghĩa 2.5. Cho CSDL giao tác DB và ràng buộc cổ phần minShare, bài toán khai phá tập mục thường xuyên cổ phần cao là việc tìm tập F tất cả các tập mục thường xuyên cổ phần cao, tức là tập F = {x/x C 7, SH(X) > minShare}.
Có thể coi bài toán khai phá tập mục thường xuyên là trường hợp đặc biệt của bài toán khai phá tập mục thường xuyên cổ phần cao. Tính chất cơ bản được khai thác để xây
dựng các thuật toán khai phá tập mục thường xuyên là tính chất Apriori. Tính chất này có thể phát biểu như sau. Nếu một tập mục là thường xuyên thì mọi tập con khác rỗng của nó cũng là thường xuyên. Điều này có nghĩa các (k + l)-tập mục thường xuyên chỉ có thể được sinh ra từ các fc-tập mục thường xuyên. Dl thấy, tính chất này không còn đúng với ràng buộc cổ phần. Ví dụ, xét CDSL Bảng 2.1, /mc({B. c. B}) = 16,	=
/mế({B,ơ}) = 12, SH({B, Ơ, £>}) = 16/47 = 34%, SH({B,D}) = 15/47 = 31,9%, SH({B. CỴ) = 12/47 = 25, 5%, tức là {B, ơ, D} là tập thường xuyên cổ phần cao, tập con của nó {B, D} là tập thường xuyên cổ phần cao nhưng tập con khác {B, C} lại không phải.
Do đó không thể áp dụng các thủ pháp lợi dụng tính chất Apriori vào việc khai phá tập mục thường xuyên cổ phần cao. Đã có nhiều công trình nghiên cứu các thuật toán tìm tập mục thường xuyên cổ phần cao. Các tác giả đã đề xuất một số thuật toán như thuật toán ZP, ZSP, SIP,... [5-11]. Yu-Chiang Li và cộng sự đã giới thiệu thuật toán FSM (Fast Share Measure) [6], đây là một thuật toán hiệu quả tìm tất cả các tập mục thường xuyên cổ phần cao. Thay vì khai thác tính chất Apriori, thuật toán FSM sử dụng một số tính chất của tập mục thường xuyên cổ phần cao để rút gọn số các tập mục ứng viên. Phần tiếp theo dưới đây trình bày nội dung cơ bản của thuật toán FSM này cùng một số nhận xét.
THUẬT TOÁN FSM
Cơ sở lý thuyết của thuật toán FSM là mệnh đề sau đây ([6]).
Ký hiệu:
min _lmv = minShare X Tmv]
ML là độ dài cực đại của các giao tác trong cơ sở dữ liệu,
ML = max{|Tợ|/Tợ e BB};
MV là giá trị cực đại của tất cả các mục trong cơ sở dữ liệu,
MV = max{m'c(ip, Tq)/ip G Tq /\Tq e DB}-
Mệnh đề 3.1. Cho minShare và k-tập mục X không là tập thuờng xuyên cổ phần cao. Nếu
Imv(X) + LgAl X MV X (ML - k) < min Jmv
k
thì tất cả các tập cha của X không là tập thuờng xuyên cổ phần cao.
Đặt
CF(X) = lmv(X) + LgAl X MV X (ML - k)
k
CF(X) được gọi là hàm tới hạn. Mệnh đề trên đảm bảo rằng, nếu X không phải là tập thường xuyên cổ phần cao và ƠF(X) < min-/mu thì không có tập cha nào của X là tập thường xuyên cổ phần cao. Thuật toán FSM dựa vào tính chất này để tỉa các tập mục ứng viên.
Thuật toán FSM
Thuật toán FSM duyệt nhiều lần CSDL, ờ lần duyệt thứ fc, Ck lưu tập các tập mục ứng viên, RCk lưu các tập mục nhận được sau khi kiểm tra hàm tới hạn ƠF, Ffc chứa tập các tập mục thường xuyên cổ phần cao nhận được. Giống như thuật toán Apriori, mỗi mục đơn là một ứng viên. Trong lần duyệt thứ nhất, thuật toán duyệt CSDL tính giá trị của mỗi mục trong CSDL. Mỗi ứng viên 1- tập mục X sẽ bị tỉa nếu CF(X) < min/ mv. Trong mỗi lần duyệt tiếp theo, thuật toán nối hai (k — l)-tập mục ứng viên trong RCk-1 nếu chúng có (k — 2) mục đầu giống nhau và nhận được fc-tập mục (giả sử các mục của CSDL đã được sắp thứ tự). Tất cả k tập con với độ dài (fc — 1) của mỗi fc-tập mục trong Ck là phải thuộc RCk- nếu không fc-tập mục này sẽ bị tỉa. Sau khi Ck được sinh ra, xóa tập RCk-1' Tiếp theo, thuật toán duyệt cơ sở dữ liệu để tìm tập mục thường xuyên cổ phần cao. Với mỗi tập mục X trong C&, nếu tập mục này có lmv(X)/Tmv lớn hơn minShare thì X được thêm vào Ffc. Ngược lại, nếu CF(X) < ĩíìindmv thì tập ứng viên X bị loại khỏi RCỵ.
Quá trình trên cứ lặp cho đến khi không có tập mục ứng viên nào được sinh ra.
Nhận xét
Thuật toán FSM sử dụng hàm tới hạn ƠF(X) để thu gọn tập các tập mục ứng viên. Tuy vậy số các tập mục của tập RCk vẫn còn lớn do giá trị hàm tới hạn ƠF(X) còn cao. Hơn nữa thuật toán còn mất nhiều thời gian ờ bước nối mỗi cặp (fc — l)-tập mục trong RCk-1 để được một fc-tập mục.
Nhằm khắc phục những hạn chế của thuật toán FSM, chúng tôi đề nghị một thuật toán mới khai phá tập mục thường xuyên cổ phần cao trên cơ sở cải tiến thuật toán FSM, gọi là thuật toán AFSM (Advanced FSM).
THUẬT TOÁN AFSM
Cơ sờ lý thuyết
Định nghĩa 4.1. Cho cơ sở dữ liệu DB và fc-tập mục X. Một tập mục cha cỡ (k + 1) của X trong giao tác Tq được ký hiệu bằng Afc+1, ờ đó xk+1 QTqE DB.
Định nghĩa 4.2. Cho cơ sở dữ liệu DB và fc-tập mục X. Tập tất cả các tập cha cỡ (fc + 1) của X trong DB được ký hiệu bằng S(Afc+1), ờ đó xk+1 e S(xk+1).
Định nghĩa 4.3. Cho cơ sở dữ liệu DB và fc-tập mục X. Tập tất cả các giao tác chứa ít nhất một xk+1 được ký hiệu bằng dbS(Xk+iy Độ hỗ trợ của S(Xk+1) ký hiệu bằng Sup(S(Xfc+1)) và Sup(S(Xfc+1)) = \dbS(Xk+i)\.
Ví dụ, trong Bảng 2.1, lấy X = {B, c, D} ta có:
xk+1 là {A, B, c, D}, {B, C,D, ơ}, {B, c, D, H}, và {B, c, D, F}.
S(Xfc+1) = {{A, B, c, D}, {B, c, D, G}, {B, c, D, H}, {B, c, D, F}}. dbS(Xk+i} = {TOI, T04}, Sup(S(Xfc+1)) = 2.
Vơi X = {B, c, D, F} thì dbs(xk+i) = ý), Sup(S(Xk+1Ỵ) = 0.
Dl dàng nhận thấy UgíY > Sup(X) > Sup(S(Xk+1Y) > . max . Sup(S(Xk+1V). k
Định lý 4.1. Cho cơ sở dữ liệu DB và k-tập mục X. Ta có:
Tmv(dbs^Xkiỉ^ < ImvỢC) + \dbS(^Xk+y\MV{ML — kỴ
Chứng minh:
Với mọi giao tác Tq G DB chứa X ta có:
tmv(Tq) = mv(ipì Tq)
tpETq
= mv(ip,Tq) + mv(ip,Tq) < imv(X,Tq) + MV(ML — fc).
ipEX	tpeTq\X
Do đó:
Tmv[dbS(Xk+iỵ) =	tmv(Tq) <	[imv(X,Tq) + MV(ML — k)
TqEdbs^x^_ị-i^	TqEdbS(Xkxi}
< irnv(x, Tq) + l^sp^+1)\MV(ML - k) = TqEdbx
ỉmv(X) + \dbs(xk+i}\MV(ML - kỴ
ta CÓ	V kmv(x, Tq) < imv(X,Tq) vì db$(Xk+iì C dbx
TqEdb s	TqEdbx
■
Định lý 4.2. Cho nguỡng minShare và k-tập mục X không là tập mục thuờng xuyên cổ phần cao. Nếu Tmv(dbs^Xk+ỉ^ < min _lmv thì mọi tập cha của tập mục X đều không phải tập mục thuờng xuyên cổ phần cao.
Chứng minh:
Giả sử X' là tập mục cha bất kỳ của X với độ dài (fc + i), trong đó 0 < i < [ML — kỴ Vì dbX' Q dbS(Xk+i) nên Tmv(dbx') < Tmv(dbS(Xk+iỵ)'
Do đó lmv[xf} < Tmv(dbxf) < Tmv(dbS(Xk+iỵ)' Nếu Tmv(dbS(Xk+iỵ) < ĩữiĩdmv thì lmv(x') < minJnw, SH[Xf) = lmp^ ) < minShare.
Vậy xf không là tập mục thường xuyên cổ phần cao.	■
Nhận xét 4.1. Từ Định lý 4.2, có thể sử dụng Tmv[dbs^xk+ỴỴ) làm hàm tới hạn cho thuật toán mới AFSM để tỉa các tập mục ứng viên. Ký hiệu hàm tới hạn của thuật toán FSM và thuật toán mới AFSM tương ứng là CFfsm[X) và CFafsm(XỴ Định lý sau so sánh giá trị của 2 hàm tới hạn này.
Định lý 4.3. Cho cơ sà dữ liệu DB và k-tập mục X. Khi dó:
CFafsmX) < CFfsmX)-
Chứng minh:
Ta có CFafsmX) = Tmv(dbs(xk+X CFfsmX) = lmv(X) + lmV^MV(ML - k).
Theo Định lý 4.1 ta có
Tmv[dbS(Xk+iỵ) < lmv(x) + |d&5(Xfc+i)|MV(ML — kỴ
Vì	|d6s(ẤHl)| = Sup(S(Xfc+1)) < Sup(X) < lmv^
nên ta có:
CFafsm(X) = Tmv(dbS(Xk+i)) < lmv(X) + \dbS(Xk+i)\MV(M L - k)
< lmv(X) + lini'^X) MV(ML - k) = CFfsm(X).
k
Vậy CFafsm (X) < CFfsm (X).	■
Nhận xét 4.2. Từ kết quả của Định lý 4.3, ta thấy rằng thuật toán AFSM sẽ tỉa các tập mục ứng viên nhiều hơn do giá trị của hàm tới hạn nhỏ hơn, do đó tập RCk được sinh ra nhỏ hơn. Điều này làm cho thuật toán AFSM thực hiện hiệu quả hơn thuật toán FSM.
Thuật toán AFSM
Dựa trên ý tưởng của thuật toán FSM, chúng tôi xây dựng thuật toán mới AFSM như sau:
Sử dụng hàm tới hạn mới CFafsm{X) = Tĩĩi.vỊdb^ỵkiiỷ cho thuật toán AFSM.
Cải tiến bước sinh tập ứng viên: Trong thuật toán FSM, quá trình sinh tập ck đòi hỏi
phải kết nối các cặp tập mục trong RCk-1' Thuật toán phải so sánh (k — 2) mục đầu của hai (k — l)-tập mục trong RCk-1, do đó độ phức tạp thời gian để sinh ck là ơ(n2fc_2), ở đó n là số các mục. Để rút gọn thời gian thực hiện ở bước sinh tập ứng viên, chúng tôi cải tiến như sau: thay cho việc nối hai (k — l)-tập mục bất kỳ trong	chúng ta kết nối mỗi tập
(k — l)-tập mục trong RCk-1 với một mục đơn trong RCỵ để sinh ra tập ck. Với cải tiến này, thời gian thực hiện ở bước sinh tập ứng viên giảm xuống là O(nk}.
Giả sử các mục trong cơ sở dữ liệu đã được sắp thứ tự. Xét (k — l)-tập mục ứng viên xk~ỵ = {31^2, ...,3fc-i} và 1-tập mục X1 = {iq} e RCỵ. Nếu ik_L < iq thì tập xk = {31^2,ik-b iq} là một fc-tập mục ứng viên thuộc C&. Tiếp đến, ở bước tỉa, thủ tục sẽ xóa tất cả các tập mục xk E ck nếu xk chứa ít nhất một (fc — l)-tập mục con không thuộc RCk-1' Thủ tục nối và tỉa như sau.
Function NơiỤRCk-i, RCỵ)
Ck := 0;
for each Xp = {31,32, •••, ik-1} E RCk-1
for each iq E RC1
if ik—i < iq then {
x = xpu{iq};
Ck:=CkU{X};}
Function Tia(Ck)
for each X E ck
if (có một tập con k — 1 mục của X không thuộc RCk-1) then
Ck\=Ck\{X}
Từ các cơ sở lý thuyết đã trình bày, chúng tôi đề nghị thuật toán AFSM như sau.
Thuật toán AFSM( )
Input: DB cơ sở dữ liệu giao tác, ngưỡng cổ phần minShare(s%).
Output: Tập F gồm các tập mục thường xuyên cổ phần cao.
Method:
fc:=l, F1 :=ự), ƠI :=z
for each T G DB // duyệt cơ sở dữ liệu DB
tính giá trị các 1-tập mục trong T; // tính lmv(ip) và cho mỗi
for each ip G Cl
if lmv(ip) > ĩữiĩdmv then
Fl := Fl u {ip}
else if CFafsm(1p) < min Jmv then
Cl := C1\U}
FC1 := Cl
repeat
fc:=fc+l
ck := Noi(RCk-i,RCi)
if (fc > 2) then ck := Tia{Ck)
for each T G DB ỊI duyệt	cơ sở dữ liệu DB
tính giá trị mỗi tập ứng viên thuộc T
for each X G ck
if lmv(x) > min _lmv then
Ffc := Ffc u {X}
else if CFafsmỢQ < min Jmv then
ck := Ck\{X}
RCk := ck
until ck = Ộ
return F = UFfc
Ví dụ, cho cơ sở dữ liệu giao tác là Bảng 2.1, minShare = 30%. Thuật toán AFSM thực hiện việc phát hiện các tập mục thường xuyên cổ phần cao như sau:
Ta có: Tmv = 47, MV = 4, ML = 6, min Jmv = minShare X Tmv = 30% X 47 = 14,1. Bước k=l. Thực hiện dòng lệnh 1 cho kết quả F1 = ự), Cl = {A.B.C.D.E.F.G.H}. Thực hiện dòng lệnh 2-3 ta tính được Imv của các mục dữ liệu. Bảng 4.1 sau biểu diln các kết quả tính toán sau.
Bảng 4.1. Các giá trị Imv và hàm tới hạn với k=l
A
B
c
D
E
F
G
H
Imv
12
9
10
6
4
4
1
1
CFafsm
32
27
41
27
20
19
6
6
CFfsm
252
189
210
126
84
84
21
21
Vì các giá trị Imv đều nhỏ hơn min _lmv = 14,1 nên không có mục nào là cổ phần cao.
d&S({A}2) = {T01,T02,T03,T05},
CFafsm({A}) = Tmv{dbs^A}2)) = tmu(TOl) + tmv(T02) + tmv(T03) + tmv(T05)
= 6 + 10 + 10 + 6 = 32 > mindmv,
do đó A không bị tỉa khỏi C1> Làm tương tự ta có G và H bị tỉa. Thực hiện các lệnh từ 4-8 ta nhận được F1 = ự), ƠI = {A, B, ơ, F>, F, F}. Dòng lệnh 9 cho kết quả RCi =
Bước k=2. Dòng lệnh 12 nối RC1 với RC1 ta được 15 tập mục độ dài k = 2. Dòng lệnh 13 thực hiện thủ tục tỉa nhưng không tỉa được tập mục nào.
Thực hiện các lệnh 14-20 cho kết quả là Bảng 4.2 sau.
Bảng 4.2. Các giá trị Imv và hàm tới hạn với k=2
AB
AC
AD
AE
AF
BC
BD
BE
BF
CD
CE
CF
DE
DF
EF
Imv
6
16
7
12
6
12
15
0
6
8
9
8
0
4
3
CFAFSM
12
26
12
20
10
21
15
0
9
21
20
19
0
10
10
CFFSM
54
144
63
108
54
108
135
0
54
72
81
72
0
36
27
Từ bảng trên ta có: F2 = {AC, BD}, c2 = {AC, AE, BC, BD, CD, CE, CF}. Dòng lệnh 21 cho ta RC2 = {AC, AE, BC, BD, CD, CE, CF}.
Lặp tiếp với k = 3, dòng lệnh 12 thực hiện nối RC2 với RC1 ta được:
Ơ3 = {ACD, ACE, ACF, AEF, BCD, BCE, BCF, BDE, BDF, CDE, CDF, CEF}.
Dòng lệnh 13 thực hiện tỉa: ACD bị tỉa vì có tập con AD không thuộc RC2. Xét tương tự có 10 tập mục bị tỉa khỏi Ơ3 và ta được Ơ3 := tia(C3) = {ACE, BCD}.
Thực hiện duyệt cơ sở dữ liệu và tính toán ta được kết quả là Bảng 4.3 sau.
Bảng 4-3. Các giá trị Imv và hàm tới hạn với k=3
ACE
BCD
Imv
18
16
CFAFSM
10
15
CFFSM
90
80
F3 = {ACE, BCD}, Ơ3 = {ACE, BCD}, RC3 = {ACE, BCD}.
Lặp tiếp với k = 4: nối RC3 với BƠI ta được Ơ4 = {ACEF, BCDE, BCDF}. Các tập mục này đều bị tỉa vì có tập con không thuộc RC3, do đó Ơ4 = tia(C^) = ộ, thuật toán dừng.
Kết quả thuật toán tìm được tập các tập mục thường xuyên cổ phần cao F = Fl UF2UF3 = {AC, BD, ACE, BCD}.
Chủ ý\ các Bảng 4.1, 4.2 và 4.3 tính cả giá trị hàm tới hạn của thuật toán FSM để so sánh. Ta thấy giá trị của CFfsm lớn hơn giá trị của CFafsm rất nhiều, khi k = 1 thuật toán FSM không tỉa ơ và H, lặp với k = 2, thuật toán FSM chỉ tỉa 2 tập mục BE và DE, trong khi đó thuật toán Afsm tỉa 8 tập mục.
Kết quả thực hiện của thuật toán được minh họa ờ Hình 4.1 sau.
Hình 4-1. Hình minh họa không gian tìm kiếm tập mục thường xuyên cổ phần cao
theo thuật toán AFSM
ĐÁNH GIÁ THUẬT TOÁN VÀ KET luận
Chúng tôi đã tiến hành thử nghiệm thuật toán AFSM trên một số cơ sở dữ liệu giao tác được tạo bằng phương pháp tạo số ngẫu nhiên. Căn cứ vào các kết quả thử nghiệm và phân tích thuật toán, chúng tôi nhận thấy AFSM có những ưu điểm sau so với FSM.
Thu gọn đáng kể không gian tìm kiếm nhờ hàm tới hạn có giá trị nhỏ hơn nhiều giá trị hàm tới hạn của thuật toán FSM. Điều này làm cho thuật toán thu gọn ngay không gian tìm kiếm từ lần lặp đầu, từ đó ảnh hưởng đến các lần lặp sau làm cho tập RCk có kích thước nhỏ. Ví dụ, đối với cơ sở dữ liệu trong Bảng 2.1, ngay từ đầu xét các mục đơn đã có G và H bị loại, trong khi đó theo thuật tỉa của FSM thì các mục này không bị tỉa. Với cơ sở dữ liệu lớn có thể hy vọng AFSM sẽ thu gọn không gian tìm kiếm nhiều hơn.
Thuật toán AFSM thay đổi cách nối và tỉa khi sinh tập ứng viên Ck bằng cách nối một tập mục độ dài (fc — 1) với một mục đơn đã giảm thời gian ờ bước nối từ O(n2k~2) xuống còn O(nkỴ
Số lần duyệt cơ sở dữ liệu của thuật toán AFSM so với thuật toán FSM là như nhau.
Với những ưu điểm trên đây, chúng tôi cho rằng thuật toán AFSM hiệu quả hơn so với thuật toán FSM trong [6].
TÀI LIỆU THAM KHẢO
Vũ Đức Thi, Cơ sở dữ liệu - Kiến thức và thục hành, Nhà xuất bản Thống kê, năm 1997.
Nguyễn Thanh Tùng, Khai phá tập mục lợi ích cao trong cơ sờ dữ liệu, Tạp chí Tin học và ■Điều khiền học 23 (4) (2007) 364-373.
Nguyễn Huy Đức, Khai phá luật kết hợp trong cơ sờ dữ liệu lớn, Kỷ yếu Hội thảo khoa học Quốc gia lần thứ nhất về nghiên cứu cơ bản và ứng dụng CNTT. Hà Nội, 10/2003.
R. Agrawal and R. Srikant, Fast algorithms for mining association rules, Proceedings of 20th International Conference on Very Large Databases, Santiago, Chile, 1994.
B. Barber and H. J. Hamilton, Extracting share frequent itemsets with infrequent subsets, Data Mining and Knowledge Discovery 7 (2) (2003).
Y. c. Li, J. s. Yeh, and c. c. Chang, A fast algorithm for mining share-frequent itemsets, “Lecture Notes in Computer Science”, Springer-Verlag, Germany, 3399 (2005) 417-428.
R. J. Hilderman, C.L. Carter, H. J. Hamilton, and N. Cercone, Mining association rules from market basket data using share measures and characterized itemsets, Journal of Artificial Intelligence Tools 7 (1998) 189-220.
C.L. Carter, H. J. Hamilton, and N. Cercone, Share based measures for itemsets, Lecture Notes in Computer Science, Springer-Verlag, Germany, 1263 (1997) 14-24.
B. Barber and H. J. Hamilton, Parametric algorithm for mining share frequent itemsets, Journal of Intelligent Information Systems 16 (2001) 277-293.
B. Barber and H. J. Hamilton, Algorithms for mining share frequent itemsets containing infrequent subsets, “Lecture Notes in Computer Sciences”, Springer-Verlag, Germany, 1910 (2000) 316-324.
T.Y. Lin, Y. Y. Yao, and E. Louie, Value added association rules, Advances in Knowledge Discovery and Data Mining, 6th Pacific-Asia Conference, Taipei, 2002.
Y. D. Shen, Q. Yang, and z. Zhang, Objective-oriented utility-based association mining, Proceedings of the 13th ACM SIGMOD International Conference on Knowledge Discovery and Data mining, San Jose, California, USA, 2007.
G.I. Webb, Discovering association rules with numeric variables, Proc, of the 7th KDD, 2001. NOI DAU?
H. Yao, H. J. Hamilton, Mining itemsets utilities from transaction databases, Data and Knowledge Engeneering 59 (3) (2006).
H. Yao, H. J. Hamilton, and c. J. Butz, A foundational approach to mining itemset utilities from databases, Proceedings of the 4th SIAM International Conference on Data Mining, Florida, USA, 2004.
IBM Synthetic data,  2004.
H. Yao, H. J. Hamilton, and L. Geng, A unified framework for utility based measures for mining itemsets, UBDM’06 Philadelphia, Pennsylvania, USA, August 2006.
Nhận bài ngày 7 - 7 - 2008