白 璐,趙 鑫,孔鈺婷,張正航,邵金鑫,錢育蓉
1.新疆大學(xué) 軟件學(xué)院,烏魯木齊830046
2.新疆大學(xué) 軟件學(xué)院重點實驗室,烏魯木齊830046
3.新疆維吾爾自治區(qū)信號檢測與處理重點實驗室,烏魯木齊830046
聚類分析是一種挖掘數(shù)據(jù)深層信息與知識的有效方法,聚類是將給定的樣本劃分成多個簇的過程。聚類最優(yōu)準(zhǔn)則[1-2]的目標(biāo)是使同一簇內(nèi)的樣本間相似度高,不同簇樣本間相似度低。K-均值(K-means)算法是傳統(tǒng)聚類中的經(jīng)典算法,K-means算法雖然易于理解但仍存在局限性,如對樣本形狀包容性差、易陷入局部最優(yōu)解[3]等問題。
為能在任意形狀的樣本空間上達(dá)到良好聚類性能,研究者們提出譜聚類算法(Spectral Clustering Algorithm,SC),SC 算法擁有對樣本形狀敏感度低、收斂于全局最優(yōu)解、對高維數(shù)據(jù)支持較好[4]等特點,因此SC算法[5]如今廣泛應(yīng)用于數(shù)據(jù)挖掘[6]、圖像分割[7-9]、模式識別[10]以及遙感[11-12]等領(lǐng)域。近年來隨著應(yīng)用場景變化,大規(guī)模數(shù)據(jù)聚類高時耗問題成為一個研究熱點,而譜聚類算法存在同樣的聚類挑戰(zhàn)[13]。
譜聚類算法是一種建立在譜圖理論上的聚類算法,主要分為兩類:迭代譜聚類算法與多路譜聚類算法,分別以SM[14]算法與NJW[15]算法為代表。在多路譜聚算法中,為解決NJW算法需要人工設(shè)置簇數(shù)K等參數(shù)問題,孔萬增等人[16]利用本征間隙特征,實現(xiàn)自動確定K值的譜聚類算法;為達(dá)到更好的聚類性能,王玲等人[17]提出基于數(shù)據(jù)先驗信息的半監(jiān)督譜聚類算法;為解決譜聚類算高法時空復(fù)雜度、對大數(shù)據(jù)樣本適應(yīng)性差等問題,將譜聚類部署在Hadoop、Spark 等平臺,利用平臺分布并行特性降低譜聚類算法時耗,或通過優(yōu)化譜聚類切割模型,來降低算法時間復(fù)雜度。
譜聚類算法的思想起源于譜圖劃分理論[18],譜聚類通過樣本相似度生成無向加權(quán)圖,樣本點可看作圖的頂點,樣本點間的相似度為兩點間邊的權(quán)重,而對無向加權(quán)圖進行譜圖劃分就是將圖劃分為若干個子圖,該過程與聚類算法的聚類過程對應(yīng)。圖論的最優(yōu)劃分準(zhǔn)則[14]與聚類最優(yōu)準(zhǔn)則在思想上具有一致性,為聚類問題轉(zhuǎn)化為圖劃分問題提供思路與理論支撐。對于譜圖劃分而言,圖劃分準(zhǔn)則的選取將直接影響劃分結(jié)果,常用的圖劃分準(zhǔn)則有規(guī)范割集、最小割集、平均割集、比例割集等準(zhǔn)則[19]。與譜圖劃分相比,譜聚類算法考慮問題連續(xù)放松形式,將圖分割問題轉(zhuǎn)換為求相似矩陣的譜分解問題[20]。譜聚類算法依據(jù)劃分準(zhǔn)則的不同,總體分為迭代譜聚算法與多路譜聚類算法。目前多路譜聚類算法因其簡單易于理解特性應(yīng)用更為廣泛,NJW 算法是經(jīng)典多路譜聚類算法。多路譜聚算法實現(xiàn)細(xì)節(jié)略有差異,但核心思想基本一致,其主要思想如下:
步驟1 通過樣本構(gòu)建可描述樣本特性的矩陣W。
步驟2 計算矩陣W的特征值及特征向量并對其進行排序。
步驟3 取排序后前k個特征值對應(yīng)特征向量,將向量按列方向排列,組成新解空間。
步驟4 在新解空間上采用典聚類算法進行聚類(模糊聚類、K-means等),最終將聚類結(jié)果映射回原解空間。
在譜聚類算法步驟1 中,采用相似矩W來表示樣本數(shù)據(jù)間的相似性是對數(shù)據(jù)集的特征的一種抽象表達(dá)。
一般情況下,求解譜圖劃分的最優(yōu)劃分準(zhǔn)則是NP難度問題,通過連續(xù)放松形式將圖劃分問題轉(zhuǎn)化為相似矩陣譜分解問題,因此譜聚類算法是對最優(yōu)圖劃分準(zhǔn)則的逼近[21]。近年放松形式的譜聚類算法研究較多,最早譜聚類采用樣本鄰接矩陣直接進行圖劃分[22],但譜聚類算法的準(zhǔn)確率受矩陣質(zhì)量影響,一般而言矩陣質(zhì)量越高,聚類結(jié)果越理想。
現(xiàn)階段譜聚類算法多基于相似矩陣(Affinity Matrix),采用W或A表示,本文統(tǒng)一采用W表示。相似矩陣定義如下:
公式(1)中v為數(shù)據(jù)樣本點;d(vi,vj)為兩樣本點之間的距離,一般取歐氏距離;σ為尺度參數(shù),W隨著σ取值變化而改變,因此σ需要經(jīng)過多次取值實驗才能確定[23]。
度矩陣是記為D的對角矩陣,度值為對角元素。計算方式如公式(2)所示:
規(guī)范相似矩陣一般形式定義為:
在面向降低W計算量方面,對數(shù)據(jù)提前進行特定清洗,在去除噪聲的同時保留更有代表性的數(shù)據(jù);而在提升W質(zhì)量方面,通過改進相似矩陣的求解的模型或引入監(jiān)督機制[24],更正相似矩陣,從而提升譜聚類算法聚類性能。
譜聚類算法早期直接采用W的最大k個特征向量進行聚類,但W無法保證被選中的k個特征值對應(yīng)的特征向量為異塊向量。因此,通過W選取特征向量,存在多次選取一塊特征向量問題,進而導(dǎo)致選取的特征向量代表性較差。拉普拉斯矩陣L(Laplacian Matrix)為半正定矩陣,L特征值最小為0且對應(yīng)的特征向量為1。當(dāng)選取L的前k個特征值所對應(yīng)的特征向量時,可確保每個分量僅含有一個特征向量[5],因此將L矩陣引入譜聚類中。L矩陣一般分為規(guī)范拉普拉斯矩陣和非規(guī)范拉普拉斯矩陣,非規(guī)范拉普拉斯矩陣表示為:
規(guī)范拉普拉斯矩陣兩種形式,I為單位矩陣。
譜聚類算法通常選取前k個特征值所對應(yīng)的特征向量,以NJW 算法為例,NJW 算法采用公式(3)計算Wnor。而由公式(6)可知,求解Wnor的最大特征值等同于求解Lnor的最小特征值,因此NJW 算法也等同基于Lnor前k個最小特征進行聚類[25]。當(dāng)采用W進行聚類時,由于公式(1)是基于距離測度的計算方法,而兩點間距離最小為0,因此有效區(qū)間為[0,+∞]。在公式(1)有效區(qū)間內(nèi),W的取值均處在0 到1 之間,如圖1 紅線部分所示。
圖1 W 取值示意圖
在機器學(xué)習(xí)特征提取中,最大特征值對應(yīng)的特征向量方向上通常包含最多信息量[26]。因此,在W特征向量選取過程中選擇前k個最大特征值所對應(yīng)的特征向量。雖然該選擇策略可大概率保證選取質(zhì)量,但仍存在高信息量的特征值不一定有較高的分類貢獻(xiàn)信息量問題。
針對特征向量選取問題,王洪森等人[27]與王興良等人[28]從特征值k值設(shè)定閾值入手,擴大選入特征值與特征向量數(shù)量。王洪森選取矩陣前3k個特征值并求取平均值記為λ,最終選擇λ數(shù)值最k近鄰的特征值,但對于3k的取值未解釋其必然性,且基于均值的選擇策略易受樣本數(shù)量影響,增加時間消耗。王興良等人提出基于約束分值的特征向量(Bootstrap aggregating,Bagging)選取法。算法選取L前2k個特征向量,并采用成對約束計分方法與Bagging 結(jié)合,在特征值選擇階段效果良好?;贐agging 的選取策略相較均值選擇策略而言,向量的選取方式理論依據(jù)更強,但也無法避免計算復(fù)雜的缺點。
由于譜聚類算法應(yīng)用場景的不斷變化,傳統(tǒng)譜聚類算無法使小數(shù)量標(biāo)簽發(fā)揮相應(yīng)價值、W矩陣構(gòu)造階段并未包含數(shù)據(jù)的多元特征,如部分先驗標(biāo)簽信息、空間信息等,W經(jīng)過譜分解、聚類等操作后,特征缺乏引起的誤差將會放大,最終影響最終聚類結(jié)果,同時兩階段聚類方式易受二階段聚類算法缺點影響。在算法時耗方面,傳統(tǒng)譜聚類算法因矩陣W與矩陣L計算量大,在處理小樣本數(shù)據(jù)集時聚類性能良好,但處理大規(guī)模數(shù)據(jù)集時,傳統(tǒng)譜聚類因數(shù)據(jù)量過大導(dǎo)致聚類中斷。
針對上述譜聚類算法的不足,眾多學(xué)者不斷提出改進算法來解決以上問題,并在現(xiàn)有研究條件下均衡優(yōu)化算法的時間、空間開銷及算法聚類性能。本文基于現(xiàn)有的譜聚類算法優(yōu)化策略與方向,將譜聚類優(yōu)化算法劃分為以下三類:半監(jiān)督與距離測度優(yōu)化、二階段聚類算法優(yōu)化及執(zhí)行效率優(yōu)化。
隨著社會的數(shù)字化,譜聚類算法應(yīng)用范圍與場景發(fā)生改變,算法及模型需要及時優(yōu)化與改進才能保持可用性與魯棒性。
機器學(xué)習(xí)分為無監(jiān)督學(xué)習(xí)與監(jiān)督學(xué)習(xí),而現(xiàn)有的數(shù)據(jù)樣本一般僅有少量標(biāo)簽,采用無監(jiān)督學(xué)習(xí)數(shù)據(jù)標(biāo)簽將被舍棄,而少量標(biāo)簽也無法滿足監(jiān)督學(xué)習(xí)需求。半監(jiān)督學(xué)習(xí)結(jié)合監(jiān)督與無監(jiān)督學(xué)習(xí)特性,使標(biāo)簽的發(fā)揮相應(yīng)價值,既節(jié)省人工成本又避免標(biāo)簽浪費。通過半監(jiān)督形式發(fā)揮標(biāo)簽應(yīng)有的作用,最終優(yōu)化算法精確度[29-30],且經(jīng)過文獻(xiàn)[31]實驗證明,相比無監(jiān)督聚類算法,半監(jiān)督聚類算法的聚類準(zhǔn)確率更高,同時半監(jiān)督譜聚類現(xiàn)今應(yīng)用于功能磁共振[32]與印刷套準(zhǔn)[33]等領(lǐng)域。下面將詳細(xì)介紹限制與測度兩種方法及相關(guān)優(yōu)化策略。
2.1.1 基于先驗信息限制方法
基于限制的半監(jiān)督譜聚類算法采用成對限制先驗信息更改W,達(dá)到提升聚類性能與準(zhǔn)確率目的,這也是限制半監(jiān)督譜聚類算法的核心思想[34]。而針對譜聚類半監(jiān)督化思想,Kamvar 等人[35]在2003 年提出并實現(xiàn)基于數(shù)據(jù)樣本自適應(yīng)的譜聚類算法,該算法同時適應(yīng)與無監(jiān)督與有監(jiān)督聚類并具有較好精度。
半監(jiān)督譜聚類算法通常采用兩類成對限制,即Must-Link(ML)與Cannot-Link(CL)來輔助聚類搜索[36]。當(dāng)兩個樣本存在ML 限制時,對應(yīng)樣本劃分為同一類,若存在CL限制對應(yīng)樣本劃分于不同類中。成對先驗信息與相似度矩陣同樣具有如下對稱性與傳遞性。
對稱性:
對于任意的i、j、q均存在以下傳遞性:
采用半監(jiān)督聚類算法時,成對限制先驗信息與聚類算法中W對應(yīng)關(guān)系如公式(10)所示:
在理想狀況下,xi,xj屬于一類Wij=1,否則Wij=0,以上分別對應(yīng)ML 與CL 情況。通過公式(10),成對約束先驗信息直接修改相似矩陣,對聚類進行監(jiān)督矯正,提高相似矩陣質(zhì)量,得到更加精準(zhǔn)的聚類結(jié)果。
通常譜聚類基于現(xiàn)有成對約束,直接聚類的策略對算法提升有限,而成對約束擁有如公式(8)、(9)所示性質(zhì),因此成對約束傳播可挖掘隱性約束信息。在面向成對約束傳播問題,趙曉曉等人[37]提出結(jié)合稀疏表示和約束傳遞的半監(jiān)督譜聚類算法。該算法在普通約束譜聚類基礎(chǔ)上,將約束集合中的數(shù)據(jù)作為地標(biāo)點來構(gòu)造稀疏表示矩陣,獲得近似相似度矩陣,同時根據(jù)相似度矩陣生成連通區(qū)域,在每個連通區(qū)域內(nèi)動態(tài)調(diào)整近鄰點,利用約束傳遞進一步提高聚類準(zhǔn)確率。
對半監(jiān)督譜聚類算法而言,監(jiān)督信息的質(zhì)量、可靠性與數(shù)目對準(zhǔn)確率影響較大,為避免選取低質(zhì)量約束,Wang[31]與王娜[24]等人從提升監(jiān)督信息選取質(zhì)量入手,提升選取監(jiān)督信息質(zhì)量。Wang等人采用主動查詢策略替換隨機查詢策略,并采用主動查詢函數(shù)來動態(tài)選擇約束以增強算法魯棒性;關(guān)于譜聚類參數(shù)敏感問題,通過采用Hessian矩陣代替拉普拉斯矩陣得到解決。王娜等人提出基于監(jiān)督信息特性的主動半監(jiān)督譜聚類算法,采用主動學(xué)習(xí)策略挖掘數(shù)據(jù)深層信息如,屬于同一類但樣本距離較遠(yuǎn)的樣本點信息;或?qū)儆诓煌惖珮颖揪嚯x較近的樣本點信息,以上信息均稱為高質(zhì)量信息。低質(zhì)量約束信息如圖2(a)所示,該圖中監(jiān)督信息可通過聚類輕易獲得,對聚類監(jiān)督矯正作用弱,所提供的監(jiān)督信息對聚類貢獻(xiàn)度低。高質(zhì)量約束信息如圖2(b)所示,約束信息e-i=CL、j-g=ML與h-d=CL是通過聚類算法無法輕易獲取的高質(zhì)量信息,因此,通過選取高質(zhì)量成對約束監(jiān)督信息,提高監(jiān)督信息對聚類貢獻(xiàn)度,避免因監(jiān)督信息質(zhì)量低導(dǎo)致的聚類結(jié)果提升不明顯等問題。
圖2 高質(zhì)量與低質(zhì)量監(jiān)督信息示例圖
在現(xiàn)實應(yīng)用中,成對限制信息通常由用戶給定、隨機選取或主動學(xué)習(xí)等方式獲得。面對真實數(shù)據(jù)集,算法無法正確聚類樣本的對應(yīng)信息是提高算法精度與性能的關(guān)鍵,同時也是半監(jiān)督聚類具有約束效力的高質(zhì)量監(jiān)督信息。相比于普通約束信息,含有高質(zhì)量約束信息的半監(jiān)督譜聚類算法在準(zhǔn)確率上有顯著提升。
在層次聚類中,Nazari 等人[38]提出的基于交點聚類算法與成對約束信息的傳遞性類似,該算法通過判斷兩簇是否存在交點來決定合并操作。如圖3所示,基于合并交點簇思想,簇間可通過傳遞的方式連續(xù)合并,這點與半監(jiān)督聚類中成對約束信息的傳遞性類似,焦點聚類算不僅簡單有效,且在球型的樣本表現(xiàn)、性能更優(yōu)。由此可見,監(jiān)督信息的傳遞等特性在聚類中具有普適性。
圖3 交點聚類算法示意圖
但僅基于成對限制的譜聚類算法在處理流形數(shù)據(jù)時提升有限,因此肖成龍[39]與楊婷[40]等人受啟發(fā)于流形正則項,將其與譜聚類結(jié)合,以提升譜聚類在處理流行數(shù)據(jù)的聚類性能。肖成龍等人將約束、正則化與深度譜聚類結(jié)合,利用反向傳播將約束與正則信息調(diào)整權(quán)重。楊婷等人利用L2,1范數(shù)與成對監(jiān)督信息構(gòu)造高質(zhì)量W,并在此基礎(chǔ)上引入流行正則項。
選取質(zhì)量低或數(shù)量少的約束信息易對算法產(chǎn)生誤導(dǎo)作用,影響聚類精度,因此選取高質(zhì)量先驗信息形成約束以監(jiān)督指導(dǎo)聚類?;谝延屑s束信息通過樣本傳播,以發(fā)現(xiàn)更深層約束信息,最終在約束與相似度矩陣的協(xié)同下提升算法準(zhǔn)確率。此外僅基于成對約束的譜聚類算法在處理流形分布數(shù)據(jù)效果欠佳,引入樣本密度信息或流行正則項等策略,提升算法在處理流形數(shù)據(jù)的表現(xiàn)。具體基于先驗信息優(yōu)化策略的對比分析如表1所示。
表1 先驗信息策略對比
2.1.2 基于距離測度方法
在基于限制的半監(jiān)督聚類中,存在限制信息重復(fù)導(dǎo)致信息含量小,無法獲得進一步提升聚類結(jié)果問題。經(jīng)研究發(fā)現(xiàn),僅基于樣本層面的限制先驗信息質(zhì)量較低,無法獲得更優(yōu)解。針對該問題,研究者將基于距離測度的半監(jiān)督方法引入譜聚類算法,以便構(gòu)造包含多維特征的W矩陣。基于測度的半監(jiān)督算法通過對監(jiān)督信息學(xué)習(xí),改變聚類算法中的距離測度函數(shù),得到適合數(shù)據(jù)聚類的新度量[41-42],最終通過新測度計算W進行聚類。
在面向反應(yīng)數(shù)據(jù)全局一致性與空間一致性的測度方面,王玲[17]與陶新民[43]等人均從數(shù)據(jù)密度特點著手改進算法。陶新民等人基于距離測度,定義含有伸縮因子與密度敏感項的密度敏感距離,通過調(diào)節(jié)參數(shù)到達(dá)類內(nèi)高內(nèi)聚、類間低耦合的理想狀態(tài),且在時間復(fù)雜度不變的條件下,提升傳統(tǒng)基于歐氏距離的譜聚類對流型樣本的聚類性能。該算法同時采用譜熵貢獻(xiàn)率[44]、最大熵代替K-means算法等方式來提高算法的準(zhǔn)確率。王玲等人則借鑒限制與測度融合方法,采用圖最短路徑長度生成密度敏感距離測度以計算W,同時成對先驗信息對W矩陣進行監(jiān)督矯正。算法密度敏感距離測度定義與相關(guān)步驟如下:
首先用密度可調(diào)節(jié)線段L代替?zhèn)鹘y(tǒng)距離:
dist(xi,xj)為數(shù)據(jù)點的歐氏距離。算法通過密度線段L計算得到密度敏感矩陣,密度敏感距離計算公式如下:
該測度將數(shù)據(jù)點看作圖的頂點V,將數(shù)據(jù)點間的線段L看作權(quán)重E。令p∈Vl表示圖上長度為l=:||p的連接點pl和p||p的路徑。邊(pk,pk+1)∈E,k∈[1,||p]。Pi,j表示連接數(shù)據(jù)點xi、xj的所有路徑集合。
相似矩陣定義如下:
密度敏感距離通過ρ調(diào)節(jié)線段L的長度,并由L組成矩陣L,通過L計算密度圖最短距,形成敏感距離,如公式(11)、(12)所示。利用成對約束信息,直接修改監(jiān)督點間Dsen矩陣對應(yīng)數(shù)值,含有監(jiān)督信息的Dsen通過公式(13)得到相似矩陣S。S在含有密度敏感空間信息的同時包含成對先驗限制信息,相比于僅采用歐氏距離的傳統(tǒng)譜聚類算法,限制與測度融合策略能夠保留更多數(shù)據(jù)特征。由此可見,距離測度的選取在譜聚類算法影響深遠(yuǎn),尤其面對高維數(shù)據(jù)時距離的選擇尤為關(guān)鍵。
以上基于密度的優(yōu)化策略提升效果顯著,但存在調(diào)節(jié)參數(shù)較多等問題,針對該問題,劉友超[45]與葛君偉[46]等人通過無參數(shù)的密度自適應(yīng)鄰域構(gòu)建法構(gòu)建無向圖。劉友超等人將相似圖與先驗信息相結(jié)合,在遵循半監(jiān)督聚類方式下,重新定義既含有成對約束與相似圖信息的W。葛君偉等人則以共享最近鄰來衡量樣本間的相似性度,避免參數(shù)帶來的誤差?;谝陨涎芯炕A(chǔ),趙萌萌等人[47]針對大規(guī)模數(shù)據(jù)應(yīng)用場景,提出增量式共享緊鄰密度的譜聚類算法。該方法將樣本隨機分為t個子集,在每次增量聚類時采用KNN 確定新增子集數(shù)據(jù)點的類別。本章舉例基于距離測度改進的譜聚類算法,針對不同問題的不同優(yōu)化策略,算法具體對比分析如表2所示。
表2 測度優(yōu)化策略對比
譜聚類在低維解空間通常采用K-means 等聚類算法進行二階段聚類,但K-means算法在選取聚類中心點時具有隨機性,存在產(chǎn)生空簇的概率,因此影響譜聚類算法整體準(zhǔn)確率與穩(wěn)定性[48-49]。
為避免引入隨機性、提高譜聚類算法的整體穩(wěn)定性,針對二階段聚類選取K-means的譜聚類算法,優(yōu)化初始聚類中心選取策略為常見優(yōu)化方法。Sapkota[50]、謝娟英[51]及周偉[52]等人通過優(yōu)化初始聚類中心以提升算法穩(wěn)定性。Sapkota 等人采用新最遠(yuǎn)啟發(fā)式思想(New Farthest Point Heuristic,NFPH)改進的K-means 來代替?zhèn)鹘y(tǒng)K-means 算法。NFPH 通過哈希表儲存樣本點對應(yīng)頻率,選取頻率最高的樣本點代替K-means隨機選取的初始聚類中心略,以加強算法穩(wěn)定性。算法選取流程如圖4 所示,當(dāng)前簇類數(shù)目小于設(shè)定K值時,通過NFPH 策略選取下一個聚類中心。基于該思想的譜聚類算法與實驗對照組相比,錯誤率低但時間消耗較高。
圖4 NFPH中心選取流程圖
謝娟英等人選取方差優(yōu)化初始聚類中心的SD_K-medoids[53]代替?zhèn)鹘y(tǒng)K-means 算法,提高譜聚類算法整體穩(wěn)定性,并將相似矩陣參數(shù)σ替換為完全自適應(yīng)的局部尺度參數(shù),使相似矩陣更好表達(dá)樣本真實分布情況。K-means的優(yōu)化算法中,趙鑫等人[54]將Canopy算法引入K-means,達(dá)到降低算法迭代次數(shù)的同時提升算法穩(wěn)定性的效果。周偉等人將Canopy優(yōu)化后的K-means算法引入譜聚類以克服初始中心點不穩(wěn)定的缺點,但基于譜聚類算法的Canopy優(yōu)化策略使聚類時耗高問題更為突出,處理大規(guī)模數(shù)據(jù)集困難。
針對二階段譜聚類中K值確定問題,孔萬增[16]與胡卓婭[55]等人從特征值本征間隙出發(fā),自適應(yīng)缺點聚類K值??兹f增等人利用本征間隙特性,自動確定K值,避免手動調(diào)參,采用基于矩陣賦零法代替K-means進行二階段聚類,基于余弦值的矩陣賦零法直接基于矩陣操作,相比于K-means算法時耗更短。該優(yōu)化策略在實現(xiàn)K值自動確定的同時,避免引入其他聚類算法的不確定性等因素。而胡卓婭等人在利用本征間隙確定K值的同時,在二階段聚類采用優(yōu)化蜂群算法代替K-means算法,借助蜂群算法特性增強譜聚類算法全局搜索能力。
上述算法在二階段聚類分別選取改進的K-means算法或選取其他聚類算法,以提升算法的穩(wěn)定性。然而每種聚類算法均有相應(yīng)的優(yōu)缺點,K-means算法線性時間復(fù)雜度是最顯著的優(yōu)點,而基于初始中線點優(yōu)化策略的K-means算法通常付出更多時間消耗,增加譜聚類算法適應(yīng)大規(guī)模數(shù)據(jù)負(fù)擔(dān)。因此,選擇第二階段聚類算法時,時間復(fù)雜度是值得考慮的因素之一。具體二階段聚類算法對比分析如表3所示。
表3 二階段聚類算法對比
傳統(tǒng)譜聚類算法基于數(shù)據(jù)樣本計算W矩陣并進行規(guī)范化,因此算法時間復(fù)雜度為O(n3)。面向大規(guī)模數(shù)據(jù)應(yīng)用場景,譜聚類算法通常因時空復(fù)雜度過高,無法完成計算而被迫中斷。為提高譜聚類算法在海量數(shù)據(jù)場景下的可用性,研究者借助Spark 等平臺優(yōu)勢對譜聚類算法并行加速,或通過優(yōu)化W矩陣計算策略減少計算時耗,或針對現(xiàn)有劃分模型進行優(yōu)化,降低算法時間復(fù)雜度,減少算法處理海量數(shù)據(jù)時間開銷。
2.3.1 并行與優(yōu)化改進方法
通信技術(shù)的發(fā)展使信息生產(chǎn)、傳播更加快速,因此,數(shù)據(jù)體積日漸龐大、種類繁多。面向海量數(shù)據(jù)的處理訴求,迫使聚類算法提高可伸縮性。Spark 并行框架因內(nèi)存計算的特性受到廣泛關(guān)注,且對聚類算法加速效果顯著,因此研究者將譜聚類算法與Spark 有機結(jié)合?;赟park 的譜聚類算法通過減少數(shù)據(jù)計算及數(shù)據(jù)傳輸開銷,從而降低算法時耗,增強譜聚類算法處理大數(shù)據(jù)的可用性。
針對基于Spark 的并行策略設(shè)計,朱光輝[56]與崔藝馨[57]等人提出算法并行策略。朱光輝等人提出的并行譜聚類算法(Spectral Clustering Algorithm Based on Spark,SCoS)中包含四個主要步驟并行化,分別為:
(1)相似矩陣構(gòu)建與稀疏化過程并行化;
(2)拉普拉斯矩陣構(gòu)建與正規(guī)化過程并行化;
(3)正規(guī)化拉普拉斯矩陣特征向量計算并行化;
(4)K-means聚類并行化。
基于多輪迭代并行方法構(gòu)建相似矩陣,在減輕主節(jié)點壓力的同時避免重復(fù)計算相似度。t近鄰方式對相似矩陣進行稀疏化,達(dá)到節(jié)省存儲空間與減少L矩陣計算量目的。由公式(6)可知,L正規(guī)化通過三矩陣鏈乘實現(xiàn),時間復(fù)雜度高。為降低求解Lnor時間復(fù)雜度,通過對角陣D的性質(zhì)對L進行相應(yīng)行列變換,即可得到Lnor。針對特征向量的求解,SCoS算法基于Scala PACK實現(xiàn)特征向量并行化求解。崔藝馨等人基于上述研究基礎(chǔ),采用二叉樹索引網(wǎng)格劃分對并行數(shù)據(jù)劃分,通過邊界值劃分?jǐn)U展提升數(shù)據(jù)分塊合理性。
基于Spark的譜聚類算法一般依賴高級語言得以實現(xiàn),而Julia語言雖然同為高級語言,但性能媲美靜態(tài)編譯語言且專為并行與分布式計算設(shè)計。Huo 等人[58]采用Julia 語言實現(xiàn)多處理器并行的譜聚類算法?;贘ulia 的譜聚類采用k近鄰策略計算W矩陣,并將k個特征值求解看作圖分割問題。得益于Julia的易用性與靈活性,算法通過調(diào)用ARPACK計算特征向量,且在二階段聚類采用K-means++提升算法穩(wěn)定性,最終文章通過實驗證明該并行策略的有效性與準(zhǔn)確性。
基于分布式平臺、語言的并行加速策略雖對譜聚類計算耗時問題有所緩解,但存在為減少時間消耗導(dǎo)致數(shù)據(jù)信息丟失影響算法準(zhǔn)確率問題。因此,Wu 等人[59]提出如圖5所示的隨機裝箱(Random Bining Features,RB)算法,采用RB算法得到矩陣Z代替相似矩陣W,并對后續(xù)特征分解加速。該方法應(yīng)用BR特征矩陣內(nèi)積近似表示W(wǎng),避免相似矩陣計算。采用預(yù)處理迭代多方法特征求解器,降低L矩陣特征分解時耗,最終得到線性時間復(fù)雜度的譜聚類算法,且優(yōu)化后的譜聚類算法時間開銷更少,對大規(guī)模數(shù)據(jù)適應(yīng)良好。
圖5 RB算法流程圖
上述算法因優(yōu)化出發(fā)角度不同而略有差異,在矩陣計算階段,Spark 環(huán)境下的譜聚類算法通過多輪迭代的方式避免重復(fù)計算數(shù)據(jù)間相似度,而基于RB 優(yōu)化的譜聚類算法通過計算落在同一網(wǎng)格內(nèi)數(shù)據(jù)點的相似度來減少計算開銷;在拉普拉斯矩陣求解階段,前者利用稀疏相似矩陣的特性,進行相應(yīng)行的操作得到Lnor,后者采用近似相似矩陣Z與度矩陣公式轉(zhuǎn)換得到L矩陣。以上優(yōu)化策略算法加速工作較為完善,但未像基于Julia的譜聚類算法一樣,考慮第二階段聚類算法對算法整體聚類性能、準(zhǔn)確率等方面影響。
2.3.2 譜圖劃分改進方法
譜聚類算法受譜圖劃分思想啟發(fā),通過構(gòu)造數(shù)據(jù)有權(quán)無向圖并逼近最優(yōu)圖劃分,進而求解聚類問題,而圖劃分結(jié)果與切割準(zhǔn)則密切相關(guān)。隨著樣本類別、數(shù)目、維度及數(shù)量等特性的改變,對劃分準(zhǔn)則進行相應(yīng)改進以提升譜聚類算法聚類精度及可伸縮性。
Chen等人[60]直接優(yōu)化規(guī)范切割準(zhǔn)則,得到直接規(guī)范切割模型(Direct Normalized Cut,DNC)。通過DNC來對規(guī)范切割模型進行直接運算,將算法時間復(fù)雜度降至O(n2c)。針對大規(guī)模數(shù)據(jù)處理,以DNC 為基礎(chǔ)提出快速規(guī)范切割法(Fast Normalized Cut,F(xiàn)NC),F(xiàn)NC 使用均衡K平均值算法,將數(shù)據(jù)分為均衡子集并采用子集中心為Anchor(錨點),計算錨點與整個數(shù)據(jù)的相似矩陣,最終通過DNC得到聚類結(jié)果矩陣Y。
相較于其他改進策略,DNC 對目標(biāo)函數(shù)進行改進使目標(biāo)函數(shù)收斂,并對問題進行求解,將譜聚類算法時間復(fù)雜度降為二次。FNC算法通過均衡K-means算法通過錨點采樣以減少相矩陣計算,并達(dá)到線性時間復(fù)雜度,且在人造數(shù)據(jù)集與真實數(shù)據(jù)集上均表現(xiàn)出色。
2.3.3 其他快速優(yōu)化方法
基于錨點圖的模型被提出以應(yīng)對規(guī)??焖僭鲩L的數(shù)據(jù),當(dāng)譜聚類算法采用錨點模型聚類時,使用過于稀疏的錨點會降低算法性能,而錨點密度足夠大時,算法時間成本顯著增加且處理困難。針對該問題,YANG等人[61]通過構(gòu)建金字塔多層錨點,如圖6所示,并利用原始數(shù)據(jù)層H0 與最后錨點層Hm構(gòu)造層次二分圖,旨在減少相似矩陣計算量與時耗。圖6(a)為金字塔模型示意圖,其中H0 為原始數(shù)據(jù)層,H2、H3 為錨點層。圖6(b)展示了H0 層與錨點層的分布與選取情況。
圖6 三層金字塔Anchor示意圖
在錨點圖模型當(dāng)中,選取錨點的質(zhì)量影響聚類效果。因此,采用如下混合數(shù)據(jù)代表點選取方法[62]。
(1)隨機選取P個候選點(其中p
(2)在P上運用K-means 算法選擇p個簇類中心作為最終代表點,并記作R={r1,r2,…,rp}。
混合數(shù)據(jù)代表點選取方法在更好捕捉數(shù)據(jù)結(jié)構(gòu)特征的同時降低算法計算量與時耗。
Nystr?m通過對數(shù)據(jù)近似計算來逼近真實的特征空間,從而降低計算復(fù)雜度,因此譜聚類算法可以通過Nystr?m 采樣法提升算法可用性。丁世飛[63]、劉靜姝[64]及邱云飛[65]等人從采樣角度出發(fā),尋求譜聚類與海量數(shù)據(jù)采樣契合點。丁世飛等人采用自適應(yīng)采樣方法多次遍歷采樣,每次采樣后更新剩余點采樣概率以提升采樣質(zhì)量。最終在犧牲較少精度條件下,達(dá)到大幅降低計算復(fù)雜度、提升算法穩(wěn)定性的目的。劉靜姝等人在Nystr?m基礎(chǔ)上運用乘法更新原理,實現(xiàn)分類指示矩陣更新,避免高時耗譜分解步驟。相比于傳統(tǒng)譜聚類算法,該策略在處理高維數(shù)據(jù)時更快速。邱云飛等人則針對Nystr?m方法選取樣本代表性弱問題,將加權(quán)思想引入,基于加權(quán)數(shù)據(jù)K-means聚類中心點采樣,且在Nystr?m階段采取并行處理方式提升集成多樣性與高效性,最終大幅降低算法復(fù)雜度。
在提升算法運行效率方面,基于分布平臺并行加速策略通常對平臺依賴性較高,且并行聚類結(jié)果合并方式直接對算法結(jié)果精度產(chǎn)生影響。而為降低算法計算復(fù)雜度與時耗,采樣方式難免引入隨機性的干擾,導(dǎo)致算法聚類精度有所下降。算法執(zhí)行效率優(yōu)化策略具體對比分析如表4所示。
表4 執(zhí)行效率策略對比
譜聚類的三類優(yōu)化策略各有側(cè)重點,優(yōu)化策略彼此互相借鑒成為近年譜聚類算法優(yōu)化的熱點。每類優(yōu)化策略特點不同,如限制策略注重樣本局部信息,距離測度策略側(cè)重樣本整體分布,兩策略相輔相成。譜聚類的具體優(yōu)化方法、策略對比分析如表5所示。
表5 優(yōu)化譜聚類算法對比
本章首先對譜聚類常用的相關(guān)數(shù)據(jù)集與評價指標(biāo)進行簡要介紹,基于部分?jǐn)?shù)據(jù)集與評價指標(biāo),選取譜聚類及代表性譜聚類優(yōu)化算法對比實驗,最終通過實驗進行對比分析。
譜聚類算法所采用數(shù)據(jù)集一般分為兩類,一類是以UCI 數(shù)據(jù)集為代表的小樣本數(shù)據(jù)集(https://archive.ics.uci.edu/ml/index.php);另一類是以圖像數(shù)據(jù)集為代表的大樣本數(shù)據(jù)集。表6、表7 對常用的兩類數(shù)據(jù)集的特點與特征進行相關(guān)總結(jié)。
表7 常見譜聚類算法圖片數(shù)據(jù)集
采用準(zhǔn)確率Acc(Accuracy)、蘭德指數(shù)RI(RandIndex)、調(diào)整蘭德指數(shù)ARI(Adjusted Rand Index)、標(biāo)準(zhǔn)互信息NMI(Normalized Mutual Information)、調(diào)整互信息AMI(Adjusted Mutual Information)等不同的關(guān)鍵性能指標(biāo),對譜聚類算法進行評價,相關(guān)公式如下:
公式(14)中,N為樣本數(shù)量,分別為聚類結(jié)果與數(shù)據(jù)標(biāo)簽,K為簇類個數(shù),δ(x,y)函數(shù)當(dāng)且僅當(dāng)x=y時值為1,否則為0[57]。
公式(17)中,MI(X,Y)為變量X、Y之間的互信息,H(X)為變量X的熵。
本節(jié)在Iris、Wine、Ionosphere、Glass 以及手寫體數(shù)據(jù)集上,采用不同譜聚類算法進行實驗對比,并進行分析總結(jié)。列舉近幾年代表性的譜聚類優(yōu)化算法的實驗結(jié)果,并在數(shù)據(jù)集上進行實驗對比與數(shù)據(jù)分析。實驗采用CPU 3.6 GHz、32 GB 內(nèi)存、Windows10 操作系統(tǒng),編程環(huán)境PyCharm2020.2.2、python3.8。為客觀性地對比算法的聚類指標(biāo),實驗將譜聚類(SC)算法與隨機約束譜聚類(RCSC)算法分別在各個數(shù)據(jù)集上執(zhí)行10次,并計算其聚類的平均指標(biāo)。
該實驗分為兩個部分:實驗一為基于UCI小樣本數(shù)據(jù)集的SC算法、RCSC算法以及基于低密度分割密度敏感距離的譜聚類算法(Low Density Separation Density Sensitive Distance-based Spectral Clustering algorithm,LDSDSD-SC)算法對比分析實驗,以上三種算法在UCI數(shù)據(jù)集上的關(guān)參數(shù)及蘭德指數(shù)如表8所示;實驗二為基于手寫體數(shù)據(jù)集的大樣本分析對比實驗,其中SC算法、CSoC 算法、FNC 算法以及基于層次二分圖譜聚類算法(Spectral Clustering Based on Hierarchical Bipartite Graph,SCHBG)算法在手寫體數(shù)據(jù)集上的準(zhǔn)確率與標(biāo)準(zhǔn)互信息如表9所示。
表8 基于UCI譜聚類算法對比
表9 基于手寫數(shù)據(jù)集上譜聚類算法對比
實驗一中,由表8中蘭德指數(shù)在不同數(shù)據(jù)集上整體對比可知,譜聚類算法在樣本數(shù)量小且數(shù)據(jù)較為平衡的數(shù)據(jù)集上,如Iris、Wine聚類性能良好,而在樣本數(shù)據(jù)不平衡數(shù)據(jù)集上,如Ionosphere、Glass 聚類性能稍遜。在Iris與Glass數(shù)據(jù)集上,基于密度距離改進的LDSDSD-SC[43]算法聚類性能最優(yōu),證明基于密度距離改進策略的優(yōu)越性。而Wine 因數(shù)據(jù)特征間數(shù)值差過大,導(dǎo)致直接聚類效果差,因此,在CS與RCSC算法中對數(shù)據(jù)集進行歸一化處理,故SC與RCSC算法聚類性能明顯優(yōu)于LDSDSDSC[43]算法,這也體現(xiàn)了數(shù)據(jù)預(yù)處理步驟的重要性。觀察Ionosphere數(shù)據(jù),相比于SC算法基于半監(jiān)督優(yōu)化的RCSC算法聚類性能會更優(yōu),但RCSC優(yōu)化策略具有隨機性聚類結(jié)果不穩(wěn)定。
實驗二中可由Acc與NMI數(shù)值觀察得知,在MNIST數(shù)據(jù)集及USPS 數(shù)據(jù)集上,基于錨點的層次二分圖改進策略聚類性能顯然更優(yōu),而SC算法聚類MNIST這樣大規(guī)模數(shù)據(jù)集存儲需求大,在實驗過程中內(nèi)存溢出導(dǎo)致聚類中斷,因此從對大數(shù)據(jù)處理方面證明SCHBG 算法優(yōu)化策略的優(yōu)異性。觀察CSoS算法NMI值可知,僅采用Spark 平臺加速對譜聚類算法的提升有限,與其他優(yōu)化策略如稀疏化等,可對譜聚類算法性能明顯提升。
近年來,譜聚類因其獨特的優(yōu)點與特性引起學(xué)術(shù)界大量關(guān)注,經(jīng)過研究者們不斷改進譜聚類算法性能逐級提高,但以下方向需要進一步研究。
(1)利用數(shù)據(jù)局部與全局先驗信息構(gòu)建相似矩陣
W矩陣是譜聚類算法誤差來源的第一環(huán),現(xiàn)有構(gòu)建W矩陣的方法眾多,如本文所介紹的基于限制的譜聚類算法,該種方法雖然利用少量標(biāo)簽實現(xiàn)對W的優(yōu)化,但并未使用其他方面的先驗信息,例如,密度先驗信息,且該方法時間復(fù)雜度較高。因此,在現(xiàn)有算法改進基礎(chǔ)上深入研究,結(jié)合多方面特征來構(gòu)造相似矩陣W,進一步提高譜聚類算法的精確性并降低時耗,也是未來提高聚類算法的一個重要的研究方向。
(2)利用矩陣?yán)碚撆c數(shù)據(jù)特征自動確定參數(shù)
對于聚類算法而言,算法結(jié)果對參數(shù)的選擇十分敏感。譜聚類算法參數(shù)一般為核函數(shù)參數(shù)與類數(shù)K,不同的參數(shù)生成不同的W,因此參數(shù)選取對聚類結(jié)果影響明顯。針對類數(shù)K的確定,本文所介紹自動確定K值的譜聚類算法,通過利用本征間隙特征來確定K。該方法實現(xiàn)K值自動確定,但涉及較多計算與排序??山梃b目前其他聚類算法自動確定參數(shù)策略,并進行相應(yīng)改進后應(yīng)用在譜聚類算法上,達(dá)到自動確定參數(shù)目的。針對大樣本數(shù)據(jù),高效快速自動確定K值也是譜聚類算法一個值得研究的方向。
(3)海量數(shù)據(jù)抽樣預(yù)處理提升算法性能
針對基于大量數(shù)據(jù)的樣本數(shù)據(jù)不均勻問題、傳統(tǒng)譜聚類算法時空復(fù)雜度高,無法適用于較大數(shù)據(jù)樣本等問題。聚類算法需要進一步解決,雖然基于Spark 平臺及二分圖等方式可對算法進行加速,降低算法時耗,但針對算法自身優(yōu)化來降低時間復(fù)雜度仍舊是該領(lǐng)域的未來研究熱點之一。
(4)啟發(fā)式算法向譜聚類算法遷移應(yīng)用
現(xiàn)階段,以蜂群算法等為代表的啟發(fā)式算法與譜聚類算法結(jié)合已有研究,且已通過相關(guān)實驗證明其有效性。因此,將譜聚類算法與啟發(fā)式算法進行有機結(jié)合,借鑒其優(yōu)化算法思想,并根據(jù)譜聚類算法的特性進行調(diào)整,形成吸納新型算法的優(yōu)點的優(yōu)化譜聚類算法,不但提升譜聚類算法聚類效果,而且形成新優(yōu)化方法,這也將成為未來譜聚類算法研究方向之一。