K-means 聚类算法

K-means 聚类算法#

前言#

今天开始学习无监督学习，K-means 是最基础也是最重要的一个算法。和之前学的分类算法不同，聚类是在没有标签的情况下，让算法自己去发现数据中的结构，把相似的数据点“物以类聚”。感觉就像是在整理一堆混在一起的乐高积木，要把相同颜色和形状的放在一起。这篇笔记记录了我对 K-means 的学习和实践。

核心思想：物以类聚，人以群分#

K-means 的目标非常明确：把一堆数据点分成 $K$ 个簇 (Cluster)，并且让簇内的数据点尽可能相似（距离近），簇间的数据点尽可能不同（距离远）。

为了实现这个目标，算法会迭代地做两件事：

分配：把每个数据点分给离它最近的那个簇的中心。
更新：把每个簇的中心移动到这个簇里所有数据点的平均位置。

不断重复这两步，直到簇的中心不再变化，就找到了最终的聚类结果。

深入数学原理#

目标函数：我们要优化什么？#

K-means 优化的目标函数是所有数据点到其所属簇中心的距离平方和 (Sum of Squared Errors, SSE)，也称为簇内平方和 (Within-Cluster Sum of Squares, WCSS) 或惯性 (Inertia)。我们的目标是最小化这个值。

J = \sum_{i=1}^n \sum_{k=1}^K r_{ik} \|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2

其中：

$n$ 是样本数量， $K$ 是要分的簇的数量。
$\mathbf{x}_i$ 是第 $i$ 个数据点。
$\boldsymbol{\mu}_k$ 是第 $k$ 个簇的中心点（质心）。
$r_{ik}$ 是一个指示变量：如果 $\mathbf{x}_i$ 属于簇 $k$ ，则 $r_{ik}=1$ ，否则为0。

算法步骤：E-M思想的体现#

K-means 的迭代过程完美地体现了 EM (Expectation-Maximization) 算法的思想。

初始化: 随机选择 $K$ 个数据点作为初始的簇中心 $\boldsymbol{\mu}_1, \boldsymbol{\mu}_2, \dots, \boldsymbol{\mu}_K$ 。
重复以下步骤直到收敛:
- E-Step (Expectation/分配步): 对于每个数据点 $\mathbf{x}_i$ ，计算它到所有 $K$ 个簇中心的距离，并把它分配给最近的那个簇。这一步是在固定簇中心 $\boldsymbol{\mu}_k$ 的情况下，优化分配 $r_{ik}$ 来最小化目标函数 $J$ 。 $r_{ik} = \begin{cases} 1 & \text{if } k = \arg\min_j \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2 \\ 0 & \text{otherwise} \end{cases}$
- M-Step (Maximization/更新步): 对于每个簇 $k$ ，重新计算它的中心点 $\boldsymbol{\mu}_k$ ，使其成为该簇内所有数据点的均值。这一步是在固定分配 $r_{ik}$ 的情况下，优化簇中心 $\boldsymbol{\mu}_k$ 来最小化目标函数 $J$ 。 $\boldsymbol{\mu}_k = \frac{\sum_{i=1}^n r_{ik} \mathbf{x}_i}{\sum_{i=1}^n r_{ik}}$

收敛性证明:

在E-step，我们把点分给最近的中心，这必然会使总的距离平方和 $J$ 减小或不变。
在M-step，把中心更新为均值，根据均值的性质，这也会使该簇内的距离平方和达到最小，从而使总的 $J$ 减小或不变。
因为 $J$ 是一个非负值，它有下界。一个单调递减且有下界的序列必然会收敛。
注意：K-means 只能保证收敛到局部最优解，而不是全局最优解。最终结果对初始点的选择很敏感。

如何选择合适的 K 值？#

这是 K-means 的一个核心问题。 $K$ 值选得太大或太小，都得不到有意义的结果。有几种常用的方法来帮助我们选择。

肘部法则 (Elbow Method):
- 方法：计算不同 $K$ 值对应的目标函数 $J$ (即 WCSS)。
- 原理：随着 $K$ 的增加，WCSS 会不断减小。我们寻找曲线下降速率由快变缓的那个点，就像人的“手肘”一样。这个拐点通常被认为是比较合适的 $K$ 值。
- 缺点：“手肘”有时不明显，主观性较强。
轮廓系数 (Silhouette Coefficient):
- 方法：对每个样本 $i$ $i$ ，计算其轮廓系数 $s(i)$ $s (i)$ 。 $s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}$
  - $a(i)$ : 样本 $i$ 到同簇其他所有点的平均距离（衡量簇内凝聚度）。
  - $b(i)$ : 样本 $i$ 到最近的异簇所有点的平均距离（衡量簇间分离度）。
- 原理： $s(i)$ $s (i)$ 的取值范围是 $[-1, 1]$ $[- 1, 1]$ 。
  - 值越接近1，说明聚类效果越好。
  - 值越接近-1，说明可能分到了错误的簇。
  - 值在0附近，说明样本在两个簇的边界上。
