(聚類)k平均算法實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)挖掘?qū)嶒?yàn)報(bào)告專業(yè)班級計(jì)算機(jī)2班實(shí)驗(yàn)地點(diǎn)邱天生202學(xué)生學(xué)號101304057指導(dǎo)教師郭淼霞學(xué)生姓名周杰實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)2 K平均算法（Kmeans）實(shí)驗(yàn)類別操作性（） 驗(yàn)證性（） 設(shè)計(jì)性（） 綜合性（ ） 其它（ ）實(shí)驗(yàn)?zāi)康募耙?.進(jìn)一步熟悉高級語言編程;2掌握使用K平均算法的方法；成 績 評 定 表類 別評 分 標(biāo) 準(zhǔn)分值得分合 計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律主動完成實(shí)驗(yàn)設(shè)計(jì)任務(wù)30分程序代碼比較規(guī)范、基本正確功能達(dá)到實(shí)驗(yàn)要求30分實(shí)驗(yàn)報(bào)告及時(shí)遞交、填寫規(guī)范內(nèi)容完整、體現(xiàn)收獲40分說明： 評閱教師： 日 期： 2013 年 5 月 28 日推薦精選實(shí) 驗(yàn) 內(nèi) 容1. 算法思想（1）

2、從 n個(gè)數(shù)據(jù)對象任意選擇 k 個(gè)對象作為初始聚類中心； （2） 循環(huán)（3）到（4）直到每個(gè)聚類不再發(fā)生變化為止； （3） 根據(jù)每個(gè)聚類對象的均值（中心對象），計(jì)算每個(gè)對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分； （4） 重新計(jì)算每個(gè)（有變化）聚類的均值（中心對象）。 k-means 算法接受輸入量 k ；然后將n個(gè)數(shù)據(jù)對象劃分為 k個(gè)聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個(gè)“中心對象”（引力中心）來進(jìn)行計(jì)算的。 k-means 算法的工作過程說明如下：首先從n個(gè)數(shù)據(jù)對象任意選擇 k

3、個(gè)對象作為初始聚類中心；而對于所剩下其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計(jì)算每個(gè)所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測度函數(shù). k個(gè)聚類具有以下特點(diǎn)：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。2 源程序使用的數(shù)據(jù)結(jié)構(gòu)int N;/數(shù)據(jù)個(gè)數(shù)int K;/集合個(gè)數(shù)int * CenterIndex;/初始化質(zhì)心數(shù)組的索引double * Center;/質(zhì)心集合double * CenterCopy;/質(zhì)心集合副本double * A

4、llData;/數(shù)據(jù)集合double * Cluster;/簇的集合#include<time.h>int * Top;/集合中元素的個(gè)數(shù)，也會用作棧處理3.源程序#include<stdlib.h> #include <stdio.h> #include <math.h>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;/

5、簇的集合#include<time.h>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(centerj=a)/重復(fù) break; if(j>=i)/如果不重復(fù)

6、，加入 centeri=a; else i-;/如果重復(fù)，本次重新隨機(jī)生成 /返回距離最小的質(zhì)心的序號int GetIndex(double value,double * center) int i=0; int index=i;/最小的質(zhì)心序號 double min=fabs(value-centeri);/距質(zhì)心最小距離 for(i=0;i<K;i+) if(fabs(value-centeri)<min)/如果比當(dāng)前距離還小，更新最小的質(zhì)心序號和距離值 index=i; min=fabs(value-centeri); return index; void CopyCente

