I HC QUC GIA TP H CHÍ MINH
I HC CÔNG NGH THÔNG TIN
KHOA: KHOA HC MÁY TÍNH

TIU LUN

CÔNG NGH TRI THC VÀ NG DNG
THUT TOÁN K-MEAN TRONG PHÂN CM D LIU VÀ NG DNG Ging dn : GS.TSKH. HOÀNG KIM

Hc viên thc hin: - NGÔ NG
- NGUYN KHC MN _ CH1101102

Lp : CH06
TP. Hồ Chí Minh, tháng 5 năm 2012
Lời cảm ơn

c tiên, nhóm chúng em xin cy GS TSKH Hoàng Kiu kin
cho nhóm tip xúc mc quan trng ca trí tu nhân to   tri th.
Cùng vi s phát trit bc ca ngành công nghip máy tính, nhu cu
ci vi máy tính ngày m gii quyt nhng công
vi           i máy tính có kh 
 gii quyt v i. Và t  nhân to nói











1

Mc lc
  4
I.  4
1.1. Khái nim 4
1.2. Bài toán phân cm nói chung 4
1.2.1. Các kiu biu din d liu 5
1.2.2.   và khong cách 6
1.2.3. Tiêu chun phân cm 10
1.3. m phân cm 11
1.3.1. Yêu cu 11
1.3.2. Mt s v trong phân cm d liu 12
1.4. m d liu 13
1.4.1. Phân hoch theo tp thô 13
1.4.1.1. Các h thông tin 13
1.4.1.2. Quan h bt kh phân 15
1.4.1.3. Xp x tp hp 16
1.4.2.  17
1.4.3.  19

1.1.  46
1.2.  47
1.3. Th phc tp ca thut toán K-means. 49
1.4.  49
1.5. -means 50
II. (LSI) 52
2.1.  52
2.2. Phân tích Singular Value Decomposition (SVD) ca ma trn t ch mc (term document A)
53
2.3. Truy vn trong mô hình LSI 56
2.4. Cp Nht Singular Value Decomposition (SVD) 58
2.4.1. Cp Nhn (SVD- Updating document): 58
2.4.2. Cp Nht t ch mc (terms): 60
2.4.3. Loi b t ch mc (Downdating) Trong Mô Hình LSI 61
2.5. Chn h s k trong mô hình LSI 61
III. -MEANS 64
3.1. Tin x lý tp d liu vào 64
3.2. Ch ng cách thích hp 66
3.3. Chn s cm cho thut toán K-means 68
3

  71
I. TRUY HI THÔNG TIN 71
1.1. Biu din mu 72
1.2. Phép  74
1.3. Mt gii thut cho phân cm d liu sách 75
II. KHAI PHÁ D LIU 76
2.1. Khai phá d liu bng php cn. 77
2.2. Khai phá d liu có cu trúc ln. 78
2.3.  liu trong  d liu a cht. 80

tc và thuc tính ri rc. Bên cu phân loi da trên h t s
kiu d liu thông dnh danh, thuc tính có th t, thuc tính
khong, thuc tính t l ng trc tin kt qu phân
cm. Vì th i ta phi chun hóa d li khc phc ym này. T nhng
yêu cu trên và vi liu chúng ta cn tìm hiu v các kiu
biu din d liu. Có hai kiu biu din d liu ph bin là:
 Biu dii dng ma trn ca các bin cu trúc hay các thuc tính ca
ng. Ví d i s có các thuc tính là tên, tui, chiu
cao, cân nng, màu m       ng, m  ng có p
thuc tính thì s có mt ma trn vi n dòng, p ct.

Hình 2. Ma trn thuc tính biu din d liu
6

 Biu din d lii d ng cách git các ci
ng. Nng, chúng s c biu din bng mt ma trn
vi n hàng và n c

Hình 3. Ma trn khong cách biu din d liu
   ng cách gi   ng i và j. Nói chung,
d(i,j) gn bng i và j là gn nhau hay có ni dung gn ging
ng có ni dung càng khác nhau. Hình 7 biu
din ma trn khong cách ca tp d liu có d(i, j) = d(j, i) và d(i, i) = 0.
1.2.2.   và khong cách
   m d liu cn có m 
khorong không gian d li
 dùng chung cho mng hp vì chúng ta bit rng, m d
liu có th cha nhiu kiu d liu thuc tính khác nhau. Mc
ng nhiu thuc tính có ki . Các ki bao gm giá tr
khong (interval-valued), nh i xng (symmetric binary), nh phân bi

trn ng thiên v trng thái
 c Y khoa, khi bt gp mt triu chng b
tiên kt lu thun tic ch
chuyên sâu và cách ly theo dõi.
Khoc tính bi công thc

