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

劉敏，杜軍

（空軍工程大學(xué)，西安　710138）

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

劉敏，杜軍

（空軍工程大學(xué)，西安710138）

0　引言

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

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

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

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

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

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

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

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

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

相對(duì)歐氏距離為負(fù)的類別集合：

相對(duì)歐氏距離最小的類別集合：

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

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

（2）當(dāng)m＞1時(shí)，需要分兩種情況討論：

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

由約束條件有：

解得：

即:

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

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

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

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

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

（3）當(dāng)0＜m＜1時(shí)，也分兩種情況討論：

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

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

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

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

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

由約束條件有：

解得：

即:

由此可得:

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

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

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

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

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

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

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

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

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

3　仿真結(jié)果

人工構(gòu)造一組包含300個(gè)樣本的數(shù)據(jù)data_4_1，共分為三類，每類樣本數(shù)各100個(gè)并呈正態(tài)分布，分布中心坐標(biāo)分別為（2，4），（4，2），（3，3）。分別采用FCM算法和TFCM算法的進(jìn)行分類試驗(yàn)。其中，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算法對(duì)于人造數(shù)據(jù)集data_4_1的聚類結(jié)果完全一致，但聚類中心位置稍有差異。將兩種算法得到的聚類中心與實(shí)際聚類中心對(duì)比如圖2所示，由圖2我們可以看出，F(xiàn)CM算法得到的聚類中心相對(duì)的實(shí)際聚類中心而言更加集中，而TFCM算法得到的聚類中心之間更為分散。這是因?yàn)镕CM算法對(duì)樣本與類間的距離不作考慮而進(jìn)行的無差別分類的結(jié)果，但TFCM算法將樣本與類間的距離作為隸屬度的一個(gè)重要的衡量標(biāo)準(zhǔn)，在一定程度上克服了無差別分類帶來的盲目性。

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

我們?nèi)∮脴?biāo)準(zhǔn)數(shù)據(jù)Iris（鳶尾草植物）作為測試樣本集。仿真參數(shù)設(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算法而言，其聚類進(jìn)度和收斂速度更好。

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

圖3　 FCM算法與TFCM算法聚類中心對(duì)比　

圖4　 FCM算法與TFCM算法聚類目標(biāo)函數(shù)對(duì)比

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

4　結(jié)語

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

［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-），男，安徽合肥人，在讀碩士研究生，研究方向?yàn)橹悄軝z測與健康狀態(tài)監(jiān)控

2015-10-09

2015-10-20

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

閾值參數(shù)；模糊聚類；FCM；半模糊

杜軍（1974-），男，山西運(yùn)城人，博士，教授，研究方向?yàn)橹悄軝z測與健康狀態(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.