BÀI GI NG NH P MÔN KHAI PHÁ D LI UẢ Ậ Ữ Ệ
CH NG 6. PHÂN C M D Li UƯƠ Ụ Ữ Ệ
PGS. TS. HÀ QUANG TH YỤ
HÀ N I 9-2011Ộ
TR NG Đ I H C CÔNG NGHƯỜ Ạ Ọ Ệ
Đ I H C QU C GIA HÀ N IẠ Ọ Ố Ộ
1
N i dungộ
Gi 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ụ
2
1. Bài toán phân c m Webụ
3
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ữ ệ ộ ụ
Các d li u trong m t c m: “t ng t ” nhau (g n nhau)ữ ệ ộ ụ ươ ự ầ
D li u hai c m: “không t ng t ” nhau (xa nhau)ữ ệ ụ ươ ự
Đo “t ng t ” (g n) nhau ?ươ ự ầ
Tiên đ phân c m:ề ụ N u ng i dùng l a ch n m t đ i t ng ế ườ ự ọ ộ ố ượ d thì h ọ
cũng l a ch n các đ i t ng cùng c m v i ự ọ ố ượ ụ ớ d
Khai thác “cách ch n l a” c a ng i dùngọ ự ủ ườ
Đ a ra m t s đ đo “t ng t ” theo bi u di n d li uư ộ ố ộ ươ ự ể ễ ữ ệ
M t s n i dung liên quanộ ố ộ
Xây d ng đ đo t ng 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 cố ượ ụ ướ ố ượ ụ ướ
S b ti p c n phân c mơ ộ ế ậ ụ
4
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ươ ụ
5
Các ph ng pháp ph bi nươ ổ ế
Phân vùng, phân c pấ, d a theo m t đ , d a theo l i, d a theo mô ự ậ ộ ự ướ ự
hình, và mờ
Phân c m phân vùngụ
Xây d ng t ng b c phân ho ch các c m và đánh giá chúng theo các ự ừ ướ ạ ụ
tiêu chí t ng ngươ ứ
Đ đo t ng t / kho ng cáchộ ươ ự ả
K-mean, k-mediod
CLARANS, …
Phân c m phân c pụ ấ
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á ự ợ ầ ụ ạ ấ ấ
theo các tiêu chí t ng ngươ ứ
Đ đo t ng t / kho ng cáchộ ươ ự ả
HAC: Hierarchical agglomerative clustering
CHAMELEON, BIRRCH và CURE, …