K-means 是一种常用的基于距离的聚类算法，核心目标是将数据集划分为 K 个簇，使得每个数据点属于距离最近的簇中心。通过反复迭代调整质心位置，算法不断优化簇内的紧密度，最终获得紧凑且彼此分离的簇。
1. 核心思想与工作流程
简单来说，K-means 就是'物以类聚'。它的流程可以概括为两个主要动作：分配和更新。
- 初始化：随机选择 K 个点作为初始质心（Centroids）。
- 分配：计算每个数据点到所有质心的距离，将其归入最近的那个簇。
- 更新：重新计算每个簇内所有点的均值，作为新的质心。
- 收敛：重复上述步骤，直到质心不再变化或达到最大迭代次数。
这个过程就像是在不断调整几个'磁铁'的位置，把周围的铁屑吸到离自己最近的地方，然后磁铁根据铁屑分布再移动一下，直到稳定下来。
算法步骤详解
假设我们要将二维数据点分为 K=2 个簇。首先随机选定两个点作为初始质心，比如 C1=(1,2) 和 C2=(8,8)。接下来计算每个点到这两个中心的欧氏距离：
$$d = \sqrt{\sum_{j=1}^{n}(x_j - \mu_j)^2}$$
| 数据点 | 到 C1 距离 | 到 C2 距离 | 归属 |
|---|---|---|---|
| 点 1 | 0 | 8.49 | 簇 1 |
| 点 2 | 1.41 | 8.06 | 簇 1 |
| 点 3 | 4.24 | 5.0 | 簇 1 |
| 点 4 | 5.0 | 4.24 | 簇 2 |
| 点 5 | 8.49 | 0 | 簇 2 |
分配完成后，我们计算新质心。例如簇 1 的新质心是其中所有点的平均值。接着用新质心再次计算距离，重复此过程，直到质心坐标基本稳定。
2. 数学基础与复杂度
K-means 的目标函数是最小化簇内平方误差和（WCSS）：
$$J = \sum_{i=1}^{K} \sum_{x \in C_i} ||x - \mu_i||^2$$
其中 $\mu_i$ 是第 i 个簇的质心，$C_i$ 是该簇的点集。这个公式本质上就是在追求簇内点越聚集越好。
关于性能，如果数据量是 n，簇数是 K，迭代次数是 T，那么总时间复杂度大约是 $O(n \cdot K \cdot T)$。对于大规模数据，这通常是可以接受的，但要注意每次迭代都要遍历所有点。
3. 优缺点分析
在实际项目中，我们需要权衡它的利弊：
- 优点：简单高效，适合处理大数据集；收敛速度通常较快。
- 缺点：对初始值敏感，容易陷入局部最优；假设簇是凸形（球形），对非凸形状（如月牙形）效果差；对噪声和离群点比较敏感。
4. K 值的选择
确定最佳的 K 值是个难点。常用的方法有：
- 肘部法（Elbow Method）：绘制不同 K 值下的 WCSS 曲线，寻找下降幅度明显变缓的拐点。
- 轮廓系数（Silhouette Coefficient）：衡量聚类结果的紧密度和分离度，值越高越好。
实际应用中，往往结合业务场景和经验来定，单纯依赖算法指标有时不够准确。
5. Python 实现
我们可以使用 scikit-learn 快速上手，也可以手动实现逻辑以便深入理解。
5.1 使用 scikit-learn
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(n_clusters=2, random_state=0).fit(X)
# 获取结果
labels = kmeans.labels_
centroids = kmeans.cluster_centers_
print("Cluster labels:", labels)
print("Centroids:", centroids)
输出结果会显示每个点属于哪个簇，以及最终的质心坐标。
5.2 手动实现核心逻辑
为了看清底层机制，这里提供一个简化的手动实现版本：
import numpy as np
def initialize_centroids(X, k):
# 随机选择 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 _ 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]])
labels, centroids = kmeans(X, k=2)
print("最终簇:", labels)
print("质心位置:", centroids)
这段代码展示了算法的核心循环：分配标签 -> 更新质心 -> 检查收敛。实际工程中建议优先使用库函数，但在调试或学习时，手写一遍很有帮助。
6. 改进方案：K-means++
标准 K-means 最大的痛点是随机初始化可能导致结果不稳定。K-means++ 改进了这一点，它在选择初始质心时，倾向于选择距离已选质心较远的点。这样能确保初始中心分布更均匀，减少陷入局部最优的风险，通常也能加快收敛速度。
具体做法是：先随机选一个点，后续每个新点的选择概率与该点到已选点的最小距离平方成正比。虽然实现稍微复杂一点，但效果提升明显。
7. 总结
K-means 是机器学习入门必学的算法之一。它结构简单、效率高，非常适合处理数值型数据的初步探索。虽然它对初始值和簇形状有限制，但配合 K-means++ 和合理的 K 值选择策略，依然能在很多场景中发挥重要作用。在实际落地时，记得关注数据预处理和异常值清洗，这往往比调参更关键。
