K-Means 聚类详解

1. 什么是 K-Means 聚类

K-Means 是最经典的无监督聚类算法之一，其目标是将 n 个数据点划分为 K 个簇，使得每个点属于离它最近的质心（centroid）所代表的簇。算法的名字直接揭示了其核心思想："K"代表簇的数量，"Means"代表每个簇由其成员的均值（即质心）来定义。

历史起源：K-Means 算法最早由 Stuart Lloyd 于 1957 年在贝尔实验室提出，作为脉冲编码调制（PCM）的一种量化技术，但直到 1982 年才正式发表。独立地，Hugo Steinhaus 在 1956 年的论文中就提出了类似的划分思想。1967 年，James MacQueen 在一篇论文中首次使用了"K-Means"这个术语，并给出了该过程的正式统计分析。因此你会看到这个算法有时也被称为 Lloyd's 算法。

为什么 K-Means 如此流行？ 原因有三：（1）算法概念极为简单直观；（2）时间复杂度为 O(n * K * d * t)（n 为样本数，d 为维度，t 为迭代次数），对大数据集也能快速收敛；（3）在许多实际场景中效果良好，如客户细分、图像压缩、文档聚类等。

2. 算法逐步解析

K-Means 算法的每一步都有其明确的数学动机。下面逐步解析算法流程以及每步背后的"为什么"。

Step 1: 初始化 K 个质心

做什么：从数据集中随机选择 K 个点作为初始质心。

为什么初始化很重要：K-Means 的目标函数（WCSS）是非凸的，存在多个局部最优解。不同的初始质心会导致算法收敛到不同的局部最优。如果初始质心恰好都集中在数据的一个区域，算法可能永远找不到全局最优的聚类结果。这就是为什么后来 Arthur 和 Vassilvitskii 在 2007 年提出了 K-Means++ 初始化来系统性地解决这个问题（见第 5 节）。

Step 2: 将每个点分配到最近的质心

做什么：对数据集中的每个点，计算它到所有 K 个质心的欧氏距离，将它分配给距离最近的质心所在的簇。

为什么这一步能最小化 WCSS：在质心固定的情况下，将每个点分配到最近的质心等价于最小化每个点对总 WCSS 的贡献。数学上，对于点 xᵢ，选择簇 k* = argmin_k ||xᵢ - μₖ||² 正是在当前质心下最小化该点的平方距离。这一步保证 WCSS 不会增加。

Step 3: 更新质心为簇内均值

做什么：对每个簇，重新计算质心为该簇所有成员点的均值：μₖ = (1/|Cₖ|) * Σᵢ xᵢ。

为什么用均值 — 导数证明：在分配固定的情况下，我们要找使簇内平方误差和（SSE）最小的点 c。对 SSE = Σᵢ ||xᵢ - c||² 求 c 的导数并令其为零：∂SSE/∂c = -2 Σᵢ (xᵢ - c) = 0，解得 c = (1/n) Σᵢ xᵢ，即均值。因此均值是最小化平方误差的最优代表点。这也解释了算法名字中"Means"的来源。

Step 4: 重复直到收敛

做什么：重复 Step 2 和 Step 3，直到质心不再变化（或变化小于阈值）。

为什么保证收敛：每次迭代中，Step 2 在固定质心下最小化 WCSS（分配阶段），Step 3 在固定分配下最小化 WCSS（更新阶段）。因此 WCSS 在每次迭代中单调递减（或不变）。同时，n 个点分配到 K 个簇的方式是有限的（最多 K^n 种），因此算法不可能无限循环。单调递减 + 有限状态空间 = 保证收敛。但注意：收敛到的是局部最优，不一定是全局最优。

# K-Means 算法伪代码
输入: 数据集 X = {x₁, x₂, ..., xₙ}, 簇数 K
输出: K 个簇 C₁, C₂, ..., Cₖ 和质心 μ₁, μ₂, ..., μₖ

1. 随机选择 K 个点作为初始质心 μ₁, μ₂, ..., μₖ
2. repeat:
     对每个点 xᵢ:
       cᵢ = argmin_k ||xᵢ - μₖ||²   (分配到最近质心)
     对每个簇 k:
       μₖ = mean({xᵢ : cᵢ = k})      (更新质心为均值)
3. until 质心不再变化

3. 目标函数 — WCSS

K-Means 优化的目标函数是 Within-Cluster Sum of Squares（簇内平方和），也称为 inertia：

WCSS（簇内平方和）

