K-Means方法是MacQueen1967年提出的。给定一个数据集合X和一个整数K（n），K-Means方法是将X分成K个聚类并使得在每个聚类中所有值与该聚类中心距离的总和最小。

K-Means聚类方法分为以下几步：

[1] 给K个cluster选择最初的中心点，称为K个Means。

[2] 计算每个对象和每个中心点之间的距离。

[3] 把每个对象分配给距它最近的中心点做属的cluster。

[4] 重新计算每个cluster的中心点。

[5] 重复2，3，4步，直到算法收敛。

以下几张图动态展示了这几个步骤：

 

 

 

 

 

 

 

 

 

 

 下面，我们以一个具体的例子来说明一下K-means算法的实现。

 

 

 

 

 

 

 

 

K-means算法的优缺点：

优点：

（1）对于处理大数据量具有可扩充性和高效率。算法的复杂度是O（tkn），其中n是对象的个数，k是cluster的个数，t是循环的次数，通常k，t<<n。

（2）可以实现局部最优化,如果要找全局最优，可以用退火算法或者遗传算法

缺点：

（1）Cluster的个数必须事先确定，在有些应用中，事先并不知道cluster的个数。

（2）K个中心点必须事先预定，而对于有些字符属性，很难确定中心点。

（3）不能处理噪音数据。

（4）不能处理有些分布的数据（例如凹形）

K-Means方法的变种

(1) K-Modes ：处理分类属性

(2) K-Prototypes：处理分类和数值属性

(3) K-Medoids

它们与K-Means方法的主要区别在于：

（1）最初的K个中心点的选择不同。

（2）距离的计算方式不同。

（3）计算cluster的中心点的策略不同。