無需特征分解的快速譜聚類算法

劉靜姝，王 莉*，劉驚雷

（1.太原理工大學(xué)大數(shù)據(jù)學(xué)院，山西晉中 030600；2.煙臺大學(xué)計算機與控制工程學(xué)院，山東煙臺 264005）

（?通信作者電子郵箱wangli@tyut.edu.cn）

0 引言

隨著信息技術(shù)的發(fā)展，人們在日常生活中從互聯(lián)網(wǎng)上獲取的信息以海量規(guī)模存在，并且持續(xù)高速增長［1］。聚類分析利用數(shù)據(jù)劃分來找到數(shù)據(jù)間的內(nèi)在聯(lián)系，能夠更快速、更高效、更低成本地收集存儲數(shù)據(jù)［2］，已經(jīng)被應(yīng)用到機器學(xué)習(xí)的各個領(lǐng)域中，例如圖像分割［3-4］、特征選擇［5-6］和降維［7-8］。在過去的幾年，研究領(lǐng)域中涌現(xiàn)出許多應(yīng)用成功的聚類方法，包括層次聚類方法［9］、中心聚類［10］。其中，使用普遍的聚類算法包括k-means 算法［11］、模糊C 均值（Fuzzy C-Means，F(xiàn)CM）算法［12］和最大期望（Expectation Maximization，EM）算法［13］等。諸如此類經(jīng)典算法，雖然步驟簡單且執(zhí)行效率高，但當(dāng)聚類樣本集的空間為非凸結(jié)構(gòu)時，算法會易陷入局部最優(yōu)劃分中，因此它們?nèi)狈μ幚韽?fù)雜簇結(jié)構(gòu)的能力。

譜聚類算法的思想基于譜圖理論，將數(shù)據(jù)聚類問題轉(zhuǎn)化成圖劃分問題，通過表示出數(shù)據(jù)的低維非線性形式來實現(xiàn)降維，并且在降維的同時也將這些對象嵌入到歐氏空間，從而在新的空間中進行聚類［14］，這種假設(shè)對數(shù)據(jù)的結(jié)構(gòu)分布要求不強，使得它能夠處理數(shù)據(jù)集非凸時的聚類任務(wù)［15］，克服了k-means 算法等傳統(tǒng)聚類方法基于中心聚類而產(chǎn)生的缺點。除此之外，因為對誤差數(shù)據(jù)和噪聲數(shù)據(jù)不敏感，譜聚類方法具有較好的魯棒性［16］。

盡管譜聚類在很多領(lǐng)域都取得了不錯的發(fā)展和應(yīng)用成果，但仍處于發(fā)展階段，還有很多缺陷需要深入研究并進一步改進。首先，譜聚類需要計算圖拉普拉斯矩陣的特征向量，所需要的時間復(fù)雜度為O（n3），導(dǎo)致當(dāng)面向大規(guī)模數(shù)據(jù)集時，譜聚類會出現(xiàn)明顯的速度缺陷。其次，傳統(tǒng)的譜聚類算法存儲相似度矩陣需要O（n2）大小的內(nèi)存空間，如此高的復(fù)雜度在處理大規(guī)模數(shù)據(jù)時是無法被接受的，導(dǎo)致它只適用于規(guī)模較小的數(shù)據(jù)集。

為提升譜聚類算法的擴展性，研究者設(shè)計出許多可以降低特征分解復(fù)雜度的算法來克服計算負(fù)擔(dān)。Fowlkes 等［17］通過改進Nystr?m方法實現(xiàn)了譜聚類的快速近似特征分解，丁世飛等［18］利用自適應(yīng)采樣技術(shù)擴展了Nystr?m方法，擴展了譜聚類在大規(guī)模數(shù)據(jù)集中的聚類效果。此外，Cai等［19］提出基于地標(biāo)點的譜聚類（Landmark-based Spectral Clustering，LSC）算法，通過選擇地標(biāo)點并計算數(shù)據(jù)點與地標(biāo)點之間的相似度矩陣的乘積得出近似矩陣，雖然利用這種矩陣近似性質(zhì)可以實現(xiàn)快速特征分解，但該方法的抽樣隨機性會導(dǎo)致處理大數(shù)據(jù)集時出現(xiàn)樣本點過于集中的問題。

本文利用Nystr?m 采樣思想，設(shè)計了一種無需特征值分解的快速譜聚類迭代優(yōu)化（Fast Spectral Clustering using Iterative optimization，IFSC）算法。該算法克服了傳統(tǒng)譜聚類方法處理大規(guī)模數(shù)據(jù)集時的缺陷，通過Nystr?m思想采樣一小部分樣本，利用小樣本矩陣來構(gòu)造整個原始相似矩陣，通過乘法更新迭代優(yōu)化規(guī)則來實現(xiàn)聚類。

本文的主要工作如下：

1）基于譜聚類問題的拉格朗日函數(shù)，對聚類指示矩陣Y進行求導(dǎo)，得到關(guān)于矩陣Y迭代更新的乘法規(guī)則，從而避免傳統(tǒng)譜聚類的特征值分解。

2）設(shè)計了一種不需要特征值分解的譜聚類算法IFSC，該算法根據(jù)關(guān)于矩陣Y的乘法迭代規(guī)則進行更新。具體來說，基于采樣的數(shù)據(jù)點間的相似矩陣E∈Rm×m、采樣點和剩余點之間的相似矩陣F∈Rm×(n-m)，以及構(gòu)造的采樣小矩陣和原始大矩陣之間的關(guān)系對小矩陣進行迭代更新，從而實現(xiàn)對大矩陣的更新，實現(xiàn)了快速譜聚類。

3）在理論上，根據(jù)聚類指示矩陣Y構(gòu)造輔助函數(shù)證明了算法的收斂性，使用KKT（Karush-Kuhn-Tucker）條件證明了本文所設(shè)計乘法更新規(guī)則的正確性。

4）在五個真實數(shù)據(jù)集上進行了實驗驗證，實驗結(jié)果表明，本文設(shè)計的快速譜聚類算法與傳統(tǒng)譜聚類算法和其他聚類算法相比，處理大規(guī)模數(shù)據(jù)集時，計算時間有所降低；且在處理含有較多噪聲的真實數(shù)據(jù)集時表現(xiàn)優(yōu)于其他聚類方法（如層次聚類）。

1 相關(guān)工作

1.1 譜聚類

譜聚類方法利用圖論思想，將數(shù)據(jù)聚類問題轉(zhuǎn)化成圖劃分問題，通過對圖拉普拉斯矩陣進行特征值分解，得到原始數(shù)據(jù)在轉(zhuǎn)換后的低維空間中的向量表示。最后，對這些低維特征向量運行k-means算法，從而得到最終聚類結(jié)果。

其中，譜聚類的時間復(fù)雜度缺陷主要體現(xiàn)在三個方面：相似度矩陣的構(gòu)建O（n2d）、拉普拉斯矩陣的特征值分解O（n3）和最終的k-means聚類步驟O（nkt）（t為迭代次數(shù)）。它的空間復(fù)雜度缺陷主要體現(xiàn)在存儲相似度矩陣與拉普拉斯矩陣需要的O（n2）上。隨著數(shù)據(jù)大小n的增加，譜聚類的計算復(fù)雜度過高，這使得譜聚類方法在處理大規(guī)模數(shù)據(jù)集時，無法發(fā)揮更好的性能。

針對以上幾點限制譜聚類應(yīng)用的主要缺陷，可將現(xiàn)有的譜聚類方法主要劃分為兩種類型：

一種類型是通過約簡相似度矩陣的大小來降低樣本數(shù)量并減小數(shù)據(jù)集規(guī)模，例如Martin 等［20］利用這種思路設(shè)計了KASP（K-means Approximate SPectral clustering）算法，優(yōu)先對數(shù)據(jù)集使用k-means等方法進行初始化聚類，從而快速地將大部分點綁定到局部的中心點上去，再針對這些中心點進行譜聚類，此時中心點聚類結(jié)果即視作綁定于中心點上的普通點的聚類結(jié)果。此外，葉茂等［21］改進了基于地標(biāo)選擇的譜聚類（LSC）算法，使用基于近似奇異值分解（Singular Value Decomposition，SVD）抽樣方法實現(xiàn)快速的標(biāo)點采樣，克服了抽樣地標(biāo)點效果不穩(wěn)定的缺點。與文獻［14］研究思路不同的是，普通點和中心點的歸一化關(guān)系是由點與點之間的最短路徑來計算，由于保留了圖的特性，它更能反映出圖的連通狀態(tài)和點與點之間的相互關(guān)系。然而即使在利用這種空間換時間的思路實現(xiàn)改進后，數(shù)據(jù)稠密圖通過閾值限定轉(zhuǎn)化成稀疏圖后仍需要O（rnlogn）的時間復(fù)雜度，不理想的算法速度限制了它在較大數(shù)據(jù)集上的聚類應(yīng)用。

另一種類型是通過選擇代表對象來降低樣本數(shù)據(jù)集的規(guī)模。這種方法通過在數(shù)據(jù)集中選擇有代表性的對象，利用代表對象構(gòu)成一個小規(guī)模數(shù)據(jù)集，從而降低可用數(shù)據(jù)集的規(guī)模。然后，利用已有的譜聚類方法劃分這些代表對象構(gòu)成的小規(guī)模數(shù)據(jù)集。最后，根據(jù)代表對象所屬的類來分配原始數(shù)據(jù)集中數(shù)據(jù)所屬的類。Chen 等［22］提出了基于子矩陣構(gòu)造的研究方法，通過利用Nystr?m 方法從原始數(shù)據(jù)集中隨機選擇p個代表，并建立大小為N×p的相似度子矩陣。張濤等［23］改進了子空間聚類算法對高斯噪聲敏感的缺陷，使用優(yōu)化的核范數(shù)對系數(shù)矩陣的奇異值進行正則化，能夠在提高算法準(zhǔn)確率的同時，保持其高斯噪聲下的穩(wěn)定性。

由此可見，特征提取是譜聚類方法完成相似度矩陣優(yōu)化的主要著手點。利用數(shù)據(jù)點距離的參照采樣雖然操作直觀簡便，但閾值的人為選擇和特征空間的映射會導(dǎo)致代表樣本和實際樣本的差異。此外，使用綁定代表點的方式將圖稀疏化會損害數(shù)據(jù)點集的密度，降低了聚類準(zhǔn)確率。如果此時根據(jù)數(shù)據(jù)集的大小增加代表點的密度，依然會產(chǎn)生數(shù)據(jù)量越大、代表點越多，從而導(dǎo)致算法準(zhǔn)確率降低的問題。

本文使用了Nystr?m 方法進行隨機采樣間接求解相似度矩陣，使得所有的行和列都能通過映射參與到計算中，最大限度保持聚類結(jié)果的準(zhǔn)確度。該算法利用選取的子矩陣與原始矩陣的關(guān)系來代入乘法更新迭代規(guī)則完成更新，從而實現(xiàn)聚類，進一步降低傳統(tǒng)方法特征值分解步驟中所需的時間開銷。

1.2 譜聚類的基本算法

譜聚類利用譜圖理論思想將數(shù)據(jù)點視作無向圖，這里無向圖邊的權(quán)重代表數(shù)據(jù)點的成對相似性，聚類的目標(biāo)就是將這些數(shù)據(jù)點分配到不同的類簇中，使得簇內(nèi)的數(shù)據(jù)點之間有較大的相似度，而簇之間的數(shù)據(jù)點之間的相似度較小。因此，需要構(gòu)建一個相似度圖，即以數(shù)據(jù)點為頂點、以相似度為權(quán)重的一個帶權(quán)圖，從而使構(gòu)建的相似度圖能夠反映原始數(shù)據(jù)集中各個點之間的相似關(guān)系。其中，本文公式推導(dǎo)所用到的一些典型數(shù)學(xué)符號如表1所示。

構(gòu)建相似度矩陣W常常使用如下的高斯核函數(shù)來作定義：

其中，Wij表示數(shù)據(jù)向量樣本xi和xj之間的相似性，使用高斯核函數(shù)的時候，需要確定參數(shù)σ。那么在相似度圖中，數(shù)據(jù)點聚類問題就轉(zhuǎn)變成圖劃分問題。劃分準(zhǔn)則是使劃分之后的子圖內(nèi)部的點間相似度盡可能大，不同子圖之間的相似度盡可能小。下面介紹利用規(guī)范割（Normalized Cut，NCut）劃分：將頂點集V劃分為兩部分A和B，即：A∪B=V，A∩B=?，構(gòu)建出相似度矩陣后，將A和B之間的權(quán)重之和記作：cut(A，B)=。此時將第i個節(jié)點的度定義為。

表1 符號描述Tab.1 Symbol description

譜聚類旨在找到使得規(guī)范割目標(biāo)函數(shù)最小的子集A和子集B［24］，用類的容量作歸一項，兼顧了類的內(nèi)部和外部的連接。利用以下公式可以計算出最優(yōu)的NCut值：

Malik等［25］給出歸一化的拉普拉斯矩陣的定義：

此時L是半正定矩陣，它的特征值區(qū)間為［0，2］，所以D-1/2WD-1/2的特征值也被限制在區(qū)間［1，1］中。擴展到k> 2的多分類問題中，公式可被重寫為：

此時有YTY=I，矩陣Y中包含歸一化拉普拉斯矩陣L的前k個特征向量。因此，優(yōu)化公式即可通過標(biāo)準(zhǔn)跡線最小化問題解決，使用文獻［25］中提出的歸一化譜聚類求解得出指示矩陣Y。在得到矩陣Y作為聚類中心后，利用k-means 算法對指示矩陣Y的行進行聚類，這種算法稱為歸一化的譜聚類算法。

為了方便在實驗中與本文設(shè)計的算法進行對比，在算法1中簡單描述了譜聚類算法的過程。

2 快速譜聚類框架

2.1 問題描述

譜聚類算法可以視作函數(shù)最小化：

其中：λ是拉格朗日常數(shù)；是正交約束項。而式（5）的目標(biāo)函數(shù)是非光滑的，因此不容易由求解拉普拉斯矩陣L的特征值分解來獲得有效的分辨率。非負(fù)矩陣分解（Nonnegative Matrix Factorization，NMF）算法能夠通過松弛技術(shù)處理聚類問題，借鑒這種思想，可以放寬離散條件，并提出乘法更新優(yōu)化的思路來解決特征值分解問題。將非負(fù)約束的指標(biāo)矩陣記作Y，其中Yij> 0。此外，一些傳統(tǒng)的譜聚類相關(guān)方法將指標(biāo)矩陣Y放松為正交約束，即YTY=I。文獻［26］指出，如果指示矩陣Y同時滿足正交和非負(fù)，則在矩陣Y的每一行中只有一個元素為正，其他元素為零。因此可以通過添加約束Y>0 和YTY=I來獲得文中定義的理想指示矩陣Y，進而利用這種簡單有效的方式解決特征值分解問題。考慮以上兩個約束的同時放寬離散條件，則式（5）可寫為：

其中Y>0。為了實現(xiàn)損失函數(shù)式（6）的最小化，有：

經(jīng)過上面推導(dǎo)能觀察出，式（6）可以視作兩部分，即Y+2λYYTY和2λY+D-1/2WD-1/2。因為Y>0，D>0 且W≥0，這兩部分都是非負(fù)的。為便于描述，將前一個因子表示為Q=Y+2λYYTY，后者表示為P=2λY+D-1/2WD-1/2。根據(jù)文獻［27］中提出的標(biāo)準(zhǔn)NMF 算法的乘法更新規(guī)則，可通過更新Y的方式來使得式（6）中的損失函數(shù)最小化，即：

其中，“°”和“?”分別表示Hadamard 乘法和Hadamard 除法（即逐元素乘法和除法），且有：

然后經(jīng)過一系列迭代后使損失函數(shù)收斂。由于在指示矩陣Y的每一行中僅有一個元素為正，其他元素接近零，因此在實現(xiàn)聚類時，可以視作完美的約束指示矩陣，而不像傳統(tǒng)的譜聚類中還需要對指示矩陣Y進行松弛和特征分解的處理。

2.2 算法設(shè)計和描述

2.2.1 設(shè)計模型

為了將譜聚類算法應(yīng)用于大規(guī)模數(shù)據(jù)集，需要進一步降低計算相似度矩陣的時間和存儲復(fù)雜度，因此本文在優(yōu)化模型中選用Nystr?m 方法來擴展近似有限樣本的原始相似度矩陣。

根據(jù)Nystr?m 采樣原理，將n個數(shù)據(jù)點視作兩部分：m個隨機采樣得到的樣本點和剩余的n-m數(shù)據(jù)點。則相似度矩陣W可以寫成：

其中：矩陣E∈Rm×m表示m個采樣數(shù)據(jù)點之間的相似度矩陣，它可以用特征分解形式UΛUT來表示，特征向量UUT=I。矩陣F∈Rm×(n-m)表示采樣點和剩余點之間的相似度矩陣，而矩陣C∈R(n-m)×(n-m)代表剩余點之間的相似度矩陣。令-U表示W(wǎng)的近似特征向量，由Nystr?m擴展可得到：

相應(yīng)的，W的近似矩陣為：

由此可見，Nystr?m 擴展技術(shù)使得矩陣C可以用C=FTE-1F來近似逼近，則W可寫為：

由于m?n，抽樣后的剩余點個數(shù)很多，而Nystr?m 技術(shù)利用近似逼近降低了計算剩余點間相似度這一步驟所需的時間和空間復(fù)雜度。定理1給出了關(guān)于矩陣正交特征向量表達式的證明。

定理1若給定一個矩陣E為正定矩陣，且定義矩陣Q=E+E-1/2FFTE-1/2，將其對角化Q=UQΛUTQ，則的正交特征向量為：

證明

1）首先證明V是W的特征向量：

2）然后證明V和VT是正交的。

將Nystr?m 擴展矩陣用于譜聚類，相似矩陣需要作歸一化處理，即，其中D是對角矩陣，它的對角線元素Dii等于矩陣的第i行元素和。

文獻［17］中給出了節(jié)點度的計算方法：

其中：用er=Elm來代表矩陣E的行和；Fln代表矩陣F的行和；fc表示矩陣F的列和；l表示元素均為1的列向量。則不需要求解C=FTE-1F，僅利用d就可以將矩陣E和F歸一化：

將式（17）中的E和F代入標(biāo)準(zhǔn)化的相似度矩陣中得到：

由于矩陣E-1中含有負(fù)數(shù)元素，故標(biāo)準(zhǔn)化結(jié)果也可能是負(fù)的。為了保證乘法迭代規(guī)則的約束性，需要滿足標(biāo)準(zhǔn)化結(jié)果非負(fù)，即，將矩陣E中的元素拆分為正負(fù)兩部分并分別記作：E+=(|E|+E)./2 和E-=(|E|-E)./2（其中./代表矩陣中的元素逐個相除），那么此時的E+和E-都是非負(fù)矩陣。

將E和F放在指示矩陣Y中，則更新規(guī)則中的P、Q可以寫作：

此時，矩陣P和Q都是非負(fù)的，即可按照式（9）來進行乘法更新迭代。

2.2.2 算法描述

第2.2.1 節(jié)中介紹了基于乘法更新迭代的快速譜聚類算法優(yōu)化模型。本文提出了基于乘法更新迭代思想的快速譜聚類算法，框架具體實現(xiàn)過程見算法2。

算法2 基于乘法更新迭代的快速譜聚類算法IFSC。

輸入 數(shù)據(jù)集X，聚類個數(shù)k，參數(shù)λ；

輸出 指示矩陣Y，聚類結(jié)果。

初始化 初始化參數(shù)λ并隨機生成指示矩陣Y∈Rn×k。

步驟1 利用式（1）計算出數(shù)據(jù)集樣本間的相似度矩陣W，從數(shù)據(jù)集中隨機選擇m個樣本，通過式（11）構(gòu)建數(shù)據(jù)點間的相似度矩陣E∈Rm×m；采樣點和剩余點間的相似度矩陣F∈Rm×(n-m)，并根據(jù)式（16）計算d。

步驟2 利用式（17）更新矩陣E和矩陣F，并根據(jù)式（18）計算出近似值用于乘法更新；

當(dāng)聚類指示矩陣Y不收斂；

計算分母函數(shù)Q=Y+2λYYTY；

步驟3 輸出指示矩陣Y，并將Y輸入k-means 聚類算法得到聚類結(jié)果。

傳統(tǒng)譜聚類算法可以視作三個階段：第一步為預(yù)處理階段，對由數(shù)據(jù)點計算出的相似度矩陣進行標(biāo)準(zhǔn)化；第二步為譜映射階段，計算相似度矩陣的特征向量；第三部為分組處理階段，使用常見的分組算法來得到聚類結(jié)果。本文的算法利用乘法更新迭代的Nystr?m擴展思想來實現(xiàn)快速譜聚類，從而降低了前兩個步驟所需要的時間損耗。

首先，在輸入包含n個點的數(shù)據(jù)集X=x1，x2，…，xn中，依據(jù)已知的相似性度量方法（式（1）），構(gòu)造數(shù)據(jù)點集的相似性矩陣W，根據(jù)式（18），利用Nystr?m 方法選取出一部分樣本來近似整個相似度矩陣。

由于需要在利用乘法更新迭代思想實現(xiàn)對目標(biāo)函數(shù)的優(yōu)化之后得到指示矩陣，再完成譜聚類最后的處理或分組步驟，但是從式（16）中可以看出，E-1中可能含有負(fù)數(shù)元素，使得可能為負(fù)。而設(shè)計條件的迭代規(guī)則中要求滿足非負(fù)約束性，因此在處理數(shù)據(jù)時，將矩陣E-1中的元素拆分為正負(fù)兩部分并分別記作：E+=(|E|+E)./2 和E-=(|E|-E)./2，那么此時二者都是非負(fù)矩陣。其次，由于中的大部分元素是正的，則近似值中的大部分元素也為正，此時可以將近似值中的負(fù)數(shù)元素視作噪聲，直接記作零元素處理。因此在公式中滿足P>0和Q>0的條件，即能按照更新規(guī)則進行后續(xù)計算。

最后對矩陣Y的行向量聚類，使用k-means算法將數(shù)據(jù)點劃分，若第i行被分到第j類中，則將數(shù)據(jù)點xi歸到第j類，從而得到k個聚類簇，輸出聚類結(jié)果。

3 算法理論分析

3.1 正確性和收斂性

在本節(jié)中，參照Ding 等［28］的思想，通過不同的對象和輔助函數(shù)來證明所提算法的正確性和收斂性。

KKT條件是非線性規(guī)劃最佳解的必要條件。KKT條件將拉格朗日乘數(shù)法所處理涉及等式的約束優(yōu)化問題推廣至不等式。為了驗證所提算法的正確性，需要引入滿足KKT 互補條件的拉格朗日函數(shù)：通過將它的梯度設(shè)置為零，能夠得到一個解必定收斂于固定點的不動點方程。如果可以證明式（10）中的更新規(guī)則滿足這些定點方程以及KKT 定點條件，則證明了本文所設(shè)計的IFSC算法的正確性。

3.1.1 正確性

命題1算法IFSC的正確性。

式（5）中給出了目標(biāo)函數(shù)，如式（17）中所示的更新規(guī)則，此時得到的約束解滿足規(guī)則下的KKT互補條件。

證明 為了解決優(yōu)化問題，需要引入拉格朗日函數(shù)，由于矩陣計算規(guī)則，有Tr(AB)=Tr(BA)且Tr(A)=Tr(AT)。則：

其中，拉格朗日乘數(shù)λ>0，Tr（YTLY）用于譜聚類，用于實現(xiàn)正交約束，這個函數(shù)滿足KKT 的互補松弛條件。將梯度設(shè)置為零，可得：

由互補松弛條件得出：

可以看出對于固定點，該等式的解必收斂，且更新規(guī)則式（17）中的極限解滿足固定點方程，在極限處有：Y（∞）=Y（t+1）=Y（t），其中t為迭代次數(shù)。

則式（24）遞減到：

當(dāng)約束區(qū)域包含目標(biāo)函數(shù)的原有可行解時，此時加上約束可行解仍落在約束區(qū)域內(nèi)，對應(yīng)g(x) < 0 的情況，此時約束條件不起作用，故此時可以讓λ=0，因為約束條件沒有作用。當(dāng)約束區(qū)域不包含目標(biāo)函數(shù)的可行解時，此時加上約束后可行解落在邊界g(x)=0 上，所以無論哪種情況都會得到：λg(x)=0。因此，式（17）中具有更新規(guī)則的約束解，滿足式（23）和KKT定點條件。

3.1.2 收斂性

為了證明IFSC 算法的收斂性，需要構(gòu)造輔助函數(shù)，從而使得在更新規(guī)則下，目標(biāo)函數(shù)單調(diào)遞減。

命題2算法IFSC的收斂性。

在更新規(guī)則（式（10））下，式（5）中所示的目標(biāo)函數(shù)單調(diào)遞減。

證明 將目標(biāo)函數(shù)式（5）記作關(guān)于矩陣X的函數(shù)：

其中，A=YTY，B=XTY。這時，文獻［29］中指出需要通過構(gòu)造輔助函數(shù)來證明等式在更新規(guī)則式（10）下單調(diào)遞減，此時輔助函數(shù)Z(X，X′)和J(X)應(yīng)同時滿足以下兩個條件：

此時，定義：

則由推導(dǎo)可得：

此時J（Xt）單調(diào)遞減。因此基于這種條件，首先需要構(gòu)造一個合適的輔助函數(shù)Z(X，X′)使得J（Xt）單調(diào)遞減，其次需要求得其最小值。根據(jù)下文中的命題3，在式（31）中定義的是J的輔助函數(shù)Z(X，X′)，其最小值由式（32）給出。根據(jù)式（28），有X(t+1)←X，X(t) ←X′，用A=FF便還原出式（10）的更新規(guī)則。

首先構(gòu)造關(guān)于矩陣Y的輔助函數(shù)。由于λI是一個常數(shù)矩陣，因此在以下證明步驟中將其省略。而需要證明的式（10）中Y的更新步驟恰好是式（28）中所構(gòu)輔助函數(shù)的更新。

命題3

對于滿足如下公式形式的函數(shù)J（X）：

其中所有矩陣均為非負(fù)值，則函數(shù)：

為目標(biāo)函數(shù)J（X）對應(yīng)的輔助函數(shù)，此處的log 為函數(shù)計算值。該輔助函數(shù)不僅滿足：J(X) ≤Z(X，X′)和J（X）=Z(X，X)，且是關(guān)于X的凸函數(shù)。故有全局最小值：

證明

為了找到兩個正項的上限，兩個負(fù)項下限，對于函數(shù)J（X）中的第三項，使用命題并令A(yù)←I，B←A+，得到一個上限：

對于函數(shù)的第二項，由于任意a，b> 0，不等式a≤(a2+b2)/(2ab)始終成立，故可以推導(dǎo)出其邊界如下：

而對于任意z> 0，都有z≥1+logz始終成立。故可以利用這個不等式，繼續(xù)推導(dǎo)函數(shù)J（X）其余兩個項的下界：

由式（36）可推導(dǎo)出函數(shù)J（X）的第一項的邊界：

由式（37）可推導(dǎo)出函數(shù)J（X）的最后一項的邊界：

匯總以上邊界值，就能夠驗證之前提出的目標(biāo)式（31）滿足J(X) ≤Z(X，X′)和J(X)=Z(X，X)的條件。此時為了求解Z(X，X′)的最小值，對函數(shù)進行求導(dǎo)得：

此時二階導(dǎo)數(shù)：

其中：

由以上證明可知，輔助函數(shù)Z(X，X′)是關(guān)于X的凸函數(shù)，通過設(shè)置求導(dǎo)，如式（40）所示，整理得到關(guān)于X的全局最小值即式（32）。

命題4

證明 令Sip=S′ipVip，用一個指定符號來表示不等式左右兩端的差異值：

由于A和B是對稱矩陣，即：

在出現(xiàn)B=I和S為列向量的特殊情況下，此結(jié)果的詳細表述在文獻［29-30］中。

3.2 算法優(yōu)勢對比

根據(jù)乘法更新迭代規(guī)則，本文設(shè)計的改進算法與傳統(tǒng)譜聚類算法相比在時間開銷上更有優(yōu)勢。傳統(tǒng)譜聚類算法花費了更多的時間來求解拉普拉斯矩陣的特征值分解，而由于利用了乘法更新優(yōu)化，本改進算法在這個方面提供了更有效的解決方案。同時，由于樣本數(shù)量和類別的增加，拉普拉斯矩陣特征值分解的時間快速增長，在處理高維數(shù)據(jù)集時需要花費更多時間。

由于非負(fù)約束和正交約束為聚類過程提供了更好的指示矩陣，這使得在后續(xù)處理的步驟（例如k-means）中能夠得到更好的聚類結(jié)果。因此，基于乘法更新迭代的算法在聚類性能方面也略勝于傳統(tǒng)譜聚類算法。

4 實驗驗證

4.1 實驗環(huán)境

由于文中涉及對算法性能的評估，實驗環(huán)境可能會對最終結(jié)果造成一定影響，因此本文在實驗過程中對于實驗公平性做了充分考慮。實驗過程中使用Matlab語言統(tǒng)一對譜聚類算法的輸入和輸出接口進行了設(shè)定，輸入接口為數(shù)據(jù)樣本及其相似度矩陣、相關(guān)類數(shù)及參數(shù)，輸出接口為聚類結(jié)果。

在實驗過程中，提取優(yōu)化了原作者所提供文獻或代碼中的算法公用模塊，即相似度矩陣的計算、拉普拉斯矩陣的構(gòu)建及k-means步驟等部分。例如，實驗在完成IFSC、SC 算法最后一步的k-means算法步驟中，并沒有使用Matlab自帶的內(nèi)置實現(xiàn)，從而避免了當(dāng)數(shù)據(jù)量較大時，計算內(nèi)存不足使用到磁盤的交換區(qū)而影響到以秒為精確度的算法評估結(jié)果，進行了單獨的抽離和統(tǒng)一的調(diào)用。在使用k-means算法進行矩陣運算時，統(tǒng)一設(shè)定閾值使分批計算的步驟能夠在內(nèi)存中完成；并對算法公用模塊進行了優(yōu)化，從而避免公用模塊與內(nèi)置實現(xiàn)差距太大導(dǎo)致的實驗誤差。

在準(zhǔn)確性評估中的計算都基于式（1）中高斯核函數(shù)：

實驗中將計算相似度指定為統(tǒng)一的帶寬參數(shù)σ，且統(tǒng)一設(shè)置了各個算法所需要的釆樣點數(shù)m，低秩估計值統(tǒng)一設(shè)定為k。

本文中的所有實驗都是在一臺8 GB DDR3內(nèi)存和主頻為2.8 GHz 的Intel Pentium CPU 的計算機上進行的，計算機的系統(tǒng)環(huán)境為Windows 10 64 位，實驗均在Matlab R2014a 中完成。為了防止計算機的讀寫速度對實驗結(jié)果造成影響，已經(jīng)將實驗的輸入數(shù)據(jù)在測試前完成讀寫預(yù)熱。

4.2 實驗數(shù)據(jù)

為了在實驗中對IFSC 算法的聚類性能進行驗證測試，實驗分別在由UCI（University of California Irvine）機器學(xué)習(xí)數(shù)據(jù)庫中選取的5 個真實數(shù)據(jù)集上和3 個人工合成數(shù)據(jù)集上進行驗證。

4.2.1 真實數(shù)據(jù)集

以下給出實驗部分所使用的真實數(shù)據(jù)集的介紹：

1）Mnist 數(shù)據(jù)集是一個手寫數(shù)字?jǐn)?shù)據(jù)集，數(shù)據(jù)集包含60 000個用于訓(xùn)練的示例和10 000個用于測試的示例。這些數(shù)字已經(jīng)過尺寸標(biāo)準(zhǔn)化并位于圖像中心，圖像為固定大?。?8像素×28像素），每個圖像都被平展并轉(zhuǎn)換為784個特征的一維numpy 數(shù)組。本文實驗使用了Mnist 數(shù)據(jù)集中包含5 000、7 500、10 000、12 500、15 000、17 500 和20 000 個樣本的子集。

2）Corel 數(shù)據(jù)集是圖像處理應(yīng)用任務(wù)中廣泛使用的數(shù)據(jù)集，包含巴士、建筑、恐龍等10 個類別的圖片，有很好的顏色、紋理、形狀等144 個屬性特征，利用這些屬性特征能夠描述并區(qū)別每一幅圖片的類別。在本文實驗中，分別使用2、6 和10類的3個子集來用于評估實驗中的算法。

3）WebKB數(shù)據(jù)集［31］中的示例是從4所大學(xué)（康奈爾大學(xué)、德克薩斯大學(xué)、華盛頓大學(xué)、威斯康星大學(xué)）數(shù)據(jù)集主頁中下載的網(wǎng)頁，這些網(wǎng)頁相應(yīng)的標(biāo)記分類為學(xué)生、教職員工、教職員工、部門、課程、項目以及其他。

4）RCV1 數(shù)據(jù)集［32］是人工對新聞故事分類整理得到文本分類測試集合，每篇文檔都是由一個詞頻-逆向文件頻率（Term Frequency-Inverse Document Frequency，TF-IDF）向量表示，實驗中選取了一個RCV1 子集，包含1 925 個文檔，包含29 992 個不同的詞，包括四個類別“C15”“ECAT”“GCAT”和“MCAT”。

5）Waveform 數(shù)據(jù)集是常用于分類和聚類任務(wù)中的噪聲波形數(shù)據(jù)集，波形數(shù)據(jù)被分為3類且各占33%，在第40維屬性之后的19維為噪聲數(shù)據(jù)，噪聲的均值為0、方差是1。

由于真實數(shù)據(jù)集中含有更多的噪聲，且樣本邊界模糊，因此，在實驗過程中調(diào)整了部分?jǐn)?shù)據(jù)集的大小，表2 中給出了實驗中使用數(shù)據(jù)集的詳細信息。

表2 實驗中使用的真實數(shù)據(jù)集Tab.2 Real datasets used in experiments

4.2.2 人工數(shù)據(jù)集

為了進一步驗證算法的正確性，實驗中除使用了真實數(shù)據(jù)集外，還在三個聚類任務(wù)中常使用的人工合成數(shù)據(jù)集［33］上進行了驗證，其主要目的是驗證IFSC 算法的有效性，即在不需要特征值分解的情況下同樣能夠達到相應(yīng)的聚類效果。圖1中給出了所使用的合成數(shù)據(jù)集的流形結(jié)構(gòu)。

根據(jù)流形結(jié)構(gòu)將數(shù)據(jù)集分別命名為環(huán)形分布數(shù)據(jù)集Circle Cluster（CC）、雙螺旋結(jié)構(gòu)數(shù)據(jù)集Two Spirals（TS）和雙月型數(shù)據(jù)集Two Moons（TM）。實驗在每個合成數(shù)據(jù)集中選取了10 000 個樣本點并劃分為兩個類簇。此時在合成數(shù)據(jù)集，尤其是環(huán)形分布數(shù)據(jù)集CC 和雙螺旋結(jié)構(gòu)數(shù)據(jù)集TS 中，僅依靠數(shù)據(jù)樣本點間距離作為標(biāo)準(zhǔn)的聚類算法就很難得到較好魯棒的聚類結(jié)果。

圖1 合成數(shù)據(jù)集的流形結(jié)構(gòu)Fig.1 Manifold structures of synthetic datasets

4.3 評價指標(biāo)

使用標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI）來評估不同聚類方法的表現(xiàn)性能，即互信息分?jǐn)?shù)的歸一化，用熵做分母將結(jié)果調(diào)整到0與1之間，由如式（44）來定義：

其中，ni、nj、nij分別代表樣本屬于聚類簇Ci(1 ≤i≤c)、屬于類別Lj(1 ≤j≤c)和同時屬于兩者時的樣本數(shù)量。NMI 值越大，則聚類結(jié)果越好。

4.4 實驗過程

為了驗證本文所設(shè)計IFSC 算法的正確性、準(zhǔn)確率和效率，在實驗中對以下方法進行比較：

1）使用k-means（KM）聚類算法。

2）使用本文所設(shè)計的基于乘法更新迭代思想的快速譜聚類（IFSC）算法。

3）傳統(tǒng)譜聚類（SC）算法，即需要特征值分解的譜聚類算法。

4）層次聚類（Hierarchical Clustering，HC）算法。

實驗結(jié)果除了給出本文算法與傳統(tǒng)譜聚類的性能對比，還能得到IFSC 算法相較于常用的基于距離迭代和基于層次分解的聚類算法在進行大規(guī)模數(shù)據(jù)集處理時的性能優(yōu)點。

4.5 正確性和收斂性

4.5.1 聚類性能比較

在真實數(shù)據(jù)集上的實驗主要用來評估算法正確率和執(zhí)行性能，實驗結(jié)果中，需要將速度和準(zhǔn)確率兩方面結(jié)合來綜合評價算法的表現(xiàn)；而在人工合成數(shù)據(jù)集上的實驗主要是驗證所設(shè)計的算法是否符合譜聚類的一般特征。

表3 中展示了不同算法在不同真實數(shù)據(jù)集上的執(zhí)行速度和準(zhǔn)確率。通過表3 可以看出，本文設(shè)計的IFSC 算法與傳統(tǒng)的譜聚類（SC）算法相比，極大地降低了算法所需要的時間成本，當(dāng)選用Corel 數(shù)據(jù)集，類數(shù)Cls=10 時，所消耗的時間僅是SC算法的28.4%，原因是IFSC算法避免了對拉普拉斯矩陣的創(chuàng)建和分解，在處理真實數(shù)據(jù)集，尤其數(shù)據(jù)規(guī)模較大和維數(shù)較高時最有效?？紤]到Matlab內(nèi)置的特征值分解是高度優(yōu)化的版本，迭代的方法完全是代碼，實際性能提升可以更高。另外可以看到，SC 算法雖然在處理WebKB 和Waveform 數(shù)據(jù)集時，在選用Washington、Texas、Wiscosin 這三個類上進行聚類的NMI 值優(yōu)于IFSC 算法，但僅增高了約21%，并且可以觀察到，在其他四個數(shù)據(jù)集上的聚類結(jié)果指標(biāo)均不如IFSC 算法有效。結(jié)合表3 中的速度對比，證明了不需要特征值分解的乘法迭代算法能夠完成譜聚類過程中對數(shù)據(jù)矩陣的度量和處理。

觀察IFSC 算法和KM 算法的速度性能對比可以發(fā)現(xiàn)，隨著數(shù)據(jù)集維數(shù)的升高，KM算法的運算消耗時間急劇增長。雖然KM 算法在Mnist 數(shù)據(jù)集上的速度性能表現(xiàn)良好，但在數(shù)據(jù)集RCV1此類高維數(shù)據(jù)集上表現(xiàn)較差。正如1.2節(jié)中提到的，傳統(tǒng)譜聚類算法在處理大規(guī)模和高維數(shù)據(jù)時需要在計算相似度矩陣方面消耗大量時間，從表3 中計算時間的對比可以發(fā)現(xiàn)，它的速度性能與KM 相比雖然有所提升，但效果仍然不佳。通過以上比較可以看出，IFSC 算法在處理小型數(shù)據(jù)集時的計算時間與k-means方法和SC類似。當(dāng)數(shù)據(jù)集規(guī)模和維數(shù)較大時，IFSC 算法的時間開銷能少，速度性能更優(yōu)，這是由于IFSC 算法簡化了計算相似度矩陣所需要的復(fù)雜步驟，且同時能有效處理譜分解問題。

表4 中展示了不同算法在不同人工合成數(shù)據(jù)集上的執(zhí)行速度和準(zhǔn)確率。由實驗結(jié)果可以觀察到，使用KM 算法的聚類結(jié)果準(zhǔn)確性很低，這是由于KM 方法是通過將距離最近樣本分配給最近的聚類中心，這種忽略數(shù)據(jù)全局分布的特點會導(dǎo)致它在處理流形數(shù)據(jù)集時的聚類能力有限。此外，可以觀察到，HC算法在處理合成數(shù)據(jù)集時能表現(xiàn)出相對較好的聚類性能，因此更適用于處理邊界清晰的合成數(shù)據(jù)；但由于對含噪聲和模糊樣本邊界的數(shù)據(jù)較敏感，在處理真實數(shù)據(jù)集時表現(xiàn)不佳。

表3 真實數(shù)據(jù)集的聚類結(jié)果Tab.3 Clustering results on real datasets

表4 合成數(shù)據(jù)集的聚類結(jié)果Tab.4 Clustering results on synthetic datasets

其次，從表4 中可以看出，IFSC 算法在TM 數(shù)據(jù)集上結(jié)果較好，但是在CC 和TS 數(shù)據(jù)集上則需要更多的迭代才能獲得更好的結(jié)果，這是因為CC 和TS 數(shù)據(jù)集符合流形分布。盡管如此，在相同精度下，IFSC 相較于傳統(tǒng)SC 方法在處理現(xiàn)實任務(wù)中更有效。本文中的IFSC 算法利用基于指示矩陣的乘法迭代完成聚類，驗證結(jié)果表明可達到與傳統(tǒng)譜聚類相當(dāng)?shù)木垲愋Ч?/p>

4.5.2 計算時間比較

為了比較IFSC算法的速度性能，在數(shù)據(jù)集Waveform 上進行了實驗驗證。計算時間主要受到迭代次數(shù)、采樣間隔、樣本維數(shù)和樣本大小的影響，因此在實驗過程中控制變量，將迭代次數(shù)設(shè)置為5 000，采樣間隔設(shè)置為5，且Waveform 數(shù)據(jù)集的維度為40，樣本個數(shù)為5 000。通過保持其中三個變量不變來評估剩余的一個變量，每種方法分別獨立運行20 次，參數(shù)λ=0.5。實驗結(jié)果如圖2所示。

首先，觀察圖2 中（a）和（b）的結(jié)果可以看出，在其他條件相同的情況下，同k-means 方法和傳統(tǒng)譜聚類（SC）方法相比，本文所設(shè)計的基于乘法更新迭代的快速譜聚類（IFSC）算法在處理大規(guī)模高維數(shù)據(jù)集時僅花費了一半的時間。

其次，由圖2（b）和（d）中的結(jié)果分析樣本維數(shù)和樣本大小對算法性能的影響可知，使用k-means方法所需的運行時間隨著樣本維數(shù)大小的升高而快速增加。

此外，從圖2（c）和（d）中還可以看出：傳統(tǒng)的譜聚類方法對樣本量的增加更敏感，這是由于譜聚類方法在計算特征向量這一運算步驟中需要O（n3）的計算復(fù)雜度，其中n為樣本個數(shù)。

圖2 不同方法的運行時間比較Fig.2 Comparison of running time of different methods

5 結(jié)語

本文簡要介紹了譜聚類技術(shù)處理復(fù)雜數(shù)據(jù)集時需要解決的兩個主要問題，即相似度矩陣構(gòu)造和拉普拉斯矩陣的特征值分解?；诔朔ǜ碌?guī)則，在聚類指示矩陣Y的基礎(chǔ)上設(shè)計了一種快速譜聚類優(yōu)化（IFSC）算法。該算法利用Nystr?m 方法對數(shù)據(jù)集隨機采樣后，根據(jù)由子矩陣表示出的指示矩陣完成迭代更新。實驗結(jié)果表明，所設(shè)計的算法在保證聚類精度的同時，提高了傳統(tǒng)譜聚類方法的效率，彌補了譜聚類在處理大樣本數(shù)據(jù)集時需要對拉普拉斯矩陣完成特征分解的時間消耗缺陷。接下來工作將使用其他采樣方法（如自適應(yīng)采樣方法）來完成算法設(shè)計模型的更新迭代，并從理論層面上進一步分析所設(shè)計的算法的誤差界和泛化界。