KHAI THÁC (cid:39)(cid:1266)(cid:3)(cid:47)(cid:44)(cid:1226)(cid:56)(cid:3)(cid:9)(cid:3) (cid:1260)(cid:49)(cid:42)(cid:3)(cid:39)(cid:1256)(cid:49)(cid:42) (DATA MINING)
(cid:42)(cid:57)(cid:3)(cid:29)(cid:3)(cid:49)(cid:42)(cid:56)(cid:60)(cid:1224)(cid:49)(cid:3)(cid:43)(cid:50)(cid:172)(cid:49)(cid:42)(cid:3)(cid:55)(cid:210)(cid:3)(cid:36)(cid:49)(cid:43)
1
BBÀI 5 (cid:178) Ph(cid:1195)n 1 GOM NHÓM D(cid:1266) LI(cid:1226)U
2
1
N(cid:1244)I DUNG
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88) 2. (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:83)(cid:75)(cid:105)(cid:83)(cid:3)(cid:83)(cid:75)(cid:107)(cid:81)(cid:3)(cid:75)(cid:82)(cid:1189)(cid:70)(cid:75) 3. (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:83)(cid:75)(cid:105)(cid:83)(cid:3)(cid:83)(cid:75)(cid:107)(cid:81)(cid:3)(cid:70)(cid:1193)(cid:83)
3
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56) 1. Gom nhóm là gì ? :
toán phân (cid:79)(cid:883)(cid:83)(cid:15) các
4
(cid:49)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:18)(cid:79)(cid:1247)(cid:83) : (cid:87)(cid:1201)(cid:83) các (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) DL Gom nhóm là quá trình nhóm các (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) thành (cid:81)(cid:75)(cid:903)(cid:81)(cid:74) (cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:893)(cid:80)(cid:18)(cid:79)(cid:883)(cid:83) có ý (cid:81)(cid:74)(cid:75)(cid:429)(cid:68). Các (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) trong cùng (cid:80)(cid:881)(cid:87) nhóm có (cid:81)(cid:75)(cid:76)(cid:857)(cid:88) tính (cid:70)(cid:75)(cid:829)(cid:87) chung và có (cid:81)(cid:75)(cid:903)(cid:81)(cid:74) tính (cid:70)(cid:75)(cid:829)(cid:87) khác (cid:89)(cid:883)(cid:76) các (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:887) nhóm khác. Cho CSDL D={t1,t2,(cid:171),tn} và (cid:86)(cid:1237) nguyên k, gom nhóm là bài toán xác (cid:255)(cid:1231)(cid:81)(cid:75) ánh (cid:91)(cid:1189) f : D(cid:74)(cid:74){1,(cid:171),k} sao cho (cid:80)(cid:1243)(cid:76) ti (cid:255)(cid:1133)(cid:1255)(cid:70) gán vào (cid:80)(cid:1245)(cid:87) nhóm (cid:11)(cid:79)(cid:1247)(cid:83)(cid:12) Kj, 1 (cid:100)(cid:100) j (cid:100)(cid:100) k . Không (cid:74)(cid:76)(cid:873)(cid:81)(cid:74) bài (cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:893)(cid:80)(cid:18)(cid:79)(cid:883)(cid:83) không (cid:255)(cid:769)(cid:891)(cid:70) (cid:69)(cid:76)(cid:855)(cid:87) (cid:87)(cid:85)(cid:769)(cid:883)(cid:70).
2
(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:47)(cid:1246)(cid:51)(cid:3)(cid:31)(cid:33)(cid:3)(cid:42)(cid:50)(cid:48)(cid:3)(cid:49)(cid:43)(cid:207)(cid:48)
Phân (cid:79)(cid:1247)(cid:83) : (cid:75)(cid:1233)(cid:70) có giám sát (Supervised learning) Tìm (cid:83)(cid:75)(cid:753)(cid:751)(cid:81)(cid:74) pháp (cid:255)(cid:843) (cid:71)(cid:889) (cid:255)(cid:82)(cid:105)(cid:81) (cid:79)(cid:867)(cid:83) (cid:70)(cid:879)(cid:68) (cid:80)(cid:819)(cid:88) (cid:80)(cid:867)(cid:76) (cid:87)(cid:883)
các (cid:80)(cid:819)(cid:88) (cid:255)(cid:109) gán nhãn (cid:79)(cid:867)(cid:83) (phân (cid:79)(cid:867)(cid:83)(cid:12) (cid:87)(cid:85)(cid:753)(cid:867)(cid:70)
5
(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:47)(cid:1246)(cid:51)(cid:3)(cid:31)(cid:33)(cid:3)(cid:42)(cid:50)(cid:48)(cid:3)(cid:49)(cid:43)(cid:207)(cid:48)
Gom nhóm : (cid:75)(cid:1233)(cid:70)(cid:3)(cid:78)(cid:75)(cid:123)(cid:81)(cid:74)(cid:3)(cid:74)(cid:76)(cid:105)(cid:80)(cid:3)(cid:86)(cid:105)(cid:87)(cid:3)(cid:11)(cid:56)(cid:81)(cid:86)(cid:88)(cid:83)(cid:72)(cid:85)(cid:89)(cid:76)(cid:86)(cid:72)(cid:71)
learning )
(cid:55)(cid:117)(cid:80)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:877)(cid:80)(cid:18)(cid:79)(cid:867)(cid:83)(cid:3)(cid:179)(cid:87)(cid:889)(cid:3)(cid:81)(cid:75)(cid:76)(cid:114)(cid:81)(cid:180)(cid:3)(cid:70)(cid:879)(cid:68)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:80)(cid:819)(cid:88)(cid:3)
(cid:70)(cid:75)(cid:753)(cid:68)(cid:3)(cid:255)(cid:753)(cid:875)(cid:70)(cid:3)(cid:74)(cid:105)(cid:81)(cid:3)(cid:81)(cid:75)(cid:109)(cid:81)(cid:3)
6
3
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56)
Khái (cid:81)(cid:76)(cid:863)(cid:80) (cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:893)(cid:80) (cid:177) (cid:81)(cid:75)(cid:837)(cid:83) (cid:81)(cid:75)(cid:841)(cid:81)(cid:74)
(cid:38)(cid:121)(cid:3)(cid:69)(cid:68)(cid:82)(cid:3)(cid:81)(cid:75)(cid:76)(cid:114)(cid:88)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:34)
(cid:25)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)
(cid:23)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)
(cid:21)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56)
(cid:122) (cid:1260)(cid:81)(cid:74) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:49)(cid:75)(cid:1201)(cid:81) (cid:71)(cid:1189)(cid:81)(cid:74) Phân tích (cid:71)(cid:903) (cid:79)(cid:76)(cid:863)(cid:88) không gian (cid:59)(cid:1265) lý (cid:1191)(cid:81)(cid:75) Khoa (cid:75)(cid:869)(cid:70) kinh (cid:87)(cid:855) ( (cid:255)(cid:847)(cid:70) (cid:69)(cid:76)(cid:863)(cid:87) nghiên (cid:70)(cid:897)(cid:88) (cid:87)(cid:76)(cid:855)(cid:83) (cid:87)(cid:75)(cid:867)(cid:12) W W W
8
Gom nhóm tài (cid:79)(cid:76)(cid:863)(cid:88) liên quan (cid:255)(cid:859) (cid:71)(cid:861) tìm (cid:78)(cid:76)(cid:855)(cid:80) Gom (cid:71)(cid:903) (cid:79)(cid:76)(cid:863)(cid:88) Weblog thành nhóm (cid:255)(cid:859) tìm các nhóm có cùng (cid:78)(cid:76)(cid:859)(cid:88) truy (cid:70)(cid:837)(cid:83) (cid:42)(cid:76)(cid:827)(cid:80) kích (cid:87)(cid:75)(cid:769)(cid:883)(cid:70) (cid:71)(cid:903) (cid:79)(cid:76)(cid:863)(cid:88) (cid:79)(cid:883)(cid:81)
4
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56)
(cid:122)Ví (cid:71)(cid:1257)
Discovered Clusters
Industry Group
1
Technology1-DOWN
2
Technology2-DOWN
Applied-Matl-DOWN,Bay-Network-Down,3-COM-DOWN, Cabletron-Sys-DOWN,CISCO-DOWN,HP-DOWN, DSC-Comm-DOWN,INTEL-DOWN,LSI-Logic-DOWN, Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down, Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOWN, Sun-DOWN Apple-Comp-DOWN,Autodesk-DOWN,DEC-DOWN, ADV-Micro-Device-DOWN,Andrew-Corp-DOWN, Computer-Assoc-DOWN,Circuit-City-DOWN, Compaq-DOWN, EMC-Corp-DOWN, Gen-Inst-DOWN, Motorola-DOWN,Microsoft-DOWN,Scientific-Atl-DOWN
Fannie-Mae-DOWN,Fed-Home-Loan-DOWN, MBNA-Corp-DOWN,Morgan-Stanley-DOWN
Financial-DOWN
Oil-UP
Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP, Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP, Schlumberger-UP
3 4
Gom gen và protein có cùng (cid:70)(cid:75)(cid:1261)(cid:70) (cid:81)(cid:259)(cid:81)(cid:74) Nhóm các (cid:70)(cid:1241) xu có (cid:83)(cid:75)(cid:76)(cid:1219)(cid:88) (cid:75)(cid:1133)(cid:1247)(cid:81)(cid:74) giá dao (cid:255)(cid:1245)(cid:81)(cid:74) (cid:74)(cid:76)(cid:1237)(cid:81)(cid:74) nhau Nhóm các vùng theo (cid:79)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:80)(cid:1133)(cid:68) (cid:1251) Úc
9
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56)
(cid:122) Ví (cid:71)(cid:1257) :
10
(cid:55)(cid:76)(cid:855)(cid:83) (cid:87)(cid:75)(cid:867) : phát (cid:75)(cid:76)(cid:863)(cid:81) các nhóm khách hàng trong CSDL khách hàng (cid:255)(cid:859) xây (cid:71)(cid:905)(cid:81)(cid:74) (cid:70)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) trình (cid:87)(cid:76)(cid:855)(cid:83) (cid:87)(cid:75)(cid:867) có (cid:80)(cid:893)(cid:70) tiêu (cid:264)(cid:829)(cid:87) (cid:255)(cid:68)(cid:76) : xác (cid:255)(cid:867)(cid:81)(cid:75) các vùng (cid:255)(cid:829)(cid:87) (cid:87)(cid:85)(cid:875)(cid:81)(cid:74) (cid:87)(cid:85)(cid:869)(cid:87) (cid:74)(cid:76)(cid:873)(cid:81)(cid:74) nhau trong CSDL quan sát trái (cid:255)(cid:829)(cid:87) (cid:37)(cid:827)(cid:82) (cid:75)(cid:76)(cid:859)(cid:80) : tìm nhóm khách hàng có (cid:78)(cid:75)(cid:827) (cid:81)(cid:259)(cid:81)(cid:74) hay (cid:74)(cid:847)(cid:83) tai (cid:81)(cid:825)(cid:81) Nghiên (cid:70)(cid:897)(cid:88) (cid:255)(cid:881)(cid:81)(cid:74) (cid:255)(cid:829)(cid:87) : gom nhóm các tâm (cid:70)(cid:75)(cid:829)(cid:81) (cid:255)(cid:881)(cid:81)(cid:74) (cid:255)(cid:829)(cid:87) quan sát (cid:255)(cid:769)(cid:891)(cid:70) theo (cid:89)(cid:855)(cid:87) (cid:81)(cid:897)(cid:87) (cid:79)(cid:893)(cid:70) (cid:255)(cid:867)(cid:68)
5
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:42)(cid:82)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:81)(cid:74)(cid:123)(cid:76)(cid:3)(cid:81)(cid:75)(cid:106)(cid:3)
(cid:39)(cid:1269)(cid:68)(cid:3)(cid:87)(cid:85)(cid:114)(cid:81)(cid:3)(cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74)(cid:3)(cid:70)(cid:105)(cid:70)(cid:75)(cid:3)(cid:255)(cid:1231)(cid:68)(cid:3)(cid:79)(cid:234)
11
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:42)(cid:82)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:81)(cid:74)(cid:123)(cid:76)(cid:3)(cid:81)(cid:75)(cid:106)(cid:3)
(cid:39)(cid:1269)(cid:68)(cid:3)(cid:87)(cid:85)(cid:114)(cid:81)(cid:3)(cid:78)(cid:116)(cid:70)(cid:75)(cid:3)(cid:87)(cid:75)(cid:1133)(cid:1247)(cid:70)
12
6
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:42)(cid:82)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)
13
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56)
(cid:38)(cid:105)(cid:70)(cid:75)(cid:3)(cid:69)(cid:76)(cid:1223)(cid:88)(cid:3)(cid:71)(cid:76)(cid:1225)(cid:81)(cid:3) (cid:70)(cid:105)(cid:70)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)
I1
0.5 0.2 0.3
I2
(cid:171)
In
14
1 2 3
Phân chia (cid:69)(cid:1205)(cid:81)(cid:74) các (cid:255)(cid:1133)(cid:1249)(cid:81)(cid:74) ranh (cid:74)(cid:76)(cid:1247)(cid:76) Các (cid:78)(cid:75)(cid:1237)(cid:76) (cid:70)(cid:1195)(cid:88) Theo xác (cid:86)(cid:88)(cid:1193)(cid:87) (cid:54)(cid:1131) (cid:255)(cid:1239) hình cây (cid:171)
7
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56) 2. (cid:55)(cid:76)(cid:114)(cid:88)(cid:3)(cid:70)(cid:75)(cid:88)(cid:1197)(cid:81)(cid:3)(cid:74)(cid:82)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)(cid:29)
(cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp gom nhóm (cid:87)(cid:1237)(cid:87) là (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp (cid:86)(cid:1217) (cid:87)(cid:1189)(cid:82) các nhóm có (cid:70)(cid:75)(cid:1193)(cid:87) (cid:79)(cid:1133)(cid:1255)(cid:81)(cid:74) :
(cid:54)(cid:905) (cid:74)(cid:76)(cid:873)(cid:81)(cid:74) nhau (cid:74)(cid:76)(cid:903)(cid:68) (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) trong cùng (cid:80)(cid:881)(cid:87) nhóm cao. (cid:42)(cid:76)(cid:903)(cid:68) các nhóm thì (cid:86)(cid:905) (cid:74)(cid:76)(cid:873)(cid:81)(cid:74) nhau (cid:87)(cid:75)(cid:829)(cid:83).
(cid:46)(cid:75)(cid:82)(cid:608)(cid:81)(cid:74)(cid:3)(cid:70)(cid:105)(cid:70)(cid:75)(cid:3) (cid:74)(cid:76)(cid:879)(cid:68)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3) nhóm là max
(cid:46)(cid:75)(cid:82)(cid:608)(cid:81)(cid:74)(cid:3)(cid:70)(cid:105)(cid:70)(cid:75)(cid:3)(cid:69)(cid:114)(cid:81)(cid:3) trong nhóm là min
15
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56) 2. (cid:55)(cid:76)(cid:114)(cid:88)(cid:3)(cid:70)(cid:75)(cid:88)(cid:1197)(cid:81)(cid:3)(cid:74)(cid:82)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)(cid:11)(cid:87)(cid:87)(cid:12)(cid:29)
(cid:38)(cid:75)(cid:1193)(cid:87) (cid:79)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:70)(cid:1259)(cid:68) (cid:78)(cid:1219)(cid:87) (cid:84)(cid:88)(cid:1191) gom nhóm (cid:71)(cid:1269)(cid:68) trên 2 (cid:92)(cid:1219)(cid:88) (cid:87)(cid:1237) :
(cid:264)(cid:881) (cid:255)(cid:82) (cid:86)(cid:905) (cid:74)(cid:76)(cid:873)(cid:81)(cid:74) nhau dùng trong (cid:83)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) pháp gom nhóm và (cid:54)(cid:905) thi hành nó
(cid:48)(cid:881)(cid:87) (cid:86)(cid:873) (cid:255)(cid:881) (cid:255)(cid:82) (cid:70)(cid:75)(cid:829)(cid:87) (cid:79)(cid:769)(cid:891)(cid:81)(cid:74) :
Bình (cid:83)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) sai (Sum of Squared Error - SSE) Entropy
16
8
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56) 3. (cid:264)(cid:1245)(cid:3)(cid:255)(cid:82)(cid:3)(cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74)(cid:3)(cid:70)(cid:105)(cid:70)(cid:75)(cid:3)(cid:29)
q
q
q
x
x
q )|
(|
|
|
|
|
... (cid:14)(cid:14)
(cid:16)
(cid:14)
(cid:16)
(cid:32)
(cid:16)
x i
j
x i p
j p
2
x i 1
2
j 1
(cid:264)(cid:1245) (cid:255)(cid:82) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:87)(cid:75)(cid:1133)(cid:1249)(cid:81)(cid:74) dùng (cid:255)(cid:1223) xác (cid:255)(cid:1231)(cid:81)(cid:75) (cid:86)(cid:1269) khác nhau hay (cid:74)(cid:76)(cid:1237)(cid:81)(cid:74) nhau (cid:74)(cid:76)(cid:1267)(cid:68) hai (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) . (cid:46)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Minkowski : jid x ),(
(cid:177) (cid:49)(cid:1219)(cid:88) q=1, d là (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Manhattan :
|
|
|
|
|
jid |),( (cid:32)
(cid:16)
(cid:14)
(cid:16)
... (cid:14)(cid:14)
(cid:16)
ix
jx
ix
jx
ix
p
jx
p
1
1
2
2
17
(cid:89)(cid:867)(cid:76) i = (xi1, xi2,(cid:171), xip) và j = (xj1, xj2,(cid:171), xjp) : hai (cid:255)(cid:849)(cid:76) (cid:87)(cid:585)(cid:867)(cid:81)(cid:74)p-(cid:70)(cid:75)(cid:76)(cid:638)(cid:88)vàqlà(cid:86)(cid:849)nguyên(cid:71)(cid:585)(cid:583)(cid:81)(cid:74)
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56) 3. (cid:264)(cid:1245)(cid:3)(cid:255)(cid:82)(cid:3)(cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74)(cid:3)(cid:70)(cid:105)(cid:70)(cid:75)(cid:3)(cid:11)(cid:87)(cid:87)(cid:12)
(cid:49)(cid:1219)(cid:88) q=2, d là (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Euclide :
2
2
x
x
x
jid ),(
(|
|
|
|
|
2 )|
(cid:32)
(cid:16)
(cid:14)
(cid:16)
... (cid:14)(cid:14)
(cid:16)
x i
j
x i p
j p
x i 1
j 1
2
2
Tính (cid:70)(cid:75)(cid:1193)(cid:87) (cid:70)(cid:1259)(cid:68) (cid:255)(cid:1245) (cid:255)(cid:82) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:132) d(i,j)(cid:116) 0 (cid:132) d(i,i)= 0
(cid:132) d(i,j)= d(j,i)
(cid:132) d(i,j)(cid:100) d(i,k)+ d(k,j)
18
9
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56)
4. Các (cid:78)(cid:76)(cid:1223)(cid:88) (cid:71)(cid:1267) (cid:79)(cid:76)(cid:1227)(cid:88)
Các (cid:78)(cid:76)(cid:1223)(cid:88) (cid:71)(cid:1267) (cid:79)(cid:76)(cid:1227)(cid:88) khác nhau yêu (cid:70)(cid:1195)(cid:88) (cid:255)(cid:1245) (cid:255)(cid:82) (cid:86)(cid:1269) khác nhau (cid:70)(cid:458)(cid:81)(cid:74) khác nhau.
(cid:122) Các (cid:69)(cid:76)(cid:855)(cid:81) (cid:87)(cid:909) (cid:79)(cid:863) theo (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) : (cid:46)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74)
cách Euclide
(cid:122) Các (cid:69)(cid:76)(cid:1219)(cid:81) (cid:81)(cid:75)(cid:1231) phân : (cid:75)(cid:1227) (cid:86)(cid:1237) so (cid:78)(cid:75)(cid:1247)(cid:83)(cid:15)
(cid:75)(cid:1227) (cid:86)(cid:1237) Jaccard
(cid:122) Các (cid:69)(cid:76)(cid:855)(cid:81) tên, (cid:87)(cid:75)(cid:897) (cid:87)(cid:905)(cid:15) (cid:87)(cid:909) (cid:79)(cid:863) : (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74)
cách Minkowski
(cid:122) Các (cid:69)(cid:76)(cid:1219)(cid:81) (cid:71)(cid:1189)(cid:81)(cid:74) (cid:75)(cid:1243)(cid:81) (cid:75)(cid:1255)(cid:83) : công (cid:87)(cid:75)(cid:1261)(cid:70)
19
(cid:87)(cid:85)(cid:1233)(cid:81)(cid:74) (cid:79)(cid:1133)(cid:1255)(cid:81)(cid:74)
(cid:42)(cid:44)(cid:1246)(cid:44)(cid:3)(cid:55)(cid:43)(cid:44)(cid:1226)(cid:56)
5. (cid:48)(cid:1245)(cid:87)(cid:3)(cid:86)(cid:1237)(cid:3)(cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:83)(cid:75)(cid:105)(cid:83)(cid:3)(cid:74)(cid:82)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)(cid:29)
(cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp phân (cid:75)(cid:82)(cid:1189)(cid:70)(cid:75) (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp phân (cid:70)(cid:1193)(cid:83) (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp (cid:71)(cid:1269)(cid:68) trên (cid:80)(cid:1201)(cid:87) (cid:255)(cid:1245) (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp (cid:71)(cid:1269)(cid:68) trên (cid:79)(cid:1133)(cid:1247)(cid:76) (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp (cid:71)(cid:1269)(cid:68) trên mô hình
20
10
N(cid:1244)I DUNG
1. (cid:42)(cid:76)(cid:1247)(cid:76) (cid:87)(cid:75)(cid:76)(cid:1227)(cid:88) 2. (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:83)(cid:75)(cid:105)(cid:83)(cid:3)(cid:83)(cid:75)(cid:107)(cid:81)(cid:3)(cid:75)(cid:82)(cid:1189)(cid:70)(cid:75) 3. (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp phân (cid:70)(cid:1193)(cid:83)
21
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
1. (cid:46)(cid:75)(cid:105)(cid:76)(cid:3)(cid:81)(cid:76)(cid:1227)(cid:80)(cid:3)(cid:70)(cid:1131)(cid:3)(cid:69)(cid:1191)(cid:81)(cid:3)(cid:29)
(cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp phân (cid:75)(cid:82)(cid:1189)(cid:70)(cid:75) : xây (cid:71)(cid:1269)(cid:81)(cid:74) k (k
22
11
(cid:37)(cid:76)(cid:1223)(cid:88) (cid:71)(cid:76)(cid:1225)(cid:81) (cid:80)(cid:1243)(cid:76) nhóm (cid:69)(cid:1205)(cid:81)(cid:74) giá (cid:87)(cid:85)(cid:867) trung bình (cid:70)(cid:1259)(cid:68) (cid:71)(cid:1267)
(cid:79)(cid:76)(cid:1227)(cid:88) trong nhóm (cid:255)(cid:121) : (cid:87)(cid:75)(cid:88)(cid:837)(cid:87) toán K-means (1967)
(cid:37)(cid:76)(cid:1223)(cid:88) (cid:71)(cid:76)(cid:1225)(cid:81) nhóm (cid:69)(cid:1205)(cid:81)(cid:74) (cid:80)(cid:1245)(cid:87) (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:81)(cid:1205)(cid:80) (cid:74)(cid:1195)(cid:81)
trung tâm (cid:70)(cid:1259)(cid:68) nhóm : (cid:87)(cid:75)(cid:88)(cid:837)(cid:87) toán k-medoids, PAM
(1987)
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
1. (cid:46)(cid:75)(cid:105)(cid:76)(cid:3)(cid:81)(cid:76)(cid:1227)(cid:80)(cid:3)(cid:70)(cid:1131)(cid:3)(cid:69)(cid:1191)(cid:81)(cid:3)(cid:11)(cid:87)(cid:87)(cid:12)(cid:29)
K
dist
2
SSE
(
xm
),
i
(cid:32)
i
Cx
i
1
(cid:32) (cid:143)
Công (cid:87)(cid:75)(cid:1261)(cid:70) tính Bình (cid:83)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) sai ( Sum of Squared
Error - SSE)
(cid:166) (cid:166)
(cid:57)(cid:883)(cid:76) x là (cid:80)(cid:881)(cid:87) (cid:255)(cid:76)(cid:859)(cid:80) DL trong nhóm Ci và mi là (cid:255)(cid:76)(cid:859)(cid:80) (cid:255)(cid:825)(cid:76) (cid:71)(cid:76)(cid:863)(cid:81) cho
nhóm (cid:11)(cid:255)(cid:76)(cid:859)(cid:80) TB nhóm (cid:75)(cid:82)(cid:847)(cid:70) (cid:255)(cid:76)(cid:859)(cid:80) trung tâm nhóm), K-(cid:86)(cid:873)
nhóm. dist (): (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách Euclide
(cid:122) (cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:87)(cid:68)(cid:3)(cid:70)(cid:121)(cid:3)(cid:21)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:3)(cid:89)(cid:1247)(cid:76)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:87)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:1261)(cid:81)(cid:74)(cid:3)
23
(cid:122) SSE = 12+0+0+62+82+162+262+72+212 =1523
m1=3, m2=4
(cid:122) K1={2,3}, K2={4,10,12,20,30,11,25}
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
2. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:78)-means :
Cho (cid:86)(cid:873) k, (cid:80)(cid:879)(cid:76) nhóm (cid:255)(cid:769)(cid:891)(cid:70) (cid:69)(cid:76)(cid:859)(cid:88) (cid:71)(cid:76)(cid:861)(cid:81) (cid:69)(cid:841)(cid:81)(cid:74) giá (cid:87)(cid:85)(cid:867) TB (cid:70)(cid:895)(cid:68) DL
(cid:122)
(cid:122)
(cid:122)
trong nhóm
B1: (cid:38)(cid:75)(cid:1233)(cid:81) (cid:81)(cid:74)(cid:1199)(cid:88) nhiên k (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:81)(cid:75)(cid:1133) là (cid:81)(cid:75)(cid:1267)(cid:81)(cid:74) trung tâm
(cid:70)(cid:1259)(cid:68) các nhóm .
B2 : Gán (cid:87)(cid:899)(cid:81)(cid:74) (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) còn (cid:79)(cid:825)(cid:76) vào nhóm có trung tâm
nhóm (cid:74)(cid:831)(cid:81) nó (cid:81)(cid:75)(cid:829)(cid:87) (cid:11)(cid:71)(cid:905)(cid:68) trên (cid:255)(cid:881) (cid:255)(cid:82) (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách Euclide)
B3 : Tính (cid:79)(cid:1189)(cid:76) giá (cid:87)(cid:85)(cid:1231) trung tâm (cid:70)(cid:1259)(cid:68) (cid:87)(cid:1263)(cid:81)(cid:74) nhóm
(cid:122)
(cid:122)
Di (cid:70)(cid:75)(cid:88)(cid:92)(cid:1223)(cid:81) trung tâm nhóm (cid:89)(cid:1221) = giá (cid:87)(cid:85)(cid:1231) TB (cid:80)(cid:1247)(cid:76) (cid:70)(cid:1259)(cid:68) nhóm
Cho nhóm Ki={ti1,ti2,(cid:171),tim}, giá (cid:87)(cid:85)(cid:867) trung bình (cid:70)(cid:895)(cid:68) nhóm là
mi = (1/m)(ti1 + (cid:171) + tim)
(cid:122)
B4 : (cid:49)(cid:855)(cid:88) các trung tâm nhóm không có gì thay (cid:255)(cid:877)(cid:76) thì
(cid:71)(cid:899)(cid:81)(cid:74)(cid:15) (cid:81)(cid:74)(cid:769)(cid:891)(cid:70) (cid:79)(cid:825)(cid:76) quay (cid:79)(cid:825)(cid:76) B2.
24
12
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:20)
k1 Y
k2
3
(cid:38)(cid:75)(cid:1233)(cid:81)
trung tâm
nhóm (cid:69)(cid:1193)(cid:87)
(cid:78)(cid:484) : k1, k2,
k3 k3
25
X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:21)
k1 Y
k2
k3 Gán (cid:87)(cid:1263)(cid:81)(cid:74)
(cid:255)(cid:76)(cid:1223)(cid:80) vào
nhóm có
trung tâm
nhóm (cid:74)(cid:1195)(cid:81)
(cid:81)(cid:75)(cid:1193)(cid:87)
26
13
X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:22)
k1 k1 Y
k2
k3 k2
27
k3 (cid:70)(cid:75)(cid:88)(cid:92)(cid:1223)(cid:81)
tâm
nhóm
(cid:255)(cid:76)(cid:1223)(cid:80)
bình
(cid:70)(cid:1259)(cid:68) Di
trung
(cid:87)(cid:1263)(cid:81)(cid:74)
(cid:89)(cid:1221)
trung
(cid:80)(cid:1247)(cid:76)
nhóm X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:23)
k1 Y
k3 (cid:42)(cid:105)(cid:81)(cid:3)(cid:79)(cid:1189)(cid:76)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)
(cid:255)(cid:76)(cid:1223)(cid:80)(cid:3)(cid:70)(cid:75)(cid:82)(cid:3)(cid:74)(cid:1195)(cid:81)(cid:3)
(cid:89)(cid:1247)(cid:76)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)
(cid:87)(cid:107)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)(cid:80)(cid:1247)(cid:76) k2
28
14
(cid:52)(cid:29)(cid:3)(cid:38)(cid:105)(cid:70)(cid:3)(cid:255)(cid:76)(cid:843)(cid:80)(cid:3)
(cid:81)(cid:106)(cid:82)(cid:3)(cid:255)(cid:753)(cid:875)(cid:70)(cid:3)(cid:74)(cid:105)(cid:81)(cid:3)
(cid:79)(cid:809)(cid:76)(cid:3)(cid:34) X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:23)(cid:3)(cid:171)
k1 Y
k3
(cid:22)(cid:3)(cid:255)(cid:76)(cid:843)(cid:80)(cid:3)
(cid:255)(cid:753)(cid:875)(cid:70)(cid:3)
(cid:74)(cid:105)(cid:81)(cid:3)(cid:79)(cid:809)(cid:76)
k2
29
X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:23)(cid:69)
k1 Y
k3 k2
(cid:55)(cid:116)(cid:81)(cid:75)(cid:3)(cid:79)(cid:1189)(cid:76)(cid:3)
trung
bình
nhóm
30
15
X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:24)
k1
Y
k2
k3
Di
(cid:70)(cid:75)(cid:88)(cid:92)(cid:1223)(cid:81)
tâm
trung
nhóm (cid:89)(cid:1221) giá
(cid:87)(cid:85)(cid:1231) TB nhóm
(cid:80)(cid:1247)(cid:76)(cid:15) (cid:171)
31
X
Ví d(cid:1257) : k-mean
Customer
Age Income
Income
(K)
0.55 0.175
John
0.34 0.25
Rachel
1
1
Hannah
0.93 0.85
Tom
0.39 0.2
nellie
0.58 0.25
David
Age
16
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:78)-mean
(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:20)(cid:29)(cid:3)(cid:38)(cid:75)(cid:1233)(cid:81)(cid:3)(cid:49)(cid:72)(cid:79)(cid:79)(cid:76)(cid:72)(cid:3)(cid:89)(cid:106)(cid:3)(cid:39)(cid:68)(cid:89)(cid:76)(cid:71)(cid:3)(cid:79)(cid:106)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:3)(cid:36)(cid:3)
và B
Customer
Income
Distance
from
David
Distance
from
Nellie
0.08
0.161
John
0.24
0.07
Rachel
Hannah
0.859
1.006
B
0.694
0.845
Tom
A
Nellie
David
Age
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:29)(cid:3)k-mean
Income
(cid:37)(cid:21)(cid:3)(cid:29)(cid:3)(cid:55)(cid:116)(cid:81)(cid:75)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:80)(cid:1247)(cid:76)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:3)(cid:36)(cid:3)(cid:89)(cid:106)(cid:3)(cid:37)(cid:3)(cid:29)
(cid:55)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:38)(cid:79)(cid:88)(cid:86)(cid:87)(cid:72)(cid:85)(cid:3)(cid:36)(cid:3)(cid:29)(cid:3)
(cid:122) Age 0.37, Income=0.23
B
A
(cid:55)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:38)(cid:79)(cid:88)(cid:86)(cid:87)(cid:72)(cid:85)(cid:3)(cid:37)(cid:3)(cid:29)(cid:3)
(cid:122) Age 0.77, Income=0.57
Age
17
(cid:39)(cid:1269)(cid:68)(cid:3)(cid:87)(cid:85)(cid:114)(cid:81)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1257)(cid:80)(cid:3)
(cid:80)(cid:1247)(cid:76)(cid:15)(cid:3)(cid:74)(cid:105)(cid:81)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:78)(cid:75)(cid:105)(cid:70)(cid:75)(cid:3)(cid:75)(cid:106)(cid:81)(cid:74)(cid:3)
(cid:89)(cid:106)(cid:82)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:17)
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:29)(cid:3)(cid:78)-mean
Customer
Distance A Distance B
Income
John
Rachel
B
Hannah
0.19
0.04
1.00
0.45
0.53
0.49
Tom
A
Nellie
0.84
0.04
0.33
0.53
David
0.22
0.37
Age
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:29)(cid:3)k-mean
Income
(cid:37)(cid:22)(cid:29)(cid:3)(cid:55)(cid:116)(cid:81)(cid:75)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:80)(cid:1247)(cid:76)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:3)(cid:36)(cid:3)(cid:89)(cid:106)(cid:3)(cid:37)(cid:3)(cid:29)
B
(cid:55)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:38)(cid:79)(cid:88)(cid:86)(cid:87)(cid:72)(cid:85)(cid:3)(cid:36)(cid:3)(cid:29)(cid:3)
(cid:122) Age 0.47, Income=0.22
(cid:122) Age 0.97, Income= 0.93
A
(cid:55)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:38)(cid:79)(cid:88)(cid:86)(cid:87)(cid:72)(cid:85)(cid:3)(cid:37)(cid:3)(cid:29)(cid:3)
(cid:122) (cid:57)(cid:883)(cid:76) các trung tâm nhóm
(cid:80)(cid:883)(cid:76) này, thành (cid:83)(cid:75)(cid:831)(cid:81) (cid:70)(cid:895)(cid:68)
các nhóm không thay (cid:255)(cid:877)(cid:76).
(cid:122) (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87) toán (cid:71)(cid:1263)(cid:81)(cid:74).
Age
18
(cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:46)-means
(cid:1132)(cid:88) (cid:255)(cid:76)(cid:1223)(cid:80) :
(cid:122) (cid:264)(cid:1131)(cid:81) (cid:74)(cid:76)(cid:1191)(cid:81)(cid:15) (cid:71)(cid:1225) (cid:75)(cid:76)(cid:1223)(cid:88)(cid:15) (cid:87)(cid:1133)(cid:1131)(cid:81)(cid:74) (cid:255)(cid:1237)(cid:76) (cid:75)(cid:76)(cid:1227)(cid:88) (cid:84)(cid:88)(cid:1191).
(cid:122) Các (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:87)(cid:905) (cid:255)(cid:881)(cid:81)(cid:74) gán vào các
nhóm.
(cid:122) (cid:55)(cid:75)(cid:1133)(cid:1249)(cid:81)(cid:74) (cid:255)(cid:1189)(cid:87) (cid:255)(cid:1133)(cid:1255)(cid:70) (cid:87)(cid:1237)(cid:76) (cid:1133)(cid:88) (cid:70)(cid:1257)(cid:70) (cid:69)(cid:1245).
37
(cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:46)-means
(cid:49)(cid:75)(cid:1133)(cid:1255)(cid:70) (cid:255)(cid:76)(cid:1223)(cid:80) :
(cid:122) (cid:55)(cid:75)(cid:88)(cid:1245)(cid:70) tính phi (cid:86)(cid:1237) ?
(cid:122) (cid:38)(cid:831)(cid:81) xác (cid:255)(cid:867)(cid:81)(cid:75) (cid:86)(cid:873) nhóm (k) (cid:87)(cid:85)(cid:769)(cid:883)(cid:70)
(cid:122) (cid:55)(cid:1193)(cid:87) (cid:70)(cid:1191) các (cid:255)(cid:1237)(cid:76)
(cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:83)(cid:75)(cid:1191)(cid:76) gán vào các
nhóm
(cid:122) (cid:51)(cid:75)(cid:1257) (cid:87)(cid:75)(cid:88)(cid:1245)(cid:70) vào (cid:89)(cid:76)(cid:1227)(cid:70) (cid:70)(cid:75)(cid:1233)(cid:81) các nhóm (cid:255)(cid:1195)(cid:88) tiên
(cid:122) (cid:42)(cid:1211)(cid:83) (cid:89)(cid:1193)(cid:81) (cid:255)(cid:1221) khi các nhóm có kích (cid:87)(cid:75)(cid:1133)(cid:1247)(cid:70)(cid:15)
(cid:80)(cid:1201)(cid:87) (cid:255)(cid:1245) khác nhau (cid:75)(cid:82)(cid:1211)(cid:70) hình dáng không
(cid:83)(cid:75)(cid:1191)(cid:76) là hình (cid:70)(cid:1195)(cid:88)
(cid:122) (cid:49)(cid:75)(cid:825)(cid:92) (cid:70)(cid:827)(cid:80) (cid:89)(cid:883)(cid:76) DL (cid:81)(cid:75)(cid:76)(cid:861)(cid:88)(cid:15) cá (cid:69)(cid:76)(cid:863)(cid:87)
38
19
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
3. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:78)-medoids : PAM
Cho (cid:86)(cid:873) k, (cid:80)(cid:879)(cid:76) nhóm (cid:255)(cid:769)(cid:891)(cid:70) (cid:69)(cid:76)(cid:859)(cid:88) (cid:71)(cid:76)(cid:861)(cid:81) (cid:69)(cid:841)(cid:81)(cid:74) (cid:80)(cid:881)(cid:87)
trong các (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:74)(cid:1195)(cid:81) trung tâm nhóm (cid:81)(cid:75)(cid:829)(cid:87)
(cid:122) B1: (cid:38)(cid:75)(cid:1233)(cid:81) (cid:81)(cid:74)(cid:1199)(cid:88) nhiên k (cid:255)(cid:1237)(cid:76)
(cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:81)(cid:75)(cid:1133) là
(cid:81)(cid:75)(cid:1267)(cid:81)(cid:74) (cid:87)(cid:85)(cid:869)(cid:81)(cid:74) tâm (cid:70)(cid:1259)(cid:68) các nhóm .
(cid:122) B2 : gán (cid:87)(cid:899)(cid:81)(cid:74) (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) còn (cid:79)(cid:825)(cid:76) vào nhóm có
(cid:87)(cid:85)(cid:869)(cid:81)(cid:74) tâm (cid:70)(cid:893)(cid:80) (cid:74)(cid:831)(cid:81) nó (cid:81)(cid:75)(cid:829)(cid:87) .
(cid:122) B3 : (cid:38)(cid:75)(cid:1233)(cid:81) (cid:80)(cid:1245)(cid:87) (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:69)(cid:1193)(cid:87) (cid:78)(cid:484). Hoán (cid:255)(cid:1241)(cid:76) nó
(cid:89)(cid:1247)(cid:76) (cid:87)(cid:85)(cid:1233)(cid:81)(cid:74) tâm (cid:70)(cid:1259)(cid:68) nhóm. (cid:49)(cid:1219)(cid:88) (cid:70)(cid:75)(cid:1193)(cid:87) (cid:79)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:70)(cid:1259)(cid:68)
các nhóm (cid:87)(cid:259)(cid:81)(cid:74) lên thì quay (cid:79)(cid:1189)(cid:76) B2. (cid:49)(cid:74)(cid:1133)(cid:1255)(cid:70) (cid:79)(cid:1189)(cid:76)
(cid:87)(cid:76)(cid:1219)(cid:83) (cid:87)(cid:1257)(cid:70) (cid:87)(cid:75)(cid:1269)(cid:70) (cid:75)(cid:76)(cid:1227)(cid:81) B3 cho (cid:255)(cid:1219)(cid:81) khi không còn có
thay (cid:255)(cid:1241)(cid:76).
39
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
3. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:78)-medoids (tt):
(cid:49)(cid:75)(cid:837)(cid:81) xét :
(cid:122) (cid:55)(cid:75)(cid:88)(cid:837)(cid:87) toán PAM (cid:75)(cid:76)(cid:863)(cid:88) (cid:84)(cid:88)(cid:827) (cid:75)(cid:767)(cid:81) so (cid:89)(cid:883)(cid:76) k-means
khi có (cid:80)(cid:847)(cid:87) DL (cid:81)(cid:75)(cid:76)(cid:861)(cid:88)(cid:15) cá (cid:69)(cid:76)(cid:863)(cid:87).
(cid:122) PAM (cid:75)(cid:76)(cid:1227)(cid:88) (cid:84)(cid:88)(cid:1191) (cid:89)(cid:1247)(cid:76) (cid:87)(cid:1201)(cid:83) DL (cid:81)(cid:75)(cid:1235) (cid:81)(cid:75)(cid:1133)(cid:81)(cid:74) không co
dãn (cid:87)(cid:1237)(cid:87) (cid:89)(cid:1247)(cid:76) (cid:87)(cid:1201)(cid:83) DL (cid:79)(cid:1247)(cid:81)
(cid:122) Phát (cid:87)(cid:85)(cid:76)(cid:859)(cid:81) :
(cid:122)
(cid:122)
40
20
CLARA (Clustering LARge Applications) : (cid:71)(cid:1269)(cid:68) trên
(cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp (cid:79)(cid:1193)(cid:92) (cid:80)(cid:1199)(cid:88) (1990)
CLARANS(Clustering LARge Application based upon
RANdomized Search) : (cid:79)(cid:1193)(cid:92) (cid:80)(cid:1199)(cid:88) (cid:255)(cid:1245)(cid:81)(cid:74) (1994)
N(cid:1244)I DUNG
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88)
2. (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:83)(cid:75)(cid:105)(cid:83)(cid:3)(cid:83)(cid:75)(cid:107)(cid:81)(cid:3)(cid:75)(cid:82)(cid:1189)(cid:70)(cid:75)
3. (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:83)(cid:75)(cid:105)(cid:83)(cid:3)(cid:83)(cid:75)(cid:107)(cid:81)(cid:3)(cid:70)(cid:1193)(cid:83)
41
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88)(cid:3)(cid:29)
(cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp phân (cid:70)(cid:1193)(cid:83) : xây (cid:71)(cid:1269)(cid:81)(cid:74) các nhóm và (cid:87)(cid:1241)
(cid:70)(cid:75)(cid:1261)(cid:70) (cid:81)(cid:75)(cid:1133) cây phân (cid:70)(cid:1193)(cid:83).
(cid:37)(cid:76)(cid:1223)(cid:88) (cid:71)(cid:76)(cid:1225)(cid:81) (cid:71)(cid:1133)(cid:1247)(cid:76) (cid:71)(cid:1189)(cid:81)(cid:74) (cid:86)(cid:1131) (cid:255)(cid:1239) hình cây (dendrogram):
(cid:79)(cid:1133)(cid:88) (cid:79)(cid:1189)(cid:76) quá trình gom (cid:79)(cid:1189)(cid:76) / phân chia nhóm
5
6
0.2
4
3
4
0.15
2
5
2
0.1
1
0.05
1
3
0
42
1
3
2
5
4
6
21
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88)(cid:3)(cid:11)(cid:87)(cid:87)(cid:12)(cid:29)
Không (cid:70)(cid:831)(cid:81) xác (cid:255)(cid:867)(cid:81)(cid:75) (cid:87)(cid:85)(cid:769)(cid:883)(cid:70) (cid:86)(cid:873) nhóm k.
Xác (cid:255)(cid:867)(cid:81)(cid:75) (cid:86)(cid:873) nhóm (cid:70)(cid:831)(cid:81) (cid:87)(cid:75)(cid:76)(cid:855)(cid:87) (cid:69)(cid:841)(cid:81)(cid:74) (cid:89)(cid:76)(cid:863)(cid:70) (cid:70)(cid:839)(cid:87) ngang (cid:86)(cid:767) (cid:255)(cid:875)
hình cây (cid:87)(cid:825)(cid:76) (cid:80)(cid:897)(cid:70) thích (cid:75)(cid:891)(cid:83).
Hai (cid:79)(cid:82)(cid:1189)(cid:76) phân (cid:70)(cid:1193)(cid:83) chính :
Tích (cid:87)(cid:1257) : (cid:87)(cid:1263) (cid:71)(cid:1133)(cid:1247)(cid:76) lên trên, (cid:80)(cid:1243)(cid:76) (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) là (cid:80)(cid:1245)(cid:87) nhóm
Chia (cid:81)(cid:75)(cid:1235) : (cid:87)(cid:1263) trên (cid:91)(cid:88)(cid:1237)(cid:81)(cid:74)(cid:15) (cid:87)(cid:1193)(cid:87) (cid:70)(cid:1191) các (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) là 1 nhóm
43
(cid:55)(cid:75)(cid:88)(cid:837)(cid:87) toán :
AGNES, DIANA
BIRCH (Balance Iterative Reducing & Clustering using
Hierachies)
CURE (Clustering Using Representative)
ROCK (Robust Clustering using linKs)
CHAMELEON
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88)(cid:3)(cid:11)(cid:87)(cid:87)(cid:12)(cid:29)
Cách xác (cid:255)(cid:867)(cid:81)(cid:75) (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:903)(cid:68) các nhóm :
Single Link : (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách (cid:74)(cid:831)(cid:81) (cid:81)(cid:75)(cid:829)(cid:87) (cid:74)(cid:76)(cid:903)(cid:68) hai (cid:255)(cid:873)(cid:76)
(cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:881)(cid:70) hai nhóm
Complete Link : (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách xa (cid:81)(cid:75)(cid:829)(cid:87) (cid:74)(cid:76)(cid:903)(cid:68) hai
(cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:881)(cid:70) hai nhóm
44
22
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
Step
1
Step
2
Step
3
Step
4
Step
0
(cid:55)(cid:116)(cid:70)(cid:75)(cid:3)(cid:87)(cid:1257)
(agglomerative)
a
a b
b
a b c d e
c
c d e
d
d e
e
(cid:38)(cid:75)(cid:76)(cid:68)(cid:3)(cid:81)(cid:75)(cid:1235)
(divisive)
45
Step
3
Step
2
Step
1
Step
0
Step
4
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
2. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)(cid:3)(cid:11)(cid:36)(cid:74)(cid:74)(cid:79)(cid:82)(cid:80)(cid:72)(cid:85)(cid:68)(cid:87)(cid:76)(cid:89)(cid:72)(cid:3)
Nesting):
B1: (cid:48)(cid:1243)(cid:76) (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) là (cid:80)(cid:1245)(cid:87) nhóm.
B2: (cid:43)(cid:891)(cid:83) (cid:81)(cid:75)(cid:829)(cid:87) các nhóm có (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:903)(cid:68)
các nhóm là (cid:81)(cid:75)(cid:871) (cid:81)(cid:75)(cid:829)(cid:87) (Single Link/ Complete
Link)
B3 : (cid:49)(cid:1219)(cid:88) thu (cid:255)(cid:1133)(cid:1255)(cid:70) nhóm (cid:179)(cid:87)(cid:82)(cid:106)(cid:81) (cid:69)(cid:1245)(cid:180) thì (cid:71)(cid:1263)(cid:81)(cid:74)(cid:15)
(cid:81)(cid:74)(cid:1133)(cid:1255)(cid:70) (cid:79)(cid:1189)(cid:76) quay (cid:79)(cid:1189)(cid:76) B2.
10
10
10
9
9
9
8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
46
23
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
3. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:39)(cid:44)(cid:36)(cid:49)(cid:36)(cid:3)(cid:11)(cid:39)(cid:76)(cid:89)(cid:76)(cid:86)(cid:76)(cid:89)(cid:72)(cid:3)(cid:36)(cid:81)(cid:68)(cid:79)(cid:92)(cid:86)(cid:76)(cid:86)(cid:12)(cid:29)
B1: (cid:55)(cid:1193)(cid:87) (cid:70)(cid:1191) các (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) là (cid:80)(cid:1245)(cid:87) nhóm.
B2 : Chia (cid:81)(cid:75)(cid:871) nhóm có (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:903)(cid:68) (cid:81)(cid:75)(cid:903)(cid:81)(cid:74)
(cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) trong nhóm là (cid:79)(cid:883)(cid:81) (cid:81)(cid:75)(cid:829)(cid:87).
B3 : (cid:49)(cid:1219)(cid:88) (cid:80)(cid:1243)(cid:76) nhóm (cid:70)(cid:75)(cid:1229) (cid:70)(cid:75)(cid:1261)(cid:68) 1 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) thì
(cid:71)(cid:1263)(cid:81)(cid:74)(cid:15) (cid:81)(cid:74)(cid:1133)(cid:1255)(cid:70) (cid:79)(cid:1189)(cid:76) quay (cid:79)(cid:1189)(cid:76) B2.
10
10
10
9
9
9
8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
47
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:264)(cid:76)(cid:1223)(cid:80) (cid:55)(cid:1233)(cid:68)(cid:3)(cid:255)(cid:1245)(cid:3)(cid:91) (cid:55)(cid:1233)(cid:68)(cid:3)(cid:255)(cid:1245)(cid:3)(cid:92)
P1
0.40
0.53
P2
0.22
0.38
P3
0.353
0.32
P4
0.26
0.19
P5
0.08
0.41
P6
0.45
0.30
(cid:122) Cho (cid:87)(cid:1201)(cid:83) DL (cid:74)(cid:1239)(cid:80) 6
(cid:255)(cid:76)(cid:1223)(cid:80) trong không
gian 2 (cid:70)(cid:75)(cid:76)(cid:1221)(cid:88). (cid:54)(cid:1265)
toán
(cid:71)(cid:1257)(cid:81)(cid:74)
(cid:87)(cid:75)(cid:88)(cid:1201)(cid:87)
AGNES (cid:89)(cid:1247)(cid:76) Single
link
(cid:11)(cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách
(cid:74)(cid:1195)(cid:81) (cid:81)(cid:75)(cid:1193)(cid:87) (cid:74)(cid:76)(cid:1267)(cid:68) 2
(cid:255)(cid:76)(cid:1223)(cid:80) (cid:70)(cid:1259)(cid:68) 2 nhóm
khác nhau) (cid:255)(cid:1223) gom
nhóm
48
24
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:122) Xây (cid:71)(cid:1269)(cid:81)(cid:74) ma (cid:87)(cid:85)(cid:1201)(cid:81) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:11)(cid:255)(cid:1245) (cid:255)(cid:82) Euclide)
(cid:74)(cid:76)(cid:1267)(cid:68) các (cid:255)(cid:76)(cid:1223)(cid:80)
P1 P2 P3 P4 P5 P6
0.00 0.23 0.22 0.37 0.34 0.24
P1
0.23 0.00 0.15 0.19 0.14 0.24
P2
0.22 0.15 0.00 0.16 0.29 0.10
P3
0.37 0.19 0.16 0.00 0.28 0.22
P4
0.34 0.14 0.29 0.28 0.00 0.39
P5
0.24 0.24 0.10 0.22 0.39 0.00
P6
49
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) Single Link :
1. (cid:37)(cid:1133)(cid:1247)(cid:70) 1 : (cid:80)(cid:1243)(cid:76) (cid:255)(cid:76)(cid:1223)(cid:80) là (cid:80)(cid:1245)(cid:87) nhóm
2. (cid:37)(cid:1133)(cid:1247)(cid:70) 2 :
(cid:135) Thu (cid:255)(cid:1133)(cid:1255)(cid:70) các nhóm : {1}, {4}, {2}, {5}, {3,6},
(cid:135) Trong (cid:86)(cid:1237) các nhóm (cid:74)(cid:1239)(cid:80) (cid:80)(cid:1245)(cid:87) (cid:255)(cid:76)(cid:1223)(cid:80) thì dist(3,6) - min
nên (cid:74)(cid:1245)(cid:83) (cid:255)(cid:76)(cid:1223)(cid:80) P3 và P6 (cid:89)(cid:1247)(cid:76) nhau thành (cid:80)(cid:1245)(cid:87) nhóm
3. Quay (cid:79)(cid:1189)(cid:76) (cid:69)(cid:1133)(cid:1247)(cid:70) 2 do (cid:70)(cid:75)(cid:1133)(cid:68) thu (cid:255)(cid:1133)(cid:1255)(cid:70) nhóm (cid:179)(cid:87)(cid:82)(cid:106)(cid:81) (cid:69)(cid:1245)(cid:180)
4. Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) các nhóm . Ví (cid:71)(cid:1257) :
50
=min(dist(3,1),dist(6,1)) (cid:135) Dist({3,6},{1})
25
=min(0.22, 0.24) = 0.22
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) Single Link :
5. dist(2,5) là (cid:81)(cid:75)(cid:1235) (cid:81)(cid:75)(cid:1193)(cid:87) nên (cid:74)(cid:1245)(cid:83) P2 và P5. Ta có các nhóm sau : {1}, {4}, {3,6}, {2,5}
6. Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) các nhóm. Ví (cid:71)(cid:1257) :
(cid:135) dist({3,6},{2,5})
= min(dist(3,2),dist(6,2),dist(3,5),dist(6,5))
= min(0.15, 0.24, 0.28, 0.39) = 0.15
(cid:171).
51
(cid:135) Ta thu (cid:255)(cid:1133)(cid:1255)(cid:70) các nhóm : {1},{4},{2,3,5,6}
(cid:135) dist({3,6},{2,5}) (cid:81)(cid:75)(cid:1235) (cid:81)(cid:75)(cid:1193)(cid:87) nên (cid:74)(cid:1245)(cid:83) các nhóm {3,6}, {2,5} thành (cid:80)(cid:1245)(cid:87) nhóm.
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) Single Link :
7. (cid:55)(cid:76)(cid:1219)(cid:83) (cid:87)(cid:1257)(cid:70) :
(cid:135) Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) các nhóm.
(cid:135) (cid:42)(cid:1245)(cid:83) {4} (cid:89)(cid:1247)(cid:76) {2,3,5,6} thu (cid:255)(cid:1133)(cid:1255)(cid:70) các nhóm {1},
{2,3,4,5,6}
8. (cid:42)(cid:1245)(cid:83) 2 nhóm này ta thu (cid:255)(cid:1133)(cid:1255)(cid:70) nhóm (cid:179)(cid:87)(cid:82)(cid:106)(cid:81) (cid:69)(cid:1245)(cid:180)
và (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87) toán (cid:71)(cid:1263)(cid:81)(cid:74)
52
26
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
5
1
3
0.2
5
0.15
2
1
0.1
2
3
6
0.05
4
0
3
6
2
5
4
1
4
53
(cid:54)(cid:1131)(cid:3)(cid:255)(cid:1239)(cid:3)(cid:75)(cid:117)(cid:81)(cid:75)(cid:3)(cid:70)(cid:107)(cid:92) Các nhóm
(Single Link)
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
4. (cid:49)(cid:75)(cid:1133)(cid:1255)(cid:70)(cid:3)(cid:255)(cid:76)(cid:1223)(cid:80) :
Tính co dãn (cid:87)(cid:75)(cid:1193)(cid:83) : (cid:264)(cid:1245) (cid:83)(cid:75)(cid:1261)(cid:70) (cid:87)(cid:1189)(cid:83) là O(n2) (cid:89)(cid:883)(cid:76) n - (cid:86)(cid:1237) (cid:255)(cid:1237)(cid:76)
(cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74)
Không (cid:87)(cid:75)(cid:1223) quay lui (cid:89)(cid:1221) (cid:69)(cid:1133)(cid:1247)(cid:70) (cid:87)(cid:85)(cid:1133)(cid:1247)(cid:70) .
Khó xác (cid:255)(cid:1231)(cid:81)(cid:75) (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp tích (cid:87)(cid:1257) hay chia (cid:81)(cid:75)(cid:1235)
Nh(cid:1189)(cid:92) (cid:70)(cid:1191)(cid:80) (cid:89)(cid:1247)(cid:76) (cid:81)(cid:75)(cid:76)(cid:1225)(cid:88)(cid:15) cá (cid:69)(cid:76)(cid:1227)(cid:87)
(cid:42)(cid:847)(cid:83) (cid:89)(cid:829)(cid:81) (cid:255)(cid:857) khi các nhóm có kích (cid:87)(cid:75)(cid:769)(cid:883)(cid:70) khác nhau và có
hình dáng (cid:79)(cid:875)(cid:76)
Có xu (cid:75)(cid:769)(cid:883)(cid:81)(cid:74) phân chia các nhóm DL (cid:79)(cid:883)(cid:81)
(cid:190) Tích (cid:75)(cid:891)(cid:83) (cid:83)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) pháp phân (cid:70)(cid:829)(cid:83) (cid:89)(cid:883)(cid:76)
(cid:83)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) pháp phân (cid:75)(cid:82)(cid:825)(cid:70)(cid:75) (cid:11)(cid:71)(cid:905)(cid:68) trên (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74)
cách) : BIRCH, CURE, CHAMELEON
54
27
(cid:38)(cid:200)(cid:38)(cid:3)(cid:38)(cid:208)(cid:49)(cid:42)(cid:3)(cid:57)(cid:44)(cid:643)(cid:38)(cid:3)(cid:38)(cid:611)(cid:49)(cid:3)(cid:47)(cid:172)(cid:48)
1. (cid:55)(cid:75)(cid:1191)(cid:82) (cid:79)(cid:88)(cid:1201)(cid:81) và (cid:87)(cid:1269) (cid:87)(cid:75)(cid:1269)(cid:70) (cid:75)(cid:76)(cid:1227)(cid:81) các bài (cid:87)(cid:1201)(cid:83) (cid:70)(cid:1259)(cid:68)
(cid:70)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) 5 (cid:177) (cid:51)(cid:75)(cid:1195)(cid:81) 1 (không (cid:81)(cid:1245)(cid:83)(cid:12)
2. (cid:38)(cid:75)(cid:88)(cid:1197)(cid:81) (cid:69)(cid:1231) bài 5 (cid:177) (cid:51)(cid:75)(cid:1195)(cid:81) 2 : Gom nhóm (cid:71)(cid:1267) (cid:79)(cid:76)(cid:1227)(cid:88)
(cid:122) Xem (cid:81)(cid:1245)(cid:76) dung bài 5 (cid:177) P.2.
(cid:122) Cách (cid:87)(cid:75)(cid:1269)(cid:70) (cid:75)(cid:76)(cid:1227)(cid:81) :
(cid:122) (cid:264)(cid:1233)(cid:70) slide, xem các ví (cid:71)(cid:1257)
(cid:122) Tham (cid:78)(cid:75)(cid:1191)(cid:82) trên Internet và tài (cid:79)(cid:76)(cid:1227)(cid:88) tham
(cid:78)(cid:75)(cid:1191)(cid:82)
3. (cid:38)(cid:75)(cid:88)(cid:1197)(cid:81) (cid:69)(cid:1231) báo cáo xemina.
55
(cid:37)(cid:106)(cid:76)(cid:3)(cid:87)(cid:1201)(cid:83)(cid:3)(cid:70)(cid:105)(cid:3)(cid:81)(cid:75)(cid:107)(cid:81)
(cid:122) (cid:55)(cid:75)(cid:1249)(cid:76) gian : 20(cid:182)
(cid:122) Cho (cid:87)(cid:1201)(cid:83) DL (cid:74)(cid:1239)(cid:80) 6 (cid:255)(cid:76)(cid:1223)(cid:80) trong không gian 2 (cid:70)(cid:75)(cid:76)(cid:1221)(cid:88)
(cid:89)(cid:1247)(cid:76) ma (cid:87)(cid:85)(cid:1201)(cid:81) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:81)(cid:75)(cid:1133) sau.
(cid:122) (cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87)
toán AGNES (cid:89)(cid:1247)(cid:76) Complete link
(cid:11)(cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) 2 nhóm là (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách xa (cid:81)(cid:75)(cid:1193)(cid:87)
(cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:76)(cid:1223)(cid:80) (cid:70)(cid:1259)(cid:68) 2 nhóm) (cid:255)(cid:1223) gom nhóm.
(cid:122) (cid:49)(cid:881)(cid:83) bài theo nhóm.
56
28
(cid:37)(cid:106)(cid:76)(cid:3)(cid:87)(cid:1201)(cid:83)(cid:3)(cid:70)(cid:105)(cid:3)(cid:81)(cid:75)(cid:107)(cid:81)
(cid:122) Cho ma (cid:87)(cid:85)(cid:1201)(cid:81) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) các (cid:255)(cid:76)(cid:1223)(cid:80) (cid:81)(cid:75)(cid:1133) sau :
P1 P2 P3 P4 P5 P6
0.00 0.23 0.22 0.37 0.34 0.24
P1
0.23 0.00 0.15 0.19 0.14 0.24
P2
0.22 0.15 0.00 0.16 0.29 0.10
P3
0.37 0.19 0.16 0.00 0.28 0.22
P4
0.34 0.14 0.29 0.28 0.00 0.39
P5
0.24 0.24 0.10 0.22 0.39 0.00
P6
57
(cid:52)(cid:88)(cid:76)(cid:3)(cid:255)(cid:648)(cid:81)(cid:75)(cid:3)(cid:87)(cid:85)(cid:117)(cid:81)(cid:75)(cid:3)(cid:69)(cid:106)(cid:92)(cid:3)(cid:69)(cid:106)(cid:76)(cid:3)(cid:81)(cid:857)(cid:83)(cid:3)
(cid:37)(cid:106)(cid:76)(cid:3)(cid:87)(cid:1201)(cid:83)(cid:3)(cid:81)(cid:1245)(cid:83)(cid:3)(cid:70)(cid:105)(cid:3)(cid:81)(cid:75)(cid:107)(cid:81)
(cid:122) (cid:49)(cid:74)(cid:106)(cid:92)(cid:3)(cid:81)(cid:1245)(cid:83)(cid:3)(cid:29)(cid:3)
(cid:122) Tên nhóm :
(cid:122) (cid:43)(cid:1233)(cid:3)(cid:89)(cid:106)(cid:3)(cid:87)(cid:114)(cid:81)(cid:29)
(cid:122) (cid:48)(cid:109)(cid:3)(cid:86)(cid:1237)(cid:3)(cid:54)(cid:57)(cid:3)(cid:29)
(cid:122) (cid:49)(cid:1245)(cid:76)(cid:3)(cid:71)(cid:88)(cid:81)(cid:74)(cid:3)(cid:29)
(cid:122) (cid:47)(cid:769)(cid:88) ý : (cid:81)(cid:881)(cid:83) bài làm theo (cid:87)(cid:899)(cid:81)(cid:74) nhóm
58
29
(cid:55)(cid:172)(cid:44)(cid:3)(cid:47)(cid:44)(cid:1226)(cid:56)(cid:3)(cid:55)(cid:43)(cid:36)(cid:48)(cid:3)(cid:46)(cid:43)(cid:1190)(cid:50)
1. J.Han, M.Kamber, (cid:38)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) 8 (cid:177) Data mining :
Concepts and Techniques
- Introduction to Data Mining
http://www.cs.sfu.ca/~han/dmbook
http://www-
faculty.cs.uiuc.edu/~hanj/bk2/slidesindex.html : 2nd
3. P.-N. Tan, M. Steinbach, V. Kumar, (cid:38)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) 8
59
http://www-users.cs.umn.edu/~kumar/dmbook/ch8.pdf
(cid:37)(cid:172)(cid:44)(cid:3)(cid:55)(cid:1200)(cid:51)
1. Cho 2 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) : (22,1,42,10) và (20,0,36,8)
a) Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Euclide (cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74)
b) Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Mahanttan (cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74)
c) Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Minkowski (cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:89)(cid:1247)(cid:76)
q=3
2. (cid:55)(cid:75)(cid:1219) nào là gom nhóm?. Trình bày chi
(cid:87)(cid:76)(cid:1219)(cid:87)
(cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp phân (cid:75)(cid:82)(cid:1189)(cid:70)(cid:75)(cid:15) phân (cid:70)(cid:1193)(cid:83). Cho ví
(cid:71)(cid:1257) (cid:70)(cid:1257) (cid:87)(cid:75)(cid:1223) (cid:87)(cid:1263)(cid:81)(cid:74) (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp. So sánh (cid:1133)(cid:88)(cid:15)
(cid:78)(cid:75)(cid:88)(cid:92)(cid:1219)(cid:87) (cid:255)(cid:76)(cid:1223)(cid:80) (cid:70)(cid:1259)(cid:68) 2 (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp.
60
30
(cid:37)(cid:172)(cid:44)(cid:3)(cid:55)(cid:1200)(cid:51)
3.
(cid:55)(cid:68)(cid:3)(cid:70)(cid:121)(cid:3)(cid:27)(cid:3)(cid:255)(cid:1237)(cid:76)(cid:3)(cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74)(cid:3)(cid:86)(cid:68)(cid:88)(cid:3)(cid:11)(cid:69)(cid:76)(cid:1223)(cid:88)(cid:3)(cid:71)(cid:76)(cid:1225)(cid:81)(cid:3)(cid:87)(cid:75)(cid:123)(cid:81)(cid:74)(cid:3)(cid:84)(cid:88)(cid:68)(cid:3)(cid:87)(cid:1233)(cid:68)(cid:3)(cid:255)(cid:1245)(cid:3)(cid:11)(cid:91)(cid:15)(cid:92)(cid:12)(cid:12)(cid:3)(cid:29)(cid:3)A1(2,10),
A2(2,5), A3(8,4), B1(5,8), B2(7,5), B3(6,4), C1(1,2), C2(4,9).
a)
(cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Euclide và (cid:74)(cid:76)(cid:1191) (cid:86)(cid:1265) gán A1, B1, C1 là
các trung tâm (cid:70)(cid:1259)(cid:68) các nhóm (cid:87)(cid:1133)(cid:1131)(cid:81)(cid:74) (cid:1261)(cid:81)(cid:74). (cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87)
toán k-means ( (cid:89)(cid:1247)(cid:76) k=3) (cid:255)(cid:1223) xác (cid:255)(cid:1231)(cid:81)(cid:75):
(cid:177)
(cid:177)
b)
c)
61
Ba trung tâm (cid:70)(cid:1259)(cid:68) nhóm sau vòng (cid:79)(cid:1211)(cid:83) thi hành (cid:255)(cid:1195)(cid:88) tiên. Tính
(cid:255)(cid:1245) (cid:255)(cid:82) SSE cho các nhóm.
Ba nhóm (cid:78)(cid:1219)(cid:87) (cid:84)(cid:88)(cid:1191) (cid:70)(cid:88)(cid:1237)(cid:76) cùng. Tính (cid:255)(cid:1245) (cid:255)(cid:82) SSE cho các nhóm.
(cid:55)(cid:905) (cid:70)(cid:75)(cid:869)(cid:81) 3 trung tâm nhóm (cid:69)(cid:829)(cid:87) (cid:78)(cid:484) không trùng (cid:89)(cid:883)(cid:76) 8 (cid:255)(cid:873)(cid:76)
(cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:255)(cid:109) cho. (cid:54)(cid:901) (cid:71)(cid:893)(cid:81)(cid:74) k-mean (k=3) (cid:255)(cid:859) xác (cid:255)(cid:867)(cid:81)(cid:75) các
nhóm. So sánh (cid:78)(cid:855)(cid:87) (cid:84)(cid:88)(cid:827) (cid:89)(cid:883)(cid:76) câu a)
(cid:54)(cid:901) (cid:71)(cid:893)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:837)(cid:87) toán phân (cid:70)(cid:829)(cid:83) (cid:79)(cid:831)(cid:81) (cid:79)(cid:769)(cid:891)(cid:87) (cid:89)(cid:883)(cid:76) Single link và
Complete link (cid:255)(cid:859) xác (cid:255)(cid:867)(cid:81)(cid:75) 3 nhóm (cid:87)(cid:899) DL trên. (cid:57)(cid:853) (cid:86)(cid:767) (cid:255)(cid:875)
hình cây (cid:87)(cid:769)(cid:767)(cid:81)(cid:74) (cid:897)(cid:81)(cid:74)
(cid:37)(cid:172)(cid:44)(cid:3)(cid:55)(cid:1200)(cid:51)
4. Cho CSDL bên :
Customer
Age
Income
(K)
No.
cards
35
37
3
(cid:55)(cid:75)(cid:1191)(cid:82)
25
51
3
(cid:43)(cid:1133)(cid:81)(cid:74)
a) (cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) k-mean (cid:255)(cid:1223)
gom (cid:70)(cid:1257)(cid:80) (cid:89)(cid:1247)(cid:76) k =3. Tính (cid:255)(cid:1245)
(cid:255)(cid:82) SSE và so sánh (cid:78)(cid:1219)(cid:87) (cid:84)(cid:88)(cid:1191).
Gia
29
44
1
Thành
45
100
3
20
30
4
(cid:55)(cid:75)(cid:1259)(cid:92)
33
57
2
(cid:264)(cid:1261)(cid:70)
b) (cid:38)(cid:75)(cid:88)(cid:1197)(cid:81) hóa CSDL và
gom (cid:70)(cid:1257)(cid:80) (cid:89)(cid:1247)(cid:76) k =3. So sánh
(cid:78)(cid:1219)(cid:87) (cid:84)(cid:88)(cid:1191) (cid:89)(cid:1247)(cid:76) câu a).
Minh
65
200
1
Nhung
54
142
2
58
175
1
(cid:49)(cid:75)(cid:1201)(cid:87)
Tùng
25
40
5
62
31
(cid:37)(cid:106)(cid:76)(cid:3)(cid:87)(cid:1201)(cid:83)
P1
P2
P3
P4
P5
P1
0.00
0.10
0.41
0.55
0.35
P2
0.10
0.00
0.64
0.47
0.98
P3
0.41
0.64
0.00
0.44
0.85
P4
0.55
0.47
0.44
0.00
0.76
5. Cho (cid:87)(cid:1201)(cid:83) DL (cid:74)(cid:1239)(cid:80) 5
(cid:255)(cid:76)(cid:1223)(cid:80) trong
không
gian 2 (cid:70)(cid:75)(cid:76)(cid:1221)(cid:88) (cid:89)(cid:1247)(cid:76) ma
(cid:87)(cid:85)(cid:1201)(cid:81) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:255)(cid:109)
cho. (cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87)
toán AGNES (cid:79)(cid:1195)(cid:81) (cid:79)(cid:1133)(cid:1255)(cid:87)
(cid:89)(cid:1247)(cid:76) Single Link và
Complete link (cid:255)(cid:1223) gom
nhóm. (cid:57)(cid:1217) (cid:86)(cid:1131) (cid:255)(cid:1239) hình
cây.
P5
0.35
0.98
0.85
0.76
0.00
63
(cid:122) Xác (cid:255)(cid:867)(cid:81)(cid:75) 3 nhóm thu
(cid:255)(cid:769)(cid:891)(cid:70) (cid:87)(cid:899) (cid:86)(cid:767) (cid:255)(cid:875) hình
cây theo (cid:70)(cid:827) 2 cách.
Q & A
64
32
22
11
(cid:37)(cid:76)(cid:1223)(cid:88) (cid:71)(cid:76)(cid:1225)(cid:81) (cid:80)(cid:1243)(cid:76) nhóm (cid:69)(cid:1205)(cid:81)(cid:74) giá (cid:87)(cid:85)(cid:867) trung bình (cid:70)(cid:1259)(cid:68) (cid:71)(cid:1267) (cid:79)(cid:76)(cid:1227)(cid:88) trong nhóm (cid:255)(cid:121) : (cid:87)(cid:75)(cid:88)(cid:837)(cid:87) toán K-means (1967) (cid:37)(cid:76)(cid:1223)(cid:88) (cid:71)(cid:76)(cid:1225)(cid:81) nhóm (cid:69)(cid:1205)(cid:81)(cid:74) (cid:80)(cid:1245)(cid:87) (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:81)(cid:1205)(cid:80) (cid:74)(cid:1195)(cid:81) trung tâm (cid:70)(cid:1259)(cid:68) nhóm : (cid:87)(cid:75)(cid:88)(cid:837)(cid:87) toán k-medoids, PAM (1987)
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
1. (cid:46)(cid:75)(cid:105)(cid:76)(cid:3)(cid:81)(cid:76)(cid:1227)(cid:80)(cid:3)(cid:70)(cid:1131)(cid:3)(cid:69)(cid:1191)(cid:81)(cid:3)(cid:11)(cid:87)(cid:87)(cid:12)(cid:29)
K
dist 2
SSE
(
xm ), i
(cid:32)
i
Cx i
1 (cid:32) (cid:143)
Công (cid:87)(cid:75)(cid:1261)(cid:70) tính Bình (cid:83)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) sai ( Sum of Squared Error - SSE) (cid:166) (cid:166)
(cid:57)(cid:883)(cid:76) x là (cid:80)(cid:881)(cid:87) (cid:255)(cid:76)(cid:859)(cid:80) DL trong nhóm Ci và mi là (cid:255)(cid:76)(cid:859)(cid:80) (cid:255)(cid:825)(cid:76) (cid:71)(cid:76)(cid:863)(cid:81) cho nhóm (cid:11)(cid:255)(cid:76)(cid:859)(cid:80) TB nhóm (cid:75)(cid:82)(cid:847)(cid:70) (cid:255)(cid:76)(cid:859)(cid:80) trung tâm nhóm), K-(cid:86)(cid:873) nhóm. dist (): (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách Euclide
(cid:122) (cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:87)(cid:68)(cid:3)(cid:70)(cid:121)(cid:3)(cid:21)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:3)(cid:89)(cid:1247)(cid:76)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:87)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:1261)(cid:81)(cid:74)(cid:3)
23
(cid:122) SSE = 12+0+0+62+82+162+262+72+212 =1523
m1=3, m2=4 (cid:122) K1={2,3}, K2={4,10,12,20,30,11,25}
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
2. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:78)-means :
Cho (cid:86)(cid:873) k, (cid:80)(cid:879)(cid:76) nhóm (cid:255)(cid:769)(cid:891)(cid:70) (cid:69)(cid:76)(cid:859)(cid:88) (cid:71)(cid:76)(cid:861)(cid:81) (cid:69)(cid:841)(cid:81)(cid:74) giá (cid:87)(cid:85)(cid:867) TB (cid:70)(cid:895)(cid:68) DL
(cid:122)
(cid:122)
(cid:122)
trong nhóm B1: (cid:38)(cid:75)(cid:1233)(cid:81) (cid:81)(cid:74)(cid:1199)(cid:88) nhiên k (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:81)(cid:75)(cid:1133) là (cid:81)(cid:75)(cid:1267)(cid:81)(cid:74) trung tâm (cid:70)(cid:1259)(cid:68) các nhóm . B2 : Gán (cid:87)(cid:899)(cid:81)(cid:74) (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) còn (cid:79)(cid:825)(cid:76) vào nhóm có trung tâm nhóm (cid:74)(cid:831)(cid:81) nó (cid:81)(cid:75)(cid:829)(cid:87) (cid:11)(cid:71)(cid:905)(cid:68) trên (cid:255)(cid:881) (cid:255)(cid:82) (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách Euclide) B3 : Tính (cid:79)(cid:1189)(cid:76) giá (cid:87)(cid:85)(cid:1231) trung tâm (cid:70)(cid:1259)(cid:68) (cid:87)(cid:1263)(cid:81)(cid:74) nhóm
(cid:122)
(cid:122)
Di (cid:70)(cid:75)(cid:88)(cid:92)(cid:1223)(cid:81) trung tâm nhóm (cid:89)(cid:1221) = giá (cid:87)(cid:85)(cid:1231) TB (cid:80)(cid:1247)(cid:76) (cid:70)(cid:1259)(cid:68) nhóm Cho nhóm Ki={ti1,ti2,(cid:171),tim}, giá (cid:87)(cid:85)(cid:867) trung bình (cid:70)(cid:895)(cid:68) nhóm là mi = (1/m)(ti1 + (cid:171) + tim)
(cid:122)
B4 : (cid:49)(cid:855)(cid:88) các trung tâm nhóm không có gì thay (cid:255)(cid:877)(cid:76) thì (cid:71)(cid:899)(cid:81)(cid:74)(cid:15) (cid:81)(cid:74)(cid:769)(cid:891)(cid:70) (cid:79)(cid:825)(cid:76) quay (cid:79)(cid:825)(cid:76) B2.
24
12
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:20)
k1 Y
k2
3 (cid:38)(cid:75)(cid:1233)(cid:81) trung tâm nhóm (cid:69)(cid:1193)(cid:87) (cid:78)(cid:484) : k1, k2, k3 k3
25
X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:21)
k1 Y
k2
k3 Gán (cid:87)(cid:1263)(cid:81)(cid:74) (cid:255)(cid:76)(cid:1223)(cid:80) vào nhóm có trung tâm nhóm (cid:74)(cid:1195)(cid:81) (cid:81)(cid:75)(cid:1193)(cid:87)
26
13
X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:22)
k1 k1 Y
k2
k3 k2
27
k3 (cid:70)(cid:75)(cid:88)(cid:92)(cid:1223)(cid:81) tâm nhóm (cid:255)(cid:76)(cid:1223)(cid:80) bình (cid:70)(cid:1259)(cid:68) Di trung (cid:87)(cid:1263)(cid:81)(cid:74) (cid:89)(cid:1221) trung (cid:80)(cid:1247)(cid:76) nhóm X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:23)
k1 Y
k3 (cid:42)(cid:105)(cid:81)(cid:3)(cid:79)(cid:1189)(cid:76)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3) (cid:255)(cid:76)(cid:1223)(cid:80)(cid:3)(cid:70)(cid:75)(cid:82)(cid:3)(cid:74)(cid:1195)(cid:81)(cid:3) (cid:89)(cid:1247)(cid:76)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3) (cid:87)(cid:107)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:3)(cid:80)(cid:1247)(cid:76) k2
28
14
(cid:52)(cid:29)(cid:3)(cid:38)(cid:105)(cid:70)(cid:3)(cid:255)(cid:76)(cid:843)(cid:80)(cid:3) (cid:81)(cid:106)(cid:82)(cid:3)(cid:255)(cid:753)(cid:875)(cid:70)(cid:3)(cid:74)(cid:105)(cid:81)(cid:3) (cid:79)(cid:809)(cid:76)(cid:3)(cid:34) X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:23)(cid:3)(cid:171)
k1 Y
k3
(cid:22)(cid:3)(cid:255)(cid:76)(cid:843)(cid:80)(cid:3) (cid:255)(cid:753)(cid:875)(cid:70)(cid:3) (cid:74)(cid:105)(cid:81)(cid:3)(cid:79)(cid:809)(cid:76)
k2
29
X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:23)(cid:69)
k1 Y
k3 k2
(cid:55)(cid:116)(cid:81)(cid:75)(cid:3)(cid:79)(cid:1189)(cid:76)(cid:3) trung bình nhóm
30
15
X
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:46)-(cid:80)(cid:72)(cid:68)(cid:81)(cid:86)(cid:15)(cid:3)(cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:24)
k1
Y
k2
k3
Di (cid:70)(cid:75)(cid:88)(cid:92)(cid:1223)(cid:81) tâm trung nhóm (cid:89)(cid:1221) giá (cid:87)(cid:85)(cid:1231) TB nhóm (cid:80)(cid:1247)(cid:76)(cid:15) (cid:171)
31
X
Ví d(cid:1257) : k-mean
Customer
Age Income
Income
(K)
0.55 0.175
John
0.34 0.25
Rachel
1
1
Hannah
0.93 0.85
Tom
0.39 0.2
nellie
0.58 0.25
David
Age
16
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:3)(cid:29)(cid:3)(cid:78)-mean (cid:37)(cid:1133)(cid:1247)(cid:70)(cid:3)(cid:20)(cid:29)(cid:3)(cid:38)(cid:75)(cid:1233)(cid:81)(cid:3)(cid:49)(cid:72)(cid:79)(cid:79)(cid:76)(cid:72)(cid:3)(cid:89)(cid:106)(cid:3)(cid:39)(cid:68)(cid:89)(cid:76)(cid:71)(cid:3)(cid:79)(cid:106)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:3)(cid:36)(cid:3) và B
Customer
Income
Distance from David
Distance from Nellie
0.08
0.161
John
0.24
0.07
Rachel
Hannah
0.859
1.006
B
0.694
0.845
Tom
A
Nellie
David
Age
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:29)(cid:3)k-mean
Income
(cid:37)(cid:21)(cid:3)(cid:29)(cid:3)(cid:55)(cid:116)(cid:81)(cid:75)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:80)(cid:1247)(cid:76)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:3)(cid:36)(cid:3)(cid:89)(cid:106)(cid:3)(cid:37)(cid:3)(cid:29)
(cid:55)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:38)(cid:79)(cid:88)(cid:86)(cid:87)(cid:72)(cid:85)(cid:3)(cid:36)(cid:3)(cid:29)(cid:3) (cid:122) Age 0.37, Income=0.23
B
A
(cid:55)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:38)(cid:79)(cid:88)(cid:86)(cid:87)(cid:72)(cid:85)(cid:3)(cid:37)(cid:3)(cid:29)(cid:3) (cid:122) Age 0.77, Income=0.57
Age
17
(cid:39)(cid:1269)(cid:68)(cid:3)(cid:87)(cid:85)(cid:114)(cid:81)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1257)(cid:80)(cid:3) (cid:80)(cid:1247)(cid:76)(cid:15)(cid:3)(cid:74)(cid:105)(cid:81)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:78)(cid:75)(cid:105)(cid:70)(cid:75)(cid:3)(cid:75)(cid:106)(cid:81)(cid:74)(cid:3) (cid:89)(cid:106)(cid:82)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:17)
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:29)(cid:3)(cid:78)-mean
Customer
Distance A Distance B
Income
John
Rachel
B
Hannah
0.19 0.04 1.00
0.45 0.53 0.49
Tom
A
Nellie
0.84 0.04
0.33 0.53
David
0.22
0.37
Age
(cid:57)(cid:116)(cid:3)(cid:71)(cid:1257)(cid:29)(cid:3)k-mean
Income
(cid:37)(cid:22)(cid:29)(cid:3)(cid:55)(cid:116)(cid:81)(cid:75)(cid:3)(cid:70)(cid:105)(cid:70)(cid:3)(cid:87)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:80)(cid:1247)(cid:76)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:81)(cid:75)(cid:121)(cid:80)(cid:18)(cid:70)(cid:1257)(cid:80)(cid:3)(cid:36)(cid:3)(cid:89)(cid:106)(cid:3)(cid:37)(cid:3)(cid:29)
B
(cid:55)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:38)(cid:79)(cid:88)(cid:86)(cid:87)(cid:72)(cid:85)(cid:3)(cid:36)(cid:3)(cid:29)(cid:3) (cid:122) Age 0.47, Income=0.22
(cid:122) Age 0.97, Income= 0.93
A
(cid:55)(cid:85)(cid:88)(cid:81)(cid:74)(cid:3)(cid:87)(cid:107)(cid:80)(cid:3)(cid:70)(cid:1259)(cid:68)(cid:3)(cid:38)(cid:79)(cid:88)(cid:86)(cid:87)(cid:72)(cid:85)(cid:3)(cid:37)(cid:3)(cid:29)(cid:3)
(cid:122) (cid:57)(cid:883)(cid:76) các trung tâm nhóm (cid:80)(cid:883)(cid:76) này, thành (cid:83)(cid:75)(cid:831)(cid:81) (cid:70)(cid:895)(cid:68) các nhóm không thay (cid:255)(cid:877)(cid:76).
(cid:122) (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87) toán (cid:71)(cid:1263)(cid:81)(cid:74).
Age
18
(cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:46)-means
(cid:1132)(cid:88) (cid:255)(cid:76)(cid:1223)(cid:80) : (cid:122) (cid:264)(cid:1131)(cid:81) (cid:74)(cid:76)(cid:1191)(cid:81)(cid:15) (cid:71)(cid:1225) (cid:75)(cid:76)(cid:1223)(cid:88)(cid:15) (cid:87)(cid:1133)(cid:1131)(cid:81)(cid:74) (cid:255)(cid:1237)(cid:76) (cid:75)(cid:76)(cid:1227)(cid:88) (cid:84)(cid:88)(cid:1191). (cid:122) Các (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:87)(cid:905) (cid:255)(cid:881)(cid:81)(cid:74) gán vào các
nhóm.
(cid:122) (cid:55)(cid:75)(cid:1133)(cid:1249)(cid:81)(cid:74) (cid:255)(cid:1189)(cid:87) (cid:255)(cid:1133)(cid:1255)(cid:70) (cid:87)(cid:1237)(cid:76) (cid:1133)(cid:88) (cid:70)(cid:1257)(cid:70) (cid:69)(cid:1245).
37
(cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:46)-means (cid:49)(cid:75)(cid:1133)(cid:1255)(cid:70) (cid:255)(cid:76)(cid:1223)(cid:80) : (cid:122) (cid:55)(cid:75)(cid:88)(cid:1245)(cid:70) tính phi (cid:86)(cid:1237) ? (cid:122) (cid:38)(cid:831)(cid:81) xác (cid:255)(cid:867)(cid:81)(cid:75) (cid:86)(cid:873) nhóm (k) (cid:87)(cid:85)(cid:769)(cid:883)(cid:70) (cid:122) (cid:55)(cid:1193)(cid:87) (cid:70)(cid:1191) các (cid:255)(cid:1237)(cid:76)
(cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:83)(cid:75)(cid:1191)(cid:76) gán vào các
nhóm
(cid:122) (cid:51)(cid:75)(cid:1257) (cid:87)(cid:75)(cid:88)(cid:1245)(cid:70) vào (cid:89)(cid:76)(cid:1227)(cid:70) (cid:70)(cid:75)(cid:1233)(cid:81) các nhóm (cid:255)(cid:1195)(cid:88) tiên (cid:122) (cid:42)(cid:1211)(cid:83) (cid:89)(cid:1193)(cid:81) (cid:255)(cid:1221) khi các nhóm có kích (cid:87)(cid:75)(cid:1133)(cid:1247)(cid:70)(cid:15) (cid:80)(cid:1201)(cid:87) (cid:255)(cid:1245) khác nhau (cid:75)(cid:82)(cid:1211)(cid:70) hình dáng không (cid:83)(cid:75)(cid:1191)(cid:76) là hình (cid:70)(cid:1195)(cid:88)
(cid:122) (cid:49)(cid:75)(cid:825)(cid:92) (cid:70)(cid:827)(cid:80) (cid:89)(cid:883)(cid:76) DL (cid:81)(cid:75)(cid:76)(cid:861)(cid:88)(cid:15) cá (cid:69)(cid:76)(cid:863)(cid:87)
38
19
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
3. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:78)-medoids : PAM
Cho (cid:86)(cid:873) k, (cid:80)(cid:879)(cid:76) nhóm (cid:255)(cid:769)(cid:891)(cid:70) (cid:69)(cid:76)(cid:859)(cid:88) (cid:71)(cid:76)(cid:861)(cid:81) (cid:69)(cid:841)(cid:81)(cid:74) (cid:80)(cid:881)(cid:87) trong các (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:74)(cid:1195)(cid:81) trung tâm nhóm (cid:81)(cid:75)(cid:829)(cid:87)
(cid:122) B1: (cid:38)(cid:75)(cid:1233)(cid:81) (cid:81)(cid:74)(cid:1199)(cid:88) nhiên k (cid:255)(cid:1237)(cid:76)
(cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:81)(cid:75)(cid:1133) là
(cid:81)(cid:75)(cid:1267)(cid:81)(cid:74) (cid:87)(cid:85)(cid:869)(cid:81)(cid:74) tâm (cid:70)(cid:1259)(cid:68) các nhóm .
(cid:122) B2 : gán (cid:87)(cid:899)(cid:81)(cid:74) (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) còn (cid:79)(cid:825)(cid:76) vào nhóm có
(cid:87)(cid:85)(cid:869)(cid:81)(cid:74) tâm (cid:70)(cid:893)(cid:80) (cid:74)(cid:831)(cid:81) nó (cid:81)(cid:75)(cid:829)(cid:87) .
(cid:122) B3 : (cid:38)(cid:75)(cid:1233)(cid:81) (cid:80)(cid:1245)(cid:87) (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:69)(cid:1193)(cid:87) (cid:78)(cid:484). Hoán (cid:255)(cid:1241)(cid:76) nó (cid:89)(cid:1247)(cid:76) (cid:87)(cid:85)(cid:1233)(cid:81)(cid:74) tâm (cid:70)(cid:1259)(cid:68) nhóm. (cid:49)(cid:1219)(cid:88) (cid:70)(cid:75)(cid:1193)(cid:87) (cid:79)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:70)(cid:1259)(cid:68) các nhóm (cid:87)(cid:259)(cid:81)(cid:74) lên thì quay (cid:79)(cid:1189)(cid:76) B2. (cid:49)(cid:74)(cid:1133)(cid:1255)(cid:70) (cid:79)(cid:1189)(cid:76) (cid:87)(cid:76)(cid:1219)(cid:83) (cid:87)(cid:1257)(cid:70) (cid:87)(cid:75)(cid:1269)(cid:70) (cid:75)(cid:76)(cid:1227)(cid:81) B3 cho (cid:255)(cid:1219)(cid:81) khi không còn có thay (cid:255)(cid:1241)(cid:76).
39
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:43)(cid:50)(cid:1188)(cid:38)(cid:43)
3. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:78)-medoids (tt):
(cid:49)(cid:75)(cid:837)(cid:81) xét : (cid:122) (cid:55)(cid:75)(cid:88)(cid:837)(cid:87) toán PAM (cid:75)(cid:76)(cid:863)(cid:88) (cid:84)(cid:88)(cid:827) (cid:75)(cid:767)(cid:81) so (cid:89)(cid:883)(cid:76) k-means
khi có (cid:80)(cid:847)(cid:87) DL (cid:81)(cid:75)(cid:76)(cid:861)(cid:88)(cid:15) cá (cid:69)(cid:76)(cid:863)(cid:87).
(cid:122) PAM (cid:75)(cid:76)(cid:1227)(cid:88) (cid:84)(cid:88)(cid:1191) (cid:89)(cid:1247)(cid:76) (cid:87)(cid:1201)(cid:83) DL (cid:81)(cid:75)(cid:1235) (cid:81)(cid:75)(cid:1133)(cid:81)(cid:74) không co
dãn (cid:87)(cid:1237)(cid:87) (cid:89)(cid:1247)(cid:76) (cid:87)(cid:1201)(cid:83) DL (cid:79)(cid:1247)(cid:81)
(cid:122) Phát (cid:87)(cid:85)(cid:76)(cid:859)(cid:81) :
(cid:122)
(cid:122)
40
20
CLARA (Clustering LARge Applications) : (cid:71)(cid:1269)(cid:68) trên (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp (cid:79)(cid:1193)(cid:92) (cid:80)(cid:1199)(cid:88) (1990) CLARANS(Clustering LARge Application based upon RANdomized Search) : (cid:79)(cid:1193)(cid:92) (cid:80)(cid:1199)(cid:88) (cid:255)(cid:1245)(cid:81)(cid:74) (1994)
N(cid:1244)I DUNG
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88) 2. (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:83)(cid:75)(cid:105)(cid:83)(cid:3)(cid:83)(cid:75)(cid:107)(cid:81)(cid:3)(cid:75)(cid:82)(cid:1189)(cid:70)(cid:75) 3. (cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74)(cid:3)(cid:83)(cid:75)(cid:105)(cid:83)(cid:3)(cid:83)(cid:75)(cid:107)(cid:81)(cid:3)(cid:70)(cid:1193)(cid:83)
41
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88)(cid:3)(cid:29)
(cid:51)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp phân (cid:70)(cid:1193)(cid:83) : xây (cid:71)(cid:1269)(cid:81)(cid:74) các nhóm và (cid:87)(cid:1241) (cid:70)(cid:75)(cid:1261)(cid:70) (cid:81)(cid:75)(cid:1133) cây phân (cid:70)(cid:1193)(cid:83). (cid:37)(cid:76)(cid:1223)(cid:88) (cid:71)(cid:76)(cid:1225)(cid:81) (cid:71)(cid:1133)(cid:1247)(cid:76) (cid:71)(cid:1189)(cid:81)(cid:74) (cid:86)(cid:1131) (cid:255)(cid:1239) hình cây (dendrogram): (cid:79)(cid:1133)(cid:88) (cid:79)(cid:1189)(cid:76) quá trình gom (cid:79)(cid:1189)(cid:76) / phân chia nhóm
5
6
0.2
4
3
4
0.15
2
5
2
0.1
1
0.05
1
3
0
42
1
3
2
5
4
6
21
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88)(cid:3)(cid:11)(cid:87)(cid:87)(cid:12)(cid:29)
Không (cid:70)(cid:831)(cid:81) xác (cid:255)(cid:867)(cid:81)(cid:75) (cid:87)(cid:85)(cid:769)(cid:883)(cid:70) (cid:86)(cid:873) nhóm k.
Xác (cid:255)(cid:867)(cid:81)(cid:75) (cid:86)(cid:873) nhóm (cid:70)(cid:831)(cid:81) (cid:87)(cid:75)(cid:76)(cid:855)(cid:87) (cid:69)(cid:841)(cid:81)(cid:74) (cid:89)(cid:76)(cid:863)(cid:70) (cid:70)(cid:839)(cid:87) ngang (cid:86)(cid:767) (cid:255)(cid:875) hình cây (cid:87)(cid:825)(cid:76) (cid:80)(cid:897)(cid:70) thích (cid:75)(cid:891)(cid:83).
Hai (cid:79)(cid:82)(cid:1189)(cid:76) phân (cid:70)(cid:1193)(cid:83) chính :
Tích (cid:87)(cid:1257) : (cid:87)(cid:1263) (cid:71)(cid:1133)(cid:1247)(cid:76) lên trên, (cid:80)(cid:1243)(cid:76) (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) là (cid:80)(cid:1245)(cid:87) nhóm Chia (cid:81)(cid:75)(cid:1235) : (cid:87)(cid:1263) trên (cid:91)(cid:88)(cid:1237)(cid:81)(cid:74)(cid:15) (cid:87)(cid:1193)(cid:87) (cid:70)(cid:1191) các (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) là 1 nhóm
43
(cid:55)(cid:75)(cid:88)(cid:837)(cid:87) toán :
AGNES, DIANA BIRCH (Balance Iterative Reducing & Clustering using Hierachies) CURE (Clustering Using Representative) ROCK (Robust Clustering using linKs) CHAMELEON
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
1. (cid:42)(cid:76)(cid:1247)(cid:76)(cid:3)(cid:87)(cid:75)(cid:76)(cid:1227)(cid:88)(cid:3)(cid:11)(cid:87)(cid:87)(cid:12)(cid:29)
Cách xác (cid:255)(cid:867)(cid:81)(cid:75) (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:903)(cid:68) các nhóm :
Single Link : (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách (cid:74)(cid:831)(cid:81) (cid:81)(cid:75)(cid:829)(cid:87) (cid:74)(cid:76)(cid:903)(cid:68) hai (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:881)(cid:70) hai nhóm
Complete Link : (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách xa (cid:81)(cid:75)(cid:829)(cid:87) (cid:74)(cid:76)(cid:903)(cid:68) hai (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:881)(cid:70) hai nhóm
44
22
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
Step 1
Step 2
Step 3
Step 4
Step 0
(cid:55)(cid:116)(cid:70)(cid:75)(cid:3)(cid:87)(cid:1257) (agglomerative)
a
a b
b
a b c d e
c
c d e
d
d e
e
(cid:38)(cid:75)(cid:76)(cid:68)(cid:3)(cid:81)(cid:75)(cid:1235) (divisive)
45
Step 3
Step 2
Step 1
Step 0
Step 4
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
2. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)(cid:3)(cid:11)(cid:36)(cid:74)(cid:74)(cid:79)(cid:82)(cid:80)(cid:72)(cid:85)(cid:68)(cid:87)(cid:76)(cid:89)(cid:72)(cid:3)
Nesting):
B1: (cid:48)(cid:1243)(cid:76) (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) là (cid:80)(cid:1245)(cid:87) nhóm. B2: (cid:43)(cid:891)(cid:83) (cid:81)(cid:75)(cid:829)(cid:87) các nhóm có (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:903)(cid:68) các nhóm là (cid:81)(cid:75)(cid:871) (cid:81)(cid:75)(cid:829)(cid:87) (Single Link/ Complete Link) B3 : (cid:49)(cid:1219)(cid:88) thu (cid:255)(cid:1133)(cid:1255)(cid:70) nhóm (cid:179)(cid:87)(cid:82)(cid:106)(cid:81) (cid:69)(cid:1245)(cid:180) thì (cid:71)(cid:1263)(cid:81)(cid:74)(cid:15) (cid:81)(cid:74)(cid:1133)(cid:1255)(cid:70) (cid:79)(cid:1189)(cid:76) quay (cid:79)(cid:1189)(cid:76) B2.
10
10
10
9
9
9
8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
46
23
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
3. (cid:55)(cid:75)(cid:88)(cid:1201)(cid:87)(cid:3)(cid:87)(cid:82)(cid:105)(cid:81)(cid:3)(cid:39)(cid:44)(cid:36)(cid:49)(cid:36)(cid:3)(cid:11)(cid:39)(cid:76)(cid:89)(cid:76)(cid:86)(cid:76)(cid:89)(cid:72)(cid:3)(cid:36)(cid:81)(cid:68)(cid:79)(cid:92)(cid:86)(cid:76)(cid:86)(cid:12)(cid:29)
B1: (cid:55)(cid:1193)(cid:87) (cid:70)(cid:1191) các (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) là (cid:80)(cid:1245)(cid:87) nhóm. B2 : Chia (cid:81)(cid:75)(cid:871) nhóm có (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:903)(cid:68) (cid:81)(cid:75)(cid:903)(cid:81)(cid:74) (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) trong nhóm là (cid:79)(cid:883)(cid:81) (cid:81)(cid:75)(cid:829)(cid:87). B3 : (cid:49)(cid:1219)(cid:88) (cid:80)(cid:1243)(cid:76) nhóm (cid:70)(cid:75)(cid:1229) (cid:70)(cid:75)(cid:1261)(cid:68) 1 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) thì (cid:71)(cid:1263)(cid:81)(cid:74)(cid:15) (cid:81)(cid:74)(cid:1133)(cid:1255)(cid:70) (cid:79)(cid:1189)(cid:76) quay (cid:79)(cid:1189)(cid:76) B2.
10
10
10
9
9
9
8
8
8
7
7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1
1
0
0
0
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9
10
47
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:264)(cid:76)(cid:1223)(cid:80) (cid:55)(cid:1233)(cid:68)(cid:3)(cid:255)(cid:1245)(cid:3)(cid:91) (cid:55)(cid:1233)(cid:68)(cid:3)(cid:255)(cid:1245)(cid:3)(cid:92)
P1
0.40
0.53
P2
0.22
0.38
P3
0.353
0.32
P4
0.26
0.19
P5
0.08
0.41
P6
0.45
0.30
(cid:122) Cho (cid:87)(cid:1201)(cid:83) DL (cid:74)(cid:1239)(cid:80) 6 (cid:255)(cid:76)(cid:1223)(cid:80) trong không gian 2 (cid:70)(cid:75)(cid:76)(cid:1221)(cid:88). (cid:54)(cid:1265) toán (cid:71)(cid:1257)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87) AGNES (cid:89)(cid:1247)(cid:76) Single link (cid:11)(cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:1195)(cid:81) (cid:81)(cid:75)(cid:1193)(cid:87) (cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:76)(cid:1223)(cid:80) (cid:70)(cid:1259)(cid:68) 2 nhóm khác nhau) (cid:255)(cid:1223) gom nhóm
48
24
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:122) Xây (cid:71)(cid:1269)(cid:81)(cid:74) ma (cid:87)(cid:85)(cid:1201)(cid:81) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:11)(cid:255)(cid:1245) (cid:255)(cid:82) Euclide)
(cid:74)(cid:76)(cid:1267)(cid:68) các (cid:255)(cid:76)(cid:1223)(cid:80)
P1 P2 P3 P4 P5 P6
0.00 0.23 0.22 0.37 0.34 0.24
P1
0.23 0.00 0.15 0.19 0.14 0.24
P2
0.22 0.15 0.00 0.16 0.29 0.10
P3
0.37 0.19 0.16 0.00 0.28 0.22
P4
0.34 0.14 0.29 0.28 0.00 0.39
P5
0.24 0.24 0.10 0.22 0.39 0.00
P6
49
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) Single Link :
1. (cid:37)(cid:1133)(cid:1247)(cid:70) 1 : (cid:80)(cid:1243)(cid:76) (cid:255)(cid:76)(cid:1223)(cid:80) là (cid:80)(cid:1245)(cid:87) nhóm
2. (cid:37)(cid:1133)(cid:1247)(cid:70) 2 :
(cid:135) Thu (cid:255)(cid:1133)(cid:1255)(cid:70) các nhóm : {1}, {4}, {2}, {5}, {3,6},
(cid:135) Trong (cid:86)(cid:1237) các nhóm (cid:74)(cid:1239)(cid:80) (cid:80)(cid:1245)(cid:87) (cid:255)(cid:76)(cid:1223)(cid:80) thì dist(3,6) - min nên (cid:74)(cid:1245)(cid:83) (cid:255)(cid:76)(cid:1223)(cid:80) P3 và P6 (cid:89)(cid:1247)(cid:76) nhau thành (cid:80)(cid:1245)(cid:87) nhóm
3. Quay (cid:79)(cid:1189)(cid:76) (cid:69)(cid:1133)(cid:1247)(cid:70) 2 do (cid:70)(cid:75)(cid:1133)(cid:68) thu (cid:255)(cid:1133)(cid:1255)(cid:70) nhóm (cid:179)(cid:87)(cid:82)(cid:106)(cid:81) (cid:69)(cid:1245)(cid:180)
4. Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) các nhóm . Ví (cid:71)(cid:1257) :
50
=min(dist(3,1),dist(6,1)) (cid:135) Dist({3,6},{1})
25
=min(0.22, 0.24) = 0.22
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) Single Link :
5. dist(2,5) là (cid:81)(cid:75)(cid:1235) (cid:81)(cid:75)(cid:1193)(cid:87) nên (cid:74)(cid:1245)(cid:83) P2 và P5. Ta có các nhóm sau : {1}, {4}, {3,6}, {2,5}
6. Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) các nhóm. Ví (cid:71)(cid:1257) :
(cid:135) dist({3,6},{2,5})
= min(dist(3,2),dist(6,2),dist(3,5),dist(6,5)) = min(0.15, 0.24, 0.28, 0.39) = 0.15
(cid:171).
51
(cid:135) Ta thu (cid:255)(cid:1133)(cid:1255)(cid:70) các nhóm : {1},{4},{2,3,5,6}
(cid:135) dist({3,6},{2,5}) (cid:81)(cid:75)(cid:1235) (cid:81)(cid:75)(cid:1193)(cid:87) nên (cid:74)(cid:1245)(cid:83) các nhóm {3,6}, {2,5} thành (cid:80)(cid:1245)(cid:87) nhóm.
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
(cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) Single Link :
7. (cid:55)(cid:76)(cid:1219)(cid:83) (cid:87)(cid:1257)(cid:70) :
(cid:135) Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) các nhóm.
(cid:135) (cid:42)(cid:1245)(cid:83) {4} (cid:89)(cid:1247)(cid:76) {2,3,5,6} thu (cid:255)(cid:1133)(cid:1255)(cid:70) các nhóm {1},
{2,3,4,5,6}
8. (cid:42)(cid:1245)(cid:83) 2 nhóm này ta thu (cid:255)(cid:1133)(cid:1255)(cid:70) nhóm (cid:179)(cid:87)(cid:82)(cid:106)(cid:81) (cid:69)(cid:1245)(cid:180)
và (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87) toán (cid:71)(cid:1263)(cid:81)(cid:74)
52
26
(cid:57)(cid:203)(cid:3)(cid:39)(cid:1256)(cid:3)(cid:29)(cid:3)(cid:55)(cid:43)(cid:56)(cid:1200)(cid:55)(cid:3)(cid:55)(cid:50)(cid:200)(cid:49)(cid:3)(cid:36)(cid:42)(cid:49)(cid:40)(cid:54)
5
1
3
0.2
5
0.15
2
1
0.1
2
3
6
0.05
4
0
3
6
2
5
4
1
4
53
(cid:54)(cid:1131)(cid:3)(cid:255)(cid:1239)(cid:3)(cid:75)(cid:117)(cid:81)(cid:75)(cid:3)(cid:70)(cid:107)(cid:92) Các nhóm
(Single Link)
(cid:51)(cid:43)(cid:1132)(cid:1130)(cid:49)(cid:42)(cid:3)(cid:51)(cid:43)(cid:200)(cid:51)(cid:3)(cid:51)(cid:43)(cid:198)(cid:49)(cid:3)(cid:38)(cid:1192)(cid:51)
4. (cid:49)(cid:75)(cid:1133)(cid:1255)(cid:70)(cid:3)(cid:255)(cid:76)(cid:1223)(cid:80) :
Tính co dãn (cid:87)(cid:75)(cid:1193)(cid:83) : (cid:264)(cid:1245) (cid:83)(cid:75)(cid:1261)(cid:70) (cid:87)(cid:1189)(cid:83) là O(n2) (cid:89)(cid:883)(cid:76) n - (cid:86)(cid:1237) (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) Không (cid:87)(cid:75)(cid:1223) quay lui (cid:89)(cid:1221) (cid:69)(cid:1133)(cid:1247)(cid:70) (cid:87)(cid:85)(cid:1133)(cid:1247)(cid:70) . Khó xác (cid:255)(cid:1231)(cid:81)(cid:75) (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp tích (cid:87)(cid:1257) hay chia (cid:81)(cid:75)(cid:1235) Nh(cid:1189)(cid:92) (cid:70)(cid:1191)(cid:80) (cid:89)(cid:1247)(cid:76) (cid:81)(cid:75)(cid:76)(cid:1225)(cid:88)(cid:15) cá (cid:69)(cid:76)(cid:1227)(cid:87) (cid:42)(cid:847)(cid:83) (cid:89)(cid:829)(cid:81) (cid:255)(cid:857) khi các nhóm có kích (cid:87)(cid:75)(cid:769)(cid:883)(cid:70) khác nhau và có hình dáng (cid:79)(cid:875)(cid:76) Có xu (cid:75)(cid:769)(cid:883)(cid:81)(cid:74) phân chia các nhóm DL (cid:79)(cid:883)(cid:81)
(cid:190) Tích (cid:75)(cid:891)(cid:83) (cid:83)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) pháp phân (cid:70)(cid:829)(cid:83) (cid:89)(cid:883)(cid:76) (cid:83)(cid:75)(cid:769)(cid:767)(cid:81)(cid:74) pháp phân (cid:75)(cid:82)(cid:825)(cid:70)(cid:75) (cid:11)(cid:71)(cid:905)(cid:68) trên (cid:78)(cid:75)(cid:82)(cid:827)(cid:81)(cid:74) cách) : BIRCH, CURE, CHAMELEON
54
27
(cid:38)(cid:200)(cid:38)(cid:3)(cid:38)(cid:208)(cid:49)(cid:42)(cid:3)(cid:57)(cid:44)(cid:643)(cid:38)(cid:3)(cid:38)(cid:611)(cid:49)(cid:3)(cid:47)(cid:172)(cid:48)
1. (cid:55)(cid:75)(cid:1191)(cid:82) (cid:79)(cid:88)(cid:1201)(cid:81) và (cid:87)(cid:1269) (cid:87)(cid:75)(cid:1269)(cid:70) (cid:75)(cid:76)(cid:1227)(cid:81) các bài (cid:87)(cid:1201)(cid:83) (cid:70)(cid:1259)(cid:68)
(cid:70)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) 5 (cid:177) (cid:51)(cid:75)(cid:1195)(cid:81) 1 (không (cid:81)(cid:1245)(cid:83)(cid:12)
2. (cid:38)(cid:75)(cid:88)(cid:1197)(cid:81) (cid:69)(cid:1231) bài 5 (cid:177) (cid:51)(cid:75)(cid:1195)(cid:81) 2 : Gom nhóm (cid:71)(cid:1267) (cid:79)(cid:76)(cid:1227)(cid:88)
(cid:122) Xem (cid:81)(cid:1245)(cid:76) dung bài 5 (cid:177) P.2. (cid:122) Cách (cid:87)(cid:75)(cid:1269)(cid:70) (cid:75)(cid:76)(cid:1227)(cid:81) :
(cid:122) (cid:264)(cid:1233)(cid:70) slide, xem các ví (cid:71)(cid:1257) (cid:122) Tham (cid:78)(cid:75)(cid:1191)(cid:82) trên Internet và tài (cid:79)(cid:76)(cid:1227)(cid:88) tham
(cid:78)(cid:75)(cid:1191)(cid:82)
3. (cid:38)(cid:75)(cid:88)(cid:1197)(cid:81) (cid:69)(cid:1231) báo cáo xemina.
55
(cid:37)(cid:106)(cid:76)(cid:3)(cid:87)(cid:1201)(cid:83)(cid:3)(cid:70)(cid:105)(cid:3)(cid:81)(cid:75)(cid:107)(cid:81)
(cid:122) (cid:55)(cid:75)(cid:1249)(cid:76) gian : 20(cid:182) (cid:122) Cho (cid:87)(cid:1201)(cid:83) DL (cid:74)(cid:1239)(cid:80) 6 (cid:255)(cid:76)(cid:1223)(cid:80) trong không gian 2 (cid:70)(cid:75)(cid:76)(cid:1221)(cid:88)
(cid:89)(cid:1247)(cid:76) ma (cid:87)(cid:85)(cid:1201)(cid:81) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:81)(cid:75)(cid:1133) sau.
(cid:122) (cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87)
toán AGNES (cid:89)(cid:1247)(cid:76) Complete link (cid:11)(cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) 2 nhóm là (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách xa (cid:81)(cid:75)(cid:1193)(cid:87) (cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:76)(cid:1223)(cid:80) (cid:70)(cid:1259)(cid:68) 2 nhóm) (cid:255)(cid:1223) gom nhóm.
(cid:122) (cid:49)(cid:881)(cid:83) bài theo nhóm.
56
28
(cid:37)(cid:106)(cid:76)(cid:3)(cid:87)(cid:1201)(cid:83)(cid:3)(cid:70)(cid:105)(cid:3)(cid:81)(cid:75)(cid:107)(cid:81)
(cid:122) Cho ma (cid:87)(cid:85)(cid:1201)(cid:81) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:74)(cid:76)(cid:1267)(cid:68) các (cid:255)(cid:76)(cid:1223)(cid:80) (cid:81)(cid:75)(cid:1133) sau :
P1 P2 P3 P4 P5 P6
0.00 0.23 0.22 0.37 0.34 0.24
P1
0.23 0.00 0.15 0.19 0.14 0.24
P2
0.22 0.15 0.00 0.16 0.29 0.10
P3
0.37 0.19 0.16 0.00 0.28 0.22
P4
0.34 0.14 0.29 0.28 0.00 0.39
P5
0.24 0.24 0.10 0.22 0.39 0.00
P6
57
(cid:52)(cid:88)(cid:76)(cid:3)(cid:255)(cid:648)(cid:81)(cid:75)(cid:3)(cid:87)(cid:85)(cid:117)(cid:81)(cid:75)(cid:3)(cid:69)(cid:106)(cid:92)(cid:3)(cid:69)(cid:106)(cid:76)(cid:3)(cid:81)(cid:857)(cid:83)(cid:3)
(cid:37)(cid:106)(cid:76)(cid:3)(cid:87)(cid:1201)(cid:83)(cid:3)(cid:81)(cid:1245)(cid:83)(cid:3)(cid:70)(cid:105)(cid:3)(cid:81)(cid:75)(cid:107)(cid:81) (cid:122) (cid:49)(cid:74)(cid:106)(cid:92)(cid:3)(cid:81)(cid:1245)(cid:83)(cid:3)(cid:29)(cid:3)
(cid:122) Tên nhóm : (cid:122) (cid:43)(cid:1233)(cid:3)(cid:89)(cid:106)(cid:3)(cid:87)(cid:114)(cid:81)(cid:29) (cid:122) (cid:48)(cid:109)(cid:3)(cid:86)(cid:1237)(cid:3)(cid:54)(cid:57)(cid:3)(cid:29) (cid:122) (cid:49)(cid:1245)(cid:76)(cid:3)(cid:71)(cid:88)(cid:81)(cid:74)(cid:3)(cid:29)
(cid:122) (cid:47)(cid:769)(cid:88) ý : (cid:81)(cid:881)(cid:83) bài làm theo (cid:87)(cid:899)(cid:81)(cid:74) nhóm
58
29
(cid:55)(cid:172)(cid:44)(cid:3)(cid:47)(cid:44)(cid:1226)(cid:56)(cid:3)(cid:55)(cid:43)(cid:36)(cid:48)(cid:3)(cid:46)(cid:43)(cid:1190)(cid:50)
1. J.Han, M.Kamber, (cid:38)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) 8 (cid:177) Data mining :
Concepts and Techniques
- Introduction to Data Mining
http://www.cs.sfu.ca/~han/dmbook http://www- faculty.cs.uiuc.edu/~hanj/bk2/slidesindex.html : 2nd 3. P.-N. Tan, M. Steinbach, V. Kumar, (cid:38)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) 8
59
http://www-users.cs.umn.edu/~kumar/dmbook/ch8.pdf
(cid:37)(cid:172)(cid:44)(cid:3)(cid:55)(cid:1200)(cid:51) 1. Cho 2 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) : (22,1,42,10) và (20,0,36,8)
a) Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Euclide (cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) b) Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Mahanttan (cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) c) Tính (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Minkowski (cid:74)(cid:76)(cid:1267)(cid:68) 2 (cid:255)(cid:1237)(cid:76) (cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74) (cid:89)(cid:1247)(cid:76)
q=3
2. (cid:55)(cid:75)(cid:1219) nào là gom nhóm?. Trình bày chi
(cid:87)(cid:76)(cid:1219)(cid:87) (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp phân (cid:75)(cid:82)(cid:1189)(cid:70)(cid:75)(cid:15) phân (cid:70)(cid:1193)(cid:83). Cho ví (cid:71)(cid:1257) (cid:70)(cid:1257) (cid:87)(cid:75)(cid:1223) (cid:87)(cid:1263)(cid:81)(cid:74) (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp. So sánh (cid:1133)(cid:88)(cid:15) (cid:78)(cid:75)(cid:88)(cid:92)(cid:1219)(cid:87) (cid:255)(cid:76)(cid:1223)(cid:80) (cid:70)(cid:1259)(cid:68) 2 (cid:83)(cid:75)(cid:1133)(cid:1131)(cid:81)(cid:74) pháp.
60
30
(cid:37)(cid:172)(cid:44)(cid:3)(cid:55)(cid:1200)(cid:51)
3.
(cid:55)(cid:68)(cid:3)(cid:70)(cid:121)(cid:3)(cid:27)(cid:3)(cid:255)(cid:1237)(cid:76)(cid:3)(cid:87)(cid:1133)(cid:1255)(cid:81)(cid:74)(cid:3)(cid:86)(cid:68)(cid:88)(cid:3)(cid:11)(cid:69)(cid:76)(cid:1223)(cid:88)(cid:3)(cid:71)(cid:76)(cid:1225)(cid:81)(cid:3)(cid:87)(cid:75)(cid:123)(cid:81)(cid:74)(cid:3)(cid:84)(cid:88)(cid:68)(cid:3)(cid:87)(cid:1233)(cid:68)(cid:3)(cid:255)(cid:1245)(cid:3)(cid:11)(cid:91)(cid:15)(cid:92)(cid:12)(cid:12)(cid:3)(cid:29)(cid:3)A1(2,10), A2(2,5), A3(8,4), B1(5,8), B2(7,5), B3(6,4), C1(1,2), C2(4,9).
a)
(cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách Euclide và (cid:74)(cid:76)(cid:1191) (cid:86)(cid:1265) gán A1, B1, C1 là các trung tâm (cid:70)(cid:1259)(cid:68) các nhóm (cid:87)(cid:1133)(cid:1131)(cid:81)(cid:74) (cid:1261)(cid:81)(cid:74). (cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87) toán k-means ( (cid:89)(cid:1247)(cid:76) k=3) (cid:255)(cid:1223) xác (cid:255)(cid:1231)(cid:81)(cid:75):
(cid:177)
(cid:177)
b)
c)
61
Ba trung tâm (cid:70)(cid:1259)(cid:68) nhóm sau vòng (cid:79)(cid:1211)(cid:83) thi hành (cid:255)(cid:1195)(cid:88) tiên. Tính (cid:255)(cid:1245) (cid:255)(cid:82) SSE cho các nhóm. Ba nhóm (cid:78)(cid:1219)(cid:87) (cid:84)(cid:88)(cid:1191) (cid:70)(cid:88)(cid:1237)(cid:76) cùng. Tính (cid:255)(cid:1245) (cid:255)(cid:82) SSE cho các nhóm. (cid:55)(cid:905) (cid:70)(cid:75)(cid:869)(cid:81) 3 trung tâm nhóm (cid:69)(cid:829)(cid:87) (cid:78)(cid:484) không trùng (cid:89)(cid:883)(cid:76) 8 (cid:255)(cid:873)(cid:76) (cid:87)(cid:769)(cid:891)(cid:81)(cid:74) (cid:255)(cid:109) cho. (cid:54)(cid:901) (cid:71)(cid:893)(cid:81)(cid:74) k-mean (k=3) (cid:255)(cid:859) xác (cid:255)(cid:867)(cid:81)(cid:75) các nhóm. So sánh (cid:78)(cid:855)(cid:87) (cid:84)(cid:88)(cid:827) (cid:89)(cid:883)(cid:76) câu a) (cid:54)(cid:901) (cid:71)(cid:893)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:837)(cid:87) toán phân (cid:70)(cid:829)(cid:83) (cid:79)(cid:831)(cid:81) (cid:79)(cid:769)(cid:891)(cid:87) (cid:89)(cid:883)(cid:76) Single link và Complete link (cid:255)(cid:859) xác (cid:255)(cid:867)(cid:81)(cid:75) 3 nhóm (cid:87)(cid:899) DL trên. (cid:57)(cid:853) (cid:86)(cid:767) (cid:255)(cid:875) hình cây (cid:87)(cid:769)(cid:767)(cid:81)(cid:74) (cid:897)(cid:81)(cid:74)
(cid:37)(cid:172)(cid:44)(cid:3)(cid:55)(cid:1200)(cid:51)
4. Cho CSDL bên :
Customer
Age
Income (K)
No. cards
35
37
3
(cid:55)(cid:75)(cid:1191)(cid:82)
25
51
3
(cid:43)(cid:1133)(cid:81)(cid:74)
a) (cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) k-mean (cid:255)(cid:1223) gom (cid:70)(cid:1257)(cid:80) (cid:89)(cid:1247)(cid:76) k =3. Tính (cid:255)(cid:1245) (cid:255)(cid:82) SSE và so sánh (cid:78)(cid:1219)(cid:87) (cid:84)(cid:88)(cid:1191).
Gia
29
44
1
Thành
45
100
3
20
30
4
(cid:55)(cid:75)(cid:1259)(cid:92)
33
57
2
(cid:264)(cid:1261)(cid:70)
b) (cid:38)(cid:75)(cid:88)(cid:1197)(cid:81) hóa CSDL và gom (cid:70)(cid:1257)(cid:80) (cid:89)(cid:1247)(cid:76) k =3. So sánh (cid:78)(cid:1219)(cid:87) (cid:84)(cid:88)(cid:1191) (cid:89)(cid:1247)(cid:76) câu a).
Minh
65
200
1
Nhung
54
142
2
58
175
1
(cid:49)(cid:75)(cid:1201)(cid:87)
Tùng
25
40
5
62
31
(cid:37)(cid:106)(cid:76)(cid:3)(cid:87)(cid:1201)(cid:83)
P1
P2
P3
P4
P5
P1
0.00
0.10
0.41
0.55
0.35
P2
0.10
0.00
0.64
0.47
0.98
P3
0.41
0.64
0.00
0.44
0.85
P4
0.55
0.47
0.44
0.00
0.76
5. Cho (cid:87)(cid:1201)(cid:83) DL (cid:74)(cid:1239)(cid:80) 5 (cid:255)(cid:76)(cid:1223)(cid:80) trong không gian 2 (cid:70)(cid:75)(cid:76)(cid:1221)(cid:88) (cid:89)(cid:1247)(cid:76) ma (cid:87)(cid:85)(cid:1201)(cid:81) (cid:78)(cid:75)(cid:82)(cid:1191)(cid:81)(cid:74) cách (cid:255)(cid:109) cho. (cid:54)(cid:1265) (cid:71)(cid:1257)(cid:81)(cid:74) (cid:87)(cid:75)(cid:88)(cid:1201)(cid:87) toán AGNES (cid:79)(cid:1195)(cid:81) (cid:79)(cid:1133)(cid:1255)(cid:87) (cid:89)(cid:1247)(cid:76) Single Link và Complete link (cid:255)(cid:1223) gom nhóm. (cid:57)(cid:1217) (cid:86)(cid:1131) (cid:255)(cid:1239) hình cây.
P5
0.35
0.98
0.85
0.76
0.00
63
(cid:122) Xác (cid:255)(cid:867)(cid:81)(cid:75) 3 nhóm thu (cid:255)(cid:769)(cid:891)(cid:70) (cid:87)(cid:899) (cid:86)(cid:767) (cid:255)(cid:875) hình cây theo (cid:70)(cid:827) 2 cách.
Q & A
64
32
