一種基于自適應(yīng)相似矩陣的譜聚類算法

王貝貝 楊明 燕慧超 孫笑仙

摘?要：為了消除在構(gòu)建譜聚類算法的相似矩陣時(shí)，高斯核函數(shù)中尺度參數(shù)的波動(dòng)影響，構(gòu)建了一種自適應(yīng)相似矩陣，并應(yīng)用到譜聚類算法中。自適應(yīng)相似矩陣中數(shù)據(jù)點(diǎn)間的距離度量采用測(cè)地距離算法，相距較近的兩點(diǎn)間的距離近似于歐氏距離，相距較遠(yuǎn)的兩點(diǎn)則先根據(jù)歐氏距離得到每個(gè)數(shù)據(jù)點(diǎn)的k個(gè)近鄰點(diǎn)，然后累加近鄰點(diǎn)的測(cè)地距離，由此得到每對(duì)數(shù)據(jù)點(diǎn)間的最短距離。兩點(diǎn)間的局部密度用共享近鄰的定義來表示，更好地刻畫了數(shù)據(jù)集的本征結(jié)構(gòu)。在5個(gè)人工數(shù)據(jù)集和國際通用UCI數(shù)據(jù)庫中的5個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，所提算法的聚類準(zhǔn)確率高于對(duì)比算法的準(zhǔn)確率，對(duì)復(fù)雜分布數(shù)據(jù)有很強(qiáng)的自適應(yīng)能力。研究成果為數(shù)據(jù)挖掘及機(jī)器學(xué)習(xí)提供了思路和方法。

關(guān)鍵詞：應(yīng)用數(shù)學(xué);相似矩陣;譜聚類;密度;測(cè)地距離

中圖分類號(hào)：TP391???文獻(xiàn)標(biāo)志碼：A

doi： 10.7535/hbgykj.2018yx02001

A spectral clustering algorithm based on

adaptive similarity matrix

WANG Beibei1， YANG Ming1， YAN Huichao1， SUN Xiaoxian2

（1.School of Science， North University of China， Taiyuan， Shanxi? 030051， China;

2.Faculty of Science and Technology， Communication University of China， Beijing 100024， China）

Abstract：

In order to eliminate the fluctuation of the scale parameters in gaussian kernel function in constructing the similarity matrix of spectral clustering algorithm， a self-adaptive similarity matrix is constructed and applied in the spectral clustering algorithm. Geodesic distance measure is used in distance measure between data points in the adaptive similarity matrix. Distance between points closer to each other is approximately equal to the Euclidean distance， while for distance between two points farther away， each data's k-nearest neighbors are firstly obtained by Euclidean distance， then the geodesic distances of the nearest neighbors are accumulated， thus， the shortest distance between each pair of data can be get. The local density of two points is defined by the shared neighbor， reflecting the eigen structure of the data set better. Finally， experiments on both five artificial data sets and five UCI data sets show that the proposed method is more accurate than the others， and has a strong adaptive ability for complex distribution data. The research provides idea and method for data mining and machine learning.

Keywords：

applied mathematics; similar matrix; spectral clustering; density; geodesic distance

聚類分析在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域都有非常廣泛的應(yīng)用，它是根據(jù)數(shù)據(jù)點(diǎn)之間相似度的不同，將待聚類的數(shù)據(jù)集劃分成不同類的方法，源于很多領(lǐng)域，包括數(shù)學(xué)、計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)、生物學(xué)和經(jīng)濟(jì)學(xué)[1]。在不同的應(yīng)用領(lǐng)域，很多聚類技術(shù)都得到了發(fā)展，這些技術(shù)方法被用作描述數(shù)據(jù)，衡量不同數(shù)據(jù)源間的相似性，以及把數(shù)據(jù)源分類到不同的簇中。其中譜聚類算法[2]是在譜圖劃分理論基礎(chǔ)上發(fā)展起來的，不僅能識(shí)別任意形狀的樣本空間，應(yīng)用在非塊狀和非凸形數(shù)據(jù)的聚類問題上，而且收斂于全局最優(yōu)解，目前已在圖像分割[3]、文本挖掘[4]、計(jì)算機(jī)視覺[5]等領(lǐng)域得到較好的應(yīng)用。

