1、精選優(yōu)質(zhì)文檔-傾情為你奉上模糊C均值聚類算法及實(shí)現(xiàn)摘要：模糊聚類是一種重要數(shù)據(jù)分析和建模的無監(jiān)督方法。本文對(duì)模糊聚類進(jìn)行了概述，從理論和實(shí)驗(yàn)方面研究了模糊c均值聚類算法，并對(duì)該算法的優(yōu)點(diǎn)及存在的問題進(jìn)行了分析。該算法設(shè)計(jì)簡(jiǎn)單，應(yīng)用范圍廣，但仍存在容易陷入局部極值點(diǎn)等問題，還需要進(jìn)一步研究。關(guān)鍵詞：模糊c均值算法；模糊聚類；聚類分析Fuzzy c-Means Clustering Algorithm and ImplementationAbstract: Fuzzy clustering is a powerful unsupervised method for the analysis of

2、data and construction of models.This paper presents an overview of fuzzy clustering and do some study of fuzzy c-means clustering algorithm in terms of theory and experiment.This algorithm is simple in design,can be widely used,but there are still some problems in it,and therefore,it is necessary to

3、 be studied further.Key words: fuzzy c-Mean algorithm；fuzzy clustering；clustering analysis1 引言20世紀(jì)90年代以來，隨著信息技術(shù)和數(shù)據(jù)庫技術(shù)的迅猛發(fā)展，人們可以非常方便地獲取和存儲(chǔ)大量的數(shù)據(jù)。但是，面對(duì)大規(guī)模的數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)分析工具只能進(jìn)行一些表層的處理，比如查詢、統(tǒng)計(jì)等，而不能獲得數(shù)據(jù)之間的內(nèi)在關(guān)系和隱含的信息。為了擺脫“數(shù)據(jù)豐富，知識(shí)貧乏”的困境，人們迫切需要一種能夠智能地、自動(dòng)地把數(shù)據(jù)轉(zhuǎn)換成有用信息和知識(shí)的技術(shù)和工具，這種對(duì)強(qiáng)有力數(shù)據(jù)分析工具的迫切需求使得數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生。將物理或抽象對(duì)象

4、的集合分組成由類似的對(duì)象組成的多個(gè)類的過程稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對(duì)象的集合，這些對(duì)象與同一個(gè)簇中的對(duì)象彼此相似，與其它簇中的對(duì)象相異。聚類是一種重要的數(shù)據(jù)分析技術(shù)，搜索并且識(shí)別一個(gè)有限的種類集合或簇集合，進(jìn)而描述數(shù)據(jù)。聚類分析作為統(tǒng)計(jì)學(xué)的一個(gè)分支，己經(jīng)被廣泛研究了許多年。而且，聚類分析也已經(jīng)廣泛地應(yīng)用到諸多領(lǐng)域中，包括數(shù)據(jù)分析、模式識(shí)別、圖像處理以及市場(chǎng)研究1。通過聚類，人們能夠識(shí)別密集的和稀疏的區(qū)域，因而發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的有趣的相互關(guān)系。在商務(wù)上，聚類能幫助市場(chǎng)分析人員從客戶基本信息庫中發(fā)現(xiàn)不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。在生物學(xué)上，聚

5、類能用于推導(dǎo)植物和動(dòng)物的分類，對(duì)基因進(jìn)行分類，獲得對(duì)種群中固有結(jié)構(gòu)的認(rèn)識(shí)。聚類在地球觀測(cè)數(shù)據(jù)庫中相似地區(qū)的確定，汽車保險(xiǎn)單持有者的分組，及根據(jù)房屋的類型、價(jià)值和地理位置對(duì)一個(gè)城市中房屋的分組上也可以發(fā)揮作用。聚類也能用于對(duì)Web上的文檔進(jìn)行分類，以發(fā)現(xiàn)信息。基于層次的聚類算法文獻(xiàn)中最早出現(xiàn)的Single-Linkage層次聚類算法是1957年在Lloyd的文章中最早出現(xiàn)的，之后MacQueen獨(dú)立提出了經(jīng)典的模糊C均值聚類算法，F(xiàn)CM算法中模糊劃分的概念最早起源于Ruspini的文章中，但關(guān)于FCM的算法的詳細(xì)的分析與改進(jìn)則是由Dunn和Bezdek完成的。聚類分析是多元統(tǒng)計(jì)分析的一種，也是非

