Luận Văn Phân cụm dữ liệu Bài toán và các giải thuật theo tiếp cận phân cấp

Đồ án tốt nghiệp năm 2013
Đề tài: Phân cụm dữ liệu: Bài toán và các giải thuật theo tiếp cận phân cấp




MỤC LỤC
LỜI MỞ ĐẦU . 5
CHƯƠNG I: KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU 7
1.1 Khai phá dữ liệu (Data Mining) là gì? 7
1.2 Quy trình khai phá dữ liệu 7
1.3 Các kỹ thuật khai phá dữ liệu. 9
1.4 Các ứng dụng của khai phá dữ liệu. 10
1.5 Một số thách thức đặt ra cho việc khai phá dữ liệu 13
1.6 Kết luận chương 13
CHƯƠNG 2: PHÂN CỤM DỮ LIỆU VÀ CÁC GIẢI THUẬT THEO
TIẾP CẬN PHÂN CẤP . 14
2.1 Phân cụm dữ liệu (Data Clustering) là gì? 14
2.2 Thế nào là phân cụm tốt? 17
2.3 Bài toán phân cụm dữ liệu 17
2.4 Các ứng dụng của phân cụm . 18
2.5 Các yêu cầu đối với thuật toán phân cụm dữ liệu . 18
2.6 Các kiểu dữ liệu và phép đo độ tương tự 19
2.6.1 Cấu trúc dữ liệu . 19
2.6.2 Các kiểu dữ liệu . 20
1) Thuộc tính khoảng (Interval Scale): 22
2) Thuộc tính nhị phân: 23
3) Thuộc tính định danh (nominal Scale): . 25
4) Thuộc tính có thứ tự (Ordinal Scale): . 25
5) Thuộc tính tỉ lệ (Ratio Scale) . 26
2.7 Các hướng tiếp cận bài toán phân cụm dữ liệu . 27
2.7.1 Phương pháp phân hoạch. 27
2.7.2 Phương pháp phân cấp . 27
2.7.3 Phương pháp dựa vào mật độ (Density based Methods) 28
2.7.4 Phân cụm dữ liệu dựa trên lưới . 29
2.7.5 Phương pháp dựa trên mô hình (Gom cụm khái niệm, mạng neural)
. 30
2.7.6 Phân cụm dữ liệu có ràng buộc . 30
2.8 Các vấn đề có thể gặp phải . 31
2.9 Phương pháp phân cấp (Hierarchical Methods) . 31
2.6.1 Thuật toán BIRCH 33
4
2.6.2 Thuật toán CURE 47
2.10 Kết luận chương 51
CHƯƠNG 3: CHƯƠNG TRÌNH DEMO 52
3.1. Bài toán và lưu đồ thuật toán 52
3.2. Chương trình demo . .
3.3. Chạy chương trình 54
KẾT LUẬN 54
TÀI LIỆU THAM KHẢO . 55




