基于中心自動融合的多尺度可能性聚類算法

胡雅婷，左春檉，曲福恒

（1.吉林農(nóng)業(yè)大學 信息技術學院，長春130118；2.吉林大學 機械科學與工程學院，長春130022；3.長春理工大學 計算機科學技術學院，長春130022）

聚類分析是一種以數(shù)據(jù)間的相似性為基礎將未標記數(shù)據(jù)劃分到不同的類別，從而獲得數(shù)據(jù)中的結構分布模式方法，在數(shù)據(jù)挖掘、圖像處理及人工智能等領域應用廣泛［1］.聚類算法主要分為硬聚類與模糊聚類［2－3］兩類.由于模糊聚類方法考慮到樣本點與各類別間的聯(lián)系，聚類結果較硬聚類更客觀，因此已成為聚類分析研究的主流.Krishnapuram等［4－5］在模糊聚類的基礎上提出了可能性c－均值（PCM）聚類算法，PCM算法中的隸屬度值代表樣本屬于各類別的絕對可能性，有效地避免了模糊聚類算法對噪聲和野值敏感的問題.但PCM算法易于產(chǎn)生重合聚類，并對初始化中心和參數(shù)設置非常敏感，作為一種模式搜索算法，當選取的初始聚類中心個數(shù)與數(shù)據(jù)模式個數(shù)不等時，PCM算法將不能自動搜索到數(shù)據(jù)中的所有模式.即使二者相等，多個初始點選取的位置不當也可能導致算法搜索到相同模式，即產(chǎn)生重合聚類問題［5－6］.而以每個數(shù)據(jù)為初始中心進行搜索又會加大計算量，也會影響目標函數(shù)對真正模式位置的搜索.中心自動融合機制［6］是為了解決參數(shù)選擇和初始化問題而提出的，以所有的數(shù)據(jù)點作為初始模式，根據(jù)原始的數(shù)據(jù)結構自組織聚類結構，有效解決了PCM算法中存在的問題.

自然界中多數(shù)數(shù)據(jù)集合都具有不同尺度的聚類結構，即在較大類別中還包含了較小類別的嵌套結構.為能分離出不同的類別結構，識別出類別間的交叉點，保證類別的光滑連續(xù)性，尤其能夠識別出通過交點的不同類別［7］，需要設計一種適用于具有多種尺度結構數(shù)據(jù)集合的有效聚類算法.本文通過在原始可能性聚類中引入多尺度因子控制聚類的尺度，采用自動融合機制自動搜索聚類模式并確定聚類數(shù)目，提出一種基于中心自動融合的多尺度可能性（multi－scale possibilistic clustering algorithm based on automatic center merging，MPC－ACM）聚類算法.MPC－ACM算法根據(jù)數(shù)據(jù)集合的結構特點自適應地組織聚類結構，并自動確定聚類數(shù)目，且算法中的多尺度因子還可獲得不同尺度下的聚類劃分.多尺度因子的引入增加了算法的可控性與靈活性，使其具有更廣的使用范圍，并從理論上給出多尺度因子的多尺度性質證明，最后在人造數(shù)據(jù)集和滾動軸承故障數(shù)據(jù)上進行實驗分析.

1 可能性聚類算法

設由n個數(shù)據(jù)點構成的數(shù)據(jù)集合X的c－劃分可表示為一個c×n階矩陣U＝（uij），其中c為聚類個數(shù).對應于集合X，可能性聚類、模糊聚類與硬聚類產(chǎn)生的c－劃分空間分別由下式表示［8］：

通過最小化目標函數(shù)JPCM獲得PCM聚類模型［4－5］：

得到滿足最優(yōu)解的兩個必要條件：

將式（5）和式（6）迭代直至收斂得到滿足式（4）的一個（局部）最優(yōu)解.其中：U＝（uij）表示可能性劃分矩陣；V＝｛v1，v2，…，vc｝??s表示聚類模式（中心）集合；c表示聚類數(shù)目；m表示模糊系數(shù)；ηi表示需要用戶定義的參數(shù).PCM算法的隸屬度值表示樣本屬于各類別的絕對可能性，可較好抑制噪聲產(chǎn)生的影響.但算法存在易于產(chǎn)生重合聚類的不足，并對初始化模式（中心）及參數(shù)ηi非常敏感.

2 MPC－ACM 算法

2.1 中心自動融合機制

