【基于圖聚類的FCM算法及MATLAB仿真探析6700字（論文）】

基于圖聚類的FCM算法及MATLAB仿真分析摘要聚類分析是當前研究的一個重要方向， 其目的是將數(shù)據(jù)集進行拆分，形成多個有意義的簇，進一步來實現(xiàn)對數(shù)據(jù)的識別。圖聚類是一種比較新的聚類方法，它一般先將數(shù)據(jù)表達成為圖，然后再將聚類的問題轉(zhuǎn)化成為圖劃分的問題。圖聚類方法可以對任意的數(shù)據(jù)信息進行聚類分析，改善了傳統(tǒng)聚類分析的不足。本文通過分析圖聚類算法的相關(guān)理論，實現(xiàn)一種基于噪聲點消除的圖聚類算法。首先，本次研究利用自然鄰居的概念構(gòu)造自然鄰居圖，構(gòu)圖時將輸入的數(shù)據(jù)集表示為自然鄰居圖;其次使用模糊C均值聚類算法（FCM算法，F(xiàn)uzzyC-Means）將數(shù)據(jù)集分為多個組，對數(shù)據(jù)集中的樣本點之間的距離進行計算，將每個組中距離其他樣本點較遠的點視為噪聲點并為其分配較低的隸屬度，根據(jù)隸屬度計算聚類中心，將隸屬度低的點刪除以達到去除噪聲的目的;最后計算非相似性指標的目標函數(shù)，根據(jù)聚類中心再返回計算隸屬度，經(jīng)過多次迭代后使得目標函數(shù)最小則完成聚類分析，輸出聚類的結(jié)果。本文通過Matlab工具對基于噪聲消除的圖聚類算法進行實現(xiàn)，以Matlab繪圖函數(shù)構(gòu)建的圖為輸入數(shù)據(jù)集，實驗結(jié)果顯示可以較好地完成圖數(shù)據(jù)集的聚類劃分。關(guān)鍵詞：圖聚類算法圖像分割噪聲MATLAB目錄1緒論 11.1研究背景及意義 11.2國內(nèi)外研究現(xiàn)狀 11.3論文主要研究內(nèi)容 22相關(guān)理論概述 32.1圖論 32.1.1圖的基本概念 32.1.2圖的鄰接矩陣 32.1.3自然鄰居圖 52.2聚類概述 52.2.1聚類分析 62.2.2主要聚類方法 63基于圖聚類的FCM算法 73.1FCM算法概述 73.1.1FCM算法的一般步驟 73.1.2隸屬度函數(shù) 83.2FCM算法的去噪原理 84基于MATLAB的圖聚類算法仿真模擬 94.1基于MATLAB的圖聚類算法仿真 94.2仿真結(jié)果 10總結(jié)與展望 15參考文獻 161緒論1.1研究背景及意義聚類分析是一種在沒有監(jiān)督學習的環(huán)境中對簇的研究，其將不同簇之間數(shù)據(jù)的區(qū)別進行擴大，縮小相同簇數(shù)據(jù)之間的區(qū)別。聚類分析具有悠久的歷史，并且隨著社會的進步該分析方法也得到了不斷的創(chuàng)新。該研究是模式識別和機器學習領(lǐng)域中關(guān)鍵的一個研究方向，作為一個重要的數(shù)據(jù)分析工具，聚類的重要作用被廣泛認可。當前有關(guān)聚類分析的研究推陳出新，多種聚類方法被提出，查閱現(xiàn)有的相關(guān)文獻可以發(fā)現(xiàn)，盡管每個研究人員所用到的技術(shù)不同，但各個研究背景重疊交叉，缺少一種判斷準則對這些方法進行歸類總結(jié)。以往聚類方法在處理局部和非線性數(shù)據(jù)模式時有很大的局限性，研究人員對于該問題經(jīng)過不斷分析并提出基于圖的聚類算法。該算法是在圖劃分理論基礎(chǔ)上，可以對各種不同形狀的聚類圖識別，在各個方面廣泛運用，基于圖的聚類方法中譜聚類方法運用最多，但易受到噪聲和異常值的影響。為了彌補這一不足，本文研究將設(shè)計出一種基于噪聲移除的圖聚類算法。1.2國內(nèi)外研究現(xiàn)狀下列是國外專家學者研究聚類算法的主要內(nèi)容：(1)提出有關(guān)聚類算法的多種最具代表性的算法，算法在應用時依據(jù)各種結(jié)構(gòu)將一個數(shù)據(jù)集分為多個不同簇。(2)提出層次式聚類算法，該算法基于基本原則多次合并，即可獲得結(jié)構(gòu)圖。(3)提出基于密度聚類算法，此類算法可以劃分低密度與高密度兩個不同區(qū)域。以上的兩種基于層次的聚類算法和基于密度的聚類算法將在本文第二章詳細介紹。我國專家學者研究聚類算法取得的成果：(1)鄭浩原等人對聚類算法改進，挖掘網(wǎng)絡社區(qū)時使用層次聚類算法，要對每個點間的相似性求解，在分析角色時引入ego(中心節(jié)點）處理。(2)重點研究網(wǎng)絡簇結(jié)構(gòu)，基于此結(jié)構(gòu)制定一個多個粒子群組成的聚類網(wǎng)絡簇結(jié)構(gòu)法，該算法在使用時是將一個粒子群優(yōu)化運用實現(xiàn)。(3)傳統(tǒng)聚類算法在處理時對于噪聲敏感性較差，難以找到其中主要噪聲源，導致達到的結(jié)果受到噪聲干擾不精準。對于該問題提出一個k-中心點算法（K-Medidos算法），該算法充分運用蜂群算法理念，利用對步長調(diào)節(jié)的方式增強聚類算法精度，使得本算法運行非常穩(wěn)定。1.3論文主要研究內(nèi)容本文主要研究圖聚類算法，并設(shè)計實現(xiàn)基于噪聲去除的圖聚類算法，該算法首先構(gòu)建圖，本文利用自然鄰居的概念構(gòu)造自然鄰居圖，因為基于自然近鄰穩(wěn)定結(jié)構(gòu)的自然鄰居圖的整個計算過程可以在沒有任何參數(shù)的情況下自動完成。其次是對基于噪聲移除的圖聚類算法的研究，對于噪聲的移除本文使用的是改進的FCM算法，該算法對數(shù)據(jù)做統(tǒng)計峰值檢測，通過數(shù)據(jù)領(lǐng)域平滑來去除噪聲。將FCM算法和自然鄰居圖結(jié)合起來，可以減少時間復雜度，避免參數(shù)的影響并且可以去除噪聲，使聚類的結(jié)果更加準確。2相關(guān)理論概述2.1圖論圖論涉及的理論知識、內(nèi)容較多，如今計算水平的快速發(fā)展，圖論與數(shù)學理論相結(jié)合，使得圖論成為人們生產(chǎn)生活的主要技術(shù)之一，用來對網(wǎng)絡間的關(guān)系分析。通常網(wǎng)絡可看作多個節(jié)點以某種固定方式相互連接形成的圖，以點對網(wǎng)絡上的不同節(jié)點表示，利用連接點的邊對網(wǎng)絡上各節(jié)點間的關(guān)系進行表示。如今人們的思維模式發(fā)生變化，圖論在各個領(lǐng)域全面應用，將圖作為工具可精準、迅速的處理問題。同時在交通運輸、管理、計算機科學、社交科學等多個方面均體現(xiàn)出圖論的價值。2.1.1圖的基本概念圖分為有向圖和無向圖，以(V,E)有序二元組進行表示，E與V分別為圖的邊、頂點。定義圖為G=(V,E)，e=(u,v)一條邊表示頂點u與e，兩點相互關(guān)聯(lián)，可表示u,v是e上的端點，而u,v為相鄰點。若e有方向，將其稱之為有向邊，相反是無向邊。圖G上若一條邊關(guān)聯(lián)的兩個頂點是重合的則會形成一個環(huán)，如果圖G沒有環(huán)，將其稱作簡單圖。頂點的度用于對頂點v邊的數(shù)量表示，即d(v)，在實際問題中，如果圖上的邊均設(shè)定一個有關(guān)的數(shù)，考慮兩地間最短距離的問題，這時需要引入賦權(quán)圖。w(e)表為邊e的權(quán)，即可由G=(V,E,w)來表示賦權(quán)圖，假如使用W、E點對一個城市表示，而邊是連接各城市間的通信線路，在該城市構(gòu)建一個通信網(wǎng)絡，根據(jù)連線上的權(quán)對線路信息流量與長度直觀反映。圖2-1無向無權(quán)圖和有向有權(quán)圖2.1.2圖的鄰接矩陣令G=(V,E)為一個無向圖，V的取值區(qū)間為[V1,V2,...,VN]。頂點I與J間的邊數(shù)由A[I,J]直接表示。G鄰接矩陣的基本性質(zhì)如下，該矩陣屬于n階方陣，對其綜合分析即可獲得，下圖2-2為鄰接矩陣，圖2-3為基于網(wǎng)絡結(jié)構(gòu)的鄰接矩陣圖。圖鄰接矩陣: （2-1） （2-2）上述公式能夠由下圖表示：圖2-2圖表示鄰接矩陣網(wǎng)絡的鄰接矩陣： （2-3）其中Wij為權(quán)值，的表示允許范圍內(nèi)大于權(quán)值的數(shù)。 （2-4）上述公式可由下圖表示： 圖2-3網(wǎng)絡表示鄰接矩陣2.1.3自然鄰居圖將數(shù)據(jù)集表示為圖對于聚類局部和非線性模式很有用。從給定的數(shù)據(jù)集構(gòu)造圖有許多方法:完全連通圖、ε-連通圖和k-最近鄰圖。在完全連通圖中，任意兩點之間都有一條邊，所有邊的權(quán)值都是用高斯核函數(shù)統(tǒng)一計算的。然而，這種方法不僅增加了時間復雜度，而且需要人工確定高斯核的方差參數(shù)δ。ε-連通圖連接成對距離小于ε的所有點。顯然，合適的ε值很難確定。k-最近鄰圖，若一個對象是另外對象的最近鄰集，需要在該對象間建立一條邊，然而，k必須手動確定?？紤]到以上方法的不足，本次研究將利用自然鄰居的概念構(gòu)造自然鄰居圖。自然鄰居穩(wěn)定結(jié)構(gòu)是一個來自客觀現(xiàn)實的新概念，它受到人類社會人際關(guān)系的啟發(fā)，即一個人真正的朋友的數(shù)量應該是把他/她作為朋友并同時被他/她視為朋友的人數(shù)。自然鄰居穩(wěn)定結(jié)構(gòu)的關(guān)鍵思想是位于稀疏區(qū)域的物體具有低能量，而位于密集區(qū)域的物體具有高能量?；谝陨详愂?，數(shù)據(jù)對象的自然鄰居穩(wěn)定結(jié)構(gòu)可以表述如下:(?xi)(?xj)(k∈N)∧(i=j)→(xi∈NNk(xj))∧(xj∈NNk(xi))其中NNk(xi)是物體xi的第k個最近鄰居。xi點的k個最近鄰是D中d(xi，x)≤d(xi，o)的一組點x。自然鄰居穩(wěn)定結(jié)構(gòu)的形成是這樣實現(xiàn)的:不斷擴大鄰居搜索范圍k，同時計算每個對象的反向鄰居數(shù)。迭代的停止標準是所有對象均存在反向鄰居，這時k搜索區(qū)間是自然鄰居上的λ特征值。對于每個對象x，自然鄰居是k個最近的鄰居，k等于自然特征λ，表示為NaN(x)。自然近鄰不同于傳統(tǒng)的k近鄰，自然近鄰穩(wěn)定結(jié)構(gòu)的整個計算過程可以在沒有任何參數(shù)的情況下自動完成。2.2聚類概述聚類基于一定標準分割一個完整的數(shù)據(jù)集為多個簇或者類，導致相同簇中的數(shù)據(jù)對象存在較大相似性，且未在相同簇內(nèi)的對象之間也具有較大差別，也就是最大限度的聚集經(jīng)過聚類操作后的相同類型數(shù)據(jù)，分離類型不同的數(shù)據(jù)。聚類是機器學習中的一種無監(jiān)督學習方法。2.2.1聚類分析近幾年數(shù)據(jù)挖掘中應用較多的算法為聚類分析，也受到社會各界的廣泛關(guān)注，推動聚類分析在各個領(lǐng)域廣泛應用，如今主要在地理學、模式識別、機器學習、研究氣候等方面運用聚類分析方法。運用以往的聚類算法聚類研究多維、離散及多種類型的數(shù)據(jù)，取得的效果不盡人意，而馬氏距離、歐式距離算法，或者對各點簇間距離計算的方式，經(jīng)過計算取得的結(jié)果均會造成聚類結(jié)果出現(xiàn)一定偏差。由于傳統(tǒng)聚類算法存在缺陷，在聚類分析離散數(shù)據(jù)時應用最多的分析方式為基于圖的聚類算法。2.2.2主要聚類方法聚類分析的研究有很長的歷史，形成多種計算方式，常見的有基于層次、基于劃分、及基于密度等多種聚類方法。1、基于劃分的聚類方法基于劃分的聚類方式在應用時要結(jié)合目標函數(shù)將全部數(shù)據(jù)分為一個聚類數(shù)量固定的分組，目前應用最多是的K均值聚類算法，簡稱K-means算法，該算法操作簡單、高效成為各領(lǐng)域應用的首選REF_Ref13775\r\h[7]。但是K-means算法有兩個致命的缺陷。首先，集群的數(shù)量需要提前手動確定。第二，由于初始聚類中心是隨機選擇的，很容易陷入局部最優(yōu)解。2、基于層次的聚類方法基于層次的聚類方法是以數(shù)據(jù)集分解成樹為主要的研究形式，該方法中的數(shù)據(jù)點采用節(jié)點進行表示的，其中的葉子節(jié)點是數(shù)據(jù)點，采用相似的程度對中間節(jié)點進行表示，將不相同的層次數(shù)分割，實現(xiàn)理想的聚類效果，該方法為聚類結(jié)構(gòu)進行了直觀的展示。根據(jù)該算法運用樹結(jié)構(gòu)有效處理數(shù)據(jù)集，并將一個聚類保存在葉節(jié)點，以半徑與中心進行直接表示，并依照一定次序?qū)θ繉ο筇幚?，將其劃分到距離最短的節(jié)點上，此類算法可當作其他聚類算法上的預處理流程，然而也存在不足之處，主要是得到的高維數(shù)據(jù)具有不理想的特征效果，同時有較高的時間復雜性。3、基于密度的聚類方法基于密度的聚類方法在各種算法中最典型，算法中數(shù)據(jù)點與其最近的鄰居聚集在一起，孤立在低密度區(qū)域的數(shù)據(jù)點被稱為離群點。典型的基于密度的聚類方法DBSCAN算法雖然可以檢測任意形狀的聚類和離群點，但DBSCAN的性能取決于用戶確定的掃描半徑Eps和密度閾值MinPts。3基于圖聚類的FCM算法1981年Bezdek與Dunn兩位學者第一次提出模糊C均值聚類算法，即FCM算法，本算法正式發(fā)布后專家學者爭相研究，也獲得諸多顯著成果，如今在數(shù)據(jù)挖掘等領(lǐng)域中應用較多。3.1FCM算法概述通過量模擬聚類的理念引入C均值算法在改進后形成模糊C均值算法，即FCM算法，本方法可將C均值算法的數(shù)據(jù)硬性劃分轉(zhuǎn)化柔性的模糊劃分。FCM算法運行期間會縮短各聚類數(shù)據(jù)間的相似性，一直到目標函數(shù)達到條件后停止。FCM算法可以更好的處理像素分類準確性差問題，在市場上應用較多，然而初始化聚類中心會直接影響聚類效果。3.1.1FCM算法的實現(xiàn)步驟本文研究先將數(shù)據(jù)集xj(j=1,2,...,n)劃分為子集Gi(i=1,2,...,c)，并計算聚類中心c，依據(jù)相似性準則對子集再次劃分，經(jīng)過多次操作與劃分后得到一個非相似性指標的目標函數(shù)，該目標函數(shù)達到最小值則算法停止。下列公式(3-1)計算目標函數(shù)。 （3-1）FCM算法的一般步驟為：

