鄧 莉, 劉士虎

(云南民族大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 昆明 650504)

在現(xiàn)實(shí)生活中，許多諸如Facebook社交網(wǎng)絡(luò)[1]、蛋白質(zhì)相互作用網(wǎng)絡(luò)[2-3]、航空網(wǎng)絡(luò)[4]、疾病傳播網(wǎng)絡(luò)[5]等都可以抽象為圖數(shù)據(jù).圖數(shù)據(jù)不僅僅刻畫(huà)了樣本點(diǎn)的特征，還包含刻畫(huà)樣本點(diǎn)之間關(guān)聯(lián)情況的信息，即拓?fù)湫畔?鑒于圖數(shù)據(jù)在理論層面和市場(chǎng)需求具有的巨大應(yīng)用價(jià)值，近年來(lái)其在各行各業(yè)掀起了研究高潮，并且取得了一系列卓有成效的研究成果[6-8].不難發(fā)現(xiàn)，圖數(shù)據(jù)中樣本點(diǎn)的相似性度量是一個(gè)重要的研究課題，在字符和圖形識(shí)別[9]、目標(biāo)跟蹤[10]、城市交通網(wǎng)絡(luò)[11-12]等領(lǐng)域發(fā)揮著重要的作用.

隨機(jī)游走方法被廣泛用于度量樣本點(diǎn)的相似性，該方法無(wú)需圖數(shù)據(jù)的全局信息，衡量從特定樣本點(diǎn)出發(fā)，通過(guò)多步隨機(jī)游走到達(dá)另一個(gè)樣本點(diǎn)的過(guò)程.為了更好地使用此方法度量樣本點(diǎn)的相似性，研究者們相繼提出了多種隨機(jī)游走模型：如有偏的隨機(jī)游走模型(biased random walk，BRW)[13-14]，最大熵隨機(jī)游走模型(maximal entropy random walk，MERW)[15]，局部隨機(jī)游走模型(local random walk，LRW)[16]等.不足的是，這些隨機(jī)游走模型的樣本點(diǎn)相似性度量方法存在大度樣本點(diǎn)依賴問(wèn)題.同時(shí)，這些方法從拓?fù)湫畔⒊霭l(fā)來(lái)度量樣本點(diǎn)基于結(jié)構(gòu)的相似性，使其難以廣泛運(yùn)用于度量屬性圖數(shù)據(jù)中樣本點(diǎn)相似性.文獻(xiàn)[17]針對(duì)屬性圖數(shù)據(jù)樣本點(diǎn)相似性的度量問(wèn)題，提出了一種樣本點(diǎn)基于隨機(jī)游走的相似性度量方法:LLRWSMM-PCO.該方法充分討論了任意兩個(gè)樣本點(diǎn)關(guān)于拓?fù)浣Y(jié)構(gòu)的可達(dá)性，在樣本點(diǎn)可達(dá)的基礎(chǔ)上，度量樣本點(diǎn)基于拓?fù)湫畔⒌南嗨菩?，從而得到一種綜合的相似性度量方法.不足的是，該方法只針對(duì)無(wú)權(quán)無(wú)向圖數(shù)據(jù).

除了基于隨機(jī)游走的樣本點(diǎn)相似性方法，大量的研究從樣本點(diǎn)共享鄰居的角度對(duì)樣本點(diǎn)相似性進(jìn)行了研究[18-23].Salton[21]和Jaccard[22]分別提出了基于余弦距離和共享鄰居Jaccard指標(biāo)，該指標(biāo)認(rèn)為樣本點(diǎn)的共享鄰居越多，其相似性程度越高.在文獻(xiàn)[23]中，Lada等從共享鄰居度的角度，提出了Adamic-Adar指標(biāo)，該指標(biāo)認(rèn)為，共享鄰居的度越小，樣本點(diǎn)間潛在的相似性越大.然而，真實(shí)網(wǎng)絡(luò)中存在許多樣本點(diǎn)沒(méi)有共同的鄰居，但是在屬性信息方面有極高的相似性，從而導(dǎo)致從共享鄰居角度度量樣本點(diǎn)相似性存在一定的局限.除了這些研究，文獻(xiàn)[24-28]中還提出了許多其它的度量方法.

對(duì)于圖數(shù)據(jù)中樣本點(diǎn)的相似性度量問(wèn)題，無(wú)向無(wú)權(quán)的圖數(shù)據(jù)已有了較多的研究.但隨著研究的不斷深入，無(wú)向無(wú)權(quán)圖數(shù)據(jù)已經(jīng)不能涵蓋大部分的網(wǎng)絡(luò)特性.大部分真實(shí)圖數(shù)據(jù)的鏈接是帶有權(quán)重的，比如共同作者網(wǎng)絡(luò)、航空網(wǎng)絡(luò)等.因此，帶權(quán)圖數(shù)據(jù)中樣本點(diǎn)的相似性度量逐漸受到重視.針對(duì)這類(lèi)問(wèn)題的研究，本文從屬性信息和拓?fù)湫畔?個(gè)角度出發(fā)，按以下2個(gè)步驟來(lái)展開(kāi)工作：①提出基于改進(jìn)的度中心性指導(dǎo)的隨機(jī)游走的方法，度量樣本點(diǎn)基于拓?fù)湫畔⒌南嗨菩?；②針?duì)歐式距離在度量相似性方面的不足，通過(guò)融合歐式距離和余弦距離來(lái)度量樣本點(diǎn)基于屬性信息的相似性，進(jìn)而得到樣本點(diǎn)間的綜合相似性.

1 預(yù)備知識(shí)

為了行文簡(jiǎn)潔及后文敘述的需要，這里給出文中需要用到的一些基本知識(shí)以及相關(guān)數(shù)學(xué)表示.

1.1 帶權(quán)圖數(shù)據(jù)

通常情況下，帶權(quán)圖數(shù)據(jù)可表示為G=(X,R,W)，其中X={x1,x2,…,xn}是一個(gè)非空有限集，表示帶權(quán)圖數(shù)據(jù)中樣本點(diǎn)的集合，xi=(xi1,xi2,…,xim)表示有m個(gè)屬性的樣本點(diǎn)，即|X|=n,X的矩陣形式表示為

R={rij|i,j=1,2,...,n}表示圖數(shù)據(jù)中樣本點(diǎn)之間關(guān)聯(lián)信息的集合，rij表示樣本點(diǎn)xi與xj間的拓?fù)湫畔?本文使用樣本點(diǎn)xi與xj基于共享鄰居與非共享鄰居的相異性來(lái)刻畫(huà)rij)，R也可使用矩陣的形式表示

其中，不妨假設(shè)，若rij≠0，則表示樣本點(diǎn)xi與xj有邊相連,反之，rij=0.

帶權(quán)圖數(shù)據(jù)G中樣本點(diǎn)的可達(dá)性可作如下定義：若樣本點(diǎn)xi與xj是零步可達(dá)，即xi與xj是相同樣本點(diǎn)；若樣本點(diǎn)xi與xj間接連接，即rij=0，但rik0≠0,rk0k1≠0,…,rkl-1j≠0，則稱樣本點(diǎn)xi與xj是l步可達(dá)的；若樣本點(diǎn)xi與xj是l步不可達(dá)的，則稱為它們恒不可達(dá)或者絕對(duì)不可達(dá).

1.2 度中心性

在帶權(quán)圖數(shù)據(jù)中，度中心性是衡量一個(gè)樣本點(diǎn)與所有其它樣本點(diǎn)相關(guān)聯(lián)的程度.對(duì)于一個(gè)樣本點(diǎn)規(guī)模為n的帶權(quán)圖數(shù)據(jù)，樣本點(diǎn)xi的度中心性定義為其直接相連鄰居n(xi)所對(duì)應(yīng)的權(quán)重之和，可用CD(xi)表示，具體計(jì)算方法如下:

其中，T(x)={y|rxy≠0}.

1.3 幾類(lèi)相似性度量方法

Jaccard相似度是一種從拓?fù)湫畔⒊霭l(fā)，考慮從共享鄰居的數(shù)量的角度，度量?jī)蓸颖军c(diǎn)之間相似性的方法，其具體定義如下

(2)

該指標(biāo)在縮短計(jì)算時(shí)間以及尋找最相似樣本點(diǎn)有很好的效果.遺憾的是，該指標(biāo)著重從最近鄰居考慮樣本點(diǎn)基于拓?fù)湫畔⒌南嗨菩?，使得在度量過(guò)程中丟失非最近鄰居樣本點(diǎn)的信息.