4. Binh danh
Binh danh là bin có th nhn nhing thái. Ví d n
màu s nh khong cách theo binh danh:
Dùng h n:
9 vi m là s thuc tính có giá tr trùng khp ging x, y và p là tng
s thuc tính.
n nh phân v binh danh bng cách thay mi trng thái bng mt
bin nh phân.
5. Bin th t
Bin th t là bin trên mt tp giá tr nh quan h th t gia các giá
tr 
Ví d bin xp hng hay bin xp hng v th
Các giá tr có th ri rc hoc liên t n th t c xây d
sau:
 Thay th x
i
bi hng ca chúng x
i
∈ 
 Ánh x hng ca tng bin vào [0, 1] bng cách thay th ng x trong
bin i thành:

vào cn thit cho mt thut toán phân cm càng ít, chi phí cho vic phân
cm càng gim và nó càng kh 
11

 Kh i d liu nhiu: Phn l d liu thc t
chng ngoi l hoc thit
toán nhy cm vi nhiu là nguyên nhân dn vic to ra mt b phân
cm kém chng.
 Không nhy cm vi th t ca bu vào: Mt s thut toán phân
cm không th sát nhp thêm d liu mi vào trong b phân cm, thêm tài
liu vào cm có sn hoc to thêm cm mi. Bên ct thut toán
phân cm tt không to ra các b phân cm khác nhau t cùng mt b d
li t sp xp khác nhau. Nhng thut toán này gi là nhy cm
vi th t d liu.
 Thích nghi vi d liu: D ling có s chiu
