K-Means聚类工具

伪代码

两个步骤交替进行，直到不再发生任何变化：把每个点分配给最近的质心，然后把每个质心移动到分配给它的那些点的平均位置。

K均值(点集, k):
    初始化 k 个质心（随机，或用 k-means++）

    重复直到分配不再改变:
        // 分配步骤
        对每个点 p:
            簇[p] = 使 距离(p, c) 最小的那个 c

        // 更新步骤
        对每个质心 c:
            c = 所有满足 簇[p] == c 的点的均值

    返回 簇划分与质心

每一步都会让簇内平方和下降或保持不变，而可能的分配方案只有有限多种，因此算法总会终止。它不保证的是终止在全局最优：它收敛到的是一个局部极小，而那完全取决于初始化，这也正是实践中必须加以处理的局限。

分步示例演算

把四个点聚成两簇，并刻意从一个糟糕的初始化出发，让两个质心都落在同一个真实簇里。

示例图: 点位于 (1,1)、(2,1)、(8,8) 和 (9,8)。初始质心被放在 (1,1) 与 (2,1)，也就是都落在左下那一簇中。

1. 第 1 轮，分配. 点 (1,1) 归到第一个质心。其余三个点 (2,1)、(8,8) 和 (9,8) 都离第二个质心更近。这个划分明显很糟：一个簇只有一个点，另一个簇有三个。
2. 第 1 轮，更新. 第一个质心留在 (1,1)。第二个移动到 (2,1)、(8,8) 和 (9,8) 的均值处，即 (6.33, 5.67)。此时簇内平方和为 61.333。
3. 第 2 轮，分配. 由于第二个质心已经上移到右上方，点 (2,1) 现在离第一个质心更近。划分变为 (1,1) 与 (2,1) 一组、(8,8) 与 (9,8) 一组，也就是正确的划分。
4. 第 2 轮，更新. 两个质心移动到 (1.5, 1) 与 (8.5, 8)。簇内平方和从 61.333 降到 1.0。
5. 第 3 轮，收敛. 分配不再变化，质心也不再移动。算法停止。

两轮之内即告收敛，簇内平方和从 61.333 降到 1.0。请注意算法从一个刻意设计的糟糕初始化中恢复了过来，当时两个质心都落在同一个真实簇内。这一点并没有保证：换一批数据，这样的初始化就可能把你困在某个局部极小里。这正是 k-means++ 要把初始质心选得彼此远离的原因，也是值得用不同初始化多跑几次的原因。

复杂度及其来源

时间: O(n · k · i · d) · 空间: O(n + k·d)

每一轮都要把 n 个点与 k 个质心在 d 维空间中逐一比较，即 O(n 乘以 k 乘以 d)，而更新步骤再把这些点扫一遍，代价相同。若迭代 i 轮，总计为 O(n 乘以 k 乘以 i 乘以 d)。实践中 i 通常很小，数十量级，尽管最坏情况下它可以超多项式地增长。空间是每个点一个簇标号再加上 k 个质心。按平方和意义求最优聚类即便在 k 等于 2 时也是 NP 困难的，因此被普遍使用的 Lloyd 算法只是一个启发式：实践中又快又好，但没有最优性保证。

何时使用K-Means 物流聚类，何时不宜

根据你预期簇的形状，以及是否事先知道 k 来选择。

常见陷阱

• 不用 k-means++ 而随机初始化. 糟糕的初始化可能收敛到明显更差的局部极小。k-means++ 以与已选中心距离平方成正比的概率来挑选初始中心，从而把它们拉开，只需极小的额外代价就能大幅改善期望结果。
• 不对特征做归一化. K-均值使用欧氏距离，因此以千为单位的特征会盖过取值在 0 到 1 之间的特征。若各特征量纲不同，请在聚类前先归一化，否则簇只会反映量程最大的那个特征。
• 只看平方和来挑选 k. 簇内平方和会随 k 增大而单调下降，直到 k 等于点数时降为零。请使用肘部法、轮廓系数或 gap 统计量，而不是取绝对最小值。
• 把它用在非球形的簇上. K-均值把空间划分成 Voronoi 单元，因此只能产生凸的边界。面对新月形或彼此嵌套的簇，它在构造上就注定失败，跑多少次都一样。此时的替代方案是 DBSCAN 或谱聚类。
• 只跑一次. 由于结果依赖初始化，只跑一次并不能说明你是否落进了某个局部极小。请用不同随机种子多跑几次，并保留簇内平方和最小的那一次。

常见问题

什么是 K-均值聚类？

K-均值通过交替执行两个步骤把一组点划分成 k 个簇：把每个点分配给最近的质心，然后把每个质心移动到其所属点的均值处。如此反复直到分配不再变化，从而最小化每个簇内部的距离平方和。

K-均值的时间复杂度是多少？

O(n 乘以 k 乘以 i 乘以 d)，其中 n 是点数、k 是簇数、i 是迭代次数、d 是维数。实践中 i 通常是数十量级。按平方和意义求最优聚类即便在 k 等于 2 时也是 NP 困难的，因此标准算法只是启发式，并无最优性保证。

K-均值一定会收敛吗？

一定会终止，因为每一步都会让簇内平方和下降或保持不变，而可能的分配方案只有有限多种。但它收敛到的是局部极小而未必是全局最优，而具体落到哪一个完全取决于初始化。

为什么 K-均值的初始化很重要？

因为该算法只能从起点出发做局部改进。初始中心放得不好，可能让它卡在一个明显劣于最优的划分上。k-means++ 通过挑选彼此远离的初始中心来缓解这一点，而用不同随机种子多跑几次并保留最好的结果则是通行做法。

如何选择 k 的取值？

没有唯一的答案。肘部法把平方和对 k 作图，寻找改善开始变平缓的那个位置。轮廓系数衡量各簇分离得有多好。gap 统计量则与随机参照数据作比较。很多时候，领域知识的分量胜过这三者。