基于聚類和決策樹(shù)的鏈路預(yù)測(cè)方法

楊妮亞 彭 濤,2 劉 露

1(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 長(zhǎng)春 130012) 2 (符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué)) 長(zhǎng)春 130012) (yangny15@mails.jlu.edu.cn)

基于聚類和決策樹(shù)的鏈路預(yù)測(cè)方法

楊妮亞1彭 濤1,2劉 露1

1(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 長(zhǎng)春 130012)2(符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué)) 長(zhǎng)春 130012) (yangny15@mails.jlu.edu.cn)

鏈路預(yù)測(cè)是數(shù)據(jù)挖掘研究的主要問(wèn)題之一.由于網(wǎng)絡(luò)的復(fù)雜性、數(shù)據(jù)的多樣性，根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)及已有信息對(duì)異質(zhì)網(wǎng)絡(luò)中的不同類型的數(shù)據(jù)進(jìn)行鏈路預(yù)測(cè)的問(wèn)題也變得更加復(fù)雜.針對(duì)雙類型異質(zhì)信息網(wǎng)絡(luò)，提出了一種基于聚類和決策樹(shù)的鏈路預(yù)測(cè)方法CDTLinks.通過(guò)將網(wǎng)絡(luò)中2種類型對(duì)象互為特征的方法得到對(duì)象的特征表示，并分別進(jìn)行聚類.對(duì)于雙類型異質(zhì)網(wǎng)絡(luò)提出了3種啟發(fā)式規(guī)則來(lái)構(gòu)建決策樹(shù)，根據(jù)信息增益來(lái)選擇樹(shù)中不同分支.最后，根據(jù)聚簇分布結(jié)果以及決策樹(shù)模型來(lái)判斷任意2個(gè)不同類型節(jié)點(diǎn)之間是否存在鏈接.另外，定義了潛在鏈接節(jié)點(diǎn)并引入層數(shù)的概念，在降低算法運(yùn)行時(shí)間的同時(shí)提高了準(zhǔn)確率.在DBLP和AMiner數(shù)據(jù)集上驗(yàn)證了提出的CDTlinks方法,結(jié)果表明:在雙類型異質(zhì)網(wǎng)絡(luò)中，CDTlinks模型能夠有效地進(jìn)行鏈路預(yù)測(cè).

鏈路預(yù)測(cè)；聚類；決策樹(shù)；異質(zhì)信息網(wǎng)絡(luò)；啟發(fā)式規(guī)則

異質(zhì)信息網(wǎng)絡(luò)挖掘是數(shù)據(jù)挖掘的一類重要問(wèn)題.預(yù)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的鏈接關(guān)系具有重要的研究?jī)r(jià)值.鏈路預(yù)測(cè)旨在根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)和已有信息發(fā)現(xiàn)并且還原網(wǎng)絡(luò)中缺失的信息，或者預(yù)測(cè)未來(lái)節(jié)點(diǎn)之間可能存在的關(guān)系.節(jié)點(diǎn)間不同的鏈接關(guān)系對(duì)網(wǎng)絡(luò)分析有重要的現(xiàn)實(shí)意義[1].鏈路預(yù)測(cè)也有廣泛的應(yīng)用，比如通過(guò)預(yù)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的關(guān)系，在社交網(wǎng)絡(luò)中進(jìn)行朋友推薦[2]、識(shí)別隱藏和虛假的鏈接對(duì)網(wǎng)絡(luò)進(jìn)行重構(gòu)[3]以及社團(tuán)劃分[4]等.

在異質(zhì)信息網(wǎng)絡(luò)中，不同類型的節(jié)點(diǎn)和鏈接包含著豐富的語(yǔ)義關(guān)系，使得鏈路預(yù)測(cè)變得更加復(fù)雜.例如文獻(xiàn)信息網(wǎng)絡(luò)包含會(huì)議/期刊、作者、論文等多種類型的節(jié)點(diǎn)以及多種鏈接關(guān)系.傳統(tǒng)的異質(zhì)信息網(wǎng)絡(luò)鏈路預(yù)測(cè)是通過(guò)分析整個(gè)網(wǎng)絡(luò)對(duì)象之間的鏈接關(guān)系找到虛假的鏈接，或者對(duì)未來(lái)的鏈接進(jìn)行預(yù)測(cè).這使得異質(zhì)信息網(wǎng)絡(luò)中鏈路預(yù)測(cè)變得十分復(fù)雜并且效率較低.

受到以上方法的啟發(fā)，本文提出一種雙類型異質(zhì)信息網(wǎng)絡(luò)鏈路預(yù)測(cè)的方法.該方法主要解決4個(gè)問(wèn)題：1)如何在簡(jiǎn)化異質(zhì)信息網(wǎng)絡(luò)的同時(shí)保留主要語(yǔ)義信息；2)如何構(gòu)建決策樹(shù)模型；3)如何選取合適的屬性作為決策樹(shù)的決策節(jié)點(diǎn)；4)如何結(jié)合不同類型節(jié)點(diǎn)聚簇分布情況以及決策樹(shù)進(jìn)行鏈路預(yù)測(cè).

為了解決上述問(wèn)題，我們提出了一種雙類型異質(zhì)信息網(wǎng)絡(luò)中基于聚類和決策樹(shù)的鏈路預(yù)測(cè)方法.該方法提取異質(zhì)網(wǎng)絡(luò)中2種關(guān)鍵類型的對(duì)象，根據(jù)2種類型節(jié)點(diǎn)之間存在的鏈接關(guān)系構(gòu)造鄰接矩陣，采用2種類型對(duì)象互為特征的方法，對(duì)2種類型的對(duì)象分別進(jìn)行聚類.這樣保留主要語(yǔ)義關(guān)系的同時(shí)對(duì)節(jié)點(diǎn)間的鏈接進(jìn)行分析.定義了3個(gè)啟發(fā)式規(guī)則作為構(gòu)建決策樹(shù)的候選屬性，選取信息增益最大的規(guī)則作為決策樹(shù)的決策節(jié)點(diǎn)來(lái)構(gòu)造決策樹(shù)模型.最后，根據(jù)不同類型節(jié)點(diǎn)間聚類分布情況以及決策樹(shù)模型對(duì)2種不同類型節(jié)點(diǎn)進(jìn)行鏈路預(yù)測(cè).以文獻(xiàn)信息網(wǎng)絡(luò)為例，我們通過(guò)分析網(wǎng)絡(luò)中作者與期刊/會(huì)議之間的鏈接關(guān)系，對(duì)作者和期刊/會(huì)議這2種類型的節(jié)點(diǎn)進(jìn)行聚類，根據(jù)3個(gè)啟發(fā)式規(guī)則構(gòu)建決策樹(shù)來(lái)預(yù)測(cè)未來(lái)作者和期刊/會(huì)議之間可能出現(xiàn)的鏈接.

