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

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

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 thg 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 hoạch 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à một số giải thuật theo tiếp cận phân
hoạch” 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.
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à:
K-Means, K-Medoids.
Chương 3: Cài đặt thực nghiệm: Để khẳng định cho khả năng và hiệu quả của
thuật toán phân cụm dữ liệu phân hoạch.
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 dataming, 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