WCSS = Σₖ₌₁ᴷ Σᵢ∈Cₖ ||xᵢ - μₖ||²

其中 Cₖ 是第 k 个簇的点集，μₖ 是第 k 个簇的质心（均值）。

为什么选择这个函数：WCSS 衡量的是簇的紧凑度（compactness）——每个点到其质心的距离之和。WCSS 越小，说明簇内的点越紧密地聚集在质心周围，聚类效果越好。这个函数具有清晰的几何意义：它等价于最小化簇内点对之间的平均距离。

NP-hard 问题：精确最小化 WCSS 已被证明是 NP-hard 的。Mahajan、Nimbhorkar 和 Varadarajan 在 2012 年证明，即使在平面（2维）上对一般的 K 值，精确求解 K-Means 也是 NP-hard 的。Aloise 等人（2009）更进一步证明即使 K=2 时也是 NP-hard 的。因此 Lloyd's 算法本质上是一种启发式方法——它不保证找到全局最优，但在实践中通常能找到足够好的解。

WCSS 与簇内方差的关系

WCSS = Σₖ |Cₖ| * Var(Cₖ)

最小化 WCSS 等价于最小化各簇的加权方差之和。这也解释了为什么 K-Means 倾向于产生大小相近的球形簇——因为加权方差会惩罚过大的簇。

4. 如何选择 K — 三种方法

K 是 K-Means 的唯一超参数，但也是最关键的。选错 K 会导致欠聚类（簇太少，不同结构被合并）或过聚类（簇太多，同一结构被分割）。以下三种方法各有其数学基础。

4.1 肘部法则（Elbow Method）

核心思想：边际收益递减

提出者：Robert L. Thorndike 在 1953 年的论文 "Who Belongs in the Family?" 中首次描述了这一思想。

方法：对 K = 1, 2, ..., K_max 分别运行 K-Means，绘制 K vs WCSS 曲线。寻找曲线从急剧下降变为平缓下降的"肘部"拐点。

为什么有效：当 K 从 1 增加到真实簇数时，每增加一个簇，WCSS 会显著下降，因为新质心能捕获之前被合并的不同数据结构。但当 K 超过真实簇数后，新增的簇只是在分割已经很紧凑的簇，WCSS 的下降变得微小——这就是边际收益递减。拐点对应的 K 就是在"解释力"和"模型复杂度"之间的最佳平衡点。

import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

wcss = []
K_range = range(1, 11)
for k in K_range:
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    km.fit(X)
    wcss.append(km.inertia_)

plt.plot(K_range, wcss, 'bo-')
plt.xlabel('K')
plt.ylabel('WCSS')
plt.title('Elbow Method')
plt.show()

4.2 轮廓系数（Silhouette Score）

核心思想：平衡内聚度与分离度

提出者：Peter J. Rousseeuw 在 1987 年的论文 "Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis" 中提出。

公式：对于数据点 i，轮廓系数定义为：

s(i) = (b(i) - a(i)) / max(a(i), b(i))

其中 a(i) = 点 i 到同簇其他点的平均距离（内聚度），b(i) = 点 i 到最近邻簇所有点的平均距离（分离度）。s(i) 的范围是 [-1, 1]。

为什么有效：轮廓系数巧妙地同时衡量了两个关键属性：(1) 内聚度（a(i) 越小，点与本簇越紧密）；(2) 分离度（b(i) 越大，点离其他簇越远）。当 s(i) 接近 1 时，b(i) >> a(i)，说明点被正确分配；当 s(i) 接近 -1 时，a(i) >> b(i)，说明点可能被错误分配。选择使平均轮廓系数最大的 K。

from sklearn.metrics import silhouette_score

scores = []
for k in range(2, 11):
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    labels = km.fit_predict(X)
    scores.append(silhouette_score(X, labels))

best_k = range(2, 11)[scores.index(max(scores))]
print(f"Best K by silhouette: {best_k}")

4.3 Gap Statistic

核心思想：与零假设的比较

提出者：Robert Tibshirani、Guenther Walther 和 Trevor Hastie 在 2001 年的论文 "Estimating the Number of Clusters in a Data Set via the Gap Statistic" 中提出。

公式：Gap(K) = E*[log(Wₖ)] - log(Wₖ)

其中 Wₖ 是实际数据的 WCSS，E*[log(Wₖ)] 是在均匀随机分布（零假设）下 WCSS 的期望值，通过蒙特卡洛模拟多组随机数据来估算。

