c++实现K-means聚类算法(模式识别课设)
原理网上很多,我随便找两篇作为参考:原理介绍计算法实现:http://blog.csdn.net/qll125596718/article/details/8243404算法质量提高分析:http://blog.csdn.net/suibianshen2012/article/details/51584537代码里写了很多注释,就不解释了#include<iostream>using na
·
原理网上很多,我随便找两篇作为参考:
原理介绍计算法实现:http://blog.csdn.net/qll125596718/article/details/8243404
算法质量提高分析:http://blog.csdn.net/suibianshen2012/article/details/51584537
代码里写了很多注释,就不解释了
#include<iostream>
using namespace std;
#include<cmath>
#include<iomanip>
#include<fstream>
#include<cstdlib>
#include<conio.h>
ifstream fin; //输入文件
ofstream fout1; //输出文件
ofstream fout2;
ofstream fout3;
ofstream fout4;
const int maxDataNum=200;//可处理的最大数据量,可自己设置
const int K=3;//数据需要分成多少类
int dataNum;//实际数据的个数
const int dimension=4;//维度,数据的维数
double data[maxDataNum][dimension];//存放样本数据的数组,maxDataNum表示取得最大数据量,dimension表示每个数据的维数
double OldKMeans[K][dimension];//用于存放老聚类中心
double NewKMeans[K][dimension];//用于存放新聚类中心
double TempDist[K];//临时存放与每个聚类中心的距离
double TempNum[K];//每次聚类时每个聚类中心包含的最终数据个数,每次初始化为1
int index[maxDataNum];//保存每个数据属于哪个分类
void getDateNum()//从数据库中获取数据
{
fin.open("iris.txt",ios::in); //打开输入文件
dataNum = 0; //读取的样本点的数目,最大为maxDataNum
while(!fin.eof() && dataNum<maxDataNum) //读入数据
{
for(int i=0;i<dimension;i++){
fin>>data[dataNum][i];
}
dataNum++;
}
fin.close();
}
double CalcDist(double a[dimension],double b[dimension]) //计算两点之间的距离的平方(欧氏距离的平方)
{ //由于距离之间的比较等同于距离平方的比较,这里只需算出距离的平方
double t=0;
for(int i=0;i<dimension;i++){
t+=(a[i]-b[i])*(a[i]-b[i]);
}
return t;
}
int getMin(double TempDist[K])//返回数组最小值所在的下标
{
int sign=0;
for(int i=1;i<K;i++){
if(TempDist[i]<TempDist[sign])
sign=i;
}
return sign;
}
double getMinValue(int a,double array[])//返回数组最小值
{
double temp=array[0];
for(int i=1;i<a;i++){
if(array[i]<temp)
temp=array[i];
}
return temp;
}
void getNewKmeans(double data[maxDataNum][dimension],double OldKMeans[K][dimension])//求聚类中心,存放在NewKMeans里
{
int sign; //记录当前数据属于哪个聚类中心
for(int q=0;q<K;q++){//每次聚类前初始化,用于记录每个聚类中心包含多少个数据
TempNum[q]=0;
}
for(int i=0;i<dataNum;i++){//每个数据分别于聚类中心进行计算,判断该数据属于哪个聚类中心
for(int j=0;j<K;j++){//计算数据与每个聚类中心的距离,存放在TempDist中
TempDist[j]=CalcDist(data[i],OldKMeans[j]);
}
sign=getMin(TempDist);//返回最小距离所对应的下标,也就是该数据属于哪个聚类中心
TempNum[sign]++;//第sign个聚类中心包含的数据+1
index[i]=sign;//标记第i个数据属于第几个聚类中心
for(int k=0;k<dimension;k++){//将每个聚类中心的数据求和
NewKMeans[sign][k]+=data[i][k];
}
}
for(int j=0;j<K;j++){//取平均值
for(int n=0;n<dimension;n++){//先减去原来的聚类中心,因为最开始New等于Old,所以就是减去Old,那就仅是数据了
NewKMeans[j][n]-=OldKMeans[j][n];
}
for(int k=0;k<dimension;k++){
NewKMeans[j][k]/=TempNum[j];//除以每个聚类中心所包含的数据个数,得出平均值
}
}
}
bool Compare(double OldKMeans[K][dimension],double NewKMeans[K][dimension]) //比较新旧聚类中心是否相等
{
for(int i=0; i<K; i++)
for (int j = 0; j<dimension; j++)
if (fabs(OldKMeans[i][j]-NewKMeans[i][j])>1e-6)//该误差和数据有关
{
return false;
}
return true;
}
void initialize()//初始化聚类中心
{
for(int g=0;g<dimension;g++){//选第一个点初始化第一个聚类中心
NewKMeans[0][g]=data[0][g];
}
int next=1;//记录现在已经初始化了多少个聚类中心,上面已经初始化了一个,所以这里初始化为1
int sign[K-1];//记录初始聚类中心位于原始数据data数组中的下标
double dist=0;//记录数据与前面已经找到的聚类中心的距离的最小中的最大的那个(有点绕),见参考文章
double temp[K-1];//记录某一个数据与前面已经找到的聚类中心的距离
while(next<K){//该算法就是参考第二篇博文写的,感谢分享
for(int j=1;j<dataNum;j++){
for(int i=0;i<next;i++){
temp[i]=CalcDist(NewKMeans[i],data[j]);
}
double b=getMinValue(next,temp);
if(dist<getMinValue(next,temp)){
sign[next-1]=j;
dist=b;
}
}
int a=sign[next-1];
cout<<a<<endl;
for(int k=0;k<dimension;k++){
NewKMeans[next][k]=data[a][k];
}
next++;
dist=0;
}
}
void main()
{
getDateNum();//获取数据
initialize();//初始化聚类中心
int mask=0;//记录迭代次数
do{ //进行聚类
mask++;
for(int i=0;i<K;i++){ //将新聚类中心的值赋值给旧聚类中心
for(int j=0;j<dimension;j++){
OldKMeans[i][j]=NewKMeans[i][j];
}
}
cout<<endl;
getNewKmeans(data,OldKMeans);//求新聚类中心
}while(!Compare(OldKMeans,NewKMeans) && mask<100);//当新旧聚类中心相等(一定误差)时退出
//计算正确率
double accuracy0=0;//记录分类的正确率
double accuracy1=0;
double accuracy2=0;
for(int h=0;h<dataNum;){
while(h<50){
if(index[h]==0)//这里的0 1 2和取得初始聚类中心有关
accuracy0++;
h++;
}
while(h<100){
if(index[h]==2)
accuracy1++;
h++;
}
while(h<150){
if(index[h]==1)
accuracy2++;
h++;
}
}
double result=(accuracy0+accuracy1+accuracy2)/150;//这是总正确率
accuracy0=accuracy0/50;//这是每一部分的正确率
accuracy1=accuracy1/50;
accuracy2=accuracy2/50;
//输出相关数据
cout<<"训练数据个数:"<<dataNum<<endl;
cout<<"迭代次数:"<<mask<<endl;
cout<<"三个聚类中心的正确率分别为:"<<setprecision(2)<<fixed<<accuracy0<<" "<<accuracy1<<" "<<accuracy2<<endl;
for(int i=0;i<K;i++){ //打印最终聚类中心
cout<<"第"<<i+1<<"个聚类中心:"<<endl;
for(int j=0;j<dimension;j++){
cout<<NewKMeans[i][j]<<" ";
}
cout<<endl;
}
//以下为把数据分类后分成K个TXT文档存储
/*
fout1.open("K1.txt",ios::out);
fout2.open("K2.txt",ios::out);
fout3.open("K3.txt",ios::out);
for(int j=0;j<dataNum;j++){
for(int l=0;l<K;l++){//计算数据与每个聚类中心的距离,存放在TempDist中
TempDist[l]=CalcDist(data[j],NewKMeans[l]);
}
switch (getMin(TempDist)){
case 0:
fout1<<setprecision(2)<<fixed<<data[j][0]<<" "<<data[j][1]<<" "<<data[j][2]<<" "<<data[j][3]<<endl;
break;
case 1:
fout2<<setprecision(2)<<fixed<<data[j][0]<<" "<<data[j][1]<<" "<<data[j][2]<<" "<<data[j][3]<<endl;
break;
case 2:
fout3<<setprecision(2)<<fixed<<data[j][0]<<" "<<data[j][1]<<" "<<data[j][2]<<" "<<data[j][3]<<endl;
break;
}
}
fout1.close();
fout2.close();
fout3.close();
*/
本身代码可以缩减一部分的,只是我为了方便测试不同的数据样本,把代码整理好了,基本上除了fout那几个输出到TXT的地方需要修改外,只需要修改“K”,”maxDataNum”,”dimension”这三个变量就好了,其他和数据有关的地方也可以根据注释提示修改,挺方便的。
放一下测试结果:
训练数据个数:150
迭代次数:5
三个聚类中心的正确率分别为:1.00 0.96 0.72
第1个聚类中心:
5.01 3.43 1.46 0.25
第2个聚类中心:
6.85 3.07 5.74 2.07
第3个聚类中心:
5.90 2.75 4.41 1.43
Press any key to continue
测试数据是经典的鸢尾花数据集,来源http://archive.ics.uci.edu/ml/index.php
也可以百度搜“鸢尾花(Iris)数据集”,很多的。
运行环境是vc++6.0,其他环境未测试。
更多推荐
已为社区贡献1条内容
所有评论(0)