Bài tập chuyên đề Datamining

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

Gom c m (clustering)

ụ

Phân tích b ng gom c m ằ ụ

ng t ự ố ượ ự

ụ

ụ ấ

 Phân tích b ng gom c m là gì ? ằ ụ  Đ i t ng t và không t ng t ươ ươ  Các lo i d li u trong phân tích b ng gom c m ằ ạ ữ ệ  Các ph ng pháp gom c m chính ươ  Các ph ng pháp phân c p ươ  Các ph ng pháp phân ho ch ạ ươ  Tóm t tắ

 Gom c mụ : Gom các đ i t

ằ ụ góc đ t ộ ự ừ ộ ệ ườ ỏ ẫ ng mà chúng ta v n ạ i trong l p, phân lo i ớ I)Phân tích b ng gom c m là gì ? nhiên là m t vi c h t s c bình th Gom c m nhìn t ệ ế ứ ụ làm và th c hi n hàng ngày ví d nh phân lo i h c sinh khá, gi ạ ọ ự đ t đai, phân lo i tài s n, phân lo i sách trong th vi n… ấ ụ ư ạ ư ệ ạ ả

ự ớ ươ ụ ụ o T ng t ươ o Không t

ố ượ ng trong các c m khác ng có cùng tính ch t hay có các tính ấ

ng d li u ữ ệ ố ượ ng khác trong cùng c m v i m t đ i t ộ ố ượ ng t v i các đ i t ố ượ ự ớ (T c là th c hi n gom các đ i t ự ệ ch t g n gi ng nhau thành nhóm) ố ạ ọ ứ ấ ầ ụ ộ ớ ể ố

ỏ i, 8-10 phân o Ví d : Phân lo i h c sinh trong m t l p theo đi m s thành 5 nhóm gi ế ữ ừ ể i, t ỏ ừ khá, trung bình khá, trung bình, y u. Nh ng h c sinh có đi m t vào nhóm gi khá, 5-6 nhóm TB, 5 tr xu ng vào nhóm y u. ở ọ 7-8 phân vào nhóm khá, 6-7 phân vào nhóm trung bình ế ố

ụ ụ ươ ủ ụ ng t ự ng đ ng còn các đ i t ng thu c các c m khác nhau s ụ ồ ộ ộ ng thu c ẽ  M c tiêu c a gom c m: ủ ng pháp phân c m d li u là nhóm các đ i M c tiêu chính c a ph ố ữ ệ ụ nhau trong t p d li u vào các c m sao cho các đ i t ng t t ố ượ ụ ậ ữ ệ ươ ượ cùng m t l p là t ươ ố ượ ộ ớ ng đ ng. không t ồ ươ

Ứ ụ ủ ụ

 ng d ng c a gom c m: o Kinh doanh: phát hi n ra nhóm khách hàng. ệ

ư Ví d Trong ti p th m ph m ị ỹ ẩ ế ụ có th phân nhóm khách hang a chu ng m ph m Hàn Qu c, nhóm khách ố ỹ ẩ ộ hang a chu ng M ph m pháp… ỹ ẩ ể ư ộ

ự ậ ạ ộ ạ ọ o Sinh h c: phân lo i đ ng, th c v t, phân lo i gen.

o Đ a lí: nh n ra các vùng đ t gi ng nhau d a vào CSDL quan sát trên trái

ự ấ ậ ố ị

đ t, phân nhóm nhà,… ấ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

ể ả ạ ả ể ớ o B o hi m: nh n d ng các nhóm công ty có chính sách b o hi m mô tô v i ậ chi phí đ n bù trung bình cao

ử ậ ạ ạ ố ị ề ị o Ho ch đ nh thành ph : nh n d ng các nhóm nhà c a theo lo i nhà, giá tr và v trí đ a lý. ạ ị ị ộ ụ ộ ậ ố ữ ệ

c ti n x lý cho các thu t toán khác ướ ề ử ậ o M t công c đ c l p đ xem xét phân b d li u ể o Làm b

ế ụ ố

 Th nào là gom c m t ng pháp t ng cao v i: t t s t o ra các c m có ch t l ố ẽ ạ ụ ấ ượ ớ

ươ ng t ng t

cao cho trong l p (intra-class) ự ớ th p gi a các l p (inter-class) ớ ự ấ ữ

gi ng nhau càng nhi u thì ch t l - M t ph ộ o T ươ o T ữ ươ o T c là nh ng đ i t ố ượ ứ ề ố ặ ầ ng cùng m t nhóm có s gi ng nhau ho c g n ự ố ng gom c m s càng cao ẽ ụ ộ ấ ượ

- ng c a k t qu gom c m ph thu c vào: ụ ụ ộ

ươ ặ ộ ả s d ng ự ử ụ ng t ự ươ Ch t l ủ ế ấ ượ o Đ đo t ng t ộ o Cài đ t đ đo t

 Các yêu c u c a gom c m trong khai phá d li u. ụ ầ ủ ữ ệ

 Scalability: Có th thay đ i kích c . ỡ ể ổ

 Kh năng làm vi c v i các lo i thu c tính khác nhau. ệ ớ ạ ả ộ

 Kh năng làm vi c v i d li u có ch a nhi u ( outliers)

 Khám phá ra các c m có hình d ng b t kì. ụ ạ ấ

