一種基于混合特征選擇的圖聚類算法

張 壽,龐 俊,2,廖明習

1(武漢科技大學 計算機科學與技術學院,武漢 430065)

2(智能信息處理與實時工業系統湖北省重點實驗室,武漢 430065)

3(武漢理工大學 計算機與人工智能學院,武漢 430070)

0 引 言

圖是一種表示模型,其中節點表示對象,邊表示對象的關系.圖聚類旨在將多個圖(或將單個圖的頂點)進行分組,使得組內的圖(或頂點)越相似越好,組間的圖(或頂點)越不相似越好.圖聚類是圖分析的一項基本工作,近幾年成為研究熱點之一[1-3].

現有的圖聚類方法根據對象的不同分為兩大類:單個大圖的聚類(簡稱大圖聚類)和多個中小規模圖的聚類(簡稱多個圖聚類).大圖聚類是對單個大圖中的節點進行聚類,其現有算法根據圖數據是否改變分為靜態算法和動態算法兩大類[4].靜態算法根據節點能否屬于不同類簇又可分為非重疊算法和重疊算法.現有大圖聚類方法常用技術包括:標簽傳播、圖分割、劃分、非負矩陣分解和馬爾可夫鏈等等.此外,深度學習技術和演化計算技術也日趨成為解決大圖聚類的重要手段.目前大圖聚類相關研究比較成熟,而多個圖的聚類算法研究尚未引起圖數據管理和分析領域足夠的重視.因此本文對多個中小規模圖的聚類方法展開研究.

多個圖的現有聚類方法主要分為3類:基于距離的方法[5]、基于深度學習的方法[6-8]和基于子結構的方法[9].第1類方法通過計算圖間距離(如圖編輯距離[10])比較圖的相似性,進行劃分聚類.該類方法需要多次計算圖之間的距離,而圖的距離計算非常復雜;第2類方法先采用深度神經網絡自動提取特征,從而將整個圖進行嵌入表示并聚類.該類方法雖然聚類效果較好,但因“黑盒”提取特征,可解釋性偏弱,不適用于對可解釋性有較高要求的場景[11].本文針對需要強可解釋性的醫療場景展開研究,故未研究該類方法;第3類方法以從圖數據集挖掘出的頻繁子結構指導圖的聚類.以頻繁子結構為特征,將圖數據表示為0-1向量,然后使用常用的聚類方法進行圖的聚類.這類方法存在所選特征失效或重要特征丟失的問題.因為有效特征未必頻繁[12],所以可能選擇一些對聚類結果沒有任何幫助的頻繁子結構作為最終特征,或漏選一些非常重要的非頻繁子結構.此外,頻繁度閾值需要通過實驗確定,且特定數據集的頻繁度閾值不一定適用于其他數據集.下文列舉一個所選特征失效或重要特征丟失的示例.

例1.已知圖數據集D包括圖G1～G5,如圖1所示.圖G1、G2、G3、G5構成分組Cluster1,G4構成分組Cluster2.子圖f1～f7被各圖包含情況如表1所示.其中,圖G1～G5均包含f1和f2,只有G4包含f3.顯然,子圖f1和f2因頻繁被選為特征;但是f1和f2也是無效的聚類特征,因為它們被Cluster1和Cluster2的所有圖包含,對區分圖數據屬于哪個組并無幫助.此外,f3只被Cluster2的每個圖所包含,未被Cluster1的任意圖包含,因此對分組有重要作用,但是由于非頻繁并未被選為特征,造成重要特征丟失.

表1 例1子圖包含統計信息Table 1 Statistics of subgraph contain of example 1

圖1 特征失效和丟失的示例圖Fig.1 Example diagram of feature invalidation and loss

因此本文研究工作主要面臨兩大挑戰:

1.如何定義并挖掘比頻繁子結構更有價值的特征子圖?既然頻繁子結構非最佳選擇,那么應該選哪些子圖作為特征、并進行挖掘呢?

2.由于子圖挖掘過程計算非常復雜,因此如何快速地挖掘出更大價值子圖也是一個挑戰.

針對第1個挑戰,采用區分子圖作為特征.根據PCA原理,挖掘的區分子圖應具有以下特點:屬于不同組別的圖所包含的區分子圖差異性越大越好.于是,提出一種評估函數,然后提出一種基于該評估函數的區分子圖評估模型,接著將查找k個區分子圖的問題轉化為挖掘k個最有價值的區分子圖問題(k是給定的參數),并求解該問題.

