基于最大團的社交網絡個性化推薦?

陳小禮 汪 洋 彭艷兵

（1.南京烽火軟件科技有限公司 南京 210019）（2.武漢郵電科學研究院 武漢 430074）

1 引言

個性化推薦是指考慮當前觀眾（網站，電視頻道或任何其他內容）的優越用戶體驗，并根據系統對這些人的了解情況升級默認外觀、感覺和內容，并作出相應推薦。個性化推薦雖然利用了推薦算法，但它更加專注于用戶本身。隨著現代計算機的出現，雖然互聯網使得各種信息獲取變得輕而易舉，但信息的信息過載問題會使人們被太多選擇淹沒而猶豫不決［1］。為了解決以上的眾多問題，傳統上人們使用協同過濾推薦來進行推薦［2］。大多數協作過濾系統應用所謂的基于鄰域的技術。在基于鄰域的方法中，基于與活動用戶的相似性來選擇多個用戶，通過計算所選擇的用戶的評級的加權平均值來進行活動用戶的預測。協同過濾算法的優點很多，主要體現在對推薦系統的項目無過于苛刻的要求，并且在面對復雜的非結構化項目時處理起來相當方便。但由于新用戶往往缺少有效的用戶購物行為數據，很難對其進行推薦，這便是推薦系統中著名的冷啟動問題［3］。

傳統的推薦系統沒有考慮到明確的用戶之間的關系，但社會影響力在產品市場中的重要性卻越來越大。此外，社會網絡的整合理論上可以提高目前推薦系統的性能。首先，就預測獲取的用戶及其朋友的附加信息，社交網絡提高了用戶行為和評級的理解能力。因此，我們可以更準確地對用戶偏好進行建模和解釋，最終提高預測精度。其次，由于社交網絡中存儲著好友的相關信息，這會無需再測量他們的相似度，因為兩個人是朋友的事實已經表明了他們有共同之處。因此，可以減輕數據稀疏問題。同時以社交關系為基礎的社團和數據流是大多數用戶所需要的［4］。實際上，許多用戶行為是由多個用戶以團隊的形式參與的。將推薦的對象由某些單個個體拓展到一個團體，這樣的推薦系統被人們稱之為團推薦系統（group recommender system）［5］。在朋友推薦和系統推薦之間做出選擇時，無論從推薦的質量還是推薦的有效性來看，用戶往往更傾向于前者，所以提取和量化高質量的社交關系是改善推薦質量的法寶［6］。

本文針對傳統的協同過濾都只能為單個用戶進行推薦、用戶項目推薦覆蓋率小、存在冷啟動的問題，提出了一種以社交網絡為基礎的最大團推薦算法。在YELP的數據集上的實驗結果表明根據團體推薦即提高了推薦的準確率，也緩解了推薦系統的冷啟動。

2 基本定義及算法描述

2.1 基本定義

定義1最大團問題，Maximum Clique Problem，MCP）：團就是最大完全子圖。給定一組頂點，其中一些頂點之間有邊緣，最大組是頂點的最大子集，其中每個點都直接連接到子集中的每個其他頂點。每次添加一個新點時，必須搜索的總群數至少增加一倍；因此我們有一個呈指數增長的問題［7］。

定義2協同過濾算法（Collaborative Filtering Recommendation，CF）：也被稱為社交過濾，通過利用其他人的建議信息來給出當前用戶的推薦信息。這是基于這樣的想法，即在過去對某些項目進行評估的同意者可能會再次同意。一個想要看電影的人可能會要求朋友推薦。有些類似興趣的朋友的建議比其他人的建議更受信任。該信息用于決定哪部電影可以看到。

定義3團預測評分［8］。群組G對項目i的預測評分groupprerating（G，i）由群組中每個用戶預測評分prerating（u，i）融合得到。本文采用均值策略進行偏好融合時的群組預測評分計算方法：

定義4最大獨立集（Maximum Independent Set，MIS）［9］：從頂點集中任意選取N個頂點，這N個頂點兩兩間并無直接連線。