第一步：確定分類數(shù)，確定迭代次數(shù)；

第二步：初始化一個隸屬度（和為1）；

第三步：根據(jù)隸屬度計算聚類中心；

第四步：計算目標函數(shù)；

第五步：根據(jù)求出的聚類中心返回去計算隸屬度，回到第三步，一直循環(huán)直到求得的目標函數(shù)達到最小值。FCM算法應用時并非一次就可以實現(xiàn)，要經(jīng)過多次迭代與重復運行后才能得到想要的結(jié)果，但是該方法難以確保獲得的結(jié)果即為最優(yōu)解，同時所選的c初始聚類中心也會影響最后算法的性能與結(jié)果，因而要多次對比運算才能取得較為理想的運算結(jié)果，選用效果理想的值當作聚類中心。3.1.2隸屬度函數(shù)概述隸屬度函數(shù)可以對對象x隸屬于集合A實際狀態(tài)反映，也是一種表現(xiàn)真實程度的函數(shù)，即A(x)，集合A上的所有對象均屬于自變量，其取值區(qū)間為[0,1]，0≤U（X）≤I。A(x)隸屬度結(jié)果十分趨近于1的情況下，x是集合A中內(nèi)容的隸屬度更高。A(x)隸屬度值逐漸趨于0，表達的意思是x是集合A內(nèi)容的可能性越小。針對有限元對象(x1,x2,...,xn)，模糊集合可以表示為式（3-2）所示。 （3-2）在式(3-3)中，多次迭代運算之后成功劃分聚類。[0,1]區(qū)間內(nèi)的值，一個元素x作為集合A上的元素的非硬性規(guī)定，聚類過程中元素x經(jīng)過多次計算后會向隸屬度較高的模糊集合上劃分，計算得出的全部樣本元素x存于集合A的隸屬度，究其根本是x的取值范圍。在本次研究中，用值在[0,1]區(qū)間內(nèi)的隨機數(shù)初始化隸屬矩陣，使其滿足條件和為1。3.2算法對噪聲的處理對于模糊聚類算法來說，對各數(shù)據(jù)簇中心拉扯力較大的是離群的噪聲點，它們會使得各數(shù)據(jù)簇中心發(fā)生偏移。在現(xiàn)有的模糊聚類算法研究中，很多聚類算法都是利用對隸屬度約束條件的放寬，去達到該目標。實際情況下針對噪聲界定屬于無監(jiān)督學習領(lǐng)域的重大難題，該情況下的樣本點無標簽信息，僅僅能經(jīng)過其間距來判斷樣本點間的關(guān)聯(lián)性。若某個樣本點附近有大量的鄰近樣本點存在時，可以識別出其與附近的樣本點具有一定的相似性。當這一樣本點被當作噪聲，則附近樣本點也會被當作噪聲。而運用聚類算法，那么這群樣本點就會形成新的數(shù)據(jù)簇，在算法中這群樣本點就不會被當作噪聲，造成了數(shù)據(jù)集中部分信息的缺失，綜上所述模糊的聚類算法在解決這類問題上主要時降低數(shù)據(jù)簇的隸屬度值，進而將這些噪聲數(shù)據(jù)的影響降低。本次研究通過計算數(shù)據(jù)集中樣本點之間的距離，為噪聲點分配較低的隸屬度，在自然鄰居圖中將低隸屬度的樣本點視為噪聲點，把噪聲點和連接到該點的邊都從自然鄰居圖中移除以達到檢測和去除噪聲的目的。下列為帶有噪聲去除的FCM算法基本流程:第一步:在初始聚類中心ci上隨機選取一個值，i的取值區(qū)間為1,,c；第二步:根據(jù)自然鄰居圖用歐式距離算法計算每組數(shù)據(jù)中的樣本點之間的距離，將與其他樣本點的距離遠大于距離平均值的樣本點標為噪聲樣本點；第三步:初始化隸屬度矩陣U，為噪聲點分配最低的隸屬度值，基于該矩陣重新分列數(shù)據(jù)；第四步:從自然鄰居圖中把噪聲點和連接到該點的邊移除；第五步:求出精準的目標函數(shù)，假如取得的結(jié)果顯示收斂需要停止使用本方法；第六步:使用同一個聚類中的數(shù)據(jù)加權(quán)均值作為本次求解的聚類中心，明確后即可跳轉(zhuǎn)到以上第二步。4基于MATLAB的圖聚類算法仿真模擬4.1基于MATLAB的圖聚類算法仿真Matlab的圖聚類算法具有工作和編程效率高，其作為目前一種先進的計算語言，能夠?qū)崿F(xiàn)數(shù)學形式的編程。在這些優(yōu)點的基礎(chǔ)之上，Matlab有著高效的編寫速度和很好的工作效率。同時對于用戶也有著較好的使用體驗，其中的庫函數(shù)和用戶信息具有一致性，使得用戶文件可以很方便的被調(diào)用。本次仿真的實驗環(huán)境是MatlabR2016a。實驗數(shù)據(jù)是如圖所示的加噪聲數(shù)據(jù)和不含噪聲數(shù)據(jù)：圖4-1實驗數(shù)據(jù)算法流程圖如下：數(shù)據(jù)載入數(shù)據(jù)載入轉(zhuǎn)化成自然鄰居圖完成數(shù)據(jù)切割與噪聲的去除圖聚類算法處理結(jié)果分析圖4-2圖聚類算法流程圖數(shù)據(jù)經(jīng)過自然鄰居圖的轉(zhuǎn)化，然后進行數(shù)據(jù)分割，產(chǎn)生的圖像再經(jīng)過圖聚類算法的處理，最終完成數(shù)據(jù)分析。4.2仿真結(jié)果圖4-3原始數(shù)據(jù)加載圖4-4形成自然鄰居圖圖4-5進行數(shù)據(jù)切割前設(shè)置參數(shù)不同的數(shù)據(jù)切割參數(shù)得出的切割結(jié)果是不同的，這里選擇的參數(shù)為0.1和0.2。圖4-6數(shù)據(jù)切割參數(shù)0.1結(jié)果圖4-7切割參數(shù)為0.2時的結(jié)果圖4-8無噪聲數(shù)據(jù)的圖聚類結(jié)果圖4-9有噪聲數(shù)據(jù)的圖聚類結(jié)果總結(jié)與展望通過對實驗結(jié)果的分析，我們可以得出：聚類分析效果可得，本算法再多次合并、刪除聚類中心數(shù)據(jù)后，保留聚類中心上關(guān)聯(lián)像素數(shù)量較多的部分，且該聚類中心大部分來源于像素灰度值非常集中的區(qū)域，導致此后圖像分割期間出現(xiàn)各種誤分割、噪聲點數(shù)量較多等問題，造成許多與特征值相應的像素難以在同一個區(qū)域劃分，同時嚴重影響圖像成像效果、灰度值集中度較高的區(qū)域也無最佳的聚類中心。但是對于對比度較高的噪聲還是有明顯的濾除效果。參考文獻賀貴明，吳元保，蔡朝暉.基于內(nèi)容的視頻編碼與傳輸控制技術(shù)[M].武漢大學出版社，2005.侯葉.基于圖論的圖像分割技術(shù)研究[D].西安電子科技大學，2011.林瑤，田捷.醫(yī)學圖像分割方法綜述[J].模式識別與人工智能，2002,15(2):192一204.秦蟬蟬.基于隨機游走算法的圖像分割方法研究[D].華中師范大學，2014.AzzouzEE,NandiAK.Automaticidentificationofdigitalmodulationtypes[J].SignalProcessing,1995,47:55-69.NandiAK,AzzouzEE.Automaticanaloguemodulationrecognition[J].SignalProcessing,1995,46:211-222.葉敏超，錢沄濤，沈言浩.基于聚類的圖像稀疏去噪方法[J].信號處理,2011(10):1593-1598.袁小軍，周濤，李琛.基于稀疏先驗的非局域聚類圖像去噪算法研究[J].計算機工程與應用,2020,56(18):177-186.NazliTekin，VehbiCagriGungor，Theimpactoferrorcontrolschemesonlifetimeofenergyharvestingwirelesssensornetworksinindustrialenvironments，P198-113，2010.TheodoreS.Rappaport.Wirelesscommunicationsprinciplesandpractice[M].Beijing:PublishingHouseofElectronicsIndustry.1998.張忠培，魏寧，史治平編著.協(xié)同無線通信導論[M].北京:電子工業(yè)出版社，20-31.SendonarisA.,ErkipE.,andAazhangB.,Usercooperationdiversity-partI:Systemdescription[J],IEEETransactionsCo