品经理3分钟都懂k-means聚类算法（附C++实现源码）

k-means：一种聚类算法，将样本集data[N]分成K个类（要把N个杂乱无章的样本聚合成K个不同的类别，所以是聚类算法嘛）。经过k-means聚类后，各类别内部的样本会尽可能的紧凑，而各类别之间的样本会尽可能的分开。

k-means思想：将距离最近的样本认为属于同一个类，每一个类有一个“质心”样本。举例，漫天繁星，距离较近的抱团星星，我们认为它们属于一个星团，而每个星团有一颗“质心”恒星作为这个星团的代表。

k-means计算过程：
1）初始化
1.1）初始化值：输入K值，输入data[N]全集
1.2）初始化质心：从data[N]全集中随机的选取K个样本，作为K个类的质心
1.3）初始化分类：对于随机选取的初始化质心，初始化每个样本的分类，将样本归入离它最近的那个质心那一类（可以认为是第0次迭代）
2）迭代运算
2.1）质心变换：对于同一个类的样本集合，重新计算质心
2.2）分类变换：对于变换后的质心，所有样本重新计算分类，计算依据仍是“将样本归入离它最近的那个质心那一类”
2.3）反复的进行迭代运算，直至2.1）质心变换与2.2）分类变换都不再变化为止，理论可以证明，k-means聚类算法一定是收敛的
3）输出结果

k-means关键点：
1）距离：两个样本之间的距离如何定义，是和业务场景紧密相关的。如果样本是二维平面上的点，两个点之间的距离可以定义为二维欧式距离（Euclidean distance），如果样本是天空中的繁星，两颗繁星之间的举例可以定义为三维欧式距离。
2）质心变换：定义了距离之后，初始化分类时，会把样本聚为最近质心那一类。初始化分类后，如何进行质心变换呢？一般使用距离方差法：将同一类中的所有样本都尝试着作为“假定质心”，计算此时该类中所有样本与“假定质心”距离的方差，将方差最小的“假定质心”设为该类的新质心。

工程实现：
工程上对k-means实现，要尽量做到算法步骤与业务场景的解耦：
1）k-means的计算过程是与业务无关的
2）样本，以及样本之间距离的计算是与业务有关的
上述解耦可以利用模版技术来实现，具体代码点“阅读原文”，欢迎下载。