- 选择：计算所有样本的平均轮廓系数，选择使平均轮廓系数最大的那个 $K$ 值。
Gap 统计量 (Gap Statistic):
- 方法：将真实数据的 WCSS 与在数据边界内随机生成的“无结构”数据的 WCSS 进行比较。
- 原理：寻找一个 $K$ 值，使得真实数据的 WCSS 下降程度，远大于随机数据的 WCSS 下降程度。这个“Gap”最大的点就是最优的 $K$ 。
- 优点：比肘部法则更自动化，但计算量更大。

实战演练：客户分群分析#

理论学完了，我们来模拟一个真实的商业场景：对客户进行分群，以便实施精准营销。

0. 准备工作#

首先，导入需要的库并生成模拟数据。在真实项目中，这一步是加载和清洗你的客户数据。

1
import numpy as np
2
import pandas as pd
3
import matplotlib.pyplot as plt
4
import seaborn as sns
5

6
# Scikit-learn 工具集
7
from sklearn.datasets import make_blobs
8
from sklearn.preprocessing import StandardScaler
9
from sklearn.cluster import KMeans
10
from sklearn.metrics import silhouette_score

1. 客户数据预处理和特征工程#

我们生成一些模拟数据，代表客户的两个特征：年收入和消费分数。

1
# 生成模拟客户数据
2
X, y_true = make_blobs(n_samples=300, centers=5, cluster_std=0.8, random_state=42)
3

4
# 为了更贴近真实场景，我们对数据进行一些变换
5
rng = np.random.RandomState(42)
6
X[:, 0] = X[:, 0] * 20000 + 80000  # 年收入
7
X[:, 1] = X[:, 1] * 30 + 50        # 消费分数 (1-100)
8

9
# 将数据转换为DataFrame，便于分析
10
customer_df = pd.DataFrame(X, columns=['Annual Income (k$)', 'Spending Score (1-100)'])
11

12
# --- 数据标准化 ---
13
# 年收入和消费分数的量纲差异很大，必须进行标准化
14
scaler = StandardScaler()
15
X_scaled = scaler.fit_transform(X)

2. 最优K值选择#

我们同时使用肘部法则和轮廓系数来确定最佳的 $K$ 值。

1
wcss = []
2
silhouette_scores = []
3
K_range = range(2, 11) # K值至少为2
4

5
for k in K_range:
6
    # 训练K-means模型
7
    kmeans = KMeans(n_clusters=k, init='k-means++', n_init=10, random_state=42)
8
    kmeans.fit(X_scaled)
9

10
    # 记录WCSS (惯性)
11
    wcss.append(kmeans.inertia_)
12

13
    # 记录轮廓系数
14
    silhouette_scores.append(silhouette_score(X_scaled, kmeans.labels_))
15

16
# 绘制K值选择图
17
plt.figure(figsize=(12, 5))
18

19
# 肘部法则
20
plt.subplot(1, 2, 1)
21
plt.plot(K_range, wcss, 'bo-')
22
plt.xlabel('簇数量 K')
23
plt.ylabel('簇内平方和 (WCSS)')
24
plt.title('肘部法则')
25
plt.grid(True)
26

27
# 轮廓系数
28
plt.subplot(1, 2, 2)
29
plt.plot(K_range, silhouette_scores, 'ro-')
30
plt.xlabel('簇数量 K')
31
plt.ylabel('平均轮廓系数')
32
plt.title('轮廓系数法')
33
plt.grid(True)
34

35
plt.tight_layout()
36
plt.show()
37

38
# 根据图像，我们选择 K=5
39
optimal_k = 5

从图中我们可以清晰地看到，肘部法则在 K=5 处有一个明显的拐点，而轮廓系数也在 K=5 时达到最大值。因此，我们确定最佳的簇数量是5。

3. 客户分群和特征分析#

现在，我们使用找到的最佳 $K$ 值来训练最终模型，并对分群结果进行分析。

1
# 使用最佳K值训练最终模型
2
final_kmeans = KMeans(n_clusters=optimal_k, init='k-means++', n_init=10, random_state=42)
3
customer_df['Cluster'] = final_kmeans.fit_predict(X_scaled)
4

5
# 可视化分群结果
6
plt.figure(figsize=(10, 8))
7
sns.scatterplot(data=customer_df, x='Annual Income (k$)', y='Spending Score (1-100)',
8
                hue='Cluster', palette='viridis', s=100, alpha=0.8, legend='full')
9
centroids = scaler.inverse_transform(final_kmeans.cluster_centers_)
10
plt.scatter(centroids[:, 0], centroids[:, 1], s=300, c='red', marker='X', label='Centroids')
11
plt.title('客户分群结果')
12
plt.xlabel('年收入 (k$)')
13
plt.ylabel('消费分数 (1-100)')
14
plt.legend()
15
plt.grid(True)
16
plt.show()
17

