2.2 k-均值示例
本节在一个真实的数据集上运用 k-均值算法进行聚类。这个数据集中有1000 封邮件，每封邮件被 d=57 个特征（维度）刻画，每个邮件属于三个给定类别中的一类。为了方便可视化显示， 我们对数据进行降维操作，把原来的高维数据降到 2 维[10][11] 。降维后的数据分布情况如图 2-1 所示，其中每个数据点代表二维特征平面上的一封邮件，不同颜色表示邮件的不同类别。
在开始的时候，每个数据点的类别都是未知的。 k-均值算法的第一步是初始化簇代表，如图 2-2 所示，我们从数据中随机选出 3 个点作为初始的簇代表点（后称簇中心）。在后续的图中，每个簇中心用红色点表示，每种颜色代表一个簇，所有被分配到该簇中的点都是用同一种颜色表示。在图 2-2 中，由于所有数据点都还没有被分配簇中心标记，故所有数据暂时使用黑色表示。
接下来，每个数据点分配到距其最近的簇中心，并将在同一个簇的数据标记上相同的颜色，如图 2-3 所示。然后，用当前所有被分配到该簇数据点的均值来作为新的簇中心，更新后簇中心的位置如图 2-4 所示。
由于随机初始化的簇中心往往具有较大的随机性，故在第一次迭代时，簇中心会出现较大幅度的移动。 图 为了强化表示， 2-5 中把移动的轨迹用红色的箭头标识。
图 2-1 降维后待聚类数据的分布情况
图 2-2 随机初始化簇中心
图 2-3 初始化的聚类结果
图 2-4 第 1 次迭代后的结果
图 2-5 第 1 次迭代中簇中心的移动轨迹
下面是 k-均值算法的第二步。k-均值算法反复将每个数据点分配到离其最近的簇中心，同时根据每次的分配结果更新所有簇中心的位置。图 2-6～图 2-14 展示了第 2～10 次迭代后的结果。
图 2-6 第 2 次迭代后的结果
图 2-7 第 3 次迭代后的结果
图 2-8 第 4 次迭代后的结果
图 2-9 第 5 次迭代后的结果
图 2-10 第 6 次迭代后的结果
图 2-11 第 7 次迭代后的结果
图 2-12 第 8 次迭代后的结果
图 2-13 第 9 次迭代后的结果
图 2-14 第 10 次迭代后的结果
如此反复，直至聚类结果不再变化，或者其变化量在可以容忍的范围内，则停止整个迭代过程。事实上，经过 11 次迭代，算法收敛，聚类结果不再变化。我们得到的最终聚类结果如图 2-15 所示。
图 2-15 算法给出的最终聚类结果
对比图 2-1 和图 2-15 可以看出，k-均值算法给出的聚类结果与实际的数据类别分布吻合得非常好。