【AI 算法精讲 12】K-Means 聚类：初始化与收敛

文章目录

• 【AI 算法精讲 12】K-Means 聚类：初始化与收敛
• • 一、为什么需要 K-Means 聚类
  • 二、算法原理
  • • 2.1 问题定义与目标函数
    • 2.2 Lloyd 算法（标准 K-Means 迭代）
    • 2.3 收敛性分析
    • 2.4 初始化策略
    • • 2.4.1 随机选取（Random Init）
      • 2.4.2 K-Means++ 初始化
      • 2.4.3 K-Means|| （Scalable K-Means++）
    • 2.5 评估指标
  • 三、Python 实现
  • • 3.1 从零实现 K-Means（含 K-Means++ 初始化）
    • 3.2 sklearn 实战：肘部法则与轮廓系数选 K
  • 四、参数调优 / 阈值选择 / 变体对比
  • • 4.1 核心参数调优
    • 4.2 初始化方法对比
    • 4.3 K-Means 变体对比
  • 五、在客服系统/订单系统中的实际应用
  • • 5.1 客服工单自动分类
    • 5.2 订单异常检测
  • 六、常见陷阱
  • 七、总结

【AI 算法精讲 12】K-Means 聚类：初始化与收敛

一、为什么需要 K-Means 聚类

在真实的业务数据中，绝大多数样本是没有标签的。客服系统每天产生数十万条工单文本、订单系统每天沉淀海量交易行为向量——这些数据没有人为标注的类别，但它们天然存在结构：某些工单描述的是同一类问题，某些订单行为属于同一类消费模式。

无监督学习的核心使命就是从无标签数据中发现结构。 聚类（Clustering）是无监督学习中最基础、最常用的工具，而 K-Means 又是聚类算法中应用最广泛的代表。

考虑以下典型痛点：

K-Means 的思想极其简洁：给定 K 个簇，让每个样本归入最近的簇，然后更新簇中心，反复迭代直到稳定。 这句话背后藏着三个关键问题——初始化策略怎么选、什么时候收敛、结果好不好评估——这正是本文要深入剖析的核心。

二、算法原理

2.1 问题定义与目标函数

给定数据集

X

=

{

x

1

,

x

2

,

…

,

x

N

}

X = \\{x_1, x_2, \\ldots, x_N\\}

X={x1​,x2​,…,xN​}，其中每个样本

x

i

∈

R

d

x_i \\in \\mathbb{R}^d

xi​∈Rd。K-Means 的目标是将

N

N

N 个样本划分为

K

K

K 个簇

C

=

{

C

1

,

C

2

,

…

,

C

K

}

C = \\{C_1, C_2, \\ldots, C_K\\}

C={C1​,C2​,…,CK​}，使得簇内平方误差和（Within-Cluster Sum of Squares, WCSS）最小化。

目标函数（也称为惯性/Inertia）：

J

=

∑

k

=

1

K

∑

x

∈

C

k

∥

x

−

μ

k

∥

2

J = \\sum_{k=1}^{K} \\sum_{x \\in C_k} \\|x – \\mu_k\\|^2

J=k=1∑K​x∈Ck​∑​∥x−μk​∥2

其中

μ

k

\\mu_k

μk​ 是第

k

k

k 个簇的均值向量（质心）：

μ

k

=

1

∣

C

k

∣

∑

x

∈

C

k

x

\\mu_k = \\frac{1}{|C_k|} \\sum_{x \\in C_k} x

μk​=∣Ck​∣1​x∈Ck​∑​x

这是一个 NP-hard 问题——穷举所有可能的划分方式有

N

!

(

N

/

K

)

!

K

⋅

K

!

\\frac{N!}{(N/K)!^K \\cdot K!}

(N/K)!K⋅K!N!​ 种，在实际数据集上根本不可能暴力求解。K-Means 通过交替优化策略寻找近似最优解。

2.2 Lloyd 算法（标准 K-Means 迭代）

Lloyd 算法是 K-Means 最经典的实现，分为两个交替执行的步骤：

步骤 1：分配（Assignment Step）

固定簇中心

μ

k

\\mu_k

μk​，将每个样本分配到最近的簇：

C

k

(

t

)

=

{

x

i

:

∥

x

i

−

μ

k

(

t

)

∥

2

≤

∥

x

i

−

μ

j

(

t

)

∥

2

,
  

∀

j

=

1

,

…

,

K

}

C_k^{(t)} = \\{x_i : \\|x_i – \\mu_k^{(t)}\\|^2 \\leq \\|x_i – \\mu_j^{(t)}\\|^2, \\; \\forall j = 1, \\ldots, K\\}

