这一节讲述最简单也很常用的一种聚类算法——k-平均算法。该算法的流程非常简单，其实就是不停地尝试对集合进行划分，直至找到符合条件的划分方式。可以简单描述如下。

第一步，确定簇的个数k，并为每个簇的中心（称为中心向量）初始化k个种子c1，c2，…，ck。

第二步，将每个元素分配给距离其最近的中心向量，生成k个簇。

第三步，重新计算每个簇的中心，并以计算结果作为每个簇新的中心向量。

第四步，重复上述第二、三步，直至算法收敛（中心不再变化或满足特定的收敛条件）。

其中在第一步，初始化种子有多种方法，一种简单的处理方法是随机地挑选k个元素作为初始化种子。在第四步，如果进一步迭代后，每个簇的中心不再发生变化，自然可以认为算法收敛，但这并不总是可以实现的。另一种判断收敛的方法是使用簇中所有元素与中心的均方差，当均方差小于给定的阈值后即停止迭代。均方差是指簇中每个元素与中心距离的平方和，即

为了更好地理解k-均值聚类的过程，下面通过一个简单的例子进行说明。给定10个平面上的点，通过k-平均算法聚成两类。这10个点的坐标分别是（3，4），（3，6），（3，8），（4，5），（4，7），（5，1），（5，5），（7，3），（7，5），（8，5），在平面上如图5-2所示。

图5-2

因为确定是聚成两类，所以要选取两个点作为初始化的聚类中心。不妨选p1=（3，4）和p2=（7，5），即图中红色的两个点。k-平均算法的第一步就完成了。

接下来进行第二步，计算每个点到初始化种子的距离，并把它归入距离最近的中心所属的簇。计算结果如表5-1所示。

表5-1

第一次迭代完成后的聚类结果如图5-3所示。

图5-3

接下来重复第二、三步开始第二次迭代。各点到中心的距离如表5-2所示，第二次聚类的结果如图5-4所示。

表5-2

图5-4

通过上面的例子可以看到，k-平均算法简单快速，也能取得较好的聚类效果。但这种方法也有一些缺点。

首先，必须事先给定要生成的簇的数量，而且对不同的初始化种子，可能会导致不同的聚类结果。为了减少初始化种子带来的干扰，可以尝试选取不同的初始化种子进行多次聚类，从中挑选最优结果作为最终的聚类结果。其次，这种聚类方法对孤立点是敏感的。所谓孤立点就是和其他任何点都没有太高的相似性的元素。这样的点会极大地干扰聚类的结果。为了解决孤立点带来的问题，可以尝试其他基于k-平均改进的算法，如k-prototype算法和k-中心点算法。