Bài toán phân cụm giải thuật và các ứng dụng

- BÀI TOÁN PHÂN CỤM Giải thuật và các ứng dụng Trường Đại học Bách khoa Hà nội Viện Công nghệ thông tin và Truyền thông CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tác giả luận văn: Nguyễn Hoàng Anh Đề tài luận văn: Bài toán phân cụm: giải thuật và các ứng dụng Chuyên ngành: Công nghệ thông tin Mã số SV: CB120053 Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày.
- Ngày 29 tháng 1 năm 2015 Giáo viên hướng dẫn Tác giả luận văn CHỦ TỊCH HỘI ĐỒNG Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 3 PHIẾU GIAO NHIỆM VỤ LUẬN VĂN CAO HỌC 1.
- Thông tin giao đề tài luận văn và cán bộ hướng dẫn: Họ và tên học viên: Nguyễn Hoàng Anh MSHV: CB120053 Tên đề tài: Bài toán phân cụm: giải thuật và các ứng dụng Mã đề tài: 2012BCNTT1-KT13 Hệ: Thạc sĩ kỹ thuật Chuyên ngành: Công nghệ thông tin Lớp: CNTT-1 Khóa: 2012B Cán bộ hướng dẫn: TS.
- Mục đích nội dung của LVCH  Tìm hiểu tổng quan các thuật toán phân cụm và các ứng dụng.
- Bài toán phân cụm cân bằng và ứng dụng.
- Cài đặt và thử nghiệm giải thuật phân cụm cân bằng.
- Các nhiệm vụ cụ thể của LVCH  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 Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 4 4.
- Lời cam đoan của học viên: Tôi - Nguyễn Hoàng Anh - cam kết LVCH là công sức đóng góp của bản thân tôi dưới sự hướng dẫn của TS Phạm Quang Dũng.
- Hà Nội, ngày 25 tháng 12 năm 2014 Tác giả LVCH Nguyễn Hoàng Anh 5.
- Xác nhận của cán bộ hướng dẫn về mức độ hoàn thành của LVCH và cho phép bảo vệ: Hà Nội, ngày 25 tháng 12 năm 2014 Cán bộ hướng dẫn Tiến sĩ Phạm Quang Dũng Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 5 TÓM TẮT NỘI DUNG LUẬN VĂN CAO HỌC 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ọc viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 6 hơn của các cụm 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ể.
- TỔNG KẾT ĐÁNH GIÁ TÀI LIỆU THAM KHẢO Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 7 Mục lục PHIẾU GIAO NHIỆM VỤ LUẬN VĂN CAO HỌC.
- Tổng quan về phân cụm.
- 11 Định nghĩa.
- 11 Ứng dụng.
- Chi tiết về phân cụm.
- 12 I.2.1 Khó khăn trong việc phân cụm.
- 12 I.2.2 Các kiểu phân cụm.
- 14 I.2.3 Các kiểu cụm.
- 16 I.2.4 Các kĩ thuật phân cụm.
- 17 Chương II : Thuật toán phân cụm cổ điển.
- 18 II.1.1 Cơ bản về thuật toán K-means.
- 20 Dữ liệu trong tọa độ Ơ-clit.
- 21 Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 8 Dữ liệu văn bản.
- 26 Điều khiển các cụm rỗng.
- 32 PHẦN 2 : PHÂN CỤM CÂN BẰNG.
- 34 Chương III : Bài toán phân cụm cân bằng.
- 34 Chương IV : Thuật toán phân cụm cân bằng.
- 40 IV.2 Phân cụm tập mẫu.
- 42 IV.3.1 Thuật toán phân phối.
- 43 IV.3.2 Thuật toán lọc.
- 46 Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 9 Chương V : Cài đặt thử nghiệm.
- 48 Dữ liệu bản đồ từ OpenStreetMap.
- 48 Thiết kế dữ liệu cho một điểm.
- 49 Xử lí nguồn dữ liệu bản đồ.
- 49 Hiển thị các cụm dữ liệu lên Google Map.
- 51 V.2.1 Thuật toán K-means.
- 53 V.2.2 Thuật toán phân cụm cân bằng.
- 53 Chia 3 cụm theo phân cụm cân bằng.
- 54 Chia 4 cụm theo phân cụm cân bằng.
- 60 Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 10 LỜI NÓI ĐẦU Sau một thời gian tìm hiểu và nghiên cứu rất nhiều các thuật toán phân cụm, em nhận thấy thuật toán phân cụm cân bằng là một thuật toán mang tư tưởng mới mẻ về ràng buộc số điểm nằm trong mỗi cụm là bằng nhau, thuật toán có tính ứng dụng cao trong đời sống hiện nay.
- Cụ thể như một công ty muốn phân công cho nhân viên của mình đi lấy dữ liệu khách hàng từ các trạm thông tin, khi đó bài toán đặt ra không chỉ là chia các trạm thành nhiều cụm mà số trạm trong một cụm cũng phải đều nhau.
- Mặc dù chưa phải tuyệt đối mĩ mãn như lí thuyết nhưng các kết quả chạy ứng dụng cài đặt thuật toán đã thu được một số thành công nhất định.
- Ngoài nỗ lực bản thân, em còn cần tới rất nhiều sự trợ giúp của nhiều người để có thể hoàn thành được luận văn cao học như ngày hôm nay.
- Cuối cùng em xin gửi lời cảm ơn tới gia đình đã luôn ở bên động viên và trợ giúp, nhất là luôn luôn tin tưởng vào cá nhân em, để em có thể hoàn thành được bản luận văn cao học của mình.
- Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 11 PHẦN I : CƠ SỞ LÍ THUYẾT Chương I : Giới thiệu chung I.1.
- Tổng quan về phân cụm Định nghĩa Phân cụm chia dữ liệu thành các nhóm (clusters) ý nghĩa hoặc hữu dụng.
- Mục đích là những đối tượng trong một nhóm sẽ tương đồng nhau và khác với các đối tượng trong nhóm khác.
- Sự tương đồng trong một nhóm càng lớn thì sự khác nhau giữa các nhóm càng lớn, như vậy là việc phân cụm tốt hơn, độc nhất hơn.
- Cụm (Cluster) là một nhóm các đối tượng có chung một số đặc điểm, đóng vai trò quan trọng trong cách con người phân tích và mô tả thế giới.
- Thực ra, con người có kĩ năng phân chia các đối tượng thành các cụm và gán các đối tượng đặc biệt vào các cụm này.
- Ứng dụng Kỹ thuật phân cụm có thể áp dụng trong rất nhiều lĩnh vực như : Marketing [2]: xác định các nhóm khách hàng (khách hàng tiềm năng, khách hàng giá trị, phân loại và dự đoán hành vi khách hàng.
- Do đó không ngạc nhiên khi từ trước đây họ đã làm việc với phân tích cụm để tìm ra thuật toán tự động tìm cấu trúc phân loại.
- Ngày nay, các Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 12 nhà sinh học áp dụng phân cụm để phân tích số lượng lớn thông tin di truyền ví dụ để tìm nhóm các gens có cùng chức năng.
- Bảo hiểm, tài chính [2]: Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch vụ tài chính, dự đoán xu hướng (trend) của khách hàng, phát hiện gian lận tài chính (identifying frauds) Truy xuất thông tin [2]: WWW bao gồm hàng tỉ các trang web, kết quả trả về theo một truy vấn máy tìm kiếm có thể trả lại hàng ngàn trang.
- Phân cụm có thể dùng để nhóm những kết quả này lại thành số ít các cụm, mỗi cái chứa một đặc tính cụ thể của truy vấn.
- Ví dụ, truy vấn :”movie” có thể được nhóm lại theo catalog là : reviews, trailers, stars … mỗi catalog (cụm) có thể chia nhỏ hơn thành các catalog con ( sub-cluster), tạo ra một cấu trúc phân cấp để hỗ trợ người dùng tìm kiếm kết quả.
- Chúng ta bắt đầu xem nhiều cách tiếp cận để chia các đối tượng thành tập các cụm và những kiểu khác nhau.
- Sau đó ta mô tả 3 kĩ thuật phân cụm cụ thể đại diện cho số lượng lớn thuật toán và minh họa cho một vài khái niệm : K-means, phân cụm phân cấp xếp đống và DBSCAN..
- Chi tiết về phân cụm Ở phần này sẽ cho chúng ta thấy định nghĩa rõ hơn về phân cụm, minh họa vì sao nó là khó khăn và giải thích mối quan hệ của nó với những kĩ thuật khác.
- Những cách khác nhau để nhóm một tập các đối tượng thành một tập các cụm  Các kiểu cụm.
- I.2.1 Khó khăn trong việc phân cụm Trong rất nhiều ứng dụng, khái niệm của một cụm không được định nghĩa tốt.
- Để hiểu rõ hơn về sự khó khăn của việc quyết định những gì tạo thành một cụm, xem hình 1: 20 điểm và 3 cách khác nhau để chia chúng thành các cụm: Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 13 Hình 1 [2].
- Các cách phân cụm khác nhau với cùng một tập điểm Hình dạng của khối đánh dấu các thành viên của cụm.
- Hình 1(b) và 1(d) chia dữ liệu thành 2 và 6 phần.
- Hình trên chứng minh rằng định nghĩa về một cụm là không chính xác và định nghĩa tốt nhất phụ thuộc vào bản chất của dữ liệu và kết quả mà ta mong muốn.
- Phân tích cụm liên quan tới các kĩ thuật chia các đối tượng dữ liệu thành các nhóm.
- Ví dụ, phân cụm có thể được xem như một phân loại trong đó nó tạo một nhãn cho các đối tượng.
- I.2.2 Các kiểu phân cụm Trong phần này chúng ta sẽ phân biệt các loại phân cụm [2.
- Toàn bộ (complete) với bộ phận (partial) Phân cấp và phân vùng Điểm khác biệt giữa những kiểu phân cụm được thảo luận nhiều nhất đó là : khi nào tập các cụm là lồng nhau (hierarchical – nested) hay không lồng nhau (partition - Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 14 unnested).
- Một partition đơn giản là một sự phân chia tập các đối tượng dữ liệu thành các tập con không chồng nhau (mỗi đối tượng dữ liệu chính xác nằm trong một tập con).
- Hình 1 b-d là phân cụm dạng partition.
- Mỗi nút là một cụm (trừ nút lá) là hợp của các con của nó ( subcluter) và gốc của cây chính là cụm tổng chứa toàn bộ các đối tượng.
- Cuối cùng, lưu ý một cây phân cấp có thể được xem như một chuỗi các phân vùng Partition và một phân vùng có thể được tách ra bằng cách lấy bất kì đoạn nào trong chuỗi phân vùng của cây phân cấp Hierarchical đó.
- Duy nhất, xếp chồng và mờ Hình 1 là tất cả là duy nhất: mỗi đối tượng được gắn với duy nhất 1 cụm.
- Nếu đối tượng có thể đồng thời gắn với nhiều hơn một cụm ta có dạng xếp chồng (overlapping hay non-exclusive).
- Ví dụ : một người ở trường đại học có thể vừa là sinh viên tham gia học vừa là nhân viên thuộc trường đó.
- Đối với phân cụm kiểu mờ (fuzzy) thì mọi đối tượng đều có một tỉ lệ nào đó thuộc về mọi cụm - tỉ lệ trọng số thành viên từ 0 tới 1.
- Toàn bộ và bộ phận Ở phân cụm kiểu toàn bộ thì mọi đối tượng được gắn vào một cụm, còn bộ phận thì không.
- I.2.3 Các kiểu cụm Mục đích chính của phân cụm là tìm ra các nhóm đối tượng có ích.
- Để mô phỏng Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 15 sự khác nhau giữa những kiểu của cụm [2], chúng ta dùng các điểm hai chiều như hình 2 Well-separated Tập các đối tượng mà trong đó mỗi đối tượng gần với những đối tượng trong cùng cụm hơn các đối tượng nằm khác cụm.
- Prototyped-Based Tập các đối tượng trong đó mỗi đối tượng gần với prototype định nghĩa ra cụm chứa nó hơn với protype của cụm khác.
- Ví dụ center-based cụm Graph-Based Nếu dữ liệu được biểu diễn dưới dạng đồ thị bao gồm các nút là các đối tượng và đường nối thì cụm sẽ được hiểu là các bộ phận được kết nối với nhau.
- Ví dụ : Cụm kề (contiguity-based clusters) trong đó hai đối tượng chỉ được nối với nhau khi chúng nằm trong phạm vi khoảng cách quy định của mỗi đối tượng.
- Có nghĩa là mỗi đối tượng nằm trong một Contiguity-based cluster sẽ gần với các đối tượng trong cùng cụm hơn bất cứ điểm nào ở cụm khác.
- Density-Based Một vùng dày đặc các đối tượng được bao quanh bởi một vùng ít dày đặc.
- Học viên : Nguyễn Hoàng Anh – CNTT1 – 2012B Page 16 Hình 2 [2].
- Các kiểu cụm khác nhau Shared-Property Tập các đối tượng mà có chung một vài đặc tính.
- Cách định nghĩa này bao hàm toàn bộ các định nghĩa về một cụm mà ta đã đề cập, ví dụ : các đối tượng trong một cụm hướng tâm có chung thuộc tính là chúng gần nhất với điểm trung tâm.
- Xem các cụm ở hình 2 (e) ta thấy : một cụm vùng tam giác kế cận với một vùng chữ nhật, và có hai vòng tròn quấn vào nhau, và cần một thuật toán rất chi tiết để nhận diện ra các vùng cụm này tuy nhiên rất phức tạp ( sang phạm trù nhận diện mẫu) nên chúng ta sẽ chỉ xem xét những kiểu cụm đơn giản hơn trong luận văn này.

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt