胡乾坤，丁世飛

中國礦業(yè)大學 計算機科學與技術學院，江蘇 徐州 221116

1 引言

聚類是數(shù)據(jù)挖掘領域中熱門的研究課題之一，其研究目的是根據(jù)相似性的大小把數(shù)據(jù)分到不同的簇中，使得簇內數(shù)據(jù)之間的相似性盡可能大，簇間數(shù)據(jù)之間的相似性盡可能小。目前，很多聚類算法已經被提出，例如層次聚類[1]、k-means聚類[2]、支持向量機[3]、初始化獨立聚類[4]、多視圖聚類[5]等算法。近幾年來，譜聚類算法逐漸發(fā)展成為較重要的聚類算法之一，原因是其具有較強的概括性、有效性和豐富的理論基礎[6]。譜聚類算法的理論基礎包括平衡圖切判據(jù)、隨機游走和擾動理論[7]。譜聚類算法的核心思想是把樣本空間的聚類問題轉化無向圖G的圖劃分問題。數(shù)據(jù)樣本視作無向圖G上的頂點，數(shù)據(jù)樣本對之間的相似性視作頂點之間邊的權重。一般譜聚類算法包含以下3個步驟：第一，根據(jù)所給的樣本數(shù)據(jù)集，定義一個相似性矩陣來描述數(shù)據(jù)之間的相似性；第二，進一步構建拉普拉斯矩陣并計算其特征值和對應特征向量；第三，選擇合適的特征向量，使用傳統(tǒng)聚類算法對數(shù)據(jù)樣本進行聚類[8]。

最近，在譜聚類中引入p-Laplacian算子，引起了研究者的廣泛關注。它使得算法可以獲得較好的圖切判據(jù)，即Cheeger cut（Ccut或者齊格切）[9]。Ccut旨在尋求一種簇內數(shù)據(jù)樣本之間的相似性盡量大，簇間數(shù)據(jù)樣本之間的相似性盡量小，同時可以獲得更具有平衡性的劃分效果。研究表明，通過計算p-Laplacian矩陣的第二小特征向量，使用圖劃分標準Ccut能夠獲得更具有平衡性的聚類效果。但是，原p-譜聚類算法的相似性計算方法很難構造一個高質量的相似性矩陣來描述數(shù)據(jù)之間的內在關系，聚類效果對相似性計算方法是非常敏感的；再者，算法中相似性計算的方法與數(shù)據(jù)聚類的方法分別在兩個不同的步驟中實現(xiàn)，故相似矩陣并不一定是適合此聚類方法的，從而有可能得不到最優(yōu)的聚類效果[10]。

本文從一種新的視角出發(fā)來解決上述聚類問題。首先，通過數(shù)據(jù)樣本與最優(yōu)近鄰之間的局部距離來優(yōu)化相似性計算的方法，從而得到高質量的相似性矩陣[11]。假設數(shù)據(jù)樣本之間距離越小，兩者之間的相似性越大。再者，通過對p-Laplacian矩陣進行秩約束獲得較為理想的近鄰分配，可以實現(xiàn)在最終矩陣中連通分量的數(shù)目等同于聚類數(shù)目，即每一個連通分量對應一個簇。本文提出的基于局部相似性優(yōu)化的p-譜聚類算法，能夠同時實現(xiàn)相似性矩陣的計算以及對數(shù)據(jù)樣本的聚類兩個步驟，從而得出較優(yōu)的聚類結果[12]。本文使用此聚類算法分別對人工數(shù)據(jù)集和UCI數(shù)據(jù)集進行實驗，結果表明，基于局部相似性優(yōu)化的p-譜聚類算法可以獲得較好的更加具有平衡性的聚類效果。

本文組織結構如下：第2章介紹了p-Laplacian矩陣的概念，分析了p-Laplacian矩陣與齊格切之間的關系；第3章描述了局部相似性優(yōu)化方法的理論基礎，并提出了基于局部相似性優(yōu)化的p-譜聚類算法；第4章通過實驗驗證了基于局部相似性優(yōu)化的p-譜聚類算法的效果；最后對全文進行總結并討論研究前景。

2 p-譜聚類

譜聚類的思想源于譜圖劃分理論。對于一個數(shù)據(jù)集，可以構造一個無向加權圖G=(V,E)，其中頂點集合V表示數(shù)據(jù)樣本，權值集合E表示數(shù)據(jù)之間的相似性。假設A是頂點集合V的子集，則A的補集可以定義為對于A和Aˉ之間的圖劃分目標函數(shù)可以表示如下[13]：

