K-means算法的起源

　　1967年，James MacQueen在他的论文《用于多变量观测分类和分析的一些方法》中首次提出 “K-means”这一术语。1957年，贝尔实验室也将标准算法用于脉冲编码调制技术。1965年，E.W. Forgy发表了本质上相同的算法——Lloyd-Forgy算法，所以这一算法有时也被称为Lloyd-Forgy算法。更高效的版本则被Hartigan and Wong提出。

K-means算法的原理

　　K-Means聚类算法是聚类算法之一，其中K表示类别的数量，也就是说，我们想要将数据分成几个类别，Means表示均值。K值决定了初始质心（通常是随机选择的中心）的数量。K值是几，必须有几个质心。 简而言之，K-Means聚类算法是一种通过均值聚类数据点的算法。

K-means算法的过程

1、首先输入K的值，将数据集分为K个类别。

2、从这组数据中随机选择K个数据点作为初始大哥（初始质心），其它数据点都作为小弟。

3、对数据集中每一个小弟，计算与每一个大哥的距离，离哪个大哥距离最近，就分配给哪个大哥。

4、每一个大哥手下都聚集了一帮小弟，这时候召开黑帮会议，推选出新的大哥（新的质心）。

5、如果新大哥和老大哥之间的距离很小或为0，说明新任大哥靠谱，选举结束（可以认为我们进行的聚类已经达到期望的结果，算法终止）。

6、如果新大哥和老大哥之间的距离很大，需要重新选举新大哥，分配小弟（重复3~5的步骤）。

K-means算法的例子

【例】以下是一组用户的年龄数据，使用K-means算法划分数据。

   15，15，16，19，19，20，22，28，35，40

【步骤】

（1）我们将K值定为2，并随机选择16和22作为初始大哥。

（2）分别计算每一个小弟与初始大哥的距离，划分门派，距离相同的随机划分。

表1 第一次划分数据