HVKTQS




 !"#$"%
Hc viên thc hin:

&'()*+



1

2



3



4
 !"#$%&'(
5
)
',' '/)

Trong thời đại bùng nổ công ngh thông tin, các công ngh lưu
trữ dữ liu ngày càng phát triển nhanh chóng tạo điều kin cho
các đơn vị thu thập dữ liu nhiều hơn và tốt hơn.

0123-4)56768-69:1

Kết quả đạt được

*+,-.%/#'%012
3#4567

*+,,&01283


2,94:;%!2<)=1
2>#?##03./'%/

Hướng phát triển

@8&-,&012
83,%$#;A1#,B8
C2="
,
.;*<,=(><'/)

Cho một CSDL D = {t1,t2,…,tn}, một tập hợp các lớp C= {C1,…,Cm}, bài
toán phân lớp được phát biểu như sau: Xác định ánh xạ
f : D

C sao cho với mỗi ti được quy về một lớp Cj.

Về mặt thc chất, bài toán phân lớp chính là chia D thành các lớp tương
đương.
-

Vic phân lớp được thc hin da trên khoảng cách Euclidean nhỏ nhất
giữa đối tượng đến phần tử trung tâm của các lớp/nhóm.

Phần tử trung tâm của nhóm được xác định bằng giá trị trung bình các
phần tử trong nhóm
0
E*.2.@5*+101.F)1<'(BC*
A = {a1, a2 an} - Tập n đối tượng
aj=(xj1, xj2, xjm) j=1 n - phần tử thứ j cần phân loại
xjs s=1 m - thuộc tính của đối tượng
ci=(ci1, ci2, cim) i=1 k - phần tử trung tâm nhóm i
cis s=1 m - thuộc tính của phần tử trung tâm i
1("2&3
"3'45"36
78#"'
9'

∑
=
−=∂
m
s
isjsij
cx
E
A
FG
:;

E*.<8'-@86&-;G1HCIJ*+

IAJ*$,P#2!;%δQ
IRJ@'%S$;(#>GAF
,33(#T,P#2=&U$2=!%#
$3
)
LM6N2.O'1HC )?--@0*ABC*D
Data input:
- n objects
- k clusters
Start
Initial k cluster centers
calculate
δ objects-centers
grouping based on
the δmin
No object
move group
recomput c
i
T
F
End
*
&=.P1-8=1HC )?--@0*

Số ô nhớ cần dùng để lưu trữ các đối tượng là O(mn) trong đó m là số
đối tượng còn n là số chiều (hay số thuộc tính) của các đối tượng

Còn độ phức tạp về thời gian của giải thuật K-MEANS là O(I*K*m*n)
trong đó I là số bước lặp cần thiết để giải thuật dừng (hội tụ), K là số

gi là một item. Gi D là một CSDL, trong đó mỗi bản ghi T là
một giao dịch và chứa các tập item, T
⊆
I.

Định nghĩa 1: Một luật kết hợp là một quan h có dạng X
⇒
Y,
trong đó X, Y
⊂
I là các tập item gi là itemsets và X
∩
Y=
φ
. Ở
đây X được gi là tiền đề, Y là mnh đề kết quả.

Hai thông số quan trng của luật kết hợp là độ hỗ trợ (s) và độ
tin cậy (c).

Định nghĩa 2: Độ hỗ trợ (support) của luật kết hợp X
⇒
Y là tỷ
l % các giao dịch có chứa X, Y với tổng số các giao dịch có
trong cơ sở dữ liu.

Định nghĩa 3: Độ tin cậy (confidence) của luật là tỷ l % của số
giao dịch có chứa X, Y với số giao dịch có chứa X.
-
)?-23-.:=

Một số khái nim liên quan

@3;2$3;

@;aC2;$,bS1 
%=C#!

@;3G>#cF2;-
,V;Vd$2;aC3(#

Các thuật toán tìm luật kết hợp

@<ef

@fM@Y

@<

@M%
/
.)?--@0*$=R'@R'

Ý tưởng: Tạo ra các tập phổ biến có 1 item, tập 2 items tạo từ
tập 1_item,……tập k items tạo từ tập k-1 items. Xây dng
luật từ tập phổ biến k items tìm được.

Mỗi tập item được tạo ra phải được tính toán độ hỗ trợ và độ
tin cậy.

Tính chất: mi tập item phổ biến thì tất cả các tập item con

tại vòng (k-1) sử dụng hàm Apriori_gen(). Sau khi
xác định được các tập ứng cử viên, thuật toán quét
từng giao dịch trong CSDL để xác định độ hỗ trợ
của các tập ứng cử viên. Quá trình xác định các tập
item phổ biến sẽ kết thúc khi không xác định được
thêm tập item phổ biến nào nữa.

.)?--@0*$=R'@R'
1.2. Nội dung hàm Apriori_gen()
+ F
k-1
được kết nối với chính nó thu được C
k
+ Apriori_gen() xoá tất cả các tập item từ kết quả kết nối mà
có 1 số tập con (k-1) không có trong F
k-1
. Sau đó nó trả về tập
item phổ biến kích thước k còn lại.
g?J
F
R
OZZEXAXRWXZEXAX[WXZEXRX[WX
ZEXRX]WXZAXRX[WW

<h;N
C
[
OZZEXAXRX[WXZEXRX[X]WW

<h;#J

G33&E
H3%
R;
R
RC
A%
fe;!;
I#&G&'E&E
C
%;
%
;
C;
%C
e;!;
G33&E
;
C;
C
%;
%
%C
e;!;
A
E
A
A
R
E
f

Với mỗi tập con h tìm được, ta xuất ra luật dạng (h)
⇒
(f-h) nếu tỉ l
support(f)/support(h)
≥
mincof.