Phân cụm K-Means — Thuật toán và cách hoạt động

Phân cụm k-means là một cách nhóm dữ liệu số thành $k$ cụm. Nếu bạn chọn $k$ và dùng phiên bản Euclid tiêu chuẩn, thuật toán sẽ lặp lại một vòng: gán mỗi điểm vào tâm gần nhất, rồi dời mỗi tâm đến giá trị trung bình của các điểm được gán cho nó.

Nói đơn giản, nó cố gắng làm cho các điểm trong cùng một nhóm nằm gần nhau và các điểm ở những nhóm khác nhau nằm xa nhau hơn. Nó nhanh và hữu ích, nhưng chỉ hoạt động tốt khi các "nhóm" đó khá gọn và khoảng cách thực sự có ý nghĩa.

K-means đang tối ưu điều gì

Trong dạng Euclid tiêu chuẩn, k-means cố gắng làm cho các điểm bên trong mỗi cụm nằm gần tâm cụm đó nhất có thể. Một hàm mục tiêu phổ biến là

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

Ở đây, $C_j$ là cụm thứ $j$ và $\mu_j$ là tâm cụm của nó.

Đây là tổng bình phương sai số trong cụm. Giá trị càng nhỏ thì các điểm được gán càng nằm chặt quanh tâm cụm của chúng.

Hàm mục tiêu đó giải thích hai phần của thuật toán:

• Nếu các tâm cụm được giữ cố định, cách tốt nhất là gán mỗi điểm cho tâm cụm gần nhất.
• Nếu việc gán đã cố định, tâm cụm tốt nhất là giá trị trung bình của các điểm được gán.

Đó là lý do quy tắc cập nhật không hề tùy ý. Từ "means" trong k-means chính là trung bình cộng theo đúng nghĩa đen.

Thuật toán k-means hoạt động như thế nào

Vòng lặp thông thường rất ngắn:

1. Chọn $k$ tâm cụm ban đầu.
2. Gán mỗi điểm cho tâm cụm gần nhất.
3. Tính lại mỗi tâm cụm bằng trung bình của các điểm được gán cho nó.
4. Lặp lại cho đến khi việc gán không còn thay đổi hoặc mức cải thiện rất nhỏ.

Quá trình này thường hội tụ nhanh, nhưng không nhất thiết cho ra cách phân cụm tốt nhất có thể. Các tâm cụm khởi tạo khác nhau có thể dẫn đến các kết quả cuối cùng khác nhau, nên bước khởi tạo rất quan trọng.

Ví dụ phân cụm k-means từng bước

Xét các điểm dữ liệu một chiều sau:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

Giả sử ta muốn $k = 2$ cụm và bắt đầu với các tâm cụm tại $1$ và $10$. Đây là một ví dụ hay vì các tâm cụm thực sự thay đổi sau lần cập nhật đầu tiên.

Bước 1: gán điểm vào tâm cụm gần nhất

Các điểm $1, 2, 3$ gần $1$ hơn.

Các điểm $10, 11, 12$ gần $10$ hơn.

Vì vậy các cụm là

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

Bước 2: cập nhật các tâm cụm

Tâm cụm mới của cụm thứ nhất là

$$\mu_1 = \frac{1+2+3}{3} = 2$$

Tâm cụm mới của cụm thứ hai là

$$\mu_2 = \frac{10+11+12}{3} = 11$$

Cả hai tâm cụm đều đã dịch chuyển, từ $1$ sang $2$ và từ $10$ sang $11$.

Bước 3: gán lại

Bây giờ hãy kiểm tra lại tâm cụm gần nhất bằng cách dùng $2$ và $11$.

Các điểm $1, 2, 3$ vẫn thuộc cụm thứ nhất, còn các điểm $10, 11, 12$ vẫn thuộc cụm thứ hai. Vì việc gán không còn thay đổi nữa, thuật toán đã hội tụ.

Đây là một ví dụ gọn gàng vì dữ liệu tự nhiên tách thành hai nhóm chặt. Các bộ dữ liệu thực tế thường lộn xộn hơn, và đó là lúc k-means có thể bắt đầu khiến bạn hiểu sai.