其中，wij表示頂點i和j之間的親和度。

為了產生更加均勻的聚類效果，Shi和Malik在此基礎上，進一步提出圖劃分標準規(guī)范切（normalized cut，Ncut），表達式如下[14]：

對該目標函數(shù)最小化意味著對類間數(shù)據(jù)樣本相似度最小化，同時，最大化類內數(shù)據(jù)樣本的相似度，故此圖劃分標準能夠產生具有較好均衡性的劃分結果。但此目標函數(shù)是投影矩陣的非線性函數(shù)，可能會存在局部極小值的問題。

為了進一步得到更具有平衡性的聚類效果，Cheeger等人提出齊格切圖劃分標準，Ccut的表達式如下[15]：

其中，|A|表示集合A中數(shù)據(jù)樣本的數(shù)目。齊格切通過最小化表達式（3）的值來得到無向圖的最優(yōu)圖劃分結果，即簇內數(shù)據(jù)樣本之間的相似度最大，簇間數(shù)據(jù)樣本之間的相似度最小。但是根據(jù)Rayleigh商原則，計算無向圖齊格切的最優(yōu)劃分結果是一個NP-難題[16]。接下來，將通過在譜聚類算法中引入p-Laplacian算子來近似得到齊格切的最優(yōu)劃分結果。

Heigh等人定義了p-Laplacian算子的內積形式，其表達式如下：

其中，p∈(1,2]；f是p-Laplacian矩陣的特征向量。

定理1對于任意p＞1以及頂點集合V的每一劃分A和Aˉ，都存在一個與p-Laplacian矩陣相關的函數(shù)Fp(f,A)滿足[17]：

表達式（5）可以被看作一個具有較強平衡性的圖劃分標準，并且可以進一步得到：

由定理1可得，利用p-Laplacian算子，齊格切的最優(yōu)劃分可以在多項式時間內被計算得到。因此Fp(f)的解決方法是齊格切的一個近似最優(yōu)解，以及最優(yōu)解可以通過p-Laplacian矩陣的譜分解獲得。

其中，λp是特征向量f對應的特征值。

特別的，通過p-Laplacian矩陣的第二小特征向量以及設定合適的閾值，可以對無向圖進行二路劃分。選擇最優(yōu)的閾值是能夠最小化對應齊格切目標函數(shù)值的。對于p-Laplacian矩陣的第二小特征向量，其閾值應該滿足：

3 局部相似性優(yōu)化的p-譜聚類算法

3.1 局部相似性測度的優(yōu)化

聚類算法中，對數(shù)據(jù)樣本之間局部相似性的求解是一個復雜的過程。根據(jù)數(shù)據(jù)樣本集合X={x1,x2,…,xn}，首先定義一個數(shù)據(jù)樣本矩陣X∈Rn×d，然后對每個數(shù)據(jù)樣本確定其第k近鄰點。本文首先把數(shù)據(jù)樣本集合X中的數(shù)據(jù)樣本均看作xi的近鄰點，并使用歐氏距離來表示相似性[18]，局部相似性用sij表示。通常，如果兩個數(shù)據(jù)樣本之間的歐氏距離較小，則表示兩者之間具有較大的相似性另外，每個數(shù)據(jù)樣本均可看作數(shù)據(jù)樣本xi的相鄰點，且具有相同的局部相似性可看作每個數(shù)據(jù)樣本進行近鄰分配的預操作。因此存在一種表示數(shù)據(jù)樣本之間局部相似性的方法，滿足下述表達式：

其中，si∈Rn×1表示向量，si的第j個元素表示數(shù)據(jù)樣本i和j之間的局部相似性sij；γ是正則化參數(shù)；定義是特征向量，的第j個元素表示然后表達式（9）可被進一步轉化為向量形式，其描述如下：

對于每個數(shù)據(jù)樣本xi，可以使用表達式（9）為其分配近鄰點。因此，可以通過表達式（11），為所有數(shù)據(jù)樣本分配近鄰點：

