基于核非負(fù)矩陣分解的有向圖聚類(lèi)算法

陳 獻(xiàn)，胡麗瑩*，林曉煒，陳黎飛，3

（1.福建師范大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院，福州 350117；2.數(shù)字福建環(huán)境監(jiān)測(cè)物聯(lián)網(wǎng)實(shí)驗(yàn)室（福建師范大學(xué)），福州 350117；3.福建省應(yīng)用數(shù)學(xué)中心（福建師范大學(xué)），福州 350117）

（?通信作者電子郵箱hlyxyz@fjnu.edu.cn）

0 引言

圖結(jié)構(gòu)可以自然地表示網(wǎng)狀結(jié)構(gòu)的數(shù)據(jù)，如社交網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、引文網(wǎng)絡(luò)、運(yùn)輸網(wǎng)絡(luò)、蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)［1］等。隨著各個(gè)領(lǐng)域網(wǎng)絡(luò)數(shù)據(jù)的增長(zhǎng)以及對(duì)網(wǎng)絡(luò)數(shù)據(jù)處理的迫切需求，分析圖結(jié)構(gòu)以及挖掘圖結(jié)構(gòu)中的關(guān)系信息成為了熱點(diǎn)問(wèn)題，圖聚類(lèi)［2］是其中的一項(xiàng)基礎(chǔ)研究課題。圖聚類(lèi)根據(jù)節(jié)點(diǎn)及節(jié)點(diǎn)間連接關(guān)系的相似性將節(jié)點(diǎn)劃分為簇，使得簇內(nèi)節(jié)點(diǎn)相似度較高，簇間的節(jié)點(diǎn)則差異較大。

目前已提出多種圖聚類(lèi)算法，包括基于圖分割的算法［3］、層次聚類(lèi)算法［4］、譜聚類(lèi)算法［5］等，這些算法大多忽視節(jié)點(diǎn)連邊的方向性，把有向圖轉(zhuǎn)化為有無(wú)向圖進(jìn)行處理。對(duì)于有向網(wǎng)絡(luò)如引文網(wǎng)絡(luò)、基因轉(zhuǎn)移網(wǎng)絡(luò)、運(yùn)輸網(wǎng)絡(luò)等，若以無(wú)向圖方式處理將丟失有用信息甚至引發(fā)歧義。例如，對(duì)于由文獻(xiàn)間引用和被引用關(guān)系構(gòu)成的引文網(wǎng)絡(luò)，當(dāng)看作無(wú)向圖時(shí)，將出現(xiàn)文獻(xiàn)間僅存在的單方面引用關(guān)系變成同時(shí)包含引用和被引用雙向關(guān)系的錯(cuò)誤情形。為有效建模節(jié)點(diǎn)間連接關(guān)系的方向性，目前典型的方法是將無(wú)向圖聚類(lèi)算法推廣到有向圖，如Satuluri 等［6］提出的轉(zhuǎn)換有向圖為無(wú)向加權(quán)圖的方法，通過(guò)有向圖上非對(duì)稱(chēng)鄰接矩陣隨機(jī)游走對(duì)稱(chēng)化或節(jié)點(diǎn)的入度和出度對(duì)稱(chēng)化手段來(lái)構(gòu)造新的對(duì)稱(chēng)鄰接矩陣，但這種方法可能導(dǎo)致有向圖上某些獨(dú)特的邊方向性信息丟失?；贚aplacian 矩陣的多種譜聚類(lèi)算法［7-9］則將聚類(lèi)目標(biāo)函數(shù)擴(kuò)展到有向圖中，并對(duì)得到的拉普拉斯矩陣做特征值分解；但該矩陣的特征值可能存在負(fù)值，降低了所構(gòu)造模型的可解釋性。

基于非負(fù)矩陣分解（Nonnegative Matrix Factorization，NMF）［10］的一類(lèi)方法［11-12］則通過(guò)將圖鄰接矩陣的非負(fù)結(jié)構(gòu)分解（structured factorization）實(shí)現(xiàn)圖聚類(lèi)。由于被分解的可以是非對(duì)稱(chēng)矩陣且分解結(jié)果均為非負(fù)矩陣，該類(lèi)方法對(duì)有向圖聚類(lèi)具有良好的適應(yīng)性和可解釋性，近年來(lái)得到廣泛關(guān)注。譬如，Wang 等［11］提出的非對(duì)稱(chēng)非負(fù)矩陣分解（Asymmetric NMF，ANMF）算法將有向圖的非對(duì)稱(chēng)鄰接矩陣分解為分別表示“節(jié)點(diǎn)-簇”隸屬度和簇間相似性的非負(fù)矩陣，進(jìn)而基于隸屬度矩陣對(duì)節(jié)點(diǎn)進(jìn)行簇劃分；在此基礎(chǔ)上，Tosyali等［12］引入節(jié)點(diǎn)間的相似先驗(yàn)信息為正則項(xiàng)，構(gòu)造了正則化的非對(duì)稱(chēng)非負(fù)矩陣分解（Regularized Asymmetric NMF，RANMF）算法，提高了有向圖聚類(lèi)的準(zhǔn)確性和魯棒性。

