模式识别中K-means算法实现

小咪咪 2022-09-18 12:49 156阅读 0赞

以前写了一个K-means(C-means)K均值也成为C均值算法，该算法是聚类分析中的一个经典算法，现把程序粘上，大家相互讨论，以前写的代码，写过看起来有许多要改的地方，懒的改了，其中是用OpenGL画的图，很简单的图，本来自己的代码能力就不强哈！

程序如下:

#include <stdio.h> 
    #include <math.h>
    #include <MALLOC.H>
    #include <TIME.H>
    #include <CONIO.H>
    #include <STDLIB.H>
    #include <MATH.H>
    #include <graphics.h>
    #include <GL/glut.h>
    #include <WINDOWS.H>
    #define TRUE            1
    #define FALSE           0 
    int N;//数据个数
    int K;//集合个数
    int * CenterIndexX;//初始化质心数组的索引
    int * CenterIndexY;
    double * CenterX;//质心集合
    double * CenterY;
    double * CenterCopyX;//质心集合副本
    double * CenterCopyY;
    double * AllDataX;//数据集合
    double * AllDataY;
    double ** ClusterX;//簇的集合
    double ** ClusterY;
    int * TopX;//集合中元素的个数，也会用作栈处理
    int * TopY;
    
    //随机生成k个数x(0<=x<=n-1)作为起始的质心集合
    void CreateRandomArray(int N,int k,int * centerX,int * centerY)
    {
        int i=0;
        int j=0;    
        srand( (unsigned)time( NULL ) );
        for( i=0;i<k;++i)//随机生成k个数
        {
            int a1=rand()%N;
    		int a2=rand()%N;
            //判重
            for(j=0;j<i;j++)
            {
                if(centerX[j]==a1&¢erY[j]==a2)//重复
                {
                    break;
                }
            }
            if(j>=i)//如果不重复，加入
            {
                centerX[i]=a1;
    			centerY[i]=a2;
            }
            else
            {
    			//如果重复，本次重新随机生成
                i--;        
            }
        }     
    }
     
    //返回距离最小的质心的序号
    int GetIndex(double valueX,double valueY,double * centerX,double * centerY)
    {
        int i=0;
        int index=i;//最小的质心序号
        double min=sqrt(pow((valueX-centerX[i]),2)+pow((valueY-centerY[i]),2) );//距质心最小距离
        for(i=0;i<K;i++)
        {
            if( ( sqrt(pow((valueX-centerX[i]),2)+pow((valueY-centerY[i]),2) ))<min)//如果比当前距离还小，更新最小的质心序号和距离值
            {
    			index=i;
    			min=sqrt(pow((valueX-centerX[i]),2)+pow((valueY-centerY[i]),2) );
            }
        }
        return index;
    }
     
    //拷贝质心数组到副本
    void CopyCenter()
    {
        int i=0;
        for(i=0;i<K;i++)
        {
            CenterCopyX[i]=CenterX[i];
    		CenterCopyY[i]=CenterY[i];
        }
    }
    
    //初始化质心，随机生成法
    void InitCenter()
    {
        int i=0;
        CreateRandomArray(N,K,CenterIndexX,CenterIndexY);//产生随机的K个<N的不同的序列
        for(i=0;i<K;i++)
        {
            CenterX[i]=AllDataX[CenterIndexX[i]];//将对应数据赋值给质心数组
    		CenterY[i]=AllDataY[CenterIndexY[i]];
        }
    	/*
    	printf("-------------Test-------------------- ");
    	printf("\n");
    	for(i=0;i<K;i++)
    	{
    		printf("CenterX[i]的数值是%.3f  ",CenterX[i]);
    	}
    	printf("\n");
    	for(i=0;i<K;i++)
    	{
    		printf("CenterY[i]的数值是%.3f  ",CenterY[i]);
    	}
    	printf("\n");
    	*/
    
        CopyCenter();//拷贝到质心副本
    }
    
    //重新计算质心集合，对每一簇集合中的元素加总求平均即可
    void UpdateCenter()
    {
        int i=0;
        int j=0;
        double sumX=0;
    	double sumY=0;
        for(i=0;i<K;i++)
        {
            sumX=0;
    		sumY=0;
            //计算簇i的元素和
            for(j=0;j<TopX[i];j++)
    		{
    			sumX+=ClusterX[i][j];
    			sumY+=ClusterY[i][j];
    		}
            if(TopX[i]>0&&TopY[i]>0)//如果该簇元素不为空
            {
    			CenterX[i]=sumX/TopX[i];//求其平均值
    			CenterY[i]=sumY/TopY[i];
            }
        }
    }
    
    //判断2数组元素是否相等
    int IsEqual(double * center1 ,double * center2)
    {
        int i;
        for(i=0;i<K;i++)
        {
             if(fabs(center1[i]!=center2[i]))
             {
                 return FALSE;
             }
        }
        return TRUE;
    }
    //加入一个数据到一个Cluster[index]集合
    void AddToCluster(int index,double valueX,double valueY)
    {
        ClusterX[index][TopX[index]++]=valueX;//这里同进栈操作
    	ClusterY[index][TopY[index]++]=valueY;
    	/*
    	int i;
    	for(i=0;i<K;i++)
    	{
    		printf("Top[%d]的值 %d  ", i,Top[i]);
    	}
    	*/
    } 
    
    //重新计算簇集合
    void UpdateCluster()
    {    
        int i=0;
        int tindex;
        //将所有的集合清空，即将TOP置0
        for(i=0;i<K;i++)
        {
            TopX[i]=0;
    		TopY[i]=0;
        }
        for(i=0;i<N;i++)
        {
            tindex=GetIndex(AllDataX[i],AllDataY[i],CenterX,CenterY);//得到与当前数据最小的质心索引
            AddToCluster(tindex,AllDataX[i],AllDataY[i]);        //加入到相应的集合中 
        }
    }
    
    //打印聚合结果
    void Print()
    {
        int i,j;
        printf("-------------------------------------- ");
    	printf("\n");
        for(i=0;i<K;i++)
        {
    		printf("第%d组: 质心(%.3f , %.3f) ",i+1,CenterX[i],CenterY[i]);
    		printf("\n");
    		for(j=0;j<TopX[i];j++)
    		{
    			printf("%.3f  %.3f",ClusterX[i][j],ClusterY[i][j]);
    			printf("\n");
    		}           
        }  
    }
    
    void display()
    {		
    		int i,j;
    		glPointSize(10.0);
    		glColor3f(1.0f , 0.0f , 0.0f);
            glEnable(GL_POINT_SMOOTH);
    		glBegin(GL_POINTS);
    		for(i=0;i<K;i++)
    		{
    			if(i==0)
    			{
    				glColor3f(1.0,0.0,0.0);
    				glVertex2f(CenterX[i],CenterY[i]);
    				for(j=0;j<TopX[i];j++)
    				{
    					glColor3f(0.5,0.0,0.0);
    					glVertex2f(ClusterX[i][j],ClusterY[i][j]);
    				}
    			}
    			else if(i==1)
    			{
    				glColor3f(0.0,1.0,0.0);
    				glVertex2f(CenterX[i],CenterY[i]);
    				for(j=0;j<TopX[i];j++)
    				{
    					glColor3f(0.0,0.5,0.0);
    					glVertex2f(ClusterX[i][j],ClusterY[i][j]);
    				}
    			}
    			else if(i==2)
    			{
    				glColor3f(0.0,0.0,1.0);
    				glVertex2f(CenterX[i],CenterY[i]);
    				for(j=0;j<TopX[i];j++)
    				{
    					glColor3f(0.0,0.0,0.5);
    					glVertex2f(ClusterX[i][j],ClusterY[i][j]);
    				}
    
    			}
    			else if(i==3)
    			{
    				glColor3f(1.0,1.0,1.0);
    				glVertex2f(CenterX[i],CenterY[i]);
    				for(j=0;j<TopX[i];j++)
    				{
    					glColor3f(0.8,0.8,0.8);
    					glVertex2f(ClusterX[i][j],ClusterY[i][j]);
    				}
    
    			}
    			else if(i==4)
    			{
    				glColor3f(1.0,1.0,0.0);
    				glVertex2f(CenterX[i],CenterY[i]);
    				for(j=0;j<TopX[i];j++)
    				{
    					glColor3f(0.5,0.5,0.0);
    					glVertex2f(ClusterX[i][j],ClusterY[i][j]);
    				}
    
    			}
    			else
    			{
    				glColor3f(1.0,0.0,1.0);
    				glVertex2f(CenterX[i],CenterY[i]);
    				for(j=0;j<TopX[i];j++)
    				{
    					glColor3f(0.5,0.0,0.5);
    					glVertex2f(ClusterX[i][j],ClusterY[i][j]);
    				}
    
    			}
    			
    		}
    		glEnd();
    		glFlush();
    }
    
    //初始化聚类的各种数据
    void InitData()
    {
        int i=0,j;
        int a,b;
        printf("请输入随机生成非重复的坐标点的个数： ");     
        scanf("%d",&N);
        printf("输入将要分几类： ");     
        scanf("%d",&K);    
        if(K>N)
        {
            exit(0);
        }
        CenterX=(double *)malloc(sizeof(double)*K);//为质心集合申请空间
    	CenterY=(double *)malloc(sizeof(double)*K);
        CenterIndexX=(int *)malloc(sizeof(int)*K);//为质心集合索引申请空间
    	CenterIndexY=(int *)malloc(sizeof(int)*K);
        CenterCopyX=(double *)malloc(sizeof(double)*K);//为质心集合副本申请空间
    	CenterCopyY=(double *)malloc(sizeof(double)*K);
        TopX=(int *)malloc(sizeof(int)*K); 
    	TopY=(int *)malloc(sizeof(int)*K);
        AllDataX=(double *)malloc(sizeof(double)*N);//为数据集合申请空间
    	AllDataY=(double *)malloc(sizeof(double)*N);
        ClusterX=(double **)malloc(sizeof(double *)*K);//为簇集合申请空间
    	ClusterY=(double **)malloc(sizeof(double *)*K);
        //初始化K个簇集合
        for(i=0;i<K;i++)
        {
            ClusterX[i]=(double *)malloc(sizeof(double)*N);
    		ClusterY[i]=(double *)malloc(sizeof(double)*N);
            TopX[i]=0;
    		TopY[i]=0;
        }
    
    	srand( (unsigned)time( NULL ) );
        for(i=0;i<N;i++)
        {
            a=rand()%10;
    		b=rand()%10;
    		for(j=0;j<i;j++)
    		{
    			if(AllDataX[j]==a&&AllDataY[j]==b)
    				break;
    		}
    		if(j>=i)
    		{
    			AllDataX[i]=a;
    			AllDataY[i]=b;
    		}
    		else
    		{
    			i--;
    		}
    		
        }
        InitCenter();//初始化质心集合      
        UpdateCluster();//初始化K个簇集合
         
    }
    
    void init()
    {
       glClearColor(1.0f , 1.0f , 1.0f , 1.0f);
       glClear(GL_COLOR_BUFFER_BIT);
       //glEnable(GL_POINT_SMOOTH);
    } 
    
    /*
    算法描述：
    K均值算法：
        给定类的个数K，将N个对象分到K个类中去，
        使得类内对象之间的相似性最大，而类之间的相似性最小。
    */
    
    int main(int argc, char **argv)
    {
        int Flag=1;//迭代标志，若为false,则迭代结束
        int i=0;
        InitData();//初始化数据      
        while(Flag)//开始迭代
         {
             UpdateCluster();//更新各个聚类
             UpdateCenter();//更新质心数组
             if(IsEqual(CenterX,CenterCopyX)&&IsEqual(CenterY,CenterCopyY))//如果本次迭代与前次的质心聚合相等，即已收敛，结束退出
             {
                 Flag=0;
             }
             else//否则将质心副本置为本次迭代得到的的质心集合
             {
                 CopyCenter();//将质心副本置为本次迭代得到的的质心集合
             }
         }
    	 Print();//输出结果
    	 glutInit(&argc, argv);  //初始化glut
         glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);    //设置显示属性为RGB颜色， 单缓冲
         glutInitWindowSize(1350,650);   //设置窗口大小
         glutInitWindowPosition(0,0);    //设置窗口位置
         glutCreateWindow("K均值聚类分析结果");     //生成窗口
    	 init();
    	 gluOrtho2D(-1,10,-1,10);
         glutDisplayFunc(&display);   //显示回调
         glutMainLoop();
         getchar();
         getchar();
         return 0;     
    }