在理想情況下對數(shù)據(jù)樣本進行近鄰分配時，可以得到無向圖G中連通分量的數(shù)目精確地等于聚類數(shù)目c。然而，通常情況下在使用表達式（11）進行近鄰分配時，對于任意的γ值，很難實現(xiàn)都能在理想情況下進行分配。并且在大多數(shù)情況下，數(shù)據(jù)樣本集合中所有數(shù)據(jù)樣本只組成一個連通分量。為了實現(xiàn)在理想情況下進行近鄰分配，表達式（11）的局部相似性應該被約束，以便于近鄰分配能夠變成一個數(shù)據(jù)樣本自適應的過程，使得連通分量的數(shù)目精確地等于聚類數(shù)目c。因為這種對局部相似性的結構約束是根本性的難題，而且操作起來也是十分困難的，所以實現(xiàn)這種約束看起來像是一個不可實現(xiàn)的目標。本文將提出一個新穎而又簡單的算法來實現(xiàn)這個目標。

近鄰分配后，S∈Rn×n被定義為相似性矩陣。假設每個頂點用函數(shù)fi∈Rc×1表示，則下述等式是正確的：

其中，F(xiàn)∈Rn×c，第i行等于fi。在圖論中被定義為拉普拉斯矩陣，Ds∈Rn×n被定義為度矩陣，其第i行對角元素等于

如果相似性矩陣S是非負的，則對應拉普拉斯矩陣具有下述主要特性[20]。

定理2拉普拉斯矩陣Ls中，其特征值為0的數(shù)目c等于對應無向圖G中連通分量的數(shù)目。

根據(jù)上述定理如果rank(Ls)=n-c，則表明近鄰分配可在理想情況下進行，同時根據(jù)相似矩陣S能夠成功把數(shù)據(jù)樣本劃分到c個簇中，并且在聚類過程中沒有使用到k-means以及其他聚類算法。由定理2可知，可以把rank(Ls)=n-c看作約束條件添加到表達式（11）所描述的問題中來實現(xiàn)理想情況下的近鄰分配。因此本文聚類算法可以解決下述表達式（13）需要解決的問題，表達式描述如下：

假設σi(Ls)表示拉普拉斯矩陣Ls的第i小特征值，由于Ls是半正定矩陣，故σi(Ls)≥0。對于一個足夠大的數(shù)值λ，表達式（15）描述的問題可用表達式（14）表示：

當λ的值足夠大時，已知σi(Ls)≥0，表達式（14）只要使趨于零就可以得到最優(yōu)解S。

根據(jù)Ky Fan的理論分析[21]，有：

因此表達式（14）可以進一步轉化為表達式（15），描述如下：

相對于原始表達式（13），表達式（15）更容易去解決。本文可以從下述選擇一種最優(yōu)的方法來解決問題。

當相似矩陣S不變時，則表達式（15）描述如下：

當F不變時，則表達式（15）描述如下：

根據(jù)表達式（11），表達式（17）可轉化為：

在表達式（18）中，每一個i都是相互獨立的，因此對于i，可得下述表達式（19），描述如下：

由上述分析可知，得到相似矩陣S的算法1如下。

算法1計算相似矩陣S

輸入：數(shù)據(jù)樣本矩陣X∈Rn×d，聚類數(shù)目c，正則化參數(shù)γ，一個足夠大的數(shù)值λ。

輸出：具有c個連接部分的相似矩陣S∈Rn×n。

使用表達式（11）的最優(yōu)解對S進行初始化；

如果不收斂，則：

（1）更新F。F由拉普拉斯矩陣的前c個最小特征值對應的特征向量組成；

（2）對于每個i，使用表達式（19）的最優(yōu)解來更新相似矩陣S的第i行，其中di∈Rn×1為特征向量，其第j行元素等于

終止。

3.2 確定正則化參數(shù)γ的值

在實際情況下，由于正則化參數(shù)的取值范圍是從零到無窮大，故對其進行訓練確定值大小是非常困難的。本文提出一種有效的方法來間接確定正則化參數(shù)γ的值。

對于每個樣本數(shù)據(jù)i，表達式（13）中的目標函數(shù)等價于表達式（10）中的目標函數(shù)，表達式（10）的拉格朗日函數(shù)表達式（21）描述如下：

其中，η和βi≥0是拉格朗日乘子。

根據(jù)KKT條件[22]，可以證實最優(yōu)解si的表達式（22）可描述如下：

當實際算法運行時，如果進一步考慮數(shù)據(jù)樣本的局部相似性，將會獲得較好的聚類效果。因此，一般情況下更傾向于只考慮xi的k個最近鄰，從而可以得到稀疏矩陣si；另一方面，聚類算法中使用稀疏矩陣還可以緩解設備的運算負擔。