18
# 分析每个客户群的特征
19
cluster_analysis = customer_df.groupby('Cluster').agg({
20
    'Annual Income (k$)': ['mean', 'median'],
21
    'Spending Score (1-100)': ['mean', 'median'],
22
    'Cluster': 'count'
23
}).rename(columns={'count': 'Num Customers'})
24

25
print("\n--- 各客户群特征分析 ---")
26
print(cluster_analysis)

4. 业务洞察和建议#

最后，也是最重要的一步，是根据分群结果给出有价值的业务建议。

簇 0: 谨慎型
- 特征: 收入低，消费分数低。
- 洞察: 可能是学生或刚入职的年轻人，对价格敏感。
- 建议: 推送折扣、优惠券等促销信息，进行低价商品营销。
簇 1: 挥霍型
- 特征: 收入低，但消费分数高。
- 洞察: “月光族”，追求时尚和潮流，但购买力有限。
- 建议: 推送新品、潮流单品，提供分期付款等服务。
簇 2: 普通型
- 特征: 收入和消费分数都处于中等水平。
- 洞察: 这是最主流的客户群体，构成了消费的基本盘。
- 建议: 维持客户关系，通过会员制度、积分兑换等方式提高客户忠诚度。
簇 3: 目标型 (高价值)
- 特征: 收入高，消费分数高。
- 洞察: 核心高价值客户，有钱又愿意花钱。
- 建议: 提供VIP服务、专属定制、高端新品发布会等，重点维护，提升品牌忠诚度。
簇 4: 理性型
- 特征: 收入高，但消费分数低。
- 洞察: 有钱但消费谨慎，可能对品质和实用性要求高。
- 建议: 强调产品的质量、耐用性和性价比，避免过度营销，提供详细的产品信息。

学习总结#

容易踩的坑#

忘记数据标准化：K-means 基于距离计算，如果特征量纲不一致，量纲大的特征会主导聚类结果。这是最致命的错误！
K 值选择不当：业务理解和多种技术方法结合来确定 $K$ 值非常重要。
初始点敏感性：传统的随机初始化可能导致很差的局部最优解。使用 k-means++ 初始化（sklearn 的默认方法）能极大地改善这个问题。
对非球形簇和异常值敏感：K-means 假设簇是凸的、球形的，对不规则形状的簇和异常值处理得不好。

学习感悟#

K-means 是一个非常直观且高效的聚类算法，完美地展示了无监督学习的魅力——在没有答案的情况下发现数据中隐藏的模式。从理论推导的 E-M 步骤，到如何选择 $K$ 值的各种权衡，再到最终如何将聚类结果转化为有价值的商业洞察，整个过程构成了一个完整的、从数据到决策的闭环。虽然它有局限性，但作为探索性数据分析的第一步，K-means 无疑是强大且不可或缺的工具。

第二部分：K-means算法的数学理论深入#

2.1 距离度量与相似性函数#

2.1.1 欧几里得距离的数学性质#

K-means算法默认使用欧几里得距离作为相似性度量，其数学定义为：

$d(\mathbf{x}_i, \mathbf{x}_j) = \|\mathbf{x}_i - \mathbf{x}_j\|_2 = \sqrt{\sum_{k=1}^{d}(x_{ik} - x_{jk})^2}$

欧几里得距离的重要性质：

非负性： $d(\mathbf{x}_i, \mathbf{x}_j) \geq 0$ ，当且仅当 $\mathbf{x}_i = \mathbf{x}_j$ 时等于0
对称性： $d(\mathbf{x}_i, \mathbf{x}_j) = d(\mathbf{x}_j, \mathbf{x}_i)$
三角不等式： $d(\mathbf{x}_i, \mathbf{x}_k) \leq d(\mathbf{x}_i, \mathbf{x}_j) + d(\mathbf{x}_j, \mathbf{x}_k)$

2.1.2 其他距离度量#

虽然K-means通常使用欧几里得距离，但在特定应用中可以考虑其他距离度量：

曼哈顿距离（L1范数）： $d_1(\mathbf{x}_i, \mathbf{x}_j) = \sum_{k=1}^{d}|x_{ik} - x_{jk}|$

闵可夫斯基距离（Lp范数）： $d_p(\mathbf{x}_i, \mathbf{x}_j) = \left(\sum_{k=1}^{d}|x_{ik} - x_{jk}|^p\right)^{1/p}$

马哈拉诺比斯距离： $d_M(\mathbf{x}_i, \mathbf{x}_j) = \sqrt{(\mathbf{x}_i - \mathbf{x}_j)^T\mathbf{S}^{-1}(\mathbf{x}_i - \mathbf{x}_j)}$

其中 $\mathbf{S}$ 是协方差矩阵，该距离考虑了特征间的相关性。

2.2 目标函数的数学分析#

2.2.1 目标函数的凸性分析#

K-means的目标函数可以重写为：

$J(\mathbf{C}, \mathbf{M}) = \sum_{i=1}^{n}\min_{k=1,\ldots,K}\|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2$

