全面了解机器语言之kmeans
深入理解 KMeans 聚类算法：原理、实现与应用
在机器学习领域，聚类算法作为无监督学习的核心技术之一，一直以来都是数据挖掘和模式识别的重要工具。其中，KMeans 算法以其简洁的原理、高效的计算性能和广泛的适用性，成为最受欢迎的聚类算法之一。本文将从算法原理、数学推导、实现细节到实际应用，全方位解析 KMeans 算法，并通过完整的代码案例帮助读者深入理解其工作机制。
一、聚类算法与 KMeans 的定位
聚类算法的核心目标是将数据集中具有相似特征的样本自动划分到同一类别，使得类内相似度最大化且类间相似度最小化。与监督学习不同，聚类不需要预先标注的训练数据，而是通过数据本身的分布特征发现潜在的结构模式。这种特性使其在客户分群、异常检测、图像分割等无标签数据场景中发挥着不可替代的作用。
在众多聚类算法中，KMeans 占据着举足轻重的地位。自 1967 年由 MacQueen 提出以来，经过半个多世纪的发展，其衍生出了 KMeans++、MiniBatchKMeans 等改进版本，但核心思想始终保持一致。据 KDnuggets 2023 年的调研数据显示，KMeans 在工业界的使用率高达 68%，远超层次聚类（23%）和 DBSCAN（19%）等其他算法，这与其简单易懂、计算高效、可扩展性强的特点密不可分。
二、KMeans 算法的核心原理
2.1 基本思想
KMeans 算法的工作流程可以概括为 "初始化 - 分配 - 更新" 的迭代过程：
- 确定聚类数量 K：用户需要预先指定将数据划分为 K 个类别
- 初始化质心：从数据集中随机选择 K 个样本作为初始聚类中心（质心）
- 分配样本：计算每个样本与 K 个质心的距离，将样本分配到距离最近的质心所在的簇
- 更新质心：计算每个簇内所有样本的均值，将其作为新的质心
- 迭代优化：重复步骤 3 和 4，直到质心位置不再显著变化或达到最大迭代次数
这种基于原型的聚类方法通过不断调整质心位置，最终使得各样本到其所属质心的距离之和最小化。
2.2 距离度量方式
KMeans 算法的性能很大程度上依赖于距离度量的选择，常用的距离计算方式包括：
- 欧氏距离（Euclidean Distance）：最常用的距离度量方式，适用于连续型数据，计算两个 n 维向量\(X=(x_1,x_2,...,x_n)\)和\(Y=(y_1,y_2,...,y_n)\)之间的直线距离：
\(d(X,Y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}\)
- 曼哈顿距离（Manhattan Distance）：适用于高维数据或需要降低计算复杂度的场景，计算各维度差值的绝对值之和：
\(d(X,Y)=\sum_{i=1}^{n}|x_i-y_i|\)
- 余弦相似度（Cosine Similarity）：常用于文本聚类等特征向量稀疏的场景，通过向量夹角的余弦值衡量相似度：
\(cos\theta=\frac{X\cdot Y}{||X||\cdot||Y||}=\frac{\sum_{i=1}^{n}x_iy_i}{\sqrt{\sum_{i=1}^{n}x_i^2}\sqrt{\sum_{i=1}^{n}y_i^2}}\)
在默认情况下，KMeans 算法采用欧氏距离作为度量标准，这也是大多数场景下的最优选择。
2.3 目标函数与收敛性
KMeans 算法的优化目标是最小化所有样本到其所属质心的距离平方和（Sum of Squared Errors，SSE），目标函数定义为：
\(J=\sum_{k=1}^{K}\sum_{x_i\in C_k}||x_i-\mu_k||^2\)
其中，\(C_k\)表示第 k 个簇，\(\mu_k\)是第 k 个簇的质心，\(||x_i-\mu_k||^2\)是样本\(x_i\)到质心\(\mu_k\)的欧氏距离平方。
由于目标函数\(J\)是非凸函数，算法可能收敛到局部最优解而非全局最优解。这也是为什么 KMeans 算法通常需要多次运行并选择 SSE 最小的结果作为最终聚类方案的原因。理论上，随着迭代次数的增加，\(J\)的值会单调递减并最终收敛，因为每次更新质心时都会选择使\(J\)最小化的新质心位置。
三、KMeans 算法的优缺点分析
3.1 优点
- 计算效率高：时间复杂度约为\(O(nkt)\)，其中 n 是样本数量，k 是聚类数，t 是迭代次数，通常远小于 n，适合大规模数据集
- 实现简单：核心逻辑仅包含距离计算和均值更新，易于理解和实现
- 可扩展性强：能够处理百万级甚至更大规模的数据集，通过 MiniBatch 等变体可进一步提升处理速度
- 结果易于解释：聚类中心具有明确的物理意义（簇内样本的均值），便于后续分析
3.2 缺点
- 需要预先指定 K 值：K 值的选择对聚类结果影响巨大，而在实际应用中往往难以确定最优 K 值
- 对初始质心敏感：不同的初始质心可能导致完全不同的聚类结果，容易陷入局部最优
- 对噪声和异常值敏感：异常值会显著影响质心的计算，导致聚类偏差
- 难以处理非凸形状簇：对于呈环形、条形等复杂分布的数据，聚类效果较差
- 对特征尺度敏感：不同量级的特征会主导距离计算，需要预先进行标准化处理
3.3 改进版本
针对上述缺点，研究者们提出了多种改进算法：
- KMeans++：通过改进初始质心的选择方式（使初始质心尽可能远离），提高了算法收敛到全局最优的概率
- MiniBatchKMeans：使用随机抽样的小批量数据更新质心，大幅提升处理大规模数据的效率
- ISODATA：能够自动调整聚类数量，通过合并和分裂操作优化聚类结果
- Kernel KMeans：通过核函数将数据映射到高维空间，解决非凸形状簇的聚类问题
四、K 值的确定方法
K 值的选择是 KMeans 算法应用中的关键难题，以下是几种常用的确定方法：
4.1 肘部法（Elbow Method）
肘部法通过绘制不同 K 值对应的 SSE 曲线，选择曲线开始趋于平缓的 "肘部" 位置对应的 K 值作为最优解。当 K 值较小时，随着 K 的增加，SSE 会急剧下降；当 K 值超过某个临界点后，SSE 的下降速度明显放缓，此时再增加 K 值对聚类效果的提升有限，该临界点即为最优 K 值。
4.2 轮廓系数法（Silhouette Score）
轮廓系数综合考虑了样本的类内相似度和类间相似度，取值范围为 [-1,1]。对于每个样本 i，计算：
- \(a_i\)：样本 i 与其同簇内其他样本的平均距离（类内不相似度）
- \(b_i\)：样本 i 与最近异簇内所有样本的平均距离（类间不相似度）
样本 i 的轮廓系数为：\(s_i=\frac{b_i-a_i}{max(a_i,b_i)}\)
整体数据集的轮廓系数为所有样本轮廓系数的平均值，越接近 1 表示聚类效果越好。通过计算不同 K 值对应的轮廓系数，选择系数最大的 K 值作为最优解。
4.3 Gap 统计量（Gap Statistic）
Gap 统计量通过比较实际数据的聚类效果与参考数据（通常是随机生成的均匀分布数据）的聚类效果来确定最优 K 值。定义为：
\(Gap(k)=E[log(D_k)]-log(D_k)\)
其中\(D_k\)是实际数据的聚类分散度，\(E[log(D_k)]\)是参考数据的期望分散度。当 Gap 统计量趋于稳定时的 K 值即为最优解。
五、KMeans 算法的实现步骤
5.1 数据预处理
在应用 KMeans 算法前，需要对数据进行必要的预处理：
- 缺失值处理：通过均值填充、中位数填充或插值法处理缺失数据
- 标准化 / 归一化：由于 KMeans 对特征尺度敏感，需将数据转换到相同量级，常用方法包括：
- 标准化：\(x'=\frac{x-\mu}{\sigma}\)（均值为 0，标准差为 1）
- 归一化：\(x'=\frac{x-min}{max-min}\)（映射到 [0,1] 区间）
- 异常值检测：使用 Z-score、IQR 等方法识别并处理异常值，避免其影响聚类中心
5.2 算法实现流程
以下是 KMeans 算法的详细实现步骤：
- 初始化参数：设置聚类数量 K、最大迭代次数、收敛阈值等
- 选择初始质心：
- 随机选择 K 个样本作为初始质心（传统方法）
- 采用 KMeans++ 策略选择初始质心（改进方法）
- 分配样本到最近簇：
- 计算每个样本与所有质心的距离
- 将样本分配到距离最近的质心所在簇
- 更新质心位置：
- 计算每个簇内所有样本的均值
- 将均值作为新的质心位置
- 检查收敛条件：
- 若质心位置变化小于收敛阈值，或达到最大迭代次数，则停止迭代
- 否则返回步骤 3 继续迭代
- 输出结果：返回最终的聚类标签和质心位置
六、完整代码案例与解析
下面将通过 Python 实现 KMeans 算法，并使用真实数据集进行聚类分析。我们将分别展示使用自定义实现和 Scikit-learn 库的两种方式，以便读者更好地理解算法细节。
6.1 自定义 KMeans 实现
首先，我们手动实现 KMeans 算法的核心逻辑，包括距离计算、质心更新和迭代优化等步骤：
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.preprocessing import StandardScaler
class CustomKMeans:
def __init__(self, n_clusters=2, max_iter=100, tol=1e-4, random_state=None):
"""
初始化KMeans模型
参数:
n_clusters: 聚类数量
max_iter: 最大迭代次数
tol: 收敛阈值，当质心变化小于该值时停止迭代
random_state: 随机数种子，保证结果可复现
"""
self.n_clusters = n_clusters
self.max_iter = max_iter
self.tol = tol
self.random_state = random_state
self.centroids_ = None # 质心
self.labels_ = None # 聚类标签
self.inertia_ = None # SSE值
def _euclidean_distance(self, X, centroids):
"""计算样本与质心之间的欧氏距离"""
distances = []
for centroid in centroids:
# 计算每个样本到当前质心的距离
dist = np.sqrt(np.sum((X - centroid) ** 2, axis=1))
distances.append(dist)
# 转换为形状为(n_samples, n_clusters)的数组
return np.array(distances).T
def _initialize_centroids(self, X):
"""随机选择K个样本作为初始质心"""
np.random.seed(self.random_state)
# 从数据集中随机选择K个不同的样本索引
indices = np.random.choice(X.shape[0], self.n_clusters, replace=False)
return X[indices]
def fit(self, X):
"""训练KMeans模型"""
# 初始化质心
self.centroids_ = self._initialize_centroids(X)
for _ in range(self.max_iter):
# 计算每个样本到各质心的距离
distances = self._euclidean_distance(X, self.centroids_)
# 为每个样本分配最近的簇
self.labels_ = np.argmin(distances, axis=1)
# 计算新的质心
new_centroids = np.array([X[self.labels_ == k].mean(axis=0)
for k in range(self.n_clusters)])
# 计算质心变化量
centroid_shift = np.sum(np.sqrt(np.sum((new_centroids - self.centroids_) **2, axis=1)))
# 更新质心
self.centroids_ = new_centroids
# 检查是否收敛
if centroid_shift < self.tol:
break
# 计算最终的SSE
self.inertia_ = np.sum([np.sum((X[self.labels_ == k] - self.centroids_[k])** 2)
for k in range(self.n_clusters)])
return self
def predict(self, X):
"""预测新样本的聚类标签"""
distances = self._euclidean_distance(X, self.centroids_)
return np.argmin(distances, axis=1)
# 生成测试数据
X, y_true = make_blobs(n_samples=500, centers=4, cluster_std=0.60, random_state=0)
# 数据标准化
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
# 测试自定义KMeans
custom_kmeans = CustomKMeans(n_clusters=4, max_iter=100, random_state=42)
custom_kmeans.fit(X_scaled)
custom_labels = custom_kmeans.labels_
custom_centroids = custom_kmeans.centroids_
# 计算轮廓系数
silhouette_avg = silhouette_score(X_scaled, custom_labels)
print(f"自定义KMeans的轮廓系数: {silhouette_avg:.4f}")
print(f"自定义KMeans的SSE值: {custom_kmeans.inertia_:.4f}")
# 可视化聚类结果
plt.figure(figsize=(10, 6))
plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=custom_labels, s=50, cmap='viridis')
plt.scatter(custom_centroids[:, 0], custom_centroids[:, 1], s=200, marker='X',
c='red', label='质心')
plt.title('自定义KMeans聚类结果', fontsize=15)
plt.xlabel('特征1', fontsize=12)
plt.ylabel('特征2', fontsize=12)
plt.legend()
plt.grid(True, linestyle='--', alpha=0.7)
plt.show()
6.2 使用 Scikit-learn 实现 KMeans
Scikit-learn 库提供了高效的 KMeans 实现，包含了 KMeans++ 初始化等优化特性，实际应用中推荐使用：
from sklearn.cluster import KMeans
from sklearn.datasets import load_iris, make_moons, make_circles
from sklearn.model_selection import train_test_split
from sklearn.metrics import adjusted_rand_score, normalized_mutual_info_score
import seaborn as sns
# 1. 测试经典数据集
iris = load_iris()
X_iris = iris.data
y_iris = iris.target
# 数据标准化
X_iris_scaled = StandardScaler().fit_transform(X_iris)
# 使用KMeans++初始化
kmeans_iris = KMeans(n_clusters=3, init='k-means++', n_init=10,
max_iter=300, random_state=42)
kmeans_iris.fit(X_iris_scaled)
iris_labels = kmeans_iris.labels_
# 评估聚类效果（已知真实标签时）
ari = adjusted_rand_score(y_iris, iris_labels)
nmi = normalized_mutual_info_score(y_iris, iris_labels)
print(f"鸢尾花数据集的调整兰德指数: {ari:.4f}")
print(f"鸢尾花数据集的标准化互信息: {nmi:.4f}")
# 可视化聚类结果（使用前两个特征）
plt.figure(figsize=(12, 5))
plt.subplot(1, 2, 1)
plt.scatter(X_iris_scaled[:, 0], X_iris_scaled[:, 1], c=y_iris, s=50, cmap='viridis')
plt.title('真实标签', fontsize=15)
plt.xlabel(iris.feature_names[0], fontsize=12)
plt.ylabel(iris.feature_names[1], fontsize=12)
plt.grid(True, linestyle='--', alpha=0.7)
plt.subplot(1, 2, 2)
plt.scatter(X_iris_scaled[:, 0], X_iris_scaled[:, 1], c=iris_labels, s=50, cmap='viridis')
plt.scatter(kmeans_iris.cluster_centers_[:, 0</doubaocanvas>