ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
-------------------------------------------
TRẦN QUANG HÀO
PHÂN CỤM DỮ LIỆU DỰA TRÊN ĐỒ THỊ
SỬ DỤNG CÂY KHUNG CỰC TIỂU
LUẬN VĂN THẠC SỸ C NG NGHỆ TH NG TIN
Hà Nội – 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
---------------------
TRẦN QUANG HÀO
PHÂN CỤM DỮ LIỆU DỰA TrRÊN ĐỒ THỊ
SỬ DỤNG CÂY KHUNG CỰC TIỂU
Ngành: Công Nghệ Thông Tin
Chuyên ngành: Kỹ thuật Phần mềm (Software Engineering)
Mã số: 60480103
LUẬN VĂN THẠC SỸ C NG NGHỆ TH NG TIN
NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN
Hà Nội – 2014
1
LỜI CẢM ƠN
Điều ầu ti n tôi xin gửi lời cảm ơn sâu sắc nhất ến PGS.TS Hoàng Xuân Huấn.
Thầy ã cung cấp cho tôi những kiến thức, tài liệu, phƣơng pháp khi nghi n cứu v l m
luận v n. Tôi xin cảm ơn thầy về sự hỗ trợ chân thành và nhiệt tình trong suốt thời gian
qua. Đối với t i thầy l một ngƣời thầy áng k nh v lu n hết l ng v học vi n
T i xin gửi lời cảm ơn chân th nh ến các thầy c ộ ã giảng y các cán ộ
trong kho c ng nghệ th ng tin kho s u i học ph ng t chức h nh ch nh
T i xin gửi lời cảm ơn ến gi nh ng nghiệp v n những ngƣời ã
ộng vi n t i rất nhiều trong quá tr nh học tập
Hà Nội, ngày 2 tháng 12 n m 2014
Học viên
Trần Quang Hào
2
LỜI CAM ĐOAN
T i xin c m o n những kiến thức trình bày trong luận v n n y l o t i t m hiểu,
nghiên cứu và trình bày theo cách hiểu của bản thân ƣới sự hƣớng dẫn trực tiếp của
PGS.TS Hoàng Xuân Huấn. Trong quá trình làm luận v n t i có th m khảo các tài liệu
có li n qu n v ã ghi rõ ngu n gốc tham khảo tài liệu ó Mọi sao chép không hợp lệ,
vi ph m quy chế o t o tôi xin chịu hoàn toàn trách nhiệm.
Hà Nội, ngày 2 tháng 12 n m 2014
Học viên
Trần Quang Hào
3
MỤC LỤC
LỜI CẢM ƠN .................................................................................................................... 1
LỜI CAM ĐOAN .............................................................................................................. 2
MỤC LỤC .......................................................................................................................... 3
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ................................................... 5
DANH MỤC HÌNH VẼ .................................................................................................... 6
LỜI MỞ ĐẦU .................................................................................................................... 7
CHƢƠNG 1: GIỚI THIỆU VỀ KH M PH TRI TH C V PH N CỤM Ữ LIỆU
............................................................................................................................................ 8
1.1. Khám phá tri thức ....................................................................................................... 8
1.2. Vai trò và các mục tiêu chính của KDD .................................................................... 9
1.3. Khái niệm phân cụm ữ liệu: ..................................................................................... 10
1.4. Các ứng dụng của phân cụm ...................................................................................... 11
1 5 Một số phƣơng pháp phân cụm iển h nh ................................................................... 12
1 5 1 Phƣơng pháp phân cụm phân ho ch ........................................................................ 12
1 5 2 Phƣơng pháp phân cụm phân cấp............................................................................. 13
1 5 3 Phƣơng pháp phân cụm dựa trên mật ộ ................................................................. 16
1 5 4 Phƣơng pháp phân cụm dự tr n lƣới ...................................................................... 17
1.6. Một số vấn ề li n qu n ến phân cụm ...................................................................... 18
1.6.1. Mêtric trên dữ liệu hỗn hợp. .................................................................................... 18
1.6.2.Độ tƣơng ng. ......................................................................................................... 20
1.6.3. Entropy ..................................................................................................................... 23
CHƢƠNG 2: THU T TO N PH N CỤM S ỤNG C Y KHUNG CỰC TIỂU ... 24
2.1.Cây khung cực tiểu ...................................................................................................... 24
2 1 1 Đ nh ngh cây khung cực tiểu ................................................................................ 24
2 1 2 Thuật toán xây ựng cây khung cực tiểu ................................................................. 24
2.2. Một số khái niệm cần dùng ....................................................................................... 26
2.3. Cụm ƣợc mô tả bởi Zahn v H n l .......................................................................... 27
2.4. Thiết lập i toán phân cụm ng thị: ................................................................... 28
2 5 Độ phức t p củ thuật toán 2-MSTs ...................................................................... 35
