分塊自適應(yīng)加權(quán)改進(jìn)大規(guī)模概率模糊聚類

景慎艷，劉松迪，2

（1.遼寧對外經(jīng)貿(mào)學(xué)院大數(shù)據(jù)研究院，遼寧 大連 116052；2.吉林大學(xué)軟件學(xué)院，長春 130000）

0 引言

聚類是一種發(fā)現(xiàn)無標(biāo)記數(shù)據(jù)中的內(nèi)在模式和重要信息的典型無監(jiān)督數(shù)據(jù)挖掘與分析手段，對于在眾多數(shù)據(jù)中發(fā)現(xiàn)有價值信息或熱點話題具有重要作用，已被廣泛應(yīng)用于計算機(jī)視覺、網(wǎng)絡(luò)安全、生物信息學(xué)等眾多領(lǐng)域［1］。

研究人員針對不同的應(yīng)用場景提出了各種聚類方法，主要分為模糊聚類或概率聚類兩大類［2］，如半監(jiān)督模糊聚類［3］、迭代模糊聚類［4］、累積聚合模糊聚類［5］、Markov 模型［6］和Dirichlet 混合模型的聚類算法［7］等。

近年來，將兩種聚類方法有效融合以實現(xiàn)優(yōu)勢互補的研究有了突破性的進(jìn)展，Aktepe 等［8］基于自然共軛先驗作為參數(shù)，提出使用貝葉斯后驗概率優(yōu)化的聚類數(shù)自適應(yīng)選擇算法；Marttinen［9］等提出基于貝葉斯模糊特征向量無監(jiān)督聚類算法，以二項式準(zhǔn)似然替代普通似然性，產(chǎn)生給定聚類解的后驗概率解析式，提高聚類性能；Sumanth［10］等提出基于混合模糊聚類與貝葉斯模型優(yōu)化的Web 聚類推薦算法，通過優(yōu)勢互補提高Web 聚類；Yeliz 等［11］提出基于模糊C 均值和K-Means 算法的多重分形貝葉斯去噪聚類算法，通過多重分形貝葉斯消除數(shù)據(jù)集的不規(guī)則性并保留奇異屬性，從而獲得準(zhǔn)確率最高的特征描述符性；Kalist 等［12］在HSL 色彩空間中，提出基于概率模糊C 均值聚類的衛(wèi)星圖像分割算法，將FCM 與概率C 均值相結(jié)合，緩解了噪聲敏感等各種限制，取得較好的圖像分割結(jié)果。

Glenn 等［13］提出貝葉斯模糊聚類算法（Bayesian Fuzzy Clustering，BFC），并推導(dǎo)計算相關(guān)參數(shù)的全局最優(yōu)解，有效融合了概率論和模糊論在聚類上的優(yōu)勢。但隨著互聯(lián)網(wǎng)技術(shù)及相關(guān)領(lǐng)域的發(fā)展，以大規(guī)模數(shù)據(jù)集為特性的TB 甚至PB 級的數(shù)據(jù)集已經(jīng)成為常態(tài)，為此，提出基于數(shù)據(jù)分塊的自適應(yīng)加權(quán)BFC 算法。算法在大規(guī)模數(shù)據(jù)集分塊的基礎(chǔ)上，首先設(shè)計了分塊內(nèi)數(shù)據(jù)加權(quán)的改進(jìn)BFC 算法，以挑選出對聚類貢獻(xiàn)最具代表的標(biāo)識數(shù)據(jù)及其自適應(yīng)權(quán)值，然后循環(huán)通過塊間聚類信息傳遞實現(xiàn)大規(guī)模數(shù)據(jù)集的聚類，并分析了算法的收斂性和時間復(fù)雜度。實驗結(jié)果驗證了算法的有效性。

1 BFC 算法的原理

式中，γ 為預(yù)設(shè)參數(shù)，影響高斯分布的密度值，取值通常為γ=3。將式（1）、式（2）和式（4）3 部分相乘可得聯(lián)合似然函數(shù)，取聯(lián)合似然函數(shù)的負(fù)對數(shù)可得BFC 算法的目標(biāo)函數(shù)，即

根據(jù)式（6），利用Metropolis-Hastings［14］算法（M-H 算法）可以迭代求解隸屬度和聚類中心。BFC算法以等價關(guān)系融合概率聚類與模糊聚類的優(yōu)勢，已被證明算法具有全局最優(yōu)解［9］，但兩種方法的融合增加了聚類復(fù)雜度，因而，針對大規(guī)模數(shù)據(jù)聚類時算法顯得力不從心。為適應(yīng)大規(guī)模數(shù)據(jù)聚類，提出適于分塊自適應(yīng)加權(quán)的改進(jìn)BFC 算法（Block Single-wayAdaptive Weighted BFC，bsawBFC）。

2 大規(guī)模分塊加權(quán)聚類算法