ệ ớ ữ ệ ứ ễ ả

 T ng t và b t t ng t ự ữ ố ượ ự

gi a hai đ i t ươ - Không có đ nh nghĩa duy nh t v s t ng t và b t t ng t ấ ề ự ươ ng (1) ự ấ ươ ự ữ ố gi a các đ i

và b t t ng t gi a các đ i t ng tùy thu c vào ấ ươ ị ng d li u ữ ệ - Đ nh nghĩa v t ấ ượ ự ữ ố ượ ộ t ượ ị

- ng th ng đ c bi u di n qua đ đo t ế gi a đ i t ự ữ ố ượ ườ ượ ể ễ ộ

- ệ ng, m i đ đo kho ng cách ph i là m t và ph i th a các đi u ki n ề ả ả ả ộ ỏ ng t ề ươ ự o Lo i d li u kh o sát ả ạ ữ ệ ng t c n thi o Lo i t ự ầ ạ ươ ng t T /B t t ng t ự ấ ượ ươ kho ng cách d(x,y) ả Lý t ọ ộ ưở sau:

yxd ,(

0) =

yxd ,(

iff 0)

yxd ,(

)

xyd ),(

‡

zxd ),(

yxd ,(

)

zyd ),(

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

II)Lo i d li u trong phân tích c m ụ

ạ ữ ệ ế ỉ ệ

ế

, t l ứ ự ỉ ệ

 Các bi n kho ng t l ả  Bi n nh phân ị  Các bi n đ nh danh, th t ế ị  Các bi n có ki u h n h p ể ổ ợ ế  Các ki u d li u ph c t p ứ ạ ể ữ ệ

Các bi n tr kho ng (1) ị ế ả

ế ả

: Bi n tr kho ng là các phép đo liên t c c a các thang đo tuy n tính, thô. Ví ng, chi u cao, chi u ngang, chi u d c, tu i, nhi Đ nh nghĩa ị d : tr ng l ụ ọ ượ ế t. t đ th i ti ệ ộ ờ ế ụ ủ ổ ề ọ ị ề ề

 M t nhóm các đ đo kho ng cách ph bi n cho bi n t l ả ế ỉ ệ ổ ế ả theo kho ng là kho ng ả ộ ộ cách Minkowski.

j ),(

++ ...

q )|

- - -

2 j + V i i = (xi1, xi2, …, xip) và j = (xj1, xj2, …, xjp) là các đ i t q là s nguên d

ng d li u p-chi u và ớ ố ượ ữ ệ ề ng ươ ố

 N u q = 1, đ đo kho ng cách là Manhattan ế ả ộ

jid

|),(

+ |

++ | ...

-= x i 1

j 1

x i

- -

 N u q = 2, đ đo kho ng cách là kho ng cách Euclidean ế ả ả ộ

jid ),(

++ ...

2 )|

x i 1

j 1

x i

- - -

Các bi n nh phân (1) ế ị

ạ ị ỉ

 Bi n nh phân ch có hai tr ng thái là 0 hay 1  B ng contingency table cho d li u nh phân: ữ ệ ế ả ị Subject j

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

sum + ba + dc

c +

d +

sum

dbca

 H s Jaccard coefficient

Subject i

(t ng t ươ ự ấ không b t bi n, n u bi n nh phân là b t ế ế ế ấ ị ệ ố đ i x ng): ố ứ

- Bi n nh phân đ i x ng và b t đ i x ng ấ ố ứ ố ứ ế ị

n u đ ng th i các tr ng thái c a nó có t m quan ố ứ ế ộ ủ ế ạ ầ ồ ờ

o M t bi n nh phân là đ i x ng ị

ố c mã hoá là 0 ho c 1. Ví d thu c tính gi ả ượ ọ ả ư

ng t ụ ế ươ

ặ ấ ả ế ổ

c mã hoá khác nhau. V i các tính gi ng nhau b t bi n, m t h ộ ọ ộ ặ gi a các bi n nh phân đ i x ng đ ị ự ữ b t bi n, trong đó k t qu không thay đ i khi 1 ho c t ả ế ớ ự ấ ượ ố