本文的主要貢獻(xiàn)有5個(gè)方面：1)提出了一種雙類型異質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測(cè)方法，對(duì)2種類型節(jié)點(diǎn)之間的關(guān)系進(jìn)行預(yù)測(cè)；2)采用2種類型對(duì)象互為特征的方法，對(duì)2種類型的對(duì)象分別進(jìn)行聚類；3)定義了3種啟發(fā)式規(guī)則作為構(gòu)建決策樹(shù)的候選屬性；4)分析不同類型節(jié)點(diǎn)的聚類結(jié)果和節(jié)點(diǎn)之間的鏈接關(guān)系，得到?jīng)Q策樹(shù)的屬性，構(gòu)造決策樹(shù)模型；5)在不同數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn).結(jié)果表明：本文提出的雙類型異質(zhì)信息網(wǎng)絡(luò)鏈路預(yù)測(cè)方法可以有效地預(yù)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的鏈接關(guān)系.

1 相關(guān)工作

鏈路預(yù)測(cè)是數(shù)據(jù)挖掘中一個(gè)關(guān)鍵的問(wèn)題，在同質(zhì)網(wǎng)絡(luò)中，研究者們做了很多深入的研究.Bliss等人[5]通過(guò)應(yīng)用協(xié)方差矩陣自適應(yīng)演化策略(CMA-ES)來(lái)優(yōu)化在16個(gè)鄰域和節(jié)點(diǎn)相似性索引的線性組合中使用的權(quán)重，提出了一種預(yù)測(cè)未來(lái)鏈路的方法；Scellato等人[6]描述了一個(gè)監(jiān)督學(xué)習(xí)框架，通過(guò)分析鏈路節(jié)點(diǎn)之間的關(guān)系來(lái)預(yù)測(cè)新的朋友和朋友的朋友之間的聯(lián)系；Zhu[7]提出了一種非參數(shù)潛在特征關(guān)系模型的最大余量學(xué)習(xí)方法，該方法可以擴(kuò)展到具有數(shù)百萬(wàn)實(shí)體和數(shù)千萬(wàn)個(gè)正鏈接的大規(guī)模實(shí)際網(wǎng)絡(luò)中；Schifanella等人[8]引入一個(gè)空模型，保留用戶的活動(dòng)，同時(shí)消除當(dāng)?shù)氐南嚓P(guān)性.實(shí)驗(yàn)結(jié)果證明由語(yǔ)義相似性構(gòu)建的社會(huì)網(wǎng)絡(luò)能夠更準(zhǔn)確地捕捉到實(shí)際的鏈路關(guān)系.

由于網(wǎng)絡(luò)中充斥著許多不同類型的對(duì)象和鏈接關(guān)系，異質(zhì)信息網(wǎng)絡(luò)中的鏈路預(yù)測(cè)問(wèn)題逐漸引起了研究者們的關(guān)注.Zeng等人[9]構(gòu)建基于元路徑的異構(gòu)網(wǎng)絡(luò)的投資行為預(yù)測(cè)模型，該模型考慮與特定投資者的投資行為相關(guān)聯(lián)的多個(gè)實(shí)體和關(guān)系類型，投資行為預(yù)測(cè)模型為元路徑提供了一個(gè)有效的相似性度量函數(shù)；Huang等人[10]使用元路徑描述不同類型的節(jié)點(diǎn)和關(guān)系的不同語(yǔ)義，提出了一種基于元路徑異構(gòu)信息網(wǎng)絡(luò)鏈路預(yù)測(cè)模型；Lakshmi等人[11]為提高效率，提出了異質(zhì)信息網(wǎng)絡(luò)中鏈路預(yù)測(cè)的并行方法，利用現(xiàn)有的多關(guān)系鏈接預(yù)測(cè)以及社區(qū)發(fā)現(xiàn)算法，在每個(gè)社區(qū)計(jì)算多關(guān)系鏈接預(yù)測(cè)分?jǐn)?shù)；Aggarwal等人[12]提出了一個(gè)有效的兩級(jí)方案，為了將網(wǎng)絡(luò)動(dòng)態(tài)性和時(shí)間敏感度相結(jié)合，使用了宏觀和微觀決策；Lee等人[13]對(duì)存在的文獻(xiàn)網(wǎng)絡(luò)進(jìn)行修改并且突出其中重要的關(guān)系，將隨機(jī)游走算法應(yīng)用到修改后的網(wǎng)絡(luò)鏈路預(yù)測(cè)問(wèn)題.

研究者們?cè)谕|(zhì)網(wǎng)絡(luò)和多類型異質(zhì)網(wǎng)絡(luò)上做了很多的鏈路預(yù)測(cè)方面的研究，但關(guān)于雙類型異質(zhì)網(wǎng)絡(luò)鏈路預(yù)測(cè)方法的研究還很少.在很多情況下，與多類型網(wǎng)絡(luò)相比較來(lái)說(shuō)，雙類型網(wǎng)絡(luò)在模型表示和計(jì)算的過(guò)程中相對(duì)簡(jiǎn)單.針對(duì)上述情況，本文針對(duì)雙類型異質(zhì)信息網(wǎng)絡(luò)提出了鏈路預(yù)測(cè)方法.

2 問(wèn)題定義

在本節(jié)中，我們先介紹鏈路預(yù)測(cè)方法需要用到的一些基本概念，再給出雙類型異質(zhì)信息網(wǎng)絡(luò)中鏈路預(yù)測(cè)的形式化定義.