Ck(t)​={xi​:∥xi​−μk(t)​∥2≤∥xi​−μj(t)​∥2,∀j=1,…,K}

即对每个样本

x

i

x_i

xi​，计算它到所有

K

K

K 个中心的欧氏距离，取最近的那个。

步骤 2：更新（Update Step）

固定簇分配，重新计算每个簇的中心为簇内所有样本的均值：

μ

k

(

t

+

1

)

=

1

∣

C

k

(

t

)

∣

∑

x

∈

C

k

(

t

)

x

\\mu_k^{(t+1)} = \\frac{1}{|C_k^{(t)}|} \\sum_{x \\in C_k^{(t)}} x

μk(t+1)​=∣Ck(t)​∣1​x∈Ck(t)​∑​x

迭代终止条件（满足任一即可）：

• 簇分配不再变化：$C_k^{(t+1)}=C_k^{(t)},\forall k$
• 目标函数变化小于阈值：$|J^{(t+1)}-J^{(t)}|<ϵ$
• 达到最大迭代次数 $T_{\max }$

2.3 收敛性分析

定理 1（单调性）： Lloyd 算法的每次迭代不会使目标函数

J

J

J 增大，即

J

(

t

+

1

)

≤

J

(

t

)

J^{(t+1)} \\leq J^{(t)}

J(t+1)≤J(t)。

证明思路：

• 分配步：将样本移到更近的中心，等价于对固定的

  μ

  k

  \\mu_k

  μk​ 做精确最小化。每个样本的分配都是当前最优的，所以

  J

  J

  J 只会减小或不变。

• 更新步：对于固定的簇分配

  C

  k

  C_k

  Ck​，均值

  μ

  k

  \\mu_k

  μk​ 是使

  ∑

  x

  ∈

  C

  k

  ∥

  x

  −

  μ

  ∥

  2

  \\sum_{x \\in C_k} \\|x – \\mu\\|^2

  ∑x∈Ck​​∥x−μ∥2 最小的

  μ

  \\mu

  μ。可以通过对

  μ

  \\mu

  μ 求导验证：

∂

∂

μ

∑

x

∈

C

k

∥

x

−

μ

∥

2

=

∑

x

∈

C

k

−

2

(

x

−

μ

)

=

0

\\frac{\\partial}{\\partial \\mu} \\sum_{x \\in C_k} \\|x – \\mu\\|^2 = \\sum_{x \\in C_k} -2(x – \\mu) = 0

∂μ∂​x∈Ck​∑​∥x−μ∥2=x∈Ck​∑​−2(x−μ)=0

解得

μ

=

1

∣

C

k

∣

∑

x

∈

C

k

x

\\mu = \\frac{1}{|C_k|} \\sum_{x \\in C_k} x

μ=∣Ck​∣1​∑x∈Ck​​x，即算术均值。因此更新步也是精确最小化，

J

J

J 只会减小或不变。

两步合起来，

J

J

J 单调不增。又因为

J

≥

0

J \\geq 0

J≥0（平方和恒非负），由单调有界定理，

J

J

J 必收敛。

注意： 收敛到的是局部最优，不保证全局最优。初始中心的选择直接决定了最终收敛到哪个局部最优点。

2.4 初始化策略

初始化是 K-Means 中影响最终质量的最关键因素。常见的初始化方法有三种：

2.4.1 随机选取（Random Init）

从数据集中随机选

K

K

K 个样本作为初始中心。

• 优点：简单快速
• 缺点：可能选到相近的点导致初始簇分布不均，收敛慢且质量差

2.4.2 K-Means++ 初始化

K-Means++ 的核心思想是让初始中心彼此尽可能远，从而获得更均匀的覆盖。算法如下：

D

(

x

i

)

=

min

⁡

j

∥

x

i

−

μ

j

∥

2

D(x_i) = \\min_{j} \\|x_i – \\mu_j\\|^2

D(xi​)=jmin​∥xi​−μj​∥2

直觉理解： 离已有中心越远的样本，被选为新中心的概率越大。这确保了初始中心散布在整个数据空间中，而不是挤在一起。

理论保证： K-Means++ 的期望目标函数值不超过最优解的

O

(

log

⁡

K

)

O(\\log K)

O(logK) 倍：

E

[

J

]

≤

8

(

ln

⁡

K

+

2

)

⋅

J

∗

\\mathbb{E}[J] \\leq 8(\\ln K + 2) \\cdot J^*

E[J]≤8(lnK+2)⋅J∗

其中

J

∗

J^*

J∗ 是全局最优目标值。

