i
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
===================
Nguyễn Thị Huế
NGHIÊN CỨU CÁC KỸ THUẬT PHÂN CỤM DỮ LIỆU
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SỸ
HÀ NỘI - 2011
ii
LỜI CẢM ƠN
Để hoàn thành được luận văn này, trước hết tôi xin gửi lời cảm ơn sâu sắc nhất
tới GS.TS Vũ Đức Thi, Viện trưởng Viện công nghệ thông tin đã tận tình hướng
dẫn, chỉ bảo, định hướng, đóng góp những ý kiến quý báu trong suốt quá trình tôi
thực hiện luận văn.
Tôi xin chân thành cảm ơn các thầy, cô giáo trong Bộ môn Hệ thống thông tin,
Khoa Công nghệ thông tin, Phòng Đào tạo Sau đại học - Nghiên cứu Khoa học,
Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất
để tôi hoàn thành khóa học này. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè,
những người luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi
xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt
quá trình học tập và làm luận văn này.
Hà Nội, ngày 10 tháng 04 năm 2011
Học viên
Nguyễn Thị Huế
iii
LỜI CAM ĐOAN
Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm
hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận
văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo
đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày
hoàn chỉnh trong bất cứ tài liệu nào.
Hà Nội, ngày 10 tháng 04 năm 2011
Học viên
Nguyễn Thị Huế
iv
MỤC LỤC
MỞ ĐẦU ................................................................................................................1
Chương 1.................................................................................................................3
TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU ..................3
1.1. Giới thiệu chung ...........................................................................................3
1.2. Khai phá tri thức và quá trình khai phá tri thức .............................................3
1.2.1. Khai phá tri thức ....................................................................................3
1.2.2. Quá trình khai phá tri thức .....................................................................4
1.3. Khai phá dữ liệu ...........................................................................................5
1.3.1. Khai phá dữ liệu.....................................................................................5
1.3.2. Mục tiêu của khai phá dữ liệu ................................................................6
1.3.3. Quá trình khai phá dữ liệu......................................................................6
1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu..7
1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu.......13
1.3.6. Ứng dụng của khai phá dữ liệu.............................................................13
1.3.7. Kết luận ...............................................................................................14
Chương 2. PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG ...............15
PHÂN CỤM DỮ LIỆU .........................................................................................15
2.1. Giới thiệu....................................................................................................15
2.2. Các ứng dụng của phân cụm .......................................................................16
2.3. Các yêu cầu về thuật toán phân cụm dữ liệu................................................17
2.4. Các kiểu dữ liệu trong phân cụm.................................................................18
2.5. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu .....................21
2.6. Các hướng tiếp cận của bài toán phân cụm dữ liệu......................................28
2.6.1. Phương pháp phân hoạch (Partitioning Methods) ...........................28
2.6.2. Phương pháp phân cấp (Hierarchical Methods) ..............................36
2.6.3. Phương pháp dựa trên mật độ (Density-Based Methods) ................44
2.6.4. Phương pháp dựa trên lưới (Gird-Based Methods)..........................51
2.6.5. Kết luận..........................................................................................56
Chương 3: ỨNG DỤNG........................................................................................58
KẾT LUẬN...........................................................................................................65
TÀI LIỆU THAM KHẢO .....................................................................................66
PHỤ LỤC..............................................................................................................68
v
DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT
Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh
Cơ sở dữ liệu CSDL DataBase
Khai phá tri thức trong cơ sở dữ liệu
KDD Knowledge Discovery in
Databases
Khai phá dữ liệu KPDL Data Mining
Phân cụm dữ liệu PCDL Data Clustering
Khai phá tri thức KPTT Knowledge Discovery