Bài giảng Nhập môn khai phá dữ liệu (PGS.TS. Hà Quang Thụy)

BÀI GI NG NH P MÔN KHAI PHÁ D LI U

Ữ Ệ

Ả

Ậ

CH

NG 6. PHÂN C M D Li U

ƯƠ

Ữ Ệ

Ụ

Ộ

TR

Ạ Ọ

ƯỜ

PGS. TS. HÀ QUANG TH YỤ HÀ N I 9-2011 NG Đ I H C CÔNG NGH Ệ Đ I H C QU C GIA HÀ N I Ộ Ố Ạ Ọ

N i dung

ộ

ớ

ệ

ụ

ậ

ụ

ấ

i thi u phân c m Thu t toán phân c m k-min ụ Thu t toán phân c m phân c p ậ Gán nhãn c mụ Đánh giá phân c mụ

ụ

1. Bài toán phân c m Web  Bài toán ậ

 T p d li u D = {d ữ ệ

i}  Phân các d li u thu c D thành các c m

ữ ệ

ự

ầ

ng t ” nhau (xa nhau)

ng t ” nhau (g n nhau) ươ ự

 Đo “t

ữ ệ ươ

ụ

ộ ố ượ

d thì h ọ

ủ

i dùng l a ch n m t đ i t ườ ọ ớ d ng cùng c m v i ườ

ươ

ự ụ i dùng ng t ” theo bi u di n d li u ể

ữ ệ

ự

ễ

ữ ệ ộ  Các d li u trong m t c m: “t ộ ụ  D li u hai c m: “không t ụ ự

ươ ự

ươ ng t ” (g n) nhau ? ầ ụ N u ng  Tiên đ phân c m: ề ế cũng l a ch n các đ i t ố ượ ọ ự  Khai thác “cách ch n l a” c a ng ọ ự  Đ a ra m t s đ đo “t ộ ố ộ ư  M t s n i dung liên quan ộ ố ộ  Xây d ng đ đo t ộ ự  Khai thác thông tin b sung  S l ụ

ng c m cho tr c, s l ng c m không cho tr ng t ổ ướ ố ượ ố ượ ụ c ướ

S b ti p c n phân c m ậ

ơ ộ ế

ụ

ả ế ụ ể ệ

ụ ễ ệ

 Phân c m mô hình và phân c m phân vùng  Mô hình: K t qu là mô hình bi u di n các c m tài li u  Vùng: Danh sách c m và vùng tài li u thu c c m  Phân c m đ n đ nh và phân c m xác su t ấ ộ

ụ ộ

ơ ỗ

ụ ị

ụ ị  Đ n đ nh: M i tài li u thu c duy nh t m t c m ệ  Xác su t: Danh sách c m và xác su t m t tài li u thu c vào các

ụ ộ ụ ộ

ấ ấ ụ ệ ấ ộ

c mụ

ẳ

ụ

ấ

 Phân c m ph ng và phân c m phân c p ệ

 Ph ng: Các c m tài li u không giao nhau  Phân c p: Các c m tài li u có quan h phân c p cha- con

ẳ ụ

ụ ệ ệ

ấ  Phân c m theo lô và phân c m tăng

ấ ụ ạ ể ệ

ụ ộ

 Lô: T i th i đi m phân c m, toàn b tài li u đã có ờ  Tăng: Tài li u ti p t c đ

c b sung trong quá trình phân c m ụ ượ ế ụ ụ ệ ổ

Các ph

ng pháp phân c m

ươ

ụ

 Các ph

ng pháp ph bi n

ươ

i, d a theo mô

ổ ế  Phân vùng, phân c pấ , d a theo m t đ , d a theo l ự

ậ ộ ự

ướ

ự

 Phân c m phân vùng

c phân ho ch các c m và đánh giá chúng theo các

ụ

ạ

ướ

tiêu chí t

ng t

hình, và mờ ụ  Xây d ng t ng b ự ừ ng ng ứ ươ / kho ng cách ự

ả

ươ

 Đ đo t ộ  K-mean, k-mediod  CLARANS, …

ấ

 Xây d ng h p (tách) d n các c m t o c u trúc phân c p và đánh giá

ụ ự

ợ

ụ

ạ

ấ

ươ

ng t

/ kho ng cách

 Phân c m phân c p ầ ng ng ứ ả

theo các tiêu chí t ươ

ự

 Đ đo t ộ  HAC: Hierarchical agglomerative clustering  CHAMELEON, BIRRCH và CURE, …

