模糊C均值聚類算法的實現(xiàn)

1、 模糊C均值聚類算法的實現(xiàn)研究背景 聚類分析是多元統(tǒng)計分析的一種，也是無監(jiān)督模式識別的一個重要分支，在模式分類 圖像處理和模糊規(guī)則處理等眾多領(lǐng)域中獲得最廣泛的應(yīng)用。它把一個沒有類別標記的樣本按照某種準則劃分為若干子集，使相似的樣本盡可能歸于一類，而把不相似的樣本劃分到不同的類中。硬聚類把每個待識別的對象嚴格的劃分某類中，具有非此即彼的性質(zhì)，而模糊聚類建立了樣本對類別的不確定描述，更能客觀的反應(yīng)客觀世界，從而成為聚類分析的主流。 模糊聚類算法是一種基于函數(shù)最優(yōu)方法的聚類算法，使用微積分計算技術(shù)求最優(yōu)代價函數(shù)，在基于概率算法的聚類方法中將使用概率密度函數(shù)，為此要假定合適的模型，模糊聚類算法的向量可

2、以同時屬于多個聚類，從而擺脫上述問題。 模糊聚類分析算法大致可分為三類 1）分類數(shù)不定，根據(jù)不同要求對事物進行動態(tài)聚類，此類方法是基于模糊等價矩陣聚類的，稱為模糊等價矩陣動態(tài)聚類分析法。 2）分類數(shù)給定，尋找出對事物的最佳分析方案，此類方法是基于目標函數(shù)聚類的，稱為模糊C均值聚類。3）在攝動有意義的情況下，根據(jù)模糊相似矩陣聚類，此類方法稱為基于攝動的模糊聚類分析法我所學習的是模糊C均值聚類算法，要學習模糊C均值聚類算法要先了解慮屬度的含義，隸屬度函數(shù)是表示一個對象x隸屬于集合A的程度的函數(shù)，通常記做A(x)，其自變量范圍是所有可能屬于集合A的對象（即集合A所在空間中的所有點），取值范圍是0,1

3、，即0=A(x)1。對于m，它是一個控制算法的柔性的參數(shù)，如果m過大，則聚類效果會很次，而如果m過小則算法會接近HCM聚類算法。算法的輸出是C個聚類中心點向量和C*N的一個模糊劃分矩陣，這個矩陣表示的是每個樣本點屬于每個類的隸屬度。根據(jù)這個劃分矩陣按照模糊集合中的最大隸屬原則就能夠確定每個樣本點歸為哪個類。聚類中心表示的是每個類的平均特征，可以認為是這個類的代表點。從算法的推導過程中我們不難看出，算法對于滿足正態(tài)分布的數(shù)據(jù)聚類效果會很好，另外，算法對孤立點是敏感的。聚類算法是一種比較新的技術(shù)，基于曾次的聚類算法文獻中最早出現(xiàn)的Single-Linkage層次聚類算法是1957年在Lloyd的文

4、章中最早出現(xiàn)的，之后MacQueen獨立提出了經(jīng)典的模糊C均值聚類算法，F(xiàn)CM算法中模糊劃分的概念最早起源于Ruspini的文章中，但關(guān)于FCM的算法的詳細的分析與改進則是由Dunn和Bezdek完成的。模糊c均值聚類算法因算法簡單收斂速度快且能處理大數(shù)據(jù)集，解決問題范圍廣，易于應(yīng)用計算機實現(xiàn)等特點受到了越來越多人的關(guān)注，并應(yīng)用于各個領(lǐng)域。算法描述模糊C均值聚類算法的步驟還是比較簡單的，模糊C均值聚類（FCM），即眾所周知的模糊ISODATA，是用隸屬度確定每個數(shù)據(jù)點屬于某個聚類的程度的一種聚類算法。1973年，Bezdek提出了該算法，作為早期硬C均值聚類（HCM）方法的一種改進。FCM把n

