MyException - 我的异常网
当前位置:我的异常网» 编程 » 强算KMeans聚类算法演练器

强算KMeans聚类算法演练器

www.MyException.Cn  网友分享于:2014-06-09  浏览:0次
强算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画图
演示如下:


1楼shuhua21133小时前
谢谢
Re: guang_jing2小时前
回复shuhua2113nwhy?

文章评论

程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
10个调试和排错的小建议
10个调试和排错的小建议
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
鲜为人知的编程真相
鲜为人知的编程真相
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
每天工作4小时的程序员
每天工作4小时的程序员
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
如何成为一名黑客
如何成为一名黑客
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
那些争议最大的编程观点
那些争议最大的编程观点
为什么程序员都是夜猫子
为什么程序员都是夜猫子
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
中美印日四国程序员比较
中美印日四国程序员比较
程序员必看的十大电影
程序员必看的十大电影
Java程序员必看电影
Java程序员必看电影
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
编程语言是女人
编程语言是女人
我是如何打败拖延症的
我是如何打败拖延症的
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员的鄙视链
程序员的鄙视链
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
我的丈夫是个程序员
我的丈夫是个程序员
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员和编码员之间的区别
程序员和编码员之间的区别
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
旅行,写作,编程
旅行,写作,编程
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有