k均值算法c++语言实现代码_C 语言

复制代码 代码如下:

//k-mean.h
 #ifndef KMEAN_HEAD
 #define KMEAN_HEAD

 #include <vector>
 #include <map>

 //空间点的定义
 class Node
 {
     public:
        double pos_x;
        double pos_y;
        double pos_z;
      Node()
      {
          pos_x = 0.0;
          pos_y = 0.0;
          pos_z = 0.0;
      }
      Node(double x,double y,double z)
      {
          pos_x = x;
          pos_y = y;
          pos_z = z;
      }
       friend bool operator < (const Node& first,const Node& second)
       {
          //对x轴的比较
          if(first.pos_x < second.pos_x)
          {
        　　　　 return true;
          }
      　　else if (first.pos_x > second.pos_x)
          {
              return false;
     　　　}
         //对y轴的比较
      else
      {
        if(first.pos_y < second.pos_y)
             {
                 return true;
             }
             else if (first.pos_y > second.pos_y)
             {
                return false;
             }
             //对z轴的比较
         else
         {
             if(first.pos_z < second.pos_z)
                 {
                     return true;
                 }
                 else if (first.pos_z >=  second.pos_z)
                 {
                  　　return false;
                 }
             }
      }
       }

       friend bool operator == (const Node& first,const Node& second)
       {
             if(first.pos_x == second.pos_x && first.pos_y == second.pos_y && first.pos_z == second.pos_z)
             {
                 return true;
             }
             else
             {
                 return false;
             }
       }
 };

 class KMean
 {
 private:
     int cluster_num;//生成的簇的数量。
     std:: vector<Node> mean_nodes;//均值点
     std:: vector<Node> data;//所有的数据点
     std:: map <int , std:: vector<Node> > cluster;//簇,key为簇的下标，value为该簇中所有点

     void Init();//初始化函数（首先随即生成代表点）
     void ClusterProcess();//聚类过程，将空间中的点分到不同的簇中
     Node GetMean(int cluster_index);//生成均值
     void NewCluster();//确定新的簇过程，该函数会调用ClusterProcess函数。
     double Kdistance(Node active,Node other);//判断两个点之间的距离

     public:
     KMean(int c_num,std:: vector<Node> node_vector);
     void Star();//启动k均值算法

 };
#endif // KMEAN_HEAD

复制代码 代码如下:

//k-mean.h
 #ifndef KMEAN_HEAD
 #define KMEAN_HEAD

 #include <vector>
 #include <map>

 //空间点的定义
 class Node
 {
     public:
        double pos_x;
        double pos_y;
        double pos_z;
      Node()
      {
          pos_x = 0.0;
          pos_y = 0.0;
          pos_z = 0.0;
      }
      Node(double x,double y,double z)
      {
          pos_x = x;
          pos_y = y;
          pos_z = z;
      }
       friend bool operator < (const Node& first,const Node& second)
       {
          //对x轴的比较
          if(first.pos_x < second.pos_x)
          {
        　　　　 return true;
          }
      　　else if (first.pos_x > second.pos_x)
          {
              return false;
     　　　}
         //对y轴的比较
      else
      {
        if(first.pos_y < second.pos_y)
             {
                 return true;
             }
             else if (first.pos_y > second.pos_y)
             {
                return false;
             }
             //对z轴的比较
         else
         {
             if(first.pos_z < second.pos_z)
                 {
                     return true;
                 }
                 else if (first.pos_z >=  second.pos_z)
                 {
                  　　return false;
                 }
             }
      }
       }

       friend bool operator == (const Node& first,const Node& second)
       {
             if(first.pos_x == second.pos_x && first.pos_y == second.pos_y && first.pos_z == second.pos_z)
             {
                 return true;
             }
             else
             {
                 return false;
             }
       }
 };

 class KMean
 {
 private:
     int cluster_num;//生成的簇的数量。
     std:: vector<Node> mean_nodes;//均值点
     std:: vector<Node> data;//所有的数据点
     std:: map <int , std:: vector<Node> > cluster;//簇,key为簇的下标，value为该簇中所有点

     void Init();//初始化函数（首先随即生成代表点）
     void ClusterProcess();//聚类过程，将空间中的点分到不同的簇中
     Node GetMean(int cluster_index);//生成均值
     void NewCluster();//确定新的簇过程，该函数会调用ClusterProcess函数。
     double Kdistance(Node active,Node other);//判断两个点之间的距离

     public:
     KMean(int c_num,std:: vector<Node> node_vector);
     void Star();//启动k均值算法

 };
#endif // KMEAN_HEAD

