K-Means聚类算法 - 机器学习-学习笔记-上海佼艾

一、聚类概述

聚类（Clustering）是机器学习中无监督学习（Unsupervised Learning）的核心任务之一。与有监督学习不同，聚类算法处理的是没有标签的数据，其目标是将数据集中相似的样本自动划分到同一个组（即"簇"），使得同一簇内的样本尽可能相似，不同簇之间的样本尽可能不同。

聚类的本质可以概括为两个基本原则：组内相似性最大化（Maximize Intra-cluster Similarity）和组间差异性最大化（Maximize Inter-cluster Dissimilarity）。这两个原则是所有聚类算法设计的出发点。

在实际应用中，聚类广泛用于客户分群、图像分割、文档主题挖掘、异常检测、生物信息学等领域。不同的应用场景对聚类算法有不同的需求，因此诞生了多种聚类算法。以下是四种最常用的聚类算法对比：

算法	核心思想	簇形状	是否需指定K	适用场景
K-Means	基于距离的划分方法	球形簇	是	大规模数据、数值型特征
层次聚类	自底向上/自顶向下合并或分裂	任意形状	否	小规模数据、层次结构分析
DBSCAN	基于密度的聚类	任意形状	否	存在噪声、簇形状不规则
高斯混合模型（GMM）	基于概率分布的软聚类	椭圆形簇	是	数据存在重叠、需要概率输出

在众多聚类算法中，K-Means因其简单、高效、可解释性强而成为最经典、应用最广泛的聚类算法之一，也是学习无监督学习的首选入门算法。

二、K-Means原理

2.1 算法核心步骤

K-Means算法最早由Stuart Lloyd于1957年提出（故也称为Lloyd算法），其核心思路是通过迭代优化，将数据集划分为K个互不相交的簇。算法步骤如下：

选择K个初始中心：从数据集中随机选择K个样本作为初始簇中心（centroids）。
分配样本到最近的中心：对于每个样本点，计算其到K个簇中心的距离（通常使用欧氏距离），将其分配到距离最近的簇。
更新簇中心：对每个簇，计算该簇内所有样本的均值（mean），作为新的簇中心。
重复迭代：重复步骤2和3，直到满足收敛条件。

整个过程直观地描述了"物以类聚"的思想：每个簇由其内部样本的均值中心来代表，样本根据与中心的距离决定归属。

2.2 数学目标函数

K-Means的数学目标是最小化所有样本点到其所属簇中心距离的平方和，即簇内误差平方和（Sum of Squared Errors, SSE），也称为惯性（Inertia）：

SSE = Σᵢ₌₁ⁿ Σₖ₌₁ᵏ wᵢₖ · ||xᵢ − μₖ||²

其中xᵢ是第i个样本，μₖ是第k个簇的中心，wᵢₖ是指示变量（若样本i属于簇k则值为1，否则为0）。K-Means本质上是求解这个优化问题，但由于这是一个NP难问题（需要穷举所有划分方式），Lloyd算法采用的是一种贪心迭代策略，在实践中能快速收敛到局部最优解。

2.3 收敛条件

K-Means迭代会持续进行，直到满足以下任一条件：

簇中心不再变化：连续两次迭代中，所有簇中心的位置变化小于设定的阈值（tol）。
达到最大迭代次数：迭代次数达到预设的max_iter上限。
SSE变化极小：目标函数（SSE）的变化小于指定阈值。

理论上，K-Means保证会在有限步内收敛。在实际应用中，通常设置max_iter=300并结合一个较小的tol（如1e-4）来平衡精度和效率。

2.4 时间复杂度

K-Means的每次迭代的时间复杂度为O(n × K × d)，其中n是样本数量，K是簇的数量，d是特征维度。具体来说：

分配步骤：计算每个样本到K个中心的距离，复杂度为O(n × K × d)。
更新步骤：对每个簇求均值，复杂度为O(n × d)。

设迭代次数为t，则总复杂度为O(t × n × K × d)。由于t通常较小（一般几十次即可收敛），且K和d也远小于n，因此K-Means在大规模数据上仍然非常高效。