歐式距離如公式(3)所示，被廣泛應(yīng)用于的各種相似性度量研究.其優(yōu)點(diǎn)在于可以克服變量之間的相關(guān)性干擾，并且消除各變量量綱的影響.但是該方法易受指標(biāo)不同單位刻度影響，難以刻畫(huà)具有相同歐式距離的屬性信息之間的散度.

(3)

余弦距離如公式(4)所示，是通過(guò)計(jì)算2個(gè)樣本點(diǎn)基于屬性信息的夾角余弦值來(lái)評(píng)估相似程度.有別于歐氏距離，該方法更加注重度量樣本點(diǎn)基于屬性信息在方向上的差異，但對(duì)具體數(shù)值的絕對(duì)值大小不敏感，使得相似性得分不具有區(qū)分性.

(4)

LLRWSMM-PCO方法是一種從屬性信息和拓?fù)湫畔?個(gè)角度出發(fā)，結(jié)合隨機(jī)游走，進(jìn)而度量圖數(shù)據(jù)中兩樣本點(diǎn)相似性的方法.在拓?fù)湫畔⒌南嗨菩远攘糠矫?，該方法充分研究了樣本點(diǎn)基于拓?fù)湫畔⒌目蛇_(dá)性，并在可達(dá)的基礎(chǔ)上，利用隨機(jī)游走計(jì)算樣本點(diǎn)基于拓?fù)湫畔⒌南嗨菩?在利用余弦相似度計(jì)算到屬性信息相似性后，該方法將屬性信息和拓?fù)湫畔⑦M(jìn)行加權(quán)，得到最終的相似性，其主要計(jì)算公式如下.

(5)

(6)

-SX(xi,xj)表示樣本點(diǎn)xi與xj關(guān)于屬性信息的相似性.

-sij(xi,xj)表示樣本點(diǎn)xi與xj的綜合相似性.

-τ:xi→xko→…→xkl-1→xj表示樣本點(diǎn)xi與xj間的一條隨機(jī)游走路徑.

2 基于拓?fù)湫畔⒌南嗨菩远攘?/h2>

針對(duì)帶權(quán)圖數(shù)據(jù)中樣本點(diǎn)基于拓?fù)湫畔⒌南嗨菩远攘繂?wèn)題，文中從共享鄰居與改進(jìn)度中心性的角度出發(fā)，利用隨機(jī)游走的方法，構(gòu)建了ICSMMP算法.該算法從以下2個(gè)方面對(duì)拓?fù)湫畔⑦M(jìn)行相似性度量.首先改進(jìn)了共享鄰居的定義，利用共享鄰居與非共享鄰居的比值構(gòu)造相鄰樣本點(diǎn)關(guān)于拓?fù)湫畔⒌南喈愋?在此基礎(chǔ)之上，利用改進(jìn)度中心性指導(dǎo)隨機(jī)游走的方法，選擇最優(yōu)路徑，進(jìn)而度量帶權(quán)圖數(shù)據(jù)中任意樣本點(diǎn)基于拓?fù)湫畔⒌南嗨菩?

2.1 基于共享鄰居的相似性度量方法

在討論樣本點(diǎn)相似性的算法中，計(jì)算樣本點(diǎn)間的連邊概率通常是基于它們的共同鄰居樣本點(diǎn)的信息.從樣本點(diǎn)的共享鄰居的角度出發(fā)，2樣本點(diǎn)的共享鄰居越多，共享鄰居對(duì)樣本點(diǎn)相似性所做出的貢獻(xiàn)就越大.相反，若2樣本點(diǎn)的共享鄰居越少，則2樣本點(diǎn)潛在的相似性越小.對(duì)任意樣本點(diǎn)xi與xj，現(xiàn)有的共享鄰居T(xi,xj)定義為

T(xi,xj)=T(xi)∩T(xj).

(8)

在解決實(shí)際問(wèn)題中，如圖1所示，(a)、(b)中T(x1,x2)={x3}，但 (b)中x1與x3之間的關(guān)聯(lián)信息比(a)多，所以其在拓?fù)湫畔⒎矫鏉撛诘南嗨菩愿?為此，文中在公式(8)的基礎(chǔ)上改進(jìn)共享鄰居的計(jì)算方法，具體公式如下:

T(xi,xj)*=T(xi)+T(xj)-(O(xi)+O(xj))+T(xi,xj),

(9)

其中，O(xi)表示與xi連接的鄰居中與xj不連接的鄰居.

(10)

其中，|T(xi,xj)*|表示共享鄰居的數(shù)目.公式(10)表明，樣本點(diǎn)的非共享鄰居越多，其共享鄰居所占的比例越小，樣本點(diǎn)間潛在的關(guān)系越少，進(jìn)而拓?fù)湫畔⑾嗨菩跃驮降?

2.2 改進(jìn)度中心性

在帶權(quán)圖數(shù)據(jù)中，樣本點(diǎn)的度中心性是衡量樣本點(diǎn)重要性的重要指標(biāo).現(xiàn)有計(jì)算帶權(quán)圖數(shù)據(jù)中樣本點(diǎn)度中心性的方法單方面考慮了其鄰居權(quán)重，沒(méi)有考慮樣本點(diǎn)鄰居個(gè)數(shù)對(duì)度中心性的影響.由公式(1)計(jì)算不難發(fā)現(xiàn)，圖2中x2與x3的度中心性的值都為1.8，但x2擁有更多的鄰居，在游走的過(guò)程中，x2作為游走過(guò)程的中間樣本點(diǎn)的可能性更大.為此，在公式(1)的基礎(chǔ)上，本文提出了一種改進(jìn)的度中心性的計(jì)算方法如下

(11)

改進(jìn)后的度中心性綜合考慮樣本點(diǎn)的鄰居個(gè)數(shù)、連邊的權(quán)重，能夠更加全面的反映這2個(gè)因素對(duì)樣本點(diǎn)重要性的影響.

圖1 樣本點(diǎn)x2的共享鄰居 圖2 鄰居個(gè)數(shù)不同但權(quán)重之和相同的樣本點(diǎn)

2.3 基于改進(jìn)度中心性指導(dǎo)的隨機(jī)游走方法

在充分研究了樣本點(diǎn)的度中心性后，本文以改進(jìn)度中心性指導(dǎo)樣本點(diǎn)的隨機(jī)游走，度量帶權(quán)圖數(shù)據(jù)G中任意樣本點(diǎn)基于拓?fù)湫畔⒌南嗨菩?一般的，在G中拓?fù)浣Y(jié)構(gòu)是連通的時(shí)候，從樣本點(diǎn)xi出發(fā)，經(jīng)過(guò)有限次的游走可達(dá)樣本點(diǎn)xj，兩樣本點(diǎn)通過(guò)有限中間樣本點(diǎn)連接，在拓?fù)湫畔⒎矫婢哂袧撛诘南嗨菩?而在游走的過(guò)程中，會(huì)產(chǎn)生多條隨機(jī)游走路徑，且基于不同路徑計(jì)算相似性的結(jié)果不同.為此，我們提出了公式(12)來(lái)選擇最優(yōu)路徑進(jìn)行相似性度量

(12)

(13)

其矩陣項(xiàng)表示圖數(shù)據(jù)中樣本點(diǎn)的相異性，具體計(jì)算方式如下

(14)

不難發(fā)現(xiàn)，基于改進(jìn)度中心性指導(dǎo)隨機(jī)游走的方法不僅考慮樣本點(diǎn)自身的信息，而且將樣本點(diǎn)鄰居蘊(yùn)含的潛在信息和一定范圍內(nèi)共享鄰居與非共享鄰居的信息作為因素考慮在相似性的度量過(guò)程中，避免度量過(guò)程僅僅考慮最近鄰相似性，使得相似性難以區(qū)分.在解決實(shí)際問(wèn)題中，利用隨機(jī)游走度量方法最關(guān)注的游走路徑長(zhǎng)度是3步，通過(guò)3步游走可達(dá)的2個(gè)樣本點(diǎn)具有很高的相似性.相反，游走路徑超過(guò)3步的樣本點(diǎn)，其潛在的拓?fù)湎嗨菩詼p少.為此，文中定義若游走路徑長(zhǎng)度超過(guò)3步，則2樣本點(diǎn)不可達(dá).

3 樣本點(diǎn)的綜合相似性度量

針對(duì)歐式距離和余弦距離這2種度量方法在單一使用中的不足，構(gòu)建了一種融合方法來(lái)計(jì)算樣本點(diǎn)屬性信息的相似性.具體如公式(15)所示，

(15)

分別對(duì)樣本點(diǎn)的屬性信息和樣本點(diǎn)間的拓?fù)湫畔⒌南喈愋赃M(jìn)行全面的討論后，文中綜合樣本點(diǎn)基于屬性信息和樣本點(diǎn)間拓?fù)湫畔⒌南喈愋?，給出公式(16)來(lái)定義帶權(quán)圖數(shù)據(jù)G中樣本點(diǎn)的綜合相異性矩陣D=(dij)n×n，其中

(16)

最后，將相異性矩陣轉(zhuǎn)化為相似性矩陣S=(Simij)n×n，進(jìn)而得出綜合性的樣本點(diǎn)相似性度量方法，相似性矩陣S的矩陣項(xiàng)的計(jì)算方式如下：

(17)

由可達(dá)的相關(guān)知識(shí)不難發(fā)現(xiàn)，本文研究相似性度量問(wèn)題可分為3類(lèi)進(jìn)行研究：0步可達(dá)，l 步可達(dá)和不可達(dá)，處于不同類(lèi)別的樣本點(diǎn)的相似性計(jì)算方式不同.針對(duì)本文的研究目的，“基于改進(jìn)度中心性的樣本點(diǎn)相似性度量方法”可以總結(jié)為ICSMMP算法.

4 ICSMMP算法

輸入 無(wú)向帶權(quán)圖數(shù)據(jù)G=(X,R,W).

輸出 帶權(quán)圖數(shù)據(jù)G的相似性矩陣S=(Simij)n×n.

步驟1 由公式(10)計(jì)算相鄰樣本點(diǎn)基于共享鄰居的相異性.

步驟2 由公式(11)計(jì)算帶權(quán)圖數(shù)據(jù)G中各樣本點(diǎn)的改進(jìn)度中心性.

步驟3 調(diào)用隨機(jī)游走算法，基于公式(12)，選擇最優(yōu)路徑.

步驟4 基于最優(yōu)路徑，使用公式(14)計(jì)算樣本點(diǎn)基于拓?fù)湫畔⒌南喈愋?

步驟5 由公式(15)計(jì)算樣本點(diǎn)屬性信息的距離.

步驟6 由公式(16)、(17)計(jì)算G中各樣本點(diǎn)的綜合相似度.

5 算例分析

本文使用了隨機(jī)生成的帶權(quán)圖數(shù)據(jù)G，該圖數(shù)據(jù)有10個(gè)樣本點(diǎn)，12條邊，為了更好的說(shuō)明本文所提出的ICSMMP算法，本文將G進(jìn)行可視化，其結(jié)果如圖3所示，并在改進(jìn)度中心性指導(dǎo)的隨機(jī)游走方法下度量樣本點(diǎn)相似性.圖4中樣本點(diǎn)大小表示該樣本點(diǎn)的改進(jìn)度中心性大小，樣本點(diǎn)越大表示改進(jìn)度中心性越大(藍(lán)色樣本點(diǎn)代表當(dāng)前樣本點(diǎn)，黃色、灰色、綠色、橙色分別代表從當(dāng)前樣本點(diǎn)出發(fā)游走1步、2步、3步和4步到達(dá)的樣本點(diǎn)).表1為G中10個(gè)樣本點(diǎn)的屬性信息.

圖3 帶權(quán)圖數(shù)據(jù)G的拓?fù)浣Y(jié)構(gòu)

圖5與圖6展示了在帶權(quán)圖數(shù)據(jù)G中的樣本點(diǎn)基于ICSMMP方法與LLRWSMM-PCO方法下的相似性矩陣的熱圖.鑒于樣本點(diǎn)間的相似性存在對(duì)稱性，所得到的相似性為關(guān)于對(duì)角線對(duì)稱的矩陣.從圖5、6易知，ICSMMP方法與LLRWSMM-PCO方法在區(qū)分樣本點(diǎn)間拓?fù)湫畔⒌南嗨菩?，捕獲樣本點(diǎn)間的鄰居相似性方面有不錯(cuò)的效果，且2種方法也能夠從數(shù)值上明顯的區(qū)分樣本點(diǎn)間拓?fù)湫畔⒌南嗨菩?但從表2分析，不難發(fā)現(xiàn)，在識(shí)別最相似樣本點(diǎn)方面，基于ICSMMP方法，x2最相似的樣本點(diǎn)為x1，而在LLRWSMM-PCO方法下，x2最相似的樣本點(diǎn)為x4.很明顯x2與x1不僅在屬性信息方面有更高的相似性，在拓?fù)湫畔⒎矫妫瑇2與x1有更多的共享鄰居和更相似的拓?fù)浣Y(jié)構(gòu)，所以它們具有更多潛在的相似性.