5、個向量xi（i=1,2,n）分為c個模糊組，并求每組的聚類中心，使得非相似性指標的價值函數(shù)達到最小。FCM與HCM的主要區(qū)別在于FCM用模糊劃分，使得每個給定數(shù)據(jù)點用值在0，1間的隸屬度來確定其屬于各個組的程度。與引入模糊劃分相適應(yīng)，隸屬矩陣U允許有取值在0，1間的元素。不過，加上歸一化規(guī)定，一個數(shù)據(jù)集的隸屬度的和總等于1： (6.9)那么，F(xiàn)CM的價值函數(shù)（或目標函數(shù)）就是式（6.2）的一般化形式：， (6.10)這里uij介于0，1間；ci為模糊組I的聚類中心，dij=|ci-xj|為第I個聚類中心與第j個數(shù)據(jù)點間的歐幾里德距離；且是一個加權(quán)指數(shù)。構(gòu)造如下新的目標函數(shù)，可求得使（6.10）

6、式達到最小值的必要條件： (6.11)這里lj，j=1到n，是（6.9）式的n個約束式的拉格朗日乘子。對所有輸入?yún)⒘壳髮?，使式?.10）達到最小的必要條件為： (6.12)和 (6.13)由上述兩個必要條件，模糊C均值聚類算法是一個簡單的迭代過程。在批處理方式運行時，F(xiàn)CM用下列步驟確定聚類中心ci和隸屬矩陣U1：步驟1：用值在0，1間的隨機數(shù)初始化隸屬矩陣U，使其滿足式（6.9）中的約束條件步驟2：用式（6.12）計算c個聚類中心ci，i=1,c。步驟3：根據(jù)式（6.10）計算價值函數(shù)。如果它小于某個確定的閥值，或它相對上次價值函數(shù)值的改變量小于某個閥值，則算法停止。步驟4：用（6.13）

7、計算新的U矩陣。返回步驟2。上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。由于不能確保FCM收斂于一個最優(yōu)解。算法的性能依賴于初始聚類中心。因此，我們要么用另外的快速算法確定初始聚類中心，要么每次用不同的初始聚類中心啟動該算法，多次運行FCM。模糊c均值聚類算法如下：Reapeat for l=1 2 3.Step 1:compute the cluseter prototypes(means):Step 2:compete the distance:Step 3:Update the partition matrix:算法改進1） 在模糊聚類的目標函數(shù)中Bezdek引入了加權(quán)指數(shù)m，使

8、Dum的聚類準則變成m=2時候的特例，從數(shù)學上說m的出現(xiàn)不自然且沒有必要，但如果不給以慮屬度乘以權(quán)值，那么從硬聚類準則函數(shù)到軟聚類目標函數(shù)的推廣準則是無效的，參數(shù)m又稱為平滑因子，控制著模式早模糊類間的分享程度，因此，要實現(xiàn)模糊c聚類就要選擇一適合的m，然而最佳的m的選取目前還缺乏理論，監(jiān)管存在一些經(jīng)驗值或經(jīng)驗范圍，但沒有面向問題的優(yōu)選方法，也缺少參數(shù)m的有效性評價準則2） 盡管模糊聚類是一種無監(jiān)督的分類，但現(xiàn)在的聚類算法卻=需要應(yīng)用聚類原型的先驗條件，否則算法會產(chǎn)生誤導，從未破壞算法的無監(jiān)督性和自動化。3） 因為模糊聚類目標是非凸的，而模糊C均值聚類算法的計算過程又是迭代爬山，一次很容易陷入

9、局部極值點，從而得不到最優(yōu)解或滿意解，同時，大數(shù)據(jù)量下算法耗時也是困擾人們的一大難題，這2個問題目前還不能得到全面的解決。4） FCM類型的聚類算法屬于劃份方法，對于1組給定的樣本集，不管數(shù)據(jù)中有無聚類結(jié)構(gòu)，也不問分類結(jié)果是否有效，總把數(shù)據(jù)劃分到C個子類中，換言之，現(xiàn)有的聚類分析與聚類趨勢，以及有效分析是隔離的分離得。5） FCM的聚類算法是針對特征空間中的點集設(shè)計的，對于特殊類型的數(shù)據(jù)，比如在樣本每維特征的賦值不是一個數(shù)，而是一個區(qū)間。集合和模糊數(shù)時，F(xiàn)CM類型的算法無法直接處理 模糊C均值聚類算法存在上述缺點，改進的算法正確率能達到更高。Fcm算法在處理小數(shù)據(jù)集的時候是有效的，但隨著數(shù)據(jù)容