复制代码 代码如下:

 #include "k-mean.h"
 #include <vector>
 #include <map>
 #include <ctime>
 #include <cstdlib>
 #include <algorithm>
 #include <cmath>
 #include <iostream>

 using namespace std;
 #define MAXDISTANCE 1000000

 KMean::KMean(int c_num,vector<Node> node_vector)
 {
       cluster_num = c_num;
       data = node_vector;
       srand((int)time(0));
       Init();
 }

 void KMean::Init()//初始化函数（首先随即生成代表点）
 {
      for(int i =0 ;i<cluster_num;)
      {
            int pos = rand() % data.size();

            bool insert_flag = true;

            //首先判断选中的点是否是中心点
            for(unsigned int j = 0;j<mean_nodes.size();j++)
            {
                if(mean_nodes[j] ==  data[i])
                {
                    insert_flag = false;
                    break;
                }
            }

            if(insert_flag )
            {
                  mean_nodes.push_back(data[pos]);
                  i++;
            }
      }
      ClusterProcess();//进行聚类过程
 }

  void KMean::ClusterProcess()//聚类过程，将空间中的点分到不同的簇中
  {
             //遍历空间上所有的点
             for( unsigned int i = 0 ; i < data.size();i++)
             {
                  //忽略中心点
                 bool continue_flag = false;
                 for(unsigned int j = 0;j<mean_nodes.size();j++)
                     {
                         if(mean_nodes[j] ==  data[i])
                         {
                                 continue_flag = true;
                                 break;
                         }
                     }
                 if(continue_flag)
                     {
                         continue;
                     }

                  //下面是聚类过程
                  //首先找到离当前点最近的中心点,并记录下该中心点所在的簇
                  int min_kdistance = MAXDISTANCE;
                  int index = 0 ;
                  for(unsigned int j = 0;j < mean_nodes.size();j++)
                  {
                      double dis = Kdistance(data[i],mean_nodes[j]);
                      if(dis < min_kdistance)
                      {
                          min_kdistance = dis;
                          index = j;
                      }
                  }

                   //先将当前点从原先的簇中删除
                   map<int,vector<Node> >::iterator iter;
         //搜索所有的簇
                   for(iter = cluster.begin();iter != cluster.end();++iter)
                   {

                vector<Node>::iterator node_iter;
                      bool jump_flag = false;
                      //对每个簇中的vector进行搜索
                      for(node_iter = iter->second.begin();node_iter != iter->second.end();node_iter++)
            　　　　  　{
          　　　　　　   if(*node_iter == data[i])
          　　　　　　　 {
                             //如果当前点就在更新的簇中，则忽略后面的操作
        　　　　　　         if(index == iter->first)
                            {
                     　　　　　　continue_flag = true;
                             }
                             else
                             {
　　　　　　                     iter->second.erase(node_iter);
                             }
          　　　       　　 jump_flag = true;
               　　　　  　　break;
             　　　　　　　}
              　　}
              　　　　　　if(jump_flag)
             　　　　　　 {
             　　　　　　　　break;
              　　　　　　}
                   　　}

                   if(continue_flag)
           　　　　{
                  　　 continue;
                   }
                   //将当前点插入到中心点所对应的簇中
                   //查看中心点是否已经存在map中
                  bool insert_flag = true;
                  for(iter = cluster.begin(); iter != cluster.end();++iter)
                  {

                     if(iter->first == index)
             　　　　　{
                     　　   iter->second.push_back(data[i]);
                       　　 insert_flag = false;
                　　　　　　　break;
              　　　　　}
                  }
                  //不存在则创建新的元素对象
                  if(insert_flag)
                  {
                      vector<Node> cluster_node_vector;
                      cluster_node_vector.push_back(data[i]);
                      cluster.insert(make_pair(index,cluster_node_vector));
                  }
             }
  }

  double KMean::Kdistance(Node active,Node other)
  {
         return sqrt(pow((active.pos_x-other.pos_x),2) + pow((active.pos_y - other.pos_y),2) + pow((active.pos_z - other.pos_z),2));
  }

  Node KMean::GetMean(int cluster_index)
  {
      //对传入的参数进行判断，查看是否越界
      if( cluster_num <0 || unsigned (cluster_index) >= mean_nodes.size() )
      {
          Node new_node;
          new_node.pos_x = -1.0;
          new_node.pos_y = -1.0;
          new_node.pos_z = -1.0;
          return new_node;
      }

      //求出簇中所有点的均值
      Node sum_node;
      Node aver_node;
        for(int j = 0;j < cluster[cluster_index].size();j++)
         {
         　　sum_node.pos_x += cluster[cluster_index].at(j).pos_x;
            sum_node.pos_y += cluster[cluster_index].at(j).pos_y;
         　　sum_node.pos_z += cluster[cluster_index].at(j).pos_z;
     　　　}
         aver_node.pos_x = sum_node.pos_x*1.0/ cluster[cluster_index].size();
         aver_node.pos_y = sum_node.pos_y*1.0 / cluster[cluster_index].size();
         aver_node.pos_z = sum_node.pos_z*1.0 / cluster[cluster_index].size();

       //找到与均值最近的点
      double min_dis = MAXDISTANCE;
      Node new_mean_doc;

      for(unsigned int i  = 0;i< cluster[cluster_index].size();i++)
      {
            double dis = Kdistance(aver_node,cluster[cluster_index].at(i));
            if(min_dis > dis)
            {
                  min_dis = dis;
                  new_mean_doc = cluster[cluster_index].at(i);
            }
      }
      return new_mean_doc;
  }

  void KMean::NewCluster()//确定新的中心点
  {
       for (unsigned int i = 0;i < mean_nodes.size();i++)
       {
            Node new_node =GetMean(i);
            mean_nodes[i] = new_node;
       }
       ClusterProcess();
  }

 void KMean::Star()
 {
     for (int i = 0;i<100;i++)
     {
         NewCluster();
         cout << "no:"<< i<<endl;
         for(int j = 0;j < mean_nodes.size();j++)
     {
         cout << cluster[j].size()<<endl;
     }

     }
 }

