白 璐，趙 鑫，孔鈺婷，張正航，邵金鑫，錢育蓉

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ù)雜度。

1 譜聚類算法概述

譜聚類算法的思想起源于譜圖劃分理論[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á)。

1.1 相似矩陣與拉普拉斯矩陣

一般情況下，求解譜圖劃分的最優(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為單位矩陣。

1.2 特征值選取

譜聚類算法通常選取前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ù)雜的缺點。

1.3 譜聚類算法存在的不足

由于譜聚類算法應(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)化。

2 譜聚類改進算法

隨著社會的數(shù)字化，譜聚類算法應(yīng)用范圍與場景發(fā)生改變，算法及模型需要及時優(yōu)化與改進才能保持可用性與魯棒性。

2.1 半監(jiān)督與距離測度優(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)化策略對比

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 二階段聚類算法對比

2.3 執(zhí)行效率優(yōu)化方法

傳統(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í)行效率策略對比

2.4 譜聚類優(yōu)化方法小結(jié)

譜聚類的三類優(yōu)化策略各有側(cè)重點，優(yōu)化策略彼此互相借鑒成為近年譜聚類算法優(yōu)化的熱點。每類優(yōu)化策略特點不同，如限制策略注重樣本局部信息，距離測度策略側(cè)重樣本整體分布，兩策略相輔相成。譜聚類的具體優(yōu)化方法、策略對比分析如表5所示。

表5 優(yōu)化譜聚類算法對比

3 數(shù)據(jù)集與算法性能比較

本章首先對譜聚類常用的相關(guān)數(shù)據(jù)集與評價指標(biāo)進行簡要介紹，基于部分?jǐn)?shù)據(jù)集與評價指標(biāo)，選取譜聚類及代表性譜聚類優(yōu)化算法對比實驗，最終通過實驗進行對比分析。

3.1 數(shù)據(jù)集

譜聚類算法所采用數(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ù)集

3.2 評價標(biāo)準(zhǔn)

采用準(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的熵。

3.3 實驗結(jié)果與分析

本節(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)化策略如稀疏化等，可對譜聚類算法性能明顯提升。

4 結(jié)束語

近年來，譜聚類因其獨特的優(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)化方法，這也將成為未來譜聚類算法研究方向之一。