K-means là gì

  -  

Bài 15: Thuật Toán K-Means Clustering

Bài này sẽ hướng dẫn bạn tìm hiểu thuật toán thuộc nhóm Unsupervised Learning đầu tiên, đó là K-Means Clustering.

Bạn đang xem: K-means là gì

Bạn đang xem: K-means là gì

K-Means Clustering là thuật toán Machine Learning phổ biến để phân cụm dữ liệu.

Mở đầu

Nhắc lại khái niệm về Unsupervised Learning đã nói đến trong bài mở đầu. Trong thuật toán Unsupervised Learning, chúng ta cũng được cung cấp các bộ input nhưng không có output. Thuật toán Unsupervised Learning không hề biết dữ liệu nó còn trả về sẽ như thế nào bởi nó không được cung cấp các ví dụ như ở Supervised Learning. Bằng cách nào đó Unsupervised Learning cần tự tìm ra cấu trúc dữ liệu để thực hiện nhiệm vụ nào đó.

Thuật toán Clustering là một loại của nhóm thuật toán Unsupervised Learning. Trong đó các dữ liệu ban đầu được phân thành cụm dựa trên vị trí tương đối của chúng so với nhau. Trong hình dưới đây, một cách định tính ta có thể thấy các dữ liệu có thể phân thành 3 cụm.


*

K-Means Clustering là thuật toán thường được sử dụng để giải quyết các bài toán phân cụm như vậy.

Thuật toán K-Means Clustering

Mô hình toán học

Ta gọi điểm tại vị trí trung bình của tất cả các điểm dữ liệu trong một cụm là trung tâm cụm. Như vậy, nếu có K cụm thì sẽ có K trung tâm cụm và mỗi trung tâm cụm sẽ nằm gần các điểm dữ liệu trong cụm tương ứng hơn các trung tâm cụm khác.

Trong hình dưới đây, K = 3 và ta có 3 trung tâm cụm là các điểm màu vàng.


*

Để phân cụm dữ liệu bằng K-Means Clustering, trước hết ta chọn K là số cụm để phân chia và chọn ngẫu nhiên K trong số m dữ liệu ban đầu làm trung tâm cụm $\mu_{1}, \mu_{2}, …, \mu_{K}$. 

Sau đó, với điểm dữ liệu $x^{(i)}$ ta sẽ gán nó cho cụm $c^{(i)}$ là cụm có trung tâm cụm gần nó nhất.

$c^{(i)} = argmin_{k} \lVert x^{(i)} - \mu_{k} \lVert^{2}$

Khi tất cả các điểm dữ liệu đã được gán về các cụm, bước tiếp theo là tính toán lại vị trí các trung tâm cụm bằng trung bình tọa độ các điểm dữ liệu trong cụm đó.

$\mu_{k} = \frac{1}{n}(x^{(k_{1})} + x^{(k_{2})} + … + x^{(k_{n})})$

với $k_{1}, k_{2}, …, k_{n}$ là chỉ số các dữ liệu thuộc cụm thứ k.

Các bước trên được lặp lại cho tới khi vị trí các trung tâm cụm không đổi sau một bước lặp nào đó.

Xem thêm: Vũ Trần Kim Nhã Chuyển Giới, Kim Nhã Bb&Ampbg Chuyển Giới


*

Độ chính xác của thuật toán

$J(c^{(1)}, …, c^{(m)}, \mu_{1}, …, \mu_{K}) = \frac{1}{m}\sum_{i=1}^{m}\lVert x^{(i)} - \mu_{c^{(i)}} \lVert^{2}$

Nghiệm của thuật toán K-Means Clustering

Trong các bước của thuật toán, thực chất bước gán các điểm dữ liệu về trung tâm cụm gần nhất và bước thay đổi trung tâm cụm về vị trí trung bình của các điểm dữ liệu trong cụm đều nhằm mục đích giảm hàm mất mát. Thuật toán kết thúc khi vị trí các trung tâm cụm không đổi sau một bước lặp nào đó. Khi đó hàm mất mát đạt giá trị nhỏ nhất.

Khi K càng nhỏ so với m, thuật toán càng dễ đi đến kết quả chưa phải tối ưu. Điều này phụ thuộc vào cách chọn K trung tâm cụm ban đầu.


*

Để khắc phục điều này, ta cần lặp lại thuật toán nhiều lần và chọn phương án có giá trị hàm mất mát nhỏ nhất.

Tóm tắt thuật toán K-Means Clustering

Yêu cầu

Cho trước m bộ dữ liệu $x^{(1)}, x^{(2)}, …, x^{(m)}$. Nhiệm vụ của ta là phân chia các điểm dữ liệu thành K cụm dựa trên vị trí tương đối của chúng so với nhau.

Thuật toán

Bước 1: Chọn ngẫu nhiên K trong số m điểm dữ liệu làm trung tâm cụm $\mu_{1}, \mu_{2}, …, \mu_{K}$.

Bước 2: Gán mỗi điểm dữ liệu về cụm có trung tâm cụm gần nhất.

$c^{(i)} = argmin_{k} \lVert x^{(i)} - \mu_{k} \lVert^{2} $

Bước 3: Di chuyển các trung tâm cụm về vị trí trung bình của các điểm dữ liệu trong cụm tương ứng.

$\mu_{k} = \frac{1}{n}(x^{(k_{1})} + x^{(k_{2})} + … + x^{(k_{n})})$

Bước 4: Lặp lại hai bước trên tới khi vị trí các trung tâm cụm không đổi sau một bước lặp nào đó.

Bước 5: Lặp lại tất cả các bước trên một số lần và chọn phương án có hàm mất mát nhỏ nhất.

Xem thêm: Cấu Hình Máy Tính Chơi Game 20 Triệu, Cấu Hình Máy Tính

$ argmin_{c^{(1)}, …, c^{(m)}, \mu_{1}, …, \mu_{K}}J(c^{(1)}, …, c^{(m)}, \mu_{1}, …, \mu_{K})$

Bạn đang nghĩ gì?

K-Means Clustering là thuật toán đơn giản và phổ biến, được biết đến như một trong những thuật toán Unsupervised Learning được sử dụng nhiều nhất.

Theo bạn, khác biệt giữa thuật toán K-Means Clustering so với những thuật toán loại Supervised Learning mà bạn đã học là gì?

«Bài 14: Ứng Dụng Thuật Toán Neural Network Bài 16: Ứng Dụng Thuật Toán K-Means Clustering»