這一節講述最簡單也很常用的一種聚類算法——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所示。