|
#include <stdio.h>
#include <math.h> #define TRUE 1 #define FALSE 0 int N;//數(shù)據(jù)個(gè)數(shù) int K;//集合個(gè)數(shù) int * CenterIndex;//初始化質(zhì)心數(shù)組的索引 double * Center;//質(zhì)心集合 double * CenterCopy;//質(zhì)心集合副本 double * AllData;//數(shù)據(jù)集合 double ** Cluster;//簇的集合 int * Top;//集合中元素的個(gè)數(shù)，也會用作棧處理 //隨機(jī)生成k個(gè)數(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)//隨機(jī)生成k個(gè)數(shù) { int a=rand()%n; //判重 for(j=0;j<i;j++) { if(center[j]==a)//重復(fù) { break; } } if(j>=i)//如果不重復(fù)，加入 { center[i]=a; } else { i--; //如果重復(fù)，本次重新隨機(jī)生成 } } } //返回距離最小的質(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)//如果比當(dāng)前距離還小，更新最小的質(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ì)心，隨機(jī)生成法 void InitCenter() { int i=0; CreateRandomArray(N,K,CenterIndex);//產(chǎn)生隨機(jī)的K個(gè)<N的不同的序列 for(i=0;i<K;i++) { Center[i]=AllData[CenterIndex[i]];//將對應(yīng)數(shù)據(jù)賦值給質(zhì)心數(shù)組 } CopyCenter();//拷貝到質(zhì)心副本 } //加入一個(gè)數(shù)據(jù)到一個(gè)Cluster[index]集合 void AddToCluster(int index,double value) { Cluster[index][Top[index]++]=value;//這里同進(jìn)棧操作 } //重新計(jì)算簇集合
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);//得到與當(dāng)前數(shù)據(jù)最小的質(zhì)心索引 AddToCluster(tindex,AllData[i]); //加入到相應(yīng)的集合中 } } //重新計(jì)算質(zhì)心集合，對每一簇集合中的元素加總求平均即可 void UpdateCenter() { int i=0; int j=0; double sum=0; for(i=0;i<K;i++) { sum=0; //計(jì)算簇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ù)個(gè)數(shù)： "); scanf("%d",&N); printf("輸入簇個(gè)數(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個(gè)簇集合 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個(gè)簇集合 } /* 算法描述： K均值算法： 給定類的個(gè)數(shù)K，將N個(gè)對象分到K個(gè)類中去， 使得類內(nèi)對象之間的相似性最大，而類之間的相似性最小。 */ main() { int Flag=1;//迭代標(biāo)志，若為false,則迭代結(jié)束 int i=0; InitData();//初始化數(shù)據(jù) while(Flag)//開始迭代 { UpdateCluster();//更新各個(gè)聚類 UpdateCenter();//更新質(zhì)心數(shù)組 if(IsEqual(Center,CenterCopy))//如果本次迭代與前次的質(zhì)心聚合相等，即已收斂，結(jié)束退出 { Flag=0; } else//否則將質(zhì)心副本置為本次迭代得到的的質(zhì)心集合 { CopyCenter();//將質(zhì)心副本置為本次迭代得到的的質(zhì)心集合 } } Print();//輸出結(jié)果 getchar(); getchar(); } 本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處：http://blog.csdn.net/ywywcy/archive/2007/07/25/1706596.aspx
|
|
|