为什么有效：肘部法则和轮廓系数的一个共同问题是：当数据本身没有明显的簇结构时，它们仍然会给出一个"最佳 K"。Gap Statistic 通过引入零假设来解决这个问题——它问的是："相比于完全没有簇结构的随机数据，当前的 K 值是否带来了统计上显著的聚类改进？" 选择使 Gap 值最大的最小 K（即 Gap(K) >= Gap(K+1) - s_{K+1}，其中 s 是标准误差）。

5. K-Means++ 初始化

提出者：David Arthur 和 Sergei Vassilvitskii 在 2007 年的论文 "k-means++: The Advantages of Careful Seeding" 中提出。这篇论文获得了 ACM-SIAM 离散算法研讨会（SODA）的最佳论文奖。

为什么需要 K-Means++：标准 K-Means 的随机初始化有一个严重的问题：如果初始质心恰好集中在数据空间的一个区域，算法几乎必然收敛到一个很差的局部最优。Arthur 和 Vassilvitskii 证明了 K-Means++ 的初始化方案能保证 WCSS 在期望意义上不超过最优解的 O(log K) 倍——这是一个理论上的竞争比保证，远优于随机初始化可能产生的任意差的结果。

K-Means++ 算法步骤

Step 1: 从数据集中均匀随机选择第一个质心 c₁。

Step 2: 对每个数据点 x，计算它到已选质心的最短距离 D(x) = min_j ||x - cⱼ||²。

Step 3: 以概率 P(x) = D(x)² / Σᵢ D(xᵢ)² 选择下一个质心。为什么用距离的平方作为概率：这使得离已有质心越远的点越有可能被选为新质心，从而确保质心在数据空间中分散开来。使用平方而非线性距离是为了更强地偏向远处的点。

Step 4: 重复 Step 2-3 直到选出 K 个质心。

Step 5: 使用这 K 个质心作为初始值，运行标准 K-Means 算法。

import numpy as np

def kmeans_plus_plus_init(X, K):
    """K-Means++ 初始化"""
    n = X.shape[0]
    # Step 1: 随机选第一个质心
    centroids = [X[np.random.randint(n)]]

    for _ in range(1, K):
        # Step 2: 计算每个点到最近质心的距离
        dists = np.array([min(np.sum((x - c)**2) for c in centroids) for x in X])
        # Step 3: 按距离的平方为概率选择下一个质心
        probs = dists / dists.sum()
        idx = np.random.choice(n, p=probs)
        centroids.append(X[idx])

    return np.array(centroids)

实践提示：sklearn 的 KMeans 默认使用 init='k-means++'，所以你在使用 sklearn 时已经自动享受了 K-Means++ 的优势。

6. K-Means 的局限性与数学原因

K-Means 虽然简单高效，但有几个根本性的局限，每一个都有其数学根源。

6.1 只能发现球形（凸形）簇

为什么：欧氏距离 + 均值 = 球形

K-Means 使用欧氏距离来分配点，并用均值作为质心。欧氏距离的等距面是超球面，均值是平方误差的最小化点。因此每个簇实际上被定义为一个 Voronoi 区域——空间中所有到该质心最近的点的集合。Voronoi 区域的边界始终是超平面（线性），因此 K-Means 永远无法捕获非凸形状的簇，如月牙形、环形等。对于非凸簇结构，应使用 DBSCAN（基于密度）或谱聚类（基于图）。

6.2 对异常值敏感

为什么：均值不具有鲁棒性

质心被定义为簇内点的均值，而均值受极端值影响很大。一个离群点可以显著拉偏质心的位置。数学上，均值的崩溃点（breakdown point）为 1/n——只需一个极端值就能使均值偏移任意远。替代方案：K-Medoids（PAM 算法），由 Kaufman 和 Rousseeuw 在 1990 年的著作 "Finding Groups in Data" 中提出。K-Medoids 使用中位点（medoid，即簇中使其他点到它距离之和最小的实际数据点）替代均值作为质心，对异常值的鲁棒性大大增强。代价是计算复杂度更高：O(n²) vs O(n)。

6.3 倾向于等大小的簇

为什么：WCSS 加权惩罚大簇

回顾 WCSS = Σₖ |Cₖ| * Var(Cₖ)。这个公式中包含了簇大小 |Cₖ| 作为权重，因此大簇的方差会被更重地惩罚。算法倾向于将大簇分裂为小簇，即使这不符合数据的真实结构。当真实簇大小差异很大时，K-Means 常常会从大簇中"偷"一些点分配给小簇，以降低总 WCSS。