區分子圖在圖分類和圖半監督學習已有應用,并已取得了比Baseline方法更高的準確率[12].但這些方法要求圖數據集包含的所有圖均具有類標簽或部分圖數據具有類標簽,與本文的問題設置不一致.

針對第2個挑戰,本文提出了一種分支定界方法,通過剪枝加速子圖的挖掘過程.在子圖搜索過程中如子圖的分值小于上界值,則對包含該子圖的子樹進行過濾,能有效加快區分子圖的挖掘.

本文首先基于上述工作提出了一種基于過濾式特征選擇的基本圖聚類算法BGCA(Basic Graph Clustering Algorithm),然后在此基礎上提出一種基于混合式特征選擇的改進算法.BGCA算法首先基于提出的區分子圖評價函數挖掘區分子圖,并提出一種分支定界策略加速區分子圖的挖掘過程;然后以區分子圖作為特征,將圖表示為0-1向量;最后采用常用的聚類算法完成圖聚類.為了進一步提高聚類準確率,改進算法在將圖表示為向量后,不失一般性地選擇了一種嵌入式特征選擇方法DGUFS(Dependence Guided Unsupervised Feature Selection),進一步對特征進行選擇并同時實現圖聚類.通過真實數據集上的實驗對本文提出的圖聚類算法的有效性進行了驗證.

綜上所述,本文的主要貢獻如下:

1.本文提出了一種基于過濾式特征選擇的基本圖聚類算法.該算法采用提出的特征評估函數挖掘出比頻繁子圖更有價值的區分特征子圖.此外,基于分支定界策略進行剪枝,加速區分子圖的挖掘過程.

2.本文提出了一種改進的基于混合式策略的圖聚類算法,提高了聚類準確率.首先采用過濾式方法挖掘區分子圖,并將圖表示為0-1向量;然后在上一步基礎上,選擇一種嵌入式特征選擇方法進一步過濾并實現圖聚類.

3.真實數據集上的實驗驗證了本文提出的基于混合特征選擇的圖聚類算法的有效性.

1 相關工作

本文相關工作主要包括大圖聚類,多個圖聚類,特征選擇.

1.1 大圖聚類

大圖聚類被廣泛研究,根據大圖是否隨時間改變分為靜態方法和動態方法[4].現有靜態方法非常豐富[13-25],根據同一個節點是否屬于不同組別又可分為非重疊聚類方法和重疊聚類方法.動態方法也有一些,尚處發展階段[4].

非重疊靜態聚類方法要求同一個節點只屬于某一個組.其中典型方法例如:Halim等人[16]提出了一種基于密度的聚類方法,將不確定的數據表示為概率圖,計算圖的結點以及鄰域的密度指導聚類.因計算過程較簡單,基于密度的方法比基于劃分的方法更快.Liu等人[17]針對大規模網絡難以了解網絡全局結構的問題,提出了一種基于模糊相似關系和最大連通子圖的局部社區發現算法.該算法只需借助鄰居節點的關系發現目標節點所在社區.Zheng等人[22]提出了一種圖卷積網絡增強的非線性非負矩陣分解社區發現算法.為了使算法具有非線性特征表示能力,還提出了一種聯合優訓練方法.雖然該算法能有效處理非線性特征復雜網絡,但其運行效率有待進一步提高.

重疊靜態聚類方法允許同一個節點屬于不同組別.其中典型算法例如:Jia等人[24]提出了一種基于標簽傳播的重疊社區發現算法.該算法采用同步的方式在以邊緣節點為中心的橋梁節點群內進行標簽傳播.此外引入節點連接社區強度,以降低標簽更新過程的隨機性.Zhao等人[25]提出了一種基于網絡嵌入和標簽傳播的異構信息網絡重疊社區發現算法.該算法采用通過網絡嵌入技術和加權融合技術改進的節點相似性指導標簽傳播.此外,為了加速標簽傳播過程,提出了一種鄰居節點影響力的節點排序方法.

此外,還有一些針對屬性圖和有向圖的聚類方法.Bu等人[26]提出了一種面向屬性圖的聚類方法.該算法采用動態類簇和博弈技術,不需指定分組的組數.Chen等人[27]提出的有向圖聚類算法采用核非負矩陣分解技術,考慮了節點間的非線性相關性,能準確揭示潛在結構信息.

本文旨在研究多個中、小規模圖的聚類.因問題設置不同,現有大圖聚類方法不能用來解決本文研究的多個中小規模圖的聚類問題.

1.2 多個圖聚類

現有多個圖的聚類方法主要分為3類:基于距離的方法[5]、基于深度學習的方法[6-8]和基于子結構的方法[9].

基于距離的方法通過圖距離(如圖編輯距離)的計算比較圖的相似性,從而實現聚類.該類方法需要進行多次計算復雜的圖距離計算.基于深度學習的圖聚類方法,采用了神經網絡自動學習圖的嵌入表示.例如:Bai等人[6]提出了一種端到端的神經網絡框架,使圖的嵌入表示保留了圖的鄰近性.Sun等人[7]提出了一種新方法,能最大化圖嵌入表示和不同尺度的子結構表示(例如:節點、邊、三角形)之間的相互信息.Xu等人[8]提出了一種統一學習框架,用于自監督圖表示學習.除了保留局部的相似性之外,還引入了分層原型來捕獲全局語義集群.基于深度學習的圖聚類方法雖然聚類效果較好,但普遍存在可解釋性不足的問題.基于子結構的方法借助從圖數據集挖掘出的頻繁子結構完成圖聚類,具有較強的可解釋性以及較好的聚類性能.挖掘頻繁特征子結構,將圖數據表示為0-1特征向量,然后使用常用的聚類方法實現圖聚類.Aggarwal等人[9]提出了一種XML聚類算法,該算法使用文檔包含的子結構,獲取重要的底層結構信息.然后使用多個頻繁子結構來指導XML文檔的聚類.這類方法因采用頻繁子結構作為特征,存在所選特征失效或重要特征丟失的問題.

本文選擇需要強可解釋性的醫療應用場景,開展了基于嵌入和子結構的圖聚類算法的研究,采用了非深度學習技術,挖掘區分特征子圖,所提出的方法兼有較好的可解釋性和較好的聚類性能.

1.3 特征選擇

本文基于傳統的特征選擇方法進行子圖特征選擇,然后完成多個圖的聚類.現有特征選擇方法主要包括:過濾式、包裹式和嵌入式3類.

過濾式特征選擇方法與學習算法無關,依靠對特征打分評估特征的重要性[12,28].Kong等人[12]提出了一種半監督圖分類算法,挖掘子圖中的區分子圖并作為特征.區分子圖評價標準是基于有標簽和無標簽樣本.包裹式特征選擇方法依賴于預定義的預測性能學習算法來評估所選特征的質量[29].過濾式特征選擇方法效率比較高,但是所選特征不一定適合后續學習算法.包裹式特征選擇依賴于學習算法選擇特征子集,特征維度高時,計算相對復雜.嵌入式方法提供了過濾式方法和包裹式方法之間的折衷解決方案,將特征選擇嵌入模型構建過程[30,31].Guo等人[30]提出了無監督嵌入式特征選擇DGUFS,在對數據進行聚類的同時完成了特征選擇,該方法增強了原始數據、被選特征和聚類標簽之間的相關性,得到了更好的結果.

為了兼具過濾式和嵌入式方法的優點,本文提出了一種混合式特征選擇策略:先提出了一種過濾式特征選擇方法;然后不失一般性地引入嵌入式特征選擇方法DGUFS實現進一步特征選擇和聚類,進一步提高圖聚類的質量.

2 方 法

首先介紹了提出的解決圖聚類問題的基本方法,然后采用嵌入式特征選擇算法進行改進.

2.1 基本方法

本節介紹提出的基本方法BGCA,其基本思想是:從圖數據中挖掘區分子圖作為特征,利用特征將圖表示為向量,然后采用傳統的聚類方法達到聚類的目的.

BGCA算法的數據流圖如圖2所示,其主要步驟是:1)提出一種過濾式特征選擇方法挖掘區分子圖;2)基于第1步的結果,將圖轉換為0-1向量;3)采用流行的劃分方法實現聚類.第1步提出一種區分子圖評價函數,然后在挖掘子圖的過程中,采用提出的區分子圖的評價函數對子圖進行評分,并選取分值較高的k個子圖作為特征.k是參數,需要通過實驗進行設定.此外,為了加速區分子圖的挖掘過程,提出了一種分支定界技術;第2步將選擇出的區分子圖作為特征,把各個圖數據分別表示為0-1向量.如果圖G包含目標特征,則G對應向量的分量為1;否則為0;第3步,由于圖數據已經表示為向量,故只需采用現有流行的聚類算法就能完成圖數據的聚類任務.下文將分別展開介紹上述3個步驟.