2.2 算法描述

協同過濾算法是基于在過去對某些項目進行評估的同意者可能會再次同意的想法。一個想要看電影的人可能會要求朋友推薦。有些類似興趣的朋友的建議比其他人的建議更受信任。該信息用于決定哪部電影可以看到。不是只依靠最相似的人，而是預測通常是基于幾個人的推薦加權平均數。一個人的評分的預測由該人與預測人之間的相關性決定［10］。相關度可以由式（1）（Jaccard index）亦或者式（2）（cosine formula，余弦公式）來獲得。當依次分別算出的兩兩用戶間的相關度的時間復雜度：O（N2×D）。D為項目的數量大小，N為用戶的數量大小。

利用式（1）或者式（2）可以得到相似性矩陣。但是在很多項目中此相似性矩陣是十分稀疏的。意味著不少用戶兩兩間沒有對相同的項目發生購買行為。如果僅僅只是單純的把相似性不為零的用戶的對數求出，隨后只需計算用戶對不為零的，這樣只會使系統的復雜度升高。利用數組W［a］［b］來存儲用戶a與b有相同的購買項目行為的數量。首先創建一個倒序排列表。各個項目都記錄了發生購買行為的用戶信息。然后對每個項目的所有發生過購買行為的用戶元組（a，b），W［a］［b］均要加上1。如此就可以只需要用戶元組的相似性不為零的數據了。

當之前獲得相似性矩陣之后，就能使用式（3）來預測項目i能讓用戶u產生興趣大小。這里面S（u，k）顯示的是用戶的相似度最靠近的k個用戶的集合，N（i）顯示的是對項目i有過購買行為用戶的集合。rvi顯示用戶v對于項目i的興趣程度的大小，wuv顯示的是用戶v與用戶u的相似性的大小值。

3 基于最大團的協同過濾推薦算法

3.1 社交網絡中最大團算法選擇

3.1.1 回溯法

Bron-Kerbosch算法［11］是用來計算圖的最大團（最大全連通分量，Most significant connected component）的一種算法。其中最基礎的一種模型是利用遞歸與回溯的搜查算法。是一種比較常見的回溯算法。給定3個初始集合（X，R，P）。集合P是包含了全部頂點的集合，而R，X集合初始都為空。依次從集合P中取出一個頂點｛v｝，當集合P中再無頂點時，可能出現以下兩種狀況：

1）集合R就是最大全連通分量，也就是包含所有最大團成員，同時集合X為空值。

2）無最大團，此時回溯。

針對從各個來自與集合P中的頂點v來說，依次做以下的各項處理：

1）頂點v添加到集合R中，頂點v的鄰居頂點組成的集合N｛v｝需與X、P集合相交，這之后循環遞歸集合（X，P，R）。

2）將集合P中的頂點v刪除的同時添加頂點v到集合X中。

只有當集合X與P均為空時，集合R才是最大團的集合。

偽代碼過程：

Bron_Kerbosch_1（X，R，P）：

if P and X are both empty：

report R as a maximal clique

for each vertex v in P：

BronKerbosch1（R∪｛v｝，P ∩N（v），X∩N（v））

P=P｛v｝

X=X∪｛v｝

3.1.2 優先分支限界算法

優先分支限界算法一般是按照廣度優先或者以最小耗費優先方案搜索問題的解空間樹。

算法思想：

1）首先我們假設解空間樹已經生成了；

2）解空間樹的根結點是初始擴展結點，對于這個特殊的擴展結點，其cn值為0（表示當前團頂點數為0）；

3）首先考察其左兒子結點。在左兒子結點處，將頂點u加入到當前團中，并檢查該頂點與當前團中其他頂點之間是否有邊相連。當頂點u與當前團中所有頂點之間都有邊相連，則相應的左兒子結點是可行結點，將它加入到解空間樹中并插入活結點優先隊列，否則就不是可行結點；

