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
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ệu1. Ý 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
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”
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ơ”.
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.
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]
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
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 Python1. 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
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ã
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-mean1. ư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
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
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ố 8Get 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ất0
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ất1
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ất2
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ếtCả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