根據(jù)等式（22）和約束條件sTi1=1，有：

因此根據(jù)等式（23）和（24）可得關于γi的不等式如下：

在已知表達式（9）具有k個非零值的情況下，為了得到最優(yōu)解si，γi可以用表達式（26）表示，描述如下：

對于γ的值等于γ1,γ2,…,γn的平均值，也就是說，γ可以用下述表達式（27）表示：

由于近鄰數(shù)k是一個整數(shù)并且具有明確的實際意義，相對于γ，k是更容易通過訓練得到的。

3.3 局部相似性優(yōu)化的p-譜聚類算法

算法通過計算數(shù)據(jù)樣本與最優(yōu)近鄰之間的局部距離來優(yōu)化相似性矩陣，同時利用p-Laplacian矩陣的秩約束條件，使最終得到的矩陣中連通部分的數(shù)目精確等于聚類數(shù)目，從而進一步實現(xiàn)聚類效果的優(yōu)化。它的主要思想是：首先根據(jù)優(yōu)化后的局部相似性測度方法來計算數(shù)據(jù)樣本之間的相似度，得到相似矩陣；接著計算p-Laplacian矩陣的特征值和特征向量，并遞歸地使用二分法進行劃分來最優(yōu)化目標函數(shù)；最終獲得更好的聚類結果。

算法2優(yōu)化的p-譜聚類算法

輸入：數(shù)據(jù)樣本集合X∈Rn×d，聚類數(shù)目c，正則化參數(shù)γ，一個足夠大的數(shù)值λ。

輸出：c個類C1,C2,…,Cc。

（1）根據(jù)算法1可得相似性矩陣S；

（2）初始化聚類C1=V,聚類數(shù)目s=1；

（3）重復步驟（3）～（7）；

（4）對每個類Ci(i=1,2,…,s)，最小化目標函數(shù)Fp(f)；

（5）對非規(guī)范化矩陣或規(guī)范化矩陣求解最優(yōu)邊值，從而得到圖劃分標準齊格切判據(jù)的近似解；

（6）利用圖切判據(jù)的最小目標函數(shù)對Ci(i=1,2,…,s)進行分割；

（7）s?s+1；

（8）s==c時，循環(huán)結束，并輸出聚類結果；

（9）利用聚類結果進一步得出衡量算法優(yōu)越性的Ncut值。

4 實驗仿真與結果分析

本文為了分析基于局部相似性優(yōu)化的p-譜聚類算法的聚類效果，分別選取了4個人工數(shù)據(jù)集和兩個模式識別測試數(shù)據(jù)集（簡稱UCI）進行實驗，并與原p-譜聚類算法的聚類效果進行對比，從而體現(xiàn)基于局部相似性優(yōu)化的p-譜聚類算法的優(yōu)越性。實驗過程中為了方便分析算法的優(yōu)越性，p值始終保持不變。實驗的計算機環(huán)境為：Intel Core i5-2450M 2.5 GHz CPU，內存6 GB,Windows 8.1 64位操作系統(tǒng)，運行平臺為Matlab R2014a。

人工數(shù)據(jù)集是根據(jù)聚類需要進行人工合成的，一般情況下都具有相對復雜或者較為獨特的數(shù)據(jù)結構，例如凸形結構、流形結構和多維結構等。一般的聚類算法往往都只能解決其中的少數(shù)問題，人工數(shù)據(jù)集對算法的要求非常嚴格，具有較強的挑戰(zhàn)性。因此，可以通過對比原p-譜聚類算法和基于局部相似性優(yōu)化的p-譜聚類算法在人工數(shù)據(jù)集上的聚類效果來分析后者的優(yōu)越性與有效性。本文選取的4個人工數(shù)據(jù)集為Twomoon、Threecircle、Smile、Fourline，其特征如表1所示，其可視化分布如圖1所示。

Table 1 Characteristics of artificial data sets表1 人工數(shù)據(jù)集及其數(shù)據(jù)特征

為了進一步驗證基于局部相似性優(yōu)化的p-譜聚類算法的優(yōu)越性，從UCI數(shù)據(jù)集庫選擇兩個真實的數(shù)據(jù)集進行實驗。本文選取的兩個數(shù)據(jù)集都是具有明確分類結果的，其具體特征如表2所示。

