基于閾值參數距離的模糊C均值聚類算法及應用

劉敏，杜軍

（空軍工程大學，西安　710138）

基于閾值參數距離的模糊C均值聚類算法及應用

劉敏，杜軍

（空軍工程大學，西安710138）

0　引言

縱觀人類歷史的發(fā)展歷程，知識總是來自于對自然界和社會中新事物、新現象的認識與研究，分類一直是最原始且最直觀的一種認識活動。所謂分類，就是人們?yōu)榱苏J知一種新事物或新現象，通過盡可能多的列舉其固有屬性與特征并在此基礎上與已知的其他事物或現象進行比較，以若干既定的標準和規(guī)則來衡量新舊事物或現象間的相似性的活動。狹義的聚類分析（或劃分）屬于硬聚類，其分類規(guī)則具有很強的唯一性，即某個對象屬于且僅屬于某個特定的類，簡單而言就是“非此即彼”。但在實際情況中，我們往往無法對事物間紛繁復雜的關系給出確定的度量，即類別界限的劃分往往是“模糊”的。1969年，Ruspini最先開始對模糊聚類進行了系統(tǒng)的表述和研究［1］，由此開啟了模糊聚類分析的浪潮。

1　模糊C均值聚類（FCM）算法

自從Ruspini提出模糊劃分概念并把模糊集理論引入到聚類分析之后，來自世界各地的研究者們在此基礎上提出了許多種模糊聚類分析方法，主要包括基于模糊等價關系的傳遞閉包方法［2-3］、基于相似性關系和模糊關系的方法［4］、模糊圖論的最大數方法［5］以及基于數據集的凸分解［6］、動態(tài)規(guī)劃［7］和難以辨識關系等方法。以上幾種模糊聚類算法共有的一個弊端是計算非常復雜，應用時往往難以落到實處，而計算量相對簡單的基于目標函數的聚類方法開始獲得研究者的青睞。在眾多基于目標函數的聚類算法中，最典型且應用最廣泛的是模糊C均值（FCM）算法。

算法通過最小化基于類內平方誤差和（WGSS）范數和聚類原型的目標函數將沒有標簽的數據進行分類。令X=｛x1，x2，…，xn｝?R表示給定的樣本集合，s是樣本空間的維數，n是樣本個數，c（c＞1）是對X進行劃分的聚類個數。FCM算法可以描述如下：

上式中：m＞1是模糊系數；U=uij是一個c×n的模糊劃分矩陣，uij是第j個樣本xj屬于第i類的隸屬值；V=是由c個聚類中心向量構成的s×c的矩陣；表示從樣本點xj到中心點vi的距離，本文采用的是歐氏距離。這是一個關于自變量（U，V）約束優(yōu)化問題，利用極值點的KT必要條件可以得到如下的迭代方程：

若Ij≠?，則uij是滿足如下條件的任意非負實數：

2　基于閾值參數距離的模糊C均值聚類（TFCM）算法

在工業(yè)領域中，模糊聚類的方法被創(chuàng)造性地應用到故障診斷中。實際的故障模式診斷過程中，我們在模糊聚類分析時通常采用的分類原則是：（1）若待分類樣本到各個類的歐氏距離之間差別不大，我們則認為該樣本與所有類之間都存在隸屬關系，隸屬度函數等同于傳統(tǒng)的FCM算法；（2）若待分類樣本到某幾類的歐氏距離相對較小，而到其他若干個類的歐氏距離差別不大，我們則認為該樣本與這些類之間都存在隸屬關系，且隸屬度函與樣本和類間的歐氏距離相關聯；（3）若待分類樣本與某一類的歐氏距離遠小于它與其他故障類的距離，我們則認為樣本僅屬于該類。通過對樣本與類間的距離尺度的篩選，使距離類中心比較遠的樣本點對該類的隸屬度為0，這在一定程度上可以剔除樣本中的野值，降低樣本數據的噪聲對聚類結果的不利影響，對算法的魯棒性也有所改善。大多數可信度較高的樣本點的隸屬度和樣本與類間歐氏距離相關，這也更符合故障分類的實際情況。為了對數據中樣本與各聚類中心的歐氏距離差異化處理，我們預先設定一個閾值參數，通過比較歐氏距離與閾值的大小對樣本進行初步篩選，根據篩選結果對隸屬函數進行調整。為方便起見，我們使用如下的閾值參數距離：

定義如下集合：相對歐氏距離非正的類別集合：

相對歐氏距離為負的類別集合：