Khi nào k-means hoạt động tốt

K-means hoạt động tốt nhất khi các điều kiện sau đúng ở mức tương đối:

• Các đặc trưng là dữ liệu số.
• Khoảng cách Euclid là cách hợp lý để đo độ giống nhau.
• Các cụm khá gọn, không quá dài hoặc cong.
• Các đặc trưng đã được chuẩn hóa để một biến không lấn át các biến còn lại.

Nếu các điều kiện đó không thỏa mãn, kết quả đầu ra vẫn có thể trông gọn gàng nhưng lại bỏ lỡ cấu trúc thật của dữ liệu.

Những lỗi thường gặp với k-means

Xem k-means như một phương pháp phân cụm dùng được cho mọi trường hợp

K-means hoạt động tốt nhất khi các cụm khá gọn và giá trị trung bình là một cách tóm tắt hợp lý. Nó không phải là lựa chọn mặc định tốt cho mọi bộ dữ liệu.

Bỏ qua việc chuẩn hóa đặc trưng

Nếu một đặc trưng được đo trên thang lớn hơn nhiều so với đặc trưng khác, đặc trưng đó có thể chi phối phép tính khoảng cách. Chuẩn hóa hoặc đưa các đặc trưng về cùng thang đo thường rất quan trọng trước khi chạy k-means.

Giả sử đáp án là duy nhất

K-means có thể hội tụ đến các cực tiểu cục bộ khác nhau từ các điểm khởi tạo khác nhau. Đó là lý do người ta thường chạy lặp lại nhiều lần hoặc dùng các phương pháp như khởi tạo k-means++.

Dùng đặc trưng không phải số hoặc được mã hóa kém

Vì tâm cụm là giá trị trung bình, k-means tiêu chuẩn được xây dựng cho các biến số. Nếu một đặc trưng là biến phân loại, việc lấy trung bình cộng có thể không có ý nghĩa.

Dùng cho các cụm có dạng phi cầu rõ rệt

Nếu các nhóm thật sự dài, cong hoặc có mật độ rất không đều, k-means có thể tách một nhóm tự nhiên thành hai hoặc gộp hai nhóm khác nhau lại. Phương pháp này ưu tiên các cụm gọn dựa trên tâm cụm.

Quên rằng ngoại lệ có thể kéo lệch tâm cụm

Vì tâm cụm là giá trị trung bình, các giá trị cực đoan có thể làm chúng dịch chuyển đáng kể. Nếu dữ liệu của bạn có ngoại lệ quan trọng, hãy kiểm tra điều này trước khi tin vào kết quả.

Phân cụm k-means được dùng ở đâu

K-means thường được dùng để nhóm dữ liệu thăm dò, phân khúc khách hàng hoặc hành vi, lượng tử hóa màu ảnh, và làm mốc cơ bản nhanh trong học không giám sát.

Nó hữu ích nhất khi bạn có các đặc trưng số, muốn một mô hình đơn giản và nhanh, và kỳ vọng các cụm tương đối gọn trong không gian Euclid.

Một mô hình hình dung đơn giản

Hãy tưởng tượng đặt $k$ chiếc ghim có thể di chuyển trên một biểu đồ phân tán. Mỗi điểm sẽ bám vào chiếc ghim gần nhất. Sau đó mỗi chiếc ghim trượt đến vị trí trung bình của các điểm đang bám vào nó. Lặp lại như vậy cho đến khi các chiếc ghim hầu như không còn di chuyển.

Hình dung đó không chỉ là trực giác. Nó gần như chính là toàn bộ thuật toán.

Hãy thử một bài toán phân cụm tương tự

Lấy một tập nhỏ các điểm trên một đường thẳng, chọn $k = 2$, rồi tự làm bằng tay một chu kỳ gán-cập nhật đầy đủ. Sau đó thay đổi các tâm cụm ban đầu hoặc thêm một điểm ngoại lệ để xem kết quả thay đổi ra sao. Nếu muốn đi thêm một bước, hãy thử phiên bản của riêng bạn trên một bộ dữ liệu nhỏ và so sánh điều gì xảy ra trước và sau khi chuẩn hóa đặc trưng.