前言
在机器学习的各类算法中，分为两类：监督学习算法以及无监督学习算法，一个月前写的ID3决策树算法就是典型的监督学习算法。两者的区别就在于给定的样本是否已经明确具有类别。
今天，在这篇文章里，要给自己备忘一下聚类算法里面，简单但是却应用广泛的算法：k均值聚类算法。
K-means
首先，我们需要来明确一下分类与聚类两者的概念。
- 分类
在我看来，所谓分类，是根据给定类别的特征，把样本分到最为符合的类别里面，如垃圾分类，就是典型的分类，根据每种垃圾的特征，分为可回收、不可回收、厨余垃圾等等。这一概念里面隐含着一个特定前提，那就是类别已经事先给定了，从机器学习的角度来说，即是给出的训练样本里面包含的明确的类别。也就是说，倘若要让计算机学习分类垃圾，那么训练样本要包括每种垃圾的特征以及该垃圾具体属于哪一类。
- 聚类 而聚类，则是给定的样本没有事先确定类别，根据自己需要，确定类别数量，再把样本归到不同的类别里面。也就是说，同样是垃圾分类的例子，你给一堆垃圾，我可以根据可回收、不可回收分为聚类为两堆；也可以根据可回收、不可回收、厨余垃圾聚类为三堆。而其中聚类为同一堆的条件，我们可以理解为垃圾间的相似程度。
可以看到，从机器学习的角度来讲，分类是明显的监督学习的例子，聚类则是无监督学习的例子。
实现
那给我们一堆数据，如何实现聚类呢？ 我们刚刚说到，判断是否聚为同一类的条件是样本间的相似性，那么，我们肯定需要该类别的标准。就拿代码来讲。
代码实现步骤如下：
- 初始化一定数量的二维坐标点（x，y），点数量可自定义，所有坐标点的初始类别都为0
- 然后根据自定义的类别数，比如说我需要把数据聚类成三类，则从上述坐标点中，随机取三个点。作为类别的中心点
- 迭代所有坐标点，分别与三个中心点计算平方距离（就是Δx^2+Δy^2）,这一平方距离可以认为是与标准类别样本的差异度，取平方距离最小的类别作为该坐标点的类别
- 根据步骤三，可以得到每种分类的样本，然后，再从每种分类的样本中，重新计算该分类的类别中心。具体来说，比较简单的一种做法就是该类别所有样本的x与y，分别求和，然后除与该类别的样本数
- 迭代步骤3、4,直到每个类别的中心点不变或变化很小为止。
通常，把聚类中的类别叫做簇。
另外平方距离也只是计算差异度的一种比较方便的方法。重新计算类别中心，亦即簇中心的方法也有很多，文中也仅仅是提及一种实现比较方便的方式更详细的计算差异度的方法可以参考这篇文章：
更详细的计算类别中心的方法可以参考这篇文章：
代码的具体结果以用图像表示就是这样：
可以看到坐标点被聚类成四类
下面是具体的代码：
#include#include #include #include #include #define max 100000000;typedef struct{ double x; double y; int centroid;//坐标点的类别} Position;//随机生成二维数据点//len：坐标点个数//range：坐标点取值范围Position *randomPosition(int len, int range){ srand((unsigned)time(NULL)); Position *allPos = malloc(len * sizeof(Position)); int tempX; int tempY; for (int i = 0; i < len; ++i) { allPos[i].x = (double)rand() / 2147483647 * range; allPos[i].y = (double)rand() / 2147483647 * range; allPos[i].centroid = 0; } return allPos;}//centroidNum：类别（簇）数量//len：坐标点数量void kMeans(Position *allPos, int centroidNum, int len){ //随机生成簇中心点 Position *centroidPos = malloc(centroidNum * sizeof(Position)); for (int i = 0; i < centroidNum; ++i) { centroidPos[i] = allPos[rand() % len]; } for (int t = 0; t < 500; ++t) { double sum = 0; //对每个数据点进行分类 for (int i = 0; i < len; ++i) { int dis = max; int newDis; for (int x = 0; x < centroidNum; ++x) { //遍历所有簇中心取最近的簇 newDis = pow((allPos[i].x - centroidPos[x].x), 2) + pow((allPos[i].y - centroidPos[x].y), 2); if (newDis < dis) { dis = newDis; allPos[i].centroid = x; } } } //重新计算簇中心 //每个簇的计数器 int *clusterS_num = malloc(centroidNum * sizeof(int)); double *clusterS_sumX = malloc(centroidNum * sizeof(double)); double *clusterS_sumY = malloc(centroidNum * sizeof(double)); for (int i = 0; i < centroidNum; ++i) { //初始化计数器 clusterS_num[i] = clusterS_sumX[i] = clusterS_sumY[i] = 0; } for (int i = 0; i < len; i++) { clusterS_num[allPos[i].centroid]++; clusterS_sumX[allPos[i].centroid] += allPos[i].x; clusterS_sumY[allPos[i].centroid] += allPos[i].y; } //重新计算簇中心 for (int i = 0; i < centroidNum; ++i) { centroidPos[i].x = clusterS_sumX[i] / clusterS_num[i]; centroidPos[i].y = clusterS_sumY[i] / clusterS_num[i]; } for (int i = 0; i < len; ++i) { sum = sum + pow((allPos[i].x - centroidPos[allPos[i].centroid].x), 2) + pow((allPos[i].y - centroidPos[allPos[i].centroid].y), 2); } free(clusterS_num); free(clusterS_sumX); free(clusterS_sumY); }}int main(){ Position *allPos = randomPosition(500, 1000); kMeans(allPos, 4, 500);}