三、K值选择

K-Means要求用户预先指定K值（簇的数量），这是K-Means最关键的参数之一。选择不合适的K值会严重影响聚类效果。以下介绍五种常用的K值选择方法。

3.1 肘部法则（Elbow Method）

肘部法是最直观的K值选择方法。其思路是：计算不同K值对应的SSE（惯性），然后绘制K值与SSE的关系曲线。随着K增大，每个簇内部更紧凑，SSE自然会下降。但当K达到某个值后，SSE的下降速度会急剧减缓，形成曲线上的"肘点"（elbow），该点即为最优K值。

肘部法的优点是简单直观，缺点是并非所有数据集的SSE曲线都有清晰的"肘部"——当数据分布连续时，曲线可能平滑下降，难以找到拐点。此时需要结合其他方法综合判断。

# 肘部法则示例代码
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

# 计算不同K值的惯性
inertias = []
K_range = range(1, 11)
for k in K_range:
    kmeans = KMeans(n_clusters=k, random_state=42)
    kmeans.fit(X)
    inertias.append(kmeans.inertia_)

# 绘制肘部图
plt.plot(K_range, inertias, 'bo-')
plt.xlabel('K (簇数量)')
plt.ylabel('惯性 (SSE)')
plt.title('肘部法则确定最优K值')
plt.show()

3.2 轮廓系数（Silhouette Score）

轮廓系数同时考虑了簇内凝聚力和簇间分离度，是评估聚类效果的综合指标。对于每个样本i，轮廓系数定义为：

s(i) = [b(i) − a(i)] / max{a(i), b(i)}

其中a(i)是样本i与同簇其他样本的平均距离（簇内不相似度），b(i)是样本i与最近邻簇中所有样本的平均距离（簇间不相似度）。轮廓系数的取值范围为[-1, 1]：

接近+1：样本远离相邻簇且位于自身簇内部，聚类效果好。
接近0：样本位于两个簇的边界上，聚类结果模糊。
接近-1：样本可能被分配到了错误的簇。

整体轮廓分数是所有样本轮廓系数的平均值。选择使平均轮廓分数最大的K值，通常能获得较好的聚类效果。

# 轮廓系数选择K值
from sklearn.metrics import silhouette_score

silhouette_scores = []
for k in range(2, 11):
    kmeans = KMeans(n_clusters=k, random_state=42)
    labels = kmeans.fit_predict(X)
    score = silhouette_score(X, labels)
    silhouette_scores.append(score)

best_k = range(2, 11)[silhouette_scores.index(max(silhouette_scores))]
print(f"最优K值: {best_k}, 轮廓系数: {max(silhouette_scores):.4f}")

3.3 Calinski-Harabasz指数

Calinski-Harabasz指数（也称方差比准则）基于簇间离散度与簇内离散度的比值来评估聚类质量。该指数越大，表示聚类效果越好。其计算公式为：

CH = [B / (K − 1)] / [W / (n − K)]

其中B是簇间协方差矩阵的迹（衡量簇间分离度），W是簇内协方差矩阵的迹（衡量簇内紧密度）。CH指数越大，说明簇间距离越远、簇内距离越近。

Calinski-Harabasz指数的计算速度比轮廓系数快很多，适合大规模数据集。但它倾向于选择凸形且大小相近的簇，对非球形簇的评价可能不够准确。

3.4 Davies-Bouldin指数

Davies-Bouldin指数衡量每个簇与其最相似簇之间的平均相似度。相似度定义为簇内平均距离之和与簇心距离之比。该指数越小越好：

对每个簇i，计算其与所有其他簇j的相似度Rᵢⱼ。
取每个簇的最大Rᵢⱼ，再计算所有簇的平均值。
DB值越小，表示簇内越紧凑、簇间越分离。

Davies-Bouldin指数的一个优势是计算简单、易于理解，但同样对非球形簇的评价效果有限。

3.5 Gap Statistic

Gap Statistic是Tibshirani等人在2001年提出的方法，它通过与零假设（无聚类结构的均匀分布）下的期望SSE进行比较来选择K值。Gap值定义为：

Gap(K) = E*[log(SSEₖ)] − log(SSEₖ)

其中E*[log(SSEₖ)]是在均匀分布（随机数据）上的期望对数SSE。选择使得Gap(K)最大的K值。Gap Statistic的理论基础扎实，但计算成本较高，因为需要进行多次蒙特卡洛模拟。

四、K-Means的初始化

4.1 随机初始化的问题

K-Means对初始簇中心的选择非常敏感，不同的初始中心可能导致截然不同的聚类结果。标准的随机初始化（从数据集中随机抽取K个样本作为初始中心）存在以下问题：

陷入局部最优：如果初始中心选择不当（如多个中心落在同一个簇内），算法可能收敛到较差的局部最优解，而非全局最优。
结果不稳定：同一数据集上多次运行可能产生不同的聚类结果，影响可重复性。
对异常值敏感：如果随机选中的初始中心是异常值，可能导致大量样本被错误地分配到该簇。

4.2 K-Means++初始化

为解决随机初始化的问题，David Arthur和Sergei Vassilvitskii在2007年提出了K-Means++初始化算法，现在是scikit-learn中K-Means的默认初始化方式。K-Means++的步骤如下：

从数据集中随机选择第一个簇中心。
对于每个样本点x，计算其到最近已选中心的距离D(x)。
以概率正比于D(x)²选择下一个中心（距离现有中心越远的点，被选为新中心的概率越大）。
重复步骤2-3，直到选完K个初始中心。

K-Means++的核心思想是让初始中心尽量分散，覆盖整个数据空间。这能显著提高找到全局最优解的概率，并且理论上保证了O(log K)的近似比。在实际应用中，K-Means++配合适当的n_init参数，几乎总能获得高质量的聚类结果。

4.3 多次运行选择最佳结果（n_init参数）

即使使用了K-Means++初始化，依然存在收敛到局部最优的可能。因此，标准做法是：使用不同的随机种子（random_state）多次运行K-Means，选择SSE最小的那一次作为最终结果。scikit-learn中的n_init参数控制这一行为：

n_init=10（默认值）：使用10个不同的随机种子运行K-Means，取最优结果。
n_init='auto'：自动根据数据规模调整运行次数。
n_init=1：只运行一次，速度快但结果质量无保障。

对于较小数据集（n < 10000），建议保持默认的n_init=10；对于大规模数据，可在计算资源受限时适当减小。设置random_state固定种子则能确保结果可重现。

# 初始化策略对比
from sklearn.cluster import KMeans

# 随机初始化（不推荐）
kmeans_random = KMeans(n_clusters=5, init='random', n_init=1, random_state=42)

# K-Means++初始化（推荐，默认）
kmeans_plus = KMeans(n_clusters=5, init='k-means++', n_init=10, random_state=42)

# 自定义初始化（传入初始中心坐标）
import numpy as np
custom_centers = np.array([[1, 2], [3, 4], [5, 6], [7, 8], [9, 10]])
kmeans_custom = KMeans(n_clusters=5, init=custom_centers, n_init=1)

五、K-Means的scikit-learn实现

5.1 KMeans参数详解

scikit-learn中的KMeans类是K-Means算法的标准实现，提供了丰富的参数控制。以下是最常用的参数：

参数	默认值	说明
n_clusters	8	簇的数量K，最重要的参数
init	'k-means++'	初始化方法：'k-means++', 'random' 或 ndarray
n_init	10	不同初始化运行的次数，取最优
max_iter	300	单次运行的最大迭代次数
tol	1e-4	收敛阈值（惯性变化量）
random_state	None	随机种子，固定后可重现结果
algorithm	'lloyd'	实现算法：'lloyd', 'elkan'（基于三角不等式加速）

5.2 聚类结果属性

训练完成后，KMeans对象提供以下重要属性来访问聚类结果：

cluster_centers_：形状为(K, n_features)的数组，存储每个簇的最终中心坐标。
labels_：形状为(n_samples,)的数组，存储每个样本所属的簇编号（0到K-1）。
inertia_：标量，存储最终的SSE值（所有样本到所属簇中心的距离平方和），用于评估聚类紧密度。
n_iter_：实际迭代次数。

5.3 预测新样本

K-Means训练完成后，可以使用predict方法将新的样本点分配到最近的簇：

# K-Means完整示例
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import numpy as np

# 生成示例数据
X, y_true = make_blobs(n_samples=500, centers=5,
                       cluster_std=0.8, random_state=42)

# 标准化（K-Means对特征尺度敏感）
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# 训练K-Means
kmeans = KMeans(n_clusters=5, init='k-means++',
                n_init=10, max_iter=300, random_state=42)
kmeans.fit(X_scaled)

# 查看结果
print("簇中心:\n", kmeans.cluster_centers_)
print("标签:", kmeans.labels_[:10])
print("SSE (inertia):", kmeans.inertia_)

# 预测新样本
new_samples = np.array([[0, 0], [2, -1], [-2, 3]])
predictions = kmeans.predict(scaler.transform(new_samples))
print("新样本所属簇:", predictions)

六、Mini-Batch K-Means

6.1 基本思想

当数据集规模非常大（百万级以上样本）时，标准的K-Means每次迭代都需要扫描全部数据，计算开销巨大。Mini-Batch K-Means是K-Means的一种高效变体，它借鉴了随机梯度下降的思想：每次迭代只使用数据的一个小批量（mini-batch）来更新簇中心。

Mini-Batch K-Means的算法流程如下：

从数据集中随机抽取一个小批量样本（如batch_size=100或1024）。
将这些样本分配到最近的簇中心（使用当前中心）。
使用批量内的样本按一定学习率更新簇中心（带衰减的移动平均）。
重复以上步骤直到收敛或达到最大迭代次数。

6.2 性能优势

Mini-Batch K-Means的核心优势是速度快、内存小：

每轮迭代只处理小批量数据，计算量远小于标准K-Means。
适合内存无法容纳全部数据的场景（但数据需能通过流式或迭代方式读取）。
在数据量极大时，Mini-Batch K-Means可以在远少于标准K-Means的时间内得到可接受的聚类结果。

代价是聚类质量略有下降（通常在可接受范围内），因为使用了近似计算而非精确的全量计算。

6.3 MiniBatchKMeans参数

scikit-learn的MiniBatchKMeans类提供了以下关键参数：

# Mini-Batch K-Means 示例
from sklearn.cluster import MiniBatchKMeans
import numpy as np

# 生成大规模数据
X_large = np.random.randn(100000, 10)

# 标准K-Means（全量计算）
kmeans = KMeans(n_clusters=50, random_state=42)
kmeans.fit(X_large)

# Mini-Batch K-Means（分批计算）
mbkmeans = MiniBatchKMeans(
    n_clusters=50,          # 簇数量
    batch_size=1024,        # 小批量大小
    max_iter=100,           # 最大迭代次数
    n_init=3,               # 初始化次数
    init='k-means++',       # 初始化方法
    random_state=42
)
mbkmeans.fit(X_large)

# 比较惯性（SSE）
print(f"K-Means SSE: {kmeans.inertia_:.2f}")
print(f"Mini-Batch SSE: {mbkmeans.inertia_:.2f}")

Mini-Batch K-Means的关键参数包括：batch_size（批量大小，默认1024）、max_iter（最大迭代次数，默认100）、n_init（初始化次数，默认3）。对于超大规模数据，适当减小batch_size可以加速迭代，但过小的batch_size会使中心更新不够稳定。

七、K-Means的优缺点

7.1 优点

优势	说明
算法简单直观	核心思想"物以类聚"易于理解，仅需距离计算和均值运算
计算效率高	时间复杂度O(t×n×K×d)，适合大规模数据集
可解释性强	簇中心直接代表该簇的"典型特征"，易于理解和传达
收敛速度快	通常几十次迭代即可收敛，配合Elkan算法可进一步加速
实现成熟	scikit-learn等库提供了高效稳定的实现，开箱即用

7.2 缺点

局限	说明
K值需预设	需要用户预先指定簇数，且K值选择对结果影响大
对初始值敏感	初试中心的选择影响收敛结果，可能陷入局部最优
只能发现球形簇	基于欧氏距离的假设，难以发现复杂形状的簇
对异常值敏感	均值计算会被极端值拉偏，且异常值可能形成孤立簇
对特征尺度敏感	不同特征的量纲差异会扭曲距离计算，需先进行标准化
仅适用数值特征	无法直接处理类别特征，需编码转换

实践建议：使用K-Means前，务必对数据进行标准化处理（StandardScaler），使用K-Means++初始化（默认），并通过肘部法+轮廓系数综合选择K值。如数据存在大量异常值或簇形状不规则，可考虑DBSCAN或层次聚类作为替代。

八、应用场景

8.1 客户分群

客户分群（Customer Segmentation）是K-Means最经典的应用场景之一。电商平台可以根据用户的消费金额、消费频率、浏览行为、购买类别等特征，将用户划分为不同的群体，从而实现精准营销：

高价值活跃用户：高频消费、高客单价，可享受VIP专属服务。
潜在流失用户：近期消费频率明显下降，需推送优惠券激活。
价格敏感型用户：偏好折扣商品，适合促销推送。
新品跟随者：经常购买新品，适合新品试用推广。

在RFM分析（最近消费时间Recency、频率Frequency、金额Monetary）中，K-Means是应用最广泛的聚类工具。

8.2 图像分割

图像分割（Image Segmentation）是将图像划分为多个有意义的区域。K-Means对图像进行分割时，将每个像素看作三维空间中的点（R, G, B通道值），然后进行聚类。同一簇内的像素具有相近的颜色，从而提取出图像中的主要色块。这种方法广泛用于：

颜色量化：将真彩色图像压缩为有限种颜色的调色板。
前景背景分离：当前景和背景颜色差异明显时有效。
图像风格化：提取图像的主色调用于艺术创作。

需要注意的是，K-Means图像分割只考虑颜色信息而忽略空间位置，因此分割结果可能包含不连续的碎片区域。

8.3 文档聚类

在自然语言处理中，K-Means可用于对大量文本进行主题聚类。文档首先通过TF-IDF或词向量（Word2Vec/BERT）转化为数值向量，然后使用K-Means将内容相似的文档聚合在一起。应用包括：

新闻自动分类：将大量新闻按主题类别自动归档。
邮件分类：区分垃圾邮件、工作邮件、个人邮件。
技术文档归类：对企业知识库进行自动整理。

文档聚类的一个挑战是高维稀疏特征空间（词表通常很大）。可以使用降维技术（如PCA、TruncatedSVD）先降低维度再进行聚类，以提高效果和速度。

8.4 异常检测

基于K-Means的异常检测（Anomaly Detection）原理简单而有效：正常样本会聚集到某个簇中心附近，而异常点（离群点）则远离所有簇中心。具体做法是：

使用K-Means对数据进行聚类，得到K个簇。
计算每个样本到其所属簇中心的距离。
设置一个距离阈值（如95百分位数），超过该阈值的样本标记为异常。

这种方法简单快速，适用于信用卡欺诈检测、工业设备故障预警、网络入侵检测等实时性要求较高的场景。但需要注意的是，K-Means本身对异常值敏感——如果数据中存在少量极端异常值，可能会干扰聚类结果本身。实践中常先使用其他方法（如孤立森林）初步剔除明显异常，再进行K-Means聚类。

小结：K-Means作为最经典的无监督学习算法，以其简洁高效的特性在众多领域发挥着重要作用。掌握K-Means不仅是学习聚类的起点，也为理解更复杂的无监督学习方法（如GMM、谱聚类、深度聚类）奠定了坚实的基础。在实际项目中，建议结合数据可视化（t-SNE、PCA降维后绘图）来辅助评估聚类效果，使分析过程更加直观和可信。