基于最大團(tuán)的社交網(wǎng)絡(luò)個(gè)性化推薦?

陳小禮 汪 洋 彭艷兵

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

1 引言

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

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

本文針對傳統(tǒng)的協(xié)同過濾都只能為單個(gè)用戶進(jìn)行推薦、用戶項(xiàng)目推薦覆蓋率小、存在冷啟動的問題，提出了一種以社交網(wǎng)絡(luò)為基礎(chǔ)的最大團(tuán)推薦算法。在YELP的數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明根據(jù)團(tuán)體推薦即提高了推薦的準(zhǔn)確率，也緩解了推薦系統(tǒng)的冷啟動。

2 基本定義及算法描述

2.1 基本定義

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

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

定義3團(tuán)預(yù)測評分［8］。群組G對項(xiàng)目i的預(yù)測評分groupprerating（G，i）由群組中每個(gè)用戶預(yù)測評分prerating（u，i）融合得到。本文采用均值策略進(jìn)行偏好融合時(shí)的群組預(yù)測評分計(jì)算方法：

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

2.2 算法描述

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

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

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

3 基于最大團(tuán)的協(xié)同過濾推薦算法

3.1 社交網(wǎng)絡(luò)中最大團(tuán)算法選擇

3.1.1 回溯法

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

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

2）無最大團(tuán)，此時(shí)回溯。

針對從各個(gè)來自與集合P中的頂點(diǎn)v來說，依次做以下的各項(xiàng)處理：

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

2）將集合P中的頂點(diǎn)v刪除的同時(shí)添加頂點(diǎn)v到集合X中。

只有當(dāng)集合X與P均為空時(shí)，集合R才是最大團(tuán)的集合。

偽代碼過程：

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 優(yōu)先分支限界算法

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

算法思想：

1）首先我們假設(shè)解空間樹已經(jīng)生成了；

2）解空間樹的根結(jié)點(diǎn)是初始擴(kuò)展結(jié)點(diǎn)，對于這個(gè)特殊的擴(kuò)展結(jié)點(diǎn)，其cn值為0（表示當(dāng)前團(tuán)頂點(diǎn)數(shù)為0）；

3）首先考察其左兒子結(jié)點(diǎn)。在左兒子結(jié)點(diǎn)處，將頂點(diǎn)u加入到當(dāng)前團(tuán)中，并檢查該頂點(diǎn)與當(dāng)前團(tuán)中其他頂點(diǎn)之間是否有邊相連。當(dāng)頂點(diǎn)u與當(dāng)前團(tuán)中所有頂點(diǎn)之間都有邊相連，則相應(yīng)的左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，將它加入到解空間樹中并插入活結(jié)點(diǎn)優(yōu)先隊(duì)列，否則就不是可行結(jié)點(diǎn)；

4）接著繼續(xù)考察當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)。當(dāng)un＞bestn（bestn表示已經(jīng)尋找到的團(tuán)的頂點(diǎn)數(shù)，初始值為0）時(shí)，右子樹中可能含有最優(yōu)解，此時(shí)將右兒子結(jié)點(diǎn)加入到解空間樹中并插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中；

5）繼續(xù)上述3）和4）步驟直到搜索完整個(gè)解空間，算法結(jié)束；

6）搜索過程中通過上界un值來截枝避免訪問不必要的節(jié)點(diǎn)。

3.1.3 最大團(tuán)算法性能測試與選擇

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

通過對圖的節(jié)點(diǎn)與邊的擴(kuò)大，分別對比了蠻力法，回溯法和分支限界法的查找步數(shù)來反應(yīng)算法復(fù)雜度。如表1所示：

表1 各個(gè)最大團(tuán)算法性能對比

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

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

3.2 基于最大團(tuán)的協(xié)同過濾改進(jìn)算法

3.2.1 算法基本思想

傳統(tǒng)的協(xié)同過濾算法理論上是基于社會理論的，因?yàn)樗鼈兣c我們參考其他人的選擇的過程類似。而最大團(tuán)的團(tuán)成員之間擁有相似的興趣愛好的可能性的概率理論上比協(xié)同過濾算法高。因?yàn)楦鶕?jù)社會化理論，朋友間的興趣影響大于社會間不認(rèn)識的人的興趣。朋友圈存在著顯著的興趣聚集的趨勢。即所謂的“物以類聚，人以群分”。根據(jù)此理論，我們設(shè)計(jì)基于最大團(tuán)的協(xié)同過濾改進(jìn)算法。

這個(gè)理論核心思想是：對于傳統(tǒng)的協(xié)同過濾，存在最大團(tuán)關(guān)系的成員的推薦值由團(tuán)成員的協(xié)同過濾值的均值決定，而不是原來協(xié)同過濾值。這樣減少了某些協(xié)同過濾的極端值對協(xié)同過濾值準(zhǔn)確性的影響，而且對于那些缺少數(shù)據(jù)的成員，也可以通過團(tuán)成員的均值來對其確定推薦值，這樣減少了冷啟動率，增加了推薦效率。

算法步驟：

1）利用Born-Kerbosch算法算出網(wǎng)絡(luò)中包括的所有節(jié)點(diǎn)數(shù)大于2的最大團(tuán)。

2）利用協(xié)同過濾算法算出網(wǎng)絡(luò)中包括的所有節(jié)點(diǎn)的協(xié)同過濾值。

3）通過對各個(gè)最大團(tuán)團(tuán)成員之間協(xié)同過濾值求均值，作為團(tuán)推薦值。將團(tuán)推薦值作為用戶推薦值推薦給團(tuán)員。