6、監(jiān)督模式識(shí)別的一個(gè)重要分支，在模式分類、圖像處理和模糊規(guī)則處理等眾多領(lǐng)域中獲得最廣泛的應(yīng)用。它把一個(gè)沒有類別標(biāo)記的樣本集按某種準(zhǔn)則劃分為若干個(gè)子集(類) ，使相似的樣本盡可能的歸為一類，而將不相似的樣本盡量劃分到不同的類中。硬聚類把每個(gè)待辨識(shí)的對(duì)象嚴(yán)格地劃分到某類中，具有非此即彼的性質(zhì)，模糊聚類由于能夠描述樣本類屬的中介性，能夠客觀地反映現(xiàn)實(shí)世界，已逐漸成為聚類分析的主流 2 - 3 。在眾多的模糊聚類算法中，模糊c均值聚類算法(FCM)應(yīng)用最為廣泛。它按照某種判別準(zhǔn)則，將數(shù)據(jù)的聚類轉(zhuǎn)化為一個(gè)非線性優(yōu)化問題，并通過迭代來進(jìn)行求解，目前已成為非監(jiān)督模式識(shí)別的一個(gè)重要分支。數(shù)據(jù)挖掘中的聚類分析主要

7、集中在針對(duì)海量數(shù)據(jù)的有一效和實(shí)用的聚類方法研究，聚類方法的可伸縮性，高維聚類分析，分類屬性數(shù)據(jù)聚類和具有混合屬性數(shù)據(jù)的聚類，非距離模糊聚類等。因此，數(shù)據(jù)挖掘?qū)垲惙治鲇衅涮厥獾囊?可伸縮性，能夠處理不同類型屬性，強(qiáng)抗噪性，高維性，對(duì)輸入順序不敏感性，可解釋性和可用性等。本文正是在此背景下對(duì)數(shù)據(jù)挖掘中的聚類分析進(jìn)行論述，并著重研究了FCM算法。2 模糊聚類算法2.1 模糊聚類算法概述模糊聚類算法是一種基于函數(shù)最優(yōu)方法的聚類算法，使用微積分計(jì)算技術(shù)求最優(yōu)代價(jià)函數(shù)。在基于概率算法的聚類方法中將使用概率密度函數(shù)，為此要假定合適的模型，模糊聚類算法的向量可以同時(shí)屬于多個(gè)聚類，從而擺脫上述問題。在模糊聚

8、類算法中，定義了向量與聚類之間的近鄰函數(shù)，并且聚類中向量的隸屬度由隸屬函數(shù)集合提供。對(duì)模糊方法而言，在不同聚類中的向量隸屬函數(shù)值是相互關(guān)聯(lián)的。硬聚類可以看成是模糊聚類方法的一個(gè)特例。2.2 模糊聚類算法的分類模糊聚類分析算法大致可分為三類4： 1）分類數(shù)不定，根據(jù)不同要求對(duì)事物進(jìn)行動(dòng)態(tài)聚類，此類方法是基于模糊等價(jià)矩陣聚類的，稱為模糊等價(jià)矩陣動(dòng)態(tài)聚類分析法。 2）分類數(shù)給定，尋找出對(duì)事物的最佳分析方案，此類方法是基于目標(biāo)函數(shù)聚類的，稱為模c均值聚類。3）在攝動(dòng)有意義的情況下，根據(jù)模糊相似矩陣聚類，此類方法稱為基于攝動(dòng)的模糊聚類分析法。3 模糊c均值（FCM）聚類算法3.1 算法描述模糊c均值聚類

9、算法的步驟還是比較簡(jiǎn)單的，模糊c均值聚類（FCM），即眾所周知的模糊ISODATA，是用隸屬度確定每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)聚類的程度的一種聚類算法。1973年，Bezdek提出了該算法，作為早期硬c均值聚類（HCM）方法的一種改進(jìn)。FCM把n個(gè)向量xi（i=1,2,n）分為c個(gè)模糊組，并求每組的聚類中心，使得非相似性指標(biāo)的價(jià)值函數(shù)達(dá)到最小。FCM與HCM的主要區(qū)別在于FCM用模糊劃分，使得每個(gè)給定數(shù)據(jù)點(diǎn)用值在0，1間的隸屬度來確定其屬于各個(gè)組的程度。與引入模糊劃分相適應(yīng)，隸屬矩陣U允許有取值在0，1間的元素。不過，加上歸一化規(guī)定，一個(gè)數(shù)據(jù)集的隸屬度的和總等于1： (3.1)那么，F(xiàn)CM的價(jià)值函數(shù)（或

10、目標(biāo)函數(shù)）就是：， (3.2)這里uij介于0，1間；ci為模糊組I的聚類中心，dij=|ci-xj|為第I個(gè)聚類中心與第j個(gè)數(shù)據(jù)點(diǎn)間的歐幾里德距離；且是一個(gè)加權(quán)指數(shù)。構(gòu)造如下新的目標(biāo)函數(shù)，可求得使（3.2）式達(dá)到最小值的必要條件： (3.3)這里lj，j=1到n，是（3.1）式的n個(gè)約束式的拉格朗日乘子。對(duì)所有輸入?yún)⒘壳髮?dǎo)，使式（3.2）達(dá)到最小的必要條件為： (3.4)和 (3.5)由上述兩個(gè)必要條件，模糊c均值聚類算法是一個(gè)簡(jiǎn)單的迭代過程。在批處理方式運(yùn)行時(shí)，F(xiàn)CM用下列步驟確定聚類中心ci和隸屬矩陣U1：步驟1：用值在0，1間的隨機(jī)數(shù)初始化隸屬矩陣U，使其滿足式（3.1）中的約束條件步

