Thuật toán phân cụm

Các thuật toán phân cụm phân chia dữ liệu thành các nhóm gồm các mục tương tự, tiết lộ cấu trúc tự nhiên mà không cần sử dụng bất kỳ nhãn nào.

Definition

Phân cụm là việc phân chia không giám sát một tập dữ liệu thành các nhóm sao cho các điểm trong một nhóm tương tự nhau hơn so với các điểm trong các nhóm khác, trong đó sự tương tự được định nghĩa bởi một tiêu chí khoảng cách hoặc mật độ được chọn cho ứng dụng.

Scope

Chủ đề này bao gồm các họ chính của phân cụm: các phương pháp dựa trên tâm cụm như k-means, phân cụm phân cấp kết tụ xây dựng một cây các nhóm lồng nhau, các phương pháp dựa trên mật độ tìm các cụm có hình dạng tùy ý, và việc lựa chọn các thước đo khoảng cách và số lượng cụm. Nó đề cập đến điều gì tạo nên một phân cụm tốt và tại sao vấn đề này vốn dĩ mơ hồ.

Core questions

• Điều gì tạo nên một tập hợp các điểm thành một cụm?
• K-means giảm thiểu phương sai trong cụm một cách lặp lại như thế nào?
• Số lượng cụm được chọn như thế nào?
• Khi nào các phương pháp phân cấp hoặc dựa trên mật độ vượt trội hơn các phương pháp dựa trên tâm cụm?

Key theories

k-means và thuật toán của Lloyd

k-means giảm thiểu tổng bình phương khoảng cách đến các tâm cụm bằng cách xen kẽ việc gán các điểm cho các tâm gần nhất và tính toán lại các tâm, một thủ tục hội tụ đến một cực tiểu cục bộ.

Phân cụm phân cấp

Phân cụm kết tụ liên tục hợp nhất các nhóm gần nhất để xây dựng một biểu đồ cây (dendrogram), đưa ra các phân cụm ở mọi mức độ chi tiết và tránh nhu cầu cố định số lượng cụm trước.

Phân cụm mô hình hỗn hợp

Việc coi các cụm là các thành phần của một hỗn hợp xác suất cho phép gán mềm và các cụm có hình dạng và kích thước khác nhau, kết nối phân cụm với ước lượng mật độ biến tiềm ẩn.

Clinical relevance

Phân cụm là nền tảng của phân khúc thị trường, tổ chức tài liệu và hình ảnh, nhóm biểu hiện gen và phát hiện dị thường, đồng thời là một công cụ chính của phân tích dữ liệu thăm dò; vì các phân cụm phụ thuộc vào khoảng cách và số lượng nhóm đã chọn, kết quả phải được diễn giải cẩn thận thay vì được coi là một sự thật cơ bản duy nhất.

History

Thủ tục k-means có nguồn gốc từ công trình lượng tử hóa năm 1957 của Lloyd, được xuất bản năm 1982, và từ công thức độc lập của MacQueen. Phân cụm phân cấp xuất hiện trong phân loại số học, và các phương pháp dựa trên mật độ như DBSCAN đã mở rộng phân cụm sang các nhóm có hình dạng tùy ý, cùng nhau tạo thành bộ công cụ tiêu chuẩn của nhóm không giám sát.

Key figures

• Stuart Lloyd
• James MacQueen
• Trevor Hastie

Seminal works

• lloyd1982
• hastie2009
• bishop2006

Frequently asked questions

Tại sao k-means yêu cầu chọn số lượng cụm?

k-means tối ưu hóa vị trí của một số lượng tâm cố định, vì vậy số lượng đó là một đầu vào. Việc chọn nó dựa vào các phương pháp heuristic như phương pháp khuỷu tay (elbow method), điểm số silhouette, hoặc kiến thức chuyên môn, vì việc thêm nhiều cụm hơn luôn làm giảm khoảng cách trong cụm.

Các phương pháp phân cụm khác nhau có thể đưa ra các câu trả lời khác nhau không?

Có. Vì không có một định nghĩa duy nhất về một cụm, các phương pháp dựa trên tâm cụm, phân cấp và dựa trên mật độ có thể tạo ra các phân vùng khác nhau của cùng một dữ liệu, mỗi phân vùng hợp lệ theo tiêu chí riêng của nó. Lựa chọn đúng đắn phụ thuộc vào hình dạng cụm mong đợi và mục tiêu.