譜聚類(lèi)算法研究綜述

白 璐，趙 鑫，孔鈺婷，張正航，邵金鑫，錢(qián)育蓉

1.新疆大學(xué) 軟件學(xué)院，烏魯木齊830046

2.新疆大學(xué) 軟件學(xué)院重點(diǎn)實(shí)驗(yàn)室，烏魯木齊830046

3.新疆維吾爾自治區(qū)信號(hào)檢測(cè)與處理重點(diǎn)實(shí)驗(yàn)室，烏魯木齊830046

聚類(lèi)分析是一種挖掘數(shù)據(jù)深層信息與知識(shí)的有效方法，聚類(lèi)是將給定的樣本劃分成多個(gè)簇的過(guò)程。聚類(lèi)最優(yōu)準(zhǔn)則[1-2]的目標(biāo)是使同一簇內(nèi)的樣本間相似度高，不同簇樣本間相似度低。K-均值（K-means）算法是傳統(tǒng)聚類(lèi)中的經(jīng)典算法，K-means算法雖然易于理解但仍存在局限性，如對(duì)樣本形狀包容性差、易陷入局部最優(yōu)解[3]等問(wèn)題。

為能在任意形狀的樣本空間上達(dá)到良好聚類(lèi)性能，研究者們提出譜聚類(lèi)算法（Spectral Clustering Algorithm，SC），SC 算法擁有對(duì)樣本形狀敏感度低、收斂于全局最優(yōu)解、對(duì)高維數(shù)據(jù)支持較好[4]等特點(diǎn)，因此SC算法[5]如今廣泛應(yīng)用于數(shù)據(jù)挖掘[6]、圖像分割[7-9]、模式識(shí)別[10]以及遙感[11-12]等領(lǐng)域。近年來(lái)隨著應(yīng)用場(chǎng)景變化，大規(guī)模數(shù)據(jù)聚類(lèi)高時(shí)耗問(wèn)題成為一個(gè)研究熱點(diǎn)，而譜聚類(lèi)算法存在同樣的聚類(lèi)挑戰(zhàn)[13]。

譜聚類(lèi)算法是一種建立在譜圖理論上的聚類(lèi)算法，主要分為兩類(lèi)：迭代譜聚類(lèi)算法與多路譜聚類(lèi)算法，分別以SM[14]算法與NJW[15]算法為代表。在多路譜聚算法中，為解決NJW算法需要人工設(shè)置簇?cái)?shù)K等參數(shù)問(wèn)題，孔萬(wàn)增等人[16]利用本征間隙特征，實(shí)現(xiàn)自動(dòng)確定K值的譜聚類(lèi)算法；為達(dá)到更好的聚類(lèi)性能，王玲等人[17]提出基于數(shù)據(jù)先驗(yàn)信息的半監(jiān)督譜聚類(lèi)算法；為解決譜聚類(lèi)算高法時(shí)空復(fù)雜度、對(duì)大數(shù)據(jù)樣本適應(yīng)性差等問(wèn)題，將譜聚類(lèi)部署在Hadoop、Spark 等平臺(tái)，利用平臺(tái)分布并行特性降低譜聚類(lèi)算法時(shí)耗，或通過(guò)優(yōu)化譜聚類(lèi)切割模型，來(lái)降低算法時(shí)間復(fù)雜度。

1 譜聚類(lèi)算法概述

譜聚類(lèi)算法的思想起源于譜圖劃分理論[18]，譜聚類(lèi)通過(guò)樣本相似度生成無(wú)向加權(quán)圖，樣本點(diǎn)可看作圖的頂點(diǎn)，樣本點(diǎn)間的相似度為兩點(diǎn)間邊的權(quán)重，而對(duì)無(wú)向加權(quán)圖進(jìn)行譜圖劃分就是將圖劃分為若干個(gè)子圖，該過(guò)程與聚類(lèi)算法的聚類(lèi)過(guò)程對(duì)應(yīng)。圖論的最優(yōu)劃分準(zhǔn)則[14]與聚類(lèi)最優(yōu)準(zhǔn)則在思想上具有一致性，為聚類(lèi)問(wèn)題轉(zhuǎn)化為圖劃分問(wèn)題提供思路與理論支撐。對(duì)于譜圖劃分而言，圖劃分準(zhǔn)則的選取將直接影響劃分結(jié)果，常用的圖劃分準(zhǔn)則有規(guī)范割集、最小割集、平均割集、比例割集等準(zhǔn)則[19]。與譜圖劃分相比，譜聚類(lèi)算法考慮問(wèn)題連續(xù)放松形式，將圖分割問(wèn)題轉(zhuǎn)換為求相似矩陣的譜分解問(wèn)題[20]。譜聚類(lèi)算法依據(jù)劃分準(zhǔn)則的不同，總體分為迭代譜聚算法與多路譜聚類(lèi)算法。目前多路譜聚類(lèi)算法因其簡(jiǎn)單易于理解特性應(yīng)用更為廣泛，NJW 算法是經(jīng)典多路譜聚類(lèi)算法。多路譜聚算法實(shí)現(xiàn)細(xì)節(jié)略有差異，但核心思想基本一致，其主要思想如下：

步驟1 通過(guò)樣本構(gòu)建可描述樣本特性的矩陣W。

步驟2 計(jì)算矩陣W的特征值及特征向量并對(duì)其進(jìn)行排序。

步驟3 取排序后前k個(gè)特征值對(duì)應(yīng)特征向量，將向量按列方向排列，組成新解空間。

步驟4 在新解空間上采用典聚類(lèi)算法進(jìn)行聚類(lèi)（模糊聚類(lèi)、K-means等），最終將聚類(lèi)結(jié)果映射回原解空間。

在譜聚類(lèi)算法步驟1 中，采用相似矩W來(lái)表示樣本數(shù)據(jù)間的相似性是對(duì)數(shù)據(jù)集的特征的一種抽象表達(dá)。

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

一般情況下，求解譜圖劃分的最優(yōu)劃分準(zhǔn)則是NP難度問(wèn)題，通過(guò)連續(xù)放松形式將圖劃分問(wèn)題轉(zhuǎn)化為相似矩陣譜分解問(wèn)題，因此譜聚類(lèi)算法是對(duì)最優(yōu)圖劃分準(zhǔn)則的逼近[21]。近年放松形式的譜聚類(lèi)算法研究較多，最早譜聚類(lèi)采用樣本鄰接矩陣直接進(jìn)行圖劃分[22]，但譜聚類(lèi)算法的準(zhǔn)確率受矩陣質(zhì)量影響，一般而言矩陣質(zhì)量越高，聚類(lèi)結(jié)果越理想。

現(xiàn)階段譜聚類(lèi)算法多基于相似矩陣（Affinity Matrix），采用W或A表示，本文統(tǒng)一采用W表示。相似矩陣定義如下：

公式（1）中v為數(shù)據(jù)樣本點(diǎn)；d(vi,vj)為兩樣本點(diǎn)之間的距離，一般取歐氏距離；σ為尺度參數(shù)，W隨著σ取值變化而改變，因此σ需要經(jīng)過(guò)多次取值實(shí)驗(yàn)才能確定[23]。

度矩陣是記為D的對(duì)角矩陣，度值為對(duì)角元素。計(jì)算方式如公式（2）所示：

規(guī)范相似矩陣一般形式定義為：

在面向降低W計(jì)算量方面，對(duì)數(shù)據(jù)提前進(jìn)行特定清洗，在去除噪聲的同時(shí)保留更有代表性的數(shù)據(jù)；而在提升W質(zhì)量方面，通過(guò)改進(jìn)相似矩陣的求解的模型或引入監(jiān)督機(jī)制[24]，更正相似矩陣，從而提升譜聚類(lèi)算法聚類(lèi)性能。

譜聚類(lèi)算法早期直接采用W的最大k個(gè)特征向量進(jìn)行聚類(lèi)，但W無(wú)法保證被選中的k個(gè)特征值對(duì)應(yīng)的特征向量為異塊向量。因此，通過(guò)W選取特征向量，存在多次選取一塊特征向量問(wèn)題，進(jìn)而導(dǎo)致選取的特征向量代表性較差。拉普拉斯矩陣L（Laplacian Matrix）為半正定矩陣，L特征值最小為0且對(duì)應(yīng)的特征向量為1。當(dāng)選取L的前k個(gè)特征值所對(duì)應(yīng)的特征向量時(shí)，可確保每個(gè)分量?jī)H含有一個(gè)特征向量[5]，因此將L矩陣引入譜聚類(lèi)中。L矩陣一般分為規(guī)范拉普拉斯矩陣和非規(guī)范拉普拉斯矩陣，非規(guī)范拉普拉斯矩陣表示為：

規(guī)范拉普拉斯矩陣兩種形式，I為單位矩陣。

1.2 特征值選取

譜聚類(lèi)算法通常選取前k個(gè)特征值所對(duì)應(yīng)的特征向量，以NJW 算法為例，NJW 算法采用公式（3）計(jì)算Wnor。而由公式（6）可知，求解Wnor的最大特征值等同于求解Lnor的最小特征值，因此NJW 算法也等同基于Lnor前k個(gè)最小特征進(jìn)行聚類(lèi)[25]。當(dāng)采用W進(jìn)行聚類(lèi)時(shí)，由于公式（1）是基于距離測(cè)度的計(jì)算方法，而兩點(diǎn)間距離最小為0，因此有效區(qū)間為[0,+∞]。在公式（1）有效區(qū)間內(nèi)，W的取值均處在0 到1 之間，如圖1 紅線(xiàn)部分所示。

圖1 W 取值示意圖

在機(jī)器學(xué)習(xí)特征提取中，最大特征值對(duì)應(yīng)的特征向量方向上通常包含最多信息量[26]。因此，在W特征向量選取過(guò)程中選擇前k個(gè)最大特征值所對(duì)應(yīng)的特征向量。雖然該選擇策略可大概率保證選取質(zhì)量，但仍存在高信息量的特征值不一定有較高的分類(lèi)貢獻(xiàn)信息量問(wèn)題。

針對(duì)特征向量選取問(wèn)題，王洪森等人[27]與王興良等人[28]從特征值k值設(shè)定閾值入手，擴(kuò)大選入特征值與特征向量數(shù)量。王洪森選取矩陣前3k個(gè)特征值并求取平均值記為λ，最終選擇λ數(shù)值最k近鄰的特征值，但對(duì)于3k的取值未解釋其必然性，且基于均值的選擇策略易受樣本數(shù)量影響，增加時(shí)間消耗。王興良等人提出基于約束分值的特征向量（Bootstrap aggregating，Bagging）選取法。算法選取L前2k個(gè)特征向量，并采用成對(duì)約束計(jì)分方法與Bagging 結(jié)合，在特征值選擇階段效果良好?；贐agging 的選取策略相較均值選擇策略而言，向量的選取方式理論依據(jù)更強(qiáng)，但也無(wú)法避免計(jì)算復(fù)雜的缺點(diǎn)。

1.3 譜聚類(lèi)算法存在的不足

由于譜聚類(lèi)算法應(yīng)用場(chǎng)景的不斷變化，傳統(tǒng)譜聚類(lèi)算無(wú)法使小數(shù)量標(biāo)簽發(fā)揮相應(yīng)價(jià)值、W矩陣構(gòu)造階段并未包含數(shù)據(jù)的多元特征，如部分先驗(yàn)標(biāo)簽信息、空間信息等，W經(jīng)過(guò)譜分解、聚類(lèi)等操作后，特征缺乏引起的誤差將會(huì)放大，最終影響最終聚類(lèi)結(jié)果，同時(shí)兩階段聚類(lèi)方式易受二階段聚類(lèi)算法缺點(diǎn)影響。在算法時(shí)耗方面，傳統(tǒng)譜聚類(lèi)算法因矩陣W與矩陣L計(jì)算量大，在處理小樣本數(shù)據(jù)集時(shí)聚類(lèi)性能良好，但處理大規(guī)模數(shù)據(jù)集時(shí)，傳統(tǒng)譜聚類(lèi)因數(shù)據(jù)量過(guò)大導(dǎo)致聚類(lèi)中斷。

針對(duì)上述譜聚類(lèi)算法的不足，眾多學(xué)者不斷提出改進(jìn)算法來(lái)解決以上問(wèn)題，并在現(xiàn)有研究條件下均衡優(yōu)化算法的時(shí)間、空間開(kāi)銷(xiāo)及算法聚類(lèi)性能。本文基于現(xiàn)有的譜聚類(lèi)算法優(yōu)化策略與方向，將譜聚類(lèi)優(yōu)化算法劃分為以下三類(lèi)：半監(jiān)督與距離測(cè)度優(yōu)化、二階段聚類(lèi)算法優(yōu)化及執(zhí)行效率優(yōu)化。

2 譜聚類(lèi)改進(jìn)算法

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

2.1 半監(jiān)督與距離測(cè)度優(yōu)化方法

機(jī)器學(xué)習(xí)分為無(wú)監(jiān)督學(xué)習(xí)與監(jiān)督學(xué)習(xí)，而現(xiàn)有的數(shù)據(jù)樣本一般僅有少量標(biāo)簽，采用無(wú)監(jiān)督學(xué)習(xí)數(shù)據(jù)標(biāo)簽將被舍棄，而少量標(biāo)簽也無(wú)法滿(mǎn)足監(jiān)督學(xué)習(xí)需求。半監(jiān)督學(xué)習(xí)結(jié)合監(jiān)督與無(wú)監(jiān)督學(xué)習(xí)特性，使標(biāo)簽的發(fā)揮相應(yīng)價(jià)值，既節(jié)省人工成本又避免標(biāo)簽浪費(fèi)。通過(guò)半監(jiān)督形式發(fā)揮標(biāo)簽應(yīng)有的作用，最終優(yōu)化算法精確度[29-30]，且經(jīng)過(guò)文獻(xiàn)[31]實(shí)驗(yàn)證明，相比無(wú)監(jiān)督聚類(lèi)算法，半監(jiān)督聚類(lèi)算法的聚類(lèi)準(zhǔn)確率更高，同時(shí)半監(jiān)督譜聚類(lèi)現(xiàn)今應(yīng)用于功能磁共振[32]與印刷套準(zhǔn)[33]等領(lǐng)域。下面將詳細(xì)介紹限制與測(cè)度兩種方法及相關(guān)優(yōu)化策略。

2.1.1 基于先驗(yàn)信息限制方法

基于限制的半監(jiān)督譜聚類(lèi)算法采用成對(duì)限制先驗(yàn)信息更改W，達(dá)到提升聚類(lèi)性能與準(zhǔn)確率目的，這也是限制半監(jiān)督譜聚類(lèi)算法的核心思想[34]。而針對(duì)譜聚類(lèi)半監(jiān)督化思想，Kamvar 等人[35]在2003 年提出并實(shí)現(xiàn)基于數(shù)據(jù)樣本自適應(yīng)的譜聚類(lèi)算法，該算法同時(shí)適應(yīng)與無(wú)監(jiān)督與有監(jiān)督聚類(lèi)并具有較好精度。

半監(jiān)督譜聚類(lèi)算法通常采用兩類(lèi)成對(duì)限制，即Must-Link（ML）與Cannot-Link（CL）來(lái)輔助聚類(lèi)搜索[36]。當(dāng)兩個(gè)樣本存在ML 限制時(shí)，對(duì)應(yīng)樣本劃分為同一類(lèi)，若存在CL限制對(duì)應(yīng)樣本劃分于不同類(lèi)中。成對(duì)先驗(yàn)信息與相似度矩陣同樣具有如下對(duì)稱(chēng)性與傳遞性。

對(duì)稱(chēng)性：

對(duì)于任意的i、j、q均存在以下傳遞性：

采用半監(jiān)督聚類(lèi)算法時(shí)，成對(duì)限制先驗(yàn)信息與聚類(lèi)算法中W對(duì)應(yīng)關(guān)系如公式（10）所示：

在理想狀況下，xi,xj屬于一類(lèi)Wij=1,否則Wij=0,以上分別對(duì)應(yīng)ML 與CL 情況。通過(guò)公式（10），成對(duì)約束先驗(yàn)信息直接修改相似矩陣，對(duì)聚類(lèi)進(jìn)行監(jiān)督矯正，提高相似矩陣質(zhì)量，得到更加精準(zhǔn)的聚類(lèi)結(jié)果。

通常譜聚類(lèi)基于現(xiàn)有成對(duì)約束，直接聚類(lèi)的策略對(duì)算法提升有限，而成對(duì)約束擁有如公式（8）、（9）所示性質(zhì)，因此成對(duì)約束傳播可挖掘隱性約束信息。在面向成對(duì)約束傳播問(wèn)題，趙曉曉等人[37]提出結(jié)合稀疏表示和約束傳遞的半監(jiān)督譜聚類(lèi)算法。該算法在普通約束譜聚類(lèi)基礎(chǔ)上，將約束集合中的數(shù)據(jù)作為地標(biāo)點(diǎn)來(lái)構(gòu)造稀疏表示矩陣，獲得近似相似度矩陣，同時(shí)根據(jù)相似度矩陣生成連通區(qū)域，在每個(gè)連通區(qū)域內(nèi)動(dòng)態(tài)調(diào)整近鄰點(diǎn)，利用約束傳遞進(jìn)一步提高聚類(lèi)準(zhǔn)確率。

對(duì)半監(jiān)督譜聚類(lèi)算法而言，監(jiān)督信息的質(zhì)量、可靠性與數(shù)目對(duì)準(zhǔn)確率影響較大，為避免選取低質(zhì)量約束，Wang[31]與王娜[24]等人從提升監(jiān)督信息選取質(zhì)量入手，提升選取監(jiān)督信息質(zhì)量。Wang等人采用主動(dòng)查詢(xún)策略替換隨機(jī)查詢(xún)策略，并采用主動(dòng)查詢(xún)函數(shù)來(lái)動(dòng)態(tài)選擇約束以增強(qiáng)算法魯棒性；關(guān)于譜聚類(lèi)參數(shù)敏感問(wèn)題，通過(guò)采用Hessian矩陣代替拉普拉斯矩陣得到解決。王娜等人提出基于監(jiān)督信息特性的主動(dòng)半監(jiān)督譜聚類(lèi)算法，采用主動(dòng)學(xué)習(xí)策略挖掘數(shù)據(jù)深層信息如，屬于同一類(lèi)但樣本距離較遠(yuǎn)的樣本點(diǎn)信息；或?qū)儆诓煌?lèi)但樣本距離較近的樣本點(diǎn)信息，以上信息均稱(chēng)為高質(zhì)量信息。低質(zhì)量約束信息如圖2（a）所示，該圖中監(jiān)督信息可通過(guò)聚類(lèi)輕易獲得，對(duì)聚類(lèi)監(jiān)督矯正作用弱，所提供的監(jiān)督信息對(duì)聚類(lèi)貢獻(xiàn)度低。高質(zhì)量約束信息如圖2（b）所示，約束信息e-i=CL、j-g=ML與h-d=CL是通過(guò)聚類(lèi)算法無(wú)法輕易獲取的高質(zhì)量信息，因此，通過(guò)選取高質(zhì)量成對(duì)約束監(jiān)督信息，提高監(jiān)督信息對(duì)聚類(lèi)貢獻(xiàn)度，避免因監(jiān)督信息質(zhì)量低導(dǎo)致的聚類(lèi)結(jié)果提升不明顯等問(wèn)題。

圖2 高質(zhì)量與低質(zhì)量監(jiān)督信息示例圖

在現(xiàn)實(shí)應(yīng)用中，成對(duì)限制信息通常由用戶(hù)給定、隨機(jī)選取或主動(dòng)學(xué)習(xí)等方式獲得。面對(duì)真實(shí)數(shù)據(jù)集，算法無(wú)法正確聚類(lèi)樣本的對(duì)應(yīng)信息是提高算法精度與性能的關(guān)鍵，同時(shí)也是半監(jiān)督聚類(lèi)具有約束效力的高質(zhì)量監(jiān)督信息。相比于普通約束信息，含有高質(zhì)量約束信息的半監(jiān)督譜聚類(lèi)算法在準(zhǔn)確率上有顯著提升。

在層次聚類(lèi)中，Nazari 等人[38]提出的基于交點(diǎn)聚類(lèi)算法與成對(duì)約束信息的傳遞性類(lèi)似，該算法通過(guò)判斷兩簇是否存在交點(diǎn)來(lái)決定合并操作。如圖3所示，基于合并交點(diǎn)簇思想，簇間可通過(guò)傳遞的方式連續(xù)合并，這點(diǎn)與半監(jiān)督聚類(lèi)中成對(duì)約束信息的傳遞性類(lèi)似，焦點(diǎn)聚類(lèi)算不僅簡(jiǎn)單有效，且在球型的樣本表現(xiàn)、性能更優(yōu)。由此可見(jiàn)，監(jiān)督信息的傳遞等特性在聚類(lèi)中具有普適性。

圖3 交點(diǎn)聚類(lèi)算法示意圖

但僅基于成對(duì)限制的譜聚類(lèi)算法在處理流形數(shù)據(jù)時(shí)提升有限，因此肖成龍[39]與楊婷[40]等人受啟發(fā)于流形正則項(xiàng)，將其與譜聚類(lèi)結(jié)合，以提升譜聚類(lèi)在處理流行數(shù)據(jù)的聚類(lèi)性能。肖成龍等人將約束、正則化與深度譜聚類(lèi)結(jié)合，利用反向傳播將約束與正則信息調(diào)整權(quán)重。楊婷等人利用L2,1范數(shù)與成對(duì)監(jiān)督信息構(gòu)造高質(zhì)量W，并在此基礎(chǔ)上引入流行正則項(xiàng)。

選取質(zhì)量低或數(shù)量少的約束信息易對(duì)算法產(chǎn)生誤導(dǎo)作用，影響聚類(lèi)精度，因此選取高質(zhì)量先驗(yàn)信息形成約束以監(jiān)督指導(dǎo)聚類(lèi)?；谝延屑s束信息通過(guò)樣本傳播，以發(fā)現(xiàn)更深層約束信息，最終在約束與相似度矩陣的協(xié)同下提升算法準(zhǔn)確率。此外僅基于成對(duì)約束的譜聚類(lèi)算法在處理流形分布數(shù)據(jù)效果欠佳，引入樣本密度信息或流行正則項(xiàng)等策略，提升算法在處理流形數(shù)據(jù)的表現(xiàn)。具體基于先驗(yàn)信息優(yōu)化策略的對(duì)比分析如表1所示。

表1 先驗(yàn)信息策略對(duì)比

2.1.2 基于距離測(cè)度方法

在基于限制的半監(jiān)督聚類(lèi)中，存在限制信息重復(fù)導(dǎo)致信息含量小，無(wú)法獲得進(jìn)一步提升聚類(lèi)結(jié)果問(wèn)題。經(jīng)研究發(fā)現(xiàn)，僅基于樣本層面的限制先驗(yàn)信息質(zhì)量較低，無(wú)法獲得更優(yōu)解。針對(duì)該問(wèn)題，研究者將基于距離測(cè)度的半監(jiān)督方法引入譜聚類(lèi)算法，以便構(gòu)造包含多維特征的W矩陣?；跍y(cè)度的半監(jiān)督算法通過(guò)對(duì)監(jiān)督信息學(xué)習(xí)，改變聚類(lèi)算法中的距離測(cè)度函數(shù)，得到適合數(shù)據(jù)聚類(lèi)的新度量[41-42]，最終通過(guò)新測(cè)度計(jì)算W進(jìn)行聚類(lèi)。

在面向反應(yīng)數(shù)據(jù)全局一致性與空間一致性的測(cè)度方面，王玲[17]與陶新民[43]等人均從數(shù)據(jù)密度特點(diǎn)著手改進(jìn)算法。陶新民等人基于距離測(cè)度，定義含有伸縮因子與密度敏感項(xiàng)的密度敏感距離，通過(guò)調(diào)節(jié)參數(shù)到達(dá)類(lèi)內(nèi)高內(nèi)聚、類(lèi)間低耦合的理想狀態(tài)，且在時(shí)間復(fù)雜度不變的條件下，提升傳統(tǒng)基于歐氏距離的譜聚類(lèi)對(duì)流型樣本的聚類(lèi)性能。該算法同時(shí)采用譜熵貢獻(xiàn)率[44]、最大熵代替K-means算法等方式來(lái)提高算法的準(zhǔn)確率。王玲等人則借鑒限制與測(cè)度融合方法，采用圖最短路徑長(zhǎng)度生成密度敏感距離測(cè)度以計(jì)算W，同時(shí)成對(duì)先驗(yàn)信息對(duì)W矩陣進(jìn)行監(jiān)督矯正。算法密度敏感距離測(cè)度定義與相關(guān)步驟如下：

首先用密度可調(diào)節(jié)線(xiàn)段L代替?zhèn)鹘y(tǒng)距離：

dist(xi,xj)為數(shù)據(jù)點(diǎn)的歐氏距離。算法通過(guò)密度線(xiàn)段L計(jì)算得到密度敏感矩陣，密度敏感距離計(jì)算公式如下：

該測(cè)度將數(shù)據(jù)點(diǎn)看作圖的頂點(diǎn)V，將數(shù)據(jù)點(diǎn)間的線(xiàn)段L看作權(quán)重E。令p∈Vl表示圖上長(zhǎng)度為l=:||p的連接點(diǎn)pl和p||p的路徑。邊(pk,pk+1)∈E,k∈[1,||p]。Pi,j表示連接數(shù)據(jù)點(diǎn)xi、xj的所有路徑集合。

相似矩陣定義如下：

密度敏感距離通過(guò)ρ調(diào)節(jié)線(xiàn)段L的長(zhǎng)度，并由L組成矩陣L，通過(guò)L計(jì)算密度圖最短距，形成敏感距離，如公式（11）、（12）所示。利用成對(duì)約束信息，直接修改監(jiān)督點(diǎn)間Dsen矩陣對(duì)應(yīng)數(shù)值，含有監(jiān)督信息的Dsen通過(guò)公式（13）得到相似矩陣S。S在含有密度敏感空間信息的同時(shí)包含成對(duì)先驗(yàn)限制信息，相比于僅采用歐氏距離的傳統(tǒng)譜聚類(lèi)算法，限制與測(cè)度融合策略能夠保留更多數(shù)據(jù)特征。由此可見(jiàn)，距離測(cè)度的選取在譜聚類(lèi)算法影響深遠(yuǎn)，尤其面對(duì)高維數(shù)據(jù)時(shí)距離的選擇尤為關(guān)鍵。

以上基于密度的優(yōu)化策略提升效果顯著，但存在調(diào)節(jié)參數(shù)較多等問(wèn)題，針對(duì)該問(wèn)題，劉友超[45]與葛君偉[46]等人通過(guò)無(wú)參數(shù)的密度自適應(yīng)鄰域構(gòu)建法構(gòu)建無(wú)向圖。劉友超等人將相似圖與先驗(yàn)信息相結(jié)合，在遵循半監(jiān)督聚類(lèi)方式下，重新定義既含有成對(duì)約束與相似圖信息的W。葛君偉等人則以共享最近鄰來(lái)衡量樣本間的相似性度，避免參數(shù)帶來(lái)的誤差?；谝陨涎芯炕A(chǔ)，趙萌萌等人[47]針對(duì)大規(guī)模數(shù)據(jù)應(yīng)用場(chǎng)景，提出增量式共享緊鄰密度的譜聚類(lèi)算法。該方法將樣本隨機(jī)分為t個(gè)子集，在每次增量聚類(lèi)時(shí)采用KNN 確定新增子集數(shù)據(jù)點(diǎn)的類(lèi)別。本章舉例基于距離測(cè)度改進(jìn)的譜聚類(lèi)算法，針對(duì)不同問(wèn)題的不同優(yōu)化策略，算法具體對(duì)比分析如表2所示。

表2 測(cè)度優(yōu)化策略對(duì)比

2.2 二階段聚類(lèi)算法優(yōu)化方法

譜聚類(lèi)在低維解空間通常采用K-means 等聚類(lèi)算法進(jìn)行二階段聚類(lèi)，但K-means算法在選取聚類(lèi)中心點(diǎn)時(shí)具有隨機(jī)性，存在產(chǎn)生空簇的概率，因此影響譜聚類(lèi)算法整體準(zhǔn)確率與穩(wěn)定性[48-49]。

為避免引入隨機(jī)性、提高譜聚類(lèi)算法的整體穩(wěn)定性，針對(duì)二階段聚類(lèi)選取K-means的譜聚類(lèi)算法，優(yōu)化初始聚類(lèi)中心選取策略為常見(jiàn)優(yōu)化方法。Sapkota[50]、謝娟英[51]及周偉[52]等人通過(guò)優(yōu)化初始聚類(lèi)中心以提升算法穩(wěn)定性。Sapkota 等人采用新最遠(yuǎn)啟發(fā)式思想（New Farthest Point Heuristic，NFPH）改進(jìn)的K-means 來(lái)代替?zhèn)鹘y(tǒng)K-means 算法。NFPH 通過(guò)哈希表儲(chǔ)存樣本點(diǎn)對(duì)應(yīng)頻率，選取頻率最高的樣本點(diǎn)代替K-means隨機(jī)選取的初始聚類(lèi)中心略，以加強(qiáng)算法穩(wěn)定性。算法選取流程如圖4 所示，當(dāng)前簇類(lèi)數(shù)目小于設(shè)定K值時(shí)，通過(guò)NFPH 策略選取下一個(gè)聚類(lèi)中心?；谠撍枷氲淖V聚類(lèi)算法與實(shí)驗(yàn)對(duì)照組相比，錯(cuò)誤率低但時(shí)間消耗較高。

圖4 NFPH中心選取流程圖

謝娟英等人選取方差優(yōu)化初始聚類(lèi)中心的SD_K-medoids[53]代替?zhèn)鹘y(tǒng)K-means 算法，提高譜聚類(lèi)算法整體穩(wěn)定性，并將相似矩陣參數(shù)σ替換為完全自適應(yīng)的局部尺度參數(shù)，使相似矩陣更好表達(dá)樣本真實(shí)分布情況。K-means的優(yōu)化算法中，趙鑫等人[54]將Canopy算法引入K-means，達(dá)到降低算法迭代次數(shù)的同時(shí)提升算法穩(wěn)定性的效果。周偉等人將Canopy優(yōu)化后的K-means算法引入譜聚類(lèi)以克服初始中心點(diǎn)不穩(wěn)定的缺點(diǎn)，但基于譜聚類(lèi)算法的Canopy優(yōu)化策略使聚類(lèi)時(shí)耗高問(wèn)題更為突出，處理大規(guī)模數(shù)據(jù)集困難。

針對(duì)二階段譜聚類(lèi)中K值確定問(wèn)題，孔萬(wàn)增[16]與胡卓婭[55]等人從特征值本征間隙出發(fā)，自適應(yīng)缺點(diǎn)聚類(lèi)K值?？兹f(wàn)增等人利用本征間隙特性，自動(dòng)確定K值，避免手動(dòng)調(diào)參，采用基于矩陣賦零法代替K-means進(jìn)行二階段聚類(lèi)，基于余弦值的矩陣賦零法直接基于矩陣操作，相比于K-means算法時(shí)耗更短。該優(yōu)化策略在實(shí)現(xiàn)K值自動(dòng)確定的同時(shí)，避免引入其他聚類(lèi)算法的不確定性等因素。而胡卓婭等人在利用本征間隙確定K值的同時(shí)，在二階段聚類(lèi)采用優(yōu)化蜂群算法代替K-means算法，借助蜂群算法特性增強(qiáng)譜聚類(lèi)算法全局搜索能力。

上述算法在二階段聚類(lèi)分別選取改進(jìn)的K-means算法或選取其他聚類(lèi)算法，以提升算法的穩(wěn)定性。然而每種聚類(lèi)算法均有相應(yīng)的優(yōu)缺點(diǎn)，K-means算法線(xiàn)性時(shí)間復(fù)雜度是最顯著的優(yōu)點(diǎn)，而基于初始中線(xiàn)點(diǎn)優(yōu)化策略的K-means算法通常付出更多時(shí)間消耗，增加譜聚類(lèi)算法適應(yīng)大規(guī)模數(shù)據(jù)負(fù)擔(dān)。因此，選擇第二階段聚類(lèi)算法時(shí)，時(shí)間復(fù)雜度是值得考慮的因素之一。具體二階段聚類(lèi)算法對(duì)比分析如表3所示。

表3 二階段聚類(lèi)算法對(duì)比

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

傳統(tǒng)譜聚類(lèi)算法基于數(shù)據(jù)樣本計(jì)算W矩陣并進(jìn)行規(guī)范化，因此算法時(shí)間復(fù)雜度為O(n3)。面向大規(guī)模數(shù)據(jù)應(yīng)用場(chǎng)景，譜聚類(lèi)算法通常因時(shí)空復(fù)雜度過(guò)高，無(wú)法完成計(jì)算而被迫中斷。為提高譜聚類(lèi)算法在海量數(shù)據(jù)場(chǎng)景下的可用性，研究者借助Spark 等平臺(tái)優(yōu)勢(shì)對(duì)譜聚類(lèi)算法并行加速，或通過(guò)優(yōu)化W矩陣計(jì)算策略減少計(jì)算時(shí)耗，或針對(duì)現(xiàn)有劃分模型進(jìn)行優(yōu)化，降低算法時(shí)間復(fù)雜度，減少算法處理海量數(shù)據(jù)時(shí)間開(kāi)銷(xiāo)。

2.3.1 并行與優(yōu)化改進(jìn)方法

通信技術(shù)的發(fā)展使信息生產(chǎn)、傳播更加快速，因此，數(shù)據(jù)體積日漸龐大、種類(lèi)繁多。面向海量數(shù)據(jù)的處理訴求，迫使聚類(lèi)算法提高可伸縮性。Spark 并行框架因內(nèi)存計(jì)算的特性受到廣泛關(guān)注，且對(duì)聚類(lèi)算法加速效果顯著，因此研究者將譜聚類(lèi)算法與Spark 有機(jī)結(jié)合。基于Spark 的譜聚類(lèi)算法通過(guò)減少數(shù)據(jù)計(jì)算及數(shù)據(jù)傳輸開(kāi)銷(xiāo)，從而降低算法時(shí)耗，增強(qiáng)譜聚類(lèi)算法處理大數(shù)據(jù)的可用性。

針對(duì)基于Spark 的并行策略設(shè)計(jì)，朱光輝[56]與崔藝馨[57]等人提出算法并行策略。朱光輝等人提出的并行譜聚類(lèi)算法（Spectral Clustering Algorithm Based on Spark，SCoS）中包含四個(gè)主要步驟并行化，分別為：

（1）相似矩陣構(gòu)建與稀疏化過(guò)程并行化；

（2）拉普拉斯矩陣構(gòu)建與正規(guī)化過(guò)程并行化；

（3）正規(guī)化拉普拉斯矩陣特征向量計(jì)算并行化；

（4）K-means聚類(lèi)并行化。

基于多輪迭代并行方法構(gòu)建相似矩陣，在減輕主節(jié)點(diǎn)壓力的同時(shí)避免重復(fù)計(jì)算相似度。t近鄰方式對(duì)相似矩陣進(jìn)行稀疏化，達(dá)到節(jié)省存儲(chǔ)空間與減少L矩陣計(jì)算量目的。由公式（6）可知，L正規(guī)化通過(guò)三矩陣鏈乘實(shí)現(xiàn)，時(shí)間復(fù)雜度高。為降低求解Lnor時(shí)間復(fù)雜度，通過(guò)對(duì)角陣D的性質(zhì)對(duì)L進(jìn)行相應(yīng)行列變換，即可得到Lnor。針對(duì)特征向量的求解，SCoS算法基于Scala PACK實(shí)現(xiàn)特征向量并行化求解。崔藝馨等人基于上述研究基礎(chǔ)，采用二叉樹(shù)索引網(wǎng)格劃分對(duì)并行數(shù)據(jù)劃分，通過(guò)邊界值劃分?jǐn)U展提升數(shù)據(jù)分塊合理性。

基于Spark的譜聚類(lèi)算法一般依賴(lài)高級(jí)語(yǔ)言得以實(shí)現(xiàn)，而Julia語(yǔ)言雖然同為高級(jí)語(yǔ)言，但性能媲美靜態(tài)編譯語(yǔ)言且專(zhuān)為并行與分布式計(jì)算設(shè)計(jì)。Huo 等人[58]采用Julia 語(yǔ)言實(shí)現(xiàn)多處理器并行的譜聚類(lèi)算法?；贘ulia 的譜聚類(lèi)采用k近鄰策略計(jì)算W矩陣，并將k個(gè)特征值求解看作圖分割問(wèn)題。得益于Julia的易用性與靈活性，算法通過(guò)調(diào)用ARPACK計(jì)算特征向量，且在二階段聚類(lèi)采用K-means++提升算法穩(wěn)定性，最終文章通過(guò)實(shí)驗(yàn)證明該并行策略的有效性與準(zhǔn)確性。

基于分布式平臺(tái)、語(yǔ)言的并行加速策略雖對(duì)譜聚類(lèi)計(jì)算耗時(shí)問(wèn)題有所緩解，但存在為減少時(shí)間消耗導(dǎo)致數(shù)據(jù)信息丟失影響算法準(zhǔn)確率問(wèn)題。因此，Wu 等人[59]提出如圖5所示的隨機(jī)裝箱（Random Bining Features，RB）算法，采用RB算法得到矩陣Z代替相似矩陣W，并對(duì)后續(xù)特征分解加速。該方法應(yīng)用BR特征矩陣內(nèi)積近似表示W(wǎng)，避免相似矩陣計(jì)算。采用預(yù)處理迭代多方法特征求解器，降低L矩陣特征分解時(shí)耗，最終得到線(xiàn)性時(shí)間復(fù)雜度的譜聚類(lèi)算法，且優(yōu)化后的譜聚類(lèi)算法時(shí)間開(kāi)銷(xiāo)更少，對(duì)大規(guī)模數(shù)據(jù)適應(yīng)良好。

圖5 RB算法流程圖

上述算法因優(yōu)化出發(fā)角度不同而略有差異，在矩陣計(jì)算階段，Spark 環(huán)境下的譜聚類(lèi)算法通過(guò)多輪迭代的方式避免重復(fù)計(jì)算數(shù)據(jù)間相似度，而基于RB 優(yōu)化的譜聚類(lèi)算法通過(guò)計(jì)算落在同一網(wǎng)格內(nèi)數(shù)據(jù)點(diǎn)的相似度來(lái)減少計(jì)算開(kāi)銷(xiāo)；在拉普拉斯矩陣求解階段，前者利用稀疏相似矩陣的特性，進(jìn)行相應(yīng)行的操作得到Lnor，后者采用近似相似矩陣Z與度矩陣公式轉(zhuǎn)換得到L矩陣。以上優(yōu)化策略算法加速工作較為完善，但未像基于Julia的譜聚類(lèi)算法一樣，考慮第二階段聚類(lèi)算法對(duì)算法整體聚類(lèi)性能、準(zhǔn)確率等方面影響。

2.3.2 譜圖劃分改進(jìn)方法

譜聚類(lèi)算法受譜圖劃分思想啟發(fā)，通過(guò)構(gòu)造數(shù)據(jù)有權(quán)無(wú)向圖并逼近最優(yōu)圖劃分，進(jìn)而求解聚類(lèi)問(wèn)題，而圖劃分結(jié)果與切割準(zhǔn)則密切相關(guān)。隨著樣本類(lèi)別、數(shù)目、維度及數(shù)量等特性的改變，對(duì)劃分準(zhǔn)則進(jìn)行相應(yīng)改進(jìn)以提升譜聚類(lèi)算法聚類(lèi)精度及可伸縮性。

Chen等人[60]直接優(yōu)化規(guī)范切割準(zhǔn)則，得到直接規(guī)范切割模型（Direct Normalized Cut，DNC）。通過(guò)DNC來(lái)對(duì)規(guī)范切割模型進(jìn)行直接運(yùn)算，將算法時(shí)間復(fù)雜度降至O(n2c)。針對(duì)大規(guī)模數(shù)據(jù)處理，以DNC 為基礎(chǔ)提出快速規(guī)范切割法（Fast Normalized Cut，F(xiàn)NC），F(xiàn)NC 使用均衡K平均值算法，將數(shù)據(jù)分為均衡子集并采用子集中心為Anchor（錨點(diǎn)），計(jì)算錨點(diǎn)與整個(gè)數(shù)據(jù)的相似矩陣，最終通過(guò)DNC得到聚類(lèi)結(jié)果矩陣Y。

相較于其他改進(jìn)策略，DNC 對(duì)目標(biāo)函數(shù)進(jìn)行改進(jìn)使目標(biāo)函數(shù)收斂，并對(duì)問(wèn)題進(jìn)行求解，將譜聚類(lèi)算法時(shí)間復(fù)雜度降為二次。FNC算法通過(guò)均衡K-means算法通過(guò)錨點(diǎn)采樣以減少相矩陣計(jì)算，并達(dá)到線(xiàn)性時(shí)間復(fù)雜度，且在人造數(shù)據(jù)集與真實(shí)數(shù)據(jù)集上均表現(xiàn)出色。

