Đồ Án Phương pháp phân cụm và ứng dụng

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
-3-
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
-4-
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án
dự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.