=),( j

+ cb +++ dcba

ế tr ng nh nhau và mang cùng m t tr ng s . Do đó, không có s u tiên khi k t ự ư ư i tính có 2 tr ng qu đ a ra ph i đ ạ ớ ượ ọ c g i thái là male và female. Tính t ố ứ t c các là tính t ng t ươ ộ ệ bi n nh phân đ ế ị ế ấ ng i và j là t đ n nhi u nh t đ xác đ nh s khác nhau gi a đ i t c bi s đ ữ ố ượ ị ế ế ố ượ h s đ i sánh đ n gi n, đ c đ nh nghĩa nh sau: ơ ệ ố ố ấ ể ượ ị ự ư ề ả

-

ị ộ ế

ế ả ủ ọ

ả ạ ươ

ườ ế ả ấ ả ọ

ng t không b t bi n. V i s t ế ẩ ươ ự ớ ự ươ ế ự ươ

ấ ệ ố ấ ố

=),( j

+ cb ++ cba

c b qua khi tính toán. M t bi n nh phân là ư ố ứ n u các k t qu c a các tr ng thái không có t m quan tr ng nh không đ i x ng ạ ầ ế ng tính khi khám b nh. Theo thói quen, nhau. Ch ng h n k t qu âm tính và d ẳ ệ ế ng là k t qu ít x y ra b ng 1 chúng ta s mã hoá k t qu quan tr ng nh t, th ế ằ ẽ gi a ng t ng tính) và b ng 0 cho k t qu khác (HIV âm tính). Tính t ự ữ (HIV d ằ ả ươ ấ c g i là t không b t ng t các bi n này đ ọ ượ ế bi n, h s đ t đ n nhi u nh t là h s Jaccard trong đó s phép so sánh c bi ệ ố ượ ế ế ph đ nh coi nh không quan tr ng và do đó đ ư ế ủ ị ượ ỏ ề ọ

Ví d : B ng h s b nh nhân ồ ơ ệ ụ ả

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

Name(tên) Gender(gi Test-1 Test-2 Test-3 Test-4 iớ

Fever(ho) Cough(s tố ) tính)

M Jack Y P N N N N

F Mary Y P N P N N

M Jim Y N N N N P

Có 8 thu c tính Name, Gender, Fever, Cough, Test-1, Test-2, Test-3, Test-4 trong đó: ộ

 Gender là thu c tính nh phân đ i x ng ố ứ ộ ị

i là nh phân b t đ i x ng  Các thu c tính còn l ộ ạ ấ ố ứ ị

c gán b ng 0. Tính kho ng cách gi a các ữ ằ ả ị

Ta gán các tr Y và P b ng 1 và tr N đ ượ b nh nhân d a vào các b t đ i x ng dùng h s Jacard ta có b ng giá tr nh sau: ệ ằ ấ ố ứ ị ư ệ ố ị ự ả

Fever Cough Test-1 Test-2 Test-3 Test-4 name

0 0 0 Jack 1 0 1

0 1 0 Marry 1 0 1

0 0 0 Jim 1 1 0

+ Tính d(Jack,Marry):

• B ng d li u d ng nh phân: ữ ệ ạ ả ị

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

Marry

sum 1 0 Jack

2 1 0 2

1 0 3 4

3 sum 3 6

+ 10 ++ 102

T b ng ta có:a=2, b=0, c=1, d=3 ừ ả

D(Jack,Marry): =0.33

+ Tính:d(Jack,Jim): B ng d li u nh phân: ữ ệ ả ị

Jim

0 1 sum

Jack 1 1 2 1

3 1 4 0

4 2 6 sum

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

ừ ả

T b ng ta có : a=2, b=1, c=2, c=3 + 11 ++ 111 D(jack,jim)= =0.67

+ Tính d(jim,marry):

B ng d li u nh phân: ữ ệ ả ị

mary

0 1 sum

Jim 1 1 2 1

2 2 4 0

3 3 6 sum

b ng: a=1, b=1, c=2 t ừ ả

+ 21 ++ 211

d(jim,marry)= =0,75

ề Nh v y, theo tính toán trên Jim và Marry có kh năng m c b nh gi ng nhau nhi u ư ậ ệ ả ắ ố

nh t vì ấ

d(jim, marry)=0.75 là l n nh t. ấ ớ

Các bi n đ nh danh ( nominal variables) ế ị

ị ạ Bi n đ nh danh là m r ng c a bi n nh phân v i nhi u h n hai tr ng ế ở ộ ủ ề ế ơ ớ ị ị

Đ nh nghĩa: thái. Ví d : thu c tính màu s c: đ , vàng, xanh, l c. ụ ụ ắ ỏ ộ

Có hai ph ng pháp đ tính toán s t ng t gi a hai đ i t ng: ươ ự ươ ể ự ữ ố ượ

ng pháp 1: Đ i sánh đ n gi n v i m là s l n đ i sáng, p là t ng s các • Ph ố ầ ả ố ơ ớ ố ổ ố

ươ bi nế

=),( j

mp p

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

• Ph ng pháp 2: Dùng m t s l ươ ộ ố ượ ng l n các bi n nh phân. ế ớ ị

 T o bi n nh phân m i cho t ng tr ng thái đ nh danh. ừ ế ạ ạ ớ ị ị

: Các bi n th t ế ứ ự có th là liên t c hay r i r c ờ ạ ụ ể

 Th t c a các tr là quan tr ng, ví d h ng. ứ ự ủ ụ ạ ọ ị

kho ng nh sau:  Có th x lý nh t l ể ử ư ỉ ệ ư ả

- Thay th xế if b i h ng c a chúng ở ạ ủ

r ˛

,...,1{

}

- ánh x ph m vi c a t ng bi n vào đo n [0,1] b ng cách thay ế ủ ừ ạ ằ ạ ạ

th đ i t ế ố ượ ng i trong bi n th f b i ế ứ ở

ng pháp cho bi n t l theo ự ươ ế ỉ ệ

- Tính s khác nhau dùng các ph kho ngả

r = if if M

Các bi n thang đo t l ỉ ệ ế

Bt hay Ae-Bt.

Là các bi n có đ đo d ị ế ộ ươ ng trên thang phi tuy n, x p x thang đo mũ. ế ấ ỉ

Đ nh nghĩa: Ví d : Aeụ

Các ph ng pháp tính đ t ng t ươ ộ ươ : ự

 X lý chúng nh các bi n thang đo kho ng ư ử ế ả

 áp d ng các bi n đ i logarithmic ụ ế ổ

 X lý chúng nh d li u th t ư ữ ệ ứ ự ử liên t c ụ

 X lý chúng theo h ng nh thang đo kho ng. ư ử ả ạ

Các bi n có ki u h n h p ể ỗ ợ ế

ộ ơ ở ữ ệ ể ứ ồ ế ể ạ

M t c s d li u có th ch a đ ng th i c sáu lo i bi n. Khi đó có th dùng công th c đ ờ ả c gán tr ng đ k t h p các hi u qu : ả ể ế ợ ứ ượ ệ ọ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

)

