一種基于領域知識的鏈路預測方法

李奮華 趙潤林

(運城學院數學與信息技術學院 山西 運城 044000)

0 引 言

個性化推薦技術已經在電子商務領域獲得了較廣泛的應用[1]。在推薦系統中，推薦算法是推薦系統的核心部分，協同過濾算法作為經典的推薦算法在推薦系統中獲得了較成功的應用[2-3]。但是協同過濾算法自身存在一些問題，例如：在數據稀疏的情況下，其推薦效果較差，且在推薦過程中并沒有考慮實體間的一些附加有用信息[2]。有些學者提出了基于鏈路預測的個性化推薦算法，這些算法主要是利用顧客商品二分網絡中顧客與商品之間的關聯信息來彌補數據稀疏的問題，通過使用二分網絡的拓撲結構信息來改善算法的推薦質量。然而，這些算法在推薦過程中僅僅利用了二分網絡的拓撲結構信息，并沒有考慮商品的領域知識。文獻[3]提出采用顧客商品二分網絡中商品的領域信息進行推薦，能夠進一步改善推薦的精度和效果。

本文結合顧客商品二分網絡的拓撲結構和網絡中節點的相關屬性，提出一種基于領域知識的鏈路預測方法。在該方法中，推薦給顧客的不同商品有不同的權重，權重的大小由與該商品相關的領域知識來決定，權重越大的商品被認為是越符合顧客需求的，越值得推薦給顧客。

1 鏈路預測算法

1.1 典型的鏈路預測算法

鏈接預測(Link prediction)是指如何通過已知的邊(即網絡拓撲結構)或者節點的特征等信息來預測評估社會網絡中節點之間未知鏈接(包括已存在而丟失的鏈接、未來的鏈接)存在的可能性[4-5]。幾種典型的鏈路預測算法介紹如下：

1) 共同鄰居方法(Common Neighbors，CN)：該方法是基于待預測節點對的共同鄰居節點的數量來對社會網絡進行鏈接預測[6-9]。在這里，假設Γ(x)代表節點x的共同鄰居的集合[10-11]。一般來說，如果待預測節點對(x,y)具有的共同鄰居數量越多，那么就認為節點x和節點y之間存在連邊的可能性越大。因此，共同鄰居方法的節點相似性度量指標定義如下：

(1)

2) Adamic Adar方法(簡稱AA)：該方法是基于待預測節點對的共同鄰居集合來進行鏈接預測的。針對待預測節點對的每個共同鄰居節點在鏈接預測中的作用不同，它賦予每個共同鄰居一個權值，該權值是對應共同鄰居節點度值對數的倒數[12-13]。如果一個節點的度值比其他節點小，那么該節點在鏈接預測中的作用比其他節點更重要[4-5，14-15]。該方法的節點相似性度量指標定義如下：

(2)

式中：Γ(x)、Γ(y)分別代表節點x、y的共同鄰居的集合；Kz表示節點z的度。

3) Jaccard Index方法(簡稱JA)：該方法由Jaccard提出[10]，是信息檢索領域被廣泛應用的一種相似度度量方法[16-17]。它的主要思想是：給定一個節點對(x,y)，在節點x、y的鄰居并集中，將隨機選擇一個鄰居節點是該節點對共同鄰居的概率作為節點相似度的度量指標。該方法定義如下：

(3)

一般來說，評估預測算法精確度的主要有兩個指標：AUC和Precision。AUC是從整體上來考慮算法的預測精度；Precision是從局部層面來考慮算法的預測精度[18]。

1.2 顧客商品二分網絡

