共享近鄰緊密度的增量式譜聚類算法*

趙萌萌，王士同

1.江南大學 數字媒體學院，江蘇 無錫214122

2.江南大學 江蘇省媒體設計與軟件技術重點實驗室，江蘇 無錫214122

1 引言

聚類分析是研究分類問題的一種統計分析方法，同時也是機器學習、數據挖掘的一種重要算法，其重要性在文本挖掘[1]、圖像處理[2]等各個領域都得到了廣泛認可。聚類算法旨在按照一定的標準將數據對象劃分進不同的簇群內，使得在同一簇群內的相似度盡量高，不同簇群間的相似度盡量低[3]。近年來，譜聚類算法[4-6]已變為最受歡迎的聚類算法之一，譜聚類算法對于用相似矩陣的特征向量去揭示數據的簇群結構有一個很好的使用，在處理不同大小、不同形狀的聚類時有很好的效果[7-9]。然而，傳統的譜聚類算法不能揭示出一些復雜數據集的真正簇群，特別是未被完全分離的數據集。SC-SNN（spectral clustering based on closeness of shared nearest neighbors）算法[10-11]通過考慮共享近鄰的緊密度來測量相似度，而非距離度量。因此SC-SNN 能夠探索出兩個數據點之間的潛在相似性，且對未能完全分離的數據集具有很好的健壯性。此外，它們在凝結的聚類算法和高維度的數據集的聚類方法中也能成功應用[12-14]。

雖然相對于其他聚類算法來說，SC-SNN 提升了未完全分離的數據集的分類質量，但它也有許多不足。由于SC-SNN 的計算時間復雜度和空間復雜度較高，當處理大規模和高維數據時，其時間開銷較大，代價太昂貴，算法有可能會因為系統內存不足的原因而失效。而早在1990 年，Can 教授等就提出了增量式聚類算法[15]，以此來解決聚類時間復雜度較高，系統內存不足導致的算法失效等問題。所謂增量式聚類是指利用前期數據所獲得的聚類結果對新增數據進行分批或逐次進行聚類的過程[16-17]。此種方法對于解決重復聚類造成的資源浪費，提高聚類算法的性能等問題有著十分重要的意義。關于增量式的譜聚類算法，目前有許多學者已有研究，如文獻[18-19]等對研究此種算法提供了許多幫助。基于此種思想，本文提出了一種新的算法ISC-SNN（incremental spectral clustering based on closeness of shared nearest neighbors）來解決SC-SNN 算法所存在的問題，即將較大的數據集（適用于SC-SNN 算法，但由SC-SNN算法無法順利、高效運行的數據集）隨機均分為若干子集，第一個子集使用SC-SNN 算法，得出一個聚類結果，隨后的子數據集以前一個子數據集及其聚類結果為訓練集，結合SC-SNN 算法和KNN（K-nearest neighbor）算法得出聚類結果。改進后的ISC-SNN 算法既能減少聚類時間，提高聚類精度，也能有效解決因內存不足所造成的算法無法執行的情況。而且在實際的數據庫中，數據量往往是不斷增加的，使用增量式聚類算法，在面對新增的數據時，只需在原有數據庫的基礎上，進行一些由于新增的數據所引起的更新，不需要修改大規模數據，這將會節省很大的工作量。

2 相關算法

2.1 Normalized Cuts

譜聚類算法是基于譜圖理論的，它能在任意形狀的樣本集上聚類且收斂于全局最優解，其本質是將聚類問題轉化為圖的劃分問題。專家們基于Ratio cut[20]、Minimum Cuts[21]、Normalized Cuts[22]等 劃分標準提出了不同的聚類方法，而本文算法是基于Normalized Cuts 提出的。Normalized Cuts 是由Shi和Malik 提出的一種無監督圖像分割技術，它將圖像分割問題轉化為了圖的劃分問題。Normalized Cuts 既能滿足類間的相似度最小，又能滿足類內的相似度最大。而基于Normalized Cuts 的譜聚類算法的目標函數為：

其中，Laplacian 矩陣L=D-1/2SD-1/2，W是圖G=(V,E)中各頂點的相似矩陣，D=diag(d1,d2,…,dn)稱為W的度矩陣，di=∑jw(i,j)表示從點xi到其他點的連接度。

2.2 SC-SNN 算法

在Rd中給出具有n個數據點的數據集X={x1,x2,…,xn}，聚類算法將數據集劃分為K個不相交的集合，每個集合稱為一個簇。

（1）構造定向KNN 圖

在定向KNN 圖中，如果xj是xi的K最近鄰之一，則xi到xj組成一條邊。xj是xi的直接繼承者，標記為xi→xj。此外，xi?xj為xi與xj互為最近鄰。

（2）建立共享近鄰

在定向KNN 圖中，Ni為xi的最近鄰的集合。在xi和xj之間共享最近鄰的集合為Ni?Nj。

成對相似性Sij是基于集合Ni?Nj進行測量的。通常Ni不包括xi這一點，故Ni?Nj不包括xi和xj兩點。點xi和xj之間共享最近鄰的集合Ni?Nj被定義為：

（3）度量成對相似性

為了測量成對相似性Sij，首先根據它們點xi和xj的距離去權重在Ni?Nj里的共享最近鄰。用wij表示共享最近鄰的權重。xr是Ni?Nj里的一個共享最近鄰。假設xr是xi的第ithr個最近鄰，是xj的第個最近鄰。在定向KNN 圖中，共享最近鄰的權重wij依下式計算：

根據統計分析得知，Sij∈[0,1]。成對相似性Sij依據下列公式計算：

（4）計算Laplacian 矩陣

其中，S是圖G=(V,E) 中各頂點的相似矩陣；D=diag(d1,d2,…,dn)稱為S的度矩陣，di=∑jS(i,j)表示從點xi到其他點的連接度。

SC-SNN 算法的具體步驟如下：

輸入：n個數據點，聚類簇數K，近鄰數k。

輸出：輸入數據的簇標記。

步驟1構造定向的KNN 圖，找出共享最近鄰。

步驟2測量成對相似性，構造相似性矩陣S。

步驟3基于相似性矩陣S，計算歸一化拉普拉斯算子矩陣L。

步驟4計算L的K最大特征向量。

步驟5以L的K最大特征向量為基礎，將數據點分為K簇。

此算法在計算相似度矩陣，求特征向量時，消耗多項式時間，不難想象，隨著數據量的不斷增加，矩陣維度慢慢增大，時間消耗將逐漸變得不可接受。因此，將提出一種新的基于共享近鄰緊密度的增量式譜聚類。

3 基于共享近鄰緊密度的增量式譜聚類

3.1 ISC-SNN 算法

本節中將介紹ISC-SNN 算法。對于ISC-SNN 算法，重點放在對聚類的精確度以及時間的優化上。本文給出的處理方法為：先將較大的數據集分解為若干子集，然后逐步求解小數據集。這種方式主要具有有利的計算性質和實現簡單等優點。下面給出其主要設計思想：

在Rd中給出具有n個數據點的數據集X={x1,x2,…,xn}，將其隨機劃分為T個大小基本相等的數據集DS1,DS2,…,DST。

首先，對于初始數據集DS1，使用算法SC-SNN得到數據集的聚類結果，構建訓練集。由于聚類方法SC-SNN 是無監督方法，沒有利用類別標簽屬性，在對數據集進行聚類時，如果對于某個數據集，初始的聚類算法分簇錯誤，就會造成某個聚簇中包含有不同實際類別的數據。為了解決此問題，在本文算法中，會在SC-SNN 算法的基礎上加入KNN 算法，KNN 算法可以利用已測試數據集中包含的類別信息得出自身的類標簽矩陣，使之與SC-SNN 算法得到的特征矩陣結合構成平衡項，這樣就可以降低發生錯誤分類這種狀況的概率，增加聚類的精確度，盡可能多地使各個數據分到正確的簇中。

然后，利用已知的訓練集，使用KNN 算法來訓練新加入的數據集DS2，再結合使用SC-SNN 算法學習到的特征，建立增量聚類模型，利用當前的增量聚類模型對新數據集進行聚類，得到新數據集的聚類結果，以此構建新的訓練集。再使用此訓練集訓練新加入的數據集DS3，DS3以DS2的方式進行增量學習。以此種方式不斷加入新的數據集，直至所有數據集均得到聚類結果。

因為新增數據不僅僅是根據自身的算法得出聚類結果，而是結合在已測試數據集的聚類結果上來預測其聚類的結果，即在根據自身特征進行訓練更新的基礎上，還會有效地結合學習到的歷史數據特征，故對新增數據的分類及預測準確度不斷增加。