其中 $\mathbf{C} = \{C_1, C_2, \ldots, C_K\}$ 表示簇的划分， $\mathbf{M} = \{\boldsymbol{\mu}_1, \boldsymbol{\mu}_2, \ldots, \boldsymbol{\mu}_K\}$ 表示簇中心。

重要性质：

关于簇中心的凸性：固定簇划分 $\mathbf{C}$ 时，目标函数关于簇中心 $\mathbf{M}$ 是凸函数
关于簇划分的非凸性：固定簇中心 $\mathbf{M}$ 时，目标函数关于簇划分 $\mathbf{C}$ 是非凸的
整体非凸性：联合优化问题是非凸的，存在多个局部最优解

2.2.2 最优性条件#

簇中心的最优性条件： 对于固定的簇划分，最优簇中心满足： $\frac{\partial J}{\partial \boldsymbol{\mu}_k} = -2\sum_{i \in C_k}(\mathbf{x}_i - \boldsymbol{\mu}_k) = 0$

解得： $\boldsymbol{\mu}_k^* = \frac{1}{|C_k|}\sum_{i \in C_k}\mathbf{x}_i$

这证明了最优簇中心就是簇内所有点的质心（均值）。

簇划分的最优性条件： 对于固定的簇中心，最优簇划分满足： $C_k^* = \{i : \|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2 \leq \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2, \forall j \neq k\}$

即每个点应该分配给距离最近的簇中心。

2.3 收敛性理论分析#

2.3.1 收敛性证明#

定理：K-means算法在有限步内收敛到局部最优解。

证明思路：

目标函数单调性：每次迭代后，目标函数值 $J$ 单调递减或保持不变
- E步：固定簇中心，重新分配点到最近簇，必然使 $J$ 减小或不变
- M步：固定簇划分，更新簇中心为质心，必然使 $J$ 减小或不变
有界性：目标函数 $J \geq 0$ ，有下界
有限状态空间：对于有限数据集，可能的簇划分数量有限
严格递减性：除非已达到局部最优，否则每次迭代 $J$ 严格递减

因此，算法必在有限步内收敛到某个局部最优解。

2.3.2 收敛速度分析#

线性收敛率：在一般情况下，K-means具有线性收敛速度： $J^{(t+1)} - J^* \leq \rho(J^{(t)} - J^*)$

其中 $0 < \rho < 1$ 是收敛因子， $J^*$ 是局部最优值。

影响收敛速度的因素：

初始化质量：好的初始化可以显著减少迭代次数
数据分布：簇间分离度越高，收敛越快
维度诅咒：高维数据可能导致收敛变慢
簇的数量：K值过大可能影响收敛稳定性

2.4 K-means++初始化算法#

2.4.1 算法动机#

标准K-means对初始化敏感，随机初始化可能导致：

收敛到较差的局部最优解
需要更多迭代次数
结果不稳定

K-means++通过智能初始化策略解决这些问题。

2.4.2 算法描述#

K-means++初始化步骤：

选择第一个中心：从数据点中均匀随机选择第一个簇中心 $\boldsymbol{\mu}_1$
迭代选择后续中心：对于 $i = 2, 3, \ldots, K$ ：
- 计算每个点 $\mathbf{x}_j$ 到最近已选中心的距离： $D(\mathbf{x}_j) = \min_{l=1,\ldots,i-1}\|\mathbf{x}_j - \boldsymbol{\mu}_l\|^2$
- 以概率正比于 $D(\mathbf{x}_j)^2$ 选择下一个中心： $P(\mathbf{x}_j) = \frac{D(\mathbf{x}_j)^2}{\sum_{k=1}^{n}D(\mathbf{x}_k)^2}$

2.4.3 理论保证#

近似比定理：K-means++初始化保证期望目标函数值不超过最优解的 $O(\log K)$ 倍：

$\mathbb{E}[J_{\text{K-means++}}] \leq 8(\log K + 2) \cdot J_{\text{OPT}}$

这个理论保证使K-means++成为实际应用中的标准选择。

2.5 算法复杂度分析#

2.5.1 时间复杂度#

单次迭代复杂度：

E步（分配）： $O(nKd)$ ，需要计算每个点到每个中心的距离
M步（更新）： $O(nd)$ ，计算新的簇中心

总时间复杂度： $O(nKdt)$

其中：

$n$ ：样本数量
$K$ ：簇的数量
$d$ ：特征维度
$t$ ：迭代次数

2.5.2 空间复杂度#

存储需求：

数据矩阵： $O(nd)$
簇中心： $O(Kd)$
簇分配： $O(n)$

总空间复杂度： $O(nd + Kd) = O((n+K)d)$

2.5.3 优化策略#

加速技术：

三角不等式加速：利用三角不等式减少距离计算
KD树加速：在低维空间中使用KD树加速最近邻搜索
Mini-batch K-means：使用小批量数据进行更新，适合大规模数据
并行化：E步和M步都可以并行化处理

第三部分：K-means算法的变种与扩展#

3.1 K-medoids算法（PAM）#

