4赞

C语言实现K-Means算法

作者：手机用户2402851335 | 2022-11-04 17:36

这篇文章主要为大家详细介绍了C语言实现K-Means算法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

一、聚类和聚类算法

聚类，就是将数据对象划分成若干个类，在同一个类中的对象具有较高的相似度，而不同的类相似度较小。聚类算法将数据集合进行划分，分成彼此相互联系的若干类，以此实现对数据的深入分析和数据价值挖掘的初步处理阶段。例如在现代商业领域，聚类分析算法可以从庞大的数据集合中对消费者的消费习惯、消费倾向，以方便决策者制订消费策略。总之，作为数据挖掘中的一个模块，聚类分析算法可以作为一个单独的工具已发现数据库中分布的一些深层信息，并概括出每一类的特点。聚类分析算法也可作为数据挖掘算法中其他分析算法的一个预处理步骤。

在数据挖掘领域，聚类分析算法可以分为一下几个大类，包括划分法、层次法、基于密度的方法、基于网络的方法和基于模型的方法。基于划分的基本思想就是通过迭代的方法将含有N个数据对象的数据集分成K个聚类。具体的步骤就是，用户先给出要划分的个数，然后通过一定的算法反复的进行迭代，使得每次得到的分组比前一次更加接近预期目标，是否优化的判定标准是同组数据之间不同数据之间的相似程度，同组数据相似程度越大，组间似程度越小越优化。

K-means聚类算法的核心思想就是基于对数据集合的划分，它把N个数据对象划分成K个类，使每个类中的数据点到该聚类中心的距离平方和最小。下面我将利用C语言来实现K-means算法，并对该算法在输入不同的聚类个数、改变数据点的密集程度以及初始聚类中心点的选择三个方面来测试该算法。

二、K-means算法实现步骤

通过对聚类和K-Means算法思想的了解，C语言算法的实现过程如下：

（1）通过文件输入N个数据点，并选取其中K（K

（2）对剩余的数据点分别计算到各个聚类聚点中心的欧氏距离，并将该点划分到最近的类中；

（3）重新计算各个聚类的聚点中心；

（4）与之前的聚类中心比较，如果聚类中心发生变化，转到（2），否则结束迭并输出结果。

三、K-means算法实现

（一）实现思路

通过以上对K-means算法的了解，该算法主要是通过迭代的思想来求解K个聚类的中心。由于传统数组需要先定义再使用，且在使用的过程中不能实现数组长度的动态增长。同时考虑到设计该算法时，没有涉及到在迭代过程中各个数据点的插入和删除，各个数据点具体划分到那个聚类中，是由结构体成员变量中的className来标识，因此选用了Vector来作为存储数据的容器，这样当从文件输入大量数据时，由程序自己开辟需要的存储空间。同时，也可通过Vector向量容器提供的size和迭代器方法，实现遍历并按照所在聚类进行输出。

每个数据点都含有X、Y坐标，算法初始状态时，指定聚类的具体个数K，初试状态的K个聚类中心由输入文件的前K个数据点来指定。算法在每一次迭代中，需要计算各个点到K个聚类中心坐标的欧氏距离，并选择距离最近的一个聚类，用该聚类的名称标识当前数据点。当所有数据点遍历完后，计算划分到每个聚类中所有数据点X与Y的均值，并将该均值与前一次聚类中心点的坐标相比较。当X与Y的误差小于或者等于1e-6时，则结束迭代并输出收敛后的K歌聚类的中心坐标。

（二）变量和函数说明

（1）定义结构体类型，用于存储数据点坐标、所在聚类、与聚类中心距离

typedef struct point

{

float x,y;    //数据点的坐标
string className; //所属的聚类
float distance;  //距离聚类中心的距离

}Point;

（2）变量声明

vector dataVector：存储从文件读取的数据

vector classPoints：存储聚类坐标

vector &totalPoints)：存储所有的数据点

（3）函数声明

字符串转换函数：将整型变量转换成字符串类型：

string converToString(int x);

读入数据函数：从文件读入坐标数据：

vector readDataFile(string fileName);

初始化数据集合函数：

void initDataset(int classNum,vector dataVector,vector &classPoints,vector &totalPoints);

计算各个数据点距离聚点中心的欧氏距离的函数：

string computerDistance(Point *p_totalPoints,vector &classPoints);

将各个点划分到相应类的函数：

void kMeansClustering(int classNum,vector totalPoints,vector classPoints);

（三）核心代码（部分）

（1）初始化数据集合函数：

