c语言生成100个点 然后k均值分类,K-means基础入门（c语言）

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

2 #include

3 #include

4 #include

5 #include

6

7 #define N 11

8 #define K 2

9

10 typedef struct

11 {12 floatx;13 floaty;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 floatd;37 d = sqrt((point1.x - point2.x) * (point1.x - point2.x) + (point1.y - point2.y) * (point1.y -point2.y));38 returnd;39 }40

41 //计算每个簇的中心点

42 void getMean(intcenter[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 其新的中心质点是 : ( %f, %f )", i+1, mean[i].x, mean[i].y);67 }68 }69

70 //计算平方误差函数

71 floatgetE()72 {73 inti, 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 returnsum;87 }88

89 ///把N个点聚类

90 voidcluster()91 {92 inti, j, q;93 floatmin;94 floatdistance[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]

109 }110 }111 printf("( %.0f, %.0f ) 该点所属的类别为——%d", point[i].x, point[i].y, center[i] + 1);112 }113 printf("-----------------------------");114 }115

116 intmain()117 {118 int i, j, count = 0;119 floattemp1;120 floattemp2, t;121 printf("----------待分类的阵点----------");122 for(i = 0; i < N; ++i)123 {124 printf("( %.0f, %.0f )", point[i].x, point[i].y);125 }126 printf("-----------------------------");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", temp1);144

145 getMean(center); //计算每个簇的新的中心点

146

147 cluster(); //第二次根据预设的k个点进行聚类

148

149 temp2 = getE(); //根据簇形成新的中心点，并计算出平方误差

150 count++; //计算形成最终的簇用了多少次

151 printf("第2次平方误差为: %f", 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", count, temp2);161 }162

163 printf("总共的迭代次数为: %d", 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