圖4 x1與其它樣本點(diǎn)的游走路徑長(zhǎng)度

表1 樣本點(diǎn)的屬性信息

圖5 基于ICSMMP的相似性度量方法

圖6 基于LLRWSMM-PCO的相似性度量方法

表2 G中樣本點(diǎn)最相似的2個(gè)樣本點(diǎn)

圖7與圖8分別是基于余弦距離方法與Jaccard相似性方法下的相似性矩陣的熱圖.從圖中分析，余弦距離方法從單一屬性信息的角度出發(fā)，未考慮拓?fù)湫畔⒌南嗨菩?，使距離較遠(yuǎn)，拓?fù)湫畔⑾嗨贫容^小的樣本點(diǎn)可能被識(shí)別為高相似樣本點(diǎn).如表2的數(shù)據(jù)可知，在余弦距離方法下，樣本點(diǎn)x1與x8，x2與x10，2組樣本點(diǎn)對(duì)利用余弦距離方法計(jì)算得出的相似度很高，但是兩樣本點(diǎn)沒(méi)有共同鄰居，且拓?fù)浣Y(jié)構(gòu)的相似性也很低.Jaccard相似性方法是從拓?fù)湫畔⒔嵌瘸霭l(fā)，計(jì)算樣本點(diǎn)的相似性.該方法能夠很好的捕獲鄰居樣本點(diǎn)的相似性，不足的是，該方法從鄰居樣本點(diǎn)的單一角度出發(fā)，損失了很多非鄰居樣本點(diǎn)的信息，即沒(méi)有共同鄰居的樣本點(diǎn)對(duì)相似度為0，并且沒(méi)有考慮屬性信息，使得大部分樣本點(diǎn)成為一般樣本點(diǎn).

圖7 基于余弦距離的相似性度量方法

圖8 基于Jaccard相似度的相似性度量方法

圖9是分別通過(guò)4種相似性度量方法計(jì)算所得的擁有相同相似度值的樣本點(diǎn)對(duì)所占比值.不難看出，通過(guò)ICSMMP的相似性度量方法計(jì)算得出的100組相似值中，相似度值相同樣本點(diǎn)對(duì)所占比值最低，說(shuō)明該方法得出的相似度值中，不存在多對(duì)樣本點(diǎn)擁有相同的相似性得分，從而能很好的識(shí)別最相似樣本點(diǎn).但是在LLRWSMM-PCO方法、余弦距離方法和Jaccard相似性方法下，存在多對(duì)樣本點(diǎn)擁有相同的相似性得分，這樣可能使得處于同一階段相似性的樣本點(diǎn)不易區(qū)分，不利于后續(xù)圖數(shù)據(jù)聚類(lèi)或識(shí)別圖數(shù)據(jù)中重要樣本點(diǎn)的工作的進(jìn)行.

圖9 同一階段相似度占總相似度比值示意圖

6 結(jié)語(yǔ)

針對(duì)帶權(quán)圖數(shù)據(jù)中樣本點(diǎn)的相似性度量問(wèn)題，從樣本點(diǎn)的屬性信息和拓?fù)湫畔⒔嵌瘸霭l(fā)，構(gòu)建了一種基于改進(jìn)度中心性的樣本點(diǎn)相似性度量方法.實(shí)驗(yàn)結(jié)果表明，該方法不僅能很好的區(qū)分樣本點(diǎn)間關(guān)于拓?fù)湫畔⒌南嗨菩?，捕獲樣本點(diǎn)間鄰居的拓?fù)湎嗨菩裕以跀?shù)值上能夠明顯的區(qū)分各個(gè)樣本點(diǎn)間的相似性得分.