K-means基础入门（c语言）

2024-03-21 20:26:58

　　K-means聚类算法是一种实现起来相对简单，应用广泛的迭代求解的聚类分析算法。其步骤是随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。（以上来自百度百科）

　　简单来说，假设有一堆点杂糅在一起，想要将其中的不同类型的点区分开来归类，就可以使用K-means算法来简单实现。

　　图a中有一堆随机的杂糅在一起的点阵，图b中我们随机选择了两个质心（即画叉叉的位置），然后在图c中分别求点阵中所有点到这两个叉叉的距离，记录下每个点距离哪个叉叉最近，对应的叉叉是什么颜色（即将这个点进行初步的归类），每个点与红色叉叉和蓝色叉叉的距离计算出来后，得到了所有样本点的第一轮迭代后的类别。此时我们对当前标记为红色和蓝色的点分别求其新的质心（叉叉），如图d所示，新的红色叉叉和蓝色叉叉的位置已经发生了变动。持续多次重复前面我们对每个点计算距离的过程（即将所有点的类别标记为距离最近的质心的类别并求新的质心）。最后，我们就能得到两种不同类别的点阵。

K-Means算法流程

算法步骤：

1.（随机）选择K个聚类的初始中心；

2.对任意一个样本点，求其到K个聚类中心的距离，将样本点归类到距离最小的中心的聚类，如此迭代n次；

3.每次迭代过程中，利用均值等方法更新各个聚类的中心点(质心)；

4.对K个聚类中心，利用2,3步迭代更新后，如果位置点变化很小(可以设置阈值)，则认为达到稳定状态，迭代结束，对不同的聚类块和聚类中心可选择不同的颜色标注。

样本与质点距离的计算公式（欧氏距离）

二维空间的公式

其中，为点与点之间的欧氏距离；为点 (x2,y2)到原点的欧氏距离。

三维空间的公式

n维空间的公式

代码段

假定这些点阵是待区分的样本点：

设置两个中心点方便进行分类

这里是手动设置的中心点，如果使用随机进行生成中心点，中心点的生成会出现乱码

通过计算每个阵点与中心点的最短距离进而实现归类

这里计算平方误差进而比较决定是否继续迭代的原因我不是很明白，希望有懂得大佬能在评论区教一下我(,,・ω・,,)。

