[Machine Learning] So tài cơ thủ với K-means Clustering

Ngắm nhan sắc nữ hoàng billiards đẹp nhất Hàn Quốc

Chào mừng bạn đọc đã quay trở lại với chuỗi bài viết về Machine Learning.

Vào một buổi chiều ngẫu hứng, các thành viên trong CLB AI gạ kèo nhau so tài Bi-a. Để rồi không ai chấp nhận “trình” mình thua ai, vì thế một bạn đã đề xuất thu thập dữ liệu và xây dựng một mô hình K-Means để giải quyết. Vậy mô hình “K-means” đó là gì ?

Với các bài trước, các bạn đã được tìm hiểu 2 thuật toán là Liner Regression và Logistic Regression. Ở bài viết này, chúng ta sẽ cùng tiếp cận và tìm hiểu một thuật toán đầu tiên trong lớp bài toán Clustering (Phân cụm). Đó là K-means Clustering!!!

Tổng quan nội dung bài viết:

Nếu bạn không muốn tốn thời gian để hiểu mặt toán học, bạn có thể bỏ qua phần III. Phần IV và VI của mình chủ yếu là build code, hãy lướt qua nếu bạn không có hứng thú! Giờ thì bắt đầu nào!!!

I. K-means Clustering là gì ?

1. Thế nào là clustering ?

Clustering (hay phân cụm) là nhiệm vụ phân chia một tập hợp các đối tượng (hay thành viên) thành các nhóm (hay các cụm) khác nhau dựa trên đặc điểm (hay thuộc tính) của đối tượng. Và rằng các thành viên của một nhóm sẽ có nhiều điểm tương đồng hơn so với những thành viên trong nhóm khác.

(Nguồn ảnh: dataaspirant.com)

Ví dụ: Mẹ bạn có một thùng hoa quả lớn (nho, dưa , dâu, cam, …) và yêu cầu bạn xếp vàp 2 giỏ đựng. Dựa vào các đặc điểm của hoa quả như màu sắc, hình dáng, vị ngọt, … Ở đây bạn có thể dựa vào đặc điểm nhiều hay ít hạt để phân chia. Rất dễ dàng bạn sẽ làm được ngay!
Bạn biết không? Việc làm đó chính là phân cụm. Bạn sẽ phải dựa vào các đặc điểm (nhiều hay ít hạt) mà phân chia các đối tượng (hoa quả) vào các cụm (giỏ đựng) phù hợp.

2. K-means Clustering

Thực tiễn cho thấy, các vấn đề về phân cụm phát sinh trong nhiều ứng dụng khác nhau: khai thác dữ liệu, khám phá kiến ​​thức; nén dữ liệu và lượng tử hóa vectơ; nhận dạng mẫu và phân loại mẫu.

Là một trong những thuật toán cơ bản và phổ biến của Machine Learning – K-means Clustering là một thuật toán Unsupervised (Học không giám sát) đơn giản. Mục tiêu của bài toán là phân tách chính xác các đối tượng trong tập dữ liệu thành các nhóm dựa trên thuộc tính của đối tượng.

II. Ý tưởng và dữ liệu bài toán

1. Ý tưởng

Với mỗi đối tượng, chúng ta sẽ vector hoá để biểu diễn đặc trưng của đối tượng dưới dạng một data point. Và ta biết rằng, những điểm dữ liệu tương đồng về bản chất thì sẽ ở gần nhau hơn. Khi đó, bài toán phân cụm của ta sẽ là bài toán đi tìm những data point nằm gần nhau.

(Nguồn ảnh: geekforgeeks.org)

Mỗi đối tượng đều có một hoặc nhiều thuộc tính riêng. K-means chính là dựa vào một số thuộc tính cụ thể mà đi gom cụm lại những đối tượng có tính chất tương đồng nhau

2. Input và Output của bài toán

2.1. Input

Đầu vào thuật toán gồm:
– Một ma trận \( X = [x_1,x_2,x_3,…,x_N] \in R^{d*N} \), trong đó \( N \) là số lượng phần tử của dataset, mỗi đối tượng \( x_i \) chính là 1 datapoint biểu diễn bởi 1 vector \( d \) chiều. ( \(d \) là số lượng thuộc tính).
– Giá trị \(K \in N^{*};K<N\) là số cụm cần phân nhóm.