定義1. 異質(zhì)信息網(wǎng)絡(luò)[14].給定一個(gè)有向圖G=(V,E)，V是節(jié)點(diǎn)集，E是邊集.存在一個(gè)節(jié)點(diǎn)類型映射函數(shù)τ:V→A，一個(gè)邊類型映射函數(shù)φ:E→R，其中，每個(gè)節(jié)點(diǎn)v∈V都屬于一個(gè)特定的對(duì)象類τ(v)∈A，每條邊e∈E都屬于一個(gè)特定的關(guān)系類φ(e)∈E.若網(wǎng)絡(luò)中節(jié)點(diǎn)類型數(shù)|A|>1或邊類型數(shù)量|R|>1，則該網(wǎng)絡(luò)被稱為異質(zhì)信息網(wǎng)絡(luò)，反之，為同質(zhì)信息網(wǎng)絡(luò).

定義2. 雙類型異質(zhì)信息網(wǎng)絡(luò)[14].給定一個(gè)異質(zhì)信息網(wǎng)絡(luò)G=(X∪Y,W).X和Y分別代表2種不同類型的對(duì)象集合，W代表對(duì)象之間的鏈接關(guān)系矩陣，其中，WXY(i,j)=pij(i=1,2,…,m;j=1,2,…,n).對(duì)于任意xi∈X，yj∈Y，pij為節(jié)點(diǎn)xi與節(jié)點(diǎn)yj之間鏈接的數(shù)量，因此，存在xi=(pi1,pi2,…,pin)，yj=(pj1,pj2,…,pjm).

定義3. 潛在鏈接節(jié)點(diǎn).給定一個(gè)雙類型異質(zhì)網(wǎng)絡(luò)G=(X∪Y,W)，且存在節(jié)點(diǎn)yj,yk∈Y，若存在節(jié)點(diǎn)xi∈X，使得xi與yj，xi與yk之間均存在鏈接關(guān)系.則yj與yk互為直接鏈接節(jié)點(diǎn)，表示為yj∈LinkNode(yk).若存在yi與yj互為直接鏈接節(jié)點(diǎn)，yj與yk互為直接鏈接節(jié)點(diǎn)，且yi與yk不存在直接鏈接關(guān)系；那么，yi與yk互為潛在鏈接節(jié)點(diǎn)(latent link node)，yi與yk的關(guān)系表示為yi∈LatentLinkNode(yk).

此時(shí)，節(jié)點(diǎn)yi與節(jié)點(diǎn)yk之間的鏈接關(guān)系可表示為yi-yj-yk，yi到y(tǒng)k的鏈接個(gè)數(shù)為2.yi與yk也互為2層潛在鏈接節(jié)點(diǎn).隨著鏈接關(guān)系中鏈接數(shù)量的增加，節(jié)點(diǎn)間的相近關(guān)系也隨之變化，因此，我們引入n層潛在鏈接節(jié)點(diǎn)的概念來(lái)分析異質(zhì)網(wǎng)絡(luò)中存在鏈路的可能性，即如果yi與yk之間存在n個(gè)鏈接，那么它們互為n層潛在鏈接節(jié)點(diǎn).下面我們給出雙類型異質(zhì)網(wǎng)絡(luò)中鏈路預(yù)測(cè)問(wèn)題的形式化定義.

問(wèn)題1. 雙類型異質(zhì)網(wǎng)絡(luò)中的鏈路預(yù)測(cè).給定一個(gè)雙類型異質(zhì)網(wǎng)絡(luò)G=(X∪Y,W)，對(duì)于網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)xi∈X，yj∈Y，根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的聚類結(jié)果以及決策樹(shù)的分析結(jié)果，預(yù)測(cè)xi與yj之間是否存在鏈接.

3 雙類型異質(zhì)網(wǎng)絡(luò)聚類過(guò)程

在用決策樹(shù)進(jìn)行鏈路預(yù)測(cè)之前，根據(jù)雙類型網(wǎng)絡(luò)中的信息對(duì)X類型節(jié)點(diǎn)以及Y類型節(jié)點(diǎn)進(jìn)行聚類.雙類型異質(zhì)信息網(wǎng)絡(luò)是一種特殊的異質(zhì)信息網(wǎng)絡(luò)，它僅包含2種類型的對(duì)象，在對(duì)X類型節(jié)點(diǎn)進(jìn)行聚類時(shí)，以Y類型節(jié)點(diǎn)作為對(duì)應(yīng)的X類型節(jié)點(diǎn)的特征.同樣，對(duì)Y類型節(jié)點(diǎn)進(jìn)行聚類時(shí)，以X類型節(jié)點(diǎn)作為對(duì)應(yīng)的Y類型節(jié)點(diǎn)的特征.采用2種對(duì)象互為特征的方法來(lái)得到每個(gè)節(jié)點(diǎn)的特征表示.以文獻(xiàn)信息網(wǎng)絡(luò)為例，2種節(jié)點(diǎn)類型分別為會(huì)議和作者，將會(huì)議作為目標(biāo)對(duì)象.因此，一個(gè)會(huì)議可以表示為向量xi=(pi1,pi2,…,pin)，其中，pij表示在會(huì)議i上作者j發(fā)表的論文數(shù).如圖1所示，會(huì)議x1表示為x1=(2,2,0,0)，會(huì)議x2表示為x2=(0,1,2,0)，會(huì)議x3表示為x3=(0,0,3,1).將每個(gè)作者在這個(gè)會(huì)議上發(fā)表論文的數(shù)作為特征值，利用余弦相似度量計(jì)算2個(gè)會(huì)議的相似程度.則x1和x2的相似程度為

得到X類型對(duì)象和Y類型對(duì)象的特征表示后，分別進(jìn)行聚類.以Y類型對(duì)象為特征，Y和X兩種類型對(duì)象之間的鏈接權(quán)值作為特征值對(duì)X類型對(duì)象進(jìn)行聚類.通過(guò)計(jì)算聚類中心與每個(gè)對(duì)象的距離反復(fù)對(duì)聚類進(jìn)行調(diào)整，使得聚類內(nèi)部的誤差平方和[15]最小，從而得到X類型對(duì)象的K1個(gè)聚類.同樣，以X類型對(duì)象為特征，X和Y兩種類型對(duì)象之間的鏈接權(quán)值作為特征值對(duì)Y類型對(duì)象進(jìn)行聚類.通過(guò)計(jì)算聚類中心與每個(gè)對(duì)象的距離反復(fù)對(duì)聚類進(jìn)行調(diào)整，得到Y(jié)類型對(duì)象的K2個(gè)聚類.

