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

田彥彥，孫 靜,2

（1.鄭州工業(yè)應(yīng)用技術(shù)學(xué)院機(jī)電工程學(xué)院，河南 鄭州451100；2.吉林大學(xué)軟件學(xué)院，吉林 長(zhǎng)春130000；）

1 引言

隨著計(jì)算機(jī)技術(shù)的發(fā)展，數(shù)據(jù)的大規(guī)模增長(zhǎng)和信息系統(tǒng)的云服務(wù)化成為基礎(chǔ)應(yīng)用，海量化、多樣化和復(fù)雜化成為數(shù)據(jù)處理的常態(tài)，如何從這些數(shù)據(jù)中提取有用信息，逐漸被人們所重視，聚類可以從各種無(wú)標(biāo)記數(shù)據(jù)中通過(guò)一定的判斷策略發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在關(guān)聯(lián)而實(shí)現(xiàn)無(wú)監(jiān)督聚類，對(duì)分析或挖掘熱點(diǎn)話題等信息具有重要的作用，已在計(jì)算機(jī)視覺(jué)、數(shù)據(jù)挖掘、審計(jì)評(píng)定、云計(jì)算、自動(dòng)化控制以及網(wǎng)絡(luò)安全等學(xué)科領(lǐng)域具有眾多的應(yīng)用，也是近幾年數(shù)據(jù)處理領(lǐng)域研究的重點(diǎn)［1］。

模糊聚類［2］基于模糊集理論分析數(shù)據(jù)集中數(shù)據(jù)對(duì)各個(gè)聚類中心的模糊隸屬度，基于模糊集理論可以實(shí)現(xiàn)更準(zhǔn)確的聚類分析，多視角聚類［3］通常以傳統(tǒng)聚類方法為基礎(chǔ)，將其目標(biāo)函數(shù)擴(kuò)展為多視角，并對(duì)擴(kuò)展后的目標(biāo)函數(shù)添加約束以平衡視角一致性和聚類貢獻(xiàn)的差異性。為此，文獻(xiàn)［4］聯(lián)合視角內(nèi)劃分與視角間協(xié)同的學(xué)習(xí)機(jī)制，提出多代表點(diǎn)一致的多視角模糊聚類算法，并通過(guò)拉格朗日乘子和KKT條件進(jìn)行目標(biāo)函數(shù)優(yōu)化；文獻(xiàn)［5］基于稀疏相似和最大熵提出兩級(jí)變權(quán)的多視角自適應(yīng)聚類算法；文獻(xiàn)［6］聯(lián)合NMF協(xié)同提高多視角聚類的相似矩陣計(jì)算，以獨(dú)立準(zhǔn)則共享視角信息，從而優(yōu)化冗余共享提高算法聚類性能。

分布式計(jì)算有效提高了大規(guī)模數(shù)據(jù)集聚類的處理效率，但其節(jié)點(diǎn)間的數(shù)據(jù)通訊占用了額外的資源，為解決節(jié)點(diǎn)通訊對(duì)資源的占用，文中提出基于大數(shù)據(jù)集抽樣分塊的多視角自適應(yīng)模糊聚類算法，算法在改進(jìn)多視角模糊聚類基礎(chǔ)上，通過(guò)數(shù)據(jù)抽樣分塊和自適應(yīng)加權(quán)塊內(nèi)聚類實(shí)現(xiàn)大規(guī)模數(shù)據(jù)集聚類。實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性。

2 模糊聚類算法的原理

設(shè)規(guī)模為N的待聚類數(shù)據(jù)集為X={x1,x2,…,xN}N×D，D為數(shù)據(jù)集中數(shù)據(jù)的維數(shù)，N?D，設(shè)V={v1,v2,…,vC}C×D為C類聚類中心，對(duì)象x（nn=1,2,…,N）劃分為第c=1,2,…,C類聚類中心的隸屬度記為為模糊劃分矩陣，則基于C均值的模糊聚類算法FCM（Fuzzy C-means）的聚類目標(biāo)函數(shù)可以表示為：

使式（1）所示目標(biāo)函數(shù)取得局部極小值則可以得到數(shù)據(jù)集的模糊劃分矩陣U=[ui,j]，其迭代優(yōu)化計(jì)算式分別為：

式中：m—模糊指數(shù)，針對(duì)經(jīng)典FCM算法的unc無(wú)法精確表達(dá)數(shù)據(jù)集的分類信息問(wèn)題，文獻(xiàn)將中立與拒分兩種度量策略引入到FCM算法中，改進(jìn)后的正則化模型［7］，可描述為

式中：η=[ηij]、ε=[εij]—聚類算法的模糊中立度矩陣與模糊拒分度矩陣，其相應(yīng)的約束條件為∑uij( 2-εik)=1和∑(ηij+εik/c)=1，采用拉格朗日乘子法可以根據(jù)式（4）計(jì)算相關(guān)參數(shù)。為提高式（4）改進(jìn)模型的魯棒性，將文獻(xiàn)［10］中的鄰域正則約束引入式（4），提出具有抗噪優(yōu)化的魯棒模糊聚類方法，其改進(jìn)后的目標(biāo)函數(shù)為：

式中：f(xi,vi)—描述了領(lǐng)域空間信息約束特征，主要用于提高算法的魯棒性并抵制背景噪聲影響，其計(jì)算式為：

為提高聚類算法對(duì)多樣化數(shù)據(jù)的適應(yīng)性，通過(guò)低秩約束和熵加權(quán)對(duì)改進(jìn)后的自適應(yīng)魯棒模糊聚類算法進(jìn)行多視角擴(kuò)展，通過(guò)視角系數(shù)優(yōu)化算法在迭代過(guò)程中對(duì)可分離性視角的權(quán)重分配，從而提高算法對(duì)多樣化數(shù)據(jù)的聚類性能，低秩約束有利于改進(jìn)算法在聚類過(guò)程中的多視角一致性，而熵加權(quán)則有利于保持不同視角數(shù)據(jù)之間的聚類貢獻(xiàn)差異性。

高頻接觸振動(dòng)產(chǎn)生巨大的垂直力增量，使鋼軌塑變層遭受反復(fù)和快速的錘擊作用，逐漸在鋼軌表面形成明暗相間的波浪形磨耗。當(dāng)有切向力作用的動(dòng)輪經(jīng)過(guò)其上時(shí)，瞬間的局部接觸間斷可使動(dòng)輪積聚起很大的能量，一旦在波浪形的峰部恢復(fù)接觸時(shí)，聚合的能量就驟然被釋放出來(lái)。

令多視角數(shù)據(jù)的各視角系數(shù)為wk≥0，則有，則擴(kuò)展算法的熵加權(quán)正則項(xiàng)為：

而低秩約束可以將多視角約束為核范數(shù)最小化求解問(wèn)題，即Γ(U)=‖U‖，U－多視角隸屬度組成的矩陣，這樣基于低迭約束和熵加權(quán)的改進(jìn)算法的目標(biāo)函數(shù)可以表示為：

式中：N—數(shù)據(jù)量，C—聚類中心數(shù)，θ、λ—正則化因子。對(duì)于式（9）的迭代求解，通過(guò)固定其中的w和U，同時(shí)迭代更新聚類中心矩陣V，可得第t+1次迭代計(jì)算得到的聚類中心的解為：

而通過(guò)固定式（9）中的w和Z，同時(shí)迭代更新模糊隸屬度，可得第t+1次迭代計(jì)算得到的模糊隸屬度U(t)+1為：

式（9）所示改進(jìn)模型以等價(jià)關(guān)系融合了多視角聚類與模糊聚類的優(yōu)勢(shì)，具有全局最優(yōu)解［9］，但算法巨大的計(jì)算量使其在應(yīng)用于大規(guī)模數(shù)據(jù)聚類時(shí)無(wú)法獲得最優(yōu)聚類甚至無(wú)法得到聚類結(jié)果，為此，借鑒已有的大規(guī)模數(shù)據(jù)分塊思想，對(duì)提出的多視角自適應(yīng)模糊聚類算法進(jìn)行改進(jìn)，以適于越來(lái)越普遍的大數(shù)據(jù)處理場(chǎng)景。

3 分塊加權(quán)大規(guī)模模糊聚類

大規(guī)模數(shù)據(jù)集難以一次性全部讀入內(nèi)存中，因而給聚類算法的數(shù)據(jù)讀取帶來(lái)壓力，Canopy算法根據(jù)一定的數(shù)據(jù)預(yù)處理規(guī)則可以將原始大規(guī)模數(shù)據(jù)集劃分為多個(gè)數(shù)據(jù)片，每個(gè)數(shù)據(jù)包含一定數(shù)量的數(shù)據(jù)，因此可以通過(guò)Canopy算法先對(duì)數(shù)據(jù)進(jìn)行分塊預(yù)處理，將原始大規(guī)模數(shù)據(jù)集劃分為可同讀入內(nèi)存進(jìn)行處理的小規(guī)模數(shù)據(jù)片，同時(shí)Canopy算法可以根據(jù)數(shù)據(jù)特征初步獲得數(shù)據(jù)的粗糙聚類中心，從而進(jìn)一步減少后續(xù)數(shù)據(jù)處理過(guò)程的迭代次數(shù)，提高算法收斂效率。

對(duì)于原始數(shù)據(jù)集list=X={x1,x2,…,xN}N×D，預(yù)設(shè)兩個(gè)閾值T1和T2，T1＞T2，則判斷任意一個(gè)數(shù)據(jù)點(diǎn)P與list中剩余數(shù)據(jù)的距離值d，并將T1＜d＜T1的原始數(shù)據(jù)點(diǎn)作為候選的初始聚類中心，重復(fù)執(zhí)行，直接所有數(shù)據(jù)被判斷一遍，同時(shí)將d＜T1的數(shù)據(jù)合并為一個(gè)臨時(shí)數(shù)據(jù)片。

在獲得初始聚類中心及其相應(yīng)聚類后，對(duì)每個(gè)聚類中的數(shù)據(jù)進(jìn)行隨機(jī)抽樣，并將一次抽樣結(jié)果作為一個(gè)數(shù)據(jù)分塊，根據(jù)數(shù)據(jù)規(guī)模判斷分塊數(shù)及每個(gè)數(shù)據(jù)塊的規(guī)模，并對(duì)數(shù)據(jù)塊進(jìn)行編號(hào)。然后對(duì)第一個(gè)數(shù)據(jù)塊執(zhí)行第2節(jié)所示的多視角自適應(yīng)模型聚類算法，獲得第一個(gè)數(shù)據(jù)塊的聚類結(jié)果及其聚類的質(zhì)心，由于每個(gè)聚類的質(zhì)心最具有該類的代表性，因而將該質(zhì)心作為代表點(diǎn)合并到第二個(gè)數(shù)據(jù)塊中，并參與第二個(gè)數(shù)據(jù)塊的聚類，依次類推，直接所有數(shù)據(jù)塊均完成多視角自適應(yīng)模糊聚類，從而獲得最終大規(guī)模數(shù)據(jù)集模糊聚類結(jié)果。

由于從第二個(gè)數(shù)據(jù)塊開(kāi)始，其中的數(shù)據(jù)除了原始抽樣數(shù)據(jù)外，還新加入了上一數(shù)據(jù)塊的代表點(diǎn)數(shù)據(jù)，從數(shù)據(jù)對(duì)最終聚類結(jié)果的貢獻(xiàn)看，由上一數(shù)據(jù)塊傳遞來(lái)的代表點(diǎn)對(duì)于當(dāng)前塊最終的聚類具有更大的貢獻(xiàn)，因而從第二個(gè)數(shù)據(jù)塊開(kāi)始，需要對(duì)原始抽樣數(shù)據(jù)和代表點(diǎn)數(shù)據(jù)賦值不同的權(quán)重，以描述其對(duì)最終聚類結(jié)果的貢獻(xiàn)，且隨著數(shù)據(jù)塊序號(hào)的增加，其新加入的代表點(diǎn)應(yīng)自適應(yīng)的賦值相應(yīng)更大的權(quán)重，為此，文中對(duì)含有代表點(diǎn)的數(shù)據(jù)塊的聚類，其目標(biāo)函數(shù)中增加數(shù)據(jù)的自適應(yīng)權(quán)重，修改后的目標(biāo)函數(shù)為：

式中：wn＞0—數(shù)據(jù)權(quán)重，其描述了數(shù)據(jù)塊不同屬性數(shù)據(jù)的聚類貢獻(xiàn)，對(duì)于不同序號(hào)的數(shù)據(jù)塊，該權(quán)重值由前一數(shù)據(jù)塊的權(quán)重值累積得到，即

表1 大規(guī)模分塊多視角自適應(yīng)FCM算法Tab.1 Large-Scale Split Field Multiview FCM Algorithm

4 實(shí)驗(yàn)與分析

為驗(yàn)證文中提出的分塊多視角自適應(yīng)模糊聚類算法（簡(jiǎn)記為pmvaFCM）的有效性，采用來(lái)自UCI機(jī)器學(xué)習(xí)庫(kù)的Iris和Wine數(shù)據(jù)集［10］作為測(cè)試數(shù)據(jù)，以傳統(tǒng)FCM算法［4］、多視角FCM算法（mvFCM）［9］作為比較算法，實(shí)驗(yàn)平臺(tái)為：Intel i7 7700HQ@2.8G Hz，16G內(nèi)存，NVIDIA GTX1060 6G顯存，以matlab 2016a軟件開(kāi)發(fā)實(shí)驗(yàn)算法。

從兩個(gè)數(shù)據(jù)集中隨機(jī)選取105條記錄進(jìn)行實(shí)驗(yàn)測(cè)試，數(shù)據(jù)集中加入噪聲，以多次實(shí)驗(yàn)結(jié)果的聚類準(zhǔn)確度平均值作為聚類性能評(píng)價(jià)指標(biāo)，首先測(cè)試不同算法的聚類性能效率實(shí)驗(yàn)結(jié)果，如表2所示和圖1所示。

表2 不同算法的聚類性能比較Tab.2 Performance Comparison of Different Algorithms

圖1 各算法聚類準(zhǔn)確率標(biāo)準(zhǔn)差Fig.1 Standard Deviation of Clustering Accuracy of Each Algorithm

從表2和表1實(shí)驗(yàn)結(jié)果可以看出，文中改進(jìn)pmvaFCM算法的收斂迭代次數(shù)有了大幅減少，從而在相同硬件條件下有效減少算法的聚類時(shí)間，這主要是因?yàn)樗惴ㄔ趯?shù)據(jù)集分塊后，大多數(shù)數(shù)據(jù)塊僅有若干代表點(diǎn)等數(shù)據(jù)是的變量動(dòng)，因而各數(shù)據(jù)塊的聚類迭代時(shí)間變化不大，而通過(guò)合理設(shè)置數(shù)據(jù)分塊大小，可以有效減少每個(gè)數(shù)據(jù)塊的聚類迭代次數(shù)。另一方面，從平均聚類準(zhǔn)確率實(shí)驗(yàn)結(jié)果可以看出，文中算法取得與mvFCM相似但略好的聚類準(zhǔn)確率，這主要是因?yàn)?，通過(guò)Canopy算法進(jìn)行初始聚類中心提取后，后續(xù)的數(shù)據(jù)抽樣分塊及聚類初始聚類中心設(shè)置，都有了一個(gè)較為準(zhǔn)確的參考，使得相關(guān)參數(shù)的設(shè)置更加合理，從而使得算法取得更優(yōu)的識(shí)別準(zhǔn)確率。從圖1準(zhǔn)確度標(biāo)準(zhǔn)差可以看出，文中算法在2個(gè)數(shù)據(jù)集中均取得最小的標(biāo)準(zhǔn)差，說(shuō)明文中算法具有最優(yōu)的聚類穩(wěn)定性。

5 結(jié)論

為解決傳統(tǒng)FCM模糊聚類算法在處理大規(guī)模數(shù)據(jù)集時(shí)遇到的時(shí)間復(fù)雜和內(nèi)存不足等瓶頸，提出基于大數(shù)據(jù)集抽樣分塊的多視角自適應(yīng)模糊聚類算法，算法通過(guò)鄰域正則約束提高傳統(tǒng)FDM算法的抗噪性，通過(guò)低秩與熵加權(quán)約束提高多視角一致性，以提高算法對(duì)多樣化數(shù)據(jù)聚類的適應(yīng)性，最后通過(guò)Canopy算法初始聚類中心提取和數(shù)據(jù)抽樣分塊優(yōu)化算法對(duì)大規(guī)模數(shù)據(jù)聚類的適應(yīng)性，實(shí)驗(yàn)結(jié)果驗(yàn)證算法的有效性。