knn

//#include <windows.h>

#include <GL/glut.h>

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

double pi=3.1415926;

//male=0;female=1

double train[20][4]={{4272.0,888,52,0},{33037,106997,35,0},

{46960,191298,74,1},{5139,224,40,1},{9576,10466,34,0},

{19619 ,37571 ,31 ,1},{29825,4700,51,1},{6565,3542,39,0},

{23909,41540,43,0},{39350,11878,70,1},{20468,21740,58,0},

{7949,4562,26,0},{4018,964,22,0},{4054,8550,23,0},

{41877,21642,51,1},{943,138,27,0},{53095,30968,67,1},

{4118,3098,25,1},{3606,2528,30,0},{61620,7823,53,0}

};

double target[4]={23000,500,39,1};//蓝色叉所表示的位置即是//Display position place immediately fork 蓝色 Shi

double maxium[4]={70000.0,210000,100,2};//各项最大值//Up 值 each clause

//int credible[20]={0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,0,0,1};//分类,1表示可信，且用绿色；0表示不可信，且用红色表示(此为线性分类)

int credible[20]={1,0,1,0,1,0,1,0,0,0,1,1,1,0,1,0,0,0,1,0};//分类,1表示可信，且用绿色；0表示不可信，且用红色表示

int axisX=0,axisY=1;//表示参与训练的标准

char romania;

//K_NN方法

int k=6;

//以下为BP算法初始化

const int floor1=2;//中间层数

int level[floor1+2];//记录每层节点数

double weight[floor1+1][10][10];//每层节点不超过10个,此矩阵记录权重

double b[floor1+1][10];//记录偏移量

double n[floor1+1][10];//求和变量

double a[floor1+2][10];//每层输入量,即上一层输出量,因初始为原数据输入，故层数多1

double s[floor1+1][10];//反向传播时的中间量

double t[10];//输出终端

double e[10];//最终误差

double alfar=0.01;//学习率

void circlepoint(GLdouble x,GLdouble y,GLdouble radius)//画圆子程序

{

double step=2.0*pi/25.0;

for(int i=0;i<100;i++)

{

glVertex3d(x+radius*cos(i*step)*768/1024.0,y+radius*sin(i*step),0);

}

}

double distance(double x,double y,double xx,double yy)

{

return sqrt(pow(x-xx,2.0)+pow(y-yy,2.0));

}

double Gray(double x,double y)//计算每个点应属的颜色

{

double distance1[20];

double yangben[20][2];//转化为0-1坐标

int cre[20];//用以存储类别

double tran1;//用以作交换

int tran2;//用以作交换

int s=0;

for(int i=0;i<20;i++)

{

yangben[i][0]=train[i][axisX]/maxium[axisX];

yangben[i][1]=train[i][axisY]/maxium[axisY];

cre[i]=credible[i];

distance1[i]=distance(x,y,yangben[i][0],yangben[i][1]);

}//计算点到各样本点距离

for(int i=0;i<k;i++)

{

for(int j=i+1;j<20;j++)

{

if(distance1[i]>distance1[j])

{

tran1=distance1[i];distance1[i]=distance1[j];distance1[j]=tran1;

tran2=cre[i];cre[i]=cre[j];cre[j]=tran2;

}

}

}

for(int i=0;i<k;i++)

s=s+cre[i];

if(s>k/2)

return 1.0;

else

return 0.0;

}

double sigmoid(double x)

{

return 1/(1+exp(-x));

}

double Dsigmoid(double x)

{

return sigmoid(x)*(1-sigmoid(x));

}

void initBP(void)

{

//BP初始化

level[0]=2;//输入端2个节点

level[floor1+1]=1;//输出端1个节点

for(int i=0;i<floor1;i++)

level[i+1]=9;//设置中间层节点数均为3

printf("%d %d %d\n",level[0],level[1],level[2]);

for(int i=0;i<floor1+2-1;i++)//初始化权重矩阵及偏移量,共计 总层数-1 个

{

for(int j=0;j<level[i+1];j++)

b[i][j]=(rand()%100*0.01)-0.5;//初始化偏移量，[-0.5,0.5]

for(int j=0;j<level[i+1];j++)//初始化权重矩阵

{

for(int k=0;k<level[i];k++)

{

weight[i][j][k]=(rand()%100*0.02)-1.0;//[-1,1]

}

}

}

}

void computeBP(double x,double y,int z)//传入的x,y是原坐标

{

//前向计算

a[0][0]=x/maxium[axisX];a[0][1]=y/maxium[axisY];//初始化输入端

t[0]=credible[z];//初始化输出终端

for(int i=0;i<floor1+1;i++)//网格计算

{

for(int j=0;j<level[i+1];j++)

{

n[i][j]=0;

for(int k=0;k<level[i];k++)

{

n[i][j]+=weight[i][j][k]*a[i][k];

}

n[i][j]+=b[i][j];

a[i+1][j]=sigmoid(n[i][j]);//下一层输入

}

if(i==floor1)

{

for(int ii=0;ii<level[floor1+1];ii++)

e[ii]=t[ii]-a[i][ii];//误差记录

}

}

//反向传递过程

//首先为各层敏感度s计算

for(int ii=0;ii<level[floor1+1];ii++)

s[floor1][ii]=-2*e[ii]*Dsigmoid(n[floor1][ii]);//最后一层s初始化

for(int i=floor1-1;i>=0;i--)//反向计算s,i表示层数

{

for(int j=0;j<level[i+1];j++)//j表示本层节点

{

s[i][j]=0;

for(int k=0;k<level[i+2];k++)//k表示上一层节点

{

s[i][j]+=s[i+1][k]*Dsigmoid(n[i][j])*weight[i+1][k][j];

}

}

}//调整结束

for(int i=0;i<floor1+2-1;i++)//更改权重矩阵及偏移量,共计 总层数-1 个

{

for(int j=0;j<level[i+1];j++)

b[i][j]=b[i][j]-alfar*s[i][j];//更改偏移量，[-0.5,0.5]

for(int j=0;j<level[i+1];j++)//更改权重矩阵

{

for(int k=0;k<level[i];k++)

{

weight[i][j][k]=weight[i][j][k]-alfar*s[i][j]*a[i][k];//[-1,1]

}

}

}

////输出

//for(int i=0;i<floor1+2-1;i++)//初始化权重矩阵及偏移量,共计 总层数-1 个

//{

// for(int j=0;j<level[i+1];j++)

// printf("b, %f\n",b[i][j]);

// printf("\n");

// for(int j=0;j<level[i+1];j++)//初始化权重矩阵

// {

// for(int k=0;k<level[i];k++)

// {

// printf("weight, %f\n",weight[i][j][k]);

// }

// printf("\n");

// }

//}

}

double finalBP(double x,double y,int z)

{

//前向计算

double sum=0.0;//误差累加

a[0][0]=x/maxium[axisX];a[0][1]=y/maxium[axisY];//初始化输入端

t[0]=credible[z];//初始化输出终端

for(int i=0;i<floor1+1;i++)//网格计算

{

for(int j=0;j<level[i+1];j++)

{

n[i][j]=0;

for(int k=0;k<level[i];k++)

{

n[i][j]+=weight[i][j][k]*a[i][k];

}

n[i][j]+=b[i][j];

a[i+1][j]=sigmoid(n[i][j]);//下一层输入

}

}

for(int ii=0;ii<level[floor1+1];ii++)

{

e[ii]=t[ii]-a[floor1+1][ii];//误差记录

sum+=pow(e[ii],2.0);

}

return sum;

}

double GrayBP(double x,double y)

{

a[0][0]=x;a[0][1]=y;//初始化输入端

for(int i=0;i<floor1+1;i++)//网格计算

{

for(int j=0;j<level[i+1];j++)

{

n[i][j]=0;

for(int k=0;k<level[i];k++)

{

n[i][j]+=weight[i][j][k]*a[i][k];

}

n[i][j]+=b[i][j];

a[i+1][j]=sigmoid(n[i][j]);//下一层输入

}

}

//printf("%f\n",a[floor1+1][0]);

if(a[floor1+1][0]>0.5)

return 1.0;

else

return 0.0;

}

void CircleBP(void)

{

double Esum=30.0;

int Isum=0;

while(Esum>0.1 && Isum<300000)

{

//printf("%f %d\n",Esum,Isum);

Esum=0.0;

Isum++;

for(int i=0;i<20;i++)

computeBP(train[i][axisX],train[i][axisY],i);

for(int i=0;i<20;i++)

Esum+=finalBP(train[i][axisX],train[i][axisY],i);

Esum=Esum/20.0;

}

printf("%f %d\n",Esum,Isum);

}

void display(void)

{

glClearColor (1,1,1, 0.0);

glClear (GL_COLOR_BUFFER_BIT);

glColor3f (0,0.0,0.0);

double red,green;

//绘制背景

if(romania=='k')

{

//K-NN

printf("K-nn %d\n",k);

glBegin(GL_POINTS);

for(double u=-0.2;u<=1.0;u+=0.001)

{

for(double v=-0.2;v<=1.0;v+=0.001)

{

red=(1.0-Gray(u,v))*0.5;

green=(Gray(u,v))*0.5;

glColor3f(red+0.3,green+0.3,0+0.4);

glVertex2d(u,v);

}

}

glEnd();

}

////BP

else if(romania=='b')

{

initBP();

CircleBP();

//printf("隐层数目为%d,每层节点数为%d,激活函数为sigmoid函数\n",floor1,level[1]);

printf("The first act of %d,Acts of nodes %d, Acts super active function sigmoid Function\n",floor1,level[1]);

glBegin(GL_POINTS);

for(double u=-0.2;u<=1.0;u+=0.001)

{

for(double v=-0.2;v<=1.0;v+=0.001)

{

red=(1.0-GrayBP(u,v))*0.5;

green=(GrayBP(u,v))*0.5;

glColor3f(red+0.3,green+0.3,0+0.4);

glVertex2d(u,v);

}

}

glEnd();

}

//绘制输出样本点及坐标轴

for(int i=0;i<20;i++)

{

if(credible[i]==0)

{

red=1.0;green=0.0;

}

else

{

red=0.0,green=1.0;

}

glColor3f(red,green,0.0);

glBegin(GL_POLYGON);

circlepoint(train[i][axisX]/maxium[axisX],train[i][axisY]/maxium[axisY],0.008);

glEnd();

}//初始化

glColor3f(0,0,0);

glBegin(GL_LINES);

glVertex2d(-0.2,-0.2);

glVertex2d(1,-0.2);

glEnd();//坐标轴

glBegin(GL_LINES);

glVertex2d(-0.2,-0.2);

glVertex2d(-0.2,1);

glEnd();//坐标轴

//下面绘制所需进行分类的目标点(十字叉)

red=target[axisX]/maxium[axisX];

green=target[axisY]/maxium[axisY];

glColor3f(0,0,1);

glBegin(GL_LINES);

glVertex2d(red-0.008,green+0.008);

glVertex2d(red+0.008,green-0.008);

glEnd();//目标点

glBegin(GL_LINES);

glVertex2d(red-0.008,green-0.008);

glVertex2d(red+0.008,green+0.008);

glEnd();//目标点

glFlush ();

}

void init (void)

{

glClearColor (0.0, 0.0, 0.0, 0.0);

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

glOrtho(-0.3, 1.1, -0.3, 1.1, -2.0, 100);//设置窗口

}

void mykey(unsigned char key,int x,int y)

{

switch(key)

{

case 'k'://clear

romania='k';

glutPostRedisplay();

break;

case 'b':

romania='b';

glutPostRedisplay();

break;

default:

break;

}

}

void initInput(void)

{

printf("   1  2 3 4   5\nIncome Debts Age Sex Credible\n\n");

for(int i=0;i<20;i++)

{

if(train[i][3]<0.5)

{

printf("%f %f %f male %d\n",train[i][0],train[i][1],train[i][2],credible[i]);

}

else

{

printf("%f %f %f female %d\n",train[i][0],train[i][1],train[i][2],credible[i]);

}

}

//printf("\n\n请输入用以分类的两个标准(横纵坐标的属性)\n以1,2,3,4表示.例如：若以income为横轴，debts为纵轴，则输入1,2。\n");

printf("\n\nStandards need (next target attribute)\n Than 1,2,3,4 Display. Example For：Younger than income axis，debts axis，Enter 1,2。\n");

scanf("%d,%d",&axisX,&axisY);

axisX--;axisY--;

//printf("\n键盘操作：‘k’表示调用K-NN算法，‘b’表示调用BP算法\n");

printf("\nKeyboard Operation：‘k’ Show K-NN algorithm，‘b’ Show BP algorithm\n");

}

int main(int argc, char** argv)

{

initInput();

glutInit(&argc, argv);

glutInitDisplayMode (GLUT_SINGLE | GLUT_RGB);

glutInitWindowSize (1024, 768);

glutInitWindowPosition (100, 100);

glutCreateWindow ("classify");

init ();

glutDisplayFunc(display);

//glutMotionFunc(myMoveMouse);

glutKeyboardFunc(mykey);

//glutMouseFunc(myMouse);

glutMainLoop();

return 0;

}