13.1. Các bước của thuật toán k-Means Clustering¶

Trong thuật toán k-Means mỗi cụm dữ liệu được đặc trưng bởi một tâm (centroid). tâm là điểm đại diện nhất cho một cụm và có giá trị bằng trung bình của toàn bộ các quan sát nằm trong cụm. Chúng ta sẽ dựa vào khoảng cách từ mỗi quan sát tới các tâm để xác định nhãn cho chúng trùng thuộc về tâm gần nhất. Ban đầu thuật toán sẽ khởi tạo ngẫu nhiên một số lượng xác định trước tâm cụm. Sau đó tiến hành xác định nhãn cho từng điểm dữ liệu và tiếp tục cập nhật lại tâm cụm. Thuật toán sẽ dừng cho tới khi toàn bộ các điểm dữ liệu được phân về đúng cụm hoặc số lượt cập nhật tâm chạm ngưỡng.

Cụ thể các bước của thuật toán k-Means được tóm tắt như sau:

1.- Khởi tạo ngẫu nhiên \(k\) tâm cụm \(\mu_1, \mu_2, \dots, \mu_k\).

2.- Lặp lại quá trình cập nhật tâm cụm cho tới khi dừng:

a. Xác định nhãn cho từng điểm dữ liệu \(c_i\) dựa vào khoảng cách tới từng tâm cụm:

\[c_i = \arg \min_{j} \|\mathbf{x}_i - \mu_j \|_2^2\]

b. Tính toán lại tâm cho từng cụm theo trung bình của toàn bộ các điểm dữ liệu trong một cụm:

\[\mu_j := \frac{\sum_{i=1}^{n} \mathbf{1}(c_i = j) \mathbf{x}_i}{\sum_{i=1}^{n} \mathbf{1}(c_i = j)}\]

Trong công thức 2.a thì \(\|\mathbf{x}\|_2^2\) là bình phương của norm chuẩn bậc 2, kí hiệu là \(L_2\), norm chuẩn bậc 2 là một độ đo khoảng cách thường được sử dụng trong machine learning.

Trong công thức 2.b chúng ta sử dụng hàm \(\mathbf{1}(.)\), hàm này có giá trị trả về là 1 nếu nhãn của điểm dữ liệu \(c_i\) được dự báo thuộc về cụm \(j\), trái lại thì trả về giá trị 0. Như vậy tử số của vế phải trong công thức 2.b chính là tổng khoảng cách của toàn bộ các điểm dữ liệu nằm trong cụm \(j\) trong khi mẫu số chính là số lượng các điểm dữ liệu thuộc cụm \(j\). \(\mu_j\) chính là vị trí của tâm cụm \(j\) mà ta dự báo tại thời điểm hiện tại. Trong thuật toán trên thì tham số mà chúng ta cần lựa chọn chính là số lượng cụm \(k\). Thời điểm ban đầu ta sẽ khởi tạo \(k\) điểm dữ liệu một cách ngẫu nhiên và sau đó gán các tâm bằng giá trị của \(k\) điểm dữ liệu này. Các bước trong vòng lặp ở bước 2 thực chất là:

a. Gán nhãn cho mỗi điểm dữ liệu bằng với nhãn của tâm cụm gần nhất.

b. Dịch chuyển dần dần tâm cụm \(\mu_j\) tới trung bình của những điểm dữ liệu mà được phân về \(j\).

Bên dưới ta sẽ xây dựng một class KMean từ đầu để phân cụm dữ liệu. Hàm quan trọng nhất là fit() có tác dụng huấn luyện theo vòng lặp thuật toán KMean(). Hàm get_labels() được sử dụng để phân các điểm dữ liệu về đúng nhãn của cụm. Trong khi đó get_centroids() được sử dụng để xác định tâm của các cụm dựa trên nhãn. Hàm should_stop() có tác dụng kiểm tra điều kiện dừng của vòng lặp. Ở đây chúng ta sẽ dừng khi số lượng vòng lặp vượt quá max_iteration hoặc các centroids ngừng thay đổi.

import numpy as np
from sklearn.datasets import make_blobs