2.2. Output

Đầu ra của thuật toán gồm:
– Ma trận \( M=[m_1,m_2,..,m_K]∈R^{d∗K}\) chỉ tâm của mỗi cụm.
– Ma trận \( Y=[y_1,y_2,y_3,…,y_N]∈R^{N∗K};y_{ij}∈ {0,1} \) Với mỗi đối tượng \(x_i\) sẽ trả về nhãn \(y_i \) tương ứng: \(y_{ik}=1 \) khi đối tượng thuộc cụm thứ \( K \), ngược lại \( y_{ik} =0 \)

2.3. Bài toán minh hoạ

Để dể dàng trong các bước phân tích tiếp theo. Từ câu chuyện Bi-a ở đầu, ta mô hình hoá thành bài toán minh hoạ sau để xây dựng và tìm hiểu nên thuật toán K-means

Dataset gồm 2 trường đặc trưng là tổng số bi được đánh vào lỗ và số lần đánh trúng liên tiếp của 24 người sau nhiều “trận chiến”. Và bây giờ bạn ấy muốn chia các cơ thủ trên vào các nhóm “pro”, “tay mơ”, “kẻ tầm thường”.

( Đây là dữ liệu demo của 7 người)

Trong thuật ngữ Billiards: Pot là hành động đánh trúng vào lỗ; Break là chuỗi đánh thành công liên tục. Thêm một chút kiến thức về Vocabulary đúng không nào!

Xét bài toán minh hoạ:
– \(N=24; d=2; X=[x_1,x_2,x_3,…,x_9,x_{10}]\)

\begin{align*}
 X=  \begin{bmatrix}        50&48&13&…\\        8&7&2&…    
\end{bmatrix}
\end{align*}

– \(K=3\) ứng với 3 nhóm cần xác định là “pro”, “kẻ tầm thường”, “tay mơ”.

III. Phân tích toán học


Cũng như các thuật toán trước, liệu rằng khía cạnh toán học của K-means được tiếp cận ra sao. Có phức tạp hay dễ dàng hơn, hãy cùng nhau phân tích ở mục này nhé!!

1. Khoảng cách Eucild

Ta biết với 2 vector \( A(x_1;y_1) \) và \( B(x_2;y_2) \) trong không gian 2 chiều \( Oxy \)  thì khoảng cách giữa chúng là  \( \parallel x – y \parallel \) có giá trị độ lớn 
\( d_{AB} = \sqrt{(x_1-x_2)^2 +(y_1-y_2)^2} \)
Khoảng cách này được gọi là khoảng cách Euclid.


(Nguồn ảnh: machinelearningcoban.com )

2. Hàm mất mát và phương pháp tối ưu

2.1. Hàm mất mát

Giả sử ta có điểm dữ liệu \(x_i\) cần phân vào cụm \(m_k\).
Khi đó ta có vector sai số giữa 2 điểm là \((m_k – x_i)\)
Để thuật toán chính xác thì \(x_i\) gần với \(m_k\), hay ta mong muốn vector sai số phải gần với vector không.

Để dễ dàng khai triển, trong bài viết này mình sử dụng tối thiểu bình phương Euclid \( {\parallel m_k – x_i \parallel}^2 \).
Vì   \( x_i \)  thuộc   \( m_k \)  nên \( y_{ik}=1 \) do đó \( {\parallel m_k -x_i \parallel}^2=y_{ik}{{\parallel m_k-x_i \parallel}^2}={\sum\limits_{j=1}^ky_{ij}{\parallel m_j -x_i \parallel}^2} \)
Vậy ta có hàm sai số trung bình cho toàn bộ dữ liệu \( N \) điểm là:
\( {L(y,m)}={\dfrac{1}{N}}{\sum\limits_{i=1}^N}{\sum\limits_{j=1}^ky_{ij}{\parallel m_j -x_i \parallel}^2} \)
Giải giải quyết bài toán, ta cần giải quyết tối ưu ràng buộc:
\( {J(y,m)}=argmin{\dfrac{1}{N}}{\sum\limits_{i=1}^N}{\sum\limits_{j=1}^ky_{ij}{\parallel m_j -x_i \parallel}^2}(*) \)
(Trong đó: argmin là arguments of the minimum)