2.4.3 K-Means|| （Scalable K-Means++）

K-Means++ 的缺点是每轮只选一个中心，需要

K

K

K 轮迭代，在

K

K

K 较大时效率低。K-Means|| 是其并行化版本：

sklearn 的 KMeans 默认使用的就是 K-Means|| 初始化（init='k-means++'）。

2.5 评估指标

K-Means 没有标签可以对照，需要内部评估指标：

惯性（Inertia / WCSS）：

Inertia

=

∑

k

=

1

K

∑

x

∈

C

k

∥

x

−

μ

k

∥

2

\\text{Inertia} = \\sum_{k=1}^{K} \\sum_{x \\in C_k} \\|x – \\mu_k\\|^2

Inertia=k=1∑K​x∈Ck​∑​∥x−μk​∥2

值越小越好，但随着

K

K

K 增大单调下降，不能直接用于选择

K

K

K。

轮廓系数（Silhouette Coefficient）：

对每个样本

x

i

x_i

xi​，定义：

s

(

x

i

)

=

b

(

x

i

)

−

a

(

x

i

)

max

⁡

(

a

(

x

i

)

,

b

(

x

i

)

)

s(x_i) = \\frac{b(x_i) – a(x_i)}{\\max(a(x_i), b(x_i))}

s(xi​)=max(a(xi​),b(xi​))b(xi​)−a(xi​)​

其中：

• $a(x_i)$
• $b(x_i)$

s

(

x

i

)

∈

[

−

1

,

1

]

s(x_i) \\in [-1, 1]

s(xi​)∈[−1,1]。接近 1 表示聚类质量好，接近 0 表示在簇边界上，为负表示可能分错了簇。

整体轮廓系数为所有样本的均值：

S

=

1

N

∑

i

=

1

N

s

(

x

i

)

S = \\frac{1}{N} \\sum_{i=1}^{N} s(x_i)

S=N1​i=1∑N​s(xi​)

肘部法则（Elbow Method）：

画出 Inertia 随

K

K

K 变化的曲线，在曲线"肘部"处（拐点）选择

K

K

K。背后的直觉是：在到达正确簇数后，再增加

K

K

K 带来的 Inertia 下降会急剧放缓。

更形式化地，可以用轮廓系数配合肘部法则：选择轮廓系数最大的

K

K

K。

三、Python 实现

3.1 从零实现 K-Means（含 K-Means++ 初始化）

import numpy as np
from typing import Optional

class KMeansFromScratch:
"""从零实现的 K-Means，支持随机初始化和 K-Means++ 初始化。"""

def __init__(
self,
n_clusters: int = 3,
init: str = "k-means++",
max_iter: int = 300,
tol: float = 1e-4,
random_state: Optional[int] = None,
):
self.n_clusters = n_clusters
self.init = init
self.max_iter = max_iter
self.tol = tol
self.rng = np.random.default_rng(random_state)
self.centroids = None
self.labels_ = None
self.inertia_ = None
self.n_iter_ = 0

def _init_random(self, X: np.ndarray) –> np.ndarray:
"""随机选取 K 个样本作为初始中心。"""
indices = self.rng.choice(
X.shape[0], size=self.n_clusters, replace=False
)
return X[indices].copy()

def _init_kmeans_plus_plus(self, X: np.ndarray) –> np.ndarray:
"""K-Means++ 初始化。"""
n_samples = X.shape[0]
centers = np.empty((self.n_clusters, X.shape[1]), dtype=X.dtype)

# 第一个中心：均匀随机
first_idx = self.rng.integers(n_samples)
centers[0] = X[first_idx]

# 逐个选取后续中心
closest_dist_sq = np.sum((X – centers[0]) ** 2, axis=1)
for c in range(1, self.n_clusters):
# 按距离平方成比例采样
probs = closest_dist_sq / closest_dist_sq.sum()
next_idx = self.rng.choice(n_samples, p=probs)
centers[c] = X[next_idx]

# 更新所有样本到最近中心的距离
new_dist_sq = np.sum((X – centers[c]) ** 2, axis=1)
closest_dist_sq = np.minimum(closest_dist_sq, new_dist_sq)

return centers

def fit(self, X: np.ndarray) –> "KMeansFromScratch":
"""拟合模型。"""
X = np.asarray(X, dtype=np.float64)

# 初始化中心
if self.init == "k-means++":
centroids = self._init_kmeans_plus_plus(X)
else:
centroids = self._init_random(X)

prev_inertia = np.inf

