Chương 1. Khái quát về phân cụm 1.1 Khái quát về bài toán phân cụm dữ liệu Không giống sự phân loại và sự dự đoán dùng để phân tích lớp đối tượng, phân loại theo lớp, sự phân cụm phân tích đối tượng dữ liệu mà không tham chiếu đến các lớp đã được phân loại trước [1]. Nói chung, các lớp đã phân loại trước không xuất hiện trong dữ liệu có sẵn. Sự phân cụm có thể được sử dụng để tạo ra các lớp.
Bài toán phân cụm có thể được phát biểu như sau: Cho một tập các đối tượng cho trước, yêu cầu phân các đối tượng trên thành các cụm sao cho các đối tượng trong cùng một nhóm là tương đối giống nhau, các đối tượng trong các nhóm khác nhau là rất khác nhau. Nói cách khác, các đối tượng được phân cụm dựa trên nguyên lý của sự cực đại hóa sự giống nhau trong lớp và tối thiểu hóa sự giống nhau giữa các lớp. Mỗi cụm được hình thành có thể được xem như một lớp của các đối tượng, mà từ đó có thể tạo ra các luật. Ví dụ, phân cụm có thể thực hiện trên dữ liệu khách hàng để nhận ra những tập khách hàng đồng nhất.
Những cụm này có thể biểu diễn các nhóm đích riêng biệt cho việc quảng cáo.1 chỉ ra cụm 2-D của khách hàng ở trong một thành phố. Ba cụm của điểm dữ liệu rất rõ ràng.1: Một phần nhỏ của dữ liệu khách hàng về các vị trí khách hàng trong một thành phố, chỉ ra ba phân cụm dữ liệu, Mỗi trung tâm phân cụm được đánh dấu ‘+’ [1] Phân cụm là một lĩnh vực nghiên cứu đầy thách thức, trong đó, các ứng dụng tiềm năng của nó đưa ra những đòi hỏi riêng. Sau đây là các yêu cầu đặc trưng của phân cụm: Tính mở rộng: nhiều thuật toán khai phá dữ liệu làm việc tốt trên những tập dữ liệu chứa ít đối tượng; tuy nhiên, một cơ sở dữ liệu lớn thường chứa hàng triệu đối tượng, đòi hỏi những thuật toán có khả năng mở rộng cao Khả năng khám phá các phân cụm với các hình dạng ngẫu nhiên: nhiều thuật toán phân cụm xác định các cụm dựa trên đại lượng khoảng cách Euclidean hoặc Manhattan. Những thuật toán dựa trên đại lượng khoảng cách này thường tìm LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 được các cụm hình cầu với kích thước và mật độ tương tự nhau.
Tuy nhiên, một cụm có thể có bất kì hình dạng nào khác. Cần phải phát triển một thuật toán phát hiện cụm với hình dạng khác nhau. Các yêu cầu tối thiểu cho tri thức miền để xác định các tham số đầu vào: nhiều thuật toán đòi hỏi người dùng phải đưa tham số đầu vào (ví dụ như số cụm). Kết quả phân cụm có thể là rất nhậy cảm đối với tham số đầu vào.
Các tham số đầu vào thường khó xác định, đặc biệt là đối với các đối tượng nhiều chiều. Khả năng làm việc với dữ liệu nhiễu: hầu hết dữ liệu trên thế giới chứa những thành phần bên ngoài hoặc dữ liệu bị thiếu hụt, bị lỗi, một số thuật toán nhạy cảm với những loại dữ liệu trên dẫn tới việc phân cụm nghèo nàn. Khả năng phân cụm tăng dần và không nhạy cảm với trình tự bản ghi đầu vào: một số thuật toán phân cụm không thể kết hợp dữ liệu thêm mới (nghĩa là, dữ liệu cập nhật) vào trong các cấu trúc phân cụm đang tồn tại, và do đó phải xác định một sự phân cụm mới từ đầu. Một số thuật toán phân cụm nhạy cảm với trình tự dữ liệu đầu vào.
Điều này quan trọng đối với các thuật toán phân cụm tăng dần và thuật toán không nhạy cảm với thứ tự đầu vào. Số chiều lớn: một cơ sở dữ liệu hoặc kho dữ liệu có thể chứa một số chiều hoặc các thuộc tính. Nhiều thuật toán phân cụm dùng tốt cho dữ liệu ít chiều, bao gồm chỉ hai hoặc ba chiều. Mắt con người dùng tốt cho việc đánh giá lên đến ba chiều.
Tìm kiếm các phân cụm của các đối tượng dữ liệu trong không gian nhiều chiều là một thách thức. Sự phân cụm dựa trên ràng buộc: các ứng dụng trong thế giới thực có thể cần sự phân cụm dưa trên nhiều loại ràng buộc khác nhau. Gỉa sử rằng công việc của bạn là tìm ra vị trí lựa chọn để đặt máy ATM, để quyết định việc này, bạn phải phân cụm và xem xét vị trí, đường cao tốc, kiểu của khách hàng trên cụm…. Tính thông dịch và hữu dụng: người dùng mong muốn kết quả phân cụm được thông dịch, hiểu và sử dụng được.
Đó là, phân cụm cần được kết hợp với sự thông dịch ngữ nghĩa và các ứng dụng. Điều quan trọng là nghiên cứu làm thế nào một mục đích ứng dụng có thể tác động lên sự lựa chọn của các đặc tính phân cụm và các phương pháp.2 Một số phương pháp phân cụm điển hình 1.1 Các phương pháp phân vùng Cho một cơ sở dữ liệu của n đối tượng hoặc dòng dữ liệu, một phương pháp phân cụm tạo ra k cụm của dữ liệu, trong đó mỗi vùng biểu diễn một cụm, và k n. Phương LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 pháp này phân chia dữ liệu vào k nhóm, đáp ứng những yêu cầu sau: (1) mỗi nhóm phải chứa ít nhất một đối tượng và, (2) mỗi đối tượng phải thuộc duy nhất một nhóm [1]. Chú ý rằng yêu cầu thứ hai có thể bỏ qua trong một số kĩ thuật được miêu tả ở phần dưới.
Đưa ra k là số lượng cụm để xây dựng, một phương thức phân cụm cần khởi tạo cụm. Sau đó sử dụng một kĩ thuật định vị trí lặp lại để cố gắng tăng sự cụm bằng cách rời các đối tượng từ một nhóm tới một nhóm khác. Tiêu chuẩn chung của một sự phân cụm tốt là các đối tượng trong cùng vùng là gần giống hoặc liên quan đến những đối tượng khác, trong khi các đối tượng của các cụm khác nhau lại rất khác nhau. Có rất nhiều kiểu tiêu chuẩn dành cho việc đánh giá chất lượng cụm.
Để có được sự tối ưu toàn diện trong cụm dựa trên sự phân cụm sẽ đòi hỏi số lượng cực lớn của mọi sự phân cụm có thể. Thay vào đó, hầu hết các ứng dụng chấp nhận một trong hai phương pháp heuristic phổ biến: thuật toán k-means, nơi mỗi cụm được biểu diễn bởi giá trị trung bình của các giá trị trong cụm; và thuật toán k-medoids, trong đó mỗi cụm được biểu diễn bởi một trong các đối tượng gần trung tâm của cụm. Các phương thức cụm heuristic này làm việc tốt khi tìm kiếm các cụm hình cầu trong cơ sở dữ liệu nhỏ hoặc trung bình. Khi tìm kiếm các cụm với hình dạng phức tạp và cho tập dữ liệu lớn, các phương pháp phân cụm trên cần phải mở rộng.
Phương pháp k-means Thuật toán k-means có tham số đầu vào k, và phân một tập n đối tượng thành k cụm sao cho các đối tượng trong một cụm là tương đối giống nhau còn các đối tượng giữa các cụm lại có sự khác biệt khá rõ [1]. Sự giống nhau trong cụm được đánh giá theo giá trị trung bình của các đối tượng trong đoạn, còn có thể được xem như là “trung tâm của trọng lực” của cụm. Thuật toán xử lý như sau: Đầu tiên, nó ngẫu nhiên lựa chọn k các đối tượng mà mỗi đối tượng đại diện cho một trung bình hay trung tâm phân đoạn. Đối với mỗi đối tượng còn lại, một đối tượng được gán cho một cụm mà giống nó nhất, dựa trên khoảng cách giữa đối tượng và trung bình của đoạn.
Nó sau đó sẽ tính trung bình mới cho mỗi đoạn. Xử lý này được lặp lại tới tận khi hàm tiêu chuẩn hội tụ. Thường hàm hội tụ sau được sử dụng: Trong đó x là điểm trong không gian biểu diễn đối tượng đưa ra, mi là trung bình của cụm C i (cả x và mi là đa chiều). Hàm này cố gắng tạo ra k cụm phân biệt nhau tới mức có thể.
Thủ tục k trung bình được tổng kết ở hình bên dưới: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 Thuật toán k means: Đầu vào: Số cụm k, và một cơ sở dữ liệu chứa n đối tượng Đầu ra: Một tập k cụm với trọng tâm của mỗi cụm Thủ tục 1. Lựa chọn ngẫu nhiên k đối tượng là trọng tâm khởi tạo của k cụm 2. Gán mỗi đối tượng vào cụm có trọng tâm giống nhất đối tượng nhất so với các cụm khác 2. Cập nhật lại trọng tâm của các cụm, trong đó tọa độ của trọng tâm bằng giá trị trung bình tọa độ các đối tượng trong cụm.
Cho đến khi giá trị hàm mục tiêu không thay đổi Thuật toán cố gắng xác định k cụm mà tối thiểu hóa hàm mục tiêu đưa ra. Phương thức này có khả năng mở rộng và hoạt động hiệu quả trong khi xử lý các tập dữ liệu lớn bởi vì độ phức tạp tính toán của thuật toán là O (knt), trong đó n là tổng số đối tượng, k là số cụm, và t là số lần lặp lại, thông thường k <<n và t<<n. Phương thức thường kết thúc ở một sự tối thiểu cục bộ.2: Quá trình phân cụm tập điểm thành 3 cụm theo k-means [1] Phương pháp k-medoids Thuật toán k-means với đối tượng khác biệt (đối tượng có sự khác biệt so với phần lớn các đối tượng trong tập) bởi vì một đối tượng với giá trị rất lớn có thể thay đổi sự phân phối dữ liệu. Làm thế nào thay đổi thuật toán để làm giảm bớt sự nhạy cảm như vậy? Thay cho việc lấy giá trị trung bình của các đối tượng trong một phân cụm như điểm tham chiếu, chúng ta có thể lấy những đối tượng thực để biểu diễn phân cụm, sử dụng một đối tượng biểu diễn một phân cụm.
Mỗi đối tượng đang tồn tại được phân cụm với đối tượng biểu LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 diễn mà giống nó nhất. Phương pháp phân cụm được thực hiện dựa trên nguyên lý tối thiểu tổng của sự khác biệt giữa mỗi đối tượng và điểm tham chiếu của nó. Đó là, một chuẩn lỗi-tuyệt đối (absolute-error criterion) được dùng như sau: k E | p o | j j 1 pc J Trong đó E là tổng lỗi tuyệt đối của mọi đối tượng trong tập dữ liệu; p là điểm trong không gian biểu diễn một đối tượng đưa ra trong phân cụm C j ; và oj là đối tượng biểu diễn của C j. Nói chung, trạng thái lặp đến tận khi mỗi đối tượng biểu diễn thực sự là medoid, hoặc đối tượng nằm ở trung tâm Xem xét trạng thái phân cụm k-medoid.