Fig. 1 An example of relationship between the conference and the author圖1 會(huì)議和作者的關(guān)系實(shí)例

4 決策樹(shù)的構(gòu)建過(guò)程

在第3節(jié)中，我們得到了2種類型對(duì)象的聚類結(jié)果.本節(jié)我們介紹如何構(gòu)建決策樹(shù)來(lái)預(yù)測(cè)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的鏈接關(guān)系.

給定一個(gè)雙類型異質(zhì)信息網(wǎng)絡(luò)G=(X∪Y,W)，對(duì)于網(wǎng)絡(luò)中任意2個(gè)節(jié)點(diǎn)xi∈X，yj∈Y，根據(jù)以下3條規(guī)則來(lái)判斷xi與yj之間是否存在鏈接.若xi與yj存在鏈接，則函數(shù)linkpredict(xi,yj)=1；反之，linkpredict(xi,yj)=0.

規(guī)則1.xi所在聚簇為Ck，若節(jié)點(diǎn)yj與xi同聚簇的節(jié)點(diǎn)之間存在鏈接，那么，xi與yj之間可能存在鏈接.該規(guī)則可表示為

?x,xi∈X, ?yj∈Y,x,xi∈Ck，
(x,yj)∈E?linkpredict(xi,yj)=1.

(1)

規(guī)則2. 若節(jié)點(diǎn)xi的直接鏈接節(jié)點(diǎn)或潛在鏈接節(jié)點(diǎn)與yj存在鏈接，那么，xi與yj之間可能存在鏈接.該規(guī)則可表示為

?x,xi∈X, ?yj∈Y，
x∈LinkNode(xi)∪LatentLinkNode(xi)，
(x,yj)∈E?linkpredict(xi,yj)=1.

(2)

規(guī)則3.yj所在聚簇為Cl，若節(jié)點(diǎn)xi與yj同聚簇的節(jié)點(diǎn)之間存在鏈接，那么，xi與yj之間可能存在鏈接.該規(guī)則可表示為

?y,yj∈Y, ?xi∈X,y,yj∈Cl，
(xi,y)∈E?linkpredict(xi,yj)=1.

(3)

我們應(yīng)用以上3條規(guī)則來(lái)預(yù)測(cè)雙類型異質(zhì)網(wǎng)絡(luò)中的鏈接，以文獻(xiàn)信息網(wǎng)絡(luò)為例，我們將會(huì)議名作為X類型節(jié)點(diǎn)，將作者名作為Y類型節(jié)點(diǎn)，并將它們之間的鏈接關(guān)系存儲(chǔ)在鄰接矩陣W中.如果一個(gè)作者yj與會(huì)議xi同領(lǐng)域的會(huì)議間存在鏈接，那么，該作者yj與會(huì)議xi可能存在鏈接(規(guī)則1).如果一個(gè)作者與yj與會(huì)議xi的直接鏈接節(jié)點(diǎn)或潛在鏈接節(jié)點(diǎn)之間存在鏈接，那么，該作者yj與會(huì)議xi可能存在鏈接(規(guī)則2).如果一個(gè)會(huì)議xi與作者yj同領(lǐng)域的作者間存在鏈接，那么，該會(huì)議xi與作者yj可能存在鏈接(規(guī)則3).

本文把3條規(guī)則作為決策樹(shù)的候選屬性集Pro.在構(gòu)造決策樹(shù)的過(guò)程中，將信息增益[16]作為選擇候選屬性的度量指標(biāo)來(lái)衡量3條規(guī)則哪一條可以更好地進(jìn)行鏈路預(yù)測(cè).設(shè)D是數(shù)據(jù)集，根據(jù)數(shù)據(jù)的類別對(duì)D進(jìn)行劃分，其中類別由存在鏈接和不存在鏈接2部分組成.存在鏈接的類別數(shù)據(jù)記為D1，不存在鏈接的類別數(shù)據(jù)記為D2，則D的熵表示為

(4)

(5)

其中,pi表示第i個(gè)類別在整個(gè)訓(xùn)練元組中出現(xiàn)的概率.假設(shè)將訓(xùn)練元組D按屬性attr進(jìn)行劃分，其中attr∈Pro，則attr對(duì)D劃分的期望信息[16]為

(6)

則信息增益[16]為兩者之間的差值：

gain(attr)=info(D)-infoattr(D).

(7)

每次分裂時(shí)，計(jì)算候選屬性attr中每個(gè)屬性的增益值，選擇增益值最大的屬性作為決策樹(shù)的分支，構(gòu)造決策樹(shù).構(gòu)造決策樹(shù)并使用決策樹(shù)進(jìn)行鏈路預(yù)測(cè)的示意圖，如圖2所示.在構(gòu)造決策樹(shù)的過(guò)程中，計(jì)算每個(gè)屬性的信息增益，選擇信息增益值較大的屬性作為決策樹(shù)的分支.在鏈路預(yù)測(cè)的過(guò)程中，判斷對(duì)象x與對(duì)象y之間是否存在鏈接，若規(guī)則1對(duì)應(yīng)的信息增益最大，則用圖2左側(cè)分支進(jìn)行鏈路預(yù)測(cè).算法1描述了決策樹(shù)的構(gòu)造過(guò)程.

Fig. 2 Illustration of constructing decision tree圖2 構(gòu)造決策樹(shù)示意圖

算法1. 決策樹(shù)構(gòu)造算法

輸入: 雙類型網(wǎng)絡(luò)G={(X∪Y),W}、一種類型對(duì)象X={x1,x2,…,xm}、另一種類型對(duì)象Y={y1,y2,…,yn}、X與Y之間的鏈接關(guān)系矩陣W，其中，WXY(i,j)=pij(i=1,2,…,m;j=1,2,…,n),加入WN(由G中節(jié)點(diǎn)構(gòu)造的不存在的鏈接矩陣，占總體鏈接的10%)，進(jìn)行鏈路預(yù)測(cè)的X類型對(duì)象x和Y類型對(duì)象y;

輸出: 決策樹(shù).

① for eachp∈(W+WN) (i=1,2,…,m;j=1,2,…,n)

② 鏈接p兩邊節(jié)點(diǎn)記作m和n，m和n按照3個(gè)啟發(fā)式規(guī)則得到每一個(gè)訓(xùn)練數(shù)據(jù)在各個(gè)屬性的對(duì)應(yīng)值(值為Yes/No)；

③ end for

④ for eachattr∈Pro(Pro為決策樹(shù)屬性的集合)

⑤ 計(jì)算attr的信息增益；

⑦attr作為決策樹(shù)的分支；

⑧Pro=Pro-attr.

⑨ end if

⑩ end for

5 基于聚類和決策樹(shù)的鏈路預(yù)測(cè)方法

通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)以及網(wǎng)絡(luò)中已有的信息來(lái)預(yù)測(cè)節(jié)點(diǎn)未來(lái)的鏈接關(guān)系是鏈路預(yù)測(cè)的主要任務(wù).網(wǎng)絡(luò)中存在著多種類型的節(jié)點(diǎn)以及多種類型的鏈接關(guān)系，根據(jù)不同節(jié)點(diǎn)間的關(guān)聯(lián)關(guān)系和語(yǔ)義關(guān)系來(lái)預(yù)測(cè)鏈接能夠幫助研究者更好地分析網(wǎng)絡(luò)中的數(shù)據(jù).因此，本節(jié)中提出了一種雙類型異質(zhì)網(wǎng)絡(luò)中基于聚類和決策樹(shù)的鏈路預(yù)測(cè)方法.

首先，我們提取異質(zhì)網(wǎng)絡(luò)中2種不同類型的對(duì)象以及對(duì)象間的鏈接關(guān)系，通過(guò)對(duì)象間互為特征的方法得到雙類型對(duì)象的特征表示，并將2種類型對(duì)象進(jìn)行聚類.得到不同類型對(duì)象的聚簇分布后，定義了3個(gè)規(guī)則作為構(gòu)建決策樹(shù)的候選屬性，選取信息增益較大的規(guī)則來(lái)構(gòu)建決策樹(shù).最后，將需要判斷的節(jié)點(diǎn)輸入到?jīng)Q策樹(shù)中，根據(jù)決策樹(shù)以及聚簇分布情況來(lái)判斷任意2個(gè)不同類型節(jié)點(diǎn)之間是否存在鏈接.

下面我們給出一個(gè)雙類型文獻(xiàn)信息網(wǎng)絡(luò)進(jìn)行鏈路預(yù)測(cè)的實(shí)例，如圖3所示.2種類型節(jié)點(diǎn)分為作者和會(huì)議名，圖3中已知對(duì)象間已有的鏈接以及對(duì)象的聚類分布情況，目標(biāo)為預(yù)測(cè)下一時(shí)刻Andy與SIGMOD間是否存在鏈接.Andy與Bob與為合作作者，Bob與Cindy互為合作作者，那么，Bob與Andy互為二層潛在鏈接作者.Cindy和David在同一聚類C1中，那么，David與Andy的合作作者Cindy在同一聚類中.根據(jù)規(guī)則2和規(guī)則1，如果David與SIGMOD之間存在鏈接，那么Andy與SIGMOD之間很可能存在鏈接.會(huì)議SIGMOD與VLDB在同一聚類中，根據(jù)規(guī)則1，如果Andy與VLDB之間存在鏈接，那么Andy與SIGMOD之間很可能存在鏈接.在圖3中，David與VLDB之間存在鏈接.所以，根據(jù)規(guī)則3，David與SIGMOD之間很可能存在鏈接.根據(jù)規(guī)則1，Cindy與SIGMOD之間很可能存在鏈接.根據(jù)規(guī)則2，Andy與SIGMOD之間很可能存在鏈接.

Fig. 3 An example of link prediction for bibliographic information network圖3 文獻(xiàn)信息網(wǎng)絡(luò)鏈路預(yù)測(cè)實(shí)例

6 實(shí)驗(yàn)與結(jié)果

在本節(jié)中，我們使用本文提出的聚類和決策樹(shù)方法構(gòu)建一個(gè)面向雙類型異質(zhì)網(wǎng)絡(luò)的鏈路預(yù)測(cè)模型，并在2個(gè)數(shù)據(jù)集上進(jìn)行測(cè)試了我們的方法.

6.1度量標(biāo)準(zhǔn)

為了評(píng)估鏈路預(yù)測(cè)模型CDTLinks的效果，我們使用準(zhǔn)確率Accuracy[17]、精確率Precision[18]、召回率Recall[19]和F-Measure[20]4種度量標(biāo)準(zhǔn)來(lái)檢測(cè)鏈路預(yù)測(cè)模型的性能.精確率和召回率分別反映了模型找對(duì)和找全鏈接的能力.我們將鏈路預(yù)測(cè)的結(jié)果分為有鏈接和無(wú)鏈接2種情況.針對(duì)2種情況，分別給出相應(yīng)的精確率和召回率.對(duì)于有鏈接的數(shù)據(jù)，精確率是被正確識(shí)別的鏈接數(shù)占被識(shí)別為有鏈接的數(shù)據(jù)的比例.召回率，也稱查全率，是被正確檢測(cè)出有鏈接的數(shù)據(jù)占實(shí)際存在鏈接數(shù)據(jù)的比例.有鏈接情況精確度和召回率的計(jì)算為

(8)

(9)

其中，CE表示被鏈路模型判斷為有鏈接的數(shù)據(jù)集合，TE表示測(cè)試集中存在的有鏈接數(shù)據(jù)的集合.對(duì)于無(wú)鏈接的數(shù)據(jù)，精確率指被正確識(shí)別為無(wú)鏈接的對(duì)象數(shù)量占被識(shí)別為無(wú)鏈接的數(shù)據(jù)的比例.召回率指被正確識(shí)別為無(wú)鏈接的對(duì)象數(shù)量占實(shí)際為無(wú)鏈接數(shù)據(jù)的比例.無(wú)鏈接情況精確度和召回率的計(jì)算為

(10)

(11)

同樣，CN表示被鏈路模型判斷為無(wú)鏈接的數(shù)據(jù)集合，TN表示測(cè)試集中存在的無(wú)鏈接數(shù)據(jù)的集合.Precision和Recall不成正相關(guān)，我們采用這2個(gè)指標(biāo)的調(diào)和平均值F-Measure來(lái)作為評(píng)估標(biāo)準(zhǔn)，F(xiàn)-Measure的計(jì)算為

(12)

β是一個(gè)反應(yīng)精確度和召回率相對(duì)重要程度的權(quán)值，若β>1，則召回率的重要性大于準(zhǔn)確率，反之亦然.在本文中將設(shè)β=1.

Accuracy作為度量標(biāo)準(zhǔn)來(lái)衡量所有數(shù)據(jù)是否和真實(shí)類別一致，即衡量模型作出正確決定的能力.Accuracy的公式定義為

(13)

其中，TP表示有鏈接數(shù)據(jù)集中被正確識(shí)別為有鏈接數(shù)據(jù)的數(shù)量，TN表示無(wú)鏈接數(shù)據(jù)集中被正確識(shí)別為無(wú)鏈接數(shù)據(jù)的數(shù)量，|TE|和|TN|之和為所有數(shù)據(jù)總數(shù).

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

在本文中，我們使用2個(gè)真實(shí)的信息網(wǎng)絡(luò)：DBLP*http://dblp.org/網(wǎng)絡(luò)和AMiner[21]網(wǎng)絡(luò).

1) DBLP數(shù)據(jù)集是異質(zhì)網(wǎng)絡(luò)中常用的實(shí)驗(yàn)數(shù)據(jù)，其中的數(shù)據(jù)類型包括會(huì)議/期刊、作者、發(fā)表時(shí)間等等.提取期刊、作者以及二者之間的鏈接信息作為實(shí)驗(yàn)數(shù)據(jù).將出現(xiàn)在實(shí)驗(yàn)中的期刊人工標(biāo)記它所屬的領(lǐng)域.在實(shí)驗(yàn)中，讀取其中的20 000條數(shù)據(jù)，出現(xiàn)22個(gè)期刊、31 181個(gè)作者、892 983條期刊與作者的鏈接關(guān)系，人工標(biāo)記期刊所屬的領(lǐng)域.

2) AMiner數(shù)據(jù)集是社會(huì)網(wǎng)絡(luò)挖掘常用的數(shù)據(jù)集，其中包括作者、會(huì)議、主題等信息.本文使用aminer-topic-data-pubs.xml文件中的數(shù)據(jù).對(duì)AMiner數(shù)據(jù)集進(jìn)行了預(yù)處理，提取出6類會(huì)議信息.以提取出的會(huì)議，作者以及會(huì)議與作者之間的鏈接信息作為實(shí)驗(yàn)數(shù)據(jù)，其中包括33個(gè)期刊、21 381個(gè)作者、836 524條期刊與作者的鏈接關(guān)系.

Fig. 4 The performance of CDLinks in DBLP with different μ圖4 CDLinks在DBLP數(shù)據(jù)集中μ變化時(shí)的性能

6.3參數(shù)分析及結(jié)果

本節(jié)中，我們通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證CDTLinks鏈路模型.首先，分析潛在鏈接節(jié)點(diǎn)的層數(shù)μ對(duì)鏈路模型的影響.對(duì)DBLP數(shù)據(jù)集和AMiner數(shù)據(jù)集，判斷作者和期刊之間是否存在鏈接.其中，待預(yù)測(cè)作者的合作作者信息對(duì)鏈路預(yù)測(cè)具有很重要的意義.如果待預(yù)測(cè)作者的直接鏈接作者與待預(yù)測(cè)期刊之間有鏈接關(guān)系，那么待預(yù)測(cè)的作者和期刊之間存在鏈接關(guān)系的可能性很高.如果待預(yù)測(cè)作者的二層潛在鏈接合作作者與待預(yù)測(cè)期刊之間有鏈接關(guān)系，那么待預(yù)測(cè)的作者和期刊之間存在鏈接關(guān)系的可能性相對(duì)較低.同時(shí)，搜索二層潛在作者信息所花費(fèi)的時(shí)間相比于搜索直接鏈接作者信息所花費(fèi)的時(shí)間要多.理論上，異質(zhì)信息網(wǎng)絡(luò)中的潛在鏈接節(jié)點(diǎn)層數(shù)可以無(wú)限大.但是，隨著搜索潛在節(jié)點(diǎn)信息的層數(shù)的增加，鏈路預(yù)測(cè)結(jié)果的準(zhǔn)確率降低，花費(fèi)的時(shí)間增加.

圖4和圖5分別給出了隨著潛在鏈接節(jié)點(diǎn)層數(shù)μ的增加，在DBLP和AMiner數(shù)據(jù)集上Accuracy,Precision,Recall和F-Measure的變化曲線.從圖4和圖5中可以看出，在2個(gè)數(shù)據(jù)集中，Accuracy,Precision,Recall和F-Measure在μ=3時(shí)取得峰值.當(dāng)μ<3時(shí)，隨著μ的增加，鏈路預(yù)測(cè)的Accuracy,Precision,Recall和F-Measure增加.當(dāng)μ>3時(shí)，Accuracy,Precision,Recall和F-Measure不再增加.這是因?yàn)殡S著潛在鏈接搜索層數(shù)的增加，從網(wǎng)絡(luò)鏈接中獲得的信息越多，CDTLinks表現(xiàn)出的性能也隨著增加.當(dāng)增加到一個(gè)峰值時(shí)，隨著搜索層數(shù)的增加，導(dǎo)致錯(cuò)誤或冗余的信息過(guò)多，CDTLinks表現(xiàn)出的性能反而下降.

Fig. 5 The performance of CDLinks in AMiner with different μ圖5 CDLinks在AMiner數(shù)據(jù)集中μ變化時(shí)的性能

圖6給出了隨著潛在鏈接節(jié)點(diǎn)層數(shù)μ的增加，CDTLinks運(yùn)行時(shí)間的變化.從圖6中可以看出，當(dāng)μ>3時(shí)，算法的迭代時(shí)間顯著增加.在實(shí)驗(yàn)中，網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量為n，鏈接的數(shù)量為m，聚類個(gè)數(shù)為k，決策樹(shù)特征的數(shù)量為p.因此，聚類部分計(jì)算的時(shí)間復(fù)雜度為O(nk)；鏈接分析部分計(jì)算的時(shí)間復(fù)雜度為O(nμ)；決策樹(shù)計(jì)算部分的時(shí)間復(fù)雜度為O(pm).隨著潛在鏈接節(jié)點(diǎn)層數(shù)的增加，算法的運(yùn)行時(shí)間增加.綜合考慮算法的性能和時(shí)間上的開(kāi)銷，我們將潛在鏈接節(jié)點(diǎn)層數(shù)μ設(shè)為3.

Fig. 6 Running time of μ on DBLP and AMiner datasets圖6 不同的μ在DBLP和AMiner數(shù)據(jù)集中的運(yùn)行時(shí)間

Fig. 7 Performance comparision of three link prediction methods on DBLP dataset圖7 3種鏈路預(yù)測(cè)方法在DBLP數(shù)據(jù)集上性能的比較

Fig. 8 Performance comparision of three link prediction methods on AMiner dataset圖8 3種鏈路預(yù)測(cè)方法在AMiner數(shù)據(jù)集中的性能比較

我們將提出的CDTLinks鏈路預(yù)測(cè)方法與2個(gè)基線算法進(jìn)行比較.其中，CDTLinks方法中的潛在鏈接節(jié)點(diǎn)層數(shù)μ=3.如圖7和圖8所示，通過(guò)Accuracy,Precision,Recall和F-Measure值，在2個(gè)數(shù)據(jù)集DBLP和AMiner上對(duì)我們提出的CDTLinks鏈路預(yù)測(cè)方法進(jìn)行測(cè)試.計(jì)算CDTLinks方法的Accuracy，Precision，Recall和F-Measure值，我們將Precision設(shè)置為(PrecisionE+PrecisionN)/2,將Recall設(shè)置為(RecallE+RecallN)/2.將我們提出的方法CDTLinks與MRCLinks[11]，MBLinks[13]相比.在DBLP和AMiner兩個(gè)數(shù)據(jù)集進(jìn)行鏈路預(yù)測(cè)的實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，我們給出的CDTLinks方法優(yōu)于MRCLinks[11]，MBLinks[13]方法.該方法提取異質(zhì)網(wǎng)絡(luò)中2種關(guān)鍵類型的對(duì)象，根據(jù)2種類型節(jié)點(diǎn)之間存在的鏈接關(guān)系構(gòu)造鄰接矩陣.采用2種類型對(duì)象互為特征的方法，對(duì)2種類型的對(duì)象分別進(jìn)行聚類.這樣保留主要語(yǔ)義關(guān)系的同時(shí)對(duì)節(jié)點(diǎn)間的鏈接進(jìn)行了分析，較為準(zhǔn)確地對(duì)2種類型對(duì)象進(jìn)行領(lǐng)域劃分.同時(shí)，定義了3個(gè)啟發(fā)式規(guī)則作為構(gòu)建決策樹(shù)的候選屬性，選取信息增益最大的規(guī)則作為決策樹(shù)的決策節(jié)點(diǎn)來(lái)構(gòu)造決策樹(shù)模型，從而保證了將決策樹(shù)模型運(yùn)用到鏈路預(yù)測(cè)中的效率.根據(jù)節(jié)點(diǎn)間的聚類分布情況以及網(wǎng)絡(luò)中的鏈接信息使用決策樹(shù)模型對(duì)2種不同類型節(jié)點(diǎn)進(jìn)行鏈路預(yù)測(cè)，經(jīng)過(guò)實(shí)驗(yàn)可以證明，我們提出的CDTLinks鏈路預(yù)測(cè)算法在鏈路預(yù)測(cè)的過(guò)程中得到了很好的效果.

7 結(jié) 論

本文針對(duì)雙類型異質(zhì)信息網(wǎng)絡(luò)提出了一種基于聚類和決策樹(shù)的鏈路預(yù)測(cè)方法.該方法結(jié)合了聚類和決策樹(shù)，在雙類型的異質(zhì)網(wǎng)絡(luò)中具有良好的預(yù)測(cè)效果.2種對(duì)象互為特征的表示方法充分利用了網(wǎng)絡(luò)中節(jié)點(diǎn)之間的信息，得到2種對(duì)象的聚類分布情況.3種啟發(fā)式規(guī)則根據(jù)網(wǎng)絡(luò)中的節(jié)點(diǎn)以及聚類分布更好地分析了網(wǎng)絡(luò)中節(jié)點(diǎn)和鏈接的關(guān)系.利用3種啟發(fā)式規(guī)則計(jì)算信息增益，將信息增益最大的規(guī)則作為決策節(jié)點(diǎn)能夠更快地構(gòu)建決策樹(shù)，進(jìn)而快速有效地進(jìn)行鏈路預(yù)測(cè).通過(guò)實(shí)驗(yàn)證明了本文提出的CDTLinks算法的正確性和有效性.

[1] Lü Linyuan. Link prediction on complex networks[J]. Journal of University of Electronic Science & Technology of China, 2010, 39(5): 651-661 (in Chinese)(呂琳媛. 復(fù)雜網(wǎng)絡(luò)鏈路預(yù)測(cè)[J]. 電子科技大學(xué)學(xué)報(bào), 2010, 39(5): 651-661)

[2] Xu Bin, Chin A, Wang Hao, et al. Using physical context in a mobile social networking application for improving friend recommendations[C] //Proc of the 4th Int Conf on Internet of Things. Piscataway, NJ: IEEE, 2011: 602-609

[3] Zhang Peng, Zeng An, Fan Ying. Identifying missing and spurious connections via the bi-directional diffusion on bipartite networks[J]. Physics Letters A, 2014, 378(32-33): 2350-2354

[4] Yang Liu, Cao Jinxin, Liu Bo, et al. Community division algorithm based on feedback of unbiased Q value[J]. Journal of Southeast University, 2011, 41(1): 31-36

[5] Bliss C A, Frank M R, Danforth C M, et al. An evolutionary algorithm approach to link prediction in dynamic social networks[J]. Journal of Computational Science, 2014, 5(5): 750-764

[6] Scellato S, Noulas A, Mascolo C. Exploiting place features in link prediction on location-based social networks[C] //Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2011: 1046-1054

[7] Zhu Jun. Max-margin nonparametric latent feature models for link prediction[C] //Proc of the 29th Int Conf on Machine Learning. New York: ACM, 2012: 719-726

[8] Schifanella R, Barrat A, Cattuto C, et al. Folks in folksonomies: Social link prediction from shared metadata[C] //Proc of the 3rd ACM Int Conf on Web Search & Data Mining. New York: ACM, 2010: 271-280

[9] Zeng Xiangxiang, Li You, Leung S C H, et al. Investment behavior prediction in heterogeneous information network[J]. Neurocomputing, 2016, 217: 125-132

[10] Huang Liwei, Li Deyi, Ma Yutao, et al. A meta path-based link prediction model for heterogeneous information networks[J]. Chinese Journal of Computers, 2014, 37(4): 848-858 (in Chinese)(黃立威, 李德毅, 馬于濤, 等. 一種基于元路徑的異質(zhì)信息網(wǎng)絡(luò)鏈路預(yù)測(cè)模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 848-858)

[11] Lakshmi T J, Bhavani S D. Heterogeneous link prediction based on multi relational community information[C] //Proc of the 6th Int Conf on Communication Systems and Networks. Piscataway, NJ: IEEE, 2014: 1-4

[12] Aggarwal C C, Xie Yan, Yu P S. A framework for dynamic link prediction in heterogeneous networks[J]. Statistical Analysis & Data Mining, 2014, 7(1): 14-33

[13] Lee J B, Adorna H. Link prediction in a modified heterogeneous bibliographic network[C] //Proc of Int Conf on Advances in Social Networks Analysis and Mining. Los Alamitos, CA: IEEE Computer Society, 2012: 442-449

[14] Sun Yizhou, Han Jiawei, Zhao Peixiang, et al. RankClus: Integrating clustering with ranking for heterogeneous information network analysis[C] //Proc of the 12th Int Conf on Extending Database Technology: Advances in Database Technology. New York: ACM, 2009: 565-576

[15] Han J W, Kamber M, Pei J. Data Mining Concepts and Techniques Third Edition[M]. San Francisco, CA: Morgan Kaufmann, 2012: 102-120

[16] Sivatha S S S, Geetha S, Kannan A. Decision tree based light weight intrusion detection using a wrapper approach[J]. Expert Systems with Applications, 2012, 39(1): 129-141

[17] Khoshelham K. Accuracy analysis of kinect depth data[J]. ISPRS-Int Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2012, 3812(5): 133-138

[18] Zhang Ke, Hutter M, Jin Huidong. A new local distance-based outlier detection approach for scattered real-world data[C] //Proc of the 13th Conf on Knowledge Discovery and Data Mining. Berlin: Springer, 2009: 813-822

[19] Tzeng J Y, Byerley W, Devlin B, et al. Outlier detection and false discovery rates for whole-genome DNA matching[J]. Journal of the American Statistical Association, 2003, 98(461): 236-246

[20] Croft W B, Metzler D, Strohman T. Search Engines: Information Retrieval in Practice[M]. Reading, MA: Addison-Wesley, 2010: 23-37

[21] Tang Jie, Zhang Jing, Yao Limin, et al. Arnetminer: Extraction and mining of academic social networks[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 990-998

LinkPredictionMethodBasedonClusteringandDecisionTree

Yang Niya1, Peng Tao1,2, and Liu Lu1

1(CollegeofComputerScienceandTechnology,JilinUniversity,Changchun130012)2(KeyLaboratoryofSymbolComputationandKnowledgeEngineering(JilinUniversity),MinistryofEducation,Changchun130012)

Link prediction is one of the primal problems in data mining. Due to the network complexity and the data diversity, the problem of link prediction for different types of data in heterogeneous networks has become more and more complicated. Aiming at link prediction in bi-typed heterogeneous information network, this paper proposes a link prediction method based on clustering and decision tree, called CDTLinks. One kind of objects is considered as the features of the other kind of objects. Then, they are clustered separately. Three heuristic rules are proposed to construct decision trees for bi-typed heterogeneous networks. The branch of the tree with the highest information gain is selected. Finally, we can judge whether there is a link between two nodes through the clustering result and the decision tree model. In addition, we define the concept of potential link nodes and introduce the number of layers, which can reduce the running time and improve the accuracy. The proposed CDTlinks method is validated on DBLP and AMiner datasets. The experimental results show that the CDTlinks model can be used to conduct link prediction effectively in bi-typed heterogeneous networks.

link prediction; clustering; decision tree; heterogeneous information network; heuristic rules

Yang Niya, born in 1992. Master. Her main research interests include Web mining and machine learning.

Peng Tao, born in 1977. PhD, professor. Member of CCF. His main research interests include Web mining, information retrieval and machine learning.

Liu Lu, born in 1989. PhD. Her main research interests include Web mining, information retrieval and machine learning.

2017-03-18；

：2017-05-11

國(guó)家自然科學(xué)基金項(xiàng)目(60903098)；吉林省發(fā)改委產(chǎn)業(yè)技術(shù)研究與開(kāi)發(fā)專項(xiàng)(2015Y055)；吉林省科技廳重點(diǎn)科技攻關(guān)項(xiàng)目(20150204040GX) This work was supported by the National Natural Science Foundation of China (60903098), the Industry Technology Research and Development Projects of Development and Reform Commission of Jilin Province (2015Y055), and the Key Scientific Research Project of Department of Science of Jilin Province (20150204040GX).

劉露(liulu12@mails.jlu.edu.cn)

TP391