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

田彥彥，孫 靜,2

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

1 引言

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

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

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

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類聚類中心，對象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)化計算式分別為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由于從第二個數(shù)據(jù)塊開始，其中的數(shù)據(jù)除了原始抽樣數(shù)據(jù)外，還新加入了上一數(shù)據(jù)塊的代表點數(shù)據(jù)，從數(shù)據(jù)對最終聚類結(jié)果的貢獻看，由上一數(shù)據(jù)塊傳遞來的代表點對于當(dāng)前塊最終的聚類具有更大的貢獻，因而從第二個數(shù)據(jù)塊開始，需要對原始抽樣數(shù)據(jù)和代表點數(shù)據(jù)賦值不同的權(quán)重，以描述其對最終聚類結(jié)果的貢獻，且隨著數(shù)據(jù)塊序號的增加，其新加入的代表點應(yīng)自適應(yīng)的賦值相應(yīng)更大的權(quá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ù)的聚類貢獻，對于不同序號的數(shù)據(jù)塊，該權(quán)重值由前一數(shù)據(jù)塊的權(quán)重值累積得到，即

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

4 實驗與分析

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

從兩個數(shù)據(jù)集中隨機選取105條記錄進行實驗測試，數(shù)據(jù)集中加入噪聲，以多次實驗結(jié)果的聚類準(zhǔn)確度平均值作為聚類性能評價指標(biāo)，首先測試不同算法的聚類性能效率實驗結(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實驗結(jié)果可以看出，文中改進pmvaFCM算法的收斂迭代次數(shù)有了大幅減少，從而在相同硬件條件下有效減少算法的聚類時間，這主要是因為算法在將數(shù)據(jù)集分塊后，大多數(shù)數(shù)據(jù)塊僅有若干代表點等數(shù)據(jù)是的變量動，因而各數(shù)據(jù)塊的聚類迭代時間變化不大，而通過合理設(shè)置數(shù)據(jù)分塊大小，可以有效減少每個數(shù)據(jù)塊的聚類迭代次數(shù)。另一方面，從平均聚類準(zhǔn)確率實驗結(jié)果可以看出，文中算法取得與mvFCM相似但略好的聚類準(zhǔn)確率，這主要是因為，通過Canopy算法進行初始聚類中心提取后，后續(xù)的數(shù)據(jù)抽樣分塊及聚類初始聚類中心設(shè)置，都有了一個較為準(zhǔn)確的參考，使得相關(guān)參數(shù)的設(shè)置更加合理，從而使得算法取得更優(yōu)的識別準(zhǔn)確率。從圖1準(zhǔn)確度標(biāo)準(zhǔn)差可以看出，文中算法在2個數(shù)據(jù)集中均取得最小的標(biāo)準(zhǔn)差，說明文中算法具有最優(yōu)的聚類穩(wěn)定性。

5 結(jié)論

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