MỤC LỤC

TRANG

LỜI CẢM ƠN 5

LỜI MỞ ĐẦU 6

CHƯƠNG I : TỔNG QUAN THUYẾT VỀ PHÂN CỤM DỮ LIỆU 7

1. Phân cụm dữ liệu 7

1.1 Định nghĩa về phân cụm dữ liệu 7

1.2 Một số ví dụ về phân cụm dữ liệu 7

2. Một số kiểu dữ liệu 10

2.1 Dữ liệu Categorical 10

2.2 Dữ liệu nhị phân 13

2.3 Dữ liệu giao dịch 14

2.4 Dữ liệu Symbolic 15

2.5 Chuỗi thời gian(Time Series) 16

3. Phép Biến đổi và Chuẩn hóa dữ liệu 16

3.1 Phép chuẩn hóa dữ liệu 17

3.2 Biến đổi dữ liệu 21

3.2.1 Phân tích thành phần chính 21

3.2.2 SVD 23

3.2.3 Phép biến đổi Karhunen-Loève 24

CHƯƠNG II. CÁC THUẬT TOÁN PHÂN CỤM DỮ LIỆU 28

1. Thuật toán phân cụm dữ liệu dựa vào phân cụm phân cấp 28

1.1 Thuật toán BIRCH 28

1.2 Thuật toán CURE 30

1.3 Thuật toán ANGNES 32

1.4 Thuật toán DIANA 33

1.5 Thuật toán ROCK 33

1.6 Thuật toán Chameleon 34

2. Thuật toán phân cụm dữ liệu mờ 35

2.1 Thuật toán FCM 36

2.2 Thuật toán εFCM 37

3. Thuật toán phân cụm dữ liệu dựa vào cụm trung tâm 37

3.1 . Thuật toán K – MEANS 37

3.2 Thuật toán PAM 41

3.3 Thuật toán CLARA 42

3.4 Thuật toán CLARANS 44

4. Thuật toán phân cụm dữ liệu dựa vào tìm kiếm 46

4.1 Thuật toán di truyền (GAS) 46

4.2 J- Means 48

5. Thuật toán phân cụm dữ liệu dựa vào lưới 49

5.1 STING 49

5.2. Thuật toán CLIQUE 51

5.3. Thuật toán WaveCluster 52

6. Thuật toán phân cụm dữ liệu dựa vào mật độ 53

6.1 Thuật toán DBSCAN 53

6.2. Thuật toán OPTICS 57

6.3. Thuật toán DENCLUDE 58

7. Thuật toán phân cụm dữ liệu dựa trên mẫu 60

7.1 Thuật toán EM 60

7.2 Thuật toán COBWEB 61

CHƯƠNG III :ỨNG DỤNG CỦA PHÂN CỤM DỮ LIỆU 62

1. Phân đoạn ảnh 62

1.1. Định nghĩa Phân đoạn ảnh 63

1.2 Phân đoạn ảnh dựa vào phân cụm dữ liệu 65

2. Nhận dạng đối tượng và ký tự 71

2.1 Nhận dạng đối tượng 71

2.2 Nhận dạng ký tự. 75

3. Truy hồi thông tin 76

3.1 Biểu diễn mẫu 78

3.2 Phép đo tương tự 79

3.3 Một giải thuật cho phân cụm dữ liệu sách 80

4. Khai phá dữ liệu 81

4.1 Khai phá dữ liệu bằng Phương pháp tiếp cận. 82

4.2 Khai phá dữ liệu có cấu trúc lớn. 83

4.3 Khai phá dữ liệu trong Cơ sở dữ liệu địa chất. 84

4.4 Tóm tắt 86

KẾT LUẬN ,HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI 90

PHỤ LỤC 91

TÀI LIỆU THAM KHẢO 99

LỜI MỞ ĐẦU

Trong những năm gần đây, sự phát triển mạnh mẽ của CNTT đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó, việc tin học hóa một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khổng lồ. Hàng triệu CSDL đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lý..., trong đó có nhiều CSDL cực lớn cỡ Gigabyte, thậm chí là Terabyte.

Sự bùng nổ này đã dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền CNTT thế giới hiện nay nói chung và Việt Nam nói riêng. Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau: marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet… Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn.

Các kỹ thuật khai phá dữ liệu thường được chia thành 2 nhóm chính:

- Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có.

- Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoándựa vào các suy diễn trên dữ liệu hiện thời.

Bản luận văn này trình bày một số vấn đề về Phân cụm dữ liệu, một trong những kỹ thuật cơ bản để Khai phá dữ liệu. Đây là hướng nghiên cứu có triển vọng chỉ ra những sơ lược trong việc hiểu và khai thác CSDL khổng lồ, khám phá thông tin hữu ích ẩn trong dữ liệu; hiểu được ý nghĩa thực tế của dữ liệu.

Luận văn được trình bày trong 3 chương và phần phụ lục :

Chương 1 : Trình bày tổng quan lý thuyết về Phân cụm dữ liệu, các kiểu dữ

liệu, Phép biến đổi và chuẩn hóa dữ liệu.

Chương 2 : Giới thiệu, phân tích, đánh giá các thuật toán dùng để phân cụm dữ liệu

Chương 3 : Trình bày một số ứng dụng tiêu biểu của phân cụm dữ liệu.

Kết luận : Tóm tắt các vấn đề được tìm hiểu trong luận văn và các vấn đề liên quan trong luận văn, đưa ra phương hướng nghiên cứu tiếp theo.