3.1.1 算法动机#

K-means使用均值作为簇中心，存在以下问题：

对异常值敏感
簇中心可能不是实际数据点
只适用于数值型数据

K-medoids（也称PAM，Partitioning Around Medoids）使用实际数据点作为簇中心。

3.1.2 算法描述#

目标函数： $J = \sum_{i=1}^{n}\min_{k=1,\ldots,K}d(\mathbf{x}_i, \mathbf{m}_k)$

其中 $\mathbf{m}_k$ 是第k个簇的medoid（中位点），必须是数据集中的实际点。

算法步骤：

初始化：随机选择K个数据点作为初始medoids
分配步：将每个点分配给最近的medoid
更新步：对每个簇，选择使簇内总距离最小的点作为新medoid： $\mathbf{m}_k = \arg\min_{\mathbf{x}_j \in C_k}\sum_{\mathbf{x}_i \in C_k}d(\mathbf{x}_i, \mathbf{x}_j)$

3.1.3 优缺点分析#

优点：

对异常值更鲁棒
簇中心是实际数据点，更有解释性
可以使用任意距离度量

缺点：

时间复杂度更高： $O(n^2Kt)$
在大数据集上计算成本昂贵

3.2 Fuzzy C-means算法#

3.2.1 软聚类的概念#

传统K-means进行硬聚类，每个点只属于一个簇。Fuzzy C-means引入模糊集合理论，允许每个点以不同程度属于多个簇。

3.2.2 数学模型#

隶属度矩阵：定义隶属度矩阵 $\mathbf{U} = [u_{ik}]_{n \times K}$ ，其中 $u_{ik}$ 表示点 $\mathbf{x}_i$ 属于簇 $k$ 的程度。

约束条件：

$0 \leq u_{ik} \leq 1$ ， $\forall i, k$
$\sum_{k=1}^{K} u_{ik} = 1$ ， $\forall i$
$0 < \sum_{i=1}^{n} u_{ik} < n$ ， $\forall k$

目标函数： $J_m = \sum_{i=1}^{n}\sum_{k=1}^{K} u_{ik}^m \|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2$

其中 $m > 1$ 是模糊化参数，控制聚类的”软”程度。

3.2.3 优化算法#

使用拉格朗日乘数法，可以得到更新公式：

隶属度更新： $u_{ik} = \frac{1}{\sum_{j=1}^{K}\left(\frac{\|\mathbf{x}_i - \boldsymbol{\mu}_k\|}{\|\mathbf{x}_i - \boldsymbol{\mu}_j\|}\right)^{\frac{2}{m-1}}}$

簇中心更新： $\boldsymbol{\mu}_k = \frac{\sum_{i=1}^{n} u_{ik}^m \mathbf{x}_i}{\sum_{i=1}^{n} u_{ik}^m}$

3.3 Mini-batch K-means#

3.3.1 大数据挑战#

标准K-means在处理大规模数据时面临挑战：

内存需求：需要将所有数据加载到内存
计算成本：每次迭代需要遍历所有数据点
收敛速度：大数据集可能需要更多迭代

3.3.2 Mini-batch策略#

核心思想：每次迭代只使用数据的一个小批量（mini-batch）进行更新。

算法步骤：

初始化：选择初始簇中心
采样：随机采样大小为 $b$ 的mini-batch
分配：将mini-batch中的点分配给最近的簇中心
更新：使用学习率 $\eta$ 更新簇中心： $\boldsymbol{\mu}_k^{(t+1)} = (1-\eta)\boldsymbol{\mu}_k^{(t)} + \eta \cdot \frac{1}{|C_k|}\sum_{\mathbf{x}_i \in C_k}\mathbf{x}_i$

3.3.3 学习率设计#

自适应学习率： $\eta_k = \frac{|C_k|}{|C_k| + \text{count}_k}$

其中 $\text{count}_k$ 是簇 $k$ 在历史中被更新的次数。

优势分析：

时间复杂度： $O(bKdt)$ ，其中 $b \ll n$
内存复杂度： $O(bd + Kd)$
适合在线学习和流数据处理

3.4 核K-means算法#

3.4.1 非线性聚类需求#

标准K-means假设簇是球形的，无法处理复杂的非线性结构。核K-means通过核技巧将数据映射到高维特征空间。

3.4.2 核函数与特征映射#

核函数定义： $\kappa(\mathbf{x}_i, \mathbf{x}_j) = \langle\phi(\mathbf{x}_i), \phi(\mathbf{x}_j)\rangle$

常用核函数：

多项式核： $\kappa(\mathbf{x}_i, \mathbf{x}_j) = (\mathbf{x}_i^T\mathbf{x}_j + c)^d$
RBF核： $\kappa(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma\|\mathbf{x}_i - \mathbf{x}_j\|^2)$
Sigmoid核： $\kappa(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\alpha\mathbf{x}_i^T\mathbf{x}_j + c)$

3.4.3 核K-means目标函数#

