Đồ Án Một số phương pháp phân cụm dữ liệu

MỤC LỤC
MỤC LỤC . . 1
DANH MỤC HÌNH MINH HỌA . . 3
LỜI CẢM ƠN . . 4
CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU . . 5
1.1 Giới thiệu về khám phá tri thức . . 5
1.2 Khai phá dữ liệu và các khái niệm liên quan . . 7
1.2.1 Khái niệm khai phá dữ liệu . . 7
1.2.2 Các phương pháp khai phá dữ liệu . 7
1.2.3 Các lĩnh vực ứng dụng trong thực tiễn . 8
1.2.4 Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu 8
CHƯƠNG 2: PHÂN CỤM DỮ LIỆU VÀ CÁC TIẾP CẬN . 10
2.1 Khái niệm chung . 10
2.2 Các kiểu dữ liệu và độ đo tương tự . 10
2.2.1 Các kiểu dữ liệu . 10
2.2.2 Độ đo tương tự và phi tương tự . 12
2.3 Các kỹ thuật tiếp cận trong phân cụm dữ liệu . 15
2.3.1 Phương pháp phân cụm phân hoạch . 15
2.3.2 Phương pháp phân cụm phân cấp . 15
2.3.3 Phương pháp phân cụm dựa trên mật độ . 16
2.3.4 Phương pháp phân cụm dựa trên lưới . 17
2.3.5 Phương pháp phân cụm dựa trên mô hình . 18
2.3.6 Phương pháp phân cụm có dữ liệu ràng buộc . 19
2.4 Các ứng dụng phân cụm dữ liệu . 20
CHƯƠNG 3: MỘT SỐ THUẬT TOÁN CƠ BẢN TRONG PHÂN CỤM DỮ LIỆU 21
3.1 Các thuật toán phân cụm phân hoạch . 21
3.1.1 Thuật toán K-means . 21
3.1.2 Thuật toán K-Medoids . 23
3.2 Thuật toán phân cụm phân cấp . 24
3.3 Thuật toán COP-Kmeans . 26
CHƯƠNG 4: ỨNG DỤNG THUẬT TOÁN K-MEANS CHO PHÂN ĐOẠN ẢNH . 28
4.1 Tổng quan về phân vùng ảnh . 28
4.1.1 Phân vùng ảnh theo ngưỡng biên độ . 28
4.1.2 Phân vùng ảnh theo miền đồng nhất . 29
4.1.3 Phân vùng dựa theo đường biên . 31
4.1.4 Phân đoạn dựa theo kết cấu bề mặt . 31
4.2 Thuật toán K-means cho phân đoạn ảnh . 32
4.2.1 Mô tả bài toán . 32
4.2.2 Các bước thực hiện chính trong thuật toán . 33
4.2.2.1 Tìm kiếm Top X color . 34
4.2.2.2 Tính khoảng cách và phân cụm . 36
4.2.2.3 Tính lại trọng tâm cụm . 37
4.2.2.4 Kiểm tra hội tụ . 38
4.2.3 Kết quả thực nghiệm . 39
4.2.3.1 Môi trường cài đặt. 39
4.2.3.2 Một số giao diện. 39
KẾT LUẬN . 41
TÀI LIỆU THAM KHẢO . 42




Một số phương pháp phân cụm dữ liệu




CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1 Giới thiệu về khám phá tri thức
Nếu cho rằng các điện tử và các sóng điện tử chính là bản chất của
công nghệ điện tử truyền thống thì dữ liệu, thông tin và tri thức hiện đang là
tiêu điểm của một lĩnh vực mới trong nghiên cứu và ứng dụng về phát hiện tri
thức (Knowledge Discovery) và khai phá dữ liệu (Data Mining).
Thông thường chúng ta coi dữ liệu như một dãy các bit, hoặc các số và
các ký hiệu, hoặc các “đối tượng” với một ý nghĩa nào đó khi được gửi cho
một chương trình dưới một dạng nhất định. Chúng ta sử dụng các bit để đo
lường các thông tin và xem nó như là các dữ liệu đã được lọc bỏ các dư thừa,
được rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu.
Chúng ta có thể xem tri thức như là các thông tin tích hợp, bao gồm các sự
kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được hiểu
ra, có thể được phát hiện, hoặc có thể được học. Nói cách khác, tri thức có thể
được coi là dữ liệu có độ trừu tượng và tổ chức cao.
Phát hiện tri thức trong các cơ sở dữ liệu là một qui trình nhận biết các
mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích,
và có thể hiểu được. Còn khai thác dữ liệu là một bước trong qui trình phát
hiện tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dưới một số
qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô
hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai
phá dữ liệu chính là tìm ra các mẫu hoặc các mô hình đang tồn tại trong các
cơ sở dữ liệu nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu.