趙萌萌，王士同

1.江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫214122

2.江南大學(xué) 江蘇省媒體設(shè)計(jì)與軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫214122

1 引言

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

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

2 相關(guān)算法

2.1 Normalized Cuts

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

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

2.2 SC-SNN 算法

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

（1）構(gòu)造定向KNN 圖

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

（2）建立共享近鄰

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

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

（3）度量成對相似性

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

根據(jù)統(tǒng)計(jì)分析得知，Sij∈[0,1]。成對相似性Sij依據(jù)下列公式計(jì)算：

（4）計(jì)算Laplacian 矩陣

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

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

輸入：n個(gè)數(shù)據(jù)點(diǎn)，聚類簇?cái)?shù)K，近鄰數(shù)k。

輸出：輸入數(shù)據(jù)的簇標(biāo)記。

步驟1構(gòu)造定向的KNN 圖，找出共享最近鄰。

步驟2測量成對相似性，構(gòu)造相似性矩陣S。

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

步驟4計(jì)算L的K最大特征向量。

步驟5以L的K最大特征向量為基礎(chǔ)，將數(shù)據(jù)點(diǎn)分為K簇。

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

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

3.1 ISC-SNN 算法

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

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

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

然后，利用已知的訓(xùn)練集，使用KNN 算法來訓(xùn)練新加入的數(shù)據(jù)集DS2，再結(jié)合使用SC-SNN 算法學(xué)習(xí)到的特征，建立增量聚類模型，利用當(dāng)前的增量聚類模型對新數(shù)據(jù)集進(jìn)行聚類，得到新數(shù)據(jù)集的聚類結(jié)果，以此構(gòu)建新的訓(xùn)練集。再使用此訓(xùn)練集訓(xùn)練新加入的數(shù)據(jù)集DS3，DS3以DS2的方式進(jìn)行增量學(xué)習(xí)。以此種方式不斷加入新的數(shù)據(jù)集，直至所有數(shù)據(jù)集均得到聚類結(jié)果。

因?yàn)樾略鰯?shù)據(jù)不僅僅是根據(jù)自身的算法得出聚類結(jié)果，而是結(jié)合在已測試數(shù)據(jù)集的聚類結(jié)果上來預(yù)測其聚類的結(jié)果，即在根據(jù)自身特征進(jìn)行訓(xùn)練更新的基礎(chǔ)上，還會(huì)有效地結(jié)合學(xué)習(xí)到的歷史數(shù)據(jù)特征，故對新增數(shù)據(jù)的分類及預(yù)測準(zhǔn)確度不斷增加。

為了提升譜聚類算法的聚類效果，本文在式（1）的基礎(chǔ)上添加了一個(gè)平衡項(xiàng)，其中λ稱為平衡因子，它的取值往往跟聚類結(jié)果密切相關(guān)。由此，可以得出該算法的目標(biāo)函數(shù)：

其中，L為Laplacian 矩陣，D稱為相似矩陣的度矩陣，y為類標(biāo)簽矩陣。

對于參數(shù)λ，應(yīng)考慮λ=0 的情況。當(dāng)λ=0 時(shí)，即不考慮KNN 算法對聚類精確度的影響，在每一個(gè)數(shù)據(jù)塊的聚類過程中，僅依據(jù)SC-SNN 算法得出聚類結(jié)果。這樣得出的聚類效果并不理想。為了提高聚類性能，應(yīng)將KNN 算法得出的聚類結(jié)果考慮在內(nèi)，即λ≠0的情況，此時(shí)平衡項(xiàng)的加入能很好地提高聚類性能。

3.2 算法流程圖示及其步驟

根據(jù)算法的設(shè)計(jì)思想，可將ISC-SNN 算法簡單概括為圖1 所示。

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

輸入：n個(gè)數(shù)據(jù)點(diǎn)，聚類簇?cái)?shù)K，近鄰數(shù)k，劃分子集個(gè)數(shù)T。

輸出：輸入數(shù)據(jù)的簇標(biāo)記。

步驟1將數(shù)據(jù)集X分為T個(gè)子集，即X={DS1,DS2,…,DST}。

步驟2對初始數(shù)據(jù)集DS1使用SC-SNN 算法進(jìn)行聚類，得到聚類結(jié)果。

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

步驟3.1對未進(jìn)行聚類的其他子數(shù)據(jù)集DSi調(diào)用SC-SNN 算法，得到拉普拉斯矩陣。

步驟3.2參照數(shù)據(jù)集DSi-1得到的聚類結(jié)果，使用KNN方法確定此新增數(shù)據(jù)集DSi中數(shù)據(jù)點(diǎn)的類別。

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

end for

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

3.3 算法的時(shí)間復(fù)雜度

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

4 實(shí)驗(yàn)分析

本章將通過人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集兩種情況對SC-SNN 和ISC-SNN 兩種聚類算法進(jìn)行實(shí)驗(yàn)驗(yàn)證。其目的是為了證實(shí)ISC-SNN 算法的有效性和優(yōu)越性。

在本文的實(shí)驗(yàn)中，主要使用兩個(gè)量來評(píng)估聚類性能：運(yùn)行時(shí)間以及聚類精度。運(yùn)行時(shí)間為對某一數(shù)據(jù)集運(yùn)行一次聚類算法所用時(shí)間（在此使用計(jì)算機(jī)時(shí)間）。聚類精度為通過每個(gè)數(shù)據(jù)集的真實(shí)簇標(biāo)記和算法所得簇標(biāo)記計(jì)算出的聚類結(jié)果正確率。在使用相同數(shù)據(jù)集和運(yùn)行環(huán)境的情況下，耗時(shí)越少，聚類精度越高則表明算法的性能越好。

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

實(shí)驗(yàn)環(huán)境：Intel Core i3-3240CPU@3.40 GHz，4.00 GB RAM，Windows10，Matlab R2016b 等。

4.1 基于人造數(shù)據(jù)集的實(shí)驗(yàn)

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

由上述實(shí)驗(yàn)結(jié)果可知，當(dāng)數(shù)據(jù)量較小時(shí)，SCSNN 算法和ISC-SNN 算法都可以得到較好的聚類效果。但當(dāng)樣本容量達(dá)到18 000 時(shí)，SC-SNN 在運(yùn)行中發(fā)生了內(nèi)存不足的問題，導(dǎo)致該算法在本文的實(shí)驗(yàn)環(huán)境中無法順利運(yùn)行。而ISC-SNN 算法不僅可以在樣本容量不斷增大的情況下順利運(yùn)行，而且聚類時(shí)間明顯少于SC-SNN。

4.2 基于真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)

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

Fig.2 Original graph and experimental graph of DS1圖2 DS1 原圖及實(shí)驗(yàn)圖

Fig.3 Original graph and experimental graph of DS2圖3 DS2原圖及實(shí)驗(yàn)圖

Table 1 Experimental results of DS3表1 DS3 的實(shí)驗(yàn)結(jié)果

Table 2 Experimental datasets表2 實(shí)驗(yàn)數(shù)據(jù)集

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

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

Table 3 Experimental results on dataset Wifi,Waveform,Musk表3 數(shù)據(jù)集Wifi、Waveform、Musk 的實(shí)驗(yàn)結(jié)果

Table 4 Experimental results on dataset MGT表4 數(shù)據(jù)集MGT 的實(shí)驗(yàn)結(jié)果

5 結(jié)束語

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

Table 5 Experimental results on dataset Covertype表5 數(shù)據(jù)集Covertype的實(shí)驗(yàn)結(jié)果