4）接著繼續考察當前擴展結點的右兒子結點。當un＞bestn（bestn表示已經尋找到的團的頂點數，初始值為0）時，右子樹中可能含有最優解，此時將右兒子結點加入到解空間樹中并插入到活結點優先隊列中；

5）繼續上述3）和4）步驟直到搜索完整個解空間，算法結束；

6）搜索過程中通過上界un值來截枝避免訪問不必要的節點。

3.1.3 最大團算法性能測試與選擇

回溯法和分支限界法都是在問題的解空間樹T上做搜索策略的算法。一般來說回溯法根據算法設計的不同，求解目標不同，一種是求出符合約束條件的所有解，一種是求出其中一種可行解。若要求出所有解，由于是NP完全問題，耗費一般難以在多項式時間內完成，時間復雜性更接近蠻力窮舉法，所以本文中以求出一種可行解為目標。

通過對圖的節點與邊的擴大，分別對比了蠻力法，回溯法和分支限界法的查找步數來反應算法復雜度。如表1所示：

表1 各個最大團算法性能對比

通過表1可知隨著頂點的增加，蠻力法的步數幾乎呈現幾何級增長，而回溯法與分支限界法增長慢了許多，而且分支界限法略好于回溯法。分支限界法的求解目標也是找出滿足條件的一個解。在搜索策略上，回溯法沿著深度優先策略搜索問題的解空間樹，分支限界法則廣度優先或以最大效益優先的方式搜索問題的解空間樹。在結點的拓展方式上，回溯法中如果當前結點不能再向深處拓展則判定為死結點，應回溯到最近的活結點，而在分支界定法中，每個活結點只有一次成為拓展結點的機會，一旦放棄不再啟用。在空間復雜度上，分支限界法的空間復雜度更高，需要更多的存儲空間。

由于分支界限法，并沒有顯著提升算法的速度，卻占用了更多的存儲空間。所以綜合這些特性，本文選用了回溯法作為最大團算法的基本算法思想。

3.2 基于最大團的協同過濾改進算法

3.2.1 算法基本思想

傳統的協同過濾算法理論上是基于社會理論的，因為它們與我們參考其他人的選擇的過程類似。而最大團的團成員之間擁有相似的興趣愛好的可能性的概率理論上比協同過濾算法高。因為根據社會化理論，朋友間的興趣影響大于社會間不認識的人的興趣。朋友圈存在著顯著的興趣聚集的趨勢。即所謂的“物以類聚，人以群分”。根據此理論，我們設計基于最大團的協同過濾改進算法。

這個理論核心思想是：對于傳統的協同過濾，存在最大團關系的成員的推薦值由團成員的協同過濾值的均值決定，而不是原來協同過濾值。這樣減少了某些協同過濾的極端值對協同過濾值準確性的影響，而且對于那些缺少數據的成員，也可以通過團成員的均值來對其確定推薦值，這樣減少了冷啟動率，增加了推薦效率。

算法步驟：

1）利用Born-Kerbosch算法算出網絡中包括的所有節點數大于2的最大團。

2）利用協同過濾算法算出網絡中包括的所有節點的協同過濾值。

3）通過對各個最大團團成員之間協同過濾值求均值，作為團推薦值。將團推薦值作為用戶推薦值推薦給團員。

4）當有用戶同時在多個團中時，在不考慮各個團的權重的情況下，將多個團推薦值求均值。將團推薦值作為用戶推薦值推薦給團員。

5）不在最大團的成員，則將原始計算的協同過濾值作為推薦值推薦給用戶。

3.2.2 算法示例

如圖1，以用戶A為中心的社交網絡圖中，包括2個最大團：團1（A，E，F）與團2（A，B，C）。

圖1 用戶A的社交網絡圖

首先利用協同過濾算法求出用戶的推薦值的集合W（表2），利用Born-Kerbosch算法算出網絡中包括的所有節點數大于2的最大團，圖1中的最大團為團1（A，E，F）與團2（A，B，C）。

表2 為用戶A的社交網絡圖的部分協同推薦值

表3為團成員對所有項目評分的均值。

表3 團1與團2的集體推薦值

