K-means 聚类是一种基于距离的无监督学习算法，通过迭代优化簇中心最小化簇内误差平方和。文章详细解析了其核心思想、工作流程、数学公式及时间复杂度，分析了优缺点并探讨了 K 值选择方法如肘部法。提供了 scikit-learn 库调用及手动实现的 Python 代码示例，同时介绍了 K-means++ 初始化策略以改善收敛效果。
K-means 聚类是一种常用的基于距离的聚类算法，旨在将数据集划分为 $K$ 个簇。算法的目标是最小化簇内的点到簇中心的距离总和。下面，我们将从 K-means 的底层原理、算法步骤、数学基础、距离度量方法、参数选择、优缺点和源代码实现等角度进行详细解析。
K-means 的目标是将数据集划分为 $K$ 个簇（clusters），使得每个数据点属于距离最近的簇中心。通过反复调整簇中心的位置，K-means 不断优化簇内的紧密度，从而获得尽量紧凑、彼此分离的簇。
如下图：
以簇中心为中心，划分范围
K-means 使用'最近距离'来分组：
K-means 聚类的流程分为两个主要步骤：分配（Assignment）和更新（Update）。以下是详细步骤：
初始化簇中心： 随机选择 $K$ 个数据点作为初始簇中心（centroids）。
选择 K 值： 设定簇的数量 $K$。
假设我们有以下二维数据点，表示顾客的'消费金额'和'访问次数'：
| 数据点编号 | 消费金额（x） | 访问次数（y） |
|---|---|---|
| 点 1 | 1 | 2 |
| 点 2 | 2 | 1 |
| 点 3 | 4 | 5 |
| 点 4 | 5 | 6 |
| 点 5 | 8 | 8 |
目标是将这些点分为 $K=2$ 个簇。
计算每个点到两个质心的欧几里得距离：
$d=\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}$
| 数据点编号 | 到 C1 的距离 | 到 C2 的距离 | 最近质心 | 分配簇 |
|---|---|---|---|---|
| 点 1 | 0 | 8.49 | C1 | 簇 1 |
| 点 2 | 1.41 | 8.06 | C1 | 簇 1 |
| 点 3 | 4.24 | 5.0 | C1 | 簇 1 |
| 点 4 | 5.0 | 4.24 | C2 | 簇 2 |
| 点 5 | 8.49 | 0 | C2 | 簇 2 |
| 数据点编号 | 到 C1 的距离 | 到 C2 的距离 | 最近质心 | 分配簇 |
|---|---|---|---|---|
| 点 1 | 0 | 9.22 | C1 | 1 |
| 点 2 | 1.41 | 9.22 | C1 | 1 |
| 点 3 | 4.24 | 5 | C1 | 1 |
| 点 4 | 5.66 | 3.61 | C2 | 2 |
| 点 5 | 9.22 | 0 | C2 | 2 |
分配结果：
对于每个簇，计算新质心的位置：
更新质心为：
再次计算每个点到新质心的距离，重复'分配簇'和'重新计算质心'步骤，直到质心不再变化。
最终结果：
质心稳定在：
K-means 的目标是最小化簇内平方误差和（Within-Cluster Sum of Squares，WCSS），即每个点到其所属簇中心的距离的平方和，公式如下：
其中：
$||x-\mu _{i}||^{2}$ 表示数据点 $x$ 与簇中心 $\mu _{i}$ 之间的欧氏距离平方。
$\mu _{i}$ 是第 $i$ 个簇的质心。
$x$ 是属于 $C_{i}$ 的数据点。
$C_{i}$ 是第 $i$ 个簇的点集。
$K$ 是簇的数量。
K-means 通常采用欧氏距离来衡量点到簇中心的距离，其公式为：
$d(x,\mu )=\sqrt{\sum_{j=1}^{n}(x_{j}-\mu _{j})^{2}}$
其中 $n$ 是数据的维度。
KMeans(X, K):
1. 随机选择 K 个点作为初始簇中心
2. 重复以下步骤，直到簇中心不再发生变化：
a. 分配每个点到最近的簇中心
b. 重新计算每个簇的中心，作为簇内所有点的均值
3. 返回最终的簇分配和簇中心
对于每个数据点，找到距离最近的簇中心 $\mu_j$：
$c_{i}=arg \underset{j}{min}|| x_{i}-\mu _{j} ||$
更新每个簇的中心 $\mu _{j}$ 为簇内所有点的均值：
$\mu {j}=\frac{1}{| C{j} |}\underset{x\in C_{j}}{\sum }x$
总复杂度：若迭代次数为 $T$，则总体复杂度为 $O(nKT)$。
更新步骤：重新计算每个簇的中心，需要遍历所有点，复杂度也是 $O(n*K)$。
每次分配步骤：需要计算每个点到 $K$ 个簇中心的距离，复杂度为 $O(n*K)$。
确定最佳的簇数 $K$ 是 K-means 聚类中的一个难点。常用的选择方法有：
肘部法（Elbow Method）： 绘制不同 K 值下的 WCSS 图，寻找'肘部'点作为最佳 $K$ 值。
下图可以发现当 k=4 或者 5 时是最佳的情况 SSE 图像下降幅度最大放缓的情况在 4-5 之间。 具体方法可参考肘部法则（Elbow Method）来确定最佳 K 值。
我们可以使用 scikit-learn 中的 KMeans，以及手动实现以便更深入理解。
from sklearn.cluster import KMeans
import numpy as np
# 生成示例数据
X = np.array([[1, 2], [2, 2], [3, 3], [8, 7], [8, 8], [25, 80]])
# 初始化并训练 KMeans 模型
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
# 获取簇标签和簇中心
labels = kmeans.labels_
centroids = kmeans.cluster_centers_
print("Cluster labels:", labels)
print("Centroids:", centroids)
输出：
Cluster labels: [0 0 0 1 1 1]
Centroids: [[ 2. 2.33333333]
[13.66666667 31.66666667]]
以下是 K-means 的核心逻辑手动实现：
import numpy as np
def initialize_centroids(X, k):
indices = np.random.choice(len(X), k, replace=False)
return X[indices]
def closest_centroid(X, centroids):
distances = np.linalg.norm(X[:, np.newaxis] - centroids, axis=2)
return np.argmin(distances, axis=1)
def update_centroids(X, labels, k):
return np.array([X[labels == i].mean(axis=0) for i in range(k)])
def kmeans(X, k, max_iters=100, tol=1e-4):
centroids = initialize_centroids(X, k)
for i in range(max_iters):
labels = closest_centroid(X, centroids)
new_centroids = update_centroids(X, labels, k)
if np.all(np.abs(new_centroids - centroids) < tol):
break
centroids = new_centroids
return labels, centroids
# 示例数据
X = np.array([[1, 2], [2, 2], [3, 3], [8, 7], [8, 8], [25, 80]])
# 运行 K-means
labels, centroids = kmeans(X, k=2)
print("最终簇:", labels)
print("质心位置:", centroids)
K-means 的收敛性受到初始簇中心选择的影响。K-means++ 是一种改进的初始化方法，可以帮助选择更合理的初始中心，优先选择'距离最远'的点作为初始质心，减少陷入局部最优的风险。
K-means 是一种简单、快速的聚类算法，广泛应用于数据聚类任务。通过反复优化簇中心位置，K-means 不断收敛并找到数据的聚类结构。然而，它对初始条件敏感，对簇形状有限制，适合于球形且均匀分布的簇。在实际应用中，可通过结合 K-means++、肘部法和轮廓系数等手段改进其效果。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
生成新的随机RSA私钥和公钥pem证书。 在线工具，RSA密钥对生成器在线工具，online
基于 Mermaid.js 实时预览流程图、时序图等图表，支持源码编辑与即时渲染。 在线工具，Mermaid 预览与可视化编辑在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online