6.4 必须预先指定 K

为什么这是个问题

在许多实际场景中，我们事先不知道数据中有多少个自然簇。虽然肘部法则和轮廓系数可以帮助选择 K，但它们本身也需要主观判断，且对噪声数据可能给出误导性结果。DBSCAN 和均值漂移（Mean Shift）等算法可以自动确定簇的数量，但也有各自的超参数需要调节。

7. Python 实现

7.1 从零实现 K-Means

import numpy as np

class KMeansFromScratch:
    def __init__(self, K=3, max_iters=100, tol=1e-4):
        self.K = K
        self.max_iters = max_iters
        self.tol = tol        # 质心变化容忍度

    def fit(self, X):
        n, d = X.shape
        # K-Means++ 初始化
        self.centroids = self._init_centroids(X)

        for iteration in range(self.max_iters):
            # Step 2: 分配每个点到最近质心
            distances = self._calc_distances(X)
            self.labels = np.argmin(distances, axis=1)

            # Step 3: 更新质心为簇内均值
            new_centroids = np.zeros_like(self.centroids)
            for k in range(self.K):
                members = X[self.labels == k]
                if len(members) > 0:
                    new_centroids[k] = members.mean(axis=0)
                else:
                    new_centroids[k] = X[np.random.randint(n)]

            # 检查收敛
            shift = np.linalg.norm(new_centroids - self.centroids)
            self.centroids = new_centroids
            if shift < self.tol:
                break

        self.inertia_ = self._calc_wcss(X)
        return self

    def predict(self, X):
        distances = self._calc_distances(X)
        return np.argmin(distances, axis=1)

    def _init_centroids(self, X):
        """K-Means++ 初始化"""
        n = X.shape[0]
        centroids = [X[np.random.randint(n)]]
        for _ in range(1, self.K):
            dists = np.min([np.sum((X - c)**2, axis=1) for c in centroids], axis=0)
            probs = dists / dists.sum()
            centroids.append(X[np.random.choice(n, p=probs)])
        return np.array(centroids)

    def _calc_distances(self, X):
        return np.array([np.sum((X - c)**2, axis=1) for c in self.centroids]).T

    def _calc_wcss(self, X):
        return sum(np.sum((X[self.labels == k] - self.centroids[k])**2)
                   for k in range(self.K))

# 使用示例
from sklearn.datasets import make_blobs
X, y_true = make_blobs(n_samples=300, centers=4, random_state=42)

km = KMeansFromScratch(K=4)
km.fit(X)
print(f"WCSS: {km.inertia_:.2f}")

7.2 sklearn 实战

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score
import matplotlib.pyplot as plt

# 数据标准化（K-Means 对尺度敏感，因为使用欧氏距离）
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 肘部法则 + 轮廓系数联合选 K
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4))
wcss, sil = [], []
for k in range(2, 11):
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    labels = km.fit_predict(X_scaled)
    wcss.append(km.inertia_)
    sil.append(silhouette_score(X_scaled, labels))

ax1.plot(range(2, 11), wcss, 'bo-')
ax1.set_xlabel('K'); ax1.set_ylabel('WCSS'); ax1.set_title('Elbow Method')
ax2.plot(range(2, 11), sil, 'ro-')
ax2.set_xlabel('K'); ax2.set_ylabel('Silhouette'); ax2.set_title('Silhouette Score')
plt.tight_layout(); plt.show()

# 使用最佳 K 进行聚类
best_k = range(2, 11)[sil.index(max(sil))]
km = KMeans(n_clusters=best_k, n_init=10, random_state=42)
labels = km.fit_predict(X_scaled)
print(f"Best K: {best_k}, Silhouette: {max(sil):.4f}")

8. K-Means vs DBSCAN vs 层次聚类

选择聚类算法需要根据数据特点来决定。以下从多个维度进行详细对比，并解释每种算法的设计哲学。

