原文写于个人博客，欢迎关注www.xiaolewei.com

简介

聚类分析最简单的方法即，将所处理的对象按照相异性划分为多个互斥的簇。对于含有n个数据的数据集D，以及簇数k，本文所讲的划分算法将基于距离函数，将对象组划分成k个分区，每个分区代表一个簇，并尽量使簇中对象相似，不同簇中对象相异。

基本概念

令数据集D包含n个欧氏空间中的对象，令ci为簇Ci的形心，即为该簇的代表，定义dist(p,ci)为对象p与该簇的代表ci的度量，其中dist(x,y)表示x与y的欧式距离。使用簇内变差来衡量Ci的质量，它是Ci中所有对象和形心直接的误差的平方和：

定义E为数据集中所有对象的误差平方和：

算法原理

为了得到k个簇，k-均值算法首先在D中随机的选取k个对象，作为k个簇的中心。对于剩下的每个对象，根据其与各个簇中心的欧式距离，将其分配到最近的一个簇中。待所有对象分配完成后，对于每个簇，计算其新的形心，并将其作为该簇的代表，重复分配每个对象，重复上述步骤，直到不再发生变化。

实例详解

选取二维的欧式空间，令D：

A1(2,10), A2(2,5), A3(8,4), B1(5,8), B2(7,5), B3(6,4), C1(1,2), C2(4,9)

距离函数为欧式距离。假设初始时选择A1,B1,C2作为每个簇的中心（该步为随机选取），进行第一轮迭代（为方便比较，未开根号）：

dist(A1,A2) = √25
dist(A1,A3) = √37
dist(A1,B2) = √50
dist(A1,B3) = √52
dist(A1,C2) = √5

dist(B1,A2) = √18
dist(B1,A3) = √25
dist(B1,B2) = √13
dist(B1,B3) = √17
dist(B1,C2) = √34

dist(C1,A2) = √10
dist(C1,A3) = √53
dist(C1,B2) = √45
dist(C1,B3) = √29
dist(C1,C2) = √58

所以可以得到如下簇：

{A1,C2}
{B1,A3,B2,B3}
{C1,A2}

重新计算各个簇的形心：
A'(3，9.5)、B'(6.5,5.25)、C'(1.5,3.5)

重复上述步骤重新分配D中所有对象，直到形心不再变化。

算法不足

该算法时间复杂度为O(nkt)，但是k-均值是无法保证结果收敛于全局最优解，且常常终止于一个局部最优解，其常常依赖于初始值的选取，更通常的做法是选取不同的初始值，多次运行该算法。

另外该算法对利群点是敏感的，当离群点被分配到某一簇时，会严重扭曲簇的平均值