7、r()/拷貝質(zhì)心數(shù)組到副本 int i=0; for(i=0;i<K;i+) CenterCopyi=Centeri;void InitCenter()/初始化質(zhì)心，隨機(jī)生成法 int i=0; CreateRandomArray(N,K,CenterIndex);/產(chǎn)生隨機(jī)的K個(gè)<N的不同的序列 for(i=0;i<K;i+)推薦精選 Centeri=AllDataCenterIndexi;/將對應(yīng)數(shù)據(jù)賦值給質(zhì)心數(shù)組/ printf("%f ",Centeri); /測試用 CopyCenter();/拷貝到質(zhì)心副本void AddToCluster(i

8、nt index,double value)/加入一個(gè)數(shù)據(jù)到一個(gè)Clusterindex集合 ClusterindexTopindex+=value;/這里同進(jìn)棧操作 /重新計(jì)算簇集合void UpdateCluster() int i=0; int tindex; /將所有的集合清空，即將TOP置0 for(i=0;i<K;i+) Topi=0; for(i=0;i<N;i+) tindex=GetIndex(AllDatai,Center);/得到與當(dāng)前數(shù)據(jù)最小的質(zhì)心索引 AddToCluster(tindex,AllDatai); /加入到相應(yīng)的集合中 void Update

9、Center()/重新計(jì)算質(zhì)心集合，對每一簇集合中的元素加總求平均即可 int i=0; int j=0; double sum=0; for(i=0;i<K;i+) sum=0; /計(jì)算簇i的元素和 for(j=0;j<Topi;j+) sum+=Clusterij; if(Topi>0)/如果該簇元素不為空 Centeri=sum/Topi;/求其平均值 bool IsEqual(double * center1 ,double * center2)/判斷2數(shù)組元素是否相等 int i; for(i=0;i<K;i+) if(fabs(center1i!=cente

10、r2i) return false; 推薦精選 return true;void Print()/打印聚合結(jié)果 int i,j; printf("n- "); for(i=0;i<K;i+) printf("n第%d組: 質(zhì)心（%f） :n",i+1,Centeri); for(j=0;j<Topi;j+) printf("%f ",Clusterij); void InitData()/初始化聚類的各種數(shù)據(jù) int i=0; int a; printf("輸入數(shù)據(jù)個(gè)數(shù)： "); scanf("

11、;%d",&N); printf("輸入簇個(gè)數(shù)： "); scanf("%d",&K); if(K>N) exit(0); Center=new doubleK; /為質(zhì)心集合申請空間 CenterIndex=new intK;/為質(zhì)心集合索引申請空間 CenterCopy=new doubleK; /為質(zhì)心集合副本申請空間 Top=new intK; AllData=new doubleN; /為數(shù)據(jù)集合申請空間 Cluster=(double *)malloc(sizeof(double *)*K);/為簇集合申請空間

12、 /初始化K個(gè)簇集合 for(i=0;i<K;i+) Clusteri=(double *)malloc(sizeof(double)*N); Topi=0; printf("輸入%d數(shù)據(jù)： ",N); for(i=0;i<N;i+)推薦精選 scanf("%d",&(a); AllDatai=a; InitCenter();/初始化質(zhì)心集合 UpdateCluster();/初始化K個(gè)簇集合 void free()/釋放申請的空間delete Center;delete CenterIndex;delete CenterCopy;d

13、elete Top;delete AllData;free(Cluster);/*算法描述：K均值算法： 給定類的個(gè)數(shù)K，將N個(gè)對象分到K個(gè)類中去， 使得類內(nèi)對象之間的相似性最大，而類之間的相似性最小。*/int main() int Flag=1;/迭代標(biāo)志，若為false,則迭代結(jié)束 int i=0; InitData();/初始化數(shù)據(jù) /* for(int j=0;j<K;j+)/測試用 printf("%f ",Centerj);*/ while(Flag)/開始迭代 UpdateCluster();/更新各個(gè)聚類 UpdateCenter();/更新質(zhì)心數(shù)組 if(IsEqual(Center,CenterCopy)/如果本次迭代與前次的質(zhì)心聚合相等，即已收斂，結(jié)束退出 Flag=0; else/否則將質(zhì)心副本置為本次迭代得到的的質(zhì)心集合 CopyCenter();/將質(zhì)心副本置為本次迭代得到的的質(zhì)心集合 /* i+; printf("n%d times",i); /測試用 for(int j=0;j<K;j+) printf("%f ",Centerj);*/推薦精選 Print();/輸出結(jié)果 free(); getchar(); return 0;實(shí) 驗(yàn) 總 結(jié)在