完整代码

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <math.h>
  5 #include <time.h>
  6  
  7 #define N 11
  8 #define K 2 
  9  
 10 typedef struct
 11 {
 12     float x;
 13     float y;
 14 }Point;
 15  
 16 int center[N];  //  判断每个点属于哪个簇
 17  
 18 Point point[N] = {
 19     {2.0, 10.0},
 20     {2.0, 5.0},
 21     {8.0, 4.0},
 22     {5.0, 8.0},
 23     {7.0, 5.0},
 24     {6.0, 4.0},
 25     {1.0, 2.0},
 26     {4.0, 9.0},
 27     {7.0, 3.0},
 28     {1.0, 3.0},
 29     {3.0, 9.0}
 30 };
 31  
 32 Point mean[K];  // 保存每个簇的中心点
 33  
 34 float getDistance(Point point1, Point point2)   //计算样本点与质点的距离 
 35 {
 36     float d;
 37     d = sqrt((point1.x - point2.x) * (point1.x - point2.x) + (point1.y - point2.y) * (point1.y - point2.y));
 38     return d;
 39 }
 40  
 41 // 计算每个簇的中心点
 42 void getMean(int center[N])
 43 {
 44     Point tep;
 45     int i, j, count = 0;
 46     for(i = 0; i < K; ++i)
 47     {
 48         count = 0;
 49         tep.x = 0.0;   // 每算出一个簇的中心点值后清0
 50         tep.y = 0.0;
 51         for(j = 0; j < N; ++j)
 52         {
 53             if(i == center[j])
 54             {
 55                 count++;
 56                 tep.x += point[j].x;
 57                 tep.y += point[j].y;       //将同一类别的样本点归类到一起 
 58             }
 59         }
 60         tep.x /= count;
 61         tep.y /= count;
 62         mean[i] = tep;  //保存每个簇的中心点 
 63     }
 64     for(i = 0; i < K; ++i)
 65     {
 66         printf("对于类别 %d 其新的中心质点是 : \t( %f, %f )\n", i+1, mean[i].x, mean[i].y);
 67     }
 68 }
 69  
 70 // 计算平方误差函数
 71 float getE()
 72 {
 73     int i, j;
 74     float cnt = 0.0, sum = 0.0;
 75     for(i = 0; i < K; ++i)
 76     {
 77         for(j = 0; j < N; ++j)
 78         {
 79             if(i == center[j])
 80             {
 81                 cnt = (point[j].x - mean[i].x) * (point[j].x - mean[i].x) + (point[j].y - mean[i].y) * (point[j].y - mean[i].y);
 82                 sum += cnt;
 83             }
 84         }
 85     }
 86     return sum;
 87 }
 88  
 89 /// 把N个点聚类
 90 void cluster()
 91 {
 92     int i, j, q;
 93     float min;
 94     float distance[N][K];
 95     for(i = 0; i < N; ++i)
 96     {
 97         min = 999999.0;
 98         for(j = 0; j < K; ++j)
 99         {
100             distance[i][j] = getDistance(point[i], mean[j]);    //调用计算样本点与质点的距离的函数 
101  
102         }
103         for(q = 0; q < K; ++q)
104         {
105             if(distance[i][q] < min)
106             {
107                 min = distance[i][q];
108                 center[i] = q;      //将最小距离所属的质点赋值给对应的样本点 
109             }
110         }
111         printf("( %.0f, %.0f )\t 该点所属的类别为——%d\n", point[i].x, point[i].y, center[i] + 1);
112     }
113     printf("-----------------------------\n");
114 }
115  
116 int main()
117 {
118     int i, j, count = 0;
119     float temp1;
120     float temp2, t;
121     printf("----------待分类的阵点----------\n");
122     for(i = 0; i < N; ++i)
123     {
124         printf("\t( %.0f, %.0f )\n", point[i].x, point[i].y);
125     }
126     printf("-----------------------------\n");
127  
128 
129 
130     mean[0].x = point[1].x;      // 初始化k个中心点（这里我们做两个中心点即红色和蓝色2两种类别） 
131     mean[0].y = point[2].y;
132  
133     mean[1].x = point[4].x;
134     mean[1].y = point[5].y;
135   
136 
137 
138  
139     cluster();          // 第一次根据预设的k个点进行聚类
140     
141     temp1 = getE();        //  第一次平方误差
142     count++;                   //  计算形成最终的簇用了多少次
143     printf("第1次平方误差为: %f\n\n", temp1);
144  
145     getMean(center);   //计算每个簇的新的中心点 
146     
147     cluster();            // 第二次根据预设的k个点进行聚类
148     
149     temp2 = getE();        //  根据簇形成新的中心点，并计算出平方误差
150     count++;                //  计算形成最终的簇用了多少次
151     printf("第2次平方误差为: %f\n\n", temp2);
152  
153     while(fabs(temp2 - temp1) != 0)   //  比较两次平方误差 判断是否相等，不相等继续迭代
154     {
155         temp1 = temp2;
156         getMean(center);
157         cluster();
158         temp2 = getE();
159         count++;
160         printf("第%d次平方误差为: %f\n", count, temp2);
161     }
162  
163     printf("总共的迭代次数为: %d\n\n", count);  // 统计出迭代次数
164     system("pause");
165     return 0;
166 }

参考网址：

https://blog.csdn.net/weixin_42029738/article/details/81978038

https://blog.csdn.net/enter89/article/details/90349943

https://baike.baidu.com/item/K%E5%9D%87%E5%80%BC%E8%81%9A%E7%B1%BB%E7%AE%97%E6%B3%95/15779627?fromtitle=K-means&fromid=4934806&fr=aladdin

代码参考https://blog.csdn.net/triumph92/article/details/41128049?tdsourcetag=s_pcqq_aiomsg

码农公寓