Xem mẫu
- Nguyễn Hữu Trọng, Lê Đức An, Trần Xuân Việt, Nguyễn Anh Hào
MỘT THUẬT TOÁN TÌM TẬP THƯỜNG XUYÊN
TRÊN CƠ SỞ DỮ LIỆU GIAO TÁC CÓ TRỌNG SỐ
A NEW METHOD TO MINE FREQUENT ITEMSETS
ON TRANSACTION DATA WEIGHTED
Nguyễn Hữu Trọng1 , Lê Đức An2 , Trần Xuân Việt2 , Nguyễn Anh Hào2
1
Trường Đại học Nha Trang; Email: trongnhntu@gmail.com
2
Trường Đại học Quy Nhơn; Email: an.leduc@gmail.com, cntranxuanviet@yahoo.com,
Hao.nguyenvan1979@gmail.com
Tóm tắt – Tìm tất cả các tập mục dữ liệu thường xuyên là công việc Abstract – Find all of the frequent itemsets are basic work in data
cơ bản trong khai phá dữ liệu. Trong hơn 20 năm từ ngày Agrawal mining. For more than 20 years from the date of Agrawal and
và các cộng sự đưa ra thuật toán AIS, các nhà nghiên cứu đã đề colleagues provide AIS algorithm, the researchers have proposed
xuất nhiều thuật toán cải tiến về tốc độ để phát hiện nhanh những many improved algorithms for detecting fast pace of the frequent
tập mục dữ liệu thường xuyên. Những thuật toán này, một hướng itemsets. These algorithms, an improved focus on navigating the
tập trung vào cải tiến cách duyệt qua tập dữ liệu và cách tính độ hỗ data sets and how to calculate the support of each candidate item
trợ của từng tập mục dữ liệu ứng viên, một hướng khác, tập trung set, a different direction, focusing on the reduced size and split
vào việc rút gọn kích thước và phân nhỏ cơ sở dữ liệu được xử lý. the data into several clusters. In this paper, we propose algorithms
Trong báo cáo này, chúng tôi đề xuất thuật toán CABOWD, nhằm CABOWD (clustering algorithm based on weighted data), in order to
rút ngắn thời gian tìm các tập thường xuyên theo hướng phân nhỏ shorten the time by the way to split the data and reduce data size.
và rút gọn kích thước dữ liệu.
Từ khóa – cơ sở dữ liệu giao tác, luật kết hợp; tập thường xuyên; Key words – database transactions; association rules; frequent
phân cụm; trọng số. practice; clustering; weight.
1. Đặt vấn đề AIS, năm 1994 Agrawal và Srikant đưa ra thuật toán Apriori
Cho I = {x1 , x2 , . . . , xn } là tập hợp các mục dữ liệu. [3], thuật toán đặt nền móng cho việc tìm tất cả các tập
Một tập con t={xi1 , xi2 , . . . , xik } ⊆ I gọi là một giao tác thường xuyên và luật kết hợp. Hạn chế lớn nhất của thuật
trên I. Một tập hợp gồm m giao tác T = {t1 , t2 , . . . , tm } gọi toán Aprori là duyệt qua cơ sở dữ liệu quá nhiều lần, đặc biệt
là một cơ sở dữ liệu (CSDL) giao tác trên I. Mỗi tập hợp X với dữ liệu lớn, lưu trữ ở bộ nhớ ngoài thì thời gian duyệt
⊆ I gọi là tập mục dữ liệu (itemset), mỗi tập con S ⊆ T gọi quá lớn, việc tìm tất cả tập thường xuyên không khả thi.
là một giao tác. Độ hỗ trợ (support) của một tập mục dữ liệu Thuật toán FP_Growth do nhóm nghiên cứu của Jiawei
X, ký hiệu Supp(X) là số các giao tác trong T chứa X. Để Han trường đại học Illinois Hoa Kỳ đề xướng năm 2000 [4]
đơn giản, quy ước dùng Supp(xi ) thay cho Supp({xi }) khi và trình bày đầy đủ trong [5]. Hạn chế của các thuật toán
tập chỉ có một mục dữ liệu. Cho S0 là một số nguyên, ta nói FP_Growth là với dữ liệu lớn, việc đệ quy để tìm tất cả các
X là tập mục dữ liệu thường xuyên (frequent itemset) theo tập thường xuyên của FP_Growth tốn một thời gian khá lớn.
ngưỡng S0 nếu Supp(X) ≥ S0 . Một biểu thức X1 → X2 , Khi dữ liệu lớn, việc đệ quy có thể tràn bộ nhớ, không thể
với X1 , X2 ⊆ I và X1 ∩ X2 = φ được gọi là một luật kết thực hiện được. Nhiều cải tiến FP_Growth đã được tổng hợp
hợp (Association rule) trên T. Độ hỗ trợ của luật kết hợp trong [9].
X1 → X2 , ký hiệu Supp(X1 → X2 ) = Supp(X1 ∪ X2 ) =
Supp(X1 X2 ). Luật kết hợp f:X1 → X2 trên T là luật thường 3. Phân cụm dữ liệu
xuyên theo ngưỡng S0 nếu Supp(X1 → X2 ) ≥ S0 . Độ Phân cụm (Data clustering) hay gom cụm là quá trình
tin cậy (Confidence) của luật X1 → X2 , là tỷ số: p = phân chia các đối tượng trong CSDL T vào các cụm sao cho
Conf(X1 → X2 ) = Supp(X1 → X2 )/Supp(X1 ), ký hiệu các đối tượng có độ tương tự giống nhau được gom vào một
Conf(X1 → X2 ). Với C0 ∈ (0, 1] ta nói f:X1 → X2 là luật cụm. Như vậy, mỗi đối tượng trong T thuộc về một và chỉ
tin cậy (Confident rule) theo ngưỡng S0 và C0 nếu f là luật một cụm. Việc xử lý thay vì làm trên toàn cơ sở dữ liệu có
thường xuyên theo ngưỡng S0 và Conf(X1 → X2 ) ≥ C0 . thể thu lại trên từng cụm. Các kết quả tiêu biểu của kỹ thuật
Bài toán tìm luật kết hợp trên một CSDL được chia
phân cụm và nén dữ liệu được trình bày trong [6][7][8] và
thành hai bài toán nhỏ. Bài toán thứ nhất là tìm tất cả các
[11][12][13][14].
tập mục dữ liệu thường xuyên theo ngưỡng tối thiểu cho
trước. Bài toán thứ hai là tìm ra những luật kết hợp từ những Thời gian tìm tập ứng viên trong thuật toán Apriori
tập mục dữ liệu thường xuyên thỏa độ tin cậy tối thiểu cho là không đáng kể khi ta có một giải thuật tốt. Trong báo
trước. Bài toán thứ hai là đơn giản, hầu hết các nghiên cứu cáo này, chúng tôi đề xuất thuật toán CABOWD (clustering
về luật kết hợp tập trung ở bài toán thứ nhất. Phát triển thuật algorithm based on weighted data), nhằm cải tiến cách tính
toán khai phá luật kết hợp là làm giảm độ phức tạp tính toán độ hỗ trợ của tập ứng viên, rút ngắn thời gian tìm các tập
của thuật toán để cải thiện tốc độ xử lý thường xuyên theo hướng phân cụm và rút gọn kích thước
dữ liệu.
2. Các thuật toán cơ bản
3.1. CSDL giao tác có trọng số được sắp rút gọn
Các thuật toán cơ bản đã được tóm tắt trong [1]. Năm
1993, Agrawal, Imielinski, Swami [2] đưa ra một thuật toán Cho I={x1 ,x2 ,. . . ,xn } là tập các mục dữ liệu.
69
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(74).2014.QUYỂN II
3.1.1. Định nghĩa 1: CSDL giao tác có trọng số Trong phần sau, cho T là CSDL giao tác có trọng số
Một bộ có thứ tự ti =((xi1 ,wi1 ),(xi2 ,wi2 ),. . .,(xik , wik )) được sắp rút gọn trên I. Cho X = {xi1 , xi2 , . . . , xik1 } ⊆ I
với {xi1 , xi2 , . . ., xik } ⊆ I và wij ∈N, j=1..k gọi là một giao thì quy ước rẳng các phần tử của X đã được sắp thứ tự thỏa
tác có trọng số trên I, wij là trọng số của mục dữ liệu xij Supp(xi1 ) ≥ . . . ≥ Supp(xi1 ).
trong ti . Đặt Set(ti )={xi1 , xi2 , . . . , xik } là tập mục dữ liệu 3.1.7. Định nghĩa 7: Quan hệ tương dương ≈
của ti . Một tập m giao tác có trọng số T={t1 ,t2 , . . . ,tm } gọi Trên T ta định nghĩa quan hệ ≈ như sau: ∀ti , tj ∈
là một CSDL giao tác có trọng số trên I. T : ti = ((xi1 , wi1 ), (xi2 , wi2 ), ..., (xis , wis )), tj =
3.1.2. Định nghĩa 2: SuppW(X) ((xj1 , wj1 ), (xj2 , wj2 ), ..., (xjr , wjr )) : ti ≈ tj ⇔ xi1 = xj1
Cho T là CSDL giao tác só trọng số trên I. Với X= {xi1 , Chứng minh dễ dàng rằng, ≈ là quan hệ tương đương
xi2 , . . . , xik } ⊆ I, ta định nghĩa SuppW(X) là độ hỗ trợ theo trên T.
trọng số của X: 3.1.8. Tính chất
X Ta có: Với X = {xi1 , xi2 , . . . , xik1 } ⊆ I : X ⊆
SuppW(X) = Min{wi1 , ..., wik }
{xi1 , xj2 , . . . , xjk2 } ⇔ {xi2 , . . . , xik1 } ⊆ {xj2 , . . . , xjk2 }
X⊆Set(ti )
ti =((xi1 ,wi1 ),...,(xik ,wik ))∈T Từ tính chất này, để xem {xi1 , xi2 , . . . , xik1 } có phải là
tập con của {xi1 , xj2 , . . . , xjk2 } hay không, ta chỉ cần xem
Function SuppW(X); {xi2 , . . . , xik1 } có là tập con của {xj2 , . . . , xjk2 } hay không.
Input: T: CSDL giao tác có trọng số trên I, X ⊆ I. 3.1.9. Phân rã giao tác
Output: SuppW(X).
Method: Với ti = ((xi1 , wi1 ), (xi2 , wi2 ), . . . , (xik , wik )) ∈ T, ta
SW:=0; có thể phân thành k giao tác con : C(ti ) = {ti1 , ti2 , ..., tik },
For each tj = ((xj1 ,wj1 ), . . . , (xjs ,wjs )) ∈ T do với: ti1 = ((xi1 , wi1 ), (xi2 , wi2 ), ..., (xik , wik )), ti2 =
If X ⊆ Set(tj ) then ((x i2 , w i2 ), ..., (xik , wik )), ti3 = ((xi3 , wi3 ), (xi4 , wi4 ), ...,
SW:=SW+Min{wj1 , wj2 , . . . , wjk } (x ik , w ik )), ..., tik = ((xik , wik )).
EndIf; Nhận xét rằng: X ⊆ Set(ti ) ⇔ Tồn tại duy nhất một
EndFor; tij để X ⊆ Set(tij ). Từ đây, để kiểm chứng X ⊆ Set(ti ) ta
Return SW; kiểm tra xem có một trên tij để X ⊆ Set(tij ) hay không.
Gọi TG là tập hợp tất cả các giao tác được phân rã từ
các giao tác của T:
3.1.3. Định nghĩa 3: CSDL giao tác có trọng số được sắp
TG = Ut∈T C(t)
Cho T là một CSDL giao tác có trọng số trên I. Một
bộ có thứ tự ti = ((xi1 , wi1 ), (xi2 , wi2 ), . . . , (xik ,wik )) có 3.1.10. Sự tương đương của 2 CSDL T và TG
SuppW (xi1 ) ≥ SuppW(xi2 ) ≥ . . . ≥ SuppW(xik ) được gọi Hai CSDL giao tác T1 và T2 trên cùng tập mục dữ
là một giao tác có trọng số được sắp trên I. liệu I gọi là tương đương nếu và chỉ nếu: ∀X ⊆ I ta có
Một CSDL giao tác có trọng số trên I mà mọi giao tác SuppT1 (X) = SuppT2 (X) với SuppT (X) là độ hỗ trợ của
đều được sắp được gọi là một CSDL giao tác có trọng số X trên T.
được sắp trên I. Từ định nghĩa việc phân rã giao tác và nhận xét ở mục
3.1.4. Định nghĩa 4: Quan hệ ≺ trên, có T và TG là hai CSDL giao tác tương đương. Từ đây,
để tính độ hỗ trợ củaX ⊆ I, thay vì tìm trên T ta đi tìm
Cho T là CSDL giao tác có trọng số được sắp trên I. trên T .
G
Trên T ta định nghĩa một quan hệ ≺ như sau: ∀ ti , tj ∈ T: ti
= ((xi1 ,wi1 ), (xi2 , wi2 ), . . . , (xis , wis )), tj = ((xj1 , wj1 ), (xj2 , 3.2. Phân cụm dữ liệu
wj2 ), . . . , (xjr , wjr )): ti ≺ tj ⇔ s ≤ r và xi1 = xj1 , xi2 = xj2 , Phân hoạch TG thành n lớp (cụm) tương đương theo
. . . , xis = xjs . quan hệ ≈ đã định nghĩa trên.
3.1.5. Định nghĩa 5: Phép toán ⊕T Gọi CWi0 là lớp tương đương của tij = ((xi , wi ),
(xi2 , wi2 ), . . . , (xik , wik )) ∈ TG , là tập hợp các giao tác
Trên T, là CSDL giao tác có trọng số được sắp trên I, trên T có mục dữ liệu đầu tiên là x :
G i
định nghĩa phép toán ⊕T như sau:
CWi0 = {(xi , wi1 ), (xi2 , wi2 ), . . . , (xik , wik ))|tij =
∀ti , tj ∈ T : ti = ((xi1 , wi1 ), (xi2 , wi2 ), . . . , (xis , wis )),
((xi , wi ), (xi2 , wi2 ), . . . , (xik , wik )) ∈ TG }, i = 1..n.
tj = ((xj1 , wj1 ), (xj2 , wj2 ), ..., (xjr , wjr )) : Nếu ti ≺
Từ phân hoạch, ta có: Với X = {xi , xi2 , . . . , xik } ⊆ I,
tj thì t = ti ⊕T tj = ((xi1 , wi1 + wj1 ), (xi2 , wi2 +
nếu có t ∈ T để X ⊆ Set(t) thì tồn tại duy nhất t0 ∈ CW0 i
wj2 ), . . . , (xis , wis + wjs ), (xis+1 , wjs+1 ), . . . , (xjr , wjr )).
để X ⊆ Set(t0 ). Từ đây, để tính SuppW(X), ta chỉ cần duyệt
3.1.6. Định nghĩa 6: CSDL giao tác có trọng số được sắp trên cụm CW0 .
i
rút gọn Từ tính chất 3.1.8, ta cắt bỏ mục dữ liệu đầu tiên của
Cho T là CSDL giao tác có trọng số được sắp trên I. Ta các giao tác trong CW0 i thành tập CWi để giảm kích
nói T là CSDL giao tác có trọng số được sắp rút gọn trên I thước mà không ảnh hưởng đến việc tìm độ hỗ trợ của tập
nếu: Không tồn tại bất kỳ hai giao tác ti , tj nào của T thỏa: X = {xi , xi2 , . . . , xik }.
ti ≺ tj . Đặt TCW = {CW1 , CW2 , . . . , CWn }.
70
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ,EndProcedure;
ĐẠI HỌC ĐÀ NẴNG - SỐ ……………….
Nguyễn Hữu Trọng, Lê Đức An, Trần Xuân Việt, Nguyễn Anh Hào
EndProcedure;
3.3.4. Thuật toán phân cụm dữ liệu:
3.3. Thuật toán phân cụm dữ liệu
3.3.1. Cây W_Tree Procedure
3.3.4.
3.3.4. Thuật
Thuật toán
phânphân
Cluster;
toán cụm cụm dữ liệu dữ liệu:
Cây W_Tree là một cây có nhiều nhánh có 2 cấp. Các
Input:
Procedure TG,
Procedure Cluster; CSDL
Cluster; giao tác có trọng số được sắp
nút cấp 1, mỗi nút chứa tên của các mục dữ liệu được sắp Input:
Input: rút
TG,TG, gọn.
CSDL CSDL giao giao tác tác có trọng
có trọng số được sốsắp được sắp
rút gọn.
xếp theo thứ tự giảm Hình
dần của trợ. Mỗi nút xi có một
độ hỗW-Tree
1. Cây Output:
Output: rút
TCW: gọn.
TCW: TậpTập cáccác cụmcác dữ cụm
liệu dữ liệu
con trỏ trỏ đến xâu nútHình
cấp 2, chứa giao
1. Cây W-Treetác của CSDL giao Method:
Output: TCW: Tập các các cụm dữ liệu
Method:
trọngThuật
tác có3.3.2. toán
số được sắp,xây
bắt dựng câyxW_Tree:
đầu bằng i. For
Fori:=1
Method: i:=1totonndodoCWi:=φ; CWi:= EndFor; ; EndFor;
3.3.2. ThuậtCreat_Tree(T,Root);
Procedure toán xây dựng cây W_Tree: For each t = ((x , wi1 ), (xEndFor;
, wi2 ),ik,w
. . .ik,))TG ik )) ∈
(xik , wdo
For each
i:=1 toiti=((xn doi1,w i1),(x
CWi:=
i1 i2;
,w i2),…,(x
i2
Procedure
Input: CSDLCreat_Tree(T,Root);
giao tác T = {t1, t2, …, tm} trên tập TG do
ForForeach
j:=1tto =((x k-1i1,wdoi1),(xi2,wi2),…,(xik,wik))TG do
mục
Input:dữCSDL liệu Igiao = {x1tác, x2, T…,=xn{t} 1, t2, …, tm} trên tập For j:=1i to k-1 do
ij+1),…,(xik,wik)); CWij:= CWijtij;
ttijij=((x
For j:=1 toij+1
= ,wdo
k-1
((x ij+1 , wij+1 ), . . . , (xik , wik )); CWij :=
Output:
mục dữ Root: liệu I =W_tree;{x1, x2, …, xn} EndFor; tij=((x ),…,(xik,wik)); CWij:= CWijtij;
CW ∪ t,w
ij ij+1 ij ;ij+1
Method:
Output: Root: W_tree; EndFor;
EndFor;
EndFor;
For each xi I do Si=Supp(xi); EndFor;
Method: TCW:={CW1,
EndFor;
EndFor; CW2, …, CWn};
I':=(x
For eachi1, xi2, x i inI)do
…,x thỏa Si1… Siin);; EndFor;
Si=Supp(x EndProcedure;
TCW:=CW1,
TCW:={CW1, CW2,. .…, CW2, . , CWn;
CWn};
I':=(xi1, xi2, …,xin) thỏa Si1… Sin;
New(Root);P:=Root; EndProcedure;
EndProcedure;
For j:=1 to n do 3.4. Ví dụ minh họa
New(Root);P:=Root;
ForNew(P1);
j:=1 to n do Hình 1: Cây;W-Tree
P1^.Inf:=x ij P^.Right:=P1;
3.4.
3.4. Ví Ví dụ
dụChominh minh
CSDLhọahọa giao tác T:
3.3.2. Thuật toán xâyP1^.Inf:=x
P1^.Left:=Nil;
New(P1); dựng câyijW_Tree:
P:=P1; ; P^.Right:=P1; GCho
tác CSDLCho
MụcCSDL DL tácgiao
giao T:t4 tác T:
A,B,D t8 A,B,C,E
Procedure
EndFor; Creat_Tree(T,Root);
P1^.Left:=Nil; P:=P1; t1
G tác A,B,E
Mục DL tt54 A,C A,B,D tt98 A,B,C
A,B,C,E
ik},1 2T do m
Input:For
CSDL each
EndFor; giaot ={xtáci1,T…,=x{t , t , . . . , t } trên tập mục dữ tt21 B
A,B,E tt65 B,C A,C tt109 A,B,E,G
A,B,C
liệu I = {x1 ,t':=((x xn }
x2 , . . . ,,1),…,(x t B,C t A,C
For each t ={x j1 i1, …, xikjk}, T do
,1)) with (Set(t')=t) and t32 B t76 B,C t 10 A,B,E,G
Output: Root: W_tree;
Method: t':=((xj1,1),…,(x
(Sj1…jk,1)) Sjk); with (Set(t')=t) and t
3.4.1. 3 B,C
Xây dựng cây W_Tree: t 7 A,C
For each x2 i ∈ I1j do(SSj1i…
P := P ^.Left; Sjk); i ); EndFor;
= Supp(x 3.4.1.
3.4.1. XâyXây
Độdựng dựng
hỗ cây câychoW_Tree:
trợW_Tree mỗi mục dữ liệu : (B:8;
I’:=(xi1 ,IfPx2i2
:=, .P.1j.^.Left;
exists ,(P
xin2k^.Inft')
) thỏa Si1or ≥ (t'
... ≥ P2kS^.Inf)
; then
in Độ hỗ
A:7; Độ
C:6; trợE:3;hỗ
chotrợ mỗicho
D:1; mục
G:1) mỗi mục (B:8;
dữ liệu: dữ liệu A:7; :C:6;
(B:8;E:3;
New(Root);P:=Root;
If exists (P ^.Inft') or (t' P ^.Inf) then D:1; G:1)
P2k^.Inf:= P2k^.InfTt'
2k 2k
A:7; C:6; E:3; D:1; G:1)
For j:=1 to n do Sắp xếp Sắp cácxếp mụccác dữ liệu mụctrong dữ giao liệu táctrong theo giao
thứ tựtác
giảm
Else P New(P2);
^.Inf:=
∧ P P2^.Inf:=t';
^.Inf ∧ Tt' Jont(P1j,P2);
2k 2k
New(P1); P1 .Inf:=xij ; P .Right:=P1; theo thứSắp tự
dần của độ hỗ trợ T’. giảm
xếp cácdần mụccủa độ
dữ hỗ trợ
liệu T’.
trong giao tác
EndIf;
Else New(P2);
P1∧ .Left:=Nil; P:=P1; P2^.Inf:=t'; Jont(P1j,P2);
theo
G tácthứMục tự giảmDL dầnt4củaB,A,D độ hỗ trợ T’. t8 B,A,C,E
EndFor;
EndFor; EndIf;
EndProcedure; G t
tác
1 B,A,E
Mục DL tt54 A,C
B,A,D tt98 B,A,C
B,A,C,E
ForEndFor;
each t ={xi1 , . . . , xik }, ∈ T do
tt21 B
B,A,E tt65 B,C A,C tt109 B,A,E,G
B,A,C
t’:=((xj1 , 1), . . . , (xjk , 1)) with (Set(t’)=t) and
EndProcedure;
3.3.3. Thuật toán chuyển CSDL giao tác thành
(Sj1 ≥ . . . ≥ Sjk );
t3 t2B,C B t6 B,C t7 A,C t10 B,A,E,G
CSDL
3.3.3. giao
P2 :=Thuật tác
toán
P1j ∧ .Left;có trọng
chuyển số CSDL
được sắp rúttác
giao gọnthành t3 TạoB,Ccây trọng tsố
7 W_Tree.
A,C
Tạo cây trọng số W_Tree.
CSDL giao(PTrans;
If exists
Procedure tác
∧ có trọng số được sắp rút gọn
∧
2k .Inf≺t’) or (t’≺ P2k .Inf) then Tạo cây trọng số W_Tree.
P∧
Procedure 2k .Inf:=
Trans;P∧2k .Inf⊕T t’
Input:
Else New(P2); Ptác
CSDL giao ∧T = {t1, t2, …, tm} trên tập
2k .Inf:=t’; Jont(P1j , P2);
Input: mục
CSDLdữ
EndIf; giao liệu
tácI =T {x
= 1{t, 1,x2t,2…,
, …,xnt}m} trên tập
Output:
EndFor; mục TG:dữ CSDL liệugiao
I = {xtác
1, xcó 2, …, trọng
xn} số được sắp
EndProcedure;
Output: rútTGgọn.
: CSDL giao tác có trọng số được sắp
3.3.3.Method:
Thuậtrút gọn.
toán chuyển CSDL giao tác thành CSDL giao
tác có trọng số được sắp
Creat_Tree(T,Root);
Method: rút gọn TG:=;
P1:=Root;
Chuyển cây thành cơ sở dữ liệu giao tác có trọng
While
Procedure P1Nil
Trans; do
Creat_Tree(T,Root); P1:=Root; TG:=;
được
Chuyển sắpcâyrút thành
gọn: cơ sở dữ liệu giao tác có trọng
Input:While
CSDL giao tác T
P2:=P1^.Left;
P1Nil do= {t1 , t2 , . . . , tm } trên tập mục dữ
liệu I = {xWhile . . , xn } do
1 , x2 , . P2Nil
đượctsắp rútTập
gọn:MDL có trọng số
P2:=P1^.Left; id
Output: TG : CSDL giao tác có trọng số được sắp rút gọn.
:=TGP2^.Inf;
WhileTGP2Nil do P2:=P2^.Next; t’
tid1 Tập MDL
((B,3), có trọng
(A,2), (E,2),số(G,1)).
Method: Chuyển
t’ cây ((B,2),
thành cơ(C,2))
sở dữ liệu giao tác có trọng số được
TG:=TGP2^.Inf;
EndWhile;
Creat_Tree(T,Root); P1:=Root;P2:=P2^.Next;
TG := φ;
2
sắp rút gọn:
1 ((B,3), (A,2), (E,2), (G,1)).
P1:=P1^.Right; t’ 32 ((B,1),
((B,2), (A,1),
(C,2)) (D,1))
While EndWhile;
P1Nil do
EndWhile;
P1:=P1^.Right;
∧ t’ 43 tid((B,2),
((B,1), (A,2),(C,2),(E,1))
Tập MDL(D,1))
(A,1), có trọng số
P2:=P1 .Left;
EndWhile;
While P2Nil do t’ 54 ((A,2),
((B,2), (C,2))
(A,2),(C,2),(E,1))
t’1 ((B,3), (A,2), (E,2), (G,1)).
4 TG := TG ∪ P2∧ .Inf; P2:=P2∧ .Next; t’5 t’2((A,2), (C,2)) ((B,2), (C,2))
EndWhile;
4 t’3 ((B,1), (A,1), (D,1))
P1:=P1∧ .Right;
EndWhile; t’4 ((B,2), (A,2),(C,2),(E,1))
EndProcedure; t’5 ((A,2), (C,2))
71
- TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(74).2014.QUYỂN II
Phân rã giao tác For each t in CWj
t’11 ((B,3),(A,2),(E,2),(G,1)) t’33 ((D,1)) If X ⊆ Set(t) ∈ then
SuppW(X):=SuppW(X)+1;
t’12 ((A,2),(E,2),(G,1)) t’41 ((B,2),(A,2),(C,2),(E,1))
EndIf;
t’13 ((E,2),(G,1)) t’42 ((A,2),(C,2),(E,1))
EndFor;
t’14 ((G,1)) t’43 ((C,2),(E,1))
If SuppW(X) ≥ S0 then
t’21 ((B,2),(C,2)) t’44 ((E,1))
X:={xj , X}; Lk := Lk ∪ X;
t’22 ((C,2)) t’51 ((A,2),(C,2))
EndIf;
t’31 ((B,1),(A,1),(D,1)) t’52 ((C,2)) EndFor;
t’32 ((A,1),(D,1)) EndFor;
Gom cụm dữ liệu L:=L ∪ Lk ;
Cụm B: Cụm A Until Lk = φ;
t’11 ((A,2),(E,2),(G,1)) t’12 ((E,2),(G,1)) EndProcedure;
t’21 ((C,2)) t’32 ((D,1)) 5. Thử nghiệm
t’31 ((A,1),(D,1)) t’42 ((C,2),(E,1))
t’41 ((A,2),(C,2),(E,1)) t’51 ((C,2)) Chúng tôi đã chạy thuật toán CABOWD và thuật toán
Cụm C: Cụm E FP_Growth trên máy tính DELL CPU Intel Core i-3 2328M
t’43 ((E,1)) t’13 ((G,1)) 2.30GHz trên hệ điều hành Windows 7, ngôn ngữ Delphi,
chạy với các ngưỡng tối thiểu và thời gian tương ứng
Cụm D = Cụm G = φ; trong các bảng so sánh sau với bộ dữ liệu mẫu trên
3.5. Tính đúng đắn của thuật toán http://fimi.ua.ac.be/data:
Thuật toán phân cụm dữ liệu có ba bước: 5.1. Tập dữ liệu T1I5D1000K
• Bước 1: Xây dựng cây W_Tree duyệt qua CSDL 2 lần
nên độ phức tạp là O(m). S0 (1) (2) S0 (1) (2)
• Bước 2: Chuyển dữ liệu từ cây W_Tree sang CSDL 100 6975 30643 600 588 4327
giao tác có trọng số rút gọn TG với ||TG || ≤ ||T|| nên 200 3197 14074 700 540 4133
có độ phức tạp O(m). 300 1662 7815 800 516 4113
• Bước 3: Phân cụm TG thành TCW chỉ duyệt qua TG 400 999 5419 900 489 3927
một lần và phân t ∈ TG thành tối đa n giao tác con 500 708 4599 1000 464 3898
nên độ phức tạp là O(m*n). (1): CABOWD (giây) (2) FP_Growth (giây)
Do đó độ phức tạp chỉ là O(m ∗ n).
Cơ sở của thuật toán được xây dựng trên phép toán ⊕T
và quan hệ tương đương ≈ nên bảo đảm tính đúng.
4. Thuật toán CABOWD
Chúng tôi đề xuất thuật toán CABOWD (clustering
algorithm based on weighted data), tìm tập thường xuyên
trên cơ sở dữ liệu giao tác có trọng số được sắp rút gọn đã
phân cụm.
Procedure CABOWD;
Input : CW=CW1, CW2, . . . , CWn;S0:Integer;
Output: L=X ∈ I| SuppW(X) = S0;
Method:
L1 := {x ∈I| SuppW(x)≥ S0}= {xi1 , xi2 , . . . xin1 };
//Có n1 mục dữ liệu thường xuyên
L:=L1 ;
Repeat k:=2; Hình 2: So sánh thời gian chạy hai thuật toán CABOWD
Ck là tập tất cả các tập ứng viên có k phần tử được và FP_Growth trên dữ liệu T1I5D1000K
tính từ Lk−1 ; 5.2. Tập dữ liệu T0.5I4D4000K
Sắp xếp các mục dữ liệu trong các phần tử của Ck
theo thứ tự giảm dần của độ hỗ trợ; S0 (1) (2) S0 (1) (2)
For j:= 1 to n1 doUj := φ; EndFor; 1000 1104 8740 6000 195 4005
For each X={xi1 , xi2 , . . . ,xik } ∈ Ck do 2000 646 5901 7000 174 3983
Ui1 := Ui1 ∪ {xi2 , . . . , xik }; 3000 427 4628 8000 161 3939
EndFor; 4000 305 4193 9000 153 3867
Lk := φ; 5000 233 4091 10000 151 3789
For j:= 1 to n1 do (1): CABOWD (giây) (2) FP_Growth (giây)
For each X in Uj do SuppW(X):=0;
72
- Nguyễn Hữu Trọng, Lê Đức An, Trần Xuân Việt, Nguyễn Anh Hào
[4] Han j, Pei H, and Yin Y, “Mining Frequent Patterns without
Candidate Generation”, In: Proc. Conf. on the Management of Data
(SIGMOD’00, Dallas, TX), ACM Press, New York, NY, USA 2000,
pages 1-12.
[5] J Han, M Kamber, J Pei Data Mining Concepts and Techniques,
Third Edition, Morgan Kaufmann, 2012
[6] Nguyễn Hữu Trọng, "Thuật toán khai thác tập thường xuyên hiệu
quả dựa trên kỹ thuật phân lớp dữ liệu", Tạp chí Tin học và Điều
khiển học, Viện Khoa học và Công Nghệ Việt Nam, Số 3, tập 23,
trang 260-271, 2007
[7] Nguyễn Hữu Trọng, Nguyễn Thị Minh Châu, Phạm Ngọc Công,
"Phát triển thuật toán khai phá tập thường xuyên dựa vào sự phân
lớp dữ liệu – Thuật toán PHL (Phân hoạch lớp)", Kỷ yếu Hội thảo
quốc gia Một số vấn đề chọn lọc của công nghệ thông tin và truyền
thông lần thứ XIV tại Cần Thơ, 07-08/10/2011. Nhà xuất bản Khoa
học và kỹ thuật Hà Nội 2012, trang 510-521.
[8] Nguyễn Hữu Trọng, Nguyễn Thị Minh Châu, Phạm Ngọc Công,
Hình 3: So sánh thời gian chạy hai thuật toán CABOWD và " Một cách tối ưu cơ sở dữ liệu giao tác cho các thuật toán tìm
FP_Growth trên dữ liệu T0.5I4D4000K. luật kết hợp", Kỷ yếu Hội thảo quốc gia Một số vấn đề chọn lọc
của công nghệ thông tin và truyền thông lần thứ XV tại Hà Nội,
6. Kết luận 03-04/12/2012. Nhà xuất bản Khoa học và kỹ thuật Hà Nội 2013.
Thuật toán CABOWD được xây dựng trên cơ sở toán Trang 227-232
[9] Damor Nirali N, Radhika Krishnan, Patel Hardik, "A New Method
học với quan hệ tương đương ≈ và phép hợp nhất ⊕T nên
to Mine Frequent Itemsets using Frequent Itemset Tree", Research
bảo đảm tính đúng đắn của thuật toán. Với một CSDL giao Journal of Computer and Information Technology Sciences, Vol.
tác, việc phân hoạch để nén dữ liệu chỉ làm một lần, với 1(3), Pp 9-12, April 2013
kết quả nén, ta có thể áp dụng nhiều thuật toán khác nhau [10] D. Kerana Hanirex, A. Kumaravel, "An Efficient Partition and
Two Dimensional Approach For Mining Frequent Itemsets",
trên tập dữ liệu này. Với độ rút gọn dữ liệu rất lớn sau khi International Journal of Technological Synthesis and Analysis,
phân hoạch tiết kiệm lớn không gian lưu trữ, tăng tốc độ Volume 1 Issue 1,
xử lý. Việc tìm các tập được xây dựng dựa trên thuật toán [11] A Tiwari, Rajendra K. Gupta, Dev Prakash Agrawal, "Cluster Based
Apriori nên bảo đảm tính dừng. Qua thử nghiệm, thuật toán Partition Approach for Mining Frequent Itemsets", International
Journal of Computer Science and Network Security, VOL.9 No.6,
CABOWD chạy nhanh hơn rất nhiều lần so với thuật toán Pp 191-199 June 2009
FP_Growth, điều này nói lên tính hiệu quả của thuật toán. [12] D.Kerana Hanirex, Dorai Rangaswamy, "Eficient Algorithm
For Mining Frequent Itemsets Using Clustering Techniques",
Tài liệu tham khảo International Journal on Computer Science and Engineering, Vol.
[1] Endu Duneja, A.K. Sachan, "A Survey on Frequent Itemset 3 No. 3 Pp 1028-1032, Mar 2011.
Mining with Association Rules", International Journal of Computer [13] Jianwei Li, Ying Liu, Wei-keng Liao, Alok Choudhary, "Parallel
Applications (0975 – 8887), Volume 46– No.23, Pp 18-24, Data Mining Algorithms for Association Rules and Clustering",
May 2012 CRC Press, Pp 1-25, 2006
[2] Agrawal. R., Imielinski. T., Swami. A., “Mining Associations [14] V.Vidhya Rani, I. Elizabeth Shanthi, "A Study on Efficient Data
between Sets of Items in Massive Databases”, In Proc.of the 1993 Mining Approach on Compressed Transaction", Global Journal of
ACM-SIGMOD Int’l Conf. on Management of Data, pages 207-216. Computer Science and Technology, Volume 11 Issue 14 Version 1.0,
[3] Agrawal. R., Mannulla. H., Srikant. R., Toivonen. H., Verkamo. A. Pp 41-46, August 2011
I.,”Fast Discovery of Association Rules”, In Advances in Knowledge
Discovery and Data Mining, AAAI Press, 1996, pages 307-328.
(BBT nhận bài: 21/12/2013, phản biện xong: 19/01/2014)
73
nguon tai.lieu . vn