譜聚類算法的核心是對(duì)特征向量的聚類，而該特征向量是由待聚類數(shù)據(jù)集的相似矩陣（拉普拉斯矩陣）特征分解得到的。因此，譜聚類算法性能的好壞取決于構(gòu)建的相似矩陣。然而傳統(tǒng)譜聚類算法中的高斯核函數(shù)只考慮數(shù)據(jù)點(diǎn)間的歐式距離，符合局部一致性，不符合全局一致性。文獻(xiàn)[6]提出一種近鄰自適應(yīng)局部尺度的譜聚類算法，局部尺度的值取為樣本點(diǎn)k個(gè)近鄰的距離和，解決了單一全局尺度參數(shù)局限的問題。文獻(xiàn)[7]用共享近鄰表征兩兩數(shù)據(jù)點(diǎn)間的局部密度，并應(yīng)用于相似度度量，提出一種基于共享近鄰的自適應(yīng)譜聚類算法（SNN-ASC）。文獻(xiàn)[8]提出一種密度敏感的相似性度量，并結(jié)合特征間隙，能根據(jù)數(shù)據(jù)的實(shí)際分布情況進(jìn)行聚類。文獻(xiàn)[9]提出一種基于無參相似矩陣的譜聚類，考慮數(shù)據(jù)集中點(diǎn)的密度、距離、連通性3個(gè)信息，然后構(gòu)造出一個(gè)無參相似圖并構(gòu)建相應(yīng)的相似矩陣。文獻(xiàn)[10]采用一種基于k-means算法的密度估計(jì)法構(gòu)造相似矩陣，其過程提高了密度估計(jì)的準(zhǔn)確性，但是卻需要6個(gè)超參數(shù)，且當(dāng)數(shù)據(jù)集中有較相似的結(jié)構(gòu)時(shí)，聚類效果不理想。

本研究在分析數(shù)據(jù)特征的基礎(chǔ)上，構(gòu)建了一種自適應(yīng)的相似矩陣。選用測(cè)地距離函數(shù)表征數(shù)據(jù)間的距離度量，相距較近的兩點(diǎn)間的距離近似于歐氏距離，相距較遠(yuǎn)的兩點(diǎn)則先根據(jù)歐氏距離得到每個(gè)數(shù)據(jù)點(diǎn)的k個(gè)近鄰點(diǎn)，然后累加近鄰點(diǎn)的測(cè)地距離，這樣便得到了每對(duì)數(shù)據(jù)點(diǎn)間的最短距離，不僅消除了高斯核函數(shù)中尺度參數(shù)的波動(dòng)影響，而且克服了歐式距離的局限性。根據(jù)每個(gè)點(diǎn)所處鄰域的稠密程度，用兩點(diǎn)間的共享近鄰數(shù)來表征，進(jìn)而得到待聚類數(shù)據(jù)點(diǎn)的[WT]基于測(cè)地距離和共享近鄰數(shù)的相似度，應(yīng)用到譜聚類算法中。最后在密度分布不均以及非塊狀（弧形、圓圈形、線形等）的人工數(shù)據(jù)集上、通用國際UCI實(shí)際數(shù)據(jù)集上都進(jìn)行實(shí)驗(yàn)，并與k-均值算法（k-means）和基于規(guī)范化拉普拉斯矩陣的譜聚類算法（NJW）進(jìn)行比較。結(jié)果表明，本文算法對(duì)復(fù)雜分布數(shù)據(jù)有更強(qiáng)的自適應(yīng)能力和更高的準(zhǔn)確率。

1 譜聚類算法的基本原理及現(xiàn)存問題

本節(jié)以傳統(tǒng)的譜聚類算法為基礎(chǔ)進(jìn)行分析，譜聚類的實(shí)現(xiàn)方法有很多種，其中主要研究對(duì)象是NJW譜聚類算法，其具體實(shí)現(xiàn)過程可以歸納為4步：

譜聚類算法的主要技巧是通過拉普拉斯矩陣將數(shù)據(jù)點(diǎn)映射到一個(gè)較低維的空間。在低維的數(shù)據(jù)空間中，數(shù)據(jù)點(diǎn)具有更好的聚類特性且滿足一致性假設(shè)。

1）局部一致性 在空間位置上相鄰的數(shù)據(jù)點(diǎn)具有更高的相似性;

2）全局一致性 同一結(jié)構(gòu)上（同類中）的數(shù)據(jù)點(diǎn)具有更高的相似性。