MPC－ACM算法對具有較高相似度的中心按設定的準則進行自動融合，這種自動融合機制［6］將全體模式作為初始的搜索點（初始化聚類中心），在迭代過程中動態(tài)地改變聚類個數(shù)與聚類結構.在某個迭代中，若當前兩個搜索點的相關性非常高，則認為這兩個搜索點來源于同一個聚類，將其進行合并操作，其中關鍵是相關度的確定.本文采用文獻［6］的方法，根據(jù)兩個點屬于其他所有聚類隸屬度向量的相關性定義其相關度大小.

設U＝（uij）c×n＝（u1，u2，…，uc）T，R＝（ril）c×c表示相關性矩陣，則有

類的合并準則建立在相關系數(shù)矩陣R上.令S＝｛S1，S2，…，Sc｝，其中

由Si的定義可見，它體現(xiàn)了所有聚類中心點與第i個中心vi間的相似程度，如果各中心與vi的距離較近則Si的值較大.因此，Si在一定程度上反映了vi周圍數(shù)據(jù)點的密度.合并操作由密度最大的中心開始，先按各類Si值的大小排序，找到最大值對應的中心vi，其他所有與vi相似度大于ρ的中心合并為一類.設I表示未合并數(shù)據(jù)的指標集合，令

這里

Pc為第c個聚類所有數(shù)據(jù)形成的集合.由于合并會導致類內(nèi)數(shù)據(jù)的增加，因此需要對發(fā)生合并的類中心進行修正，合并后新的聚類中心按下式計算：

本文稱這種中心自動融合機制下的算法為合并算法（merging algorithm，MA），步驟如下：

1）令k＝1，I＝｛1，2，…，c｝；

2）根據(jù)式（7）更新R；

3）根據(jù)式（8）更新S；

4）根據(jù)式（9）更新Em；

5）令I＝I＼Em，如果I≠?，則令k＝k＋1，返回4）；否則，更新cnew＝k；

6）根據(jù)式（10），（11）更新Pnew和Vnew，算法結束.

2.2 MPC－ACM算法流程

為使MPC－ACM算法不僅能對初始化與參數(shù)具有較強的魯棒性，而且同時具有對數(shù)據(jù)的聚類結構進行多尺度分析能力.本文在已有可能性聚類算法PCM中引入一個多尺度因子，通過調節(jié)多尺度因子獲得不同大小的聚類結構.同時，采用自動融合機制進行模式搜索和聚類數(shù)目自動確定，算法實現(xiàn)步驟如下：

1）設置ε，η值，其中ηc＝（η，…，η）1×c；

2）初始化k′＝0，V（0）＝X，U（0）＝f（η，V（0），X）；

3）先根據(jù)U（k）找出V（k′）中相關性大于ρ的中心，利用MA算法對這些中心合并，再根據(jù)式（11）對合并后的中心進行修正得到Vnew；先利用Vnew與式（6）更新U（k′＋1），再利用U（k′＋1）與式（5）更新V（k′＋1）；

4）如果‖V（k′＋1）－V（k′）‖＜ε，則停止；否則，返回3），令k′＝k′＋1.

2.3 多尺度性質

在原始可能性聚類中，ηi與聚類大小相關，用于識別不同體積的聚類.本文MPC－ACM算法中假設ηi為常數(shù)，即ηi＝η（i＝1，2，…，c）.通過調節(jié)η的值，MPC－ACM 算法可得到不同尺度下的聚類結構，本文稱η為多尺度因子.

定理1 設m＞1，ρ∈（0，1），則當η→0＋時，MPC－ACM算法得到數(shù)據(jù)的最小尺度聚類結構，即每個模式自身為一類.

證明：假設X＝｛x1，x2，…，xn｝??s中數(shù)據(jù)不存在重復現(xiàn)象，即當j1≠j2時，必有xj1≠xj2.MPC－ACM算法的初始搜索點是數(shù)據(jù)集合中的任意一點，式（5）表明，當η→0＋時，對任意給定的1≤j≤n，當i≠j時，uij＝0；當i＝j時，uij→1.MPC－ACM算法中的rij→0（i≠j），此時必有rij＜ρ，根據(jù)MA算法可知，不會對任何兩個中心進行合并操作.式（6）表明，中心xj將更新為x′j，且兩者必然滿足‖xj－x′j‖＜ε.根據(jù)MPC－ACM算法的終止條件可知，算法此時停止.由于沒有進行任何合并操作，因此每個模式自身必然為一類.若有重復數(shù)據(jù)，可先把重復數(shù)據(jù)合并為一個數(shù)據(jù)得到同樣的結果，證畢.