10、量和維數(shù)的增加，迭代步驟會顯著增加，而且在迭代的每一步都要對整個數(shù)據(jù)集進行操作，無法滿足數(shù)據(jù)挖掘時的需要。 改進算法的思想是首先采用隨機抽樣的辦法，從數(shù)據(jù)集中選取多個樣本，對每個樣本應(yīng)用FCM算法，將得到的結(jié)果作為初始群體，然后再利用遺傳算法對聚類結(jié)果進行優(yōu)化，選取其中的最優(yōu)解做為問題的輸出，由于采樣技術(shù)顯著的壓縮了問題的規(guī)模，而遺傳又可以對結(jié)果進行全局最優(yōu)化處理，因此在時間性能和聚類質(zhì)量上都能獲得較滿意的結(jié)果。遺傳算法是美國Michigon大學的John Holland研究機器學習時創(chuàng)立的一種新型的優(yōu)化算法，它的主要優(yōu)點是：遺傳算法是從一系列點的群體開始搜索而不是從單個樣本點進行搜索，遺傳算

11、法利用適應(yīng)值的相關(guān)信息，無需連續(xù)可導或其他輔助信息，遺傳算法利用轉(zhuǎn)移概率規(guī)則，而非確定性規(guī)則進行迭代，遺傳算法搜索過程中，以對群體進行分化以實現(xiàn)并行運算，遺傳算法經(jīng)過遺傳變異和雜交算子的作用，以保證算法以概率1收斂到全局最優(yōu)解具有較好的全局特性，其次遺傳算法占用計算機的內(nèi)存小，尤其適用計算復雜的非線性問題。遺傳算法的設(shè)計部分（1） 種群中個體的確定聚類的關(guān)鍵問題是聚類中心的確定，因此可以選取聚類中心作為種群的個體，由于共有C個聚類中心，而每個聚類中心是一個S維的實數(shù)向量，因此每個個體的初始值是一個c*s維的市屬向量。（2） 編碼常用的編碼方式有二進制與實數(shù)編碼，由于二進制編碼的方式搜索能力最強

12、，且交叉變異操作簡單高效，因此采用二進制的編碼方式，同時防止在進行交叉操作時對優(yōu)良個體造成較大的破壞，在二進制編碼的方式中采用格雷碼的編碼形式。每個染色體含c*s個基因鏈，每個基因鏈代表一維的數(shù)據(jù)，由于原始數(shù)據(jù)中各個屬性的取值可能相差很大，因此需首先對數(shù)據(jù)進行交換以統(tǒng)一基因鏈的長度，可以有以下兩種變換方式。1掃描整個數(shù)據(jù)集，確定每維數(shù)據(jù)的取值范圍，然后將其變換到同一量級，在保留一定有效位的基礎(chǔ)上取整，根據(jù)有效位的個數(shù)動態(tài)的計算出基因鏈的長度。2對數(shù)據(jù)進行正規(guī)化處理，即將各維數(shù)據(jù)都變換到相同的區(qū)間，可以算出此時的基因鏈長度為10。（3） 適應(yīng)度函數(shù) 由于在算法中只使用了聚類中心V，而未使用慮屬矩

13、陣u,因此需要對FCM聚類算法的目標函數(shù)進行改進，以適用算法的要求，和目標函數(shù)是等價的，由于遺傳算法的適用度一般取值極大，因此可取上式的倒數(shù)作為算法的使用度函數(shù)。（4） 初始種群的確定 初始種群的一般個體由通過采樣后運行FCM算法得到的結(jié)果給出，另外的一般個體通過隨機指定的方法給出，這樣既保證了遺傳算法在運算之初就利用背景知識對初始群體的個體進行了優(yōu)化，使算法能在一個較好的基礎(chǔ)上進行，又使得個體不至于過分集中在某一取值空間，保證了種群的多樣性。（5） 遺傳操作 選擇操作采用保持最優(yōu)的錦標賽法，錦標賽規(guī)模為2，即每次隨機取2個個體，比較其適應(yīng)度，較大的作為父個體，并保留每代的最優(yōu)個體作為下一代，