然而，以上算法忽略了有向圖上潛在的節(jié)點(diǎn)間的非線(xiàn)性關(guān)系。在許多實(shí)際應(yīng)用產(chǎn)生的圖（網(wǎng)絡(luò)）中，節(jié)點(diǎn)與節(jié)點(diǎn)之間通常是非線(xiàn)性相關(guān)的。如社交網(wǎng)絡(luò)中，個(gè)體（節(jié)點(diǎn)）之間的關(guān)系并不是單一的，有可能是同事、家人甚至更復(fù)雜的人際關(guān)系（有向邊）。顯然，這些關(guān)系不能簡(jiǎn)單地以線(xiàn)性方式來(lái)逼近。當(dāng)前，深度學(xué)習(xí)（deep learning）與核學(xué)習(xí)（kernel learning）是兩種主流的節(jié)點(diǎn)間非線(xiàn)性關(guān)系建模方法。例如，Perozzi 等［13］提出深度游走（DeepWalk）算法，通過(guò)隨機(jī)游走捕捉圖的高階近鄰結(jié)構(gòu)，進(jìn)而將深度學(xué)習(xí)技術(shù)運(yùn)用到圖聚類(lèi)問(wèn)題中；但是，該算法并未考慮節(jié)點(diǎn)間連接的方向性。核學(xué)習(xí)方法［14］通過(guò)將低維數(shù)據(jù)嵌入到高維核空間中，使得低維不可分?jǐn)?shù)據(jù)在新空間中線(xiàn)性可分或接近線(xiàn)性可分，從而有效挖掘隱含在數(shù)據(jù)中的非線(xiàn)性關(guān)系。近年，已提出多種核非負(fù)矩陣分解（Kernel NMF，KNMF）算法，利用小樣本條件下核學(xué)習(xí)方法在非線(xiàn)性學(xué)習(xí)中的良好性能進(jìn)行人臉識(shí)別、文本聚類(lèi)等［15-18］。

本文提出用于非線(xiàn)性有向圖聚類(lèi)的核非負(fù)矩陣分解算法，稱(chēng)為正則化的核非對(duì)稱(chēng)非負(fù)矩陣分解（Regularized Kernel Asymmetric NMF，RKANMF）。首先，基于核化機(jī)制構(gòu)造了有向圖核聚類(lèi)目標(biāo)函數(shù)，定義了約束核空間中節(jié)點(diǎn)相似性關(guān)系的正則化項(xiàng)，以保持原空間中節(jié)點(diǎn)間相似關(guān)系的同時(shí)強(qiáng)化核空間中同簇節(jié)點(diǎn)間的（非線(xiàn)性）相似性；其次，基于梯度下降法提出了一種聚類(lèi)優(yōu)化算法，證明了算法的收斂性；最后，在8個(gè)有向網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，并與深度學(xué)習(xí)算法等進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法的有效性。

1 相關(guān)工作

1.1 基本定義

定義1有向圖。在有向圖中G=(V，E)，邊(i，j)∈E將節(jié)點(diǎn)i連接到節(jié)點(diǎn)j，|V|表示節(jié)點(diǎn)數(shù)，|E|表示邊數(shù)。有向圖可以由鄰接矩陣來(lái)表示。

構(gòu)建有向圖鄰接矩陣：鄰接矩陣A∈Rn×n+，其中n是節(jié)點(diǎn)數(shù)，若從節(jié)點(diǎn)到節(jié)點(diǎn)存在有向邊，[A]ij=1，否則[A]ij=0。特別地，[A]ii=0。本文用[·]ij表示矩陣第i行第j列元素。

圖聚類(lèi)基于節(jié)點(diǎn)間的相似性：節(jié)點(diǎn)之間越相似，則越可能劃分到同一個(gè)簇。文獻(xiàn)中常用的節(jié)點(diǎn)相似性度量有：

1）Katz 中心相似性度量［19］。對(duì)于圖中每一條路徑，利用加權(quán)方案計(jì)算其權(quán)重，公式如下：

其中：I為元素全為1 的矩陣；當(dāng)參數(shù)β＜1 時(shí)，較長(zhǎng)的路徑將分配到較小的權(quán)重，較短的路徑則獲得更大的權(quán)重，權(quán)重越大，節(jié)點(diǎn)間就越相似。

2）余弦相似性度量［19］。計(jì)算節(jié)點(diǎn)間公共鄰居的數(shù)量，公共鄰居的數(shù)量越多表示節(jié)點(diǎn)間越相似。計(jì)算公式為：

其中：cij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j的公共鄰居數(shù)量；為由所有鄰居數(shù)量組成的向量的長(zhǎng)度，取值在0到1之間。余弦相似度為1表示兩個(gè)節(jié)點(diǎn)具有相同的鄰居，0則表示沒(méi)有相同鄰居。

1.2 基于NMF的聚類(lèi)算法

其中：r?min{m，n}為分解矩陣的秩；‖?‖F(xiàn)表示矩陣的Frobenious 范數(shù)。對(duì)于聚類(lèi)任務(wù)［20］，分解結(jié)果中的W可以視為隸屬度矩陣，根據(jù)規(guī)則將第i個(gè)樣本xi分配到隸屬度最大的簇j*，完成聚類(lèi)。

下面介紹兩種基于NMF 的代表性有向圖聚類(lèi)算法：ANMF［12］和RANMF［13］算法。ANMF 將式（3）中的B矩陣用HWT代替，其中，，定義其優(yōu)化問(wèn)題如下：

RANMF 在A(yíng)NMF 算法基礎(chǔ)上添加了圖正則化項(xiàng)，對(duì)同簇節(jié)點(diǎn)間的相似性進(jìn)行約束，其定義的優(yōu)化問(wèn)題如下：

其中：Tr(?)是矩陣的跡；S是節(jié)點(diǎn)間相似性矩陣；D為對(duì)角矩陣，其中每個(gè)對(duì)角元Dii是矩陣S的第i行元素的和。

1.3 核函數(shù)與KNMF

核函數(shù)是從低維空間到高維空間中的一種映射函數(shù)。設(shè)R為輸入空間，H為特征空間（希爾伯特空間或核再生空間，以下簡(jiǎn)稱(chēng)核空間），核學(xué)習(xí)方法［14］利用核函數(shù)實(shí)現(xiàn)從R到H的映射：φ(X)：R→H。對(duì)于輸入空間的樣本對(duì)(xi，xj)，核技巧（kernel trick）通過(guò)替換核空間中樣本對(duì)的內(nèi)積為核函數(shù)κ(xi，xj)的值（核化），解決φ(X)難于計(jì)算的問(wèn)題，即：

常用的核函數(shù)包括多項(xiàng)式核函數(shù)和徑向基核函數(shù)等，其定義分別如下：

為捕捉數(shù)據(jù)中的局部結(jié)構(gòu)信息，文獻(xiàn)［21］新近提出了分?jǐn)?shù)階核（Fractional power kernel）：

其中：zd表示任意向量z中每個(gè)元素的d次冪。鑒于圖聚類(lèi)的目的在于根據(jù)圖的局部結(jié)構(gòu)特性進(jìn)行節(jié)點(diǎn)分組，本文采用如式（4）所示的分?jǐn)?shù)階核函數(shù)，并用矩陣形式加以表示，如下：

在傳統(tǒng)NMF 的基礎(chǔ)上，利用上述核化機(jī)制可以對(duì)輸入矩陣進(jìn)行核非負(fù)矩陣分解（KNMF）。例如，基于KNMF 的人臉識(shí)別［17-18］定義其優(yōu)化問(wèn)題為：

意在優(yōu)化兩個(gè)非負(fù)矩陣W和B，使得映射后的人臉圖像在核空間可以近似地表示為基圖像的線(xiàn)性組合，即：φ(X)≈φ(W)B。相比僅能對(duì)數(shù)據(jù)中線(xiàn)性關(guān)系建模的傳統(tǒng)NMF，KNMF 的優(yōu)勢(shì)在于可以通過(guò)核函數(shù)對(duì)數(shù)據(jù)進(jìn)行高維映射發(fā)掘隱含的非線(xiàn)性特征，并利用核技巧降低算法的時(shí)間復(fù)雜度。

2 RKANMF有向圖聚類(lèi)算法