Cuối cùng vẫn là tìm nghiệm toán học

2.2. Tối ưu hàm mất mát

\( J(y,m) \) là hàm khó để tìm nghiệm tối ưu toàn cục bởi ta có điều kiện biến  là số nguyên. Để giải quyết hàm mất mát này, mình sẽ sử dụng đến kĩ thuật đan xen, nghĩa là:

  • Giả sử đã tìm được các tâm cụm, xác định cụm cho mỗi điểm dữ liệu để hàm mất mát là nhỏ nhất. (Cố định \( m \), tìm\( y \) )
  • Giả sử đã biết cụm của từng điểm dữ liệu, xác định tâm cụm mới để hàm mất mát là nhỏ nhất. (Cố định \( y \), tìm \( m \) )

Ta cứ làm xen kẽ như vậy đến khi hàm mất mát hội tụ tại giá trị nhỏ nhất.

Và một câu hỏi mới được đặt ra, liệu rằng hàm số có hội tu được sau hữu hạn bước nhảy hay không ?

Đương nhiên rồi, thử nhìn vào biểu thức \( (∗) \)nhé, hàm số ta bị chặn dưới bởi 0 và là hàm không tăng sau mỗi bước nên sẽ hội tụ sau hữu hạn bước nhảy. Giờ thì làm rõ kĩ thuật tối ưu nào.

1.   Cố định \( m \) , tìm \( y \)
Nếu cố định \(m\) thì coi \( {m=constant} \) , ta lại có \( {y_{ij} \in {0,1} }\).
Khi đó việc tối ưu hàm mất mát lúc này chính là tìm  \( {j}={argmin}{{\parallel m_j – x_i \parallel}^2 }\).
Và hàm mất mát tối ưu khi \( x_i \) gần \( m_j \) hơn. 

Nên có thể kết luận “mỗi điểm dữ liệu thuộc vào tâm cụm gần nó nhất.”

2.   Cố định \( y \), tìm \( m \):
Khi cố định \( y \) thì mục tiêu ta sẽ là tìm tối ưu của hàm \( {m_j}=argmin{\sum\limits_{i=1}^Ny_{ij}{\parallel m_j -x_i \parallel}^2} \).

Hàm \(m_i \) là hàm liên tục và có đạo hàm nên ta sẽ tối ưu bằng cách cho đạo hàm bằng không.

\( \nabla(m)={2\sum\limits_{i=1}^Ny_{ij}{\parallel m_j -x_i \parallel}}=0 \) \( \Longleftrightarrow \) \( \sum\limits_{i=1}^Ny_{ij}m_j \) \( ={\sum\limits_{i=1}^Ny_{ij}x_i} \)
\( \Rightarrow \) \( m_j= \) \( \frac{\sum\limits_{i=1}^Nx_iy_{ij}}{\sum\limits_{i=1}^Ny_{ij}} ={\frac{1}{N}} {\sum\limits_{i=1}^Nx_iy_{ij}} \)

Từ biểu thức trên ta có thể kết luận, tâm cụm \(m_i\) chính là trung bình cộng của các điểm trong cụm.

Dễ hiểu hơn thì việc xử lý toán học này là tìm ra những thằng gần nhau dựa vào khoảng cách của nó. Còn tâm cụm sẽ được đặt vào giữa cụm dữ liệu.

IV. Xây dựng thuật toán trên Python


1. Tóm tắt thuật toán và lưu đồ

Ta đã phân tích xong mặt toán học của K-means, mình sẽ tóm tắt lại thuật toán và xây dựng lưu đồ trong ngôn ngữ lập trình.

1.1 Tóm tắt thuật toán

  • Bước 1: Chọn ngẫu nhiên K điểm bất kì trong tập huấn luyện để làm các tâm cụm ban đầu.
  • Bước 2: Phân nhóm các điểm dữ liệu vào cụm có tâm gần nó nhất: 
    \( {j}={argmin}{{\parallel m_j – x_i \parallel}^2} \)
  • Bước 3: Cập nhập tâm cụm bằng cách lấy trung bình cộng của các điểm dữ liệu:
    \( m_j= \) \( \frac{\sum\limits_{i=1}^Nx_iy_{ij}}{\sum\limits_{i=1}^Ny_{ij}} \)  
  • Bước 4: Nếu tâm cụm ở bước 3 không thay đổi so với vòng lặp trước đó thì dừng thuật toán.
  • Bước 5: Quay lại bước 2.

