- CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc TÓM TẮT LUẬN VĂN THẠC SĨ Đề tài : Bài toán phân cụm: giải thuật và các ứng dụng Tác giả luận văn : Nguyễn Hoàng Anh Khóa: 2012B Người hướng dẫn : TS Phạm Quang Dũng A) Lý do chọn đề tài Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong các lĩnh vực của đời sống, kinh tế, xã hội trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu ngày một nhiều lên. - Người ta ngày càng cần có nhiều thông tin để trợ giúp việc ra quyết định và điều hành doanh nghiệp dựa trên một khối lượng dữ liệu khổng lồ đã có Phân cụm có ý nghĩa rất quan trọng trong khai phá dữ liệu và các hoạt động của con người, được sử dụng rộng rãi trong nhiều ứng dụng, bao gồm bài toán phân phối, nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trường. - Hiện nay có khá nhiều thuật toán đã được đưa ra để áp dụng cho bài toán phân cụm, tuy nhiên mỗi giải thuật đều có những ưu, nhược điểm riêng. - Giải thuật phân cụm cân bằng giúp giải bài toán phân cụm mở rộng với ràng buộc cân bằng về số điểm trong mỗi một cụm là một hướng đi mới, có nhiều hứa hẹn B) Mục đích nghiên cứu của luận văn, đối tượng, phạm vi nghiên cứu Tìm hiểu tổng quan về phân cụm và các ứng dụng trong thực tế Tìm hiểu các thuật toán phân cụm cổ điển và các ưu nhược điểm của chúng Nghiên cứu chi tiết thuật toán phân cụm cân bằng Cài đặt thử nghiệm thuật toán phân cụm cân bằng trên dữ liệu nguồn OpenStreetMap là các trạm ATM trên địa bàn Hà Nội. - Đánh giá và kết luận C) Tóm tắt cô đọng các nội dung chính và đóng góp mới của tác giả Luận văn được chia ra làm 5 chương cụ thể như sau: PHẦN I : CƠ SỞ LÍ THUYẾT CHƯƠNG I : Giới thiệu chung Giới thiệu tổng quan về phân cụm, bao gồm các định nghĩa cơ bản tới các ứng dụng của phân cụm trong thực tế. - Chương này cũng nêu lên những khó khăn trong việc phân cụm, chi tiết về các kiểu cụm và cuối cùng là giới thiệu các kĩ thuật phân cụm phổ biến nhất. - CHƯƠNG II : Thuật toán phân cụm cổ điển Tìm hiểu thuật toán phân cụm cổ điển K-means, K-medoid nhưng chỉ tập trung chi tiết vào thuật toán K-means, thuật toán phân cụm phổ biến nhất. - Sau đó các vấn đề bổ sung, nâng cao khi thực hiện phân cụm theo thuật toán K-means cũng sẽ được đề cập và cuối cùng là các ưu nhược điểm của thuật toán. - PHẦN II : PHÂN CỤM CÂN BẰNG CHƯƠNG III : Bài toán phân cụm cân bằng Chương này giới thiệu cụ thể về bài toán phân cụm cân bằng, các nhu cầu thực tế của phân cụm nhưng cần thêm điều kiện ràng buộc cân bằng số điểm bằng nhau trong mỗi cụm. - Chương cũng trình bày một cách tóm tắt về tiến trình thực hiện phân cụm dữ liệu theo yêu cầu mở rộng này. - CHƯƠNG IV : Thuật toán phân cụm cân bằng Chương này nghiên cứu một cách chi tiết về thuật toán phân cụm cân bằng. - Ba bước được trình này vắn tắt ở chương trước đó là : lấy mẫu, phân cụm tập mẫu và phân phối, lọc sẽ được mô tả cụ thể và trình bày dưới dạng giả ngôn ngữ. - Phần trọng tâm của thuật toán là bước phân phối và lọc. - CHƯƠNG V : Cài đặt thử nghiệm Mô tả các bước cài đặt thuật toán dựa vào bộ dữ liệu nguồn OpenStreetMap, là các điểm ATM có trên địa bàn Hà Nội. - Các kết quả so sánh giữa việc phân cụm theo thuật toán cổ điển K-means và phân cụm theo thuật toán phân cụm cân bằng, sự ổn định hơn của các cluster khi áp dụng bước hậu xử lí sau khi áp dụng thuật toán phân cụm cân bằng cũng sẽ được trình bày cụ thể. - D) Phương pháp nghiên cứu Luận văn sử dụng phương pháp nghiên cứu các mô hình lí thuyết về các thuật toán phân cụm cổ điển để làm cơ sở cho thuật toán chính là phân cụm cân bằng là một thuật toán mang tư tưởng mới mẻ và có nhiều ứng dụng trong thực tế. - Ngoài ra, việc cài đặt phần mềm ứng dụng theo giải thuật phân cụm cân bằng cũng rất được chú trọng, các kết quả thu được từ phần mềm ứng dụng đã phản ánh đúng lí thuyết thông qua các số liệu cụ thể và cũng rất trực quan. - E) Kết luận Như vậy, luận văn cao học này đã cho chúng ta thấy một cái nhìn tổng quan về khái niệm phân cụm, ý nghĩa rất quan trọng của nó trong các hoạt động của con người cùng các ứng dụng rộng rãi như nhận dạng mẫu, phân tích dữ liệu, xử lý ảnh, nghiên cứu thị trường … Có rất nhiều các thuật toán phân cụm cổ điển nhưng phổ biến nhất và mang nhiều ý nghĩa trong luận văn nhất là thuật toán K-means, do đó, luận văn đi khá sâu vào tìm hiểu kĩ giải thuật K-means cùng các ưu nhược điểm của nó, tiến tới thiết lập bước cơ sở cho mục đích nghiên cứu về thuật toán phân cụm cân bằng của luận văn. - Thật vậy, một số ứng dụng khai phá dữ liệu đòi hỏi rằng các cụm mà ta thu được phải được cân bằng, ví dụ, cùng có kích thước hoặc độ quan trọng ngang nhau. - Trong luận văn này, chúng tôi tìm hiểu chi tiết và cài đặt thử nghiệm giải thuật phân cụm thỏa mãn các ràng buộc cân bằng dựa trên kích thước cụm được phát triển bởi các tác giả Arindam Banerjee và Joydeep Ghosh [1]. - Theo đó tiến trình phân cụm dữ liệu được chia nhỏ thành 3 bước. - Lấy mẫu một tập hợp nhỏ các điểm đại diện Phân cụm dữ liệu mẫu thành các cụm khởi tạo Phân phối (populating) những cụm khởi tạo đó với phần dữ liệu còn lại, tuân theo điều kiện lọc (refining) Tập dữ liệu đầu vào được dùng để cài đặt giải thuật là các điểm ATM có trong bản đồ Hà Nội từ nguồn OpenStreetMap. - Tuy nhiên, để thu được các kết quả tốt hơn nữa, luận văn có đề xuất thêm một bước hậu xử lí nằm ngoài thuật toán. - Cuối cùng, luận văn đã đi sâu vào nghiên cứu và cài đặt thành công giải thuật phân cụm cân bằng là một giải thuật phức tạp, khó cài đặt đặc biệt là các giải thuật ở bước thứ ba: phân phối và lọc – pha đóng góp chủ yếu vào tư tưởng của thuật toán
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt