Phân cụm k-means

Phân cụm k-means là 1 phương pháp lượng tử hóa vector dùng để phân các điểm dữ liệu cho trước vào các cụm khác nhau. Phân cụm k-means có nhiều ứng dụng, nhưng được sử dụng nhiều nhất trong Trí tuệ nhân tạo và Học máy (cụ thể là Học không có giám sát).

Lịch sử

Thuật ngữ " k -means" được James MacQueen sử dụng lần đầu tiên vào năm 1967,  mặc dù ý tưởng này quay trở lại Hugo Steinhaus vào năm 1956.  Thuật toán tiêu chuẩn được đề xuất lần đầu tiên bởi Stuart Lloyd của Bell Labs vào năm 1957 như một kỹ thuật cho điều chế mã xung, mặc dù nó không được xuất bản dưới dạng một bài báo cho đến năm 1982.  Năm 1965, Edward W. Forgy đã công bố về cơ bản cùng một phương pháp, đó là lý do tại sao nó đôi khi được gọi là Lloyd-Forgy

Mô tả chung

Thuật toán k-means sử dụng phương pháp tạo và cập nhật trung tâm để phân nhóm các điểm dữ liệu cho trước vào các nhóm khác nhau. Đầu tiên chúng sẽ tạo ra các điểm trung tâm ngẫu nhiên. Sau đó gán mỗi điểm trong tập dữ liệu vào trung tâm gần nó nhất. Sau đó chúng sẽ cập nhật lại trung tâm và tiếp tục lặp lại các bước đã kể trên. Điều kiện dừng của thuật toán: Khi các trung tâm không thay đổi trong 2 vòng lặp kế tiếp nhau. Tuy nhiên, việc đạt được 1 kết quả hoàn hảo là rất khó và rất tốn thời gian, vậy nên thường người ta sẽ cho dừng thuật toán khi đạt được 1 kết quả gần đúng và chấp nhận được

Thuật toán chi tiết

Thuật toán k-means có thể được chia thành các bước như sau:

Bước 1: Tạo các trung tâm ngẫu nhiên

${\displaystyle \mathbb {C} ^{(0)}=\left\{m_{1}^{(0)},\ m_{2}^{(0)},\ \dots ,\ m_{k}^{(0)}\right\}}$

Bước 2: Gán các điểm dữ liệu vào các cụm

Với mỗi điểm dữ liệu, ta sẽ tính khoảng cách của nó tới các trung tâm (bằng Khoảng cách Euclid). Ta sẽ gán chúng vào trung tâm gần nhất. Tập hợp các điểm được gán vào cùng 1 trung tâm sẽ tạo thành cụm.

${\displaystyle \mathbb {S} _{i}^{(t)}=\left\{x_{p}:\parallel x_{p}-m_{i}^{(t)}\parallel ^{2}\leq \parallel x_{p}-m_{j}^{(t)}\parallel ^{2}\right\},\ \forall j,\ 1\leq j\leq k}$

Bước 3:Cập nhật trung tâm

Với mỗi cụm đã tìm được ở bước 2, trung tâm mới sẽ là trung bình cộng của các điểm dữ liệu trong cụm đó.

${\displaystyle m_{i}^{(t+1)}={\frac {1}{\left\vert \mathbb {S} _{i}^{(t)}\right\vert }}\sum _{x\in \mathbb {S} _{i}^{(t)}}x_{j}}$

Thuật toán sẽ lặp lại các bước trên cho tới khi đạt được kết quả chấp nhận được.

Ứng dụng

K-means được sử dụng nhiều trong máy học (học không giám sát) để phân nhóm dữ liệu. Chúng cũng thường được dùng trong phân vùng ảnh

Tham khảo

• Triển khai với python
• Triển khai với c++