ng pháp phân c m

ụ

ậ ộ

i n i có m t đ cao

ạ ơ

ậ ộ

chính

chính t ậ

ầ ử

Các ph ươ  Phân c m d a theo m t đ ự ụ  Hàm m t đ : Tìm các ph n t ầ ử ậ ộ  Hàm liên k t: Xác đ nh c m là lân c n ph n t ụ ị ế  DBSCAN, OPTICS…  Phân c m d a theo l

ụ

ự i các ô cùng c

i ướ ỡ

i theo m t s tiêu chí: s l

ng đ i t

ng trong ô

ướ

ướ ấ

ố ượ

ụ

thi

c phân c m

ả

ụ

 S d ng l ử ụ  T o phân c p ô l ộ ố ạ  STING, CLIQUE, WaweCluster…  Phân c m d a theo mô hình ự t đ ế ượ ộ ố t nh t phù h p v i d li u ợ

ử ụ ị

ớ ữ ệ

ố

ấ

ờ

 Gi

ế

ữ ệ

ụ

ố ượ

ng có th ể

t: không có phân c m “c ng” cho d li u và đ i t ứ ộ ố ụ

các đ i t

ng t

i các c m

 S d ng m t s mô hình gi  Xác đ nh mô hình t  MCLUST…  Phân c m mụ thi ả ộ ử ụ

ờ ừ

ố ượ

ớ

ụ

thu c m t s c m  S d ng hàm m t  FCM (Fuzzy CMEANS),…

Ch đ và đ c đi m phân c m web ể

ế ộ

ụ

ặ

 Hai ch đế ộ ự

ế ả ế

 Tr c tuy n: phân c m k t qu tìm ki m ng ụ  Ngo i tuy n: phân c m t p văn b n cho tr ụ

ả ạ ế ậ i dùng ườ c ướ

ặ

ộ

ớ ộ

i câu h i tìm ki m ụ ớ ỏ ế

ế

Carpineto C., Osinski S., Romano G., Weiss D. (2009). A survey of web clustering engines, ACM Comput. Surv. , 41(3), Article 17, 38 pages.

ế  Đ c đi m ể  Ch đ tr c tuy n: t c đ phân c m ố ế ộ ự ụ ế ng l n, tăng nhanh và bi n đ ng l n  Web s l ớ ố ượ ế ng pháp gia tăng i ph  Quan tâm t ươ ớ  M t l p quan tr ng: phân c m liên quan t ọ ộ ớ  Tr c tuy n ự  Ngo i tuy n ế ạ

Thuât toán K-mean gán c ngứ

ệ

ổ ụ

 M t s l u ý ộ ố ư  Đi u ki n d ng ừ ề  Sau b ướ  Đi u ki n d ng c ệ ố

c 2 không có s thay đ i c m ự ng b c ứ ề

ỏ

ưỡ ế ố ầ ặ

b ầ ở ướ ạ ấ

ng t ừ  Kh ng ch s l n l p  Giá tr m c tiêu đ nh ủ ị ụ  V n đ ch n t p đ i di n ban đ u ệ ề ọ ậ  Có th dùng đ đo kho ng cách thay cho đ đo t ả ộ ể c Kh i đ ng ở ộ ươ ộ ự

Thuât toán K-mean gán c ngứ

 M t s l u ý (ti p) và ví d

ế

c 2: các tr ng tâm có th không thu c S

ụ ể

ọ ộ

ộ ố ư ướ ự ế ố ầ ặ £ : s l n l p

 Trong b  Th c t  Thi hành k-mean v i d li u trên đĩa

ể ở ộ

ầ ỗ

ự ủ

c 2.2

ướ

50 ớ ữ ệ  Toàn b d li u quá l n: không th b nh trong ớ ớ  V i m i vòng l p: duy t CSDL trên đĩa 1 l n ệ ng t

ướ ộ ế

c a d v i các c ớ c 2.1 kh i đ ng (t ng, b đ m); b ổ ở ộ ộ ế c 2.3 ch th c hi n k phép chia. ệ ỉ ự

ướ

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger,

2007.

ộ ữ ệ ặ ớ c đ t  Tính đ ộ ươ ượ i cạ i m i: b  Tính l ớ c ng và tăng b đ m; b ộ

ề

ạ

t tr c ế ướ

