聚类算法的设计与实现

 常用的聚类算法有K-Means（K均值聚类算法）、DBSCAN和OPTICS等。

K均值聚类算法的相关信息自行从网上获取。简单介绍如下：

K-Means算法实质上是一种将聚类视为密度估计问题的概率方法。k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。

K-Means 算法的步骤：

（1）选K个初始聚类中心，z1(1)，z2(1)，…，zK(1)，其中括号内的序号为寻找聚类中心的迭代运算的次序号。聚类中心的向量值可任意设定，例如可选开始的K个模式样本的向量值作为初始聚类中心。

（2）逐个将需分类的模式样本{x}按最小距离准则分配给K个聚类中心中的某一个zj(1)。假设i=j时，其中k为迭代运算的次序号，第一次迭代k=1，Sj表示第j个聚类，其聚类中心为zj。

（3）计算各个聚类中心的新的向量值，zj(k+1)，j=1,2,…,K。求各聚类域中所包含样本的均值向量；其中Nj为第j个聚类域Sj中所包含的样本个数。以均值向量作为新的聚类中心，可使如下聚类准则函数最小：在这一步中要分别计算K个聚类中的样本均值向量，所以称之为K-均值算法。

（4）若j=1,2,…,K，则返回第二步，将模式样本逐个重新分类，重复迭代运算；

若本次迭代与前次的质心聚合相等，即已收敛，计算结束。

实现代码（参考自http://blog.csdn.net/blue4689/article/details/6629488）：

#include <stdio.h> 
#include <math.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;//集合中元素的个数，也会用作栈处理

 
//随机生成k个数x(0<=x<=n-1)作为起始的质心集合
void CreateRandomArray(int n, int k,int * center)
{
    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();//拷贝到质心副本
}
//加入一个数据到一个Cluster[index]集合
void AddToCluster(int index,double value)
{
    Cluster[index][Top[index]++]=value;//这里同进栈操作
} 

//重新计算簇集合
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]); //加入到相应的集合中 
    }
}
//重新计算质心集合，对每一簇集合中的元素加总求平均即可
void UpdateCenter()
{
    int i=0;
    int j=0;
    double sum=0;
    for(i=0;i<K;i++)
    {
        sum=0;    
        //计算簇i的元素和
        for(j=0;j<Top[i];j++)
         {
             sum+=Cluster[i][j];
         }
        if(Top[i]>0)//如果该簇元素不为空
        {
           Center[i]=sum/Top[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;
}
//打印聚合结果
void Print()
{
    int i,j;
    printf("-------------------------------------- \n");
    for(i=0;i<K;i++)
    {
         printf("第%d组: 质心(%f)\t",i,Center[i]);
          for(j=0;j<Top[i];j++)
          {
              printf("%f\t",Cluster[i][j]);
          }  
          printf("\n");
    }     
}
//初始化聚类的各种数据
void InitData()
{
    int i=0;
    int a;
    printf("输入数据个数： ");     
    scanf("%d",&N);
    printf("输入簇个数： ");     
    scanf("%d",&K);    
    if(K>N)
    {
        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);//为簇集合申请空间
    //初始化K个簇集合
    for(i=0;i<K;i++)
    {
        Cluster[i]=(double *)malloc(sizeof(double)*N);
        Top[i]=0;
    }
    printf("输入%d数据：\n",N);
    for(i=0;i<N;i++)
    {
        scanf("%d",&(a));
        AllData[i]=a;
    }
    InitCenter();//初始化质心集合      
    UpdateCluster();//初始化K个簇集合
     
}
/*
算法描述：
K均值算法：
    给定类的个数K，将N个对象分到K个类中去，
    使得类内对象之间的相似性最大，而类之间的相似性最小。
*/
main()
{
    int Flag=1;//迭代标志，若为false,则迭代结束
    int i=0;
     InitData();//初始化数据      
     while(Flag)//开始迭代
     {
         UpdateCluster();//更新各个聚类
         UpdateCenter();//更新质心数组
         if(IsEqual(Center,CenterCopy))//如果本次迭代与前次的质心聚合相等，即已收敛，结束退出
         {
             Flag=0;
         }
         else//否则将质心副本置为本次迭代得到的的质心集合
         {
             CopyCenter();//将质心副本置为本次迭代得到的的质心集合
         }
     }
     Print();//输出结果
}