基于聚類和決策樹的鏈路預測方法

楊妮亞 彭 濤,2 劉 露

1(吉林大學計算機科學與技術學院 長春 130012) 2 (符號計算與知識工程教育部重點實驗室(吉林大學) 長春 130012) (yangny15@mails.jlu.edu.cn)

基于聚類和決策樹的鏈路預測方法

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

1(吉林大學計算機科學與技術學院 長春 130012)2(符號計算與知識工程教育部重點實驗室(吉林大學) 長春 130012) (yangny15@mails.jlu.edu.cn)

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

鏈路預測；聚類；決策樹；異質信息網絡；啟發式規則

異質信息網絡挖掘是數據挖掘的一類重要問題.預測網絡中節點之間的鏈接關系具有重要的研究價值.鏈路預測旨在根據網絡結構和已有信息發現并且還原網絡中缺失的信息，或者預測未來節點之間可能存在的關系.節點間不同的鏈接關系對網絡分析有重要的現實意義[1].鏈路預測也有廣泛的應用，比如通過預測網絡中節點之間的關系，在社交網絡中進行朋友推薦[2]、識別隱藏和虛假的鏈接對網絡進行重構[3]以及社團劃分[4]等.

在異質信息網絡中，不同類型的節點和鏈接包含著豐富的語義關系，使得鏈路預測變得更加復雜.例如文獻信息網絡包含會議/期刊、作者、論文等多種類型的節點以及多種鏈接關系.傳統的異質信息網絡鏈路預測是通過分析整個網絡對象之間的鏈接關系找到虛假的鏈接，或者對未來的鏈接進行預測.這使得異質信息網絡中鏈路預測變得十分復雜并且效率較低.

受到以上方法的啟發，本文提出一種雙類型異質信息網絡鏈路預測的方法.該方法主要解決4個問題：1)如何在簡化異質信息網絡的同時保留主要語義信息；2)如何構建決策樹模型；3)如何選取合適的屬性作為決策樹的決策節點；4)如何結合不同類型節點聚簇分布情況以及決策樹進行鏈路預測.

為了解決上述問題，我們提出了一種雙類型異質信息網絡中基于聚類和決策樹的鏈路預測方法.該方法提取異質網絡中2種關鍵類型的對象，根據2種類型節點之間存在的鏈接關系構造鄰接矩陣，采用2種類型對象互為特征的方法，對2種類型的對象分別進行聚類.這樣保留主要語義關系的同時對節點間的鏈接進行分析.定義了3個啟發式規則作為構建決策樹的候選屬性，選取信息增益最大的規則作為決策樹的決策節點來構造決策樹模型.最后，根據不同類型節點間聚類分布情況以及決策樹模型對2種不同類型節點進行鏈路預測.以文獻信息網絡為例，我們通過分析網絡中作者與期刊/會議之間的鏈接關系，對作者和期刊/會議這2種類型的節點進行聚類，根據3個啟發式規則構建決策樹來預測未來作者和期刊/會議之間可能出現的鏈接.

本文的主要貢獻有5個方面：1)提出了一種雙類型異質網絡的鏈路預測方法，對2種類型節點之間的關系進行預測；2)采用2種類型對象互為特征的方法，對2種類型的對象分別進行聚類；3)定義了3種啟發式規則作為構建決策樹的候選屬性；4)分析不同類型節點的聚類結果和節點之間的鏈接關系，得到決策樹的屬性，構造決策樹模型；5)在不同數據集中進行實驗.結果表明：本文提出的雙類型異質信息網絡鏈路預測方法可以有效地預測網絡中節點之間的鏈接關系.

1 相關工作

鏈路預測是數據挖掘中一個關鍵的問題，在同質網絡中，研究者們做了很多深入的研究.Bliss等人[5]通過應用協方差矩陣自適應演化策略(CMA-ES)來優化在16個鄰域和節點相似性索引的線性組合中使用的權重，提出了一種預測未來鏈路的方法；Scellato等人[6]描述了一個監督學習框架，通過分析鏈路節點之間的關系來預測新的朋友和朋友的朋友之間的聯系；Zhu[7]提出了一種非參數潛在特征關系模型的最大余量學習方法，該方法可以擴展到具有數百萬實體和數千萬個正鏈接的大規模實際網絡中；Schifanella等人[8]引入一個空模型，保留用戶的活動，同時消除當地的相關性.實驗結果證明由語義相似性構建的社會網絡能夠更準確地捕捉到實際的鏈路關系.