class KMeans():
  def __init__(self, k, max_iteration=10):
      self.k = k
      self.max_iteration = max_iteration
      self.all_centroids = []
      self.all_labels = []

  # Hàm thuật toán k-Means lấy đầu vào là một bộ dữ liệu và số lượng cluster k. Trẻ về tâm của k cụm
  def fit(self, dataSet):
      # Khởi tạo ngẫu nhiên k centroids
      numFeatures = dataSet.shape[1]
      centroids = self.get_random_centroids(numFeatures, self.k)
      self.all_centroids.append(centroids)
      self.all_labels.append(None)

      # Khởi tạo các biến iterations, oldCentroids
      iterations = 0
      oldCentroids = None
      
      # Vòng lặp cập nhật centroids trong thuật toán k-Means
      while not self.should_stop(oldCentroids, centroids, iterations):
          # Lưu lại centroids cũ cho quá trình kiểm tra hội tụ
          oldCentroids = centroids
          iterations += 1
          
          # Gán nhãn cho mỗi diểm dữ liệu dựa vào centroids
          labels = self.get_labels(dataSet, centroids)
          self.all_labels.append(labels)

          # Cập nhật centroids dựa vào nhãn dữ liệu
          # print('0ld centroids: ', centroids)
          centroids = self.get_centroids(dataSet, labels, self.k)
          # print('new centroids: ', centroids)
          self.all_centroids.append(centroids)
  
      return centroids

  # Hàm khởi tạo centroids ngẫu nhiên
  def get_random_centroids(self, numFeatures, k):
    return np.random.rand(k, numFeatures)
    # return np.array([[-5., -5.],
    #                  [4., 6.]])

  # Hàm này trả về nhãn cho mỗi điểm dữ liệu trong datasets
  def get_labels(self, dataSet, centroids):
      # Với mỗi quan sát trong dataset, lựa chọn centroids gần nhất để gán label cho dữ liệu.
      labels = []
      for x in dataSet:
        # Tính khoảng cách tới các centroids và cập nhận nhãn
        distances = np.sum((x-centroids)**2, axis=1)
        label = np.argmin(distances)
        labels.append(label)
      return labels
      
  # Hàm này trả về True hoặc False nếu k-Means hoàn thành. Điều kiện k-Means hoàn thành là 
  # thuật toán vượt ngưỡng số lượng vòng lặp hoặc centroids ngừng thay đổi
  def should_stop(self, oldCentroids, centroids, iterations):
      if iterations > self.max_iteration: 
        return True
      return np.all(oldCentroids == centroids)

  # Trả về toan độ mới cho k centroids của mỗi chiều.
  def get_centroids(self, dataSet, labels, k):
      centroids = []
      for j in np.arange(k):
        # Lấy index cho mỗi centroids
        idx_j = np.where(np.array(labels) == j)[0]
        centroid_j = dataSet[idx_j, :].mean(axis=0)
        centroids.append(centroid_j)
      return np.array(centroids)

dataset, _ = make_blobs(n_samples=250, cluster_std=3.0, random_state=123)

kmean = KMeans(k=2, max_iteration=8)
centroids = kmean.fit(dataset)

import matplotlib.pyplot as plt
from matplotlib.gridspec import GridSpec

gs = GridSpec(nrows=3, ncols=3)
plt.figure(figsize = (20, 20))
plt.subplots_adjust(wspace=0.2,hspace=0.4)
colors = ['green', 'blue']
labels = ['cluster 1', 'cluster 2']

for i in np.arange(len(kmean.all_centroids)):
  ax = plt.subplot(gs[i])
  if i == 0:
    centroids_i = kmean.all_centroids[i]
    plt.scatter(dataset[:, 0], dataset[:, 1], s=50, alpha=0.5, color='red')
    for j in np.arange(kmean.k):
      plt.scatter(centroids_i[j, 0], centroids_i[j, 1], marker='x', s=100, color='red')
    plt.title('All points in original dataset')
  else:
    # Lấy centroids và labels tại bước thứ i
    centroids_i = kmean.all_centroids[i]
    labels_i = kmean.all_labels[i]
    # Visualize các điểm cho từng cụm
    for j in np.arange(kmean.k):
      idx_j = np.where(np.array(labels_i) == j)[0]
      plt.scatter(dataset[idx_j, 0], dataset[idx_j, 1], color=colors[j], label=labels[j], s=50, alpha=0.3, lw = 0)
      plt.scatter(centroids_i[j, 0], centroids_i[j, 1], marker='x', color=colors[j], s=100, label=labels[j])
    plt.title(r'iteration {}'.format(i))

Hình 1: Sự dịch chuyển tâm của cụm sau mỗi vòng lặp. Thời điểm ban đầu hai tâm cụm được khởi tạo một cách ngẫu nhiên. Sau đó sau mỗi vòng lặp thì các nhãn được cập nhật lại tuỳ theo vị trí của chúng đối với tâm cụm. Tiếp tục cập nhật lại tâm cụm theo các nhãn dữ liệu mới. Cuối cùng thì thuật toán sẽ hội tụ khi tâm cụm ngừng thay đổi vị trí.

Trên sklearn chúng ta có thể dễ dàng huấn luyện thuật toán k-Means thông qua class KMeans của sklearn.cluster

from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=2, random_state=0)
kmeans.fit(dataset)
print('kmeans labels of 5 observation: ', kmeans.labels_[:5])
print('kmeans centroids: \n', kmeans.cluster_centers_)

kmeans labels of 5 observation:  [0 0 0 1 0]
kmeans centroids: 
 [[ 4.58876493 -3.13006162]
 [-4.99023469  0.44409831]]

Dự báo cụm cho một quan sát mới:

x = np.array([[5, 1]])
kmeans.predict(x)

array([0], dtype=int32)

Deep AI KhanhBlog

13.1. Các bước của thuật toán k-Means Clustering¶

13.2. Sự hội tụ của thuật toán k-Means clustering¶

13.3. Phương pháp Elbow trong lựa chọn số cụm¶

13.4. Biểu diễn dữ liệu đa chiều trên đồ thị¶

13.5. Hạn chế của k-Means¶

13.6. Online k-Means Clustering¶

13.7. Tổng kết¶

13.8. Bài tập¶

13.9. Tài liệu¶