本章討論基于正則化核非對(duì)稱(chēng)非負(fù)矩陣分解（RKANMF）的有向圖聚類(lèi)算法。首先構(gòu)造了新的聚類(lèi)優(yōu)化目標(biāo)函數(shù)，給出參數(shù)優(yōu)化方法；接著，提出優(yōu)化該目標(biāo)函數(shù)的聚類(lèi)算法，并嚴(yán)格證明了算法的收斂性。

2.1 聚類(lèi)目標(biāo)函數(shù)及其優(yōu)化方法

為在保持原空間中節(jié)點(diǎn)間（線(xiàn)性）相似關(guān)系的同時(shí)強(qiáng)化核空間中同簇節(jié)點(diǎn)間的（非線(xiàn)性）相似性，在構(gòu)造約束核空間中節(jié)點(diǎn)相似性關(guān)系的正則項(xiàng)的基礎(chǔ)上，利用核化機(jī)制定義RKANMF有向圖核聚類(lèi)目標(biāo)函數(shù)如下：

其中：D是對(duì)角線(xiàn)矩陣，其對(duì)角元Dii是矩陣S的第i行的和。整理聚類(lèi)目標(biāo)函數(shù)式（6）得到：

從優(yōu)化角度分析，聚類(lèi)是求解聚類(lèi)目標(biāo)函數(shù)最優(yōu)值的過(guò)程，即在矩陣W和H非負(fù)約束條件下最小化式（7）。根據(jù)梯度下降方法，矩陣W和H通過(guò)迭代以下乘法更新規(guī)則求解：

其中Zd表示矩陣Z中每個(gè)元素的d次冪。

2.2 聚類(lèi)算法及收斂性分析

依據(jù)2.1 節(jié)中W和H的更新公式（式（8）和（9）），提出基于RKANMF的有向圖聚類(lèi)算法，具體描述如下：

算法 基于RKANMF的有向圖聚類(lèi)算法。

計(jì)算KWAWd和KWWHKWW的時(shí)間復(fù)雜度分別為O(n2r)和O(r2(r+n))，由于r＜n，每次迭代更新公式H的時(shí)間復(fù)雜度為O(n2r)。同理，每次迭代更新W的時(shí)間復(fù)雜度為O(n2r)，因此，算法在不考慮迭代次數(shù)的情況下，時(shí)間復(fù)雜度為O(n2r)。

接著對(duì)算法的收斂性進(jìn)行分析，借鑒文獻(xiàn)［11，22］中的輔助函數(shù)法來(lái)證明在所提更新規(guī)則下算法的收斂性。

定理1式（7）中的目標(biāo)函數(shù)在矩陣W和H的更新規(guī)則式（8）和（9）下是單調(diào)非增的。

證明 當(dāng)固定H時(shí)，令

可得以下三個(gè)不等式：

令φ(W)=Wd，即得式（8）中W的更新公式。

同理，當(dāng)W固定時(shí)，正則項(xiàng)部分與H無(wú)關(guān)。此時(shí)，令

則有：

得出式（8）中H的乘法更新公式。又由于

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

本章通過(guò)在三個(gè)領(lǐng)域有向網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)來(lái)驗(yàn)證所提算法RKANMF 在有向圖聚類(lèi)中的有效性，并與當(dāng)前若干主流算法（ANMF［11］、RANMF［12］及DeepWalk 算法［13］）進(jìn)行對(duì)比。實(shí)驗(yàn)平臺(tái)如下：Core i7-9750 2.60 GHz CPU，16.00 GB 內(nèi)存，操作系統(tǒng)為Windows 10。

3.1 數(shù)據(jù)集

實(shí)驗(yàn)使用的有向網(wǎng)絡(luò)數(shù)據(jù)集包含專(zhuān)利-引文網(wǎng)絡(luò)（Patent Citation Network，PCN）數(shù)據(jù)集［23］、World Wide Knowledge Base（WebKB）數(shù)據(jù)集［24］和人工合成網(wǎng)絡(luò)LFR（Lancichinetti-Fortunato-Radicchi）數(shù)據(jù)集［25］，數(shù)據(jù)集的詳細(xì)信息見(jiàn)表1。

表1 有向網(wǎng)絡(luò)數(shù)據(jù)集的詳細(xì)信息Tab.1 Details of directed network datasets