由于網絡中充斥著許多不同類型的對象和鏈接關系，異質信息網絡中的鏈路預測問題逐漸引起了研究者們的關注.Zeng等人[9]構建基于元路徑的異構網絡的投資行為預測模型，該模型考慮與特定投資者的投資行為相關聯的多個實體和關系類型，投資行為預測模型為元路徑提供了一個有效的相似性度量函數；Huang等人[10]使用元路徑描述不同類型的節點和關系的不同語義，提出了一種基于元路徑異構信息網絡鏈路預測模型；Lakshmi等人[11]為提高效率，提出了異質信息網絡中鏈路預測的并行方法，利用現有的多關系鏈接預測以及社區發現算法，在每個社區計算多關系鏈接預測分數；Aggarwal等人[12]提出了一個有效的兩級方案，為了將網絡動態性和時間敏感度相結合，使用了宏觀和微觀決策；Lee等人[13]對存在的文獻網絡進行修改并且突出其中重要的關系，將隨機游走算法應用到修改后的網絡鏈路預測問題.

研究者們在同質網絡和多類型異質網絡上做了很多的鏈路預測方面的研究，但關于雙類型異質網絡鏈路預測方法的研究還很少.在很多情況下，與多類型網絡相比較來說，雙類型網絡在模型表示和計算的過程中相對簡單.針對上述情況，本文針對雙類型異質信息網絡提出了鏈路預測方法.

2 問題定義

在本節中，我們先介紹鏈路預測方法需要用到的一些基本概念，再給出雙類型異質信息網絡中鏈路預測的形式化定義.

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

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

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

此時，節點yi與節點yk之間的鏈接關系可表示為yi-yj-yk，yi到yk的鏈接個數為2.yi與yk也互為2層潛在鏈接節點.隨著鏈接關系中鏈接數量的增加，節點間的相近關系也隨之變化，因此，我們引入n層潛在鏈接節點的概念來分析異質網絡中存在鏈路的可能性，即如果yi與yk之間存在n個鏈接，那么它們互為n層潛在鏈接節點.下面我們給出雙類型異質網絡中鏈路預測問題的形式化定義.

問題1. 雙類型異質網絡中的鏈路預測.給定一個雙類型異質網絡G=(X∪Y,W)，對于網絡中任意2個節點xi∈X，yj∈Y，根據網絡中節點的聚類結果以及決策樹的分析結果，預測xi與yj之間是否存在鏈接.

3 雙類型異質網絡聚類過程

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

得到X類型對象和Y類型對象的特征表示后，分別進行聚類.以Y類型對象為特征，Y和X兩種類型對象之間的鏈接權值作為特征值對X類型對象進行聚類.通過計算聚類中心與每個對象的距離反復對聚類進行調整，使得聚類內部的誤差平方和[15]最小，從而得到X類型對象的K1個聚類.同樣，以X類型對象為特征，X和Y兩種類型對象之間的鏈接權值作為特征值對Y類型對象進行聚類.通過計算聚類中心與每個對象的距離反復對聚類進行調整，得到Y類型對象的K2個聚類.

Fig. 1 An example of relationship between the conference and the author圖1 會議和作者的關系實例

4 決策樹的構建過程

在第3節中，我們得到了2種類型對象的聚類結果.本節我們介紹如何構建決策樹來預測網絡中節點之間的鏈接關系.

給定一個雙類型異質信息網絡G=(X∪Y,W)，對于網絡中任意2個節點xi∈X，yj∈Y，根據以下3條規則來判斷xi與yj之間是否存在鏈接.若xi與yj存在鏈接，則函數linkpredict(xi,yj)=1；反之，linkpredict(xi,yj)=0.

規則1.xi所在聚簇為Ck，若節點yj與xi同聚簇的節點之間存在鏈接，那么，xi與yj之間可能存在鏈接.該規則可表示為

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

(1)

規則2. 若節點xi的直接鏈接節點或潛在鏈接節點與yj存在鏈接，那么，xi與yj之間可能存在鏈接.該規則可表示為

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

(2)

規則3.yj所在聚簇為Cl，若節點xi與yj同聚簇的節點之間存在鏈接，那么，xi與yj之間可能存在鏈接.該規則可表示為

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

(3)

我們應用以上3條規則來預測雙類型異質網絡中的鏈接，以文獻信息網絡為例，我們將會議名作為X類型節點，將作者名作為Y類型節點，并將它們之間的鏈接關系存儲在鄰接矩陣W中.如果一個作者yj與會議xi同領域的會議間存在鏈接，那么，該作者yj與會議xi可能存在鏈接(規則1).如果一個作者與yj與會議xi的直接鏈接節點或潛在鏈接節點之間存在鏈接，那么，該作者yj與會議xi可能存在鏈接(規則2).如果一個會議xi與作者yj同領域的作者間存在鏈接，那么，該會議xi與作者yj可能存在鏈接(規則3).

