Một、Python triển khai k-means

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

# Để giảm số lần lặp, chúng ta nên khởi tạo tâm cụm trong phạm vi phân bố dữ liệu
def initialize_centroids(data, k):  # Định nghĩa hàm chọn ngẫu nhiên tâm cụm
    data_min = data.min() # Trả về giá trị nhỏ nhất của mỗi đặc trưng
    data_max = data.max() # Trả về giá trị lớn nhất của mỗi đặc trưng
    centroids = np.random.uniform(data_min, data_max, (k, data.shape[1])) # Tạo ngẫu nhiên K tâm cụm giữa giá trị lớn nhất và nhỏ nhất
    return centroids 

# Đóng gói thành hàm, tính khoảng cách từ một mẫu đến tất cả các tâm cụm và trả về khoảng cách nhỏ nhất cùng chỉ số tương ứng
def calculate_min_distance(sample, centroids):
    distances = np.sum(np.power((sample - centroids), 2), axis=1)  # Khoảng cách từ một mẫu đến tất cả các tâm cụm
    min_distance = distances.min() # Giá trị khoảng cách nhỏ nhất
    min_index = np.where(distances == min_distance)[0] # Chỉ số của khoảng cách ngắn nhất
    return min_distance, min_index



def kmeans_clustering(data, k):
    m, n = data.shape # Lấy số hàng và cột của tập dữ liệu
    centroids = initialize_centroids(data, k)
    
    # Thêm 3 cột bổ sung để lưu trữ thông tin khoảng cách và chỉ số cụm
    data_with_extra = np.zeros((m, 3))
    data_with_extra[:, 0] = np.inf
    data_with_extra[:, 1: 3] = -1
    data_extended = pd.concat([data, pd.DataFrame(data_with_extra)], axis=1)
    
    cluster_changed = True # Đặt biến điều khiển vòng lặp
    while cluster_changed: 
        cluster_changed = False # Đặt lại biến để tránh vòng lặp vô hạn
        for i in range(m): # Lặp qua từng mẫu trong tập dữ liệu
            min_dist, min_idx = calculate_min_distance(data_extended.iloc[i, :n].values, centroids) # Tính khoảng cách từ mẫu hiện tại đến k tâm cụm
            data_extended.iloc[i, n] = min_dist # Lưu khoảng cách nhỏ nhất vào cột thứ n
            # Lưu chỉ số cụm vào cột thứ n+1
            data_extended.iloc[i, n+1] = min_idx[0] 
        # Kiểm tra xem cột cuối cùng có thay đổi không, nếu có thì tiếp tục vòng lặp
        cluster_changed = not (data_extended.iloc[:, -1] == data_extended.iloc[:, -2]).all()
        # Tính toán lại tâm cụm
        if cluster_changed:
            new_centroids = data_extended.groupby(n+1).mean() # Tính trung bình cho mỗi cụm
            centroids = new_centroids.iloc[:, :n].values  # Gán giá trị trung bình làm tâm cụm mới
            data_extended.iloc[:, -1] = data_extended.iloc[:, -2] # Cập nhật chỉ số cụm hiện tại
            
    
    return centroids, data_extended

Hiệu quả như sau:

from sklearn.datasets import make_blobs # Nhập gói tạo tập dữ liệu

# Tạo tập dữ liệu mẫu
X, y = make_blobs(n_samples=500, n_features=2, centers=4, random_state=1)

plt.scatter(X[:, 0], X[:, 1]
            , marker='o' # Hình dạng điểm
            , s=8 # Kích thước điểm
           );

Biểu đồ phân bố tập dữ liệu:

Gọi thuật toán k-means tự viết để phân cụm:

centroids, clustered_data = kmeans_clustering(pd.DataFrame(X), 4)

plt.scatter(clustered_data.iloc[:, 0], clustered_data.iloc[:, 1], c=clustered_data.iloc[:, -1])
plt.scatter(centroids[:, 0], centroids[:, 1], c='r');

Kết quả vẫn rất tốt