Thuât toán K-mean d ng m m  Input ố ậ

 S nguyên k > 0: s c m bi  T p tài li u D (cho tr ệ

 Output

ố ụ ướ

 T p k “đ i di n c m” ạ

C làm t

m i u l i “l ng t ” ụ ệ ậ ố ư ỗ ượ ử

ng

 Đ nh h ị

m (learning rate)

ướ  Tinh ch nh ỉ

C d n v i t

ầ ớ ỷ ệ ọ h l h c

Thuât toán K-mean

 u đi m Ư ể  Đ n gi n, d s d ng ả ơ  Hi u qu v th i gian: tuy n tính O(tkn), t s l n l p, k s c m, n ệ

ễ ử ụ

ế ố ụ ố ầ ặ

là s ph n t ố

ụ

 Nh

i u c c b . T i u toàn c c r t khó tìm ụ ố ư ổ ế ộ ố ư ụ ấ

c”: d li u phân l p thì d a theo t n s ữ ệ ự ầ ớ ố

ượ c k : s c m ầ

i): ớ ạ ạ

ố ữ ệ ạ ạ ệ

ả ề ờ ầ ử  M t thu t toán phân c m ph bi n nh t ấ ộ ậ  Th ng cho t ườ c đi m ượ ể  Ph i “tính trung bình đ ả  C n cho tr  Nh y c m v i ngo i l ạ ngo i l ạ ệ ự ế ạ ướ ớ ả th c t ớ ả ươ t ố

ố ụ ạ ệ , ngo i l ng pháp ch n m u thô t  Nh y c m v i m u ban đ u: c n ph ọ ẫ  Không thích h p v i các t p d li u không siêu-ellip ho c siêu (cách xa so v i đ i đa s d li u còn l do quan sát sai (làm s ch d li u) ầ ậ ữ ệ ẫ ặ ầ ữ ệ ợ

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007.

c u (các thành ph n con không ellip/c u hóa) ầ ầ ớ ầ

Thuât toán K-mean

ạ ả ầ ẫ ọ ớ

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007.

Trái: Nh y c m v i ch n m u ban đ u Ph iả : Không thích h p v i b d li u không siêu ellip/c u hóa ớ ộ ữ ệ ầ ợ

3. Phân c m phân c p t

d

i lên

ấ ừ ướ

ụ

t c m

ệ ụ

 Đ t  Đ t

ệ

ụ

ệ

single-link complete-link

ộ ộ

ạ ể

ữ

ộ

 HAC: Hierarchical agglomerative clustering  M t s đ đo phân bi ộ ố ộ ng t hai tài li u ự ộ ươ ng t gi a hai c m ụ ư ữ ộ ươ  Đ t ạ ự ữ ộ ươ  Đ t ữ ự ự ộ ươ  Đ t ự ự ữ ộ ươ  Đ t ự ộ ươ ơ ộ ề

gi a hai đ i di n c c đ i gi a hai tài li u thu c hai c m: c c ti u gi a hai tài liêu thu c hai cum: trung bình gi a hai tài liêu thu c hai cum ậ

ệ

c s l ng c m k, cho phép đ a ra ướ ụ ư

ố ượ ng án phân c m theo các giá tr k khác nhau ặ các ph ể ươ

ng t ng t ng t ng t  S b v thu t toán  Đ c đi m: Không cho tr ụ ố  “tìm k t  L u ý: k là m t tham s ố ộ i khái quát  Tinh ch nh: T c th t ừ ụ ể ớ

ị t nh t” ấ ư

ỉ

Phân c m phân c p t

d

i lên

ấ ừ ướ

ụ

 Gi

ả

i thích ậ

 G là t p các c m trong phân c m ụ  Đi u ki n |G| < k có th thay th b ng |G|=1

ụ ế ằ ệ ể ề

Phân c m phân c p t

d

i lên

ấ ừ ướ

ụ

ạ ộ

 Ho t đ ng HAC  Cho phép v i m i k  Ch n phân c m theo “ng

ớ ọ

ng” v đ t ng t ụ ọ ưỡ ề ộ ươ ự

HAC v i các đ đo khác nhau ộ

ớ

ủ

ưở

ộ

đ t

ng c a các đ đo ậ ạ ộ ự ự

ớ ự ộ ơ

 nh h Ả  Trên: Ho t đ ng thu t toán khác nhau theo các đ đo khác nhau: c c ti u (complete-link) có tính c u h n so v i c c đ i ể ạ c c đ i (Single-link) t o c m chu i dòng ự ự

ng t ng t ộ ươ  D iướ : Đ t ộ ươ ầ ụ ạ ạ ỗ

ễ ụ

4. Bi u di n c m và gán nhãn ể  Các ph

ng pháp bi u di n đi n dình

ễ

ể

ụ

ươ  Theo đ i di n c m ạ ệ

ạ

ủ

ụ

ạ

ị

ể t ố

ụ

ệ  Đ i di n c m làm tâm ụ  Tính bán kính và đ l ch chu n đ xác đ nh ph m vi c a c m ẩ ộ ệ  C m không ellip/c u hóa: không t ầ

 Theo mô hình phân l pớ ỉ ố ụ ậ ạ

 Ch s c m nh nhãn l p ớ  Ch y thu t toán phân l p đ tìm ra bi u di n c m ớ

ụ ễ ể ể

 Dùng cho d li u phân lo i ạ  T n s xu t hi n các giá tr đ c tr ng cho t ng c m

 Theo mô hình t n sầ ữ ệ ệ

ố

 L u ýư

ấ ị ặ ư ừ ụ ầ ố

 D li u phân c m ellip/c u hóa: đ i di n c m cho bi u di n t  C m hình d ng b t th ấ

ụ ể t ễ ố

ụ ầ ạ ng r t khó bi u di n ễ ườ ữ ệ ụ ệ ể ạ ấ

ệ

Gán nhãn c m tài li u ụ t các c m (MU)  Phân bi ụ

ệ

ng quan c m

ụ

ọ ừ

khóa đ c tr ng t ặ

khóa t, y tài li u thu c C)