本文把3條規則作為決策樹的候選屬性集Pro.在構造決策樹的過程中，將信息增益[16]作為選擇候選屬性的度量指標來衡量3條規則哪一條可以更好地進行鏈路預測.設D是數據集，根據數據的類別對D進行劃分，其中類別由存在鏈接和不存在鏈接2部分組成.存在鏈接的類別數據記為D1，不存在鏈接的類別數據記為D2，則D的熵表示為

(4)

(5)

其中,pi表示第i個類別在整個訓練元組中出現的概率.假設將訓練元組D按屬性attr進行劃分，其中attr∈Pro，則attr對D劃分的期望信息[16]為

(6)

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

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

(7)

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

Fig. 2 Illustration of constructing decision tree圖2 構造決策樹示意圖

算法1. 決策樹構造算法

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

輸出: 決策樹.

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

② 鏈接p兩邊節點記作m和n，m和n按照3個啟發式規則得到每一個訓練數據在各個屬性的對應值(值為Yes/No)；

③ end for

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

⑤ 計算attr的信息增益；

⑦attr作為決策樹的分支；

⑧Pro=Pro-attr.

⑨ end if

⑩ end for

5 基于聚類和決策樹的鏈路預測方法

通過網絡結構以及網絡中已有的信息來預測節點未來的鏈接關系是鏈路預測的主要任務.網絡中存在著多種類型的節點以及多種類型的鏈接關系，根據不同節點間的關聯關系和語義關系來預測鏈接能夠幫助研究者更好地分析網絡中的數據.因此，本節中提出了一種雙類型異質網絡中基于聚類和決策樹的鏈路預測方法.

首先，我們提取異質網絡中2種不同類型的對象以及對象間的鏈接關系，通過對象間互為特征的方法得到雙類型對象的特征表示，并將2種類型對象進行聚類.得到不同類型對象的聚簇分布后，定義了3個規則作為構建決策樹的候選屬性，選取信息增益較大的規則來構建決策樹.最后，將需要判斷的節點輸入到決策樹中，根據決策樹以及聚簇分布情況來判斷任意2個不同類型節點之間是否存在鏈接.

下面我們給出一個雙類型文獻信息網絡進行鏈路預測的實例，如圖3所示.2種類型節點分為作者和會議名，圖3中已知對象間已有的鏈接以及對象的聚類分布情況，目標為預測下一時刻Andy與SIGMOD間是否存在鏈接.Andy與Bob與為合作作者，Bob與Cindy互為合作作者，那么，Bob與Andy互為二層潛在鏈接作者.Cindy和David在同一聚類C1中，那么，David與Andy的合作作者Cindy在同一聚類中.根據規則2和規則1，如果David與SIGMOD之間存在鏈接，那么Andy與SIGMOD之間很可能存在鏈接.會議SIGMOD與VLDB在同一聚類中，根據規則1，如果Andy與VLDB之間存在鏈接，那么Andy與SIGMOD之間很可能存在鏈接.在圖3中，David與VLDB之間存在鏈接.所以，根據規則3，David與SIGMOD之間很可能存在鏈接.根據規則1，Cindy與SIGMOD之間很可能存在鏈接.根據規則2，Andy與SIGMOD之間很可能存在鏈接.

Fig. 3 An example of link prediction for bibliographic information network圖3 文獻信息網絡鏈路預測實例

6 實驗與結果

在本節中，我們使用本文提出的聚類和決策樹方法構建一個面向雙類型異質網絡的鏈路預測模型，并在2個數據集上進行測試了我們的方法.

6.1度量標準

為了評估鏈路預測模型CDTLinks的效果，我們使用準確率Accuracy[17]、精確率Precision[18]、召回率Recall[19]和F-Measure[20]4種度量標準來檢測鏈路預測模型的性能.精確率和召回率分別反映了模型找對和找全鏈接的能力.我們將鏈路預測的結果分為有鏈接和無鏈接2種情況.針對2種情況，分別給出相應的精確率和召回率.對于有鏈接的數據，精確率是被正確識別的鏈接數占被識別為有鏈接的數據的比例.召回率，也稱查全率，是被正確檢測出有鏈接的數據占實際存在鏈接數據的比例.有鏈接情況精確度和召回率的計算為

(8)

(9)

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

(10)

(11)

同樣，CN表示被鏈路模型判斷為無鏈接的數據集合，TN表示測試集中存在的無鏈接數據的集合.Precision和Recall不成正相關，我們采用這2個指標的調和平均值F-Measure來作為評估標準，F-Measure的計算為

