胡雅婷，左春檉，曲福恒

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

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

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

1 可能性聚類算法

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

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

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

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

2 MPC－ACM 算法

2.1 中心自動(dòng)融合機(jī)制

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

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

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

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

這里

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

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

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

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

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

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

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

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

2.2 MPC－ACM算法流程

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

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

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

3）先根據(jù)U（k）找出V（k′）中相關(guān)性大于ρ的中心，利用MA算法對(duì)這些中心合并，再根據(jù)式（11）對(duì)合并后的中心進(jìn)行修正得到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 多尺度性質(zhì)

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 人造數(shù)據(jù)實(shí)驗(yàn)

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

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

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

3.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)

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

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

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

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

［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］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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.