( ij

= 1

),( j

0=f

)

( ) f ij d d

( ij

= 1

(cid:229) v i ớ n u xế if ho c xặ jf missing (cid:229)

1=f

ho c xặ if =xjf =0

 Đóng góp c a bi n f vào kho ng cách d(i,j):

tr ng h p khác ườ ợ

ủ ế ả

( =f )

ijd

if =xjf

- N u f là bi n nh phân hay đ nh danh: ị ế ế ị

( =f )

n u xế

ijd

các tr ng h p khác ườ ợ

- N u f là d a trên kho ng cách: dùng kho ng cách đ ự ế ả ả ượ c chu n hoá. ẩ

- N u f là th t

if và x lý z ử

thang đo t s tính các h ng r ứ ự ế ỉ ố ạ ả if nh thang đo kho ng ư

r = if if M

Các bi n t l

ng trên thang phi tuy n, x p x thang đo mũ ế ấ ỉ

ế ỉ ệ o Đ đo d ươ ộ Bt hay Ae-Bt ng pháp:

o Ví d Aeụ o Các ph ươ ử

ọ ố ! t ự ế ả ả ư ế ổ ụ liên t c và x lý chúng theo h ng nh thang đo ứ ự ụ ử ư ạ x lý chúng nh các bi n thang đo kho ng không ph i là l a ch n t áp d ng bi n đ i logarithmic yif = log(xif) x lý chúng nh d li u th t ư ữ ệ ử kho ng ả

ế ể ỗ ợ ạ

)

ứ ượ ể c gán tr ng đ k t h p các hi u qu : ả ể ế ợ ệ Các bi n có ki u h n h p o CSDL Có th ch a c sáu lo i bi n ế ể ứ ả o Có th dùng công th c đ ọ

p f

=

(

)

d = 1 p x f if