定理2 設m＞1，ρ∈（0，1），則當η→＋∞時，MPC－ACM算法得到數(shù)據(jù)的最大尺度聚類結構，即所有模式分為一類.

證明：當η→＋∞時，式（5）表明uij→1（?i，j），又由式（7）可知rij→1（?i，j）.ρ是一個常值，且滿足ρ＜1.由MA算法可知，所有的模式即初始化的聚類中心將被合并為一類，證畢.

定理1和定理2也表明了MPC－ACM算法的多尺度性質.文獻［9］中MPCM算法的多尺度性質來源于均值漂移聚類的帶寬控制，可能性聚類具有輔助調整最終聚類中心的作用；本文MPC－ACM算法的多尺度性質由可能性聚類本身的多尺度因子控制.MPCM算法由于采用了均值漂移聚類，其計算復雜度較高，網(wǎng)格剖分的引入雖然會減少初始迭代中心個數(shù)，降低計算復雜度，但同時會降低聚類精度.即使在不引入網(wǎng)格剖分的前提下，MPC－ACM算法由于在迭代過程中的中心個數(shù)會逐漸減少，必然具有效率優(yōu)勢，且MPC－ACM算法同樣可采用完全相同的“利用網(wǎng)格剖分減少初始迭代點的技術”降低計算復雜度.因此，MPC－ACM算法比MPCM算法更高效.

3 實驗結果及分析

3.1 人造數(shù)據(jù)實驗

圖1為不同聚類算法在具有不同大小聚類結構數(shù)據(jù)集合上的聚類結果.由圖1可見：FCM算法由于對初始化的依賴性較高導致其很難發(fā)現(xiàn)正確的聚類結果，即使FCM算法的初始化中心是正確的，也無法得到真正不同大小的聚類結構，且FCM算法的初始化中心如何選取目前仍沒有合理方法；PFCM算法與FCM算法類似，由于初始化的敏感性導致錯誤的聚類劃分；PCM算法的聚類結果也嚴重依賴于初始化中心的選擇，如圖1（D）所示PCM算法還存在容易產(chǎn)生重合聚類的問題，但算法的模式搜索性質使其正確的確定了4個類中心位置；UPC算法受到初始化、產(chǎn)生重合聚類的影響，其結果最不理想，算法不具備模式搜索性質，產(chǎn)生兩組重合聚類的聚類中心位置與實際偏差較大；本文提出的算法獲得了正確的聚類劃分.

圖1 不同尺寸與個數(shù)的數(shù)據(jù)集聚類結果Fig.1 Clustering results on set of different size and number

下面測試本文算法的多尺度性質.實驗數(shù)據(jù)集具有如圖2（A）所示的多尺度聚類結構，第一級尺度為左右2類，第二級尺度為左上、左下、右上和右下4類，第三級尺度為12個小類.如圖2（B）～（F）所示，當多尺度因子η由大至小逐漸變化時，算法能逐級找到不同尺度下的聚類結構，這也驗證了定理1和定理2.如定理2所述，當尺度因子充分大時，所有數(shù)據(jù)將被劃分為一類.如圖2（B）所示，當η≥10×θ（X）時，所有數(shù)據(jù)被劃分到同一類中.如定理1所述，當尺度因子充分小時，每個不同的數(shù)據(jù)分為一類.如圖2（F）所示，當η≤0.01×θ（X）時，每個數(shù)據(jù)獨立成為一類.因此，尺度因子可控制算法得到的聚類尺度.

3.2 真實數(shù)據(jù)實驗

實驗數(shù)據(jù)源于美國凱斯西儲大學電氣工程實驗室采集的6205－2RS JEM SKF深溝球軸承數(shù)據(jù)［12］.分別選取在正常、內(nèi)環(huán)故障、滾動體故障情況下樣本各473個和外環(huán)故障情況下樣本474個.軸承上所有類型的故障均為由電火花加工的單點損傷，其中直徑為0.177 8mm和0.533 4mm的故障狀態(tài)分別對應輕微和嚴重故障.在故障特征提取階段，首先對數(shù)據(jù)進行EMD分解，對其IMF1分量［13］進行統(tǒng)計分析，計算其裕度系數(shù)、均方根、波形因子、峰值、峭度及脈沖因子值組成的六維特征矢量.由于信號中含有正常與故障兩種狀態(tài)的數(shù)據(jù)，且在故障數(shù)據(jù)中還可細分為輕微故障與嚴重故障兩類.因此，特征矢量具有明顯的兩級尺度.表1為故障數(shù)據(jù)的多級聚類結果.由表1可見，MPC－ACM算法不但能判斷出信號中是否存在故障成分，而且通過降低尺度因子的值，能對故障成分進行細分.這種方法的優(yōu)點是不需提前設定聚類個數(shù)，故障成分可自動得到.雖然尺度因子的值需要人為設定，但可根據(jù)經(jīng)驗進行設定.這種方法在計算效率上也比常規(guī)的采用有效性指標的無監(jiān)督聚類方法更高，更符合實際應用.

