Với bài toán học phi giám sát, làm sao ta có thể sắp xếp dữ liệu vào các nhóm tương ứng? Bài viết này sẽ trình bày một phương pháp đơn giản để có thể thực hiện được việc này là phương pháp phân cụm K-Means.

Mục lục

1. Đặt vấn đề

Giả sử ta có một tập dữ liệu và ta cần phải nhóm các dữ liệu có tính chất tượng tự nhau vào các cụm khác nhau chưa biết trước. Một cách đơn giản để mô phỏng bài toán này là biểu diễn qua cái nhìn hình học. Các dữ liệu có thể coi là các điểm trong không gian và khoảng cách giữa các điểm có thể được coi là thông số mức độ giống nhau của chúng. 2 điểm càng gần nhau thì chúng càng giống nhau.

Grapical view of clustering

Với cách nhìn hình học như vậy, ta có thể viết lại bài toán dưới dạng hình thức như sau:

Dữ liệu: tập dữ liệu $\mathbf{X}\in\mathbb{R}^{nd}$ gồm $n$ điểm dữ liệu có $d$ chiều
Nhiệm vụ: phân tập dữ liệu ra làm $k$ cụm các dữ liệu tương tự nhau. Đương nhiên là $k\le n$.

Để giải quyết bài toàn này, người ta có thể dùng 1 phương pháp đơn giản là giải thuật K-Means mà ta sẽ cùng thảo luận trong bài viết này.

2. Giải thuật

2.1. Lý thuyết

Về cơ bản giải thuật được thực hiện như sau:

1. Khởi tạo
- Chọn ngẫu nhiên $k$ điểm bất kì làm điểm trung tâm $$\mathbb{C}^{(0)}=\{m_1^{(0)},m_2^{(0)},…,m_k^{(0)}\}$$
2. Nhóm dữ liệu
- Nhóm mỗi điểm dữ liệu vào 1 cụm có điểm trung tâm gần nhất với nó $$\mathbb{S}_i^{(t)}=\{x_p:\Vert{x_p-m_i^{(t)}}\Vert^2 \le \Vert{x_p-m_j^{(t)}}\Vert^2\} ~~~,\forall j,1 \le j \le k$$
- Nếu các cụm sau khi nhóm không thay đổi so với trước khi nhóm thì ta dừng giải thuật
3. Cập nhập trung tâm
- Với mỗi cụm sau khi nhóm lại, ta cập nhập lại điểm trung tâm của chúng bằng cách lấy trung bình cộng $$m_i^{(t+1)}=\frac{1}{\vert{\mathbb{S}_i^{(t)}}\vert} \sum_{x_j\in\mathbb{S}_i^{(t)}}x_j$$
- Quay lại bước 2

Để dễ hiểu hơn bạn có thể thao tác với mô phỏng dưới đây để xem thuật toán được thực thi thế nào nhé. Thao tác cơ bản như sau:

Bước 1: Tạo dữ liệu mô phỏng bằng nút Tạo dữ liệu với số điểm dữ liệu và số cụm tương ứng.
Bước 2: Sử dụng nút Tiếp theo để chạy một vòng lặp: 2. Nhóm dữ liệu ⇄ 3. Cập nhập trung tâm. Ngoài ra, bạn cũng có thể click ngay vào mà hình mô phỏng để chạy vòng lặp cực kì tiện lợi.
Bước 3: Nếu bạn muốn khởi động lại vòng lặp mà vẫn giữ nguyên tập dữ liệu hiện tại thì có thể sử dụng nút Khởi tạo lại.

N (số điểm dữ liệu):

K (số cụm):

Source: http://tech.nitoyon.com/ja/blog/2013/11/07/k-means/

Theo như mô phỏng ta có thể thấy, ban đầu các điểm trung tâm khởi tạo x sẽ được gắn một cách ngẫu nhiên. Sau mỗi vòng lặp thì màu của chúng được thay đổi và điểm trung tâm mới được cập nhập. Khi giải thuật thực hiện xong thì việc cập nhập thế này sẽ dừng lại.

2.2. Lập trình

Cũng như mọi lần trước, code đầy đủ tôi có để trên Github. Còn ở đây, tôi chỉ viết lại các phần chính.

kmeans.pykmeans.py

# Số nhóm K
K = 6
# Tạo dữ liệu gồm 1500 điểm quây tụ lại với K nhóm ở trên
from sklearn.datasets import make_blobs
X,_ = make_blobs(n_samples=1500,
               n_features=2,
               centers=K,
               cluster_std=0.5,
               shuffle=True,
               random_state=0)

# Các hàm thành phần thực hiện giải thuật
# 1. init center points
def init_centers(X, k):
    return X[np.random.choice(X.shape[0], k, replace=False)]

# 2. grouping
def group_data(X, centers):
    y = np.zeros(X.shape[0])
    for i in range(X.shape[0]):
        d = X[i] - centers
        d = np.linalg.norm(d, axis=1)
        y[i] = np.argmin(d)

    return y

# 3. Update center points
def update_centers(X, y, k):
    centers = np.zeros((k, X.shape[1]))
    for i in range(k):
        X_i = X[y==i, :]
        centers[i] = np.mean(X_i, axis = 0)
    return centers

# kmeans algorithm
def kmeans(X, k):
    centers = init_centers(X, k)
    y = []
    while True:
        # save pre-loop groups
        y_old = y
        # grouping
        y = group_data(X, centers)
        # break while loop if groups are not changed
        if np.array_equal(y, y_old):
            break

        #  update centers
        centers = update_centers(X, y, k)
    return (centers, y)

Đoạn mã trên sẽ cho kết quả như hình dưới đây:

K-Means Result with K=6

Về cơ bản, giải thuật gồm 3 phần chính như phần lý thuyết đề cập phía trên:

1. Khởi tạo K điểm trung tâm: init_centers(X, k)
2. Phân cụm dựa trên điểm trung tâm: group_data(X, centers)
3. Cập nhập lại các điểm trung tâm của mỗi cụm: update_centers(X, y, k)

Hi vọng là đoạn code này không quá khó hiểu. Nếu có đoạn nào chưa hiểu bạn cứ để lại câu hỏi ở bên dưới nhé.

3. Hạn chế và dị bản

3.1. Cần biết số nhóm trước

Dễ thấy rằng điều kiện đầu vào của giải thuật bắt buộc phải chỉ rõ giá trị của $k$, nhưng trong thực tế không phải lúc nào ta cũng có thể biết trước được có bao nhiêu nhóm cả. Vấn đề này có thể cải thiện dựa vào một số phương pháp sau:

Phương pháp Elbow
Phương pháp X-means

3.2. Khởi tạo ảnh hưởng tới chất lượng

Vị trí của các điểm khởi tạo có ý nghĩa lớn tới tốc độ và độ chính xác của thuật toán. Để phần nào khắc phục được tình trạng này, người ta có thể sử dụng một số cách như:

Chạy giải thuật nhiều lần với mỗi cách khởi tạo khác nhau và chọn lấy cách đưa ra kết quả tốt nhất
Sử dụng phương pháp khởi tạo K-Means++

[ML] Phân cụm K-Means (K-Means clustering)