聚类算法–近邻聚类算法(C++实现)
写在前面:
最近邻聚类算法,应该不是KNN,也不是K-means,就是一个特别基础的算法,但是在CSDN没有找到C++实现的这个算法,只有一个python写的(/Ha_hha/article/details/79128777),于是自己写了一个,目前还有错误,相同数据多次运行的结果不一样,希望有大佬可以指出是哪里有问题
算法介绍:
代码介绍:
用的vector存放内容,sampoint 存放样本点,clucenter存放聚类中心点。
在测试版输入样本点有两中方式,一个是样本点随机生成,一个是自己输入。
第一个聚类中心点随机生成。
euclidean_clu函数用来计算样本点和当前已有的聚类中心的欧式距离,如果样本点和每个聚类中心的距离都大于阈值T,就增加新的聚类中心,同时退出当前循环,重新执行当前函数。当该函数执行完,说明已经找到了全部的聚类中心。
euclidean_step再次计算所有样本点和聚类中心点的距离,找到距离样本点最近的一个聚类中心,进行分类,这里用了map存放。同时该函数输出最后的结果。
代码(纯净版):
#include <bits/stdc++.h>using namespace std;vector<vector<long long >> sampoint;vector<vector<long long >> clucenter;long long n,v,T,random_num;void euclidean_clu();void append_clu(long long x);void euclidean_step();int main(){/*1.输入数据*/long long temp;cout<<"输入样本个数和维度:"<<endl;cin>>n>>v; //输入样本个数和维度 cout<<"输入阈值T:"<<endl;cin>>T;vector<long long > intemp_clu;long long temp_n=n;cout<<"随机生成的样本点如下:"<<endl;while(n--){for(long long i=0;i<v;i++){temp=rand()%100;intemp_clu.push_back(temp);}sampoint.push_back(intemp_clu);intemp_clu.clear(); //每次输入完成都要清空,否则之前的数据会保留 }n=temp_n;/*输出测试*/for(long long i=0;i<temp_n;i++){for(long long j=0;j<v;j++){cout<<sampoint[i][j]<<" ";}cout<<endl;}/*2.获取第一个聚类中心,并在样本点中删除聚类中心*/long long temp_random;vector<long long > first_clucenter;temp_random=rand()%sampoint.size();for(long long i=0;i<v;i++){first_clucenter.push_back(sampoint[temp_random][i]);} sampoint.erase(sampoint.begin()+temp_random);clucenter.push_back(first_clucenter);cout<<endl;euclidean_clu();euclidean_step();}void euclidean_clu(){for(long long i=0;i<sampoint.size();i++){long long temp_dean=0,min_dean=1000000,min_clu=0,min_sam;for(long long j=0;j<clucenter.size();j++){for(long long k=0;k<v;k++){ temp_dean+=pow((sampoint[i][k]-clucenter[j][k]),2);}temp_dean=sqrt(temp_dean);if(temp_dean>T){append_clu(i);euclidean_clu(); //加入新的中心点后重新进行欧氏距离的计算 } temp_dean=0; }}return ;}/*4.增加聚类中心点*/void append_clu(long long x){clucenter.push_back(sampoint[x]);sampoint.erase(sampoint.begin()+x);}/*对样本点根据已有的聚类中心进行划分*/void euclidean_step(){long long temp_dean=0,min_dean=1000000,min_clu=0;map<long long ,long long > pdean;for(long long i=0;i<sampoint.size();i++){temp_dean=0,min_dean=1000000,min_clu=0;for(long long j=0;j<clucenter.size();j++){for(long long k=0;k<v;k++){ temp_dean+=pow((sampoint[i][k]-clucenter[j][k]),2);}if(temp_dean<min_dean){ //取最小的距离和对应的聚类中心 min_dean=temp_dean;min_clu=j;} temp_dean=0;}pdean.insert({i,min_clu});}cout<<"总共有"<<clucenter.size()<<"个聚类中心:"<<endl;for(long long i=0;i<clucenter.size();i++){for(long long j=0;j<v;j++){cout<<clucenter[i][j]<<" ";}cout<<endl;}cout<<endl;for(long long i=0;i<clucenter.size();i++){cout<<"第"<<i+1<<"类样本点:"<<endl;cout<<"(";for(long long j=0;j<v;j++){cout<<clucenter[i][j]<<" ";}cout<<")";cout<<endl;for(auto it=pdean.begin();it!=pdean.end();it++){if((*it).second==i){cout<<"(";for(long long j=0;j<v;j++){cout<<sampoint[(*it).first][j]<<" ";}cout<<") ";}}cout<<endl;}}
代码(测试用):
#include <bits/stdc++.h>using namespace std;vector<vector<long long>> sampoint;vector<vector<long long>> clucenter;long long n,v,T,random_num;void euclidean_clu();void append_clu(long long x);void euclidean_step();int main(){/*1.输入数据*/long long temp;cout<<"输入样本个数和维度:"<<endl;cin>>n>>v; //输入样本个数和维度 cout<<"输入阈值T:"<<endl;cin>>T;vector<long long> intemp_clu;long long temp_n=n;cout<<"随机生成的样本点如下:"<<endl;while(n--){for(long long i=0;i<v;i++){//cin>>temp;temp=rand()%100;intemp_clu.push_back(temp);//cout<<long longemp_clu[long longemp_clu.size()-1]<<endl;}sampoint.push_back(intemp_clu);intemp_clu.clear(); //每次输入完成都要清空,否则之前的数据会保留 }n=temp_n;/*输出测试*/for(long long i=0;i<temp_n;i++){for(long long j=0;j<v;j++){cout<<sampoint[i][j]<<" ";}cout<<endl;}/*2.获取第一个聚类中心,并在样本点中删除聚类中心*/long long temp_random;vector<long long> first_clucenter;temp_random=rand()%sampoint.size();//cout<<temp_random<<endl;for(long long i=0;i<v;i++){first_clucenter.push_back(sampoint[temp_random][i]);} sampoint.erase(sampoint.begin()+temp_random);clucenter.push_back(first_clucenter);cout<<"生成的第一个聚类中心点是:"<<endl;for(long long i=0;i<v;i++){cout<<clucenter[0][i]<<" ";}cout<<endl;/*first_clucenter.clear(); //测试是否成功删除聚点的样本点 for(long long i=0;i<temp_n;i++){for(long long j=0;j<v;j++){cout<<sampoint[i][j]<<" ";}cout<<endl;}*/euclidean_clu();cout<<"over"<<endl;euclidean_step();//std::cout << "The run time is: " <<(double)clock() / CLOCKS_PER_SEC << "s" << std::endl;//printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);}/*3.计算各样本点到聚类中心的欧式距离,函数实现*/void euclidean_clu(){vector<long long> all_dean;//cout<<sampoint.size()<<endl; /*输出样本点的个数*/long long temp_x=0;for(long long i=0;i<sampoint.size();i++){long long temp_dean=0,min_dean=1000000,min_clu=0,min_sam;for(long long j=0;j<clucenter.size();j++){for(long long k=0;k<v;k++){ temp_dean+=(sampoint[i][k]-clucenter[j][k])*(sampoint[i][k]-clucenter[j][k]);}/*得到样本点和某聚类中心点的距离之后,判断是否大于阈值,如果大于,则成为新的聚类中心点*///cout<<temp_dean<<" "<<i<<" "<<j<<endl; //输出各个样本点和聚类中心的欧氏距离 temp_x=sqrt(temp_dean);temp_dean=0;//cout<<"temp_x:"<<temp_x<<endl;all_dean.push_back(temp_x);/*if(long long(sqrt(temp_dean))>T){cout<<j<<endl;cout<<temp_dean<<" "<<long long(sqrt(temp_dean))<<" "<<i<<" "<<j<<endl; //cout<<"出现新的聚类中心"<<endl; append_clu(i);*///测试用/*for(long long i=0;i<sampoint.size();i++){for(long long j=0;j<v;j++){cout<<sampoint[i][j]<<" ";}cout<<endl;}*///euclidean_clu(); //加入新的中心点后重新进行欧氏距离的计算//return ; } bool bool_clu=true;for(long long a=0;a<all_dean.size();a++){//cout<<all_dean[i]<<" ";if(all_dean[i]<T){bool_clu=false;break;}}all_dean.clear();if(bool_clu){//cout<<"出现新的聚类中心"<<endl; append_clu(i);euclidean_clu(); //加入新的中心点后重新进行欧氏距离的计算return ; }//cout<<temp_dean<<endl;/*if(temp_dean<min_dean){ //取最小的距离和对应的聚类中心 min_dean=temp_dean;min_clu=j;}temp_dean=0; }cout<<i<<" "<<min_clu<<" "<<" "<<min_dean<<endl;pdean.insert({i,min_clu});}return ;} */}return ;}/*4.增加聚类中心点*/void append_clu(long long x){clucenter.push_back(sampoint[x]);/*cout<<"加入新的聚类中心:";for(long long i=0;i<v;i++){cout<<sampoint[x][i]<<" ";}*///cout<<"加入了新的聚类中心"<<endl;if(x==sampoint.size()-1){sampoint.pop_back();//cout<<"最后一个"<<endl;}else{sampoint.erase(sampoint.begin()+x);}return ;}/*对样本点根据已有的聚类中心进行划分*/void euclidean_step(){/* 测试用cout<<"聚类中心点为:"<<endl;for(long long i=0;i<clucenter.size();i++){for(long long j=0;j<v;j++){cout<<clucenter[i][j]<<" ";}cout<<endl;} *//*cout<<endl;for(long long i=0;i<sampoint.size();i++){for(long long j=0;j<v;j++){cout<<sampoint[i][j]<<" ";}cout<<endl;}*/long long temp_dean=0,min_dean=10000,min_clu=0;map<long long,long long> pdean;for(long long i=0;i<sampoint.size();i++){temp_dean=0,min_dean=10000,min_clu=0;for(long long j=0;j<clucenter.size();j++){for(long long k=0;k<v;k++){ temp_dean+=pow((sampoint[i][k]-clucenter[j][k]),2);}//cout<<temp_dean<<endl;if(temp_dean<min_dean){ //取最小的距离和对应的聚类中心 min_dean=temp_dean;min_clu=j;} //cout<<i<<" "<<min_clu<<" "<<" "<<min_dean<<endl;temp_dean=0;}pdean.insert({i,min_clu});}/*for(auto it=pdean.begin();it!=pdean.end();it++){cout<<(*it).first<<" "<<(*it).second<<endl;}*/cout<<"总共有"<<clucenter.size()<<"个聚类中心:"<<endl;for(long long i=0;i<clucenter.size();i++){for(long long j=0;j<v;j++){cout<<clucenter[i][j]<<" ";}cout<<endl;}cout<<endl;for(long long i=0;i<clucenter.size();i++){cout<<"第"<<i+1<<"类样本点:";cout<<"{";cout<<"(";for(long long j=0;j<v;j++){cout<<clucenter[i][j]<<" ";}cout<<")";//cout<<endl;for(auto it=pdean.begin();it!=pdean.end();it++){if((*it).second==i){cout<<"(";for(long long j=0;j<v;j++){cout<<sampoint[(*it).first][j]<<" ";}cout<<") ";}}cout<<"}";//cout<<endl;}}
写在最后:
ldu模式识别,代码仅作学习参考使用,🈲抄袭🙅,而且最后结果还是有错的。