圖2 不同參數(shù)下多級聚類結果Fig.2 Multi－level clustering results of different parameters

表1 故障數(shù)據(jù)的多級聚類結果Table 1 Multi－level clustering results on fault data

綜上所述，本文算法通過在可能性聚類算法中引入自動融合機制進行模式搜索，增強了算法對聚類參數(shù)設置的魯棒性.同時，多尺度因子的引入使其具有發(fā)現(xiàn)數(shù)據(jù)中不同尺度聚類結構的能力.本文算法的優(yōu)點是參數(shù)少、易于控制，并能對數(shù)據(jù)進行多尺度分析，但該方法仍存在一些問題.首先，算法不能在指定的聚類個數(shù)下運行.該問題類似于層次聚類方法，在某些必須指定聚類個數(shù)的場合不適用.其次，關于尺度因子參數(shù)值的設置，已經(jīng)發(fā)現(xiàn)其與數(shù)據(jù)間的距離有關，因此本文采用在數(shù)據(jù)的互距離矩陣間尋找，但理論依據(jù)仍有待論證.由實驗結果可見，在沒有先驗知識的情況下，η＝θ（X）可得到較好的聚類結果，但其選擇仍缺乏合理的理論解釋.對于算法的時間與空間復雜度問題，可通過在不損失任何精度的前提下進行采樣，從而降低算法的時間與空間復雜度.

［1］Duda R O，Hart P E.Pattern Classification and Scene Analysis［M］.New York：Wiley，1973.

［2］Jain A K，Duin R P W，Mao J.Statistical Pattern Recognition：A Review ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（1）：4－37.

［3］Bezdek J C.Pattern Recognition with Fuzzy Objective Function Algorithms ［M］.New York：Plenum Press，1981.

［4］Krishnapuram R，Keller J M.A Possibilistic Approach to Clustering［J］.IEEE Transactions on Fuzzy Systems，1993，1（2）：98－110.

［5］Krishnapuram R，Keller J M.The Possibilistic c－Means Algorithm：Insights and Recommendations［J］.IEEE Transactions on Fuzzy Systems，1996，4（3）：385－393.

［6］Yang M S，Lai C Y.A Robust Automatic Merging Possibilistic Clustering Method［J］.IEEE Transactions on Fuzzy Systems，2011，19（1）：26－41.

［7］Kushnir D，Galun M，Brandt A.Fast Multiscale Clustering and Manifold Identification［J］.Pattern Recognition，2006，39（10）：1876－1891.

［8］Dave R N，Krishnapuram R.Robust Clustering Methods：A Unified View ［J］.IEEE Transactions on Fuzzy Systems，1997，5（2）：270－293.

［9］HU Ya－ting，ZUO Chun－cheng，QU Fu－h(huán)eng，et al.Multi－scale Possibilistic Clustering Algorithm ［J］.Journal of Changchun University of Science and Technology：Natural Science Edition，2010，33（4）：124－127.（胡雅婷，左春檉，曲福恒，等.多尺度可能性聚類算法 ［J］.長春理工大學學報：自然科學版，2010，33（4）：124－127.）

［10］Pal N R，Pal K，Keller J M，et al.A Possibilistic Fuzzy c－Means Clustering Algorithm ［J］.IEEE Transactions on Fuzzy Systems，2005，13（4）：517－530.

［11］Yang M S，Wu K L.Unsupervised Possibilistic Clustering［J］.Pattern Recognition，2006，39（1）：5－21.

［12］Loparo K A.Bearings Vibration Data Set ［EB／OL］.2010－05－11.http：／／www.eecs.case.edu／laboratory／bearing／download.htm.

［13］CHENG Jun－sheng，YU De－jie，YANG Yu.A Fault Diagnosis Approach for Roller Bearings Based on EMD Method and AR Model［J］.Mechanical Systems and Signal Processing，2006，20（2）：350－362.