11、驟2：用式（3.4）計(jì)算c個(gè)聚類中心ci，i=1,c。步驟3：根據(jù)式（3.2）計(jì)算價(jià)值函數(shù)。如果它小于某個(gè)確定的閥值，或它相對(duì)上次價(jià)值函數(shù)值的改變量小于某個(gè)閥值，則算法停止。步驟4：用（3.5）計(jì)算新的U矩陣。返回步驟2。上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。由于不能確保FCM收斂于一個(gè)最優(yōu)解。算法的性能依賴于初始聚類中心。因此，我們要么用另外的快速算法確定初始聚類中心，要么每次用不同的初始聚類中心啟動(dòng)該算法，多次運(yùn)行FCM。設(shè)被分類的對(duì)象的集合為：X = x1 ， x2 ，xN，其中每一個(gè)對(duì)象xk有n 個(gè)特性指標(biāo)，設(shè)為xk = ( x1k ，x2k ， ， xnk) T , 如

12、果要把X 分成c 類，則它的每一個(gè)分類結(jié)果都對(duì)應(yīng)一個(gè)c×N 階的Boolean矩陣U= uik c×N，對(duì)應(yīng)的模糊c劃分空間為：Mfc = | uik 0，1 ，i ，k ； = 1 ，k;0<，i在此空間上，模糊c 均值算法如下：Repeat for l = 1 ，2Step 1：compute the cluseter prototypes(means)：Step 2：compete the distance：Step 3：Update the partition matrix：For If for all i=1，2，cOtherwise=0 if >0，

13、and 0，1 with Until <3.2 實(shí)驗(yàn)采用著名的iris數(shù)據(jù)集對(duì)算法進(jìn)行測(cè)試實(shí)現(xiàn)，其中樣本總數(shù)m=150，樣本屬性數(shù)n=4，設(shè)定的劃分內(nèi)別k=3。運(yùn)算次數(shù)為10次的輸出結(jié)果：能對(duì)數(shù)組實(shí)現(xiàn)分類，但是分類正確率不是很理想。3.3 FCM算法優(yōu)缺點(diǎn)通過實(shí)驗(yàn)和算法的研究學(xué)習(xí)，不難發(fā)現(xiàn)FCM算法的優(yōu)缺點(diǎn)5-8：首先，模糊c 均值泛函Jm 仍是傳統(tǒng)的硬c 均值泛函J1 的自然推廣。J1 是一個(gè)應(yīng)用很廣泛的聚類準(zhǔn)則，對(duì)其在理論上的研究已經(jīng)相當(dāng)?shù)耐晟?，這就為Jm 的研究提供了良好的條件。其次，從數(shù)學(xué)上看，Jm與Rs的希爾伯特空間結(jié)構(gòu)(正交投影和均方逼近理論) 有密切的關(guān)聯(lián)，因此Jm 比其他

14、泛函有更深厚的數(shù)學(xué)基礎(chǔ)。最后，F(xiàn)CM 聚類算法不僅在許多鄰域獲得了非常成功的應(yīng)用，而且以該算法為基礎(chǔ)，又提出基于其他原型的模糊聚類算法，形成了一大批FCM類型的算法，比如模糊c線( FCL) ，模糊c面(FCP) ，模糊c殼(FCS) 等聚類算法，分別實(shí)現(xiàn)了對(duì)呈線狀、超平面狀和“薄殼”狀結(jié)構(gòu)模式子集(或聚類) 的檢測(cè)。4 結(jié)語模糊c均值算法因設(shè)計(jì)簡(jiǎn)單，解決問題范圍廣，易于應(yīng)用計(jì)算機(jī)實(shí)現(xiàn)等特點(diǎn)受到了越來越多人的關(guān)注，并應(yīng)用于各個(gè)領(lǐng)域。但是，自身仍存在的諸多問題，例如強(qiáng)烈依賴初始化數(shù)據(jù)的好壞和容易陷入局部鞍點(diǎn)等，仍然需要進(jìn)一步的研究。參考文獻(xiàn)：1 A K Jain，M N Murty，P J Fl

15、ynn. Data Clustering：A Review，ACM Computing SurveysJ，1999，31(3)：264-323.2 Spragins J. Learning without a teacher J .IEEE Transactions of Information Theory ，2005 ，23 (6) ：223 -230.3 Babusk R. FUZZYAND NEURAL CONTROLM . Netherlands：Delft University of Technology ，2001.4 Theodoridis S.Pattern Recongnitio