K-means 聚类算法：原理、步骤与 Python 实现

分配结果：

• 簇 1：点 1、点 2、点 3
• 簇 2：点 4、点 5

第三步：重新计算质心 对于每个簇，计算新质心的位置：

• 簇 1 的质心：(平均 x, 平均 y) = ((1+2+4)/3, (2+1+5)/3) ≈ (2.33, 2.67)
• 簇 2 的质心：(平均 x, 平均 y) = ((5+8)/2, (6+8)/2) = (6.5, 7.0)

第四步：重复分配与更新 再次计算每个点到新质心的距离，重复上述步骤，直到质心不再变化。最终质心稳定在 C1=(2.33, 2.67), C2=(6.5, 6.0)。

3. 数学基础

K-means 的目标是最小化簇内平方误差和（Within-Cluster Sum of Squares，WCSS），公式如下： $$ J = \sum_{i=1}^{K} \sum_{x \in C_i} ||x - \mu_i||^2 $$ 其中 $||x - \mu_i||^2$ 表示数据点 $x$ 与簇中心 $\mu_i$ 之间的欧氏距离平方。

欧氏距离公式为： $$ d(x, \mu) = \sqrt{\sum_{j=1}^{n} (x_j - \mu_j)^2} $$ 其中 $n$ 是数据的维度。

4. 伪代码

KMeans(X, K):
  1. 随机选择 K 个点作为初始簇中心
  2. 重复以下步骤，直到簇中心不再发生变化：
     a. 分配每个点到最近的簇中心
     b. 重新计算每个簇的中心，作为簇内所有点的均值
  3. 返回最终的簇分配和簇中心

5. 时间复杂度

若迭代次数为 $T$，则总体复杂度为 $O(n \cdot K \cdot T)$。

• 分配步骤：需要计算每个点到 $K$ 个簇中心的距离，复杂度为 $O(n \cdot K)$。
• 更新步骤：重新计算每个簇的中心，需要遍历所有点，复杂度也是 $O(n \cdot K)$。

6. 优缺点分析

优点

• 简单高效：适合大规模数据，处理大数据集时非常高效，具有良好的伸缩性。
• 收敛速度快：在适合的初始中心选择下，K-means 通常可以较快收敛。

缺点

• 对初始点敏感：初始簇中心的选择对最终结果影响较大。
• 形状限制：假设每个簇是凸形且大小相近，不适合发现非凸形状的簇（如'月牙型'数据）。
• 对噪声敏感：离群点会影响簇的中心计算。
• 局部最优：不能保证全局最优，只能达到局部最优。

7. K 值的选择

确定最佳的簇数 $K$ 是 K-means 聚类中的一个难点。常用的选择方法有：

1. 轮廓系数（Silhouette Coefficient）：衡量聚类结果的紧密度和分离度。
2. Calinski-Harabasz 指数：衡量簇内的方差与簇间方差之比。
3. 肘部法（Elbow Method）：绘制不同 K 值下的 WCSS 图，寻找'肘部'点作为最佳 $K$ 值。当 SSE 图像下降幅度最大放缓时，即为最佳 K 值区间。

8. Python 实现

我们可以使用 scikit-learn 中的 KMeans，以及手动实现以便更深入理解。

8.1 使用 scikit-learn

from sklearn.cluster import KMeans
import numpy as np

# 生成示例数据
X = np.array([[1, 2], [2, 2], [3, 3], [8, 7], [8, 8], [25, 80]])

# 初始化并训练模型
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)

# 获取簇标签和簇中心
labels = kmeans.labels_
centroids = kmeans.cluster_centers_

print("Cluster labels:", labels)
print("Centroids:", centroids)

8.2 手动实现

以下是 K-means 的核心逻辑手动实现，有助于理解内部机制：

import numpy as np

def initialize_centroids(X, k):
    indices = np.random.choice(len(X), k, replace=False)
    return X[indices]

def closest_centroid(X, centroids):
    distances = np.linalg.norm(X[:, np.newaxis] - centroids, axis=2)
    return np.argmin(distances, axis=1)

def update_centroids(X, labels, k):
    return np.array([X[labels == i].mean(axis=0) for i in range(k)])

def kmeans(X, k, max_iters=100, tol=1e-4):
    centroids = initialize_centroids(X, k)
    for i in range(max_iters):
        labels = closest_centroid(X, centroids)
        new_centroids = update_centroids(X, labels, k)
        if np.all(np.abs(new_centroids - centroids) < tol):
            break
        centroids = new_centroids
    return labels, centroids

# 示例数据
X = np.array([[1, 2], [2, 2], [3, 3], [8, 7], [8, 8], [25, 80]])
labels, centroids = kmeans(X, k=2)
print("最终簇:", labels)
print("质心位置:", centroids)

9. 收敛性与 K-means++

K-means 的收敛性受到初始簇中心选择的影响。K-means++ 是一种改进的初始化方法，优先选择'距离最远'的点作为初始质心，减少陷入局部最优的风险。

K-means++ 步骤

1. 随机选择一个点作为第一个中心。
2. 对于每个点，计算其与已选择中心的最小距离 $D(x)$。
3. 根据 $D(x)$ 的平方来选择下一个聚类中心，距离越远的点被选为新中心的概率越大。
4. 重复直到选择 $K$ 个聚类中心。

优势

• 避免随机性问题：确保初始中心分布更均匀。
• 提高收敛速度：减少迭代次数。
• 更稳定的结果：尤其在处理复杂结构数据时效果更佳。

10. 总结

K-means 是一种简单、快速的聚类算法，广泛应用于数据聚类任务。通过反复优化簇中心位置，K-means 不断收敛并找到数据的聚类结构。然而，它对初始条件敏感，对簇形状有限制，适合于球形且均匀分布的簇。在实际应用中，可通过结合 K-means++、肘部法和轮廓系数等手段改进其效果。