LỜI MỞ ĐẦU
Trong những năm gần đây, cùng với sự phát triển vượt bậc của công nghệ
điện tử và truyền thông, khả năng thu thập và lưu trữ thông tin của các hệ thống
thông tin không ngừng được nâng cao. Theo đó, lượng thông tin được lưu trữ trên
các thiết bị nhớ không ngừng tăng lên. Khai phá dữ liệu là một lĩnh vực khoa học
mới xuất hiện, nhằm tự động hóa việc khai thác những thông tin, những tri thức
tiềm ẩn, hữu ích từ những CSDL lớn cho các đơn vị, tổ chức, doanh nghiệp, từ đó
làm thúc đẩy khả năng sản xuất, kinh doanh, cạnh tranh cho các đơn vị, tổ chức này.
Những ứng dụng thành công trong khám phá tri thức, cho thấy khai phá dữ liệu là
một lĩnh vực phát triển bền vững mang lại nhiều lợi ích và có nhiều triển vọng,
đồng thời có ưu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Hiện
nay, khai phá dữ liệu đã và đang được ứng dụng ngày càng rộng rãi trong các lĩnh
vực như: thương mại, tài chính, điều trị y học, viễn thông, tin-sinh.
Một trong những hướng nghiên cứu chính của khai phá dữ liệu là phân cụm
dữ liệu (Data Clustering). Phân cụm dữ liệu là quá trình tìm kiếm và phát hiện ra
các cụm dữ liệu tự nhiên tiềm ẩn trong cơ sở dữ liệu lớn, từ đó cung cấp thông tin,
tri thức hữu ích cho việc ra quyết định. Có rất nhiều kĩ thuật trong phân cụm dữ liệu
như: phân cụm dữ liệu phân hoạch, phân cụm dữ liệu phân cấp, phân cụm dựa trên
mật độ, Tuy nhiên các kĩ thuật này đều hướng tới hai mục tiêu chung đó là chất
lượng các cụm khám phá được và tốc độ thực hiện của thuật toán. Trong đó, kĩ
thuật phân cụm dữ liệu phân cấp là một kĩ thuật có thể đáp ứng được những mục
tiêu này và có khả năng làm việc với các CSDL lớn.
Nghiên cứu và ứng dụng một cách hiệu quả các phương pháp khai phá dữ
liệu là vấn đề hấp dẫn, đã và đang thu hút sự quan tâm chẳng những của các nhà
nghiên cứu, ứng dụng mà của cả các tổ chức, doanh nghiệp. Do đó, em đã chọn đề
tài nghiên cứu “Phân cum dữ liệu: Bài toán và các giả thuật theo tiếp cận phân
cấp” cho đồ án tốt nghiệp của mình.
Nội dung của đồ án gồm 3 chương:
Chương 1: Khái quát về khai phá dữ liệu: Trong chương này em trình bày
tổng quan về khai phá dữ liệu, quy trình khai phá, các k ỹ thuật khai phá và các ứng
dụng của khai phá dữ liệu, cuối cùng là các thách thức đặt ra.
6
Chương 2: Trình bày về các phương pháp phân cụm dữ liệu, trong đó đồ án
đi sâu vào tìm hiểu về phương pháp phân cụm phân cấp với 2 thuật toán điển hình
là: BIRCH và CURE.
Chương 3: Chương trình demo: Để khẳng định cho khả năng và hiệu quả của
thuật toán phân cụm phân cấp, xây dựng một chương trình demo đơn giản sử dụng
thuật toán CURE.
Cuối cùng là phần kết luận trình bày tóm tắt các kết quả thu được và các đề
xuất cho hướng phát triển của đề tài.




TÀI LIỆU THAM KHẢO
[1] Nguyễn Thị Ngọc, Phân cụm dữ liệu dựa trên mật độ, Đồ án tốt
nghiệp đại học Ngành công nghệ Thông tin – ĐHDL Hải Phòng, 2008.
[2] Trần Thị Quỳnh, Thuật toán phân cụm dữ liệu nửa giám sát và giải thuật
di truyền, Đồ án tốt nghiệp đại học Ngành công nghệ Thông tin – ĐHDL Hải
Phòng, 2008.
[3] Nguyễn Lâm, Thuật toán phân cụm dữ liệu nửa giám sát , Đồ án tốt
nghiệp đại học Ngành công nghệ Thông tin – ĐHDL Hải Phòng, 2007.
[4] Nguyễn Trung Sơn, Phương pháp phân cụm và ứng dụng, Luận văn thạc
sĩ khoa học máy tính, Khoa công nghệ thông tin trường Đại học Thái Nguyên.
[5] Nguyễn Thị Hướng, Phân cụm dữ liệu trong data mining, Luận văn tốt
nghiệp ngành công nghệ thông tin Đại học sư phạm Hà Nội.
[6] Tian Zhang, Raghu Ramakrishnan, Miron Livny. BIRCH: A New Data
Clustering Algorithm and Its Applications. Data Mining and Knowledge Discovery,
1, 141–182 (1997), Kluwer Academic Publishers, 1997.
[7] Sudipto Guha, Rajeev Rastogi, Kyuseok Shim, CURE: an efficient
clustering algorithm for large databases, Information Systems Vol. 26, No.1, pp.35-58,Elsevier Science, 2001.
[8] J.Han, M. Kamber and A.K.H. Tung, Spatial Clustering Methods in Data
Mining, Sciences and Engineering Research Council of Canada.