1.2. Lưu đồ

2. Xây dựng bài toán minh hoạ trên Numpy và so sánh với scikit-learn

2.1. Xây dựng trên Numpy

Biểu diễn dữ liệu ban đầu.

Từ đồ thị phân bố dữ liệu trên, bạn hãy thử dự đoán và khoanh tròn 3 cụm để so sánh với Máy học nhé!

Tạo hàm khởi tạo K cụm ban đầu

# X là ma trận dữ liệu, n_cluster = K là số cụm 
def kmeans_init_centers(X, n_cluster):
  return X[np.random.choice(X.shape[0], n_cluster, replace=False)]

Tạo hàm phân chia dữ liệu vào các cụm gần nó nhất

def kmeans_predict_labels(X, centers):
  D = cdist(X, centers) #cdist là hàm tính khoảng cách
  return np.argmin(D, axis = 1) #argmin là trả về giá trị nhỏ nhất

Tạo hàm cập nhập lại tâm cụm

def kmeans_update_centers(X, labels, n_cluster):
  centers = np.zeros((n_cluster, X.shape[1]))
  for k in range(n_cluster):
    Xk = X[labels == k, :]
    centers[k,:] = np.mean(Xk, axis = 0) #mean là trả về giá trị trung bình cộng
  return centers

Khảo sát hội tụ (xem thử tâm cụm lúc này bằng tâm cụm trước đó hay chưa)

def kmeans_has_converged(centers, new_centers):
  return (set([tuple(a) for a in centers]) == 
      set([tuple(a) for a in new_centers]))

Giờ thì là hàm build K-means nhé

# Hàm xây dựng thuật toán K-means
def kmeans(init_centes, init_labels, X, n_cluster):
  centers = init_centes
  labels = init_labels
  times = 0
  while True:
    labels = kmeans_predict_labels(X, centers)
    kmeans_visualize(X, centers, labels, n_cluster, 
                     'Phân nhãn cho dữ liệu lần  ' + str(times + 1))
    new_centers = kmeans_update_centers(X, labels, n_cluster)
    if kmeans_has_converged(centers, new_centers):
      break
    centers = new_centers
    kmeans_visualize(X, centers, labels, n_cluster, 
                     'Update center lần ' + str(times + 1))
    times += 1 # Biến times của mình để xem việc update center xảy ra mấy lần
  return (centers, labels, times)

Và đây là kết quả

2.2. Sử dụng thư viện scikit-learn

Train K-means bằng thư viện

kmeans = KMeans(n_clusters = 3,
                n_jobs = -1,
                random_state = 123).fit(X)

Tạo label cho từng dữ liệu

kmeans.labels_

Xong rồi đấy, chỉ với 2 dòng code.

Python hỗ trợ các thư viện mạnh mẽ

Và đây là kết quả.

Nhận xét: Thuật toán cho cùng kết quả mong đợi khi xây dựng trên Numpy và sử dụng thư viện Sckit-learn

Bạn có thể thử kiểm chứng lại kết quả với code tại đây nhé!

V. Thảo luận về bài toán K-means

1. Ưu điểm

  • K-means là thuật toán đơn giản, dễ dàng sử dụng tốt cho các bài toán phân cụm.
  • K-means thực hiện phân cụm tốt mà không cần biết nhãn dữ liệu đầu vào. (Học không giám sát)
  • K-means là nền tảng cho nhiều thuật toán phức tạp sau này.

2. Nhược điểm

  • Số K cần được xác định trước. Ở nhiều bài toán, việc xác định được K không phải là dễ dàng, khi đó K-means sẽ không hiệu quả.
  • K-means không đảm bảo tìm được nghiệm tối ưu toàn cục. Và nghiệm cuối cùng phụ thuộc hoàn toàn vào việc khởi tạo các tâm cụm ban đầu.
  • K-means sẽ không hiệu quả nếu các cụm chêch lệch về số lượng điểm, phân bố dữ liệu không có dạng cầu, hay bài toán với 1 điểm dữ liệu có thể là con của 2 cụm.