圖2 BGCA算法的數據流圖Fig.2 Data flow diagram of BGCA

2.1.1 挖掘區分子圖

1)評價函數

區分子圖是能區分屬于不同組別的圖數據的子圖.在介紹挖掘區分子圖的評價模型之前,先定義幾個符號,如表2所示.

表2 符號定義Table 2 Definition of symbols

接著提出了一種區分子圖評價模型,如式(1)所示.給定k值,選擇區分能力最強的k個子圖.其中,F( )是評價T總區分能力的打分函數,|T|表示特征集的大小,k是所選特征的最大數量.

(1)

基于PCA的原理可知:不同組別圖數據所包含的區分子圖差異性越大越好.因此,設計一種函數F(T),如式(2)所示.

其中,DT是一個對角矩陣,表示從集合S中選擇哪些特征到T中.Du是圖的集合.

(2)

上述評價函數計算了無標簽樣品之間距離的平均值.若兩個樣本的距離越大,則評價函數值越大;說明差異較大,區分能力越好.直接使用式(1)和式(2)來求解最優區分子圖集合,計算復雜度非常高.因此,接下來通過化解,將求解最優子圖集的問題轉換為求k個單個最優子圖特征的問題.

化解前先定義輔助矩陣W,如式(3)所示.

(3)

根據式(3)重寫式(2),得到式(4).其中tr表示矩陣的跡,D為W的對角矩陣,L=D-W是拉普拉斯矩陣.

(4)

F(T)=∑gi∈T,1≤i≤kq(gi)

(5)

2)分支定界

基于gSpan算法[32]查找前k個得分最高的區分子圖.為了加速挖掘過程,提出一種分支定界技術.

(6)

證明：

所以u(g′)≤u(g)成立.

基于定理1,搜索DFS編碼樹時,若當前子圖的評分小于已挖掘出的前k個子圖的評分,那么當前子圖以及當前子圖的超圖都不符合要求被剪枝.

3)區分子圖挖掘算法

基于上述技術,提出了一種區分子圖挖掘算法.算法偽代碼如算法1所示.其主要步驟是:通過gSpan算法搜索圖的DFS編碼樹,搜索到當前子圖g時,若最佳子圖集合FT的基數小于k時,則直接將其添加到集合FT中;否則計算當前子圖的評分,并與集合中評分最小的子圖(該評分設為上界值)進行比較.若當前子圖評分較高,則刪除集合中最小評分子圖,添加當前子圖,并更新集合中最小評分設為上界值;若當前子圖評分小于集合上界值,則搜索其他子樹.由于gSpan的時間復雜度為O(2n×n2)[32],因此gMining時間復雜度也為O(2n×n2).n表示圖數據集中包含的圖的個數.

算法1.gMining (D,min_s,k)

輸入：圖形數據集D={G1,G2,…,Gn},最小支持閾值min_s,所選子圖特征的數量k

輸出：最佳子圖特征集FT

1.FT←?,θ←0//θ表示上界值

2. 遞歸訪問gSpan中的DFS編碼樹

3.g←DFS編碼中當前訪問的子圖樹

4. if |FT|

5.FT←FT∪{g}

6. else ifq(g)>min(q(g′))then //g′∈FT

7.FT←FT-{g′}//更新FT

8.FT←FT∪{g},θ←q(g′)

9. ifq(g)≥θandfreq(g)≥min_sthen

10. 深度優先搜索以其為根的子樹節點g

11. returnFT

2.1.2 BGCA算法

本節提出了基本的圖聚類算法BGCA:基于上一步挖掘出的區分子圖,將圖數據集中的每個圖數據分別表示為一個0-1向量,然后不失一般性,選擇一種劃分聚類算法完成聚類,如k-均值聚類算法.

算法2.BGCA

輸入：圖數據D,最小支持度min_s,所選子圖特征的數量k,聚類分組數k1

輸出：聚類結果Cr

1.FT←gMining(D,min_s,k)//最佳區分子圖集FT

2.DV←Fv(FT,D)//DV表示D根據FT生成的0-1向量集合

3. returnCr←K-means(k1,DV)//假設劃分聚類方法使用K-means

BGCA算法步驟如算法2所示.其中,向量化函數Fv(FT,D)根據FT將D中每個圖G轉化為0-1向量.該向量的維數和FT的基數相同.如G包含了gi∈FT,則第i維分量值為1;否則為0.K-means算法參數k1表示分組數.一個向量化示例如例2所示.

例2.已知圖數據集D={G1,G2,G3},獲得的區分子圖集合FT={f1,f2,f3}.每個圖包含區分子圖情況和其0-1向量表示如表3所示.

表3 圖數據向量化示例Table 3 Example of graph data vectorization

易知,算法2前2步的時間復雜度為O(2n×n2+n).剩余步驟的時間復雜度與采用的劃分算法有關.假設采用時間復雜度為O(n)的K-means算法,則BGCA算法時間復雜度為O(2n×n2+n+n)=O(2n×n2).n表示圖數據集中包含的圖的個數.

2.2 改進方法

雖然基本方法能夠使用提出的評價函數挖掘區分子圖,并采用分支定界策略加速挖掘過程,但是聚類準確率不夠高,不能完全滿足實際需求.因此,在采用圖特征表示方法將圖數據表示為0-1向量后,進一步進行特征選擇并聚類,以提高分類準確率.

由于嵌入式特征選擇方法能同時實現特征選擇和聚類,因此選擇采用它來實現特征的進一步選擇和圖數據的聚類.目前,流行的嵌入式特征選擇方法有很多種,包括EUFS,DGUFS[30],RUFS等算法.現有研究成果表明:DGUFS的聚類結果要優于其他嵌入式特征選擇方法[30,31].因此,不失一般性,采用DGUFS實現特征的再次選擇和圖數據的聚類.

如算法3所示,DGUFS算法使用了一種聯合特征選擇和聚類的學習框架,通過原始數據、被選特征、原始數據與被選特征之間的依賴關系以及被選特征與聚類標簽之間的依賴關系構建目標函數;基于目標函數,重復迭代計算被選特征與聚類標簽直至達到收斂,得到聚類結果.

算法3.DGUFS算法

輸入：數據矩陣X=[x1,x2,…,xn],被選擇的特征數量m,聚類分組數量c,每個樣本的最近鄰數量k

輸出：被選擇的特征Y和聚類標簽V

1. 計算相似性矩陣S

2. 初始化Y,L=VTVL=VTV

3. 根據目標函數重復迭代計算Y和L,直到達到收斂

4. 得到收斂時的結果Y,L

5. 分解L得到聚類結果V

3 性能評價

3.1 實驗設置

本節分別介紹實驗數據集、Baseline算法和評價標準.實驗采用圖聚類常用的兩個數據集進行實驗:呼吸癌數據MCF-7和肺癌數據NCI-H23.數據集統計信息如表4所示.

表4 實驗數據集統計信息Table 4 Statistics of experimental data set

本文將比較的方法包括:

·Baseline算法:據作者所知,目前采用非深度學習技術的最優的多個圖的聚類算法Xproj[9]作為本文的Baseline算法.該方法挖掘圖數據的頻繁子結構并將其作為特征,然后將每個圖表示為0-1特征向量,最后通過計算子結構的相似性對圖數據進行聚類.不失一般性,本實驗采用典型的K-means聚類算法完成聚類.

·本文提出的基本方法BGCA:該方法基于本文提出的區分子圖評價函數,挖掘區分子圖并將其作為特征;并且采用一種分支定界的策略減少搜索空間,加快區分子圖的挖掘過程.算法其余部分同Baseline算法.BGCA-U表示未使用分支定界的BGCA.

·本文提出的改進算法HFS-GC-D:在BGCA基礎上,該方法基于嵌入式特征選擇算法DGUFS,進一步進行特征選擇,并同時實現圖聚類.

采用常用的準確率(Accuracy,ACC)[12]和標準化互信息(Normalized Mutual Information,NMI)[26]作為圖聚類算法的性能評價指標.其計算方法如式(7)和式(8)所示.兩者值越大,對應圖聚類算法的性能越好.所有實驗隨機初始化20次,報道平均實驗結果.

(7)

其中,TF表示正確分組結果的數量之和,AF表示所有分組結果的數量之和.