14、交叉方式一般采用單點交叉或多點交叉法進行，經(jīng)過試驗表明單點交叉效果較好，因此采用單點交叉法，同時在交叉操作中，應(yīng)該對每維數(shù)據(jù)分開進行，以保證較大的搜索空間和結(jié)果的有效性，變異操作采用基本位變異法。（6） 終止條件的確定 遺傳算法在以下二種情況下終止a最佳個體保持不變的代數(shù)達到設(shè)定的閾值b遺傳操作以到達給定的最大世代數(shù)算法具體步驟如下1確定參數(shù)，如聚類個數(shù) 樣本集大小 種群規(guī)模 最大世代數(shù) 交叉概率和變異概率等。2對數(shù)據(jù)集進行多次采樣并運行FCM算法，得到初始種群的一般個體，通過隨機制定產(chǎn)生另一半個體。3對數(shù)據(jù)集進行正規(guī)化處理并編碼。4計算初始種群中個體的適應(yīng)度。5對種群進行遺傳操作產(chǎn)生下一代，

15、在操作的過程中，應(yīng)該排除產(chǎn)生的無效個體。6計算個體的適應(yīng)度，如果滿足終止條件，則算法結(jié)束，否則轉(zhuǎn)到5繼續(xù) 在理論上講進行遺傳操作的樣本容量越大，聚類的誤差越小，由于采樣技術(shù)顯著壓縮了問題規(guī)模，而遺傳算法又可以對全局進行最優(yōu)化處理，因此改進的算法在時間與性能上都能獲得較滿意的結(jié)果，此算法利用采樣技術(shù)來提高算法的運行速度，利用遺傳算法對聚類進行優(yōu)化，避免陷入局部最優(yōu)解，在性能上相比于傳統(tǒng)的模糊C均值聚類算法獲得較大提高。算法實現(xiàn)采用VC+進行編寫文檔的讀取#include data.h/函數(shù)定義double *DataRead(char*name,int row,int col)double *p