復雜系統在現實生活中普遍存在，復雜網絡是表示和研究復雜系統的有效方法之一。在復雜網絡中，節點表示復雜系統中的個體，邊表示個體之間存在的關系[5，16]。二分網絡是復雜網絡的一種特殊形式，在該網絡中節點被分成不同的兩類節點，同類節點之間不存在關系，只有在不同類節點之間才存在關系[19]。在電子商務領域，顧客購買商品構成的網絡就是二分網絡，假設P={p1,p2,…,pn}表示顧客商品網絡中的商品集合，C={c1,c2,…,cm}表示顧客商品網絡中的顧客集合，因此，能夠獲得一個隸屬關系矩陣A=(aij)n×m，其中aij表示網絡中節點i代表的特定對象(即商品i)與節點j代表的特定對象(即顧客j)的隸屬(即購買)關系值，也就是說，在該矩陣中如果顧客ci購買了商品pj，那么aij賦值為1，否則aij賦值為0。在顧客商品二分網絡中，如何選擇顧客沒有購買過的合適商品推薦給每個顧客是個性化推薦中很關鍵的問題，傳統的協同過濾算法雖然有時能夠取得較好的推薦效果，但是該算法僅僅考慮網絡節點(顧客/商品)的直接鄰居，具有一定的局限性[20]。圖1為一個顧客商品二分網絡，在該網絡中平行四邊形代表顧客，橢圓代表商品，實線表示顧客已購買商品，虛線表示將來顧客可能購買的商品(即個性化推薦)。

圖1 顧客商品二分網絡

2 方法設計與實現

2.1 基于領域知識的鏈路預測方法

鏈路預測實際上是根據網絡的拓撲結構的特點來推斷未來有可能出現的關系。在生物研究領域，研究者根據共有鄰居的數量來計算蛋白質對之間的拓撲相似度，以此來進行預測和推薦。文獻[3]利用二分網絡的拓撲特點，在電子商務中的商品推薦方面做了一定的研究。在此啟發下，根據顧客商品二分網絡的拓撲特點，把鏈路預測和領域知識相融合，描述了一種顧客商品推薦方法。假設顧客商品二分網絡G，通過相似度分值來計算未來顧客c購買商品P的連邊的可能性大小，以此作為推薦的依據。對于節點x，Γ(x)代表節點x的共同鄰居的集合，那么節點x的鄰居的鄰居集合定義如下：

Γ′(x)=Γc″∈Γ(x)(c″)

(4)

對式(1)作修改后，連邊可能性的度量標準如下：

CP_CN(p,c)=|Γ(p)∩Γ′(c)|

(5)

同理，對式(3)作修改后，可獲得連邊可能性的度量標準如下：

(6)

在文獻[3]的啟發下，根據實際顧客商品網絡中商品的分類，構建商品的分類層次結構樹，在此分類結構樹的基礎上，構建商品之間的語義相似度的度量標準，如下：

(7)

式中:dis(pi)表示商品分類樹中商品pi與根節點的路徑長度；set(P)表示商品pi和商品pj共同的祖先節點的集合；n表示set(P)中祖先節點的個數。

把式(7)和式(5)、式(6)相融合就得到在顧客商品二分網絡中基于鏈路預測和領域知識的推薦評估指標，如下：

(8)

(9)

式中：pi表示顧客c已經購買的商品；CHB(c)表示顧客c已經購買商品的集合；m表示顧客已經購買商品的數量(即CHB(c)集合的大小)。

2.2 實驗分析

根據2.1節中描述的顧客商品推薦方法，在實際的超市購買數據集上進行實驗，該數據集包含了近1年3 542名顧客的購買信息，其中涉及到的商品有487種，交易次數達到36 873次。在本實驗中，用鏈路預測中的AUC作為推薦結果的度量標準，把該方法中的分值最高的前20種商品推薦給顧客，分別把數據集的70%、80%作為訓練集，剩余的作為測試集，實驗結果如表1和圖2所示。

表1 顧客商品二分網絡中不同推薦方法的推薦精度比較

圖2 顧客商品網絡中不同推薦方法的精度比較

從表1和圖2的實驗結果來看，在顧客商品二分網絡中采用鏈路預測和領域知識相融合的推薦方法能夠取得較理想的推薦效果。

3 結 語

基于電子商務二分網絡個性化推薦精度低的現狀，本文描述一種基于領域知識的鏈路預測方法，并在真實的超市顧客商品數據集上進行實驗。結果表明，該方法推薦效果較好，能夠在一定程度上提高個性化推薦的精度，具有一定的實用價值。