( ( d ij ij d ( f ) = x or 1 ij jf

if 0

missing,

jid ),( d = ij or x if

x jf

= ;0 δ(f) otherwise

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

Đóng góp c a bi n d(i,j): ế f vào kho ng cách ủ ả

( =f )

if =xjf

ijd

- N u f là bi n nh phân hay đ nh danh: ị ế ế ị

( =f )

n u xế

ijd

các tr ng h p khác ườ ợ

- N u f là d a trên kho ng cách: dùng kho ng cách đ ự ế ả ả ượ c chu n hoá. ẩ

- N u f là th t

if và x lý z ử

thang đo t s tính các h ng r ứ ự ế ỉ ố ạ ả if nh thang đo kho ng ư

r = if if M

ng đ ạ ữ ệ c xem xét a trong KPDL là không quan h => Lo i d li u ứ ạ ượ ệ

ữ ệ ư ậ ươ ữ ệ c thu ữ ệ ỗ ữ ệ ữ ệ ả ả ờ ng ti n, d li u di ệ ữ ệ ượ

World-Wide Web ng t và b t t ng t ng hoàn toàn khác nhau ng v i các lo i d th ự ườ ấ ươ ươ ự ớ ạ ữ ứ Các ki u d li u ph c t p ể ữ ệ T t c các đ i t ấ ả ố ượ ph c t p ứ ạ Ví d v lo i d li u nh v y là d li u không gian, d li u đa ph ụ ề ạ ữ ệ truy n, d li u văn b n, d li u chu i th i gian, d li u văn b n và d li u đ ữ ệ ề gom t ừ Các đ đo t ộ li u trên ệ

III. Các ph

ng pháp gom c m (clustering) chính y u

ươ

ụ

ế

 Các ph  Các ph

ng pháp phân c p ấ ng pháp d a trên phân ho ch

ươ ươ

ự

ạ

III.1 Ph ng pháp phân c p ( Hierachical methods): ươ ấ

ạ ấ ụ ả ạ

ố ượ ả ậ ở ầ ấ

ớ ng. Khác v i đ u vào và dùng ma tr n kho ng cách làm ụ ng pháp phân c p có th dùng đi u ki n d ng. Ví d : ứ ầ ố ụ ươ ụ ừ ể ề ệ ấ

Phân c p:ấ T o phân c p c m ch không ph i phân ho ch các đ i t phân ho ch, phân c p không c n s c m k ạ tiêu chu n gom c m. Trong ph ẩ s c m. ố ụ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

Cây các c mụ

ng đ c bi u di n d i d ng cây c a các c m. Trong đó: Phân c p c m th ấ ụ ườ ượ ễ ướ ạ ủ ụ ể

- Các lá c a cây bi u di n t ng đ i t ng ễ ừ ố ượ ủ ể

- Các nút trong bi u di n các c m ụ ễ ể

Có hai ph ng pháp t o cây phân c p: t i lên: ươ ấ ạ ừ trên xu ng và tù d ố ướ

Ph

ng pháp phân c p t

trên xu ng:

ươ

ấ ừ

ố

c m l n nh t ch a t t nh t thành ắ ầ ừ ụ ng. Chia c m phân bi ụ ấ ớ

B t đ u t t c các đ i t ấ các c m nh h n và ti p di n cho đ n khi có n c m tho mãn đi u ki n d ng. ứ ấ ả ế ố ượ ụ ệ ệ ừ ỏ ơ ụ ề ế ễ ả

a

a b

b

a b c d e

c

c d e

d

d e

e

ân chia- divisive divisive

PhPhân chia-

Step 3

Step 2 Step 1 Step 0

Step 4

Ph

ng pháp t

i lên:

ươ

d ừ ướ

Các b c th c hi n: ướ ự ệ

ng và l p ma tr n kho ng cách c p n. B1: T o n nhóm, m i nhóm g m m t đ i t ỗ ộ ố ượ ạ ồ ậ ậ ả ấ

B2:Tìm 2 nhóm u,v có kho ng cách nh nh t (duv) ỏ ấ ả

ệ ả ậ ậ ớ ớ

B3: G p nhóm u v i nhóm v. Ký hi u nhóm m i là (uv). L p ma tr n kho ng cách ộ m i b ng cách: ớ ằ

+ Lo i các hàng và c t t ng ng v i các nhóm u,v ộ ươ ứ ạ ớ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

ộ ộ ể ư ủ ả ộ ớ

+Thêm m t hàng và m t c t đ l u kho ng cách c a nhóm uv v i các nhóm còn l iạ

c 2 và b i các b c 3 cho đ n khi ch n đ c k nhóm thích h p nh t cho ướ ướ ọ ượ ấ ợ

B4: L p l ế bài toán ho c ch có m t nhóm duy nh t. ặ ạ ặ ấ ộ ỉ

Ph ng pháp này đ a t i bài toán nh h n : Tìm kho ng cách gi a hai nhóm ươ ư ớ ỏ ơ ữ ả

 Các ph ng pháp tính kho ng cách gi a hai nhóm là: ươ ữ ả

ng pháp k t n i đ n

ươ

ả

ắ

ế ố ơ đi u ki n ấ ừ ộ

ệ ở ề ủ m t thành viên c a

đây là kho ng cách gi a hai c m là kho ng cách ng n nh t t ụ nhóm t

ữ i thành viên c a nhóm khác. ủ

ớ

d(C1,C2) = min(drs), v i r thu c C1; s thu c C2 (*)

ớ

ộ

ng.V i kho ng cách gi a các đ i t

ng đ

c cho nh sau:

ố ượ

ượ

ữ

ớ

Ví d :ụ Cho 5 đ i t ả d(1,2) =2, d(1,3)=6, d(1,4)=10, d(1,5)=9, d(2,3)=5, d(2,4)=9, d(2,5)=8,

d(3,4)=4, d(3,5)=5, d(4,5)=3.

ma tr n kho ng cách c a 5 đ i t

ng là D nh sau:

ố ưọ

ủ

ả

ậ

0 2 6 10 9

D = 2 0 5 9 8

6 5 0 4 5

1. Ph ng pháp k t n i đ n: ươ ế ố ơ Trong ph

10 9 4 0 3

9 8 5 3 0

ự ữ ả ậ ậ

B1: Ta xây d ng 5 nhóm và l p ma tr n kho ng cách gi a 5 nhóm này là D=D1

B2: Kho ng cách gi a 2 nhóm 1 và 2 nh nh t là 2. ỏ ấ ữ ả

ẽ ậ ộ ậ ạ ậ i ma tr n

B3: Ta s g p nhóm 1 và 2 thành m t nhóm.. Khi đó ta s c p nh t l kho ng cách m i là D1 ẽ ộ ớ ả

+ xoá c t 1 và dòng 1 c a nhóm 1. Xoá c t 2 và dòng 2 c a nhóm 2. ủ ủ ộ ộ

kho ng cách c a nhom (12) đ n các ộ ộ ẻ ưư ủ ế ả

+ Đ thêm m t c t và m t dòng đ l nhóm còn l ể i ta tính theo công th c (*) . ạ ộ ứ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

D(12,3)= min(drs) v i r thu c nhóm (12), và s thu c nhóm 3. ộ ớ ộ

D(1,3)=6, d(2,3)=5. v y nên d(12,3)=5. ậ

Hoàn toàn t ng t ta tính đ c d(12,5)=8, d(12,4)=9. ươ ự ượ

Khi đó ta thu đ c ma tr n kho ng cách m i D1 là ượ ả ậ ớ

0 5 9 8

D1= 5 0 4 5

9 4 0 3

8 5 3 0

B4:

- L p l

i b c 2, kho ng cách c a nhóm 5 và nhóm 4 là nh nh t d(5,4)=3 ặ ạ ướ ủ ấ ả ỏ

c 3, Ta s g p nhóm 4 và 5 thành m t nhóm.. Khi đó ta s c p nh t l ẽ ậ ậ ạ i ộ

- L p l ẽ ộ ma tr n kho ng cách m i là D2 i b ặ ạ ướ ả ậ ớ

+ xoá c t 4 và dòng 4 c a nhóm 4. Xoá c t 5 và dòng 5 c a nhóm 5 ủ ủ ộ ộ

các kho ng cách c a nhóm (45) t ủ ả ớ ộ ộ ể ưư

+ Thêm m t dòng và m t c t đ l ộ nhóm khác. Ta tính theo công th c (*) ứ

D(45, 12)=min(drs) v i r thu c (45), s thu c (12) ộ ớ ộ

D(4,1)=10, d(4,2)=9, d(5,1)=9, d(5,2)=8.

v y d(45,12)=8. ậ

Hoàn toàn t ng t ta tính đ oc d(45,3)=4. ươ ự ự

Khi đó ta thu đ c ma tr n kho ng cách m i D2 là: ượ ả ậ ớ

0 5 8

D2 = 5 0 4

8 4 0

- L p l i b c 2: d (45,3)= 4 là nh nh t ặ ạ ướ ấ ỏ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

i b ậ c 3: ta g p nhóm (45) và nhóm 3 thành m t nhóm. C p nh t ma tr n ậ ậ ộ ộ

- L p l kho ng cách m i là D3. ặ ạ ướ ả ớ

+ Xoá dòng và c t c a nhóm (45), xoá dòng và c t c a nhóm 3 ộ ủ ộ ủ

kho ng cách c a nhóm m id này đ n các nhóm ộ ủ ế ơ

+ Thêm m t dong f và m t c t đ l ả khác ta s tính kho ng cách theo công th c (*) ộ ộ ẻ ưư ứ ẽ ả

D(345,12)= min( drs) v i r thu c (345) và s thu c(12). ộ ớ ộ

D(3,1)=6, d(3,2)=5, d(4,1)=10, d(4,2)=9, d(5,1)=9, d(5,2)=8.

v y d(345,12)=5. ậ

Ta thu đ c kho ng cách m i là D3 là: ượ ả ớ

0 5

D3= 5 0

Cu i cùng nhóm thu đ oc s là nhóm (12543) ự ẽ ố

S đ mô t các b c: ơ ồ ả ướ

12345

1 2

345

4 5

B0 B1 B2 B3 B4

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

2.Ph

ươ

ng pháp k t n i đ y đ : ế ố ầ ủ

d(C1,C2) = max(drs), v i r thu c C1; s thu c C2. ớ ộ ộ

3.Ph

ng pháp k t n i trung bình:

ươ

ế ố

ng đ

ả

ươ

ộ

ả ng kho ng m t vài thành viên c a m t nhóm này đ n m t vài thành viên

ươ ế

ủ

ộ

Kho ng cách gi a m t cluster này và m t cluster khác là t ữ ộ cách trung bình t ừ ộ c a nhóm khác. ủ

CCD

)2,1(

(

drs

)

V i r thu c C1, s thu c C2.

ộ

ớ

1 nn 21

= 1

Đánh giá:

(cid:229) (cid:229)

- Các ph ng pháp phân c p có u đi m l n là: khái ni m đ n gi n, lý thuy t t ể ả ấ

ớ c tr n tách, quy t đ nh là vĩnh c u, vì v y s các ph ế ố t. ng án khác ơ ệ ậ ố ư ế ị ươ ử ộ

ươ Khi c m đ ượ ụ c n xem xét b rút gi m. ị ầ ả

III.2 Các ph

ươ

ạ

ự ng pháp

ể ế ủ ươ ụ ng pháp phân c p: Do vi c tr n tách các c m là vĩnh c u nên ộ ng pháp phân chia c n th i gian ệ c. Các ph ươ ể ắ ử ờ ế ị ầ - Đi m y u c a ph ấ quy t đ nh sai là không th kh c ph c đ ụ ượ tính toán và không th scalable cho t p d li u l n ậ ữ ệ ớ ể

ng pháp d a trên phân ho ch ph a. Mô t ả ươ Cho m t c s d li u D ch a n đ i t ộ ơ ở ữ ệ

ng, t o phân ho ch thành t p có k c m sao cho: ố ượ ứ ạ ụ ạ ậ

- M i c m ch a ít nh t m t đ i t ng ộ ố ượ ỗ ụ ứ ấ

- M i đ i t ỗ ố ượ ng thu c v m t c m duy nh t ấ ộ ề ộ ụ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

ị ụ ạ ố ư i u hoá tiêu chu n phân ho ch đ ẩ ạ ượ c

ng pháp ươ ng pháp gom c m k-mean - Cho tr k, tìm phân ho ch có k c m sao cho t ch n.ọ b. Các ph b.1.Ph ươ ụ

Input: S các c m k c n gom và c s d li u ch a n đ i t ng. ơ ở ữ ệ ố ượ ứ ụ ầ ố

Output: k c m đã đ c gom. ụ ượ

Thu t gi c ậ ả g m 4 b i: ồ ướ

- B c1: Phân ho ch đ i t ng thành k t p con ( c m) ng u nhiên. ố ượ ướ ạ ụ ẫ ậ

ướ ủ ố ượ ụ ng trong c m) cho t ng c m ừ ụ

- B c 2: Tính các tâm ( trung bình c a các đ i t trong phân ho ch hi n hành. ạ ệ

- B c 3: Gán m i đ i t ỗ ố ượ ướ ng cho c m tâm g n nh t ấ ụ ầ

- B c 4: N u c m không có s thay đ i thì d ng, ng i quay l c 2.. ế ụ ướ ừ ự ổ c l ượ ạ i b ạ ướ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

ể

ướ

ạ ộ ủ

ể

ạ

ằ

ố

B c 2: Đ xác đ nh các đi m h t gi ng ta đi tìm to đ c a nó b ng cách tính hoành đ và ộ ị tung đ trung bình. G i (ọ

ạ ộ ủ

ể

ạ

ố

ộ 1x , 1y ), ( 2x , 2y ) là to đ c a 2 đi m h t gi ng. Ta có:

= 3.67

1x =

=5.17

1y =

= 6.75

2x =

= 4.25

2y =

+++++ 544333 6 +++++ 876541 6 +++ 8775 4 +++ 5543 4

Ví d v thu t toán k-mean, n=10, k=2 ụ ề ậ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

B c 3: Tính kho ng cách t

các centroid đ n các đi m

ướ

ả

ừ

ế

ể

STT To đ các

ả

Thu cộ c m 1ụ

Thu cộ c m 2ụ x x

x x

1 2 3 4 5 6 7 8 9

ạ ộ đi mể (5,1) (7,3) (3,4) (7,4) (4,5) (5,5) (8,5) (3,6) (4,7) (3,8)

ế Kho ng cách đ n centroid 1 (3.67, 5.17) 4.2 3.86 1.22 3.45 0.30 1.30 4.30 1.22 2.02 3,08

ế Kho ng cách đ n centroid 2 (6.75, 4.25) 3.62 1.24 3.71 0.36 2.82 1.88 1.52 4.12 3.89 5.3

x x x

c 2.

ướ

ố ượ

ụ

ổ

i b ạ ướ

B c 4: Các đ i t ng trong các c m có s thay đ i nên quay l ự B c 2: Tính to đ các đi m centroid m i ớ

ạ ộ

ướ

ể

= 3.67

1x =

+++++ 544333 6

=5.83

1y =

+++++ 876554 6

= 6.75

2x =

= 3.25

2y =

+++ 8775 4 +++ 5431 4

B c 3: Tính kho ng cách t

các centroid đ n các đi m

ướ

ả

ừ

ế

ể

STT

ả

Thu cộ c m 1ụ

Thu cộ c m 2ụ x x

x x

1 2 3 4 5 6 7 8 9 10

To đạ ộ các đi mể (5,1) (7,3) (3,4) (7,4) (4,5) (5,5) (8,5) (3,6) (4,7) (3,8)

Kho ng cách đ n ế centroid 1 (3.67, 5.17) 5.00 4.37 1.95 3.80 0.44 1.57 4.4 0.69 1.21 2.17

Kho ng cách đ n ế centroid 2 (6.75, 4.25) 2.85 0.35 3.82 0.79 2.82 2.47 2.15 4.65 4.65 6.05

x x x

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

Nh n xét: Sau khi th c hi n b

c 3 các c m không có s thay đ i nên d ng t

i đây.

ệ ướ

ự

ậ

ừ

ụ

ự

ổ

ạ

ng pháp gom c m k- means  Đi m m nh c a ph ạ ủ ể ươ ụ

ng đ i: O(nkt) v i n là s đ i t ố ố ượ ố ớ ố ầ ặ ng, k là s c m, t là s l n l p. ố ụ

- Hi u su t t ệ Thông th ng k, t << n. ấ ươ ườ

- Thu t toán này có u đi m là rõ ràng, d dàng cài đ t. ể

ễ

ậ

ặ

 Đi m y u c a ph ng pháp k- means ế ủ ể ươ

- Có th áp d ng ch khi xác đ nh đ c tr trung bình ụ ể ỉ ị ượ ị

- C n ch đ nh tr c s các c m- k. ầ ị ỉ ướ ố ụ

- Không th x lý nhi u và outliers ể ử ễ

b.1.2. Thu t toán k-medoid ậ

Input: S các c m k c n gom và c s d li u ch a n đ i t ng. ơ ở ữ ệ ố ượ ụ ứ ầ ố

Output: k c m đã đ c gom. ụ ượ

 B c 1: Ch n k đ i t

Thu t toán: ậ

 B c 2: Gán t ng đ i t

ng ng u nhiên làm tâm c a nhóm. ố ượ ướ ọ ủ ẫ

 B c 3: Ch n ng u nhiên 1 đ i t

ng còn l i vào c m có tâm g n nh t. ố ượ ướ ừ ạ ụ ầ ấ

ng không là đ i t ố ượ ướ ẫ

ng tâm, và thay m t trong ng cho ổ ố ượ ố ượ ng trong c m(gán đ i t ụ ộ ố ượ

 B c 4: N u gán tâm m i thì quay l

các tâm đó b ng nó n u nó làm thay đ i đ i t ế c m có tâm g n nh t). ụ ấ ọ ằ ầ

c 2, ng i thì d ng. ướ ế ớ i b ạ ướ c l ượ ạ ừ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

Gán mỗi đối tượng còn lại vào cụm có tâm mới

Ví d thu t toán k-medoid, n=10, k=2. ụ ậ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

ể

ọ

i vào c m có tâm g n đ i t

ạ ộ ng còn l

• B c 1: Ch n 2 đi m có to đ K1 (3,8) và K2(6,4) làm tâm c a 2 c m. ụ • B c 2: Gán t ng đ i t ng nh t. ấ ạ

ủ ố ượ

ướ ướ

ố ượ

ừ

ụ

ầ

STT

Kho ng cách đ n ế ả K1 (3,8)

Thu c c m ộ ụ k1

Thu c c m ộ ụ k2

T a đ các ọ ộ đi mể

x x

1 2 3 4 5 6 7 8 9 10

(2,6) (3,4) (3,8) (4,7) (6,2) (6,4) (7,3) (7,4) (7,6) (8,5)

2.24 4.00 0 1.41 6.71 5.00 6.40 5.66 4.47 5.83

Kho ngả cách đ nế K2(6,4) 4.47 3.00 5.00 3.61 2.00 0 1.41 1.00 2.24 2.24

x x x x x x

• B c 3: Ch n đi m (7,6) làm tâm.

ướ

ể

ọ

STT

Kho ng cách đ n ế ả K1 (3,8)

Thu c c m ộ ụ k1

Thu c c m ộ ụ k2

T a đ các ọ ộ đi mể

x x x x

1 2 3 4 5 6 7 8 9

(2,6) (3,4) (3,8) (4,7) (6,2) (6,4) (7,3) (7,4) (7,6)

2.24 4.00 0 1.41 6.71 5.00 6.40 5.66 4.47

Kho ngả cách đ n K2 ế (7,6) 5.00 4.47 4.47 3.16 4.12 2.24 3.00 2.00 0

x x x x x

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

(8,5)

5.83

1.41

ụ

ộ ng trong c m k1, k2 thay đ i. Đ i tâm (6,4) thành (7,6) t o ra m t ổ

ạ

ng v i tâm m i là (7,6). Quay l

c 2.

ướ t p đ i t ậ

• B c 4: Các đ i t ố ượ ớ ố ượ ướ

ọ

ổ i b ạ ướ ớ o B c 3: Ch n đi m (8,5) làm tâm m i ớ ể

STT

Kho ng cách đ n ế ả K1 (3,8)

Thu c c m ộ ụ k1

Thu c c m ộ ụ k2

T a đ các ọ ộ đi mể

x x x x

1 2 3 4 5 6 7 8 9 10

(2,6) (3,4) (3,8) (4,7) (6,2) (6,4) (7,3) (7,4) (7,6) (8,5)

Kho ngả cách đ n K2 ế (8,5) 6.08 5.1 5.83 4.47 3.61 2.24 2.24 1.41 1.41 0

2.24 4.00 0 1.41 6.71 5.00 6.40 5.66 4.47 5.83

x x x x x x

Nh n xét: Đ i t

ng trong c m k1, k2 không thay đ i nên d ng.

ố ượ

ậ

ừ

ụ

ổ

Bài t p chuyên đ Datamining_nhóm 2

ề

ậ

GVHD: Nguy n H ng Giang ễ

ươ

T NG K T

Ổ

Ế

ng t ng t ự ự ự ự ượ ượ

ụ ụ ụ ụ

ề ề tùy thu c vào d li u đ tùy thu c vào d li u đ c dùng và lo i t c dùng và lo i t ng t ng t ộ ộ ọ ọ ữ ệ ượ ữ ệ ượ ự ự ộ ộ ạ ươ ạ ươ ự ự

ụ ụ

 Phân tích gom c m các đôi t Phân tích gom c m các đôi t ng d a trên s t ự ươ ng d a trên s t ự ươ  Phân tích gom c m có ph m vi ng d ng to l n Phân tích gom c m có ph m vi ng d ng to l n ớ ụ ứ ạ ạ ớ ụ ứ  Có th tính đ đo t cho nhi u lo i d li u khác nhau. ng t Có th tính đ đo t ạ ữ ệ ự ươ ể ng t cho nhi u lo i d li u khác nhau. ự ươ ạ ữ ệ ể ng t Vi c l a ch n đ đo t ươ ộ ệ ự  Vi c l a ch n đ đo t ng t ươ ộ ệ ự c n tìmầc n tìmầ , ,  Các ph Các ph ươ ươ - Các ph - Các ph ng pháp gom c m ng pháp gom c m ng pháp phân c p ấ ng pháp d a trên phân ho ch ươ ươ ự ạ