16、=new double* row;ifstream infile;infile.open(name,ios:in);for(int i=0;irow;i+)pi=new doublecol;for(int j=0;jpij;infile.close();cout成功讀取數(shù)據(jù)文件:name!n;return p;/釋放內(nèi)存for(i=0;irow;i+)deletepi;deletep;文檔的保存#include data.hvoid DataSave(double*data,int row,int col,char*name)int i,j;ofstream outfile;/打開文件，輸出數(shù)

17、據(jù)outfile.open(name,ios:out);outfile.setf(ios:fixed);outfile.precision(4); for(i=0;irow;i+)for(j=0;jcol;j+)outfiledataij ;outfileendl;outfileendlendl;outfile.close(); 數(shù)據(jù)標準化處理#include data.hdouble *Standardize(double *data,int row,int col)int i,j;double* a=new doublecol; /矩陣每列的最大值double* b=new doublec

18、ol; /矩陣每列的最小值double* c=new doublerow; /矩陣列元素for(i=0;icol;i+)/取出數(shù)據(jù)矩陣的各列元素for(j=0;jrow;j+)cj=Dataji; ai=c0,bi=c0;for(j=0;jai)ai=cj;/取出該列的最小值if(cjbi)bi=cj;/數(shù)據(jù)標準化for(i=0;irow;i+)for(j=0;jcol;j+)dataij=(dataij-bj)/(aj-bj);cout完成數(shù)據(jù)極差標準化處理!n;deletea;deleteb;deletec;return data;生成樣本慮屬矩陣#include data.hvoid I

19、nitialize(double *u, int k, int row)int i,j;/初始化樣本隸屬度矩陣srand(time(0); for(i=0;ik;i+)for(j=0;jrow;j+)uij=(double)rand()/RAND_MAX;/得到一個小于1的小數(shù)隸屬度/rand()函數(shù)返回0和RAND_MAX之間的一個偽隨機數(shù)數(shù)據(jù)歸一化處理#include data.hvoid Normalize(double *u,int k,int col)int i,j;double *sum=new doublecol;/矩陣U的各列元素之和for(j=0;jcol;j+)double

20、 dj=0;for(i=0;ik;i+)dj=dj+Uij;sumj=dj;/隸屬度各列之和for(i=0;ik;i+)for(j=0;jcol;j+)uij=Uij/sumj;/規(guī)一化處理(每列隸屬度之和為1)迭代過程#include data.h#include func.h/對模糊C均值進行迭代運算,并返回有效性評價函數(shù)的值double Update(double*u,double*data,double*center,int row,int col, int k)int i,j,t;double *p=NULL;for(i=0;ik;i+)for(j=0;jrow;j+)/模糊指數(shù)取2

21、uij=pow(uij,2);/根據(jù)隸屬度矩陣計算聚類中心p=MatrixMul(u,k,row,data,row,col);for(i=0;ik;i+)/計算隸屬度矩陣每行之和double si=0;for(j=0;jrow;j+)si+=uij;for(t=0;tcol;t+)centerit=pit/si; /類中心/計算各個聚類中心i分別到所有點j的距離矩陣dis(i,j)double* a=new doublecol; /第一個樣本點double* b=new doublecol; /第二個樣本點double*dis=new double*k; /中心與樣本之間距離矩陣for(i=0

22、;ik;i+)disi=new doublerow;for(i=0; ik; i+)/聚類中心for(t=0; tcol; t+)at=centerit; /暫存類中心 /數(shù)據(jù)樣本for(j=0; jrow; j+)for(t=0; tcol; t+)bt=datajt;/暫存一樣本double d=0;/中心與樣本之間距離的計算for(t=0; tcol; t+)d+=(at-bt)*(at-bt); /d為一中心與所有樣本的距離的平方和disij=sqrt(d); /距離/根據(jù)距離矩陣計算隸屬度矩陣for(i=0;ik;i+)for(j=0;jrow;j+)double temp=0;fo

23、r(t=0;tk;t+)/disij依次除以所在列的各元素,加和；/模糊指數(shù)為2.0temp+=pow(disij/distj,2/(2.0-1);/一個類中心和一個元素的距離平方與uij=1/temp;/所有類與該元素距離平方的和的商/計算聚類有效性評價函數(shù)double func1=0;for(i=0;ik;i+)double func2=0;for(j=0;jrow;j+)func2+=pow(uij,2.0)*pow(disij,2);func1+=func2;double obj_fcn=1/(1+func1);return obj_fcn;/內(nèi)存釋放deletea;deleteb;f

24、or(i=0;ik;i+)deletedisi;deletedis;詳細過程#include data.h#include func.h#include max.h/全局變量定義double *Data; /數(shù)據(jù)矩陣double *Center; /聚類中心矩陣double *U; /樣本隸屬度矩陣 int m; /樣本總數(shù)int n; /樣本屬性數(shù)int k; /設(shè)定的劃分類別數(shù) int main()int Lab; /數(shù)據(jù)文件標號int num; /算法運行次數(shù)/cout模糊C均值聚類算法:endl;cout1-iris.txt; 2-wine.txt; 3-ASD_12_2.txt; 4

25、-ASD_14_2.txtendl;coutLab;coutnum;/各次運行結(jié)束后的目標函數(shù)double* Index=new doublenum;/各次運行結(jié)束后的聚類正確率double* R=new double num;/num次運行的平均目標函數(shù)及平均正確率double M_Index=0;double M_R=0;/FCM聚類算法運行num次，并保存記錄與結(jié)果for(int i=0;i0)coutendlendl;coutsetfill(#)setw(10)endl;cout第i+1次運行記錄:endl;/讀取數(shù)據(jù)文件if(Lab=1)m=150;n=4;k=3;Data=Data

26、Read(datasetiris.txt,m,n);else if(Lab=2)m=178;n=13;k=3;Data=DataRead(datasetwine.txt,m,n);else if(Lab=3)m=535;n=2;k=12;Data=DataRead(datasetASD_12_2.txt,m,n);else if(Lab=4)m=685;n=2;k=14;Data=DataRead(datasetASD_14_2.txt,m,n);/數(shù)據(jù)極差標準化處理Data=Standardize(Data,m,n);/聚類中心及隸屬度矩陣,內(nèi)存分配Center=new double*k;U

27、=new double *k;for(j=0;jk;j+)Centerj=new doublen;Uj=new doublem;/隸屬度矩陣的初始化Initialize(U, k, m);/對隸屬度矩陣進行歸一化Normalize(U,k,m);/歷次迭代過程中的目標函數(shù)double Objfcn100=0;cout第i+1次運行記錄:endl;cout開始迭代過程!endl;cout*endl;/輸出精度為小數(shù)點后5位cout.precision(5);/固定格式cout.setf(ios:fixed);/目標函數(shù)連續(xù)20代無改進，停止該次聚類迭代過程while(e0 & Objfcnnx-

28、Objfcnnx-1epsilon )e+;elsee=0;Enx=e;/輸出結(jié)果到文件，保存ofstream outfile(運行記錄.txt,ios:app);outfile第i+1次運行記錄:endl;outfile開始迭代過程!endl;outfile*endl;outfile.precision(5);outfile.setf(ios:fixed);for(int n1=1;n1=nx;n1+)coutesetw(2)n1=setw(2)En1 Objfcnsetw(2)n1=Objfcnn1 n;/保存數(shù)據(jù)文件outfileesetw(2)n1=setw(2)En1 Objfcns

29、etw(2)n1=Objfcnn1 n;coutendl;outfileendl;outfile.close();/本次運行的最大目標函數(shù)Indexi=Objfcnnx;/保存聚類正確率，輸出聚類結(jié)果：Ri=Result(Lab, U, k, m, i);/內(nèi)存釋放for(j=0;jk;j+)deleteCenterj;deleteUj;deleteCenter;deleteU;/統(tǒng)計平均/double temp1=0, temp2=0;for(i=0;inum;i+)temp1+=Indexi;temp2+=Ri;/計算各次結(jié)果的統(tǒng)計平均M_Index=(double)temp1/num;M

30、_R=(double)temp2/num;cout/endl;coutnum次運行,平均聚類正確率: 100*M_R%endl;/輸出精度為小數(shù)點后6位cout.precision(6);/固定格式cout.setf(ios:fixed);cout平均目標函數(shù): M_Indexendl;/統(tǒng)計結(jié)果文件保存ofstream resultfile(聚類結(jié)果.txt,ios:app);resultfile/endl;resultfilenum次運行,平均聚類正確率: 100*M_R%endl;/輸出精度為小數(shù)點后6位resultfile.precision(6);/固定格式resultfile.se

31、tf(ios:fixed);resultfile平均目標函數(shù): M_Indexendl;return 0;采用著名的iris數(shù)據(jù)集對程序進行測試，運算次數(shù)輸入10次能對數(shù)組實現(xiàn)分類，但是分類正確率不是很理想，沒達到預期的90%以上總結(jié)這次綜合實習，首先我學會了模糊C均值聚類算法，以前沒接觸過，也不知道何為數(shù)據(jù)集，數(shù)據(jù)集是做啥用的，增加了自己的見解，其次增強了自我學習能力，平時學習的學習都是老師已經(jīng)安排好得內(nèi)容，看啥知識都已經(jīng)知道，只需要安心的看就能學會，都是書本上的知識，沒有聯(lián)系實際，一般都是一些理論算法，算法比較簡單而且古老，但這次綜合實習通過自己從網(wǎng)上查找資料學習，了解算法的詳細步驟，研究算法的不足，雖然查找資料學習的過程比較繁瑣，但總算在最后學會了模糊C均值聚類算法，也對算法的改進有所了解，人工智能學習的GA遺傳算法進行了改進，通過這次綜合實習，我對不懂得知識的學習有了一個比較系統(tǒng)的學習過程，為以后的自我學習打下了基礎(chǔ)，模糊C均值聚類算法的程序是用c+實現(xiàn)的，通過對程序的而研究，我對于文件的讀取 保存 計算的迭代過程等都已經(jīng)非常的了解，對于以前所學的進行了一次復習，這次綜合實現(xiàn)收獲很大，自己所學的東西學會了如何使用，不同的算法進行銜