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

模糊C均值聚類算法及實現(xiàn)摘要：模糊聚類是一種重要數(shù)據(jù)分析和建模的無監(jiān)督方法。本文對模糊聚類進行了概述，從理論和實驗方面研究了模糊c均值聚類算法，并對該算法的優(yōu)點及存在的問題進行了分析。該算法設(shè)計簡單，應(yīng)用范圍廣，但仍存在容易陷入局部極值點等問題，還需要進一步研究。關(guān)鍵詞：模糊c均值算法；模糊聚類；聚類分析Fuzzyc-MeansClusteringAlgorithmandImplementationAbstract:Fuzzyclusteringisapowerfulunsupervisedmethodfortheanalysisofdataandconstructionofmodels.Thispaperpresentsanoverviewoffuzzyclusteringanddosomestudyoffuzzyc-meansclusteringalgorithmintermsoftheoryandexperiment.Thisalgorithmissimpleindesign,canbewidelyused,buttherearestillsomeproblemsinit,andtherefore,itisnecessarytobestudiedfurther.Keywords:fuzzyc-Meanalgorithm；fuzzyclustering；clusteringanalysis1引言20世紀90年代以來，隨著信息技術(shù)和數(shù)據(jù)庫技術(shù)的迅猛發(fā)展，人們可以非常方便地獲取和存儲大量的數(shù)據(jù)。但是，面對大規(guī)模的數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)分析工具只能進行一些表層的處理，比如查詢、統(tǒng)計等，而不能獲得數(shù)據(jù)之間的內(nèi)在關(guān)系和隱含的信息。為了擺脫“數(shù)據(jù)豐富，知識貧乏”的困境，人們迫切需要一種能夠智能地、自動地把數(shù)據(jù)轉(zhuǎn)換成有用信息和知識的技術(shù)和工具，這種對強有力數(shù)據(jù)分析工具的迫切需求使得數(shù)據(jù)挖掘技術(shù)應(yīng)運而生。將物理或抽象對象的集合分組成由類似的對象組成的多個類的過程稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其它簇中的對象相異。聚類是一種重要的數(shù)據(jù)分析技術(shù)，搜索并且識別一個有限的種類集合或簇集合，進而描述數(shù)據(jù)。聚類分析作為統(tǒng)計學(xué)的一個分支，己經(jīng)被廣泛研究了許多年。而且，聚類分析也已經(jīng)廣泛地應(yīng)用到諸多領(lǐng)域中，包括數(shù)據(jù)分析、模式識別、圖像處理以及市場研究[1]。通過聚類，人們能夠識別密集的和稀疏的區(qū)域，因而發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的有趣的相互關(guān)系。在商務(wù)上，聚類能幫助市場分析人員從客戶基本信息庫中發(fā)現(xiàn)不同的客戶群，并且用購買模式來刻畫不同的客戶群的特征。在生物學(xué)上，聚類能用于推導(dǎo)植物和動物的分類，對基因進行分類，獲得對種群中固有結(jié)構(gòu)的認識。聚類在地球觀測數(shù)據(jù)庫中相似地區(qū)的確定，汽車保險單持有者的分組，及根據(jù)房屋的類型、價值和地理位置對一個城市中房屋的分組上也可以發(fā)揮作用。聚類也能用于對Web上的文檔進行分類，以發(fā)現(xiàn)信息?；趯哟蔚木垲愃惴ㄎ墨I中最早出現(xiàn)的Single-Linkage層次聚類算法是1957年在Lloyd的文章中最早出現(xiàn)的，之后MacQueen獨立提出了經(jīng)典的模糊C均值聚類算法，F(xiàn)CM算法中模糊劃分的概念最早起源于Ruspini的文章中，但關(guān)于FCM的算法的詳細的分析與改進則是由Dunn和Bezdek完成的。聚類分析是多元統(tǒng)計分析的一種，也是非監(jiān)督模式識別的一個重要分支，在模式分類、圖像處理和模糊規(guī)則處理等眾多領(lǐng)域中獲得最廣泛的應(yīng)用。它把一個沒有類別標記的樣本集按某種準則劃分為若干個子集(類)，使相似的樣本盡可能的歸為一類，而將不相似的樣本盡量劃分到不同的類中。硬聚類把每個待辨識的對象嚴格地劃分到某類中，具有非此即彼的性質(zhì)，模糊聚類由于能夠描述樣本類屬的中介性，能夠客觀地反映現(xiàn)實世界，已逐漸成為聚類分析的主流[2-3]。在眾多的模糊聚類算法中，模糊c均值聚類算法(FCM)應(yīng)用最為廣泛。它按照某種判別準則，將數(shù)據(jù)的聚類轉(zhuǎn)化為一個非線性優(yōu)化問題，并通過迭代來進行求解，目前已成為非監(jiān)督模式識別的一個重要分支。數(shù)據(jù)挖掘中的聚類分析主要集中在針對海量數(shù)據(jù)的有一效和實用的聚類方法研究，聚類方法的可伸縮性，高維聚類分析，分類屬性數(shù)據(jù)聚類和具有混合屬性數(shù)據(jù)的聚類，非距離模糊聚類等。因此，數(shù)據(jù)挖掘?qū)垲惙治鲇衅涮厥獾囊?可伸縮性，能夠處理不同類型屬性，強抗噪性，高維性，對輸入順序不敏感性，可解釋性和可用性等。本文正是在此背景下對數(shù)據(jù)挖掘中的聚類分析進行論述，并著重研究了FCM算法。2模糊聚類算法2.1模糊聚類算法概述模糊聚類算法是一種基于函數(shù)最優(yōu)方法的聚類算法，使用微積分計算技術(shù)求設(shè)被分類的對象的集合為：X={x1，x2，…，xN}，其中每一個對象xk有n個特性指標，設(shè)為xk=(x1k，x2k，…，xnk)T,如果要把X分成c類，則它的每一個分類結(jié)果都對應(yīng)一個c×N階的Boolean矩陣Mfc={|uik∈[0，1]，i，k；=1，k;0<，i}在此空間上，模糊c均值算法如下：Repeatforl=1，2……Step1：computethecluseterprototypes(means)：Step2：competethedistance：Step3：Updatethepartitionmatrix：ForIfforalli=1，2，…，cOtherwise=0if>0，and∈[0，1]withUntil<3.2實驗采用著名的iris數(shù)據(jù)集對算法進行測試實現(xiàn)，其中樣本總數(shù)m=150，樣本屬性數(shù)n=4，設(shè)定的劃分內(nèi)別k=3。運算次數(shù)為10次的輸出結(jié)果：能對數(shù)組實現(xiàn)分類，但是分類正確率不是很理想。3.3FCM算法優(yōu)缺點通過實驗和算法的研究學(xué)習(xí)，不難發(fā)現(xiàn)FCM算法的優(yōu)缺點[5-8]：首先，模糊c均值泛函Jm仍是傳統(tǒng)的硬c均值泛函J1的自然推廣。J1是一個應(yīng)用很廣泛的聚類準則，對其在理論上的研究已經(jīng)相當(dāng)?shù)耐晟?，這就為Jm的研究提供了良好的條件。其次，從數(shù)學(xué)上看，Jm與Rs的希爾伯特空間結(jié)構(gòu)(正交投影和均方逼近理論)有密切的關(guān)聯(lián)，因此Jm比其他泛函有更深厚的數(shù)學(xué)基礎(chǔ)。最后，F(xiàn)CM聚類算法不僅在許多鄰域獲得了非常成功的應(yīng)用，而且以該算法為基礎(chǔ)，又提出基于其他原型的模糊聚類算法，形成了一大批FCM類型的算法，比如模糊c線(FCL)，模糊c面(FCP)，模糊c殼(FCS)等聚類算法，分別實現(xiàn)了對呈線狀、超平面狀和“薄殼”狀結(jié)構(gòu)模式子集(或聚類)的檢測。4結(jié)語模糊c均值算法因設(shè)計簡單，解決問題范圍廣，易于應(yīng)用計算機實現(xiàn)等特點受到了越來越多人的關(guān)注，并應(yīng)用于各個領(lǐng)域。但是，自身仍存在的諸多問題，例如強烈依賴初始化數(shù)據(jù)的好壞和容易陷入局部鞍點等，仍然需要進一步的研究。參考文獻：[1]AKJain，MNMurty，PJFlynn.DataClustering：AReview，ACMComputingSurveys[J]，1999，31(3)：264-323.[2]SpraginsJ.Learningwithoutateacher[J].IEEETransactionsofInformationTheory，2005，23(6)：223-230.[3]BabuskR.FUZZYANDNEURALCONTROL[M].Netherlands：DelftUniversityofTechnology，2001.[4]TheodoridisS.PatternRecongnition[M].SecondEdition.USA：ElsevierScinece，2003.[5]高新波.FCM聚類算法中模糊加權(quán)指數(shù)m的