相對歐氏距離最小的類別集合：

以下討論模糊加權指數m在不同范圍取值時的算法情況。

（1）當m=1時，算法為傳統(tǒng)硬聚類，有劃分矩陣

（2）當m＞1時，需要分兩種情況討論：

式（3）最優(yōu)的一階必要條件為：

由約束條件有：

解得：

即:

可見，算法為傳統(tǒng)FCM算法，有劃分矩陣：

②如果NIk≠?，則有iNIk，uik=0。式可轉化為：

約束條件轉化為：

顯然，由于m＞1且對i∈NIk，dik≤0，所以是｛uik|i∈NIk｝的凹函數，因此｛uik|i∈NIk｝只能在可行域的邊界上取值，且：

可見，當m＞1時，以上兩種情況都無法實現半模糊劃分。

（3）當0＜m＜1時，也分兩種情況討論：

①如果NIk=?，必有dik≥0，1≤i≤c，所以所示的目標函數Jm'是Uk=（u1k，u2k，…，uck）'的凹函數，因此最優(yōu)解｛uik|i∈NIk｝只能在可行域的邊界上取值，且：

②如果Nk≠?，則有iNIk，uik=0。上式可轉化為：

約束條件轉化為：

由于對?i∈Nk，dik＜0，以及0＜m＜1，所以式是Uk= （u1k，u2k，…，uck）'的凸函數，而約束條件給出的可行域也為凸函數，因此這是一個凸規(guī)劃問題?？捎肔agrange乘子法來求解，引入乘子，并建立Lagrange函數：

其最優(yōu)的一階必要條件為：

由約束條件有：

解得：

即:

由此可得:

由上式可知，當0＜m＜1時，基于隸屬函數的模糊聚類改進算法具有了“半模糊”的特性，具體表現為：樣本對其相對歐氏距離的中心點對應的類的隸屬度為0，對其相對歐氏距離的中心點對應的類的隸屬度互不相同。

TFCM聚類算法的迭代過程簡述如下：首先判斷一個樣本xk與各個類間的相對歐氏距離是否非正，若為正，則樣本xk屬于與其相對歐氏距離最小的中心點對應的類（即傳統(tǒng)的硬聚類）；若為負，則樣本xk與此類間都有隸屬關系。

迭代目的是尋找一組中心矢量使得類內加權平均誤差和函數最小，因此可以將迭代的過程視為目標函數逐漸減小的過程，那么閾值參數η理應隨著迭代次數的增加而減小。同時要確保閾值參數η趨近于0，即，這樣才能確保得到最終的聚類結果。

對于閾值參數η相對迭代次數的遞減方式，我們分別選擇平穩(wěn)下降和凹狀遞減下降兩種方式，其中，平穩(wěn)遞減方式采用正比例下降規(guī)律，選取的閾值函數η（t）如下：

令Tmax為算法的最大迭代次數，η（0）為初始閾值，閾值隨著迭代遞減：

凹狀遞減方式采用反函數下降規(guī)律，選取的閾值函數η（t）如下：

FCM算法目標函數和兩種下降方式下閾值參數變化曲線如圖1所示。

由圖1可以看出，相對當凹狀遞減方式而言，平穩(wěn)遞減方式閾值參數η下降速度更緩慢。由于迭代初期目標函數隨迭代次數的下降速度比平穩(wěn)遞減方式下閾值參數的下降速度快，因此會導致閾值參數距離普遍為負值繼而使大量的樣本被確定地劃分到與其歐氏距離最小的類中，即隸屬度函數出現邊界分化現象；而凹狀遞減方式下閾值參數的下降速度始終比目標函數下降速度快，因此可以避免邊界分化現象的發(fā)生。故而本章中我們對閾值參數η的選取原則是隨著迭代次數的增加呈現凹狀遞減方式。

圖1　FCM算法目標函數與兩種下降方式下閾值參數變化曲線

3　仿真結果

人工構造一組包含300個樣本的數據data_4_1，共分為三類，每類樣本數各100個并呈正態(tài)分布，分布中心坐標分別為（2，4），（4，2），（3，3）。分別采用FCM算法和TFCM算法的進行分類試驗。其中，FCM算法初始化參數為：其中，FCM算法初始化參數為：c=3，m= 2，Tmax=50，TFCM算法初始化參數為：c=3，m=0.7，Tmax= 50，η（0）=1。聚類結果圖2所示。