ộ

ươ ệ

ộ

ụ

ụ ụ

ộ ộ

ệ ệ ệ ệ

ứ ứ

ụ

ộ

ệ

ổ

 Ch n t  Nxy (x có t ừ  N11 : s tài li u ch a t thu c c m C ố ứ  N10 : s tài li u ch a t không thu c c m C ố ứ  N01 : s tài li u không ch a t thu c c m C ố  N00 : s tài li u không ch a t không thu c c m C ố  N: T ng s tài li u ướ

ụ

ố  H ng “tr ng tâm” c m ọ khóa t n s cao t  Dùng các t ừ

 Tiêu đề

 Chon tiêu đ c a tài li u trong c m g n tr ng tâm nh t ấ

i tr ng tâm c m ạ ọ ụ ầ ố

ề ủ ụ ệ ầ ọ

Gán nhãn c m tài li u ụ

ệ

ọ

ụ

ươ

ố ớ

ụ

ệ

ụ

ệ

 Ví dụ  Ba ph ụ ầ

ủ

ng pháp ch n nhãn c m đ i v i 3 c m là c m 4 (622 tài li u), c m 9 (1017 tài li u), c m 10 (1259 tài li u) khi phân c m 10000 tài li u ệ đ u tiên c a b Reuters-RCV1 ộ  centroid: các t ầ ừ

ọ

ố

ụ

ề

khóa có t n s cao nh t trong tr ng tâm; mutual ấ information (MU): thông tin liên quan phân bi t các c m; title: tiêu đ tài ệ li u g n tr ng tâm nh t. ấ ệ

ầ

ọ

Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information 19

Retrieval, Cambridge University Press. 2008.

ng phân c m là khó khăn ự

ể

 Ng

 Ch a bi ư ế  M t s ph ộ ố ườ

5. Đánh giá phân c mụ  Đánh giá ch t l ấ ượ ụ t các c m th c s ụ ự ng pháp đi n hình ươ i dùng ki m tra ể ứ

ủ ề

 Nghiên c u tr ng tâm và mi n ph ọ  Lu t t cây quy t đ nh ậ ừ  Đ c các d li u trong c m ữ ệ ọ

 Đánh giá theo các đ đo t

ế ị

/kho ng cách ự ả

 Đ phân bi  Phân ly theo tr ng tâm

ụ ng t ươ t gi a các c m ụ ộ ệ

ộ ữ ọ

ọ ớ

 Dùng thu t toán phân l p ớ  Coi m i c m là m t l p ộ ớ  H c b phân l p đa l p (c m) ớ  Xây d ng ma tr n nh m l n khi phân l p ầ  Tính các đ đo: entropy, tinh khi

ậ ỗ ụ ộ ự ụ ẫ ậ ớ

t, chính xác, h i t ế ộ ồ ưở ng, đ ộ

đo F và đánh giá theo các đ đo này ộ