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Ở ĐẦ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ỹ 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.
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