在特征空间中，目标函数变为： $J = \sum_{i=1}^{n}\min_{k=1,\ldots,K}\|\phi(\mathbf{x}_i) - \boldsymbol{\mu}_k^{\phi}\|^2$

其中 $\boldsymbol{\mu}_k^{\phi} = \frac{1}{|C_k|}\sum_{i \in C_k}\phi(\mathbf{x}_i)$ 是特征空间中的簇中心。

距离计算： $\|\phi(\mathbf{x}_i) - \boldsymbol{\mu}_k^{\phi}\|^2 = \kappa(\mathbf{x}_i, \mathbf{x}_i) - \frac{2}{|C_k|}\sum_{j \in C_k}\kappa(\mathbf{x}_i, \mathbf{x}_j) + \frac{1}{|C_k|^2}\sum_{j,l \in C_k}\kappa(\mathbf{x}_j, \mathbf{x}_l)$

第四部分：聚类评估与验证#

4.1 内部评估指标#

4.1.1 轮廓系数（Silhouette Coefficient）#

定义：对于点 $\mathbf{x}_i$ ，其轮廓系数为： $s_i = \frac{b_i - a_i}{\max(a_i, b_i)}$

其中：

$a_i$ ：点 $i$ 到同簇其他点的平均距离
$b_i$ ：点 $i$ 到最近异簇所有点的平均距离

数学表达： $a_i = \frac{1}{|C_k|-1}\sum_{j \in C_k, j \neq i}d(\mathbf{x}_i, \mathbf{x}_j)$ $b_i = \min_{l \neq k}\frac{1}{|C_l|}\sum_{j \in C_l}d(\mathbf{x}_i, \mathbf{x}_j)$

整体轮廓系数： $S = \frac{1}{n}\sum_{i=1}^{n}s_i$

取值范围： $s_i \in [-1, 1]$

$s_i$ 接近1：聚类效果好
$s_i$ 接近0：点在簇边界上
$s_i$ 接近-1：点可能被分配到错误的簇

4.1.2 Calinski-Harabasz指数#

定义： $CH = \frac{\text{tr}(B_K)}{\text{tr}(W_K)} \cdot \frac{n-K}{K-1}$

其中：

$B_K$ ：簇间散布矩阵
$W_K$ ：簇内散布矩阵

数学表达： $B_K = \sum_{k=1}^{K}|C_k|(\boldsymbol{\mu}_k - \boldsymbol{\mu})(\boldsymbol{\mu}_k - \boldsymbol{\mu})^T$ $W_K = \sum_{k=1}^{K}\sum_{i \in C_k}(\mathbf{x}_i - \boldsymbol{\mu}_k)(\mathbf{x}_i - \boldsymbol{\mu}_k)^T$

其中 $\boldsymbol{\mu} = \frac{1}{n}\sum_{i=1}^{n}\mathbf{x}_i$ 是全局均值。

解释：CH指数越大，表示簇间分离度越高，簇内紧密度越高。

4.1.3 Davies-Bouldin指数#

定义： $DB = \frac{1}{K}\sum_{k=1}^{K}\max_{l \neq k}\left(\frac{\sigma_k + \sigma_l}{d(\boldsymbol{\mu}_k, \boldsymbol{\mu}_l)}\right)$

其中：

$\sigma_k = \frac{1}{|C_k|}\sum_{i \in C_k}\|\mathbf{x}_i - \boldsymbol{\mu}_k\|$ ：簇内平均距离
$d(\boldsymbol{\mu}_k, \boldsymbol{\mu}_l)$ ：簇中心间距离

解释：DB指数越小，表示聚类效果越好。

4.2 外部评估指标#

4.2.1 调整兰德指数（Adjusted Rand Index, ARI）#

当有真实标签时，可以使用外部指标评估聚类效果。

兰德指数： $RI = \frac{TP + TN}{TP + FP + FN + TN}$

其中：

TP：同簇且同类的点对数
TN：异簇且异类的点对数
FP：同簇但异类的点对数
FN：异簇但同类的点对数

调整兰德指数： $ARI = \frac{RI - E[RI]}{\max(RI) - E[RI]}$

ARI的取值范围为[-1, 1]，值越大表示聚类效果越好。

4.2.2 归一化互信息（Normalized Mutual Information, NMI）#

互信息： $MI(C, T) = \sum_{k=1}^{K}\sum_{l=1}^{L}P(k,l)\log\frac{P(k,l)}{P(k)P(l)}$

其中C是聚类结果，T是真实标签。

归一化互信息： $NMI = \frac{MI(C, T)}{\sqrt{H(C) \cdot H(T)}}$

NMI的取值范围为[0, 1]，值越大表示聚类效果越好。

第五部分：实际应用技巧与最佳实践#

5.1 数据预处理策略#

5.1.1 特征标准化#

问题：不同特征的量纲和数值范围差异很大时，欧几里得距离会被大数值特征主导。

解决方案：

