基于鏈路預測的推薦方法研究

丁 沂

（武漢軟件工程職業學院 計算機學院，湖北 武漢 430205）

基于鏈路預測的推薦方法研究

丁 沂

（武漢軟件工程職業學院 計算機學院，湖北 武漢 430205）

推薦系統在數字化環境中能夠提供有價值的服務，并且在圖書、電影和音樂等在線產業中取得了巨大的商業成功。大多數推薦系統采用協同過濾算法，通過分析用戶和物品之間的交互行為推理用戶的興趣和偏好。協同過濾算法的推薦效果受到數據稀疏性問題的影響很大。為了解決這個問題，文章使用一種基于圖的方法探索用戶和物品之間的交互。文章采用二分網絡鏈路預測的方法對用戶進行物品推薦，并與協同過濾方法進行了比較，通過在豆瓣數據集上的實驗結果表明，基于鏈路預測的方法比標準的協同過濾方法要好。

推薦系統；協同過濾；鏈路預測

近年來，通過向潛在的用戶推薦商品、服務和信息，推薦系統在很多領域得到了廣泛的應用。推薦系統中最關鍵部分是推薦算法。推薦算法通常利用用戶和物品的屬性或者用戶和物品之間的交互（打分行為、瀏覽行為、購買行為等）預測用戶對某個物品的偏好[1]。協同過濾算法是推薦系統中最成功也是被關注最多的算法，這個算法依賴用戶和物品之間的交互數據進行推薦。標準的協同過濾算法首先找到目標用戶的鄰居，尋找鄰居的方法并不是使用與目標用戶屬性相似的用戶，而是使用與目標用戶具有相似行為的用戶，然后根據目標用戶鄰居的經驗對目標用戶進行推薦。盡管協同過濾算法在業界取得了巨大的成功，但是協同過濾算法的效果受到數據稀疏性的影響很大，因為沒有足夠的歷史行為數據用來幫助找到目標用戶的鄰居。為了解決這個問題，人們使用一種基于圖的算法來探索用戶和物品之間的交互行為。從二分網絡的觀點來看，推薦問題可以看作為每個用戶節點選擇未觀測到的邊的過程。因此，可以使用二分網絡鏈路預測的方法對推薦問題進行建模[2]。

1 鏈路預測

二分網絡又叫二部圖，是一種具有特殊結構特征的網絡。一個簡單的二分網絡G(V,E)存在一對節點集合X和Y，并且滿足E中任意一條連邊一定恰有一個頂點在集合X中，另一個頂點在集合Y中。現實世界中很多復雜的系統具有二分結構，可以用二分網絡進行建模。例如，新陳代謝網絡可以視為是以化學物質和化學反應為兩個分離集合的二分網絡，合作網絡可以看作以參與者和事件為兩個分離集合的二分網絡，互聯網是以電腦和網絡設備為兩個分離集合的二分網絡，開源社區是以開發者和軟件項目為兩個分離集合的二分網絡，電子商務是以用戶和商品為兩個分離集合的二分網絡，異性的性關系網絡是以男性和女性為兩個分離集合的二分網絡，人類疾病網絡是以身心機能失調表現和致病基因為兩個分離集合的二分網絡。二分網絡具有很多網絡不具備的性質。比如，二分網絡都不包含長度為奇數的圈，因此，一個包括長度為奇數的圈的網絡肯定不是一個二分網絡；另外，二分網絡都是可以二著色的并且二分網絡的譜具有對稱性等等。由于二分網絡具有這些特征，因此針對一個節點規模為N的無向簡單網絡，可以以線性時間復雜性0(N)判斷該網絡是不是一個二分網絡。

網絡分析方法近年來廣泛應用在復雜系統的研究中，例如，Internet，WWW、社會網絡和基因網絡。鏈路預測是網絡建模中的一個重要問題，在社會網絡、基因網絡和引文網絡中受到廣泛關注。二分網絡中的鏈路預測與推薦系統比較相似，二分網絡的鏈路預測是指如何通過已知的網絡節點及網絡結構等信息，預測網絡中尚未產生連邊的兩個節點之間產生連邊的可能性，既包含對未知連邊的預測，也包含對未來連邊的預測[3]。應用社會網絡鏈路預測中的三個連邊權重指標，采用用戶和物品交互圖的建模方法對用戶進行推薦。

在二分網絡G中，用戶和物品代表兩種不同類型的節點，不同類型節點之間的連邊代表用戶和物品之間的交互。由于我們研究的是基于事務的協同過濾問題，二分網絡中的連邊是沒有權重的，而且整個二分網絡代表了輸入數據的全部信息。基于二分網絡G的拓撲結構，我們可以為二分網絡中每一對未連接用戶-物品節點對計算相應的權重w(u，i)。這個權重可以作為該節點對的一個候選得分，用來評估節點u和節點i之間連邊的概率，從而對用戶進行推薦[4]。

在經典網絡鏈路預測中有很多連邊權重的度量指標，在二分網絡中連邊權重的度量指標相對較少。因此，修改了3個經典網絡中的連邊權重度量指標并應用在二分網絡中。如表1所示，本文對于節點x，我們定義為節點x的鄰居集合Nh。

表1 基于鄰居的權重指標

這3個連邊權重指標都是基于鄰居的相似性度量指標。Common neighbors指標表示二分網絡中兩個節點共同鄰居的數量；Jaccard指標和Common neighbors指標類似，不僅考慮了兩個節點共同鄰居的數量，還考慮到了兩個節點各自的鄰居數目；Delta指標考慮到了兩個節點鄰居數量不均衡的情況[5]。

2 實驗

調查都使用豆瓣數據集為研究對象，數據集覆蓋了4年內2 000多個用戶對1 000多本圖書的20 000多個交互事務。為了評價推薦的效果，采用top-N推薦，為每個用戶推薦top-10本尚未購買的圖書。將基于二分網絡鏈路預測的推薦方法和標準協同過濾算法進行了對比。從實驗結果可以看出，基于二分網絡鏈路預測的方法要比標準的協同過濾方法好。

表2 實驗結果

3 結語

本文運用網絡結構和網絡分析技術，采用二分網絡鏈路預測方法對用戶推薦它們感興趣的物品，并與標準協同過濾算法進行了比較。未來將采用更多權重度量指標驗證本方法的有效性。

[1]鄧愛林，朱揚勇，施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報，2003（9）：1621-1628.

[2]孟祥武，胡勛，王立才，等.移動推薦系統及其應用[J].軟件學報，2013（1）：91-108.

[3]王立才，孟祥武，張玉潔.上下文感知推薦系統[J].軟件學報，2012（1）：1-20.

[4]項亮.推薦系統實踐[M].北京：人民郵電出版社，2012.

[5]朱郁筱，呂琳媛.推薦系統評價指標綜述[J].電子科技大學學報，2012（2）：163-175.

Research on recommendation method based on link prediction

Ding Yi
（Computing School of Wuhan Vocational College of Software and Engineering, Wuhan 430205, China）

The recommendation system in the digital environment can provide valuable services, and has achieved great commercial success in books, movies, music and other online industries. Most recommendation system adopt collaborative fi ltering algorithm, which reasons out users’ interests and preference through the interactive behavior between users and items. The recommendation effect of collaborative fi ltering algorithm has been greatly influenced by the data sparsity problem. Ιn order to solve this problem, this paper uses method on the basis of graph to explore the interaction between a user and item. This paper applies two network link prediction method to recommend items for users, and makes a comparison w ith the collaborative fi ltering method. According to the experimental results on the bean data set, it shows that the link prediction method is better than the standard collaborative fi ltering method

recommendation system; collaborative fi ltering; link prediction

武漢市市屬高校產學研項目；項目編號：201310。

丁沂（1978－ ），男，湖北武漢，碩士，教師；研究方向信息檢索，推薦系統。