當有用戶同時在多個團中時（如A），在不考慮各個團的權重的情況下，將多個團推薦值求均值。將團推薦值作為用戶推薦值推薦給團員。最后將團推薦值與未出現在最大團中的成員的協同過濾推薦值放入集合F，作為最終的推薦值返回推薦給用戶。其中圖3為社交網絡圖的算法流程圖。

4 實驗結果及分析

4.1 數據集

Yelp網站是美國最著名的評論網站之一，Yelp數據集來源于Yelp舉辦的“Yelp數據集挑戰賽”的第八輪［12］。本文涉及到的部分Yelp數據集包括客戶對店鋪的評分和好友關系。數據量大約為400M。

4.2 評價標準

均方誤差（Mean Squared Error，MSE）：用于預測業務分析和供應鏈管理準確性的最常用措施之一。實際觀察值與預測值之間的平均值是平均值。誤差的平方往往會大大加重統計學異常值，影響結果的準確性。

圖2 社交網絡圖的算法流程圖

K-平均準確率（Average Precision at Kmetric，MAPK）［14］：K的平均精度是數據集中所有實例的K（APK）度量的平均精度的平均值。經常被使用的一種用于信息檢索的指標是APK。APK是對一組響應查詢提交的top-k文檔的平均相關性分數的量度。在APK的指標當中，結果集的順序位置對結果有很大的影響，因為如果結果文檔都相關且相關文檔在結果中顯示較高，則APK分數會更高。因此，這是推薦系統的良好指標。

推薦率（Recommendation rate，RA）：推薦率來描述被推薦用戶占總用戶的比率。

推薦率=被推薦用戶/總用戶數

冷啟動率［15］（Cold start rate，CSB）：冷啟動率來描述未被推薦用戶占總用戶的比率。

冷啟動率=未被推薦用戶/總用戶

ROC曲線［16］：又稱感受性曲線，是一種標準技術，用于在真陽性（TP）和假陽性（FP）錯誤率之間的一系列權衡范圍內總結分類器性能。ROC曲線是靈敏度（模型預測事件的能力正確）與可能的截止分類概率值π0的1特異性的關系曲線。

4.3 YELP數據集實驗結果分析

實驗一：算法的有效性對比

表4是兩種算法在YELP數據集中測試的效果?？傮w而言，無論是推薦率，推薦的準確率都有提升。而且對于傳統推薦系統中比較嚴重的冷啟動問題也得到了一定程度的緩解。

表4 最終實驗數據及對比

實驗二：算法敏感性和特異性

圖3為2個算法的ROC曲線圖。ROC曲線圖對連續的變量設計多個不相同的閾值，依次算出多個感性度和異常度，再以（1-異常性）為橫坐標、感性度為縱坐標勾畫成曲線圖。圖中最大團算法曲線的陰影面積更大，顯示評測的準確度更高。敏感性和特異性均較高的臨界值的點均分布在曲線的最靠近坐標圖左上方，顯示最大團無論是敏感性還是特異性均變現的比傳統的協同過濾算法優秀。

圖3 ROC曲線圖

實驗三：算法性能測試

圖4利用邏輯回歸來刻畫Precision與Recall之間的關系。由圖可知最大團正確率與召回率更高，而且正確率與召回率更加均衡。

圖4 Precision與Recall邏輯回歸圖

由上述實驗結果可知：

提出的基于最大團的協同過濾算法在無論是推薦率，推薦的準確率都有提升，而且對于傳統推薦系統中比較嚴重的冷啟動問題也得到了一定程度的緩解。

5 結語

基于最大團的協同過濾算法，融合傳統的協同過濾與社交網絡關系來進行推薦，無論在推薦率，推薦的準確率都有提升。由于利用了社團的關系推薦，冷啟動問題也得到了一定程度的緩解。但是由于社會關系數據比較少，最大團算法的提升效率并不大，而且對于團并未進行側重分析，設置必要的權重，這也讓精度提升的并不明顯，這是將來可以進一步改進和探索的方向。