Z-score标准化： $\mathbf{x}_i^{(j)} = \frac{x_i^{(j)} - \mu^{(j)}}{\sigma^{(j)}}$
Min-Max标准化： $\mathbf{x}_i^{(j)} = \frac{x_i^{(j)} - \min^{(j)}}{\max^{(j)} - \min^{(j)}}$
鲁棒标准化： $\mathbf{x}_i^{(j)} = \frac{x_i^{(j)} - \text{median}^{(j)}}{\text{IQR}^{(j)}}$

5.1.2 异常值处理#

检测方法：

统计方法：3σ原则，IQR方法
基于距离：局部异常因子（LOF）
基于密度：DBSCAN预处理

处理策略：

删除异常值
异常值截断（Winsorization）
使用鲁棒的聚类算法（如K-medoids）

5.1.3 维度降维#

高维数据的挑战：

维度诅咒：高维空间中距离失去区分性
计算复杂度增加
噪声特征影响

降维方法：

主成分分析（PCA）： $\mathbf{Y} = \mathbf{X}\mathbf{W}$ 其中W是主成分矩阵
t-SNE：适合可视化，保持局部结构
UMAP：保持全局和局部结构
特征选择：基于方差、相关性或模型的特征选择

5.2 K值选择的高级方法#

5.2.1 信息准则方法#

贝叶斯信息准则（BIC）： $BIC(K) = -2\ln(L) + K \cdot \ln(n)$

其中L是似然函数，第二项是复杂度惩罚。

赤池信息准则（AIC）： $AIC(K) = -2\ln(L) + 2K$

选择使BIC或AIC最小的K值。

5.2.2 Gap统计量#

定义： $\text{Gap}(K) = \mathbb{E}[\log(W_K^*)] - \log(W_K)$

其中：

$W_K$ ：实际数据的簇内平方和
$W_K^*$ ：参考分布（如均匀分布）的簇内平方和

算法步骤：

对每个K，计算实际数据的 $W_K$
生成B个参考数据集，计算 $W_K^{*(b)}$
计算Gap统计量和标准误差
选择满足Gap(K) ≥ Gap(K+1) - s_{K+1}的最小K

5.2.3 X-means算法#

核心思想：自动确定K值，通过BIC准则决定是否分裂簇。

算法流程：

从K=1开始运行K-means
对每个簇，尝试分裂为两个子簇
使用BIC准则判断分裂是否改善模型
重复直到没有簇需要分裂

5.3 处理特殊数据类型#

5.3.1 类别型数据聚类#

K-modes算法：

距离度量：使用汉明距离 $d(\mathbf{x}_i, \mathbf{x}_j) = \sum_{l=1}^{d}\delta(x_{il}, x_{jl})$

其中 $\delta(a,b) = 0$ 如果 $a=b$ ，否则为1。

簇中心：使用众数而非均值 $\text{mode}_k^{(l)} = \arg\max_{v}\sum_{i \in C_k}\mathbf{1}(x_i^{(l)} = v)$

5.3.2 混合数据类型#

K-prototypes算法：结合K-means和K-modes

距离度量： $d(\mathbf{x}_i, \mathbf{x}_j) = \sum_{l=1}^{d_n}(x_{il}^{(n)} - x_{jl}^{(n)})^2 + \gamma\sum_{l=1}^{d_c}\delta(x_{il}^{(c)}, x_{jl}^{(c)})$

其中 $\gamma$ 是权重参数，平衡数值型和类别型特征的贡献。

5.4 大规模数据处理#

5.4.1 分布式K-means#

MapReduce框架：

Map阶段：

输入：数据分片和当前簇中心
输出：(簇ID, 点的坐标和计数)

Reduce阶段：

输入：同一簇的所有点
输出：新的簇中心

Spark实现：

1
# 伪代码
2
def distributed_kmeans(data_rdd, k, max_iter):
3
    centers = initialize_centers(k)
4

5
    for iteration in range(max_iter):
6
        # 广播簇中心
7
        broadcast_centers = spark.broadcast(centers)
8

9
        # 分配点到最近簇
10
        assignments = data_rdd.map(lambda x: assign_to_cluster(x, broadcast_centers.value))
11

12
        # 计算新簇中心
13
        new_centers = assignments.reduceByKey(lambda a, b: combine_points(a, b)) \
14
                                .map(lambda x: compute_center(x))
15

16
        centers = new_centers.collect()

5.4.2 在线K-means#

流数据处理：

算法特点：

数据逐个到达，无法存储所有历史数据
需要实时更新簇中心
内存使用固定

更新策略： $\boldsymbol{\mu}_k^{(t+1)} = \frac{n_k^{(t)}\boldsymbol{\mu}_k^{(t)} + \mathbf{x}_{new}}{n_k^{(t)} + 1}$

其中 $n_k^{(t)}$ 是簇k在时刻t的点数。

第六部分：实际项目案例分析#

6.1 客户细分案例#

6.1.1 业务背景#

目标：基于客户行为数据进行市场细分，制定差异化营销策略。

数据特征：