for iteration in range(self.max_iter):
# 分配步：每个样本归入最近的簇
# 计算所有样本到所有中心的距离矩阵 (N, K)
dists = np.linalg.norm(
X[:, np.newaxis, :] – centroids[np.newaxis, :, :],
axis=2,
)
labels = np.argmin(dists, axis=1)

# 更新步：重新计算中心
new_centroids = np.array(
[
X[labels == k].mean(axis=0)
if np.any(labels == k)
else centroids[k]
for k in range(self.n_clusters)
]
)

# 计算目标函数
inertia = sum(
np.sum((X[labels == k] – new_centroids[k]) ** 2)
for k in range(self.n_clusters)
if np.any(labels == k)
)

# 收敛判断
if abs(prev_inertia – inertia) < self.tol:
break

centroids = new_centroids
prev_inertia = inertia

self.centroids = centroids
self.labels_ = labels
self.inertia_ = inertia
self.n_iter_ = iteration + 1
return self

def predict(self, X: np.ndarray) –> np.ndarray:
"""预测新样本所属簇。"""
X = np.asarray(X, dtype=np.float64)
dists = np.linalg.norm(
X[:, np.newaxis, :] – self.centroids[np.newaxis, :, :],
axis=2,
)
return np.argmin(dists, axis=1)

# ============ 测试 ============
if __name__ == "__main__":
# 生成测试数据：3 个高斯团
rng = np.random.default_rng(42)
cluster_1 = rng.normal(loc=[0, 0], scale=1.0, size=(100, 2))
cluster_2 = rng.normal(loc=[6, 6], scale=1.0, size=(100, 2))
cluster_3 = rng.normal(loc=[0, 6], scale=1.0, size=(100, 2))
X = np.vstack([cluster_1, cluster_2, cluster_3])

# K-Means++ 初始化
km_pp = KMeansFromScratch(n_clusters=3, init="k-means++", random_state=42)
km_pp.fit(X)
print(f"K-Means++ 惯性: {km_pp.inertia_:.2f}, 迭代次数: {km_pp.n_iter_}")

# 随机初始化
km_rand = KMeansFromScratch(n_clusters=3, init="random", random_state=42)
km_rand.fit(X)
print(f"随机初始化 惯性: {km_rand.inertia_:.2f}, 迭代次数: {km_rand.n_iter_}")

运行结果示例：

K-Means++ 惯性: 611.37, 迭代次数: 7
随机初始化 惯性: 611.37, 迭代次数: 12

在这个数据分布良好、簇分离明显的场景中，两种初始化方法最终都找到了全局最优，但 K-Means++ 用了更少的迭代次数。当簇之间有重叠或存在噪声时，差异会更加显著。

3.2 sklearn 实战：肘部法则与轮廓系数选 K

import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

# 生成更复杂的数据：5 个簇，有部分重叠
X, y_true = make_blobs(
n_samples=1000, centers=5, cluster_std=1.2, random_state=42
)
# 标准化：K-Means 对量纲敏感
X = StandardScaler().fit_transform(X)

# 遍历 K=2..10，计算 Inertia 和 Silhouette
k_range = range(2, 11)
inertias = []
silhouettes = []

for k in k_range:
km = KMeans(
n_clusters=k,
init="k-means++",
n_init=10, # 运行 10 次取最优
max_iter=300,
tol=1e-4,
random_state=42,
)
km.fit(X)
inertias.append(km.inertia_)
silhouettes.append(silhouette_score(X, km.labels_))

print(f"{'K':>3} | {'Inertia':>12} | {'Silhouette':>12}")
print("-" * 32)
for k, inertia, sil in zip(k_range, inertias, silhouettes):
print(f"{k:>3} | {inertia:>12.2f} | {sil:>12.4f}")

# 选最优 K
best_k_sil = k_range[np.argmax(silhouettes)]
print(f"\\n轮廓系数最优 K = {best_k_sil} (S = {max(silhouettes):.4f})")

运行结果示例：

K | Inertia | Silhouette
——————————–
2 | 1800.32 | 0.3901
3 | 1200.87 | 0.4523
4 | 820.15 | 0.5102
5 | 615.43 | 0.5318
6 | 580.21 | 0.4892
7 | 545.67 | 0.4631
8 | 510.89 | 0.4412
9 | 480.33 | 0.4256
10 | 450.77 | 0.4101

轮廓系数最优 K = 5 (S = 0.5318)

可以看到 Inertia 随

K

K

K 单调递减，但下降速率在

K

=

5

K=5

K=5 处明显放缓（肘部），同时轮廓系数在

K

=

5

K=5

K=5 处取得最大值，两个指标互相印证。

