【手撕算法系列】k-means

k-means算法介绍

K-means算法是一种用于聚类的迭代算法，它将数据集划分为K个簇，其中每个数据点属于与其最近的簇的中心。这个算法的目标是最小化簇内的平方和误差（簇内数据点与簇中心的距离的平方和）。

以下是K-means算法的基本步骤：

• 初始化中心点： 随机选择K个数据点作为初始的簇中心点。

• 分配数据点： 对于每个数据点，计算它与各个簇中心的距离，并将其分配给距离最近的簇。

• 更新簇中心： 对每个簇，计算其所有数据点的平均值，将该平均值作为新的簇中心。

重复步骤2和步骤3： 重复执行步骤2和步骤3，直到簇中心不再发生显著变化或达到预定的迭代次数。

收敛： 算法收敛于一组簇中心，每个数据点属于与其最近的中心。

import numpy as np
import matplotlib.pyplot as plt

def kmeans(X, k, max_iters=100, tol=1e-4):
    # 初始化簇中心
    centroids = X[np.random.choice(len(X), k, replace=False)]
    
    for _ in range(max_iters):
        # 计算每个点到簇中心的距离
        distances = np.linalg.norm(X[:, np.newaxis] - centroids, axis=2)
        
        # 分配每个点到最近的簇
        labels = np.argmin(distances, axis=1)
        
        # 计算新的簇中心
        new_centroids = np.array([X[labels == z].mean(axis=0) for z in range(k)])
        
        # 判断是否收敛
        if np.linalg.norm(new_centroids - centroids) < tol:
            break
        
        centroids = new_centroids

    return centroids, labels

# 生成一些随机样本数据
np.random.seed(42)
X, _ = make_blobs(n_samples=300, centers=4, random_state=42, cluster_std=1.0)

# 使用自己实现的K-means算法进行聚类
centroids, labels = kmeans(X, k=4)

# 绘制原始数据和簇中心
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', edgecolors='k', s=50, alpha=0.7)
plt.scatter(centroids[:, 0], centroids[:, 1], marker='X', s=200, linewidths=3, color='r', label='Centroids')
plt.title('K-means Clustering (Implemented)')
plt.legend()
plt.show()