Thạc Sĩ Nghiên cứu và cài đặt một số giải thuật phân cụm, phân lớp

MỤC LỤC
MỞ ĐẦU . 3
MỘT SỐ TỪ VIẾT TẮT VÀ THUẬT NGỮ THƯỜNG DÙNG 5
DANH MỤC BẢNG . 6
DANH MỤC HÌNH 7
CHƯƠNG 1: TỔNG QUAN PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ
LIỆU 8
1.1 Giới thiệu chung 8
1.2 Các kỹ thuật khai phá dữ liệu 10
1.3 Lợi thế của khai phá dữ liệu so với các phương pháp khác 13
1.4 Các ứng dụng của KDD và những thách thức đối với KDD 15
1.5 Kết luận 17
CHƯƠNG 2: KỸ THUẬT PHÂN LOẠI TRONG KHAI PHÁ DỮ LIỆU . 18
2.1 Phân loại là gì? 18
2.2 Các vấn đề quan tâm của phân loại . 20
2.3 Phân loại bằng cây quyết định quy nạp . 22
2.4 Phân loại Bayesian 30
2.5 Phân loại bằng lan truyền ngược . 37
2.6 Phân loại dựa trên sự kết hợp 48
2.7 Các phương pháp phân loại khác 50
2.8 Độ chính xác classifier 56
2.9 Kết luận 59
CHƯƠNG 3: KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU 60
3.1 Phân cụm là gì . 60
3.2 Các kiểu dữ liệu trong phép phân cụm 64
3.3 Phân loại các phương pháp phân cụm chính . 74
3.4 Các phương pháp phân chia 77
3.5 Các phương pháp phân cấp . 84
3.6 Các phương pháp phân cụm dựa trên mật độ 94
3.7 Các phương pháp phân cụm dựa trên lưới 101
3.8 Kết luận 107
CHƯƠNG 4: CÀI ĐẶT THỬ NGHIỆM 108
4.1 Thiết kế tổng thể 108
4.2 Chuẩn bị dữ liệu 108
4.3 Thiết kế chương trình 109
4.4 Kết quả thực nghiệm và đánh giá 110
4.5 Kết luận 114
KẾT LUẬN . 116
TÀI LIỆU THAM KHẢO . 118
-2-
LỜI CẢM ƠN
Trước tiên em xin chân thành cảm ơn thầy giáo PGS.TS Nguyễn Ngọc
Bình đã tận tình hướng dẫn, chỉ bảo em trong thời gian qua.
Em xin bày tỏ lòng biết ơn tới các thầy cô giáo trong khoa Công nghệ
Thông tin nói riêng và trường Đại học Bách Khoa Hà Nội nói chung đã dạy bảo,
cung cấp những kiến thức quý báu cho em trong suốt quá trình học tập và
nghiên cứu tại trường.
Em cũng xin gửi lời cảm ơn tới gia đình, bạn bè, những người luôn cổ vũ,
quan tâm và giúp đỡ em trong suốt thời gian học tập cũng như làm luận văn.
Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi
những thiếu sót nhất định. Em rất mong nhận được những sự góp ý quý báu của
thầy cô và các bạn.
Hà Nội, 11-2006
Vũ Lan Phương
-3-
MỞ ĐẦU
ã Giới thiệu
Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông
tin trong nhiều lĩnh vực của đời sống, kinh tế xã hội trong nhiều năm qua cũng
đồng nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một
tích luỹ nhiều lên. Họ lưu trữ các dữ liệu này vì cho rằng trong nó ẩn chứa
những giá trị nhất định nào đó. Tuy nhiên, theo thống kê thì chỉ có một lượng
nhỏ của những dữ liệu này (khoảng từ 5% đến 10%) là luôn được phân tích, số
còn lại họ không biết sẽ phải làm gì hoặc có thể làm gì với chúng nhưng họ vẫn
tiếp tục thu thập rất tốn kém với ý nghĩ lo sợ rằng sẽ có cái gì đó quan trọng đã
bị bỏ qua sau này có lúc cần đến nó. Mặt khác, trong môi trường cạnh tranh,
người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc ra
quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả
lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy,
các phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng
không đáp ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới
đó là Kỹ thuật phát hiện tri thức và khai phá dữ liệu (KDD - Knowledge
Discovery and Data Mining).
Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam
kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần
đưa vào ứng dụng. Bước quan trọng nhất của quá trình này là Khai phá dữ liệu
(Data Mining - DM), giúp người sử dụng thu được những tri thức hữu ích từ
những CSDL hoặc các nguồn dữ liệu khổng lồ khác. Rất nhiều doanh nghiệp và
tổ chức trên thế giới đã ứng dụng kĩ thuật khai phá dữ liệu vào hoạt động sản
xuất kinh doanh của mình và đã thu được những lợi ích to lớn. Nhưng để làm
được điều đó, sự phát triển của các mô hình toán học và các giải thuật hiệu quả
là chìa khoá quan trọng. Vì vậy, trong luận văn này, tác giả sẽ đề cập tới hai kỹ
-4-
thuật thường dùng trong Khai phá dữ liệu, đó là Phân loại (Classification) và
Phân cụm (Clustering hay Cluster Analyse).
ã Bố cục luận văn
Ngoài các phần Mở đầu, Mục lục, Danh mục hình, Danh mục bảng, Kết
luận, Tài liệu tham khảo, luận văn được chia làm 4 phần:
Phần I: Tổng quan về Phát hiện tri thức và Khai phá dữ liệu
Phần này giới thiệu một cách tổng quát về quá trình phát hiện tri thức nói
chung và khai phá dữ liệu nói riêng. Đặc biệt nhấn mạnh về hai kỹ thuật chính
được nghiên cứu trong luận văn đó là Kỹ thuật phân loại và Kỹ thuật phân cụm.
Phần II: Kỹ thuật phân loại (Classification)
Trong phần này, kỹ thuật phân loại được giới thiệu một cách chi tiết. Có
nhiều kiểu phân loại như phân loại bằng cây quyết định quy nạp, phân loại
Bayesian, phân loại bằng mạng lan truyền ngược, phân loại dựa trên sự kết hợp
và các phương pháp phân loại khác. Ngoài ra còn đánh giá độ chính xác của
phân loại thông qua các classifier - người phân loại.
Phần III: Kỹ thuật phân cụm (Clustering)
Kỹ thuật phân cụm cũng được chia làm nhiều kiểu: phân cụm phân chia,
phân cụm phân cấp, phân cụm dựa trên mật độ và phân cụm dựa trên lưới.
Phần IV: Cài đặt thử nghiệm
Phần này trình bày một số kết quả đã đạt được khi tiến hành áp dụng các
giải thuật khai phá dữ liệu để khai thác thông tin dữ liệu mẫu.