四、参数调优 / 阈值选择 / 变体对比

4.1 核心参数调优

4.2 初始化方法对比

在 6 个不同数据集上各运行 100 次的平均表现：

数据为典型实验参考值，

J

o

p

t

J_{opt}

Jopt​ 为全局最优 Inertia。

结论： K-Means++ 配合 n_init=10 是性价比最高的选择，这也是 sklearn 的默认配置。

4.3 K-Means 变体对比

其中

N

N

N 为样本数，

K

K

K 为簇数，

d

d

d 为维度，

I

I

I 为迭代次数。

五、在客服系统/订单系统中的实际应用

5.1 客服工单自动分类

场景：客服系统每天接收上万条工单，经 BERT 编码为 768 维语义向量后，需要自动分组到不同的处理队列。

import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
from sklearn.preprocessing import StandardScaler

# 模拟：10000 条工单的 BERT 向量 (768维)
rng = np.random.default_rng(42)
ticket_vectors = rng.normal(size=(10000, 768))

# 标准化（虽然 BERT 向量已归一化，这里作为通用习惯）
X = StandardScaler().fit_transform(ticket_vectors)

# 用肘部法则 + 轮廓系数选 K
best_k, best_s = 0, –1
for k in range(5, 21):
km = KMeans(n_clusters=k, n_init=10, random_state=42)
km.fit(X)
s = silhouette_score(X, km.labels_, sample_size=5000)
print(f"K={k:>2} Inertia={km.inertia_:.0f} Silhouette={s:.4f}")
if s > best_s:
best_k, best_s = k, s

# 最终模型
final_km = KMeans(n_clusters=best_k, n_init=20, random_state=42).fit(X)

# 每个簇的工单数量
for cluster_id in range(best_k):
count = np.sum(final_km.labels_ == cluster_id)
print(f"簇 {cluster_id}: {count} 条工单 ({count/len(X)*100:.1f}%)")

# 新工单归类
new_ticket_vec = rng.normal(size=(1, 768))
cluster = final_km.predict(StandardScaler().fit_transform(new_ticket_vec))
print(f"新工单归入簇: {cluster[0]}")

5.2 订单异常检测

场景：订单系统中有用户的下单行为特征（下单频率、金额方差、时间集中度等），正常用户的特征聚成紧致簇，异常用户远离所有簇中心。

import numpy as np
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler

# 模拟正常用户行为特征: [日均订单数, 平均金额, 下单时间方差, 品类集中度]
rng = np.random.default_rng(42)
normal_users = np.column_stack([
rng.uniform(1, 5, size=5000), # 日均 1-5 单
rng.uniform(50, 500, size=5000), # 均价 50-500
rng.uniform(0.5, 2.0, size=5000), # 时间方差 0.5-2.0
rng.uniform(0.1, 0.6, size=5000), # 品类集中度 0.1-0.6
])

# 拟合 K-Means（K=4 种正常消费模式）
X = StandardScaler().fit_transform(normal_users)
km = KMeans(n_clusters=4, n_init=10, random_state=42).fit(X)

# 计算每个用户到最近中心的距离
dists = np.min(
np.linalg.norm(
X[:, np.newaxis, :] – km.cluster_centers_[np.newaxis, :, :],
axis=2,
),
axis=1,
)

# 取 99 分位数作为异常阈值
threshold = np.percentile(dists, 99)
print(f"异常阈值（99分位）: {threshold:.4f}")

# 检测异常订单
anomaly_users = np.array([
[20, 50, 0.01, 0.95], # 高频低价、时间固定、品类极度集中
[0.1, 9999, 5.0, 0.01], # 极低频天价订单
])
anomaly_scaled = StandardScaler().fit_transform(anomaly_users)
anomaly_dists = np.min(
np.linalg.norm(
anomaly_scaled[:, np.newaxis, :] – km.cluster_centers_[np.newaxis, :, :],
axis=2,
),
axis=1,
)
for i, d in enumerate(anomaly_dists):
flag = "⚠️ 异常" if d > threshold else "✅ 正常"
print(f"用户 {i}: 距离={d:.4f} {flag}")

工程落地建议：

六、常见陷阱

七、总结

K-Means 的美在于简洁——一个距离公式、一个均值更新、一轮迭代——就构成了无监督学习中最经久不衰的算法。它的局限同样清晰：假设球形簇、对初始化敏感、需要预先指定

K

K

K。理解这些边界，才能在正确的场景中用好它。

下一篇我们将探讨 DBSCAN 密度聚类——它不需要预设

K

K

K，能发现任意形状的簇，是 K-Means 最自然的互补方案。