void initDataset(int classNum,vectordataVector,vector&classPoints, 
         vector&totalPoints) 
{ 
  int i,j; 
  Point point; 
  for(i=0,j=1; i

（2）K-means函数：

void kMeansClustering(int classNum,vector totalPoints,vector classPoints) 
{ 
  float tempX=0;//计算聚类中所有数据点X的均值 
  float tempY=0;//计算聚类中所有数据点Y的均值 
  int count=0; //记录每一个类中数据点的数目 
  float errorX=INT_MAX; //假设初始时误差最大 
  float errorY=INT_MAX; 
  vector::iterator p_totalPoints; 
  vector::iterator p_classPoints; 
  Point temp; 
  int i; 
  while(errorX > 1e-6 && errorY > 1e-6) 
  { 
    for(p_totalPoints=totalPoints.begin(); p_totalPoints!=totalPoints.end(); p_totalPoints++) 
    { 
      //将所有的点就近分类 
      string className=computerDistance(p_totalPoints,classPoints); 
      (*p_totalPoints).className=className; 
    } 
    errorX=0; 
    errorY=0; 
    //按照均值重新划分聚类中心点 
    for(p_classPoints=classPoints.begin(); p_classPoints!=classPoints.end(); p_classPoints++) 
    { 
      count=0; 
      tempX=0; 
      tempY=0; 
      cout<<"Partition to cluster center "<className<<":"; 
      for(p_totalPoints=totalPoints.begin(); p_totalPoints!=totalPoints.end(); p_totalPoints++) 
      { 
        if((*p_totalPoints).className==(*p_classPoints).className) 
        { 
          cout<<" ("<<(*p_totalPoints).x<<","<<(*p_totalPoints).y<<") "; 
          count++; 
          tempX+=(*p_totalPoints).x; 
          tempY+=(*p_totalPoints).y; 
        } 
      } 
      cout<

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

推荐阅读

程序员
如何在Xcode中调试ios的金属内核？

如何解决《如何在Xcode中调试ios的金属内核？》经验，为你挑选了0个好方法。 ... [详细]
程序员
反应原生的TextInput焦点样式

如何解决《反应原生的TextInput焦点样式》经验，为你挑选了1个好方法。 ... [详细]
程序员
containsTheSameElementsAs如何在specs2中工作

如何解决《containsTheSameElementsAs如何在specs2中工作》经验，为你挑选了1个好方法。 ... [详细]
程序员
在Delphi 10 Seattle上接收iOS推送通知

如何解决《在Delphi10Seattle上接收iOS推送通知》经验，为你挑选了0个好方法。 ... [详细]
程序员
在空内使用修剪

如何解决《在空内使用修剪》经验，为你挑选了1个好方法。 ... [详细]
程序员
如何跳过Perl中while循环中的迭代步骤？

如何解决《如何跳过Perl中while循环中的迭代步骤？》经验，为你挑选了1个好方法。 ... [详细]
程序员
如何将其他参数传递给pyspark中用户定义的方法进行过滤方法？

如何解决《如何将其他参数传递给pyspark中用户定义的方法进行过滤方法？》经验，为你挑选了1个好方法。 ... [详细]
程序员
如何在SBT项目中列出活动插件？

如何解决《如何在SBT项目中列出活动插件？》经验，为你挑选了1个好方法。 ... [详细]
程序员
Android在Android UI中绘制圆角矩形

如何解决《Android在AndroidUI中绘制圆角矩形》经验，为你挑选了1个好方法。 ... [详细]
程序员
如何创建未在类中指定的成员的对象？

如何解决《如何创建未在类中指定的成员的对象？》经验，为你挑选了1个好方法。 ... [详细]
程序员
指针声明数组

如何解决《指针声明数组》经验，为你挑选了1个好方法。 ... [详细]
程序员
在ios9中,GCM注册尚未准备好使用auth凭据

如何解决《在ios9中,GCM注册尚未准备好使用auth凭据》经验，为你挑选了0个好方法。 ... [详细]
程序员
java中的immutable和final有什么区别？

如何解决《java中的immutable和final有什么区别？》经验，为你挑选了2个好方法。 ... [详细]
程序员
Open Layers 3获得Google Maps baselayer？

如何解决《OpenLayers3获得GoogleMapsbaselayer？》经验，为你挑选了1个好方法。 ... [详细]
程序员
没有类导航的Bootstrap scrollspy

如何解决《没有类导航的Bootstrapscrollspy》经验，为你挑选了0个好方法。 ... [详细]
程序员
电报机器人和方法getUpdates

如何解决《电报机器人和方法getUpdates》经验，为你挑选了0个好方法。 ... [详细]
程序员
如何运行Windows命令并每次都返回true？

如何解决《如何运行Windows命令并每次都返回true？》经验，为你挑选了1个好方法。 ... [详细]
程序员
为什么Webpack在每行之前输出奇怪的注释？

如何解决《为什么Webpack在每行之前输出奇怪的注释？》经验，为你挑选了0个好方法。 ... [详细]
程序员
Simple Injector是否可以通过对象工厂注册RegisterConditional？

如何解决《SimpleInjector是否可以通过对象工厂注册RegisterConditional？》经验，为你挑选了1个好方法。 ... [详细]
程序员
如何使多次启动的NSTimer无效

如何解决《如何使多次启动的NSTimer无效》经验，为你挑选了1个好方法。 ... [详细]

手机用户2402851335

这个屌丝很懒，什么也没留下！

关注作者

Tags | 热门标签

RankList | 热门文章