keans.c

C语言的C均值聚类

#include <stdio.h> 
#include <math.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
#define TRUE            1
#define FALSE           0
//数据个数	//集合个数
int N;		int K;
//质心数组的索引  //质心集合      //质心集合副本      //数据集合       //簇的集合
int * CenterIndex;double * Center;double * CenterCopy;double * AllData;double ** Cluster;
int * Top;//集合中元素的个数，也会用作栈处理

void CreateRandomArray(int n, int k,int * center)//随机生成k个数x(0<=x<=n-1)作为起始的质心集合
{
	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(center[j]==a){break;}}//重复
        if(j>=i){center[i]=a;}else{i--;}//如果不重复，加入;如果重复，本次重新随机生成
    }     
}

int GetIndex(double value,double * center)//返回距离最小的质心的序号
{
    int i=0;int index=i;//最小的质心序号
    double min=fabs(value-center[i]);//距质心最小距离
    for(i=0;i<K;i++)
    {
        if(fabs(value-center[i])<min){index=i;min=fabs(value-center[i]);}
		//如果比当前距离还小，更新最小的质心序号和距离值
    }
    return index;
}

void CopyCenter()//拷贝质心数组到副本
{
    int i=0;for(i=0;i<K;i++){CenterCopy[i]=Center[i];}
}

void InitCenter()//初始化质心，随机生成法
{
    int i=0;
    CreateRandomArray(N,K,CenterIndex);//产生随机的K个<N的不同的序列
    for(i=0;i<K;i++){Center[i]=AllData[CenterIndex[i]];}//将对应数据赋值给质心数组
    CopyCenter();//拷贝到质心副本
}

void AddToCluster(int index,double value)//加入一个数据到一个Cluster[index]集合
{
    Cluster[index][Top[index]++]=value;//这里同进栈操作
} 


void UpdateCluster()//重新计算簇集合
{    
    int i=0;int tindex;
    for(i=0;i<K;i++){Top[i]=0;}//将所有的集合清空，即将TOP置0
    for(i=0;i<N;i++)
    {
        tindex=GetIndex(AllData[i],Center);//得到与当前数据最小的质心索引
        AddToCluster(tindex,AllData[i]);//加入到相应的集合中 
    }
}

void UpdateCenter()//重新计算质心集合，对每一簇集合中的元素加总求平均即可
{
    int i=0;int j=0;double sum=0;
    for(i=0;i<K;i++)
    {
        sum=0;
        for(j=0;j<Top[i];j++){sum+=Cluster[i][j];}//计算簇i的元素和
        if(Top[i]>0){Center[i]=sum/Top[i];}//如果该簇元素不为空,求其平均值
    }
}

int IsEqual(double * center1 ,double * center2)//判断2数组元素是否相等
{
    int i;
    for(i=0;i<K;i++){if(fabs(center1[i]!=center2[i])){return FALSE;}}
    return TRUE;
}

void Print()//打印聚合结果
{
    int i,j;printf("--------------------------------------\n");
    for(i=0;i<K;i++)
    {
         printf("第%d组: 质心（%f） ",i,Center[i]);
         for(j=0;j<Top[i];j++){printf("%f ",Cluster[i][j]);}
		 printf("\n");
    }     
}

void InitData()//初始化聚类的各种数据
{
    int i=0;int a;
    printf("输入数据个数： ");scanf("%d",&N);
    printf("输入簇个数： ");scanf("%d",&K);    
    if(K>N){printf("错误：簇个数 > 数据个数");getchar();getchar();exit(0);}
    Center=(double *)malloc(sizeof(double)*K);//为质心集合申请空间
    CenterIndex=(int *)malloc(sizeof(int)*K);//为质心集合索引申请空间
    CenterCopy=(double *)malloc(sizeof(double)*K);//为质心集合副本申请空间
    Top=(int *)malloc(sizeof(int)*K); 
    AllData=(double *)malloc(sizeof(double)*N);//为数据集合申请空间
    Cluster=(double **)malloc(sizeof(double *)*K);//为簇集合申请空间
    for(i=0;i<K;i++){Cluster[i]=(double *)malloc(sizeof(double)*N);Top[i]=0;}//初始化K个簇集合
    printf("输入%d数据： ",N);for(i=0;i<N;i++){scanf("%d",&(a));AllData[i]=a;}
    InitCenter();//初始化质心集合      
    UpdateCluster();//初始化K个簇集合
}
/*
K均值算法：
    给定类的个数K，将N个对象分到K个类中去，
    使得类内对象之间的相似性最大，而类之间的相似性最小。
*/
main()
{
    int i=0;int Flag=1;//迭代标志，若为0，则迭代结束
	InitData();//初始化数据    
	while(Flag)//开始迭代
    {
        UpdateCluster();UpdateCenter();//更新各个聚类，更新质心数组
        if(IsEqual(Center,CenterCopy)){Flag=0;}else{CopyCenter();}
		//如果本次迭代与前次的质心聚合相等，结束循环；否则将质心副本置为本次迭代得到的的质心集合
    }
    Print();getchar();getchar();//输出结果
}