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

劉靜姝，王 莉*，劉驚雷

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

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

0 引言

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

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

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

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

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

本文的主要工作如下：

1）基于譜聚類問題的拉格朗日函數，對聚類指示矩陣Y進行求導，得到關于矩陣Y迭代更新的乘法規則，從而避免傳統譜聚類的特征值分解。

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

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

4）在五個真實數據集上進行了實驗驗證，實驗結果表明，本文設計的快速譜聚類算法與傳統譜聚類算法和其他聚類算法相比，處理大規模數據集時，計算時間有所降低；且在處理含有較多噪聲的真實數據集時表現優于其他聚類方法（如層次聚類）。

1 相關工作

1.1 譜聚類

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

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

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

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

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

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

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

1.2 譜聚類的基本算法

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

構建相似度矩陣W常常使用如下的高斯核函數來作定義：

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

表1 符號描述Tab.1 Symbol description

譜聚類旨在找到使得規范割目標函數最小的子集A和子集B［24］，用類的容量作歸一項，兼顧了類的內部和外部的連接。利用以下公式可以計算出最優的NCut值：

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

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

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

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

2 快速譜聚類框架

2.1 問題描述

譜聚類算法可以視作函數最小化：

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

其中Y>0。為了實現損失函數式（6）的最小化，有：

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

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

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

2.2 算法設計和描述

2.2.1 設計模型

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

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

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

相應的，W的近似矩陣為：

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

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

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

證明

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

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

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

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

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

將式（17）中的E和F代入標準化的相似度矩陣中得到：

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

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

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

2.2.2 算法描述

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

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

輸入 數據集X，聚類個數k，參數λ；

輸出 指示矩陣Y，聚類結果。

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

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

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

當聚類指示矩陣Y不收斂；

計算分母函數Q=Y+2λYYTY；

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

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

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

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

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

3 算法理論分析

3.1 正確性和收斂性

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

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

3.1.1 正確性

命題1算法IFSC的正確性。

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

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

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

由互補松弛條件得出：

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

則式（24）遞減到：

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

3.1.2 收斂性

為了證明IFSC 算法的收斂性，需要構造輔助函數，從而使得在更新規則下，目標函數單調遞減。

命題2算法IFSC的收斂性。

在更新規則（式（10））下，式（5）中所示的目標函數單調遞減。

證明 將目標函數式（5）記作關于矩陣X的函數：

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

此時，定義：

則由推導可得：

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

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

命題3

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

其中所有矩陣均為非負值，則函數：

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

證明

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

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

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

由式（36）可推導出函數J（X）的第一項的邊界：

由式（37）可推導出函數J（X）的最后一項的邊界：

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

此時二階導數：

其中：

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

命題4

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

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

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

3.2 算法優勢對比

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

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

4 實驗驗證

4.1 實驗環境

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

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

在準確性評估中的計算都基于式（1）中高斯核函數：

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

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

4.2 實驗數據

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

4.2.1 真實數據集

以下給出實驗部分所使用的真實數據集的介紹：

1）Mnist 數據集是一個手寫數字數據集，數據集包含60 000個用于訓練的示例和10 000個用于測試的示例。這些數字已經過尺寸標準化并位于圖像中心，圖像為固定大小（28像素×28像素），每個圖像都被平展并轉換為784個特征的一維numpy 數組。本文實驗使用了Mnist 數據集中包含5 000、7 500、10 000、12 500、15 000、17 500 和20 000 個樣本的子集。

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

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

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

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

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

表2 實驗中使用的真實數據集Tab.2 Real datasets used in experiments

4.2.2 人工數據集

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

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

圖1 合成數據集的流形結構Fig.1 Manifold structures of synthetic datasets

4.3 評價指標

使用標準化互信息（Normalized Mutual Information，NMI）來評估不同聚類方法的表現性能，即互信息分數的歸一化，用熵做分母將結果調整到0與1之間，由如式（44）來定義：

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

4.4 實驗過程

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

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

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

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

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

實驗結果除了給出本文算法與傳統譜聚類的性能對比，還能得到IFSC 算法相較于常用的基于距離迭代和基于層次分解的聚類算法在進行大規模數據集處理時的性能優點。

4.5 正確性和收斂性

4.5.1 聚類性能比較

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

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

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

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

表3 真實數據集的聚類結果Tab.3 Clustering results on real datasets

表4 合成數據集的聚類結果Tab.4 Clustering results on synthetic datasets

其次，從表4 中可以看出，IFSC 算法在TM 數據集上結果較好，但是在CC 和TS 數據集上則需要更多的迭代才能獲得更好的結果，這是因為CC 和TS 數據集符合流形分布。盡管如此，在相同精度下，IFSC 相較于傳統SC 方法在處理現實任務中更有效。本文中的IFSC 算法利用基于指示矩陣的乘法迭代完成聚類，驗證結果表明可達到與傳統譜聚類相當的聚類效果。

4.5.2 計算時間比較

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

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

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

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

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

5 結語

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