Table 2 Characteristics of UCI data sets表2 UCI數(shù)據(jù)集及數(shù)據(jù)特征

以上分別對4個人工數(shù)據(jù)集Twomoon、Threecircle、Smile、Fourline和兩個UCI數(shù)據(jù)集Wine和USPS進行了描述和分析。接下來，分別使用原p-譜聚類算法和基于局部相似性優(yōu)化的p-譜聚類算法對人工數(shù)據(jù)集和UCI數(shù)據(jù)集進行實驗。為了驗證算法的一般性，首先對4個人工數(shù)據(jù)集進行聚類，兩種聚類算法的效果如圖2所示，（a）表示數(shù)據(jù)集Twomoon的聚類效果，（b）表示數(shù)據(jù)集Threecircle的聚類效果，（c）表示數(shù)據(jù)集Smile的聚類效果，（d）表示數(shù)據(jù)集Fourline的數(shù)據(jù)效果。

從圖2中可以看出，對于人工數(shù)據(jù)集，相對原p-譜聚類算法，基于局部相似性優(yōu)化的p-譜聚類算法可以獲得更好的聚類效果。

Fig.1 Distribution of artificial data sets圖1 人工數(shù)據(jù)集的分布

Table 3 Ncutvalue of two algorithms on artificial data sets表3 兩種算法在人工數(shù)據(jù)集得出的Ncut值

在本文實驗中，根據(jù)第2章中圖劃分標準規(guī)范切和最終的聚類結果可以得出Ncut值，其大小能夠作為衡量算法優(yōu)越性的標準，即Ncut值越小，則算法越具有優(yōu)越性、有效性。表3給出了兩種聚類算法分別在4個人工數(shù)據(jù)集Twomoon、Threecircle、Smile、Fourline的Ncut值。

表3中，第一行數(shù)據(jù)表示原p-譜聚類算法在4個人工數(shù)據(jù)集上聚類后，得出的Ncut值，第二行數(shù)據(jù)表示基于局部相似性優(yōu)化的p-譜聚類算法在4個人工數(shù)據(jù)集上聚類后，得出的Ncut值。從表中可以看出，對于人工數(shù)據(jù)集，后者的Ncut值明顯小于前者，故基于局部相似性優(yōu)化的p-譜聚類算法產生更好的聚類效果。

通過上述對人工數(shù)據(jù)集進行實驗與分析，驗證了本文的譜聚類算法的有效性。接下來，將使用兩種聚類算法進一步對兩個UCI數(shù)據(jù)集Wine和USPS進行聚類。

表4給出了兩種聚類算法分別在兩個UCI數(shù)據(jù)集Wine和USPS上的Ncut值。

Table 4 Ncutvalue of two algorithms on UCI data sets表4 兩種算法在UCI數(shù)據(jù)集得出的Ncut值

Fig.2 Clustering results of two algorithms on artificial data sets圖2 兩種聚類算法在人工數(shù)據(jù)集的聚類效果

表4中，第一行數(shù)據(jù)表示原p-譜聚類算法在兩個UCI數(shù)據(jù)集上聚類后，得出的Ncut值，第二行數(shù)據(jù)表示基于局部相似性優(yōu)化的p-譜聚類算法在兩個UCI數(shù)據(jù)集上聚類后，得出的Ncut值。從表中可以看出，對于UCI數(shù)據(jù)集，后者的Ncut值明顯小于前者，故基于局部相似性優(yōu)化的p-譜聚類算法產生更好的聚類效果。

經過上述實驗仿真和結果分析可知，基于局部相似性優(yōu)化的p-譜聚類算法具有更好的優(yōu)越性和有效性。

5 結束語

本文提出了一種基于局部相似性優(yōu)化的p-譜聚類算法。該算法通過數(shù)據(jù)樣本的自適應和最優(yōu)近鄰之間的局部距離來優(yōu)化相似性測度的計算方法，同時通過引入p-Laplacian矩陣的秩約束，可以得到聚類過程中無向圖G中連通分量的數(shù)目精確地等于聚類數(shù)目，從而有效地解決了原p-譜聚類算法中不能充分挖掘數(shù)據(jù)集的局部結構信息和相似性矩陣的計算與數(shù)據(jù)樣本的聚類分別在兩個不同的步驟中實現(xiàn)，導致有可能得不到最優(yōu)聚類效果的問題。為了驗證基于局部相似性優(yōu)化的p-譜聚類算法的優(yōu)越性和有效性，在本文實驗中，采用了4個人工數(shù)據(jù)集和兩個UCI數(shù)據(jù)集分別進行實驗，并且將聚類效果與原p-譜聚類算法的聚類效果進行了對比。從實驗仿真與結果分析中可知，基于局部相似性優(yōu)化的p-譜聚類算法具有更好的優(yōu)越性和有效性。接下來的工作是通過分析研究特征向量的結構信息來自動確定數(shù)據(jù)集的聚類數(shù)目，從而獲得更好的聚類效果。