人口统计学特征：年龄、性别、收入、教育水平
行为特征：购买频率、平均订单金额、品类偏好
时间特征：客户生命周期、最近购买时间

6.1.2 技术实现#

特征工程：

RFM分析：
- Recency：最近购买时间
- Frequency：购买频率
- Monetary：购买金额

特征变换：

1
# 对数变换处理偏态分布
2
df['log_monetary'] = np.log1p(df['monetary'])
3

4
# 标准化处理
5
scaler = StandardScaler()
6
features_scaled = scaler.fit_transform(features)

聚类分析：

1
# K值选择
2
inertias = []
3
silhouette_scores = []
4
K_range = range(2, 11)
5

6
for k in K_range:
7
    kmeans = KMeans(n_clusters=k, random_state=42, n_init=10)
8
    kmeans.fit(features_scaled)
9
    inertias.append(kmeans.inertia_)
10
    silhouette_scores.append(silhouette_score(features_scaled, kmeans.labels_))
11

12
# 最终聚类
13
optimal_k = 5
14
kmeans = KMeans(n_clusters=optimal_k, random_state=42)
15
cluster_labels = kmeans.fit_predict(features_scaled)

6.1.3 结果解释#

簇特征分析：

簇ID	客户类型	特征描述	营销策略
0	高价值客户	高频高额购买	VIP服务，个性化推荐
1	潜力客户	中频中额购买	促销活动，品类扩展
2	新客户	低频低额购买	欢迎礼包，引导购买
3	流失风险客户	长时间未购买	召回活动，优惠券
4	价格敏感客户	促销时购买	定向折扣，限时优惠

6.2 图像分割案例#

6.2.1 技术原理#

颜色空间聚类：将图像像素在颜色空间中进行聚类，实现图像分割。

算法流程：

将图像从RGB转换到Lab颜色空间
提取像素的颜色特征
使用K-means进行聚类
将聚类结果映射回图像

6.2.2 代码实现#

1
import cv2
2
import numpy as np
3
from sklearn.cluster import KMeans
4

5
def image_segmentation(image_path, k=3):
6
    # 读取图像
7
    image = cv2.imread(image_path)
8
    image = cv2.cvtColor(image, cv2.COLOR_BGR2LAB)
9

10
    # 重塑为二维数组
11
    pixel_values = image.reshape((-1, 3))
12
    pixel_values = np.float32(pixel_values)
13

14
    # K-means聚类
15
    kmeans = KMeans(n_clusters=k, random_state=42)
16
    labels = kmeans.fit_predict(pixel_values)
17
    centers = kmeans.cluster_centers_
18

19
    # 将聚类结果映射回图像
20
    centers = np.uint8(centers)
21
    segmented_data = centers[labels.flatten()]
22
    segmented_image = segmented_data.reshape(image.shape)
23

24
    return segmented_image

6.3 文档聚类案例#

6.3.1 文本预处理#

TF-IDF特征提取： $\text{TF-IDF}(t,d) = \text{TF}(t,d) \times \text{IDF}(t)$

其中： $\text{TF}(t,d) = \frac{\text{count}(t,d)}{\sum_{t' \in d}\text{count}(t',d)}$ $\text{IDF}(t) = \log\frac{N}{|\{d : t \in d\}|}$

降维处理：使用截断SVD（LSA）降维： $\mathbf{X} \approx \mathbf{U}_k\mathbf{\Sigma}_k\mathbf{V}_k^T$

6.3.2 聚类效果评估#

主题一致性：使用困惑度和主题连贯性评估聚类质量。

可视化分析：使用t-SNE将高维文档向量投影到2D空间进行可视化。

学习总结与思考#

算法优势与局限性#

K-means的优势：

简单高效：算法原理直观，实现简单，计算复杂度低
可扩展性：适合大规模数据处理，有多种优化变种
广泛适用：在多个领域都有成功应用案例
理论基础：有完整的数学理论支撑

主要局限性：

K值选择：需要预先指定簇数，缺乏自适应性
形状假设：假设簇是球形的，无法处理复杂形状
初始化敏感：结果依赖于初始化，可能陷入局部最优
异常值敏感：均值计算容易受异常值影响

实际应用建议#

数据预处理至关重要：标准化、异常值处理、降维等步骤直接影响聚类效果
多种方法结合：使用多个指标选择K值，结合领域知识验证结果
算法选择：根据数据特点选择合适的变种算法
结果解释：聚类结果需要结合业务背景进行解释和验证

未来发展方向#

深度聚类：结合深度学习的端到端聚类方法
自适应聚类：能够自动确定簇数和形状的算法
多模态聚类：处理图像、文本、音频等多种数据类型
增量学习：支持在线学习和概念漂移的聚类算法

K-means作为聚类分析的基石算法，虽然有其局限性，但其简单性和有效性使其在实际应用中仍然占据重要地位。通过深入理解其数学原理、掌握各种变种算法、熟练运用评估方法，我们能够在实际项目中更好地发挥其价值。