复制代码 代码如下:

#include <iostream>
#include <vector>
#include "k-mean.h"
#include <ctime>
#include <cstdlib>

using namespace std;
int main()
 {
     srand((int) time(0));

     vector<Node> data;

     for(int i =0;i<100;i++)
     {
          Node node;
          node.pos_x = (random() % 17 )*1.2;
          node.pos_y = (random() % 19 )*1.2;
          node.pos_z = (random() % 21) *1.2;
          data.push_back(node);
     }

     KMean kmean(3,data);
     kmean.Star();

     return 0;
 }

时间： 2024-08-23 23:37:07

k均值算法c++语言实现代码_C 语言的相关文章

马尔可夫链算法（markov算法）的awk、C++、C语言实现代码_C 语言

1. 问题描述 马尔可夫链算法用于生成一段随机的英文,其思想非常简单.首先读入数据,然后将读入的数据分成前缀和后缀两部分,通过前缀来随机获取后缀,籍此产生一段可读的随机英文. 为了说明方便,假设我们有如下一段话:   复制代码 代码如下:    Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious.   假

C语言对堆排序一个算法思路和实现代码_C 语言

算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

贪心算法 WOODEN STICKS 实例代码_C 语言

Problem DescriptionThere is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to

优先队列(priority_queue)的C语言实现代码_C 语言

优先队列(priority_queue)和一般队列(queue)的函数接口一致,不同的是,优先队列每次出列的是整个队列中最小(或者最大)的元素. 本文简要介绍一种基于数组二叉堆实现的优先队列,定义的数据结构和实现的函数接口说明如下: 一.键值对结构体:KeyValue 复制代码 代码如下: // =============KeyValue Struct==================================typedef struct key_value_struct KeyValu

哈夫曼的c语言实现代码_C 语言

我们设置一个结构数组 HuffNode 保存哈夫曼树中各结点的信息.根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有 2n-1 个结点,所以数组 HuffNode 的大小设置为 2n-1 .HuffNode 结构中有 weight, lchild, rchild 和 parent 域.其中,weight 域保存结点的权值, lchild 和 rchild 分别保存该结点的左.右孩子的结点在数组 HuffNode 中的序号,从而建立起结点之间的关系.为了判定一个结点是否已加入到要建立的哈夫曼树

C语言 奇偶排序算法详解及实例代码_C 语言

C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

C语言二分查找算法及实现代码_C 语言

二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列.该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分.接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解. #include <stdio.h> binar

C语言实现排序算法之归并排序详解_C 语言

排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

C语言合并排序及实例代码_C 语言

归并排序也称合并排序,其算法思想是将待排序序列分为两部分,依次对分得的两个部分再次使用归并排序,之后再对其进行合并.仅从算法思想上了解归并排序会觉得很抽象,接下来就以对序列A[0], A[l]-, A[n-1]进行升序排列来进行讲解,在此采用自顶向下的实现方法. 操作步骤如下: (1)将所要进行的排序序列分为左右两个部分,如果要进行排序的序列的起始元素下标为first,最后一个元素的下标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是A[first