k均值算法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;
}
相关文章
- vector是表示可以改变大小的数组的序列容器，本文主要介绍了C++STL标准库std::vector的使用详解，文中通过示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子，讲述了C++调用C#的DLL程序的方法，作出了以下总结，下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码，小编觉得挺不错的，现在分享给大家，也给大家做个参考。...2020-04-25
- 整数拆分，指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解，非常不错，感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析，sort函数是algorithm库下的一个函数，sort函数是不稳定的，即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文)，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法，而是讲解我个人比较好奇的问题，就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的，但是开发人员在与内存的斗争问题上并没有解放，如果我门实用不当仍然有内存泄漏问题，其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用，一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员，删除map容器中value为指定元素的问题是我们经常与遇到的一个问题，下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料，需要的朋友可以参考借鉴，下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍，需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧...2020-04-25