由圖2可以看出，FCM與TFCM算法對于人造數據集data_4_1的聚類結果完全一致，但聚類中心位置稍有差異。將兩種算法得到的聚類中心與實際聚類中心對比如圖2所示，由圖2我們可以看出，FCM算法得到的聚類中心相對的實際聚類中心而言更加集中，而TFCM算法得到的聚類中心之間更為分散。這是因為FCM算法對樣本與類間的距離不作考慮而進行的無差別分類的結果，但TFCM算法將樣本與類間的距離作為隸屬度的一個重要的衡量標準，在一定程度上克服了無差別分類帶來的盲目性。

FCM算法與TFCM聚類算法的目標函數對比如上圖3所示：由圖4可以看出，隨著迭代次數的增加，目標函數一直下降至迭代閾值，且TFCM算法相比FCM算法收斂速度更快。

我們取用標準數據Iris（鳶尾草植物）作為測試樣本集。仿真參數設置如下：FCM算法初始化參數為：c= 3，m=2，Tmax=50，TFCM算法初始化參數為：c=3，m= 0.75，Tmax=50，η（0）=18。聚類結果如表1所示：由表1可以看出，TFCM算法相比較FCM算法而言，其聚類進度和收斂速度更好。

圖2　 FCM算法與TFCM算法聚類結果對比

圖3　 FCM算法與TFCM算法聚類中心對比　

圖4　 FCM算法與TFCM算法聚類目標函數對比

表1數據組的類中心統(tǒng)計結果

4　結語

本文提出了一種基于閾值參數距離的TFCM算法，通過引入閾值參數對樣本與類間歐氏距離進行分段使得FCM算法的隸屬函數更加合理，數據仿真實驗驗證了TFCM算法相比較傳統(tǒng)的FCM算法具有更好的收斂性與聚類準確性。

［1］Ruspini E H.A new approach to clustering［J］.Information and control，1969，15（1）:22-32.

［2］Dunn J C.A graph theoretic analysis of pattern classification via tamura's fuzzy relation［J］.IEEE Trans.SMC，1974，4（3）:310-313.

［3］Zkim Le.Fuzzy relation compositions and pattern recognition［J］.IEEE Trans.Fuzzy Syst.，1993，1（2）:98-110.

［4］Backer E，Jain A.A clustering performance measure based on fuzzy set decomposition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1981，PAMI-3（1）:66-75.

［5］Leahy R，Wu Z.An optimal graph theoretic approach to data clustering:theory and it's application to image segmentation［J］.IEEE Trans on PAMI，1993，15（11）:1101-1113.

［6］Esogbue A O.Optimal clustering of fuzzy data via fuzzy dynamic programming［J］.Fuzzy Sets and Systems，1986，（18）:283-298.

［7］Harris J O，Bezdek J C.Convex decompositions of fuzzy partitions［J］.J.Math.Anal.&Appl，1979.

Threshold Parameter；Fuzzy Clustering；FCM；Half Fuzzy

Fuzzy C Means Clustering Algorithm Based on Distance Threshold Parameter and Application

LIU Min，DU Jun
（Air Force Engineering University，Xi'an 710138）

1007-1423（2015）29-0021-06

10.3969/j.issn.1007-1423.2015.29.006

劉敏（1992-），男，安徽合肥人，在讀碩士研究生，研究方向為智能檢測與健康狀態(tài)監(jiān)控

2015-10-09

2015-10-20

針對提出一種基于閾值參數距離的模糊C均值聚類算法，其思想是在對設定閾值參數對樣本數據到聚類中心的距離進行分段，距離大于閾值參數的點相對聚類中心的隸屬度為0，距離小于閾值參數的點相對聚類中心的隸屬度不同且服從特定的隸屬函數。理論推導該算法有效時模糊度指數應介于0到1之間，仿真結果表明該算法相比較傳統(tǒng)的FCM算法具有更好的收斂性與聚類準確性。

閾值參數；模糊聚類；FCM；半模糊

杜軍（1974-），男，山西運城人，博士，教授，研究方向為智能檢測與健康狀態(tài)監(jiān)控

Presents a kind of fuzzy C Means clustering algorithm based on distance threshold parameter is in.The attach degree of distance greater than the threshold value of the parameter point opposite the center of the cluster will be 0，oppositely belong with an approach function since the distance less than the threshold value of the parameter point opposite the center of the cluster by setting a threshold parameter. Theoretical derivation of the algorithm is effective when ambiguity index should be between 0 and 1.Simulation results show that the algorithm has better convergence and clustering accuracy compared to traditional FCM algorithm.