This image has an empty alt attribute; its file name is fmyo2pb95wa41.jpg

VI. Ứng dụng K-means trong bài toán nén ảnh

1. Mô tả

Mục tiêu của việc nén hình ảnh là giảm kích thước bộ nhớ xuống càng nhỏ càng tốt trong khi vẫn duy trì sự tương đồng với hình ảnh gốc.

Mỗi hình ảnh đều được đặc trưng bởi một ma trận pixel, với lượng mà là hữu hạn. Khi đó ta có thể giảm số màu của ảnh đi đến một giá trị K nào đó, sao cho dung lượng ảnh giảm nhưng độ tương đồng vẫn giống ảnh gốc.

K-means sẽ giải quyết được nhu cầu này!!.

2. Xây dựng model

Cứ import thư viện trước tiên

Import thư viện nào !

#Hỗ trợ xXử lý ảnh 
from PIL import Image
from io import BytesIO
import webcolors

#Hỗ trợ phân tích dữ liệu
import math
import numpy as np 
import pandas as pd

#Hỗ trợ biểu diễn dữ liệu
import matplotlib.pyplot as plt
from importlib import reload
from mpl_toolkits import mplot3d
import seaborn as sns

#Train Model
from sklearn.cluster import KMeans

Đọc và vector hoá ảnh

#ĐỌC ẢNH
img = Image.open("./image_test.png")

#VECTOR HOÁ
#Đọc và in ra ma trận màu RGB của từng pixel
X = np.array(img.getdata()) 
print(X)
#Đọc và in ra thông số ảnh (wide, hight, dimensional  number)
img_size = X.reshape(*img.size, -1)
print('Shape:',img_size.shape)

Lấy kích thước ảnh và số lượng màu

# Hàm trả về kích thước ảnh
def image_ByteSize(img):
    img_file = BytesIO() 
    image = Image.fromarray(np.uint8(img))
    image.save(img_file, 'png')
    return int(img_file.tell()/1024)
img_size = image_ByteSize(img)
img_n_colors = len(set(img.getdata()))

print('Dung lượng ảnh:',img_size,'KB') 
print('Số lượng màu trong ảnh:',img_n_colors) 

Training việc phân cụm bằng Kmeans:

# Training việc phân cụm 
def replaceWithCentroid(kmeans):
    new_pixels = []
    for label in kmeans.labels_:
        pixel_as_centroid = list(kmeans.cluster_centers_[label])
        new_pixels.append(pixel_as_centroid)
    new_pixels = np.array(new_pixels).reshape(*img.size, -1)
    return new_pixels
new_pixels = replaceWithCentroid(kmeans)

Hàm vẽ ảnh sau khi nén

#vẽ ảnh sau khi nén:
def plotImage(img_array, size):
    reload(plt)
    plt.imshow(np.array(img_array/255).reshape(*size))
    plt.axis('off')
    return plt

Mình sẽ vẽ 9 ảnh với K=2 đến K=10:

range_k_clusters = (2,11)
kmeans_result = []
for k in range(*range_k_clusters):
    # CLUSTERING
    kmeans = KMeans(n_clusters = k,
                    n_jobs = -1,
                    random_state = 123).fit(X)
    
    # REPLACE PIXELS WITH ITS CENTROID
    new_pixels = replaceWithCentroid(kmeans)

Nhận xét: Ảnh sau khi nén có kích thước đã giảm, vẫn giữ được độ tương quan với ảnh gốc.

Lời kết

Machine learning: The future of digital marketing | AppsFlyer

Cảm ơn các bạn đọc đã cố gắng cùng mình tìm hiểu về thuật toán K-means ở bài viết này, hi vọng các bạn sẽ có thêm kiến thức mới về một trong những bài toán cơ bản của Marchine Learning. Mong rằng bạn có thể để lại góp ý cho bài viết, đó là động lực giúp mình và CLB cải tiến hơn cho những bài viết sau.

Chuỗi series về Machine Learning của CLB AI vẫn còn nhiều bài toán hay phía sau, cảm ơn và hẹn gặp lại các bạn!

References:


Tác giả: Nguyen Hoai Nam – KHNT2020

Leave a Reply

Your email address will not be published. Required fields are marked *