①PCN 數(shù)據(jù)集。PCN 由4 142 個(gè)節(jié)點(diǎn)和18 385 條邊組成，形成一個(gè)單一的連接樹(shù)結(jié)構(gòu)。本文選擇PCN 中的149個(gè)節(jié)點(diǎn)（專(zhuān)利）和215 個(gè)有向邊（引用）來(lái)檢驗(yàn)聚類(lèi)效果。由于同一簇的專(zhuān)利不一定具有直接公共鄰居，而是具有一個(gè)或多個(gè)中間專(zhuān)利連接的非中間鄰居，因此根據(jù)式（1）計(jì)算相似矩陣。由于PCN數(shù)據(jù)集沒(méi)有提供節(jié)點(diǎn)標(biāo)簽，因此該數(shù)據(jù)集的簇?cái)?shù)目未知，表1用“—”給予了標(biāo)識(shí)。

②WebKB 數(shù)據(jù)集。該數(shù)據(jù)集包含從4 所大學(xué)（Cornel、Texas、Washington 和Wisconsin）收集的網(wǎng)頁(yè)，網(wǎng)頁(yè)分為學(xué)生、課程、項(xiàng)目、教師和工作人員5 類(lèi)。通常，一個(gè)高質(zhì)量的簇應(yīng)具有較少的簇間連接和更多的簇內(nèi)連接。由于WebKB 數(shù)據(jù)集中的簇與簇之間的連通性較高，選用式（2）計(jì)算節(jié)點(diǎn)間的相似矩陣。

③LFR 數(shù)據(jù)集。LFR 是一個(gè)人工合成數(shù)據(jù)集，包含的網(wǎng)絡(luò)是根據(jù)某些參數(shù)控制的機(jī)制產(chǎn)生的。比如，通過(guò)混合參數(shù)μ控制合成網(wǎng)絡(luò)中簇間連通性的強(qiáng)度，其值越大意味著更強(qiáng)的簇間連通性。本文取μ=0.1，0.3，0.5（分別對(duì)應(yīng)表1 中的LFR1、LFR2 和LFR3），并使用Katz 中心相似性度量式（2）計(jì)算節(jié)點(diǎn)間的相似矩陣。

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

當(dāng)數(shù)據(jù)集沒(méi)有真實(shí)簇劃分時(shí)采用Davies-Bouldin（DB）指標(biāo)［26］和Distance-based Quality Function（DQF）指標(biāo)［27］評(píng)價(jià)多個(gè)算法的聚類(lèi)結(jié)果質(zhì)量；當(dāng)存在真實(shí)簇劃分時(shí)采用聚類(lèi)準(zhǔn)確率（ACcuracy，AC）指標(biāo)、NMI 指標(biāo)及Jaccard 指標(biāo)［28］。各指標(biāo)簡(jiǎn)要介紹如下：

①DB指標(biāo)。

計(jì)算簇內(nèi)散射與簇間分離之比，公式如下：

其中：N表示簇的個(gè)數(shù)；表示第i個(gè)簇中節(jié)點(diǎn)的平均分散程度；Mij為第i類(lèi)與第j類(lèi)簇的距離。當(dāng)DB 指標(biāo)值越小時(shí)，算法得到的聚類(lèi)效果越好。

②DQF指標(biāo)。

計(jì)算簇與簇之間的平均距離，公式如下：

其中：A表示鄰接矩陣；是根據(jù)算法得到節(jié)點(diǎn)簇集合劃分r個(gè)簇后構(gòu)建的新鄰接矩陣，若節(jié)點(diǎn)i與j同簇，則。DQF指標(biāo)越高，則得到的聚類(lèi)結(jié)果越好。

③AC指標(biāo)。

計(jì)算預(yù)測(cè)的節(jié)點(diǎn)簇集合的準(zhǔn)確率，公式如下：

其中：n表示節(jié)點(diǎn)個(gè)數(shù)；ri、si分別為第i個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的獲得的標(biāo)簽和真實(shí)標(biāo)簽；map(ri)是一個(gè)映射函數(shù)，表示將ri映射到相應(yīng)的節(jié)點(diǎn)簇類(lèi)上。δ是指示函數(shù)，其公式如下：

AC指標(biāo)越高，聚類(lèi)質(zhì)量越高。

④NMI指標(biāo)。

計(jì)算預(yù)測(cè)的節(jié)點(diǎn)簇集合與真實(shí)節(jié)點(diǎn)簇劃分的相似度，公式如下：

其中：C1和C2分別是預(yù)測(cè)的節(jié)點(diǎn)簇集合與真實(shí)節(jié)點(diǎn)簇集合；分別表示真實(shí)簇的數(shù)目與預(yù)測(cè)簇的數(shù)目；矩陣R=代表混淆矩陣，rij為真實(shí)簇的節(jié)點(diǎn)i出現(xiàn)在發(fā)現(xiàn)簇j的數(shù)量，ri?和r?j分別是混淆矩陣第i行的和與第j列的和。NMI指標(biāo)越高則聚類(lèi)質(zhì)量越好。

⑤Jaccard指標(biāo)。

計(jì)算預(yù)測(cè)的節(jié)點(diǎn)簇集合與真實(shí)節(jié)點(diǎn)簇集合的交集和并集之比，公式如下：

其中：C1表示預(yù)測(cè)的節(jié)點(diǎn)簇集合，C2為真實(shí)節(jié)點(diǎn)簇集合。Jaccard指標(biāo)越高，則得到聚類(lèi)結(jié)果與真實(shí)簇劃分越相似。

3.3 參數(shù)設(shè)置

為檢驗(yàn)本文RKANMF 算法是否能有效建模節(jié)點(diǎn)間的非線(xiàn)性關(guān)系，將它與ANMF算法［11］、RANMF算法［12］進(jìn)行了比較，并通過(guò)對(duì)比DeepWalk算法［13］，檢驗(yàn)了小樣本條件下算法對(duì)有向聚類(lèi)的準(zhǔn)確性。

在對(duì)不同網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)中，RANMF 算法與ANMF 算法中Katz 中心相似性度量的β參數(shù)以及懲罰項(xiàng)權(quán)重系數(shù)λ的設(shè)置與文獻(xiàn)［12］中的最佳參數(shù)一致，所有基于NMF 的算法統(tǒng)一設(shè)置迭代停止精度ε=10-6。DeepWalk 算法參照文獻(xiàn)［13］設(shè)置每個(gè)節(jié)點(diǎn)出發(fā)游走10 次，游走長(zhǎng)度為10；skip-gram 模型設(shè)置詞向量的維度為30，窗口大小設(shè)置為7。

簇的數(shù)目r值是有向圖聚類(lèi)算法的重要問(wèn)題，也是各個(gè)算法需要設(shè)置的先驗(yàn)參數(shù)，本文在具有類(lèi)標(biāo)簽的數(shù)據(jù)集上采用真實(shí)簇的數(shù)目作為r值，對(duì)于沒(méi)有類(lèi)標(biāo)簽的PCN 數(shù)據(jù)集，選取不同的r值來(lái)對(duì)算法性能進(jìn)行測(cè)試。

在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集中（PCN 和WebKB 數(shù)據(jù)集）重點(diǎn)討論分?jǐn)?shù)階核的次冪d值與懲罰項(xiàng)權(quán)重系數(shù)λ值對(duì)RKANMF 算法的影響。在PCN 數(shù)據(jù)集的實(shí)驗(yàn)中，為了與ANMF 與RANMF算法進(jìn)行對(duì)照實(shí)驗(yàn)，RKANMF 算法設(shè)置共同的參數(shù)λ=0.1，β=0.2。當(dāng)參數(shù)d值取得過(guò)小時(shí)，計(jì)算過(guò)程中，W的更新公式（8）中的分母可能會(huì)接近于0，因此選擇d值在0.2 到0.9 區(qū)間。圖1與圖2顯示當(dāng)簇?cái)?shù)r=2，d=0.2時(shí)，RKANMF 算法在DB與DQF指標(biāo)上均取得最優(yōu)。隨著d值增加，越趨近于1時(shí)，算法不再對(duì)節(jié)點(diǎn)間的非線(xiàn)性關(guān)系建模，從而導(dǎo)致聚類(lèi)質(zhì)量下降。為檢驗(yàn)簇?cái)?shù)不同時(shí)對(duì)算法的影響，統(tǒng)一設(shè)置參數(shù)d=0.2。

圖1 參數(shù)d對(duì)DB指標(biāo)的影響Fig.1 Influence of parameter d on DB index

圖2 參數(shù)d對(duì)DQF指標(biāo)的影響Fig.2 Influence of parameter d on DQF index

在具有真實(shí)簇劃分的WebKB 數(shù)據(jù)集實(shí)驗(yàn)中，著重考慮d值在0.2 到0.9 區(qū)間變化時(shí)，RKANMF 算法對(duì)AC 指標(biāo)的影響。結(jié)果如圖3所示，在多個(gè)子數(shù)據(jù)集上，當(dāng)d值在0.4到0.5之間時(shí)，算法的聚類(lèi)結(jié)果在A(yíng)C 指標(biāo)上更高。當(dāng)d值趨于1 時(shí)AC指標(biāo)呈下降趨勢(shì)，算法不再建模節(jié)點(diǎn)間的非線(xiàn)性關(guān)系從而導(dǎo)致聚類(lèi)質(zhì)量下降。根據(jù)圖3，對(duì)四個(gè)子數(shù)據(jù)集（Cornel、Texas、Washington 和Wisconsin）分別取合適的d值為0.4、0.4、0.9和0.5。

圖3 WebKB數(shù)據(jù)集上d值對(duì)AC指標(biāo)影響Fig.3 Influence of d value on AC index on WebKB dataset

為考慮λ值對(duì)算法的影響，當(dāng)固定d值后，設(shè)置權(quán)重系數(shù)λ值區(qū)間為0 到500。圖4 顯示，當(dāng)λ值越大時(shí)，算法越傾向于考慮節(jié)點(diǎn)間的相似性信息；當(dāng)λ值過(guò)大時(shí)，算法過(guò)于依賴(lài)節(jié)點(diǎn)相似性，將原來(lái)屬于不同簇的節(jié)點(diǎn)劃分到同一簇中從而導(dǎo)致聚類(lèi)準(zhǔn)確性下降。根據(jù)圖4，對(duì)四個(gè)子數(shù)據(jù)集（Cornel、Texas、Washington 和Wisconsin）分別取合適的λ值為20、5、50 和20。同理，在LFR 的3個(gè)數(shù)據(jù)集中，所提算法通過(guò)對(duì)比多次得到的AC指標(biāo)值，設(shè)置合適的參數(shù)β=0.1，λ=0.1，d=0.88。

圖4 WebKB數(shù)據(jù)集中λ值對(duì)AC指標(biāo)影響Fig.4 Influence of λ value on AC index on WebKB dataset

3.4 PCN數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對(duì)比分析

本節(jié)使用PCN 數(shù)據(jù)集［23］來(lái)檢驗(yàn)四種算法的性能表現(xiàn)。表2 是利用DB 和DQF 指標(biāo)上對(duì)不同算法進(jìn)行比較的結(jié)果。方便起見(jiàn)，表中均采用“Rnd”對(duì)隨機(jī)初始化策略進(jìn)行標(biāo)識(shí)；用“SVD”表示基于SVD策略［12］的初始化，方法與文獻(xiàn)［12］一致；使用隨機(jī)初始化策略的算法運(yùn)行100 次，每一次都按不同的初始化矩陣進(jìn)行迭代，取最終結(jié)果的平均值。

表2 簇?cái)?shù)（r）不同時(shí)各算法在PCN上的DB和DQF指標(biāo)比較Tab.2 Comparison of DB and DQF indexes on PCN for each algorithm with different number of clusters（r）

表2 結(jié)果表明，隨著簇?cái)?shù)r的增加，所有算法的聚類(lèi)質(zhì)量均有所下降，說(shuō)明當(dāng)簇的數(shù)目r越來(lái)越多時(shí)，本應(yīng)該劃分到相同簇的節(jié)點(diǎn)被分到不同簇，導(dǎo)致聚類(lèi)質(zhì)量降低。對(duì)于DB 指標(biāo)，當(dāng)簇?cái)?shù)r=6 時(shí)，RANMF 算法與RKANMF 算法的DB 指標(biāo)均低于DeepWalk 算法，這是由于過(guò)多考慮非中間鄰居從而導(dǎo)致聚類(lèi)效果變差。對(duì)于DQF 指標(biāo)，在隨機(jī)初始化的情況下，所提算法也能比基于SVD 策略初始化［12］的RANMF 與ANMF算法在DQF 指標(biāo)上取得更好的表現(xiàn)。這說(shuō)明RKANMF 算法有效地對(duì)節(jié)點(diǎn)間的非線(xiàn)性關(guān)系建模得到了更好的特征表示，顯著提高了聚類(lèi)質(zhì)量。對(duì)比三種基于NMF 的算法可知，好的初始化策略及考慮了非線(xiàn)性關(guān)系的NMF 算法均能避免分解過(guò)程陷入較差的局部最優(yōu)值。

3.5 WebKB數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對(duì)比分析