傳統(tǒng)譜聚類算法中的高斯核函數(shù)[WT]exp（[SX（]-‖xi-xj‖22σ2[SX）]）只考慮數(shù)據(jù)點(diǎn)間的歐式距離，符合局部一致性，不符合全局一致性，且當(dāng)尺度參數(shù)σ[WT]選取不同值時(shí)，聚類結(jié)果也不相同。圖1顯示了在歐氏距離的測(cè)度下，選取不同的尺度參數(shù)時(shí)在“Twomoons”數(shù)據(jù)集上的測(cè)試實(shí)驗(yàn)。

可以看出，尺度參數(shù)[WTBX]σ取不同數(shù)值時(shí)得到的聚類結(jié)果也不相同。當(dāng)σ=0.1時(shí)，聚類結(jié)果是最理想的;當(dāng)σ=0.22時(shí)，聚類結(jié)果出現(xiàn)了微小的偏差;當(dāng)σ=0.3時(shí)，聚類結(jié)果誤差較大;當(dāng)σ=25時(shí)，聚類結(jié)果完全錯(cuò)誤。針對(duì)不同的[WT]數(shù)據(jù)集，尺度參數(shù)的選擇范圍也不相同。

2 基于測(cè)地距離和密度的自適應(yīng)譜聚類算法

2.1 測(cè)地距離

在構(gòu)建相似度測(cè)度時(shí)，距離函數(shù)占著至關(guān)重要的地位，沒有任何一種距離測(cè)度適合所有的數(shù)據(jù)集。傳統(tǒng)的歐式距離做測(cè)度度量時(shí)，只是單純的計(jì)算連接兩點(diǎn)的直線段的長度，如圖2 a），如若這兩點(diǎn)間存在障礙物或者說存在另一個(gè)結(jié)構(gòu)中的樣本，此時(shí)的歐式距離是沒有實(shí)際意義的，這就是歐氏距離的局限性，圖2 b）是要得到的真實(shí)距離效果。越來越多的文獻(xiàn)都在做距離測(cè)度方法的改進(jìn)，文獻(xiàn)[11]提出用有效距離函數(shù)代替?zhèn)鹘y(tǒng)的地理距離函數(shù)，刻畫了目標(biāo)樣本和其他所有數(shù)據(jù)樣本之間的距離信息，具有全局特性。文獻(xiàn)[12]提出一種基于電阻距離的中文文本譜聚類算法，把文本表示成二分圖形式，使用電阻值表示兩點(diǎn)間的相似度值，電阻值隨著節(jié)點(diǎn)間路徑減小而減小，從而計(jì)算出任意節(jié)點(diǎn)間的有效電阻距離更具有實(shí)際意義。

測(cè)地距離是數(shù)學(xué)形態(tài)學(xué)中的一個(gè)重要概念，最早是TENENBAUM等[13]在研究非線性降維時(shí)提出的，能很好地表示流形結(jié)構(gòu)上樣本之間的真實(shí)距離。如圖3中的點(diǎn)[WTBX]A，B，C位于同一流形結(jié)構(gòu)上，[WTBX]dAB，dAC，dBC分[WTBX]別表示點(diǎn)A和點(diǎn)B，點(diǎn)A和點(diǎn)C，點(diǎn)B和點(diǎn)C之間的歐式距離，[WTBX]gAC，gBC[WTBX]分別表示點(diǎn)A和點(diǎn)C，點(diǎn)B和點(diǎn)C之間的測(cè)地距離，假設(shè)點(diǎn)A和點(diǎn)B之間存在障礙物不能直接計(jì)算歐式距離，在同一結(jié)構(gòu)中，從點(diǎn)A到達(dá)點(diǎn)B的路徑有很多條，最短的一條測(cè)地弧的長度稱為點(diǎn)A和點(diǎn)B間的測(cè)地距離。由圖3可以看出，當(dāng)A，C兩點(diǎn)非常近時(shí)，取[WTBX]gAC≈dAC，[WTBX]即認(rèn)為A，C兩點(diǎn)間的測(cè)地距離近似等于其歐氏距離。而當(dāng)A，B兩點(diǎn)之間相距較遠(yuǎn)時(shí)，則取兩點(diǎn)間的測(cè)地距離等于其近鄰點(diǎn)間的測(cè)地距離累加和，即[WTBX]gAB=gAC+gCB≈dAC+dCB，從而得到待聚類數(shù)據(jù)集中每對(duì)數(shù)據(jù)點(diǎn)之間的實(shí)際最短距離。

測(cè)地距離具體算法如下。

1）輸入數(shù)據(jù)集X=[x1，x2，…，xi，…，xn]，根據(jù)歐式距離計(jì)算點(diǎn)xi的k個(gè)近鄰。

2）初始化測(cè)地距離：

dG（xi，xj）=

d（xi，xj），點(diǎn)xj是點(diǎn)xi的k近鄰之一，∞ ，其他，

其中d（xi，xj）表示的是點(diǎn)xi和點(diǎn)xj之間的歐氏距離。

3）計(jì)算任意兩點(diǎn)間最短路徑：

For m=1：n

dG（xi，xj）=min{dG（xi，xj），

dG（xi，xm）+dG（xm，xj）}

End

2.2密度

僅用距離來描述數(shù)據(jù)之間的相似性遠(yuǎn)遠(yuǎn)不夠，特別是對(duì)密度分布不均的數(shù)據(jù)集，好的相似性度量不僅不依賴于尺度參數(shù)σ，而且能夠根據(jù)每個(gè)點(diǎn)所處鄰域的稠密程度得到正確的聚類結(jié)果。JARVIS等[14]曾提出一種基于共享近鄰相似度測(cè)量方法的聚類，本研究借鑒其中的共享近鄰的定義來表征兩點(diǎn)間的局部密度，進(jìn)而影響兩點(diǎn)間的相似度。共享近鄰的定義如下。

定義1數(shù)據(jù)集X={x1，x2，…，xn}中任意兩點(diǎn)xi和xj的共享近鄰定義為

SNN（xi，xj）=|n（xi）∩n（xj）|?? ，

其中n（xi）表示離點(diǎn)xi距離最近的前p個(gè)點(diǎn)，n（xj）表示離點(diǎn)xj距離最近的前p個(gè)點(diǎn)。一般地，參數(shù)p=20，本研究取數(shù)據(jù)集中樣本點(diǎn)數(shù)的5%。

2.3所提算法

譜聚類算法是依托譜圖劃分理論發(fā)展起來的，能在任意形狀的樣本空間上得到全局最優(yōu)解。其主要核心是對(duì)特征向量的聚類，而特征向量是由樣本數(shù)據(jù)的相似矩陣特征分解得到的，構(gòu)建一個(gè)性能優(yōu)越的相似矩陣至關(guān)重要。本研究構(gòu)建了一種自適應(yīng)的相似矩陣，首先選用測(cè)地距離函數(shù)表征數(shù)據(jù)間的距離度量，相距較近的兩點(diǎn)間的距離近似于歐式度量，相距較遠(yuǎn)的兩點(diǎn)間的距離則是通過最近鄰點(diǎn)間的歐式度量疊加得到的，這樣得到的距離度量克服了歐式距離的局限性，實(shí)際意義較明顯。然后根據(jù)每個(gè)點(diǎn)所處鄰域的稠密程度，用兩點(diǎn)間的共享近鄰數(shù)表征其密度，進(jìn)而得到待聚類數(shù)據(jù)點(diǎn)的基于測(cè)地距離和共享近鄰數(shù)的相似度，構(gòu)建對(duì)應(yīng)的相似矩陣，對(duì)其特征分解后得到的特征向量進(jìn)行聚類。算法流程如下。

輸入：待聚類數(shù)據(jù)集X={x1，x2，…，xn}，聚類個(gè)數(shù)k，共享近鄰數(shù)p;

1）根據(jù)2.1節(jié)計(jì)算數(shù)據(jù)集X={x1，x2，…，xn}中數(shù)據(jù)點(diǎn)之間的測(cè)地距離dG（xi，xj）;

2）根據(jù)定義1計(jì)算任意兩點(diǎn)xi和xj的前p個(gè)共同近鄰數(shù)SNN（xi，xj）;

3）計(jì)算基于測(cè)地距離和共享近鄰的數(shù)據(jù)點(diǎn)之間的相似度，構(gòu)造相應(yīng)的相似矩陣W=[wij]n×n，其中：

wij=exp（-d2G（xi，xj）σiσj（SNN（xi，xj）+1）），i≠j，1，i=j，

式中σi和σj分別表示點(diǎn)xi和xj到各自第l個(gè)近鄰的歐式距離，參見文獻(xiàn)[15]，建議l=7。

4）構(gòu)建規(guī)范化Laplacian矩陣L=D-1/2WD-1/2，其中D=diag（d1， d2，…， di，…，dn），di=∑nj=1wij 。

5）計(jì)算矩陣L的前k個(gè)最大特征值及其對(duì)應(yīng)的特征向量v1，v2，…，vk，可以得到特征矩陣V=[v1，v2，…，vk]∈Rn×k;

6）將矩陣V的行向量規(guī)范為單位向量，得到新矩陣為U，則uij=vij/（∑kv2ik）1/2;

7）將矩陣U的每一行對(duì)應(yīng)回原數(shù)據(jù)集中的相應(yīng)點(diǎn)，利用kmeans算法將其聚成k類C1，C2，…，Ck。

3實(shí)驗(yàn)與分析

為了驗(yàn)證本研究算法的性能，對(duì)比算法為k均值算法（kmeans）和基于規(guī)范化拉普拉斯矩陣的譜聚類算法（NJW），實(shí)驗(yàn)數(shù)據(jù)集為5個(gè)人工數(shù)據(jù)集和5個(gè)真實(shí)UCI數(shù)據(jù)集。

實(shí)驗(yàn)的操作平臺(tái)為64位win7系統(tǒng)、CPU為Intel（R） Core（TM）i52450M（2.50 GHz）、4G內(nèi)存的計(jì)算機(jī)和Matlab R2014a。

3.1評(píng)價(jià)指標(biāo)

對(duì)聚類結(jié)果的評(píng)價(jià)是檢驗(yàn)聚類算法結(jié)果好壞的重要環(huán)節(jié)，不同的評(píng)價(jià)標(biāo)準(zhǔn)會(huì)突出聚類算法不同的特性。本研究選取Rand指標(biāo)[16]作為評(píng)價(jià)標(biāo)準(zhǔn)，即根據(jù)本研究算法得到的決策數(shù)的正確率來評(píng)價(jià)算法的性能。定義決策數(shù)的正確率如下：

RI=a+da+b+c+d。

假設(shè)待聚類數(shù)據(jù)集有n個(gè)樣本，任意2個(gè)樣本可組成一個(gè)樣本對(duì)，則有n（n-1）/2個(gè)樣本對(duì)，即有n（n-1）/2個(gè)決策數(shù)目。式中：a表示同一類的樣本對(duì)被聚類到同一簇中;b表示不同類的樣本對(duì)被聚類到同一簇中;c表示同一類的樣本對(duì)被聚類到不同簇中;d表示不同類的樣本對(duì)被聚類到不同類的簇中，即a+d表示聚類正確的決策數(shù)，a+b+c+d表示總決策數(shù)n（n-1）/2。可知RI ∈（0，1），當(dāng)RI的值越大，則說明決策數(shù)的正確率越高。當(dāng)RI=1時(shí)，則說明聚類算法的聚類結(jié)果完全正確。

3.2數(shù)據(jù)集及實(shí)驗(yàn)結(jié)果分析

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

5個(gè)人工實(shí)驗(yàn)二維數(shù)據(jù)集的詳細(xì)信息如下：

Twomoons數(shù)據(jù)集：由2個(gè)弧形結(jié)構(gòu)構(gòu)成，1 502個(gè)樣本，2個(gè)類。

LineBlobs數(shù)據(jù)集：笑臉形，包含266個(gè)樣本，3個(gè)類。

Spiral數(shù)據(jù)集：螺旋形，包含944個(gè)樣本，2個(gè)類。

Sticks數(shù)據(jù)集：由4個(gè)線形結(jié)構(gòu)構(gòu)成，包含512個(gè)樣本，4個(gè)類。

Threecircles數(shù)據(jù)集：由同心圓構(gòu)成，包含299個(gè)樣本，3個(gè)類。

實(shí)驗(yàn)結(jié)果在圖4中給出，本研究所提算法在密度分布不均和非塊狀（弧形、圓圈形、線形等）數(shù)據(jù)集上都得到最優(yōu)劃分，證明了基于自適應(yīng)相似度矩陣的譜聚類算法的強(qiáng)大聚類功能。而kmeans算法和NJW算法都或多或少的出現(xiàn)了不同程度的聚類錯(cuò)誤。試驗(yàn)中NJW算法中σ的取值為數(shù)據(jù)點(diǎn)距離差值Δd的10%～20%時(shí)較理想[17]（Δd=maxi≠j Dij-mini≠j Dij，這里的D為歐式距離矩陣），統(tǒng)一取σ=0.1Δd。

3.2.2標(biāo)準(zhǔn)UCI數(shù)據(jù)集

5個(gè)真實(shí)實(shí)驗(yàn)數(shù)據(jù)集來自UCI數(shù)據(jù)庫，分別是：

鳶尾花數(shù)據(jù)集——Iris Data Set，后文簡(jiǎn)稱Iris;

葡萄酒數(shù)據(jù)集——Wine Data Set，后文簡(jiǎn)稱Wine;

玻璃鑒定數(shù)據(jù)集——Glass Identification Data Set，后文簡(jiǎn)稱Glass;

澳大利亞信貸審批數(shù)據(jù)集——Statlog （Australian Credit Approval） Data Set，后文簡(jiǎn)稱Acd;

鈔票驗(yàn)證數(shù)據(jù)集——Banknote Authentication Data Set，后文簡(jiǎn)稱Bna。

數(shù)據(jù)特征如表1所示。

表2給出的是k-means、NJW和本研究算法的聚類準(zhǔn)確率，在NJW算法中的最后一步會(huì)用到k-means算法劃分，而在應(yīng)用該算法時(shí)，不同的初始類中心會(huì)產(chǎn)生不同的聚類結(jié)果，為了降低此影響，本研究的k-means和NJW算法的取值都是程序運(yùn)行20次的平均值。上節(jié)提到NJW算法中σ的取值為數(shù)據(jù)點(diǎn)距離差值的10%～20%較理想，不失一般性，取δ=0.1d和δ=0.2d兩種情況下進(jìn)行驗(yàn)證實(shí)驗(yàn)。

從表2給出的準(zhǔn)確率的對(duì)比分析可知，在Wine數(shù)據(jù)集和Bna數(shù)據(jù)集上的聚類效果k-means算法優(yōu)于NJW算法，在Iris數(shù)據(jù)集和Acd數(shù)據(jù)集上的聚類結(jié)果，不論NJW算法取哪個(gè)參數(shù)都要比k-means算法高，而在Glass數(shù)據(jù)集上，k-means算法的聚類結(jié)果則介于NJW算法的2個(gè)不同參數(shù)得到的聚類準(zhǔn)確率之間，這表明對(duì)具有不同結(jié)構(gòu)的數(shù)據(jù)集，不同算法都有其優(yōu)缺點(diǎn)。而本研究所提算法在這5個(gè)實(shí)際數(shù)據(jù)集上的聚類準(zhǔn)確率都是最高的，再一次證明了本研究算法的魯棒性。

4結(jié)語

聚類結(jié)果對(duì)高斯核函數(shù)中尺度參數(shù)的選取極其敏感，距離函數(shù)在相似矩陣的構(gòu)建中同樣占據(jù)至關(guān)重要的地位，沒有一種距離函數(shù)適合所有類型的數(shù)據(jù)集。本研究在充分分析數(shù)據(jù)聚類一致性特征的基礎(chǔ)上，選用測(cè)地距離函數(shù)表征數(shù)據(jù)間的距離度量，同時(shí)引入共享近鄰的定義來表征兩點(diǎn)間的局部密度，進(jìn)而構(gòu)建了一種自適應(yīng)的相似矩陣，更好地刻畫數(shù)據(jù)集的本征結(jié)構(gòu)，應(yīng)用到譜聚類算法后，在密度分布不均以及非塊狀（弧形、圓圈形、線形等）的人工數(shù)據(jù)集上、通用國際UCI實(shí)際數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，表明了本文算法對(duì)復(fù)雜分布數(shù)據(jù)有很強(qiáng)的自適應(yīng)能力，且準(zhǔn)確率較高。下一步的研究重心將放在運(yùn)行效率的提高以及在高維數(shù)據(jù)集上的準(zhǔn)確性研究方面。

參考文獻(xiàn)/References：