2.3.3 其他快速優(yōu)化方法

基于錨點(diǎn)圖的模型被提出以應(yīng)對(duì)規(guī)?？焖僭鲩L(zhǎng)的數(shù)據(jù)，當(dāng)譜聚類(lèi)算法采用錨點(diǎn)模型聚類(lèi)時(shí)，使用過(guò)于稀疏的錨點(diǎn)會(huì)降低算法性能，而錨點(diǎn)密度足夠大時(shí)，算法時(shí)間成本顯著增加且處理困難。針對(duì)該問(wèn)題，YANG等人[61]通過(guò)構(gòu)建金字塔多層錨點(diǎn)，如圖6所示，并利用原始數(shù)據(jù)層H0 與最后錨點(diǎn)層Hm構(gòu)造層次二分圖，旨在減少相似矩陣計(jì)算量與時(shí)耗。圖6（a）為金字塔模型示意圖，其中H0 為原始數(shù)據(jù)層，H2、H3 為錨點(diǎn)層。圖6（b）展示了H0 層與錨點(diǎn)層的分布與選取情況。

圖6 三層金字塔Anchor示意圖

在錨點(diǎn)圖模型當(dāng)中，選取錨點(diǎn)的質(zhì)量影響聚類(lèi)效果。因此，采用如下混合數(shù)據(jù)代表點(diǎn)選取方法[62]。

（1）隨機(jī)選取P個(gè)候選點(diǎn)（其中p

（2）在P上運(yùn)用K-means 算法選擇p個(gè)簇類(lèi)中心作為最終代表點(diǎn)，并記作R={r1,r2,…,rp}。

混合數(shù)據(jù)代表點(diǎn)選取方法在更好捕捉數(shù)據(jù)結(jié)構(gòu)特征的同時(shí)降低算法計(jì)算量與時(shí)耗。

Nystr?m通過(guò)對(duì)數(shù)據(jù)近似計(jì)算來(lái)逼近真實(shí)的特征空間，從而降低計(jì)算復(fù)雜度，因此譜聚類(lèi)算法可以通過(guò)Nystr?m 采樣法提升算法可用性。丁世飛[63]、劉靜姝[64]及邱云飛[65]等人從采樣角度出發(fā)，尋求譜聚類(lèi)與海量數(shù)據(jù)采樣契合點(diǎn)。丁世飛等人采用自適應(yīng)采樣方法多次遍歷采樣，每次采樣后更新剩余點(diǎn)采樣概率以提升采樣質(zhì)量。最終在犧牲較少精度條件下，達(dá)到大幅降低計(jì)算復(fù)雜度、提升算法穩(wěn)定性的目的。劉靜姝等人在Nystr?m基礎(chǔ)上運(yùn)用乘法更新原理，實(shí)現(xiàn)分類(lèi)指示矩陣更新，避免高時(shí)耗譜分解步驟。相比于傳統(tǒng)譜聚類(lèi)算法，該策略在處理高維數(shù)據(jù)時(shí)更快速。邱云飛等人則針對(duì)Nystr?m方法選取樣本代表性弱問(wèn)題，將加權(quán)思想引入，基于加權(quán)數(shù)據(jù)K-means聚類(lèi)中心點(diǎn)采樣，且在Nystr?m階段采取并行處理方式提升集成多樣性與高效性，最終大幅降低算法復(fù)雜度。

在提升算法運(yùn)行效率方面，基于分布平臺(tái)并行加速策略通常對(duì)平臺(tái)依賴(lài)性較高，且并行聚類(lèi)結(jié)果合并方式直接對(duì)算法結(jié)果精度產(chǎn)生影響。而為降低算法計(jì)算復(fù)雜度與時(shí)耗，采樣方式難免引入隨機(jī)性的干擾，導(dǎo)致算法聚類(lèi)精度有所下降。算法執(zhí)行效率優(yōu)化策略具體對(duì)比分析如表4所示。

表4 執(zhí)行效率策略對(duì)比

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

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

表5 優(yōu)化譜聚類(lèi)算法對(duì)比

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

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

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

譜聚類(lèi)算法所采用數(shù)據(jù)集一般分為兩類(lèi)，一類(lèi)是以UCI 數(shù)據(jù)集為代表的小樣本數(shù)據(jù)集（https：//archive.ics.uci.edu/ml/index.php）；另一類(lèi)是以圖像數(shù)據(jù)集為代表的大樣本數(shù)據(jù)集。表6、表7 對(duì)常用的兩類(lèi)數(shù)據(jù)集的特點(diǎn)與特征進(jìn)行相關(guān)總結(jié)。

表7 常見(jiàn)譜聚類(lèi)算法圖片數(shù)據(jù)集

3.2 評(píng)價(jià)標(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)，對(duì)譜聚類(lèi)算法進(jìn)行評(píng)價(jià)，相關(guān)公式如下：

公式（14）中，N為樣本數(shù)量，分別為聚類(lèi)結(jié)果與數(shù)據(jù)標(biāo)簽，K為簇類(lèi)個(gè)數(shù)，δ(x,y)函數(shù)當(dāng)且僅當(dāng)x=y時(shí)值為1，否則為0[57]。

公式（17）中，MI(X,Y)為變量X、Y之間的互信息，H(X)為變量X的熵。

3.3 實(shí)驗(yàn)結(jié)果與分析

本節(jié)在Iris、Wine、Ionosphere、Glass 以及手寫(xiě)體數(shù)據(jù)集上，采用不同譜聚類(lèi)算法進(jìn)行實(shí)驗(yàn)對(duì)比，并進(jìn)行分析總結(jié)。列舉近幾年代表性的譜聚類(lèi)優(yōu)化算法的實(shí)驗(yàn)結(jié)果，并在數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比與數(shù)據(jù)分析。實(shí)驗(yàn)采用CPU 3.6 GHz、32 GB 內(nèi)存、Windows10 操作系統(tǒng)，編程環(huán)境PyCharm2020.2.2、python3.8。為客觀性地對(duì)比算法的聚類(lèi)指標(biāo)，實(shí)驗(yàn)將譜聚類(lèi)（SC）算法與隨機(jī)約束譜聚類(lèi)（RCSC）算法分別在各個(gè)數(shù)據(jù)集上執(zhí)行10次，并計(jì)算其聚類(lèi)的平均指標(biāo)。

該實(shí)驗(yàn)分為兩個(gè)部分：實(shí)驗(yàn)一為基于UCI小樣本數(shù)據(jù)集的SC算法、RCSC算法以及基于低密度分割密度敏感距離的譜聚類(lèi)算法（Low Density Separation Density Sensitive Distance-based Spectral Clustering algorithm，LDSDSD-SC）算法對(duì)比分析實(shí)驗(yàn)，以上三種算法在UCI數(shù)據(jù)集上的關(guān)參數(shù)及蘭德指數(shù)如表8所示；實(shí)驗(yàn)二為基于手寫(xiě)體數(shù)據(jù)集的大樣本分析對(duì)比實(shí)驗(yàn)，其中SC算法、CSoC 算法、FNC 算法以及基于層次二分圖譜聚類(lèi)算法（Spectral Clustering Based on Hierarchical Bipartite Graph，SCHBG）算法在手寫(xiě)體數(shù)據(jù)集上的準(zhǔn)確率與標(biāo)準(zhǔn)互信息如表9所示。

