#include <stdio.h>
#include <math.h>
#define TRUE 1
#define FALSE 0
int N;//數(shù)據(jù)個數(shù)
int K;//集合個數(shù)
int * CenterIndex;//初始化質(zhì)心數(shù)組的索引
double * Center;//質(zhì)心集合
double * CenterCopy;//質(zhì)心集合副本
double * AllData;//數(shù)據(jù)集合
double ** Cluster;//簇的集合
int * Top;//集合中元素的個數(shù)，也會用作棧處理
//隨機生成k個數(shù)x(0<=x<=n-1)作為起始的質(zhì)心集合
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個數(shù)
{
int a=rand()%n;
//判重
for(j=0;j<i;j++)
{
if(center[j]==a)//重復
{
break;
}
}
if(j>=i)//如果不重復，加入
{
center[i]=a;
}
else
{
i--;
//如果重復，本次重新隨機生成
}
}
}
//返回距離最小的質(zhì)心的序號
int GetIndex(double value,double * center)
{
int i=0;
int index=i;//最小的質(zhì)心序號
double min=fabs(value-center[i]);//距質(zhì)心最小距離
for(i=0;i<K;i++)
{
if(fabs(value-center[i])<min)//如果比當前距離還小，更新最小的質(zhì)心序號和距離值
{
index=i;
min=fabs(value-center[i]);
}
}
return index;
}
//拷貝質(zhì)心數(shù)組到副本
void CopyCenter()
{
int i=0;
for(i=0;i<K;i++)
{
CenterCopy[i]=Center[i];
}
}
//初始化質(zhì)心，隨機生成法
void InitCenter()
{
int i=0;
CreateRandomArray(N,K,CenterIndex);//產(chǎn)生隨機的K個<N的不同的序列
for(i=0;i<K;i++)
{
Center[i]=AllData[CenterIndex[i]];//將對應數(shù)據(jù)賦值給質(zhì)心數(shù)組
}
CopyCenter();//拷貝到質(zhì)心副本
}
//加入一個數(shù)據(jù)到一個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);//得到與當前數(shù)據(jù)最小的質(zhì)心索引
AddToCluster(tindex,AllData[i]); //加入到相應的集合中
}
}
//重新計算質(zhì)心集合，對每一簇集合中的元素加總求平均即可
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數(shù)組元素是否相等
int IsEqual(double * center1 ,double * center2)
{
int i;
for(i=0;i<K;i++)
{
if(fabs(center1[i]!=center2[i]))
{
return FALSE;
}
}
return TRUE;
}
//打印聚合結(jié)果
void Print()
{
int i,j;
printf("-------------------------------------- ");
for(i=0;i<K;i++)
{
printf("第%d組: 質(zhì)心（%f） ",i,Center[i]);
for(j=0;j<Top[i];j++)
{
printf("%f ",Cluster[i][j]);
}
}
}
//初始化聚類的各種數(shù)據(jù)
void InitData()
{
int i=0;
int a;
printf("輸入數(shù)據(jù)個數(shù)： ");
scanf("%d",&N);
printf("輸入簇個數(shù)： ");
scanf("%d",&K);
if(K>N)
{
exit(0);
}
Center=(double *)malloc(sizeof(double)*K);//為質(zhì)心集合申請空間
CenterIndex=(int *)malloc(sizeof(int)*K);//為質(zhì)心集合索引申請空間
CenterCopy=(double *)malloc(sizeof(double)*K);//為質(zhì)心集合副本申請空間
Top=(int *)malloc(sizeof(int)*K);
AllData=(double *)malloc(sizeof(double)*N);//為數(shù)據(jù)集合申請空間
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數(shù)據(jù)： ",N);
for(i=0;i<N;i++)
{
scanf("%d",&(a));
AllData[i]=a;
}
InitCenter();//初始化質(zhì)心集合
UpdateCluster();//初始化K個簇集合
}
/*
算法描述：
K均值算法：
給定類的個數(shù)K，將N個對象分到K個類中去，
使得類內(nèi)對象之間的相似性最大，而類之間的相似性最小。
*/
main()
{
int Flag=1;//迭代標志，若為false,則迭代結(jié)束
int i=0;
InitData();//初始化數(shù)據(jù)
while(Flag)//開始迭代
{
UpdateCluster();//更新各個聚類
UpdateCenter();//更新質(zhì)心數(shù)組
if(IsEqual(Center,CenterCopy))//如果本次迭代與前次的質(zhì)心聚合相等，即已收斂，結(jié)束退出
{
Flag=0;
}
else//否則將質(zhì)心副本置為本次迭代得到的的質(zhì)心集合
{
CopyCenter();//將質(zhì)心副本置為本次迭代得到的的質(zhì)心集合
}
}
Print();//輸出結(jié)果
getchar();
getchar();
}
本站僅提供存儲服務，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點擊舉報。