ít, t hn ba chiu mà mt s thut toán phân ct qu rt tt.
Bên c liu (nhing và cn
thic phân nhóm cho nhiu ng dng thc t. Vi loi d liu này,
vic phân loi da vào kin thi t ra có hiu qu, tuy nhiên vi
khng d liu ly, vic s dng kin thc chuyên gia là tn
kém nên chúng ta cn tìm các thut toán phân c gii quyc vn
 này.
 Phân cm trên mt s ràng buc: Trong mt s ng dng, chúng ta cn
phân c d liu cha các liên kt bt buc gia hai hay nhiu
ng. Vic phân cm c m b  ng này tha mãn các
ràng bu
 D hiu, d t và kh thi: mt thut toán càng d hiu và d t và
mang tính kh thi cao s i dung tin cy và s dng rng rãi.
1.3. m phân cm
1.3.1. Yêu cu

cng nhiu bng các giá tr thung.
13

 Dò tìm phn t ngoi lai. Phn t ngoi lai là mt nhóm nh ng
d ling so vi các d li d liu. Loi b nhng d
li tránh n kt qu phân cm.
 Phân cm hi m và khó: Vì phân ci
gii quyt mt s v bn: Xây d , xây dng
các tiêu chun phân cm, xây dng mô hình cho cu trúc d liu, xây dng
các thut toán phân cm và xác lu kin khi to, xây dng các th
tc biu dit qu phân cm. Hi
pháp phân cm tng quát nào có th gii quyt trn vn cho tt c các dng
cu trúc d liu. Vi nhng d liu hn hp thì vic phân cm càng khó
t thách thc trong ngành khai phá d liu.
1.4. m d liu
1.4.1. Phân hoch theo tp thô
Lý thuyt tc Z. Pawlak phát triu thp niên 1980. Lý thuyt
tp thô rt hiu qu trong khai thác d liu, tìm kim thông tin, h tr quynh,
máy hc, các h  tri thc
1.4.1.1. Các h thông tin
a. Hệ thông tin
Mt t   d li c mô t i dng b   i
dòng miêu t mt s kin, m ng hp, mt thành ph  
ging. Mi ct là mt thuc tính (mt bii, mt
quan sát, m c cho mi tng; nó
 c cung cp bi nhi có chuyên môn hoi
dùng. B  c gi là mt h thng thông tin (information
system). C th    t c         i
ng, hu hn, khác rng và A là tp thuc tính, hu hn, khác rng
sao cho A a V I a a ∈∀ 

lu
u Age = 16  
u Age = 46  60 và LEMS = 26 - 
1.4.1.2. Quan h bt kh phân
Mt h quynh (bng quynh) biu din tt c các tri thc v
mô hình. Bng này có th c ln vì nó có th a d liu
theo hai mng ging nhau hoàn toàn hay bt kh phân
bit có th c mô t nhiu ln; (2) các thuc tính có th a. Ta s
xem xét v 
Xét quan h nh phân X X R × ⊆ có tính cht phn x 
xRx X x , ∈∀ i xng (nu xRy thì yRx ) và bc cu (nu xRy và
c gi là quan h a
16

mt phn t X x∈ , ký hiu [x]R là tp hp cha mng y ∈ X,
sao cho xRy.
Cho h thông tin U = (I, A), vi tp thuc tính B ⊆ 
quan h 
U


ind
U
c gi là quan h bt kh phân theo B (B-indiscernibility
relation). N∈ ind
U
 phân
bit theo tp thuc tính B. La quan h bt kh phân
c ký hiu là [x]B. Suy ra, các l
B

xác nhng thành phy t bng 1.2. T m
tp thô. Mt dù, chúng ta không th ng mt cách
     ch    ng mà chc chn có giá tr
ng giá tr chc chn không có giá tr i cùng là
ng nào thuc vào vùng biên ging hp chc chn. Nu
vùng biên này khác rng thì tp thô.
Cho h thông tin U = (I, A) và B ⊆A, X ⊆I . Nu có th xp x tp
ng X ch vithông tin cha trong B bng cách xây dng các xp
x B-i và B-trên ca tp X, ký hing là BX, BX 

1.4.2. 
 hi t là thut toán phân cp hi t. Ta thit k thut
toán bng cách ci tin k thut gom cc
phát tri khám phá các lut cu theo lp trong CSDL quan h.
Chameleon là thut toán gom cm phân cp. Thut toán dùng kt ni ni ca
gom cm a các item trong cm.
Cho D là CSDL quan h cha T dòng và k thuc tính. Chameleon tìm các cm
tha các ràng buc: kt ni ni quan h  g RC(Ci,Cj)
 18

Kt ni ni gia hai cm Ci và Cj gi là EC(CiCj) là tng trng s ca các
cung nnh trong Cj. ECCi là tng trng s các cung
 th thành 2phn b n các bài toán v s
phân bit trong các hình ca các c phân bit trong kt ni ca các
cm khác nhau.

S


Gi s supp(S h tr ca itemset S, giá tr Chi-squared 2(S), vi S =
{i1,i2im} và trng s ca ij là wj

Trng s ca 1 item có th nh bng mt giá tr i
dùng chn.
1.5. 
Các k thut phân cm có rt nhiu cách tip cn và các ng dng trong thc
tng ti hai mng ca các cm khám phá
c và t thc hin ca thut toán. Hin nay, các k thut phân cm có th
phân loi theo các cách tip cn chính sau :
1.5.1. m phân hoch
K thut này phân hoch mt tp hp d liu có n phn t thành knhóm cho
nh s các cc thit lp. S các cc thitlc
c la cht cho vic tìmcác cm hình cu
20

trong không gian Euclide       thuc vào
khon gi la chmd liu nào có quan h là
gn nhau vi mm d liunào không có quan h hoc có
quan h là xa nhau so vi m
x lí các cm có hình dng k quc hoccác cm có m m dc. Các
thut toán phân hoch d liphc tp rt lnh nghim t
toàn cc cho v PCDL, do nóphi tìm kim tt c các cách phân hoch có th
c. Chính vì vy, trên thct i pháp tc b cho v
này bng cách s dngmt hàm tiêu chu ng ca c
 ng dncho quá trình tìm kim phân hoch d ling
chính ca thuttoán phân cm phân hoch tc b là s dng chi
 tìm kim nghim.
1.5.2. m phân cp

thành các ô to thành cu trúc d liu lm ch cn
làm vic vi tng trong tng ô trên li ch không phi tng d
liu. Cách tip cn da trên li này không di chuyi tng trong các ô
mà xây dng nhiu mc phân cp ci tng trong mt ô. Ph
pháp này gn ging vi phm phân cp nhng chúng không trn
  ng thi gii quyt khc phc yêu c i vi d liu nhiu chiu mà
phm da trên m không gii quyc. m ca
phm da trên li là thi gian x c lp vi s i
22

tng d liu trong tp d li thuc vào s ô
trong mi chiu ca không gian li.


1.5.5. m da trên mô hình
Ph gng khám phá các phép xp x tt ca các tham s mô hình
sao cho khp vi d liu mt cách tt nht. Chúng có th s dng chin lc phân
cm phân hoch hoc phân cm phân cp, da trên cu trúc hoc mô hình mà
chúng gi nh v tp d liu và cách chúng hiu chnh các mô hình  nhn
dng ra các phân hoch. Phm da trên mô hình c gng khp
gia các d liu vi mô hình toán hc, nó da trên gi nh rng d lic to
ra bng hn hp phân phi xác sun. Các thut toán phân cm da trên mô
hình có hai cách tip cn chính: mô hình thng kê và m. Ph
này gn ging vi phm da trên m, vì chúng phát trin các
cm riêng bit nhm ci tinh tr
khi nó không bu vi mt s cm c nh và không s dng cùng mt khái
nim m cho các cm.

Trích đoạn Khai phá dữliệu bằng phƣơng pháp tiếp cận Khai phá dữliệu có cấu trúc lớn

---