表8 基于UCI譜聚類(lèi)算法對(duì)比

表9 基于手寫(xiě)數(shù)據(jù)集上譜聚類(lèi)算法對(duì)比

實(shí)驗(yàn)一中，由表8中蘭德指數(shù)在不同數(shù)據(jù)集上整體對(duì)比可知，譜聚類(lèi)算法在樣本數(shù)量小且數(shù)據(jù)較為平衡的數(shù)據(jù)集上，如Iris、Wine聚類(lèi)性能良好，而在樣本數(shù)據(jù)不平衡數(shù)據(jù)集上，如Ionosphere、Glass 聚類(lèi)性能稍遜。在Iris與Glass數(shù)據(jù)集上，基于密度距離改進(jìn)的LDSDSD-SC[43]算法聚類(lèi)性能最優(yōu)，證明基于密度距離改進(jìn)策略的優(yōu)越性。而Wine 因數(shù)據(jù)特征間數(shù)值差過(guò)大，導(dǎo)致直接聚類(lèi)效果差，因此，在CS與RCSC算法中對(duì)數(shù)據(jù)集進(jìn)行歸一化處理，故SC與RCSC算法聚類(lèi)性能明顯優(yōu)于LDSDSDSC[43]算法，這也體現(xiàn)了數(shù)據(jù)預(yù)處理步驟的重要性。觀察Ionosphere數(shù)據(jù)，相比于SC算法基于半監(jiān)督優(yōu)化的RCSC算法聚類(lèi)性能會(huì)更優(yōu)，但RCSC優(yōu)化策略具有隨機(jī)性聚類(lèi)結(jié)果不穩(wěn)定。

實(shí)驗(yàn)二中可由Acc與NMI數(shù)值觀察得知，在MNIST數(shù)據(jù)集及USPS 數(shù)據(jù)集上，基于錨點(diǎn)的層次二分圖改進(jìn)策略聚類(lèi)性能顯然更優(yōu)，而SC算法聚類(lèi)MNIST這樣大規(guī)模數(shù)據(jù)集存儲(chǔ)需求大，在實(shí)驗(yàn)過(guò)程中內(nèi)存溢出導(dǎo)致聚類(lèi)中斷，因此從對(duì)大數(shù)據(jù)處理方面證明SCHBG 算法優(yōu)化策略的優(yōu)異性。觀察CSoS算法NMI值可知，僅采用Spark 平臺(tái)加速對(duì)譜聚類(lèi)算法的提升有限，與其他優(yōu)化策略如稀疏化等，可對(duì)譜聚類(lèi)算法性能明顯提升。

4 結(jié)束語(yǔ)

近年來(lái)，譜聚類(lèi)因其獨(dú)特的優(yōu)點(diǎn)與特性引起學(xué)術(shù)界大量關(guān)注，經(jīng)過(guò)研究者們不斷改進(jìn)譜聚類(lèi)算法性能逐級(jí)提高，但以下方向需要進(jìn)一步研究。

（1）利用數(shù)據(jù)局部與全局先驗(yàn)信息構(gòu)建相似矩陣

W矩陣是譜聚類(lèi)算法誤差來(lái)源的第一環(huán)，現(xiàn)有構(gòu)建W矩陣的方法眾多，如本文所介紹的基于限制的譜聚類(lèi)算法，該種方法雖然利用少量標(biāo)簽實(shí)現(xiàn)對(duì)W的優(yōu)化，但并未使用其他方面的先驗(yàn)信息，例如，密度先驗(yàn)信息，且該方法時(shí)間復(fù)雜度較高。因此，在現(xiàn)有算法改進(jìn)基礎(chǔ)上深入研究，結(jié)合多方面特征來(lái)構(gòu)造相似矩陣W，進(jìn)一步提高譜聚類(lèi)算法的精確性并降低時(shí)耗，也是未來(lái)提高聚類(lèi)算法的一個(gè)重要的研究方向。

（2）利用矩陣?yán)碚撆c數(shù)據(jù)特征自動(dòng)確定參數(shù)

對(duì)于聚類(lèi)算法而言，算法結(jié)果對(duì)參數(shù)的選擇十分敏感。譜聚類(lèi)算法參數(shù)一般為核函數(shù)參數(shù)與類(lèi)數(shù)K，不同的參數(shù)生成不同的W，因此參數(shù)選取對(duì)聚類(lèi)結(jié)果影響明顯。針對(duì)類(lèi)數(shù)K的確定，本文所介紹自動(dòng)確定K值的譜聚類(lèi)算法，通過(guò)利用本征間隙特征來(lái)確定K。該方法實(shí)現(xiàn)K值自動(dòng)確定，但涉及較多計(jì)算與排序?？山梃b目前其他聚類(lèi)算法自動(dòng)確定參數(shù)策略，并進(jìn)行相應(yīng)改進(jìn)后應(yīng)用在譜聚類(lèi)算法上，達(dá)到自動(dòng)確定參數(shù)目的。針對(duì)大樣本數(shù)據(jù)，高效快速自動(dòng)確定K值也是譜聚類(lèi)算法一個(gè)值得研究的方向。

（3）海量數(shù)據(jù)抽樣預(yù)處理提升算法性能

針對(duì)基于大量數(shù)據(jù)的樣本數(shù)據(jù)不均勻問(wèn)題、傳統(tǒng)譜聚類(lèi)算法時(shí)空復(fù)雜度高，無(wú)法適用于較大數(shù)據(jù)樣本等問(wèn)題。聚類(lèi)算法需要進(jìn)一步解決，雖然基于Spark 平臺(tái)及二分圖等方式可對(duì)算法進(jìn)行加速，降低算法時(shí)耗，但針對(duì)算法自身優(yōu)化來(lái)降低時(shí)間復(fù)雜度仍舊是該領(lǐng)域的未來(lái)研究熱點(diǎn)之一。

（4）啟發(fā)式算法向譜聚類(lèi)算法遷移應(yīng)用

現(xiàn)階段，以蜂群算法等為代表的啟發(fā)式算法與譜聚類(lèi)算法結(jié)合已有研究，且已通過(guò)相關(guān)實(shí)驗(yàn)證明其有效性。因此，將譜聚類(lèi)算法與啟發(fā)式算法進(jìn)行有機(jī)結(jié)合，借鑒其優(yōu)化算法思想，并根據(jù)譜聚類(lèi)算法的特性進(jìn)行調(diào)整，形成吸納新型算法的優(yōu)點(diǎn)的優(yōu)化譜聚類(lèi)算法，不但提升譜聚類(lèi)算法聚類(lèi)效果，而且形成新優(yōu)化方法，這也將成為未來(lái)譜聚類(lèi)算法研究方向之一。