(8)

其中,H(U)表示信息熵的值,MI(U,V)表示互信息計算.U表示實際的分組結果,V表示聚類結果.

(9)

(10)

其中pi表示歸屬第i類的數據占數據總量的比例.

3.2 結果分析

本節通過實驗對比,分析了本文提出的區分子圖挖掘方法、分支定界策略和混合式特征選擇方法的性能.

1)區分子圖的性能分析

在MCF-7和NCI-H23數據集上,分別比較了未使用分支定界的BGCA-U與Xproj算法的ACC和NMI.實驗結果如表5第1～2行所示.k表示區分子圖數量,min_s表示頻繁度閾值,c表示聚類分組數量.

表5 MCF-7和NCI-H23數據集上各算法的性能比較(k=50,min_s=0.15,c=2)Table 5 Performance comparison of algorithms on MCF-7 and NCI-H23 data sets

從表5第1～2行可見,在NCI-H23和MCF-7兩個真實數據集上,與Xproj算法相比,BGCA-U均具有更高的ACC和NMI.此實驗結果驗證了與頻繁子圖方法相比,區分子圖方法具有更好的聚類性能.一方面,區分子圖是根據PCA原理挖掘出的特征子圖,具有下述特點:屬于不同組的樣本中所包含的特征子圖應該不同.另一方面,不頻繁的子圖可能具有較好的區分能力,頻繁的子圖可能具有較差的區分能力[12].因此采用區分子圖作為特征,比采用頻繁子圖作為特征取得的聚類效果更好.

2)分支定界的性能分析

本小節在MCF-7和NCI-H23數據集上分別比較了BGCA和BGCA-U挖掘區分子圖的時間和聚類結果.其實驗結果分別如表5第2～3行和表所示.表5可見兩種方法的ACC和NMI一樣.因為分支定界策略只加快區分子圖挖掘的過程,并沒有改變挖掘結果.表6顯示BGCA的區分子圖挖掘時間比BGCA-U算法更短.由正文2.1.2小節可知,BGCA算法時間復雜度主要由挖掘區分子圖的時間決定;如果采用分支定界策略,減少子圖搜索空間,能加速區分子圖挖掘過程,從而使BGCA算法提速.

表6 MCF-7和NCI-H23數據集上BGCA-U與BGCA挖掘區分子圖的時間比較 (k=50,min_s=0.15,c=2)Table 6 Time comparison of mining discriminative subgraphs of BGCA-U and BGCA on MCF-7 and NCI-H23 datasets

3)混合特征選擇性能分析

在兩個真實數據集上分別比較了基本算法BGCA與改進算法HFS-GC-D的ACC和NMI.實驗結果如表5第3～4行所示.從表5第3～4行可見,在MCF-7和NCI-H23數據集上,與BGCA算法相比,HFS-GC-D算法均具有更高的ACC和NMI.因為HFS-GC-D算法采用混合式特征選擇方法,獲得的特征子圖比BGCA算法的更好,所以取得了更好的聚類性能.

4)算法參數性能分析

本小節在真實數據集上進行了實驗對比分析了不同區分子圖數量對聚類準確率的影響.為了分析不同區分子圖數量對聚類準確率的影響,選擇頻繁度閾值為0.15,c的值為2,在數據集MCF-7上進行實驗,實驗結果如圖3所示.

圖3 不同區分子圖數量下的聚類準確率Fig.3 Clustering accuracy under different numbers of discriminative subgraphs

從圖3可見,在MCF-7數據集上,隨著區分子圖數量的增加,HFS-GC-D與BGCA算法的聚類準確率在隨之增長.因為在一定范圍內,區分子圖的數量越多,相應的向量表示也越準確,所以聚類結果會更好.

4 結 論

本文提出了一種基于混合特征選擇的圖聚類算法.首先提出了一種評價模型,旨在挖掘區分能力最強的子圖集合;然后將該問題轉化為求解k個最有價值子圖問題.為了減少區分子圖搜索空間,設計了一種分支定界策略,提出了一種基本的圖聚類算法BGCA.為了進一步提高聚類準確率,在BGCA特征選擇基礎上,不失一般性選擇了一種流行的嵌入式特征選擇方法DGUFS,同時實現了進一步特征選擇和圖聚類.真實數據集上的實驗結果表明:本文提出算法的聚類準確率均高于Baseline方法.