4）當(dāng)有用戶同時(shí)在多個(gè)團(tuán)中時(shí)，在不考慮各個(gè)團(tuán)的權(quán)重的情況下，將多個(gè)團(tuán)推薦值求均值。將團(tuán)推薦值作為用戶推薦值推薦給團(tuán)員。

5）不在最大團(tuán)的成員，則將原始計(jì)算的協(xié)同過濾值作為推薦值推薦給用戶。

3.2.2 算法示例

如圖1，以用戶A為中心的社交網(wǎng)絡(luò)圖中，包括2個(gè)最大團(tuán)：團(tuán)1（A，E，F(xiàn)）與團(tuán)2（A，B，C）。

圖1 用戶A的社交網(wǎng)絡(luò)圖

首先利用協(xié)同過濾算法求出用戶的推薦值的集合W（表2），利用Born-Kerbosch算法算出網(wǎng)絡(luò)中包括的所有節(jié)點(diǎn)數(shù)大于2的最大團(tuán)，圖1中的最大團(tuán)為團(tuán)1（A，E，F(xiàn)）與團(tuán)2（A，B，C）。

表2 為用戶A的社交網(wǎng)絡(luò)圖的部分協(xié)同推薦值

表3為團(tuán)成員對所有項(xiàng)目評分的均值。

表3 團(tuán)1與團(tuán)2的集體推薦值

當(dāng)有用戶同時(shí)在多個(gè)團(tuán)中時(shí)（如A），在不考慮各個(gè)團(tuán)的權(quán)重的情況下，將多個(gè)團(tuán)推薦值求均值。將團(tuán)推薦值作為用戶推薦值推薦給團(tuán)員。最后將團(tuán)推薦值與未出現(xiàn)在最大團(tuán)中的成員的協(xié)同過濾推薦值放入集合F，作為最終的推薦值返回推薦給用戶。其中圖3為社交網(wǎng)絡(luò)圖的算法流程圖。

4 實(shí)驗(yàn)結(jié)果及分析

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

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

4.2 評價(jià)標(biāo)準(zhǔn)

均方誤差（Mean Squared Error，MSE）：用于預(yù)測業(yè)務(wù)分析和供應(yīng)鏈管理準(zhǔn)確性的最常用措施之一。實(shí)際觀察值與預(yù)測值之間的平均值是平均值。誤差的平方往往會大大加重統(tǒng)計(jì)學(xué)異常值，影響結(jié)果的準(zhǔn)確性。

圖2 社交網(wǎng)絡(luò)圖的算法流程圖

K-平均準(zhǔn)確率（Average Precision at Kmetric，MAPK）［14］：K的平均精度是數(shù)據(jù)集中所有實(shí)例的K（APK）度量的平均精度的平均值。經(jīng)常被使用的一種用于信息檢索的指標(biāo)是APK。APK是對一組響應(yīng)查詢提交的top-k文檔的平均相關(guān)性分?jǐn)?shù)的量度。在APK的指標(biāo)當(dāng)中，結(jié)果集的順序位置對結(jié)果有很大的影響，因?yàn)槿绻Y(jié)果文檔都相關(guān)且相關(guān)文檔在結(jié)果中顯示較高，則APK分?jǐn)?shù)會更高。因此，這是推薦系統(tǒng)的良好指標(biāo)。

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

推薦率=被推薦用戶/總用戶數(shù)

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

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

ROC曲線［16］：又稱感受性曲線，是一種標(biāo)準(zhǔn)技術(shù)，用于在真陽性（TP）和假陽性（FP）錯(cuò)誤率之間的一系列權(quán)衡范圍內(nèi)總結(jié)分類器性能。ROC曲線是靈敏度（模型預(yù)測事件的能力正確）與可能的截止分類概率值π0的1特異性的關(guān)系曲線。

4.3 YELP數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)一：算法的有效性對比

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

表4 最終實(shí)驗(yàn)數(shù)據(jù)及對比

實(shí)驗(yàn)二：算法敏感性和特異性

圖3為2個(gè)算法的ROC曲線圖。ROC曲線圖對連續(xù)的變量設(shè)計(jì)多個(gè)不相同的閾值，依次算出多個(gè)感性度和異常度，再以（1-異常性）為橫坐標(biāo)、感性度為縱坐標(biāo)勾畫成曲線圖。圖中最大團(tuán)算法曲線的陰影面積更大，顯示評測的準(zhǔn)確度更高。敏感性和特異性均較高的臨界值的點(diǎn)均分布在曲線的最靠近坐標(biāo)圖左上方，顯示最大團(tuán)無論是敏感性還是特異性均變現(xiàn)的比傳統(tǒng)的協(xié)同過濾算法優(yōu)秀。

圖3 ROC曲線圖

實(shí)驗(yàn)三：算法性能測試

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

圖4 Precision與Recall邏輯回歸圖

由上述實(shí)驗(yàn)結(jié)果可知：

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

5 結(jié)語

基于最大團(tuán)的協(xié)同過濾算法，融合傳統(tǒng)的協(xié)同過濾與社交網(wǎng)絡(luò)關(guān)系來進(jìn)行推薦，無論在推薦率，推薦的準(zhǔn)確率都有提升。由于利用了社團(tuán)的關(guān)系推薦，冷啟動問題也得到了一定程度的緩解。但是由于社會關(guān)系數(shù)據(jù)比較少，最大團(tuán)算法的提升效率并不大，而且對于團(tuán)并未進(jìn)行側(cè)重分析，設(shè)置必要的權(quán)重，這也讓精度提升的并不明顯，這是將來可以進(jìn)一步改進(jìn)和探索的方向。