[1]楊英，李海萍，于向東，等.基于因子和聚類分析的中國各省市競(jìng)爭(zhēng)力分析與研究[J].河北工業(yè)科技， 2013， 30（5）： 347-351.

YANG Ying，LI Haiping，YU Xiangdong，et al. Research of competitive power of provinces and cities in China based on factor analysis and cluster analysis[J]. Hebei Journal of Industrial Science and Technology， 2013， 30（5）： 347-351.

[2]LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing， 2007，17（4）： 395-416.

[3]劉仲民， 李戰(zhàn)明， 李博皓，等. 基于稀疏矩陣的譜聚類圖像分割算法[J].吉林大學(xué)學(xué)報(bào)（工學(xué)版）， 2017， 47（4）：1308-1313.

LIU Zhongmin， LI Zhanming， LI Bohao，et al. Spectral clustering image segmentation algorithm based on sparse matrix[J]. Journal of Jilin University（Engineering and Technology Edition）， 2017， 47（4）：1308-1313.

[4]MIJANGOS V， SIERRA G， MONTES A. Sentence level matrix representation for document spectral clustering[J]. Pattern Recognition Letters， 2017， 85：29-34.

[5]RODRGUEZ-PULIDO F J， GORDILLO B， LOURDES GONZLEZ-MIRET M， et al. Analysis of food appearance properties by computer vision applying ellipsoids to colour data[J]. Computers & Electronics in Agriculture， 2013， 99（99）：108-115.

[6]孔萬增， 孫昌思核， 張建海，等. 近鄰自適應(yīng)局部尺度的譜聚類算法[J]. 中國圖象圖形學(xué)報(bào)， 2012; 17（4）： 523-529.

KONG Wanzeng， SUNCHANG Sihe， ZHANG Jianhai，et al. Spectral clustering based on neighboring adaptive local scale[J]. Journal of Image and Graphics， 2012， 17（4）： 523-529.

[7]劉馨月， 李靜偉， 于紅，等. 基于共享近鄰的自適應(yīng)譜聚類[J]. 小型微型計(jì)算機(jī)系統(tǒng)， 2011， 32（9）： 1876-1880.

LIU Xinyue， LI Jingwei， YU Hong，et al. Adaptive spectral clustering based on shared nearest neighbors[J]. Journal of Chinese Mini-Micro Computer Systems， 2011， 32（9）： 1876-1880.

[8]張亞平， 楊明. 一種基于密度敏感的自適應(yīng)譜聚類算法[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)， 2013， 43（20）： 150-156.

ZHANG Yaping， YANG Ming. A kind of density sensitive adaptive spectral clusting algorithm[J]. Mathematics in Practice and Theory， 2013， 43（20）： 150-156.

[9]INKAYA T. A parameter-free similarity graph for spectral clustering[J]. Expert Systems with Applications， 2015， 42（24）： 9489-9498.

[10]BEAUCHEMIN M. A density-based similarity matrix construction for spectral clustering[J]. Neurocomputing， 2015， 151（151）： 835-844.

[11]BROCKMANN D， HELBING D. The hidden geometry of complex， network-driven contagion phenomena[J]. Science， 2013， 342（6164）： 1337-1342.

[12]李方源. 基于電阻距離的中文文本譜聚類算法研究[D].廣州：華南理工大學(xué)， 2013.

LI Fangyuan. Study of Spectral Clustering for Chinese Document Base on Resistance Distance[D]. Guangzhou： South China University of Technology， 2013.

[13]TENENBAUM J B， de SILVA V， LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science， 2000， 290（5500）： 2319-2323.

[14]JARVIS R A， PATRICK E A. Clustering using a similarity measure based on shared nearest neighbors[J]. IEEE Transactions on Computers， 1973， 22（11）： 1025-1034.

[15]ZELNIK-MANOR L， PERONA P. Self-tuning spectral clustering[J]. In Proceeding of NIPS， 2005， 1601-1608.

[16]YEH C C， YANG M S. Evaluation measures for cluster ensembles based on a fuzzy generalized Rand index[J]. Applied Soft Computing， 2017， 57：225-234.

[17]ERTZ L， STEINBACH M， KUMAR V. A new shared nearest neighbor clustering algorithm and its applications[C]// Workshop on Clustering High Dimensional Data and Its Applications， at Siam International Conference on Data Mining.[S.l.]：[s.n.]， 2002， 105-115.