大規(guī)模數(shù)據(jù)聚類需要解決數(shù)據(jù)集過大而無法一次全部導(dǎo)入內(nèi)存的困境［11］，文中采用分塊思想，在聚類前，先將大規(guī)模數(shù)據(jù)集分成多個易管理的數(shù)據(jù)分塊，并采用分布式終端對各個分塊進(jìn)行初始聚類，由于數(shù)據(jù)分塊易破壞原有數(shù)據(jù)聚類結(jié)構(gòu)，為此，對每個分塊的聚類中心根據(jù)其閾值內(nèi)的聚類數(shù)進(jìn)行自適應(yīng)加權(quán)，作為標(biāo)識點與其他分塊進(jìn)行合并，每個分塊的聚類閾值之外的數(shù)據(jù)，作為散點數(shù)據(jù)不加權(quán)，然后對合并后的數(shù)據(jù)重新進(jìn)行BFC 聚類，從而實現(xiàn)整個大規(guī)模數(shù)據(jù)集的聚類。

2.1 自適應(yīng)加權(quán)BFC 聚類

由于分塊破壞了原始數(shù)據(jù)的分類特性，分塊后的數(shù)據(jù)雖然進(jìn)行了分布式聚類，但一個聚類內(nèi)可能存在其他類的數(shù)據(jù)，為此，對分塊聚類后的每一個聚類中心，設(shè)置一個半徑閾值dthre，并以閾值內(nèi)的數(shù)據(jù)量判斷該聚類中心對合并后數(shù)據(jù)的聚類貢獻(xiàn)程度，進(jìn)而計算每個分塊內(nèi)聚類中心的自適應(yīng)權(quán)重，實現(xiàn)大規(guī)模數(shù)據(jù)的約減和不同權(quán)重數(shù)據(jù)的模糊聚類，其目標(biāo)函數(shù)定義為：

2.2 改進(jìn)模型的聚類求解

文中自適應(yīng)awBFC 算法參數(shù)的求解采用與原始BFC 算法相近的優(yōu)化策略，根據(jù)式（7）所示改進(jìn)目標(biāo)函數(shù)可得模型的后驗概率模型為：

表1 改進(jìn)模型的參數(shù)優(yōu)化求解

2.3 大規(guī)模分塊自適應(yīng)加權(quán)BFC 算法

分塊自適應(yīng)加權(quán)BFC 算法首先對每個分塊進(jìn)行BFC 聚類；然后根據(jù)聚類中心的半徑閾值計算分塊內(nèi)每個聚類中心的自適應(yīng)權(quán)重，并以聚類中心及其閾值半徑作為分塊內(nèi)每個聚類的代表，與各分塊內(nèi)的散點、閾值半徑之外的數(shù)據(jù)一起重新合并為一個規(guī)模較小的數(shù)據(jù)集；最后，在新的數(shù)據(jù)集內(nèi)采用加權(quán)BFC 進(jìn)行聚類，從而實現(xiàn)大規(guī)模數(shù)據(jù)集的快速BFC 聚類。整個算法的計算過程如表2 所示。

3 算法復(fù)雜度分析

4 實驗與分析

4.1 實驗設(shè)置

為驗證文中算法的有效性，采用合成數(shù)據(jù)集與圖像數(shù)據(jù)集作為實驗用測試數(shù)據(jù)集，以經(jīng)典模糊C均值聚類（FCM）及其改進(jìn)單程模糊C 均值聚類算法swFCM［8］和BFC 算法［6］作為比較算法，實驗平臺為：Intel Xeon E5-2643 v4 @3.4 GHz，32 G 內(nèi)存，NVIDIA M4000 8 G 顯存，以matlab 2016a 軟件開發(fā)實驗算法。采用聚類準(zhǔn)確度（faccuracy）［4］、歸一化互信息（fNMI）［7］和芮氏指數(shù)（fRI）［15］作為聚類性能評價指標(biāo)，取值范圍為［0，1］，越接近1，說明聚類結(jié)果與真實分類越接近。

4.2 算法參數(shù)影響分析

圖1 算法在不同模擬指數(shù)下的聚類準(zhǔn)確度

從實驗結(jié)果可以看出，當(dāng)m 與α 取值在1 附近時，文中算法的聚類性能最優(yōu)，而取值較大或較少將降低算法的聚類性能，根據(jù)大量實驗結(jié)果及文獻(xiàn)中BFC 算法的實驗結(jié)果［13］，后續(xù)實驗中取值m=1.2，α=1。

數(shù)據(jù)分塊也影響算法的聚類性能，如果分塊過大，不僅占用內(nèi)存較大，證據(jù)讀取和聚類過程的耗時也隨之增加，分塊過小則會影響各分塊的數(shù)據(jù)聚類結(jié)構(gòu)。因此，以1 豫、5 豫、10 豫和20 豫的塊比例對Skin、Brainweb、Pen Digits 3 個數(shù)據(jù)集進(jìn)行聚類實驗，以分析不同分塊比例對算法的加速性能，多次實驗結(jié)果的平均值如表3 和下頁表4 所示。