[1]Johnson S C.Hierarchical clustering schemes[J].Psychometrika,1967,32(3):241-254.

[2]MacQueen J.Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability,Berkeley,1965.Berkeley:University of California Press,1967:281-297.

[3]Benhur A.Support vector clustering[J].Journal of Machine Learning Research,2002,2(2):125-137.

[4]Nie Feiping,Xu Dong,Li Xuelong.Initialization independent clustering with actively self-training method[J].IEEE Transactions on Systems,Man and Cybernetics:Part B,2012,42(1):17-27.

[5]Cai Xiao,Nie Feiping,Huang Heng.Multi-viewK-means clustering on big data[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence,Beijing,Aug 3-9,2013.Menlo Park:AAAI,2013:2598-2604.

[6]Jia Hongjie,Ding Shifei,Xu Xinzheng,et al.The latest research progress on spectral clustering[J].Neural Computing&Applications,2014,24(7/8):1477-1486

[7]Zhang Xianchao,You Quanzeng.An improved spectral clustering algorithm based on random walk[J].Frontiers of Computer Science in China,2011,5(3):268-278.

[8]Jia Hongjie,Ding Shifei,Meng Lingheng,et al.A densityadaptive affinity propagation clustering algorithm based on spectral dimension reduction[J].Neural Computing&Applications,2014,25(7/8):1557-1567.

[9]Bühler T,Hein M.Spectral clustering based on the graphp-Laplacian[C]//Proceedings of the 26th Annual International Conference on Machine Learning,Montreal,Jun 14-18,2009.New York:ACM,2009:81-88.

[10]Zelnik-Manor L,Perona P.Self-tuning spectral clustering[C]//Proceedings of the 2004 Conference on Neural Information Processing Systems,Vancouver,Dec 13-18,2004:1601-1608.

[11]Jia Hongjie,Ding Shifei,Du Mingjing.Self-tuningp-spectral clustering based on shared nearest neighbors[J].Cognitive Computation,2015,7(5):622-632.

[12]Nie Feiping,Wang Xiaoqian,Huang Heng.Clustering and projected clustering with adaptive neighbors[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,Aug 24-27,2014.New York:ACM,2014:977-986.

[13]Donath W E,Hoffman A J.Lower bounds for the partitioning of graphs[J].IBM Journal of Research&Development,1973,17(5):420-425.

[14]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2000,22(8):888-905.

[15]Amghibech S.Bounds for the largestp-Laplacian eigenvalue for graphs[J].Discrete Mathematics,2006,306(21):2762-2771.

[16]Ding Shifei,Jia Hongjie,Zhang Liwen,et al.Research of semi-supervised spectral clustering algorithm based on pairwise constraints[J].Neural Computing&Applications,2014,24(1):211-219.

[17]Hagen L,Kahng A.Fast spectral methods for ratio cut partitioning and clustering[C]//Proceedings of the 1991 International Conference on Computer-Aided Design,Santa Clara,Nov 11-14,1991.Piscataway:IEEE,1991:10-13.

[18]Ding Shifei,Jia Hongjie,Du Mingjing,et al.p-spectral clustering based on neighborhood attribute granulation[C]//Proceedings of the 9th IFIP TC 12 International Conference on Intelligent Information Processing,Melbourne,Nov 18-21,2016.Berlin,Heidelberg:Springer,2016:50-58.

[19]Shi Jianbo,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[20]Hein M,Audibert J Y,Luxburg U V.Graph Laplacians and their convergence on random neighborhood graphs[J].Journal of Machine Learning Research,2007,8(9):1325-1370.

[21]Ding Shifei,Qi Bingjuan,Jia Hongjie,et al.Research of semi-supervised spectral clustering based on constraints expansion[J].Neural Computing&Applications,2012,22(1):405-410.

[22]Boyd S,Vandenberghe L.Convex optimization[M].Cambridge:Cambridge University Press,2004.