為了提升譜聚類算法的聚類效果，本文在式（1）的基礎上添加了一個平衡項，其中λ稱為平衡因子，它的取值往往跟聚類結果密切相關。由此，可以得出該算法的目標函數：

其中，L為Laplacian 矩陣，D稱為相似矩陣的度矩陣，y為類標簽矩陣。

對于參數λ，應考慮λ=0 的情況。當λ=0 時，即不考慮KNN 算法對聚類精確度的影響，在每一個數據塊的聚類過程中，僅依據SC-SNN 算法得出聚類結果。這樣得出的聚類效果并不理想。為了提高聚類性能，應將KNN 算法得出的聚類結果考慮在內，即λ≠0的情況，此時平衡項的加入能很好地提高聚類性能。

3.2 算法流程圖示及其步驟

根據算法的設計思想，可將ISC-SNN 算法簡單概括為圖1 所示。

ISC-SNN 算法的具體步驟如下所述：

輸入：n個數據點，聚類簇數K，近鄰數k，劃分子集個數T。

輸出：輸入數據的簇標記。

步驟1將數據集X分為T個子集，即X={DS1,DS2,…,DST}。

步驟2對初始數據集DS1使用SC-SNN 算法進行聚類，得到聚類結果。

步驟3fori=2,3,…,T

步驟3.1對未進行聚類的其他子數據集DSi調用SC-SNN 算法，得到拉普拉斯矩陣。

步驟3.2參照數據集DSi-1得到的聚類結果，使用KNN方法確定此新增數據集DSi中數據點的類別。

步驟3.3依據式（5）得到此層中的最終指示向量，繼而得出聚類結果。

end for

Fig.1 Algorithm process diagram圖1 算法流程圖示

3.3 算法的時間復雜度

本文中算法的時間復雜度取決于步驟2、步驟3。其中步驟2 的時間復雜度為Ο((n/T)2lbn)。步驟3單次計算的時間復雜度為Ο((n/T)2lbn+(n/T×knum))，其中knum是使用KNN 算法求解數據集類別時所選擇的近鄰數，而在第3 步的計算次數為T，故這兩步的時間復雜度為Ο(n2lbn/T+n×knum)。故可以得知此算法的時間復雜度為Ο((n/T)2lbn+n2lbn/T+n×knum))。可以看出當T值越大時，時間復雜度越低。

4 實驗分析

本章將通過人造數據集和真實數據集兩種情況對SC-SNN 和ISC-SNN 兩種聚類算法進行實驗驗證。其目的是為了證實ISC-SNN 算法的有效性和優越性。

在本文的實驗中，主要使用兩個量來評估聚類性能：運行時間以及聚類精度。運行時間為對某一數據集運行一次聚類算法所用時間（在此使用計算機時間）。聚類精度為通過每個數據集的真實簇標記和算法所得簇標記計算出的聚類結果正確率。在使用相同數據集和運行環境的情況下，耗時越少，聚類精度越高則表明算法的性能越好。

SC-SNN 和ISC-SNN 算法中所有的參數都按如下取值：近鄰數k，由文獻[10]可知，k值的選擇對于聚類的精度影響不大，且在大多數情況下，在其值為7 時取得最優值，故本文實驗中SC-SNN 和ISC-SNN兩種算法的k值均設置為7；KNN 中的K均取7；λ的取值為多次重復實驗中，提到的聚類指標的均值達到較好的時候的取值；T為數據集分成的子數據集的個數，需要根據數據量的大小來選取適合的值，其取值情況將在實驗結果中給出。

實驗環境：Intel Core i3-3240CPU@3.40 GHz，4.00 GB RAM，Windows10，Matlab R2016b 等。

4.1 基于人造數據集的實驗

為了方便將聚類結果圖形化，給定3 類人造數據集：DS1 是兩個圓形的數據集，包含582 個數據點；DS2 是兩個半月形的數據集，包含1 200 個數據點；DS3是將兩個半月形的數據集DS2擴容為包含30 000個數據點的數據集。由于SC-SNN 算法在數據集容量為30 000 時，算法失效，故僅將其在DS1 和DS2 的數據集下的聚類效果圖展示出來。對于DS3，將從中抽取不同容量的子集來運行SC-SNN 和ISC-SNN 兩種算法以測試其聚類所需時間和準確度。在實驗中，由于聚類的實驗結果不穩定，故實驗結果均為多次實驗后計算的平均值。對于ISC-SNN 中的參數λ分別為2、3；實驗結果如圖2、圖3 所示，不同簇使用不同的顏色來表示。而在表1 中，設置了λ為0 的對比實驗，其中在ISC-SNN 的實驗結果中，數據的第一行為λ=3 的結果，第二行為λ=0 的結果，在真實數據集中實驗結果同樣按照此種格式設置。

由上述實驗結果可知，當數據量較小時，SCSNN 算法和ISC-SNN 算法都可以得到較好的聚類效果。但當樣本容量達到18 000 時，SC-SNN 在運行中發生了內存不足的問題，導致該算法在本文的實驗環境中無法順利運行。而ISC-SNN 算法不僅可以在樣本容量不斷增大的情況下順利運行，而且聚類時間明顯少于SC-SNN。

4.2 基于真實數據集的實驗

真實數據集由于噪聲信息的存在，聚類劃分的難度要大于人造數據集，對算法性能的驗證也更具說服力。在本節，將使用UCI 數據庫里的5 個數據集Wifi、Waveform、Musk、MGT、Covertype 來 進 行 實驗。數據集的詳細信息如表2 所示。

Fig.2 Original graph and experimental graph of DS1圖2 DS1 原圖及實驗圖

Fig.3 Original graph and experimental graph of DS2圖3 DS2原圖及實驗圖

Table 1 Experimental results of DS3表1 DS3 的實驗結果

Table 2 Experimental datasets表2 實驗數據集

其中，對于3 個數據集Wifi、Waveform、Musk，SC-SNN 算法可以成功執行，故直接對其中的所有樣本進行多次重復實驗，取其平均值作為實驗結果，其中Wifi、Waveform、Musk 中的λ依次設置為3、3、1，并給出與λ=0 的對比。其實驗結果如表3 所示，從結果中可以看出，當λ為非零值時，ISC-SNN 相較于SC-SNN 而言，不僅時間縮短了很多，而且聚類精度也明顯增加。但當λ為0 時，聚類時間雖然縮短了很多，但聚類精度有可能會下降。由此可知當選取適合的λ時，ISC-SNN 算法在小數據集的聚類問題上可以達到很好的聚類效果。為了進一步驗證ISCSNN 的聚類性能的優越性，將使用MGT 和Covertype兩個較大一點的數據集，由于樣本容量過大，當一次性載入所有樣本時會致使SC-SNN 算法失效，故從中分別隨機選取若干種不同容量的子集進行測試。關于數據集MGT 和Covertype 中的λ分別設置為2、3，并給出與λ=0 的對比。其實驗結果在表4 和表5 中給出。

由上述實驗可知，在表4 中，SC-SNN 在樣本容量達到18 000 時，計算中發生了內存不足的問題，導致在本文的實驗環境中無法順利運行。由于Covertype的維度比MGT 的維度要高，導致SC-SNN 在樣本容量達到15 000 時就發生了內存不足的問題。不難知道，當數據集的維度越來越高時，SC-SNN 算法所能正常執行的容量將會越來越低。而ISC-SNN 算法不僅可以在樣本容量不斷增大，維度不斷升高的情況下順利運行，在λ為零時，聚類時間雖然有了大幅度減少，但準確度可能會有降低的情況，但在λ為非零值時，聚類時間和準確度都明顯優于SC-SNN。此外，從上述實驗中能夠發現，數據集分成的數據子集越多，精確度越高，聚類所需的時間越短。因此，當樣本容量較大時，選擇劃分的子集數也是很重要的，要想達到快速運行的目的，應該劃分較多的子集來進行聚類。

Table 3 Experimental results on dataset Wifi,Waveform,Musk表3 數據集Wifi、Waveform、Musk 的實驗結果

Table 4 Experimental results on dataset MGT表4 數據集MGT 的實驗結果

5 結束語

本文提出了一種基于共享近鄰緊密度的增量式譜聚類算法。它是在基于共享近鄰緊密度的譜聚類算法的基礎上，為了能增強精度，減少運行時間并能夠適用于大數據的目的上提出的。此算法采用增量式的方法，不僅解決了因內存不足而造成的算法失效問題，而且能在很大程度上提升聚類的性能。盡管此種算法有一定的優點，但仍有許多可改進之處，故在今后的研究中將會對此算法的不足之處進行不斷的優化。

Table 5 Experimental results on dataset Covertype表5 數據集Covertype的實驗結果