本節(jié)使用WebKB 數(shù)據(jù)集［24］中的四個(gè)子數(shù)據(jù)集來(lái)檢驗(yàn)幾種算法在數(shù)據(jù)集的簇間連通性強(qiáng)時(shí)的性能，結(jié)果如表3?？梢钥闯觯?dāng)數(shù)據(jù)集簇間連通性較高時(shí)，基于隨機(jī)初始化策略的算法能得到較好的聚類(lèi)結(jié)果，這是由于經(jīng)過(guò)多次隨機(jī)初始化的過(guò)程，算法更容易找到一個(gè)更好的局部極小值。對(duì)比基于NMF 的算法與DeepWalk 算法可知，在大多數(shù)情況下，基于NMF 的算法能得到更好的聚類(lèi)結(jié)果。這說(shuō)明當(dāng)圖的結(jié)構(gòu)變得模糊，DeepWalk 算法無(wú)法準(zhǔn)確獲取有向圖的高階近鄰結(jié)構(gòu)，從而導(dǎo)致聚類(lèi)質(zhì)量下降。

表3 各算法在WebKB數(shù)據(jù)集上的結(jié)果比較Tab.3 Result comparison of different algorithms on WebKB dataset

在Cornell 子數(shù)據(jù)集中，RKANMF 算法在NMI 指標(biāo)上最高，表明在數(shù)據(jù)集的簇間連通性高的情況下，RKANMF 算法也能有效發(fā)掘節(jié)點(diǎn)間非線(xiàn)性關(guān)系。在Texas 子數(shù)據(jù)集中，RANMF 與RKANMF 算法的NMI 指標(biāo)低于A(yíng)NMF 算法，因?yàn)樵谡齽t項(xiàng)權(quán)重系數(shù)逐漸變大的過(guò)程中，帶正則項(xiàng)的兩個(gè)算法均忽視了鄰接矩陣的結(jié)構(gòu)信息，從而聚類(lèi)質(zhì)量下降。

3.6 LFR網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果對(duì)比分析

本節(jié)使用LFR網(wǎng)絡(luò)［25］來(lái)檢驗(yàn)幾種算法檢驗(yàn)在度分布不平衡的復(fù)雜網(wǎng)絡(luò)中的表現(xiàn)，結(jié)果如表4。表4顯示了不同算法在LFR 網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果，其中“—”表示基于SVD 策略初始化的ANMF算法得不到聚類(lèi)結(jié)果。由表4可以看出，隨著μ值的增加，算法對(duì)簇的劃分變得愈加困難。當(dāng)簇類(lèi)結(jié)構(gòu)變得模糊時(shí)，基于NMF 的算法在NMI 指標(biāo)上低于DeepWalk 算法，這說(shuō)明DeepWalk 更有針對(duì)性地獲取圖的結(jié)構(gòu)來(lái)提高劃分簇的質(zhì)量。RKANMF 算法在A(yíng)C 和Jaccard 指標(biāo)上有更好的表現(xiàn)，這是由于RKANMF 算法中正則項(xiàng)發(fā)掘了節(jié)點(diǎn)間的（非線(xiàn)性）相似性關(guān)系。相比其他基于NMF 的算法，RKANMF 不僅在NMI指標(biāo)上與DeepWalk 算法比較接近，且在A(yíng)C 和Jaccard 指標(biāo)上有顯著的提高，這說(shuō)明當(dāng)節(jié)點(diǎn)關(guān)系變得復(fù)雜時(shí)，對(duì)節(jié)點(diǎn)間的非線(xiàn)性關(guān)系進(jìn)行建模能更有效地提高聚類(lèi)算法的表現(xiàn)。

表4 各算法在LFR網(wǎng)絡(luò)數(shù)據(jù)集上的結(jié)果比較Tab.4 Result comparison of different algorithms on LFR network dataset

4 結(jié)語(yǔ)

本文提出了一個(gè)用于有向圖聚類(lèi)的圖正則化核非對(duì)稱(chēng)非負(fù)矩陣分解優(yōu)化方法。該方法基于核化機(jī)制構(gòu)造了有向圖聚類(lèi)新目標(biāo)函數(shù)，其正則項(xiàng)同時(shí)考慮了原始空間中節(jié)點(diǎn)間的相似性及節(jié)點(diǎn)在核空間中的（非線(xiàn)性）相關(guān)性；基于梯度下降法推導(dǎo)了一個(gè)有向圖聚類(lèi)（RKANMF）算法，給出了算法的詳細(xì)過(guò)程及收斂性分析，并在多個(gè)有向網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，與未結(jié)合核學(xué)習(xí)方法的非負(fù)矩陣分解算法及DeepWalk 等算法相比，新算法在多個(gè)聚類(lèi)有效性指標(biāo)上有更好的表現(xiàn)。今后我們將針對(duì)性地考慮節(jié)點(diǎn)的方向性以及不同核函數(shù)對(duì)有向圖聚類(lèi)的影響等方面做進(jìn)一步研究。