Computer Vision

[Image Classification] k-Means Clustering

Xin chào, trong bài viết này chúng ta sẽ tìm hiểu về k-Means Clustering – một thuật toán Unsupervised Learning được sử dụng rất phổ biến để phân nhóm dữ liệu.


TÌM HIỂU VỀ K-MEANS CLUSTERING

Với k-Means clustering, chúng ta có thể phân chia tập dữ liệu thành k nhóm (cluster) riêng biệt, trong đó mỗi cluster được đại diện bởi một trọng tâm (centroid). Trọng tâm của mỗi cluster chính là giá trị trung bình của tất cả các điểm thuộc về cluster đó.

Hình 1 – k-Means Clustering với k=3

Để mô tả thuật toán, chúng ta sử dụng các kí hiệu sau:

  • m là số lượng điểm dữ liệu;
  • K là số lượng cluster;
  • c^{(i)} là index của cluster mà instance x^{(i)} đang được nhóm vào, i \in [1,K];
  • \mu_{k} là trọng tâm của cluster k;

Cost function của k-Means Clustering:

J = \frac{1}{m} \Sigma^{m}_{i=1}\|x^{(i)}-\mu_{c^{(i)}}\|^2

Giải thuật:

  1. Chọn ngẫu nhiên K điểm bất kỳ trong tập dữ liệu làm “initial centroids” cho k clusters;
  2. Tính khoảng cách Euclidean của từng điểm dữ liệu đến K centroids và nhóm điểm dữ liệu đó với cluster có centroid gần nó nhất;
  3. Update trọng tâm của từng cluster centroid bằng cách lấy trung bình cộng tất cả các điểm đang được nhóm vào cluster đó;
  4. Lặp lại bước 2 và 3 cho đến khi đủ số vòng lặp.

Chú ý: số lượng cluster K được lựa chọn dựa trên mục đích của việc phân nhóm.

ÁP DỤNG K-MEANS CLUSTERING

Ở bài viết về Color Channel Statistics and Color Histograms chúng ta đã có một ví dụ sử dụng k-Means Clustering để phân loại các bức ảnh thiên nhiên, các bạn có thể tham khảo nếu cần.
Tuy nhiên trong Computer Vision, ứng dụng phổ biến nhất của k-Means Clustering là tạo codebook trong Bag-of-Visual Words (BOVW) model.


Như vậy chúng ta đã có cái nhìn cơ bản về thuật toán k-Means Clustering và ứng dụng của nó trong Computer Vision. Cảm ơn các bạn đã theo dõi bài viết.

Thân ái và quyết thắng.

Hãy để lại comment nếu có câu hỏi!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s