维度	K-Means	DBSCAN	层次聚类
提出者	Lloyd (1957/1982)	Ester, Kriegel, Sander, Xu (1996), KDD 会议	多人独立提出，Ward (1963) 提出最小方差法
核心思想	最小化簇内平方和 (WCSS)	基于密度：核心点、边界点、噪声点	递归合并/分裂，构建树状图（dendrogram）
是否需要指定 K	是，必须预先指定	否，自动确定。需指定 eps（邻域半径）和 min_samples（最少点数）	否，可通过切割 dendrogram 在任意层级获得不同 K
簇形状	仅球形 / 凸形（因为 Voronoi 划分）	任意形状（因为基于密度连通性）	取决于链接方式：单链接可发现链状簇，完全链接倾向球形
异常值处理	差——异常值被强制分配到某个簇，拉偏质心	好——密度不足的点被标记为噪声（-1标签）	中等——取决于链接方式，单链接易受链式效应影响
时间复杂度	O(n * K * d * t)，接近线性	O(n log n) 使用 KD-tree，最坏 O(n²)	O(n²log n) 或 O(n³)，大数据不实用
可扩展性	优秀，可处理百万级数据。Mini-Batch K-Means 更快	中等，受 eps 选择影响，高维数据效果差（维度灾难）	差，O(n²) 内存消耗，通常限于几千个样本
适用场景	球形簇、大数据、特征量化、图像压缩	任意形状簇、含噪声数据、地理空间聚类	小数据集、需要层次结构、基因表达分析

DBSCAN 为什么不需要指定 K

DBSCAN（Ester 等人，1996 年 KDD 会议）定义了三种点：(1) 核心点：在 eps 半径内至少有 min_samples 个邻居；(2) 边界点：在某个核心点的 eps 范围内，但自身邻居不足；(3) 噪声点：既不是核心点也不是边界点。簇由密度可达的核心点自动形成——无需人为指定 K。DBSCAN 的名字含义是 "Density-Based Spatial Clustering of Applications with Noise"。

层次聚类的 Dendrogram 为什么有用

层次聚类（尤其是凝聚型）从每个点作为一个簇开始，逐步合并最相似的簇对，直到所有点合并为一个簇。这个过程形成一个树状图（dendrogram），记录了每次合并的距离。通过在不同高度切割 dendrogram，可以得到不同粒度的聚类结果——不需要预先选择 K。Ward 链接方式（Ward, 1963）在每次合并时最小化方差增量，与 K-Means 的 WCSS 目标最为一致。

10. 常见问题 (FAQ)

Q: K-Means 聚类前需要对数据做标准化吗？

是的，强烈建议标准化。K-Means 使用欧氏距离来衡量点到质心的距离，而欧氏距离对特征尺度非常敏感。例如，如果特征 A 的范围是 [0, 1000] 而特征 B 的范围是 [0, 1]，那么距离几乎完全由特征 A 主导，特征 B 对聚类结果几乎没有影响。使用 StandardScaler（零均值单位方差）或 MinMaxScaler 可以确保所有特征对距离计算贡献均等。

Q: K-Means 的 n_init 参数是什么意思？

由于 K-Means 可能收敛到局部最优，sklearn 的 KMeans 默认会用不同的随机种子运行 n_init=10 次，然后选择 WCSS 最小的那次结果。增大 n_init 可以提高找到更好解的概率，但会线性增加计算时间。对于重要任务，可以设为 20-50 次。

Q: K-Means 能处理类别型（categorical）数据吗？

不能直接使用。K-Means 依赖欧氏距离和均值运算，这对类别型数据没有数学意义（例如，"红色"和"蓝色"的均值是什么？）。对于类别型数据，可以使用 K-Modes（Huang, 1998）算法，它用众数（mode）替代均值，用汉明距离替代欧氏距离。对于混合型数据（同时包含数值和类别特征），可以使用 K-Prototypes 算法。

Q: Mini-Batch K-Means 和标准 K-Means 有什么区别？

Mini-Batch K-Means（Sculley, 2010）在每次迭代中只使用数据的一个随机子集（mini-batch）来更新质心，而非全部数据。这使得它在大数据集上比标准 K-Means 快数倍到数十倍，代价是聚类质量略有下降（通常在 1-3% 以内）。sklearn 提供了 MiniBatchKMeans 类。当数据超过 10 万条时，推荐使用 Mini-Batch 版本。

Q: 如何评估 K-Means 聚类结果的好坏（没有真实标签时）？

当没有真实标签时（无监督学习的常见情况），主要依赖内部评估指标：(1) 轮廓系数（Silhouette Score）：值越接近 1 越好，综合衡量簇内紧凑度和簇间分离度；(2) Calinski-Harabasz 指数：簇间方差与簇内方差的比值，越高越好；(3) Davies-Bouldin 指数：衡量簇间相似度，越低越好。当有真实标签时，可以用调整兰德指数（ARI）和标准化互信息（NMI）来评估聚类与真实标签的一致性。