这一节讲述最简单也很常用的一种聚类算法——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所示。