Sử dụng python phân cụm k-means

Vào một buổi chiều ngẫu hứng, các thành viên trong CLB AI gạ gẫm nhau rất tài Bi-a. Để rồi không ai chấp nhận “trình” mình thua ai, vì thế thì bạn đã đặt vấn đề xuất dữ liệu thu thập 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 bài toán phân cụm cụm (Phân cụm). Đó là K-means Clustering

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

• I. K-means Clustering là gì?
• II. Ý tưởng và bài toán dữ liệu
• III. Phân tích toán học
• IV. Xây dựng thuật toán Python
• V. Thảo luận về bài toán K-mean
• VI. Ứng dụng của K-means trong bài toán nén ảnh

Nếu bạn không muốn khoảng 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, lướt qua nếu bạn không có hứng thú. Time thì bắt đầu nào

I. K-means Clustering là gì ?

1. Thế nào là phân cụm?

Phân cụm (hay cụm 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ụm từ) 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 các thành viên trong nhóm khác

( Nguồn ảnh. dữ liệu. 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 sọt. dựa vào đặc điểm của kết quả hoa 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? . 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ả) thành các cụm (giỏ vặn) phù hợp.

2. K-nghĩa là phân cụm

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;

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à bài toán dữ liệu

1. Ý tưởng

Với mỗi đối tượng, chúng ta sẽ vector hóa biểu tượng đặc trưng của đối tượng dưới dạng một điểm dữ liệu. 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 đó, cụm phân cụm bài toán của ta sẽ là bài toán đi tìm những điểm dữ liệu nằm gần nhau

( Nguồn ảnh. chuyên viên máy tính. tổ chức)

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. Đầu vào và đầu ra của bài toán

2. 1. Đầu vào

Đầu vào thuật toán bao 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 . ( \(d \) is a number of property).
– Giá trị \(K \in N^{*};K

2. 2. đầu ra

Đầu ra của thuật toán bao 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 . \(y_{ik}=1 \) khi đối tượng thuộc cụm thứ \( K \), đảo ngược \( y_{ik} =0 \)

2. 3. Bài toán minh hoạ

To easy easy in the step of the parsing next. Từ câu chuyện Bi-a ở đầu, ta mô hình hóa thành bài toán minh họa sau để xây dựng và tìm hiểu nên thuật toán K-means

Bộ dữ liệu bao gồm 2 trường đặc trưng là tổng số bi bị đánh vào lỗi 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 đang muốn chia các cơ thủ trên các nhóm “chuyên nghiệp”, “tay mơ”, “tước 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ỗi; . Thêm một chút kiến ​​thức về Vocabulary không đúng

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

\ .
 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 Euclid

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à\( \ .
\( 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. máy họccoban. com )

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

2. 1. mất mát hàm

Giả sử ta có điểm dữ liệu \(x_i\) cần phân cụm vào \(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 .

To dễ dàng khai triển, trong bài viết này mình sử dụng tối tiểu bình bình Euclid \( {\parallel m_k – x_i \parallel}^2 \).
Vì     \( x_i \)   Thuộc      \( m_k \)  nên \( y_{ik}=1 \) làm điều đó \( {\parallel m_k -x_i \parallel}^2=y_{ .
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 .
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_{ . argmin là đối số của tối thiểu)
(Trong đó: argmin là arguments of the minimum)

Cuối cùng vẫn là học toán học

2. 2. Mất mát chức năng tối ưu

\( J(y,m) \) là hàm khó tìm nghiệm tối ưu toàn cục do ta có điều kiện biến  là số nguyên. Để giải quyết chức năng 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 thấy các cụm từ, cụm từ xác định 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 từ của từng điểm dữ liệu, xác định tâm cụm từ 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ụ vớ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 bước nhảy hay không ?

Đương nhiên rồi, hãy thử nhìn vào biểu thức \( (∗) \)nhé, hàm số ta bị chặn dưới 0 và là hàm không tăng sau mỗi bước sẽ hội tụ sau hữu hạn bước nhảy. Giờ thì làm rõ các 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_ .
Khi đó hàm tối ưu bị mất mát lúc này chính là tìm kiếm  \( {j}={argmin}{{\parallel m_j – x_i \parallel}^2 }\).
Và hàm mất tối ưu khi \( x_i \) gần \( m_j \) hơn.

Nên có thể kết luận “từng đ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 co đị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} .

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

\( \nabla(m)={2\sum\limits_{i=1}^Ny_{ij}{\parallel m_j -x_i \parallel}}=0 \) \( \Longleftrightarrow \) \
\( \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ì công 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 cụm tâ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 bản 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 để thực hiện 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 từ có tâm gần nó nhất.
  \( {j}={argmin}{{\parallel m_j – x_i \parallel}^2} \)
• Bước 3. Cập nhật cụm từ tâm trí 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 cụm từ tâ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 họa trên Numpy và so sánh với scikit-learning

2. 1. Xây dựng trên Numpy

Ban đầu dữ liệu biểu tượng

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

Create start function K cluster 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 từ 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ật lại cụm từ tâ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)

And here is results

2. 2. Sử dụng thư viện scikit-learning

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

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

Tạo nhãn cho từng dữ liệu

kmeans.labels_

Xong rồi đó, chỉ với 2 dòng mã

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

And here is results

Nhận xét. Các thuật toán cho cùng một 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 tra lại kết quả với mã tại đây nhé

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

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-nghĩa là thực hiện phân cụm tốt mà không cần biết nhãn dữ liệu bắt đầ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 K không phải là dễ dàng, khi đó K-means sẽ không hiệu quả
• K-means không chắc chắn đã tìm được bằng chứng tối ưu toàn cục. Và trải nghiệm cuối cùng phụ thuộc hoàn toàn vào việc khởi tạo các cụm từ ban đầu
• K-means sẽ không ảnh hưởng nếu các cụm chêch Sự chênh lệch về 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

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

1. description

Mục tiêu của công 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 pixel ma trận, với số lượng là hữu hạn. Khi đó ta có thể giảm số lượng màu của ảnh đi theo 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-mean sẽ giải quyết được như yêu cầu này

2. Xây dựng mô hình

Cứ nhập thư viện trước tiên

Nhập 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à chuyển đổi ảnh vector

________số 8

Get the image size and number of color

# 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) 

Đào tạo công việc phân cụm bằng Kmeans

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

0

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

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

1

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

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

2

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

Lời kết

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

Series về Machine Learning của CLB AI 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