数组k均值.cpp

不使用欧式距离

#include <stdio.h> 
#include <math.h>
#include<stdlib.h>
#include<time.h>
#define N 5//一共要比较几个元组
#define K 2//要分成的簇
#define A 6//每个元组中的元素个数
double alldata[N][A]={{1,2,2,4,5,6},{6,7,2,4,5,6},{7,2,9,4,5,4},{1,2,4,6,5,9},{4,2,2,7,6,8}};
double center[K][A];
double centercopy[K][A]; 
double  Cluster[K][N][A];//假想簇的集合。第一维是簇，第二维是簇的第几个，第三维开始各个序列的元素
int Top[K];//集合中元素的个数，也会用作栈处理,TOP只是一个标示某个簇里有多少个元素用的，没有必要加维


 int IsEqual(double * center1 ,double * center2)//判断两个数组是否相同,我传过来的是两个指向数组的指针
{
    int i;
    for(i=0;i<A;i++)
    {
         if(center1[i]!=center2[i])
         {
             return 0;
         }
    }
    return 1;
}
void add(double * center1 ,double * center2)//拷贝数组形成质心，传的参数同上

{int i;
    for(i=0;i<A;i++)
    {
		center1[i]=center2[i];}
}
 void CopyCenter()
{
    int i=0;
	int j=0;
    for(i=0;i<K;i++)
		for(j=0;j<A;j++)
    {
        centercopy[i][j]=center[i][j];
    }
}//把质心拷贝出来
        
void InitCenter(int n, int k,double  center[][A])
{
    int i=0;
    int j=0;    
    srand( (unsigned)time( NULL ) );
    for( i=0;i<k;++i)//随机生成k个数
    {
        int a=rand()%n;
        //判重
        for(j=0;j<i;j++)
        {
            if((IsEqual(center[j],alldata[a])))//重复

            {
                break;
            }
        }
        if(j>=i)//如果不重复，加入
        {
            add(center[j],alldata[a]);
        }
        else
        {
            i--;
            //如果重复，本次重新随机生成
        }
    } 
	CopyCenter();
	
}

double rela(double *str1 ,double * str2)//两个数组计算相关性公式,程序运行没错，计算也没有错误，应该是这个公式貌似理解有错误。
{
	int i=0;
	double sum1=0;
	double sum2=0;
	double sum3=0;
	double sum4=0;
	double sum5=0;
	double avg1;
	double avg2;
	double res;
	for(i=0;i<A;i++)
	{//sum1=str1[i]*str2[i]+sum1;
     sum2=str1[i]+sum2;
     sum3=str2[i]+sum3;
	}
     avg1=sum2/A;
	 avg2=sum3/A;
	 
   for(i=0;i<A;i++)
   { sum1=(str1[i]-avg1)*(str2[i]-avg2)+sum1;
     sum4= (str1[i]-avg1)*(str1[i]-avg1)+sum4;
     sum5= (str2[i]-avg2)*(str2[i]-avg2)+sum5;
	}
   
res=sum1/((sqrt(sum4))*(sqrt(sum5)));


return res;
}
int GetIndex(double *value,double center[][A])
{
    int i=0;
    int index=i;//最小的质心序号

    double max=rela(value,center[i]);//跟此元组最相似的质心
    for(i=0;i<K;i++)
    {
        if((rela(value,center[i]))>max)//如果比当前还相似，更新质心编号
        {
             index=i;
             max=rela(value,center[i]);
        }
    }
	//printf("%f\n",max);
    return index;
	
}
void AddToCluster(int index,double *value)//测试
{   int j=0;
    for(j=0;j<A;j++)
    Cluster[index][Top[index]][j]=value[j];//这里同进栈操作
    Top[index]++;
} 
void UpdateCluster()
{    
    int i=0;
    int tindex;
    //将所有的集合清空，即将TOP置0
    for(i=0;i<K;i++)
    {
        Top[i]=0;
    }
    for(i=0;i<N;i++)
    {
        tindex=GetIndex(alldata[i],center);//得到与当前数据最小的质心索引
        AddToCluster(tindex,alldata[i]);        //加入到相应的集合中 ，这块的错。。。NND
    }
}




void UpdateCenter()//已测试
{
    int i=0;
    int j=0;
	int n=0;
    double sum=0;
    for(i=0;i<K;i++)
    {
           
        //计算簇i的元素和
		for(n=0;n<A;n++)
		{ sum=0; 
			for(j=0;j<Top[i];j++)
			
         {
             sum+=Cluster[i][j][n];//循环掉个个
         }
        if(Top[i]>0)//如果该簇元素不为空
        {
           center[i][n]=sum/Top[i];//求其平均值
        }
		}
    }
}
void Print()//已测试
{
    int i,j,n;
	
    for(i=0;i<K;i++)
	{
		 printf("第%d组: 质心:(",i);
   		  for(j=0;j<A;j++)
          printf("%f,",center[i][j]);
		  printf(")\n");
	}
    printf("--------------------------------------crazy------------------------------------");
    for(i=0;i<K;i++)
    {
		printf("第%d组: {",i);
          for(j=0;j<Top[i];j++)
		  {
			  printf("{");
			   for(n=0;n<A;n++) 
          {
              printf("%f,",Cluster[i][j][n]);
          }
			   printf("},\n");
		  }
		   printf("}\n");
    }     
}
int IsEqualCenter(double a[][A],double b[][A])//比较质心的二维数组是否相等，测试通过


{   int i;
    int j;
	for(i=0;i<K;i++)
	{	for(j=0;j<A;j++)
		if(a[i][j]!=b[i][j])
	          break;
		
      if(j<A)
	  return 0;
		}
return 1;
}
void main()
{  
	int Flag=1;//迭代标志，若为false,则迭代结束
    int i=0;
	InitCenter(N, K,center);
	
    UpdateCluster();
	
    	   while(Flag)//开始迭代
     {
         UpdateCluster();//更新各个聚类
         UpdateCenter();//更新质心数组
         if(IsEqualCenter(center,centercopy))//如果本次迭代与前次的质心聚合相等，即已收敛，结束退出
         {
             Flag=0;
         }
         else//否则将质心副本置为本次迭代得到的的质心集合
         {
            CopyCenter();//将质心副本置为本次迭代得到的的质心集合
         }
     }

     Print();//输出结果
    

    
}