劉敏，杜軍

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

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

劉敏，杜軍

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

以下討論模糊加權(quán)指數(shù)m在不同范圍取值時的算法情況。

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

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

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

由約束條件有：

解得：

即:

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

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

約束條件轉(zhuǎn)化為：

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

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

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

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

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

約束條件轉(zhuǎn)化為：

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

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

由約束條件有：

解得：

即:

由此可得:

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

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

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

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

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

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

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

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

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

3　仿真結(jié)果

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

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

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

我們?nèi)∮脴藴蕯?shù)據(jù)Iris（鳶尾草植物）作為測試樣本集。仿真參數(shù)設置如下：FCM算法初始化參數(shù)為：c= 3，m=2，Tmax=50，TFCM算法初始化參數(shù)為：c=3，m= 0.75，Tmax=50，η（0）=18。聚類結(jié)果如表1所示：由表1可以看出，TFCM算法相比較FCM算法而言，其聚類進度和收斂速度更好。

圖2　 FCM算法與TFCM算法聚類結(jié)果對比

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

圖4　 FCM算法與TFCM算法聚類目標函數(shù)對比

表1數(shù)據(jù)組的類中心統(tǒng)計結(jié)果

4　結(jié)語

本文提出了一種基于閾值參數(shù)距離的TFCM算法，通過引入閾值參數(shù)對樣本與類間歐氏距離進行分段使得FCM算法的隸屬函數(shù)更加合理，數(shù)據(jù)仿真實驗驗證了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

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

閾值參數(shù)；模糊聚類；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.