(12)

β是一個反應精確度和召回率相對重要程度的權值，若β>1，則召回率的重要性大于準確率，反之亦然.在本文中將設β=1.

Accuracy作為度量標準來衡量所有數據是否和真實類別一致，即衡量模型作出正確決定的能力.Accuracy的公式定義為

(13)

其中，TP表示有鏈接數據集中被正確識別為有鏈接數據的數量，TN表示無鏈接數據集中被正確識別為無鏈接數據的數量，|TE|和|TN|之和為所有數據總數.

6.2數據集

在本文中，我們使用2個真實的信息網絡：DBLP*http://dblp.org/網絡和AMiner[21]網絡.

1) DBLP數據集是異質網絡中常用的實驗數據，其中的數據類型包括會議/期刊、作者、發表時間等等.提取期刊、作者以及二者之間的鏈接信息作為實驗數據.將出現在實驗中的期刊人工標記它所屬的領域.在實驗中，讀取其中的20 000條數據，出現22個期刊、31 181個作者、892 983條期刊與作者的鏈接關系，人工標記期刊所屬的領域.

2) AMiner數據集是社會網絡挖掘常用的數據集，其中包括作者、會議、主題等信息.本文使用aminer-topic-data-pubs.xml文件中的數據.對AMiner數據集進行了預處理，提取出6類會議信息.以提取出的會議，作者以及會議與作者之間的鏈接信息作為實驗數據，其中包括33個期刊、21 381個作者、836 524條期刊與作者的鏈接關系.

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

6.3參數分析及結果

本節中，我們通過實驗來驗證CDTLinks鏈路模型.首先，分析潛在鏈接節點的層數μ對鏈路模型的影響.對DBLP數據集和AMiner數據集，判斷作者和期刊之間是否存在鏈接.其中，待預測作者的合作作者信息對鏈路預測具有很重要的意義.如果待預測作者的直接鏈接作者與待預測期刊之間有鏈接關系，那么待預測的作者和期刊之間存在鏈接關系的可能性很高.如果待預測作者的二層潛在鏈接合作作者與待預測期刊之間有鏈接關系，那么待預測的作者和期刊之間存在鏈接關系的可能性相對較低.同時，搜索二層潛在作者信息所花費的時間相比于搜索直接鏈接作者信息所花費的時間要多.理論上，異質信息網絡中的潛在鏈接節點層數可以無限大.但是，隨著搜索潛在節點信息的層數的增加，鏈路預測結果的準確率降低，花費的時間增加.

圖4和圖5分別給出了隨著潛在鏈接節點層數μ的增加，在DBLP和AMiner數據集上Accuracy,Precision,Recall和F-Measure的變化曲線.從圖4和圖5中可以看出，在2個數據集中，Accuracy,Precision,Recall和F-Measure在μ=3時取得峰值.當μ<3時，隨著μ的增加，鏈路預測的Accuracy,Precision,Recall和F-Measure增加.當μ>3時，Accuracy,Precision,Recall和F-Measure不再增加.這是因為隨著潛在鏈接搜索層數的增加，從網絡鏈接中獲得的信息越多，CDTLinks表現出的性能也隨著增加.當增加到一個峰值時，隨著搜索層數的增加，導致錯誤或冗余的信息過多，CDTLinks表現出的性能反而下降.

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

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

Fig. 6 Running time of μ on DBLP and AMiner datasets圖6 不同的μ在DBLP和AMiner數據集中的運行時間

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

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

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

7 結 論

本文針對雙類型異質信息網絡提出了一種基于聚類和決策樹的鏈路預測方法.該方法結合了聚類和決策樹，在雙類型的異質網絡中具有良好的預測效果.2種對象互為特征的表示方法充分利用了網絡中節點之間的信息，得到2種對象的聚類分布情況.3種啟發式規則根據網絡中的節點以及聚類分布更好地分析了網絡中節點和鏈接的關系.利用3種啟發式規則計算信息增益，將信息增益最大的規則作為決策節點能夠更快地構建決策樹，進而快速有效地進行鏈路預測.通過實驗證明了本文提出的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)(呂琳媛. 復雜網絡鏈路預測[J]. 電子科技大學學報, 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)(黃立威, 李德毅, 馬于濤, 等. 一種基于元路徑的異質信息網絡鏈路預測模型[J]. 計算機學報, 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

國家自然科學基金項目(60903098)；吉林省發改委產業技術研究與開發專項(2015Y055)；吉林省科技廳重點科技攻關項目(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