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