表3 分塊比例對算法運行時間影響

表4 分塊比例對算法運行時間和加速影響

從表中實驗結(jié)果可以看出，通過數(shù)據(jù)集分塊處理，算法的運行時間明顯減少。對于小規(guī)模數(shù)據(jù)集Pen Digits 聚類效率提升不明顯，但對于skin 和Brainweb 兩個大數(shù)據(jù)集，分塊聚類的運行效率提升明顯，且對于數(shù)據(jù)規(guī)模最大的Skin 數(shù)據(jù)集來說，算法的運行效率最優(yōu)，說明算法更適于大規(guī)模數(shù)據(jù)集聚類。

4.3 聚類性能分析比較

將文中算法（記為bsawBFC）與FCM、swFCM 和BFC 一起在2D2C、skin 和Brainweb 3 個數(shù)據(jù)集上進(jìn)行聚類性能比較實驗，以faccuracy、fNMI和fRI的多次實驗結(jié)果的均值和標(biāo)準(zhǔn)差來描述算法的聚類性能和魯棒性，實驗結(jié)果如圖3 和圖4 所示。

圖3 各算法在不同數(shù)據(jù)集實驗結(jié)果平均值

圖4 各算法聚類準(zhǔn)確率標(biāo)準(zhǔn)差

從評價指標(biāo)的均值結(jié)果可以看出，總體上各算法的聚類性能隨數(shù)據(jù)集規(guī)模的增大，指標(biāo)值均有所下降，但在3 個數(shù)據(jù)集上，文中bsawBFC 與傳統(tǒng)BFC 算法的各指標(biāo)值均優(yōu)于FCM 和swFCM 的指標(biāo)值；同時在各數(shù)據(jù)集上，文中bsawBFC 算法的各指標(biāo)值取得與傳統(tǒng)BFC 算法指標(biāo)值相近的結(jié)果，略優(yōu)于BFC 算法；主要因為通過自適應(yīng)加權(quán)改進(jìn)BFC，在提高算法運行效率和保持BFC 算法優(yōu)勢的同時，根據(jù)數(shù)據(jù)對象及標(biāo)識對象對聚類中心的模糊隸屬度，自適應(yīng)設(shè)置對象的聚類權(quán)值，使得權(quán)值設(shè)置更符合數(shù)據(jù)聚類的實際隸屬情況，圖2 實驗結(jié)果中，bsawBFC 算法取得最優(yōu)的評價指標(biāo)值，說明文中算法的聚類性能最優(yōu)。從圖3 準(zhǔn)確度標(biāo)準(zhǔn)差可以看出，文中算法在3 個數(shù)據(jù)集中均取得最小的標(biāo)準(zhǔn)差，說明文中算法具有最優(yōu)的魯棒性。

圖2 算法在不同先驗參數(shù)下的聚類準(zhǔn)確度

5 結(jié)論

隨著互聯(lián)網(wǎng)機(jī)技術(shù)及相關(guān)領(lǐng)域的發(fā)展，以大規(guī)模數(shù)據(jù)集為特性的TB 甚至PB 級的數(shù)據(jù)集已經(jīng)成為常態(tài)，傳統(tǒng)BFC 算法的時間開銷和存儲代價瓶頸隨著數(shù)據(jù)規(guī)模的膨脹越發(fā)突出，為此，提出基于數(shù)據(jù)分塊的單程自適應(yīng)加權(quán)BFC 算法。算法在大規(guī)模數(shù)據(jù)集分塊的基礎(chǔ)上，首先設(shè)計了基于數(shù)據(jù)加權(quán)的改進(jìn)BFC 算法，用于數(shù)據(jù)分塊內(nèi)數(shù)據(jù)聚類，以挑選出對聚類貢獻(xiàn)最具代表的標(biāo)識數(shù)據(jù)及其自適應(yīng)權(quán)值，然后在塊間迭代聚類過程中，將標(biāo)識數(shù)據(jù)及其權(quán)值合并到下一數(shù)據(jù)塊中并參與聚類，從而將上一數(shù)據(jù)塊的聚類信息有效地傳遞到下一數(shù)據(jù)中，循環(huán)迭代直到所有數(shù)據(jù)塊都完成加權(quán)BFC 聚類，實現(xiàn)大規(guī)模數(shù)據(jù)集聚類，并分析了算法的收斂性和時間復(fù)雜度。實驗結(jié)果表明，算法在繼承傳統(tǒng)BFC 算法良好聚類性能基礎(chǔ)上，減少了計算復(fù)雜度，有效提高了聚類效率，適于大規(guī)模數(shù)據(jù)集聚類。