k均值聚類報告

1、K-均值聚類算法報告摘要K-均值是聚類方法中長用的一種劃分方法，有很多優(yōu)點，本文主要對K-均值是聚類方法的產(chǎn)生，工作原理，一般步驟，以及它的源碼進行簡單的介紹，了解K-均值是聚類！（一）課題名稱：K-均值聚類(K-means clustering)（二）課題分析： J.B.MacQueen 在 1967 年提出的K-means算法22到目前為止用于科學和工業(yè)應(yīng)用的諸多聚類算法中一種極有影響的技術(shù)。它是聚類方法中一個基本的劃分方法，常常采用誤差平方和準則函數(shù)作為聚類準則函數(shù)，誤差平方和準則函數(shù)定義為：K-means 算法的特點采用兩階段反復循環(huán)過程算法，結(jié)束的條件是不再有數(shù)據(jù)元素被重新分配： 指

2、定聚類，即指定數(shù)據(jù) 到某一個聚類，使得它與這個聚類中心的距離比它到其它聚類中心的距離要近。 修改聚類中心。優(yōu)點：本算法確定的K 個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區(qū)別明顯時，效果較好。對于處理大數(shù)據(jù)集，這個算法是相對可伸縮和高效的，計算的復雜度為O(NKt)，其中N是數(shù)據(jù)對象的數(shù)目，t是迭代的次數(shù)。一般來說，KN，tN 。動態(tài)聚類方法是模式識別中一種普遍采用的方法，它具有以下3個要點： 1：選定某種距離度量作為樣本間的相似性度量2：確定某個評價聚類結(jié)果質(zhì)量的準則函數(shù)3：給定某個初始分類，然后用迭代算法找出使準則函數(shù)取極值的最好的聚類結(jié)果處理流程：（1） 從 n個數(shù)據(jù)對象任意選

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

4、下其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標準測度函數(shù)開始收斂為止。一般都采用均方差作為標準測度函數(shù). k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。（三）總體檢索思路：利用goole，百度，搜狗等搜索引擎及校內(nèi)的一些數(shù)據(jù)庫進行相關(guān)內(nèi)容的檢索。主要檢索內(nèi)容為K-均值聚類算法的工作原理，一般步驟，源碼。（四）檢索過程記錄：關(guān)鍵詞：K-均值聚類算法搜索引擎：百度檢索內(nèi)容：K-均值聚類算法工作原理K-均值聚類算法的一般步驟K-均

5、值聚類算法的源碼中文數(shù)據(jù)庫檢索：中國知網(wǎng)（/）維普網(wǎng) （/）萬方 （/）學科范圍：信息技術(shù)檢索詞：K-均值聚類算法（五）檢索結(jié)果分析：1. K-均值聚類算法的工作原理：K-means算法的工作原理：算法首先隨機從數(shù)據(jù)集中選取 K個點作為初始聚類中心，然后計算各個樣本到聚類中的距離，把樣本歸到離它最近的那個聚類中心所在的類。計算新形成的每一個聚類的數(shù)據(jù)對象的平均值來得到新的聚類中心，如果相鄰兩次的聚類中心沒有任何變化，說明樣本調(diào)整結(jié)束，聚類準則函數(shù) 已經(jīng)收斂。本算法的

6、一個特點是在每次迭代中都要考察每個樣本的分類是否正確。若不正確，就要調(diào)整，在全部樣本調(diào)整完后，再修改聚類中心，進入下一次迭代。如果在一次迭代算法中，所有的樣本被正確分類，則不會有調(diào)整，聚類中心也不會有任何變化，這標志著 已經(jīng)收斂，因此算法結(jié)束。2.K-means聚類算法的一般步驟：處理流程：（1） 從 n個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心；（2） 循環(huán)（3）到（4）直到每個聚類不再發(fā)生變化為止；（3） 根據(jù)每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進行劃分；（4） 重新計算每個（有變化）聚類的均值（中心對象）3.K-均值聚類算法代

7、碼#include #include #define TRUE 1#define FALSE 0int 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=

8、0;int j=0;srand( (unsigned)time( NULL ) );for( i=0;ik;+i)/隨機生成k個數(shù)int a=rand()%n;/判重for(j=0;j=i)/如果不重復，加入centeri=a;elsei-;/如果重復，本次重新隨機生成/返回距離最小的質(zhì)心的序號int GetIndex(double value,double * center)int i=0;int index=i;/最小的質(zhì)心序號double min=fabs(value-centeri);/距質(zhì)心最小距離for(i=0;iK;i+)if(fabs(value-centeri)min)/如果

9、比當前距離還小，更新最小的質(zhì)心序號和距離值index=i;min=fabs(value-centeri);return index;/拷貝質(zhì)心數(shù)組到副本void CopyCenter()int i=0;for(i=0;iK;i+)CenterCopyi=Centeri;/初始化質(zhì)心，隨機生成法void InitCenter()int i=0;CreateRandomArray(N,K,CenterIndex);/產(chǎn)生隨機的K個N的不同的序列 for(i=0;iK;i+)Centeri=AllDataCenterIndexi;/將對應(yīng)數(shù)據(jù)賦值給質(zhì)心數(shù)組 CopyCenter();/拷貝到質(zhì)心副本

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

11、對每一簇集合中的元素加總求平均即可void UpdateCenter()int i=0;int j=0;double sum=0;for(i=0;iK;i+)sum=0;/計算簇i的元素和for(j=0;j0)/如果該簇元素不為空Centeri=sum/Topi;/求其平均值/判斷2數(shù)組元素是否相等int IsEqual(double * center1 ,double * center2)int i;for(i=0;iK;i+)if(fabs(center1i!=center2i)return FALSE;return TRUE;/打印聚合結(jié)果void Print()int i,j;prin

12、tf(- );for(i=0;iK;i+)printf(第%d組: 質(zhì)心（%f） ,i,Centeri);for(j=0;jN)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(sizeo

13、f(double)*N);/為數(shù)據(jù)集合申請空間 Cluster=(double *)malloc(sizeof(double *)*K);/為簇集合申請空間 /初始化K個簇集合for(i=0;iK;i+)Clusteri=(double *)malloc(sizeof(double)*N);Topi=0;printf(輸入%d數(shù)據(jù)：,N);for(i=0;iN;i+)scanf(%d,&(a);AllDatai=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é)果ge