1.cpp

这是针对一维K-means算法的实现

#include <stdio.h> 
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define TRUE   1
#define FALSE  0 
int N;    //数据个数
int K;    //集合个数
int * CenterIndex; //初始化质心数组的索引
float * Center;  //质心集合
float * CenterCopy; //质心集合副本
float * AllData; //数据集合
float ** Cluster; //簇的集合
int * Top;   //集合中元素的个数，也会用作栈处理
 
//随机生成k个数x(0<=x<=n-1)作为起始的质心集合中元素的ID
void CreateRandomArray(int n, int k, int * center)
{
    int i = 0, j;  
 int flag;
    /* 
 * Seed the random-number generator with current time so that
    * the numbers will be different every time we run.
    */
   srand( (unsigned)time( NULL ) );
    while (i<k)      //随机生成k个数
    {
        int randK = rand()%n;
  flag = FALSE;
       
        for (j=0; j<i; j++)   //判重
        {
            if(center[j] == randK) //重复
            {
             flag = TRUE;
                break;
            }
        }
        if(flag == FALSE)   //如果不重复，加入
        {
            center[i] = randK;
   i++;
        }
        else      //如果重复，本次重新随机生成
        {
        }
    }     
}
 
//返回距离最小的质心的序号
int GetIndex(float value, float * center)
{
    int i;
    int index = 0;      //最小的质心序号
    double min = fabs(value-center[0]); //距质心最小距离
   
 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;
    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, float value)
{
    Cluster[index][Top[index]++] = value; //这里同进栈操作
} 
//重新计算簇集合
void UpdateCluster()
{    
    int i=0;
    int tempIndex;
    //将所有的集合清空，即将TOP置0
    for (i=0; i<K; i++)
    {
        Top[i] = 0;
    }
    for (i=0; i<N; i++)
    {
        tempIndex = GetIndex(AllData[i], Center); //得到与当前数据最小的质心索引
        AddToCluster(tempIndex, AllData[i]);      //加入到相应的集合中 
    }
}
//重新计算质心集合，对每一簇集合中的元素加总求平均即可
void UpdateCenter()
{
    int i, j;
    double sum;
    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] = (float)sum/Top[i];//求其平均值
        }
    }
}
//判断2数组元素是否相等
int IsEqual(float * center1, float * 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("-------------------------------------- ");
    for (i=0; i<K; i++)
    {
         printf("\n第%d个聚类: 质心(%f)",i,Center[i]);
          for (j=0; j<Top[i]; j++)
          {
              printf("%f ",Cluster[i][j]);
          }           
    }     
}
//初始化聚类的各种数据
void InitData()
{
    int i=0;
    printf("输入数据个数: ");     
    scanf("%d",&N);
    printf("输入簇个数: ");     
    scanf("%d",&K); 
 
    if(K>N)
    {
        exit(0);
    }
    Center=(float *)malloc(sizeof(float)*K);//为质心集合申请空间
    CenterIndex=(int *)malloc(sizeof(int)*K);//为质心集合索引申请空间
    CenterCopy=(float *)malloc(sizeof(float)*K);//为质心集合副本申请空间
    Top=(int *)malloc(sizeof(int)*K); 
    AllData=(float *)malloc(sizeof(float)*N);//为数据集合申请空间
    Cluster=(float **)malloc(sizeof(float *)*K);//为簇集合申请空间
    //初始化K个簇集合
    for(i=0;i<K;i++)
    {
        Cluster[i]=(float *)malloc(sizeof(float)*N);
        Top[i]=0;
    }
    printf("输入%d数据:\n ",N);
    for(i=0;i<N;i++)
    {
        scanf("%f",&AllData[i]);
    }
    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();//输出结果
 getchar();
 getchar();
 
}