Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thông báo: Download 4 khóa học Python từ cơ bản đến nâng cao tại đây.
Thuật toán K-Means Clustering trong Python
Trong bài hướng dẫn này, mình sẽ triển khai thuật toán K-Means Clustering bằng cách sử dụng các module Python cơ bản và thư viện numpy. Kèm theo đó là giải thích chi tiết giúp bạn hiểu khái niệm và toán học đứng sau thuật toán phân cụm phổ biến này.
Tổng quan Về K-Means trong Python
.png)
K-Means là thuật toán phân cụm đơn giản nhưng mạnh mẽ, thường được sử dụng để nhóm các điểm dữ liệu thành các cụm dựa trên tính tương đồng. Thuật toán hoạt động qua các bước chính:
- Chọn ngẫu nhiên K tâm cụm ban đầu.
- Phân bổ các điểm dữ liệu vào cụm gần nhất.
- Tính lại vị trí trung tâm của mỗi cụm.
- Lặp lại quá trình cho đến khi các trung tâm không còn thay đổi.
Dưới đây là mã nguồn đầy đủ, kèm theo chú thích chi tiết từng phần.
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(42)
def euclidean_distance(x1, x2):
"""Tính khoảng cách Euclidean giữa hai điểm."""
return np.sqrt(np.sum((x1 - x2)**2))
class KMeans:
def __init__(self, K=5, max_iters=100, plot_steps=False):
"""
Khởi tạo K-Means với:
- K: Số cụm cần phân chia.
- max_iters: Số vòng lặp tối đa để tối ưu cụm.
- plot_steps: Hiển thị quá trình tối ưu (tùy chọn).
"""
self.K = K
self.max_iters = max_iters
self.plot_steps = plot_steps
# Lưu danh sách chỉ số của các mẫu trong từng cụm
self.clusters = [[] for _ in range(self.K)]
# Lưu vị trí trung tâm của từng cụm
self.centroids = []
def predict(self, X):
"""
Áp dụng thuật toán K-Means lên dữ liệu X.
- Trả về nhãn cụm của từng mẫu trong dữ liệu.
"""
self.X = X
self.n_samples, self.n_features = X.shape
# Khởi tạo tâm cụm ngẫu nhiên
random_sample_idxs = np.random.choice(self.n_samples, self.K, replace=False)
self.centroids = [self.X[idx] for idx in random_sample_idxs]
# Tối ưu hóa các cụm
for _ in range(self.max_iters):
# Gán mỗi mẫu vào cụm gần nhất
self.clusters = self._create_clusters(self.centroids)
if self.plot_steps:
self.plot()
# Tính lại tâm cụm
centroids_old = self.centroids
self.centroids = self._get_centroids(self.clusters)
# Kiểm tra xem cụm có thay đổi không
if self._is_converged(centroids_old, self.centroids):
break
if self.plot_steps:
self.plot()
# Trả về nhãn cụm của các mẫu
return self._get_cluster_labels(self.clusters)
def _create_clusters(self, centroids):
"""
Gán mỗi mẫu vào cụm có tâm cụm gần nhất.
"""
clusters = [[] for _ in range(self.K)]
for idx, sample in enumerate(self.X):
centroid_idx = self._closest_centroid(sample, centroids)
clusters[centroid_idx].append(idx)
return clusters
def _closest_centroid(self, sample, centroids):
"""
Tìm tâm cụm gần nhất với mẫu.
"""
distances = [euclidean_distance(sample, point) for point in centroids]
return np.argmin(distances)
def _get_centroids(self, clusters):
"""
Tính vị trí tâm cụm mới dựa trên trung bình của các điểm trong cụm.
"""
centroids = np.zeros((self.K, self.n_features))
for cluster_idx, cluster in enumerate(clusters):
cluster_mean = np.mean(self.X[cluster], axis=0)
centroids[cluster_idx] = cluster_mean
return centroids
def _is_converged(self, centroids_old, centroids):
"""
Kiểm tra nếu tâm cụm không thay đổi so với lần trước.
"""
distances = [euclidean_distance(centroids_old[i], centroids[i]) for i in range(self.K)]
return sum(distances) == 0
def _get_cluster_labels(self, clusters):
"""
Gán nhãn cụm cho từng mẫu.
"""
labels = np.empty(self.n_samples)
for cluster_idx, cluster in enumerate(clusters):
for sample_idx in cluster:
labels[sample_idx] = cluster_idx
return labels
def plot(self):
"""
Hiển thị cụm và tâm cụm trong không gian 2D.
"""
fig, ax = plt.subplots(figsize=(12, 8))
for i, index in enumerate(self.clusters):
point = self.X[index].T
ax.scatter(*point)
for point in self.centroids:
ax.scatter(*point, marker="x", color='black', linewidth=2)
plt.show()
Phân tích mã nguồn
Tính khoảng cách Euclidean (euclidean_distance):
Bài viết này được đăng tại [free tuts .net]
- Tính độ dài giữa hai điểm bằng công thức Euclid.
Khởi tạo mô hình KMeans (__init__):
- Chỉ định số cụm (K), số lần lặp tối đa, và tùy chọn hiển thị quá trình tối ưu.
Tâm cụm ngẫu nhiên:
- Chọn ngẫu nhiên K điểm làm tâm cụm ban đầu.
Phân cụm (_create_clusters):
- Gán từng điểm vào cụm có tâm cụm gần nhất.
Cập nhật tâm cụm (_get_centroids):
- Tính trung bình các điểm trong cụm để cập nhật tâm.
Kiểm tra hội tụ (_is_converged):
- So sánh tâm cụm mới và cũ, dừng nếu không thay đổi.
Trực quan hóa (plot):
- Hiển thị cụm trong không gian 2D với các tâm cụm.
Ví dụ sử dụng
from sklearn.datasets import make_blobs # Tạo dữ liệu mẫu X, y = make_blobs(n_samples=300, n_features=2, centers=5, random_state=42) # Khởi tạo và huấn luyện mô hình K-Means kmeans = KMeans(K=5, max_iters=100, plot_steps=True) y_pred = kmeans.predict(X) # Hiển thị kết quả cuối kmeans.plot()
Kết bài
K-Means là thuật toán dễ hiểu nhưng rất hiệu quả trong phân cụm dữ liệu. Triển khai từ đầu giúp bạn hiểu rõ cơ chế hoạt động và tối ưu. Hy vọng bài viết đã cung cấp đầy đủ thông tin để bạn áp dụng thành thạo trong các dự án của mình!
