强算KMeans聚类算法演示器
这些天做C#实验以及这个KMeans算法演示器,学了一下openGL,感觉有待加强。
//Point.h /* Point 结构体定义及实现 结构体重载了2个运算符: 1.== //判断两个Point的坐标值是否相等 2.<< //用于显示(以友元函数的方式重载) */ #ifndef Point_h_ #define Point_h_ #include <iostream> #include <string> #include <iomanip> using namespace std; const int mWidth=3; //显示时每个字符宽度 //存放点坐标的结构 struct Point{ string name; //点名称 double x; //x轴坐标 double y; //y轴坐标 //默认的结构体构造器 Point() :x(-999),y(-999){ } Point(double xx,double yy,string n) :x(xx),y(yy),name(n){ } //复制构造函数 Point(const Point &p) :x(p.x),y(p.y),name(p.name){ } //赋值复制函数 Point operator=(const Point &p){ if(this==&p) return *this; x=p.x; y=p.y; name=p.name; return *this; } //判断两个Point坐标值是否相等 bool operator==(const Point &point)const{ return x==point.x&&y==point.y; } //重载<< friend ostream& operator<<(ostream &os,const Point &p){ os<<setw(mWidth)<<right<<p.name<< "("<<setw(mWidth)<<left<<p.x <<","<<setw(mWidth)<<p.y<<")"<<" "; return os; } }; #endif
functions.h主要是一些函数
//functions.h #ifndef functions_h_ #define functions_h_ #include <iostream> #include <cstdlib> #include <ctime> #include <vector> #include <iomanip> #include <string> #include <sstream> #include <vector> #include <iterator> #include <algorithm> #include "Point.h" #include <ctime> #include <windows.h> using namespace std; const int MAX=20; //聚类点数 const int M_GROUP=3; //簇数 const int LIMIT=20; //允许聚类的最大次数 const int X_LIMIT=15; //X轴最大坐标 const int Y_LIMIT=15; //Y---- //数字转字符串 string numberToString(int i){ stringstream s; s<<i; return s.str(); }; //delay(n) 延时n秒 void delay(double sec) { time_t start_time, cur_time; // 变量声明 time(&start_time); do { time(&cur_time); }while((cur_time - start_time) < sec ); }; //生成随机点 //size 生成随机点的个数 bool randPoint(vector<Point> &vp,int size){ vp.clear(); srand(time(0)); int i=0; //生成随机点 while(i<size){ int x=rand()%X_LIMIT; int y=rand()%Y_LIMIT; string name="p"; string num=numberToString(i+1); name+=num; //加入到数组中 vp.push_back(Point(x,y,name)); i++; } if(i==size) return true; else return false; }; //输出单个坐标 static int countTimes=0;//用于输出格式控制 void outPoint(Point &p){ cout<<p; countTimes++; if(countTimes%5==0) cout<<endl; }; //输出数组中所有点 //展示所有点的函数 void display(vector<Point> &vp){ countTimes=0; for_each(vp.begin(),vp.end(),outPoint); }; //清空流内容 void eatLine(){ while(cin.get()!='\n') continue; }; //选择起始中心点输入 //center 存储中心点的数组 //vp 所有点 bool inputCenter(vector<Point> ¢er,vector<Point> &vp){ //可分簇的最大数目 int vpSize=vp.size(); //清空center中内容 center.clear(); cout<<"\n请输入分簇的数目:0--"<<vpSize<<endl; int group; cin>>group; while(group<=0||group>vpSize){ cout<<"输入有误!"<<endl; cout<<"\n请输入分簇的数目:0--"<<vpSize<<endl; cin>>group; } //选择起始中心点 int j=0; while(j<group){ int locate; cout<<"请选择"<<group<<"个坐标点作为起始点,输入1代表p1:"<<endl; cin>>locate; if(locate>0&&locate<=vpSize){ Point temp=vp[locate-1]; cout<<"已经成功选择了"<<j+1<<"个起始点!"<<temp; center.push_back(temp); if(j!=group-1) cout<<"请继续完成剩余选择:"<<endl; else{ cout<<"\n选择完成!选择的中心点为:"<<endl; display(center); return true; } j++; }else{ cout<<"选择有误!"<<"请重新输入正确的值:" <<1<<"--"<<vpSize<<":"<<endl; } eatLine();//清空流 } return false; }; #endif
//kmeans.h #ifndef kmeans_h_ #define kmeans_h_ /* @author:天下无双 @date:2014-6-5 @version:9.0 聚类算法K-means实现:采用强算算法 随机生成20个点,然后进行分成三个聚类 change: 坐标点改为double类型 //已经完成聚类算法 //弃用指针,全部使用vector<Point>代替 //界面版openGL */ #include "functions.h" #include "openglFunc.h" #include "Point.h" #include <vector> #include <cmath> //参数为一维数组,数组大小,簇大小,选择的初始点 //返回值为聚类进行次数 //判断两次中心是否相等 bool isEqual(vector<Point> &lhs,vector<Point> &rhs){ int size=rhs.size(); for(int i=0;i<size;i++){ if(lhs[i]==rhs[i]) continue; else return false; } return true; }; //计算中心点 //当size为0时,返回一个(-999,-999)表示没有元素 Point calCenter(vector<Point> &arr){ int size=arr.size(); if(size!=0){ double xSum=0; double ySum=0; for(int i=0;i<size;i++){ xSum+=arr[i].x;//注意优先级 ySum+=arr[i].y; } double x=xSum/size; double y=ySum/size; return Point(x,y,"center"); }else return Point(-999,-999,"中心点重复,该中心没有点"); }; //计算两个点之间的距离 double pointToPoint(const Point &lhs,const Point &rhs){ double xToX=abs(lhs.x-rhs.x); double yToY=abs(lhs.y-rhs.y); double sum=pow(xToX,2)+pow(yToY,2); double f=sqrt(sum); return f; }; //kmeans //vp 点数组 //center 起始中心点数组 int kMeans(vector<Point> &vp,vector<Point> ¢er){ vector<Point> first;// 记录聚类上一次的中心 vector<Point> second; //记录这一次聚类的中心 vector<vector<Point>> group;//存放簇 /* center和group的关系 下标对应 0 1 2 3 4 center 0 1 2 3 4 group 00 01 02 03 04 10 11 12 13 14 20 21 22 23 24 .. .. .. .. .. */ int centerSize=center.size(); int vpSize=vp.size(); //先复制起始点到第一次聚类中心 for(int i=0;i<centerSize;i++) first.push_back(center[i]); cout<<"\n选择的起始中心点为:"<<endl; display(first); cout<<"图中标记为红色的为中心点:"<<endl; //表明第一次选择的中心点 paintCenterPoint(first); //number 聚类进行的次数 int number=0; //color用于显示点时自动选择颜色 int color=0; //第一次选择的中心点不应该被擦除 bool flag=true; do{ //先置group拥有相应的数组 group.clear(); for(int i=0;i<centerSize;i++){ vector<Point> p; group.push_back(p); } //将每个点指派到数组里面去 for(int i=0;i<vpSize;i++){ //locate 距离最近的中心点的坐标在center的下标 int locate=0; double min=999; for(int j=0;j<centerSize;j++){ double f=pointToPoint(vp[i],first[j]); //标记距离最短的那个中心点 if(f<min){ min=f; locate=j; } } //将点指派到对应的vector<Point> group[locate].push_back(vp[i]); //输出点指派信息 //cout<<vp[i]<<"将被指派到簇"<<locate+1<<";"<<endl; } //显示簇 cout<<"经过聚类后的分簇情况:"<<endl; for(int i=0;i<centerSize;i++){ cout<<"\n簇"<<numberToString(i+1)<<":"<<endl; display(group[i]); cout<<endl; } for(int i=0;i<centerSize;i++){ if(color==5) color=0;//重置color setColor(color++); paintVectorPoint(group[i]); } //重新计算簇中心并存放在second中 //先清空second second.clear(); for(int i=0;i<centerSize;i++){ second.push_back(calCenter(group[i])); } for(int i=0;i<centerSize;i++){ if(second[i].x!=-999&&second[i].y!=-999) second[i].name="c"+numberToString(i+1); } cout<<"\n新的簇中心为:"<<endl; display(second); //擦除旧中心点 if(!flag) RemoveCenterPoint(first); else{ flag=false; } //标明每个新中心 paintCenterPoint(second); if(isEqual(first,second)){ cout<<"\n聚类完成!"<<endl; cout<<"共聚类"<<number<<"次"<<endl; break; }else if(number>LIMIT){ cout<<"聚类次数超过了限制次数!"<<endl; cout<<"程序将退出"<<endl; break; }else{ cout<<"\n未达到条件,继续聚类!"<<endl<<endl<<endl; //重置first中心 first.clear(); for(int i=0;i<centerSize;i++){ first.push_back(second[i]); } } number++; }while(true); return 0; }; #endif
//openglFunc.h #ifndef opengl_kmeans_h_ #define opengl_kmeans_h_ #include <GL/glut.h> #include <vector> #include <iterator> #include <windows.h> #include <string> #include "Point.h" #include "functions.h" //延时时间 #define DELAYTIME 0.2 //点的大小 #define POINTSIZE 8 //显示比例 #define BILI 10 //边 #define BIAN 1 //X,Y边 #define XLIMIT 1.5 #define YLIMIT 1.5 void drawString(const char *str); //在屏幕上绘制单个点 void paintPoint(Point &p){ float x=p.x*1.0/BILI; float y=p.y*1.0/BILI; glPointSize(POINTSIZE); glBegin(GL_POINTS); glVertex2f(x,y); glEnd(); const char *name=p.name.c_str(); glRasterPos2f(x+0.02f,y+0.0f); drawString(name); glFlush(); }; //绘制一个数组的点 void paintVectorPoint(vector<Point> &vp){ int size=vp.size(); for(int i=0;i<size;i++){ paintPoint(vp[i]); delay(DELAYTIME); } }; //绘制中心点,使用红颜色 //不延时 void paintCenterPoint(vector<Point> &vp){ int size=vp.size(); glColor3f(1.0,0.0,0.0); for(int i=0;i<size;i++){ paintPoint(vp[i]); } }; //将坐标绘制成网格 void paintGrid(){ glColor3f(0.0,0.0,0.0); //竖向网格 for(int i=1;i<10*XLIMIT;i++){ float xx=i*1.0/10; glBegin(GL_LINES); glVertex2f(xx,0.0); glVertex2f(xx,YLIMIT); glEnd(); } //横向网格 for(int i=1;i<10*YLIMIT;i++){ float yy=i*1.0/10; glBegin(GL_LINES); glVertex2f(0.0,yy); glVertex2f(XLIMIT,yy); glEnd(); } }; //显示坐标轴 // ASCII字符总共只有0到127,一共128种字符 #define MAX_CHAR 128 void drawString(const char* str) { static int isFirstCall = 1; static GLuint lists; if( isFirstCall ) { // 如果是第一次调用,执行初始化 // 为每一个ASCII字符产生一个显示列表 isFirstCall = 0; // 申请MAX_CHAR个连续的显示列表编号 lists = glGenLists(MAX_CHAR); // 把每个字符的绘制命令都装到对应的显示列表中 wglUseFontBitmaps(wglGetCurrentDC(), 0, MAX_CHAR, lists); } // 调用每个字符对应的显示列表,绘制每个字符 for(; *str!='\0'; ++str) glCallList(lists + *str); }; //擦除旧的中心点 //使其变为白色 void RemoveCenterPoint(vector<Point> &vp){ int size=vp.size(); glColor3f(1.0,1.0,1.0); for(int i=0;i<size;i++){ paintPoint(vp[i]); } //重绘网格 paintGrid(); }; //绘制背景色为白色 void paintNull(){ glColor3f(1.0,1.0,1.0); glBegin(GL_POLYGON); glVertex2f(-BIAN,-BIAN); glVertex2f(-BIAN,BIAN); glVertex2f(BIAN,BIAN); glVertex2f(BIAN,-BIAN); glEnd(); }; //绘制XY轴 void paintXY(){ glColor3f(0.0,0.0,0.0); //绘制X轴 glBegin(GL_LINES); glVertex2f(-0.2,0); glVertex2f(XLIMIT,0); glEnd(); //Y glBegin(GL_LINES); glVertex2f(0.0,YLIMIT); glVertex2f(0.0,-0.2); glEnd(); //坐标轴数字 glColor3f(1.0f, 0.0f, 0.0f); glRasterPos2f(-0.05f,-0.05f); drawString("0"); glRasterPos2f(0.49f,-0.05f); drawString("5"); glRasterPos2f(0.99f,-0.05f); drawString("10"); glRasterPos2f(-0.05f,0.5f); drawString("5"); glRasterPos2f(-0.05f,0.99f); drawString("10"); glRasterPos2f(1.45f,-0.05f); drawString("y"); glRasterPos2f(-0.05f,1.45f); drawString("x"); glutSwapBuffers(); }; //设置各簇的颜色 //i最大值为6 void setColor(int i){ switch(i){ case 2:glColor3f(1.0, 1.0, 0.0);break; //--> 黄色 case 1:glColor3f(0.0, 0.0, 1.0);break; //--> 蓝色 case 0:glColor3f(0.0, 1.0, 0.0);break; //--> 绿色 //case 3:glColor3f(1.0, 0.0, 0.0);break; //--> 红色 case 4:glColor3f(0.0, 1.0, 1.0);break; //--> 青色 case 5:glColor3f(1.0, 0.0, 1.0);break; //--> 品红色 case 3:glColor3f(0.0, 0.0, 0.0);break; //--> 黑色 default:break; } } #endif
//tFunc.h #ifndef tFunc_h_ #define tFunc_h_ #include <iostream> #include "functions.h" #include <vector> #include "openglFunc.h" #include "kmeans.h" #include "functions.h" #include <string> using namespace std; void yourChoice(){ cout<<"请输入生成的随机点个数:(建议小于20点可以看得更清晰)"<<endl; int num; cin>>num; eatLine(); vector<Point> vp; vector<Point> center; randPoint(vp,num); cout<<"随机生成的坐标点如下:"<<endl; display(vp); cout<<"请等待画好点后选择中心点:"<<endl; paintVectorPoint(vp); inputCenter(center,vp); kMeans(vp,center); }; //演示书本例子 void Example(){ Point p[10]={ Point(3,4,"p1"), Point(3,6,"p2"), Point(7,3,"p3"), Point(4,7,"p4"), Point(3,8,"p5"), Point(8,5,"p6"), Point(4,5,"p7"), Point(4,1,"p8"), Point(7,4,"p9"), Point(5,5,"p10"), }; vector<Point> vp; vector<Point> center; for(int i=0;i<10;i++) vp.push_back(p[i]); center.push_back(p[6]); center.push_back(p[9]); paintVectorPoint(vp); kMeans(vp,center); }; #endif
//main.cpp #include "openglFunc.h" #include "functions.h" #include "tFunc.h" #include "displayFunc.h" int main(int argc,char **argv) { glutInit(&argc,argv); Init(); glutMainLoop(); }
DOS界面+openGL画图
演示如下: