王 帥 蘭少華

(南京理工大學計算機科學與工程學院 江蘇 南京 210094)

?

基于顯式和隱式社交網(wǎng)絡的混合推薦

王 帥 蘭少華

(南京理工大學計算機科學與工程學院 江蘇 南京 210094)

傳統(tǒng)的社交網(wǎng)絡推薦一般依靠用戶之間的好友關系，但好友關系不是基于共同興趣而產(chǎn)生的。針對這種情況，提出通過用戶標簽所表達的情感興趣來擴展用戶好友關系，形成基于用戶好友關系和共同興趣的混合推薦。利用用戶間直接的朋友關系構建顯式社交網(wǎng)絡，利用標簽數(shù)據(jù)構建隱式社交網(wǎng)絡;在顯式和隱式社交網(wǎng)絡圖中分別采用提出的SNA_SPFA(Social Networks Algorithm Based on Shortest Path Faster Algorithm)算法得到推薦結果;最后按照一定權重混合兩種推薦結果。實驗表明，該方法優(yōu)于傳統(tǒng)的協(xié)同過濾方法和社交網(wǎng)絡推薦。

社交網(wǎng)絡 標簽 情感 混合推薦

0 引 言

隨著信息技術和互聯(lián)網(wǎng)的發(fā)展，個性化推薦逐漸融入到了人們的日常生活中。而個性化推薦一般需要滿足兩個基本條件：第一是信息過載，如果用戶很容易就能在互聯(lián)網(wǎng)上找到想要的資源，就不需要個性化推薦了；第二是用戶一般沒有特別明確的需求，因為如果有明確的需求就可以通過搜索引擎來找到感興趣的物品。個性化推薦在當前的互聯(lián)網(wǎng)產(chǎn)品中已被廣泛應用，包括大家所熟知的電商推薦、話題推薦、相關搜索、交友推薦等。

如今，社交網(wǎng)絡在我們日常生活中開始占據(jù)越來越重要的地位，它不僅定義了用戶之間的聯(lián)系，而且隱含了豐富的用戶偏好信息。相對于傳統(tǒng)的推薦方法，如協(xié)同過濾、基于內容的推薦等推薦方法，基于社交網(wǎng)絡的推薦較好地利用了用戶之間的朋友關系，這和現(xiàn)實生活中向朋友尋求推薦具有較大相似性。大量研究實驗表明，基于社交網(wǎng)絡的推薦要優(yōu)于傳統(tǒng)的推薦方法。

在社交網(wǎng)絡中，標簽的應用也越來越廣。推薦系統(tǒng)的目的是聯(lián)系用戶的興趣和相應的物品，而標簽作為物品的一種特殊特征，在一定程度上表達了用戶對物品的興趣，所以標簽特別適合作為推薦的中間媒介。標簽一般分為兩種：一種是特定領域的專家給物品打的標簽，這種標簽一般具有較高的信任度，在屬性上更傾向于物品的固有屬性；另一種是普通用戶給物品打的標簽，簡稱UGC。這種標簽一方面表達了用戶的興趣，另一方面表達了物品的語義，從而將用戶興趣和物品聯(lián)系起來[1]。

1 相關工作

傳統(tǒng)的推薦方法主要包括基于內容的過濾和協(xié)同過濾?；趦热莸倪^濾通過物品特征和用戶偏好來推薦物品。然而，這種方法存在很多局限，目前商業(yè)領域幾乎沒有純粹的基于內容的推薦系統(tǒng)。協(xié)同過濾是推薦系統(tǒng)中最古老的算法，它主要分為兩種：一種是基于用戶的協(xié)同過濾，該算法首先通過用戶對物品的評分來計算所有用戶之間興趣的相似度，計算方法一般采用余弦相似性或皮爾遜相關性的方法；然后通過與目標用戶興趣最相似的K個用戶去預測目標用戶對某一物品的興趣程度。另一種是基于物品的協(xié)同過濾，該算法給用戶推薦那些和他們之前喜歡的物品相似的物品[6]。但協(xié)同過濾最大的局限在于數(shù)據(jù)的稀疏性和計算復雜度，而且K值的選擇也相應地影響推薦的效果[2]。

隨著Web 2.0的發(fā)展和興起，社交網(wǎng)絡在人們的日常生活中扮演著越來越重要的角色，而且越來越多的研究者開始將社交網(wǎng)絡的方法引入到推薦系統(tǒng)中。研究發(fā)現(xiàn)，基于社交網(wǎng)絡的推薦效果要優(yōu)于傳統(tǒng)的協(xié)同過濾。如文獻[3]在3個真實的電影推薦系統(tǒng)和3個圖書推薦系統(tǒng)上，分別進行社會化推薦和基于協(xié)同過濾的推薦，發(fā)現(xiàn)社會化推薦結果的滿意度明顯高于基于協(xié)同過濾的算法。雖然實驗存在一些問題，比如不是雙盲實驗，用戶知道結果來自哪個推薦系統(tǒng)，但還是得到了業(yè)界認可。部分文獻將協(xié)同過濾與社交網(wǎng)絡的推薦相結合，用戶之間邊的權重由熟悉程度和興趣相似度按一定權重混合，然后采用重啟型隨機游走算法，取得了較好的實驗效果。但所采用的重啟型隨機游走算法計算復雜度過高，且用戶全部好友的歷史行為數(shù)據(jù)過于龐大，在實際環(huán)境中難以操作[4,5,9,12]。

因此，本文提出一種基于顯式和隱式社交網(wǎng)絡的混合推薦算法，主要貢獻如下：

(1) 對標簽進行情感分析，然后利用情感得分計算用戶之間的相似度來構建隱式社交網(wǎng)絡，擴展用戶的好友關系。

(2) 在所構建的顯式和隱式社交網(wǎng)絡上，采用下文提出的SNA_SPFA算法進行推薦。

(3) 將以上兩種推薦結果按照加權組合的方式進行混合，得到最終的推薦結果。

2 基于顯式和隱式社交網(wǎng)絡的推薦

2.1 顯式社交網(wǎng)絡

根據(jù)用戶之間的朋友關系，可以用圖來表示一個社交網(wǎng)絡。用圖G(V,E,W)定義一個社交網(wǎng)絡，其中V是頂點集合，每一個頂點代表社交網(wǎng)絡中的一個用戶；E是邊的集合，如果用戶Va和Vb是朋友關系，那么就有一條邊E(Va,Vb)直接連接這兩個用戶；而W(Va,Vb)則定義邊的權重，在這里代表兩個用戶之間的熟悉程度或信任程度。

目前社交網(wǎng)絡上主要有三種不同的社交網(wǎng)絡數(shù)據(jù)。一種是雙向確認的社交網(wǎng)絡數(shù)據(jù)，這類社交網(wǎng)絡以Facebook和人人網(wǎng)為代表，好友關系的形成需雙方確認，一般采用無向圖表示；第二種是單向關注的社交網(wǎng)絡數(shù)據(jù)，這類社交網(wǎng)絡以Twitter和新浪微博為代表，好友關系的形成是單向的，一般采用有向圖表示；第三種是基于社區(qū)的社交網(wǎng)絡數(shù)據(jù)，在這種數(shù)據(jù)中，用戶之間并沒有明確的關系，但是這類數(shù)據(jù)中包含了用戶屬于不同社區(qū)的信息。本文中采用的是雙向確認的社交網(wǎng)絡數(shù)據(jù)。

2.2 隱式社交網(wǎng)絡

標簽作為一種重要的用戶行為數(shù)據(jù)，蘊含了豐富的用戶興趣信息，因此對標簽數(shù)據(jù)的深入研究有助于改進和提高推薦系統(tǒng)的質量。由于讓專家給物品打標簽的成本較大，而且在Web 2.0時代不能代表用戶的個性化情感傾向。而UGC標簽是一種表達用戶興趣和物品語義的重要方式，所以本文根據(jù)這種UGC標簽來分析用戶的情感從而進行個性化推薦。

2.2.1 情感分析

本文首先根據(jù)所要推薦的領域和常用的情感詞典來建立實驗所需的情感詞典。然后對標簽進行情感分析，將標簽情感分為正向情感、中性情感和負向情感。最后將標簽情感轉換為對物品的顯式評分，來表示對物品感興趣的程度。其中正向情感對應1分，中性情感對應0.5分，負向情感對應0分。

2.2.2 隱式好友關系的建立

由于用戶對同一個物品可能會打多個標簽，我們取多個情感標簽評分的平均值來代表用戶對物品的評分。將用戶所打的標簽轉換為情感評分后，采用常用的Pearson相關系數(shù)來計算用戶間相似度，Pearson相關系數(shù)的取值從+1(強正相關)到-1(強負相關)。當用戶間相似度不小于閾值0.3時，則可在兩用戶之間建立隱式好友關系。Pearson相關系數(shù)的計算公式如下：

(1)

2.2.3 隱式社交網(wǎng)絡圖

本文通過UGC標簽來擴展用戶社交關系，若不同用戶對相同物品打了相同或相似的標簽，則認為用戶之間存在著一定程度的隱式好友關系。隱式社交網(wǎng)絡通過以下三步來建立：(1)將用戶對物品所打的標簽按所表達的情感轉換為相應的情感評分；(2)通過Pearson相關系數(shù)來計算用戶之間的相似度，當相似度大于一定閾值時，可建立直接的隱式好友關系，類似于顯式網(wǎng)絡中直接的朋友關系；(3)用圖G′(V,E,W)來表示所建立的隱式社交網(wǎng)絡。

2.3 推薦算法

社交網(wǎng)絡定義了用戶之間的好友關系，而用戶行為數(shù)據(jù)集定義了不同用戶的歷史行為和興趣傾向。傳統(tǒng)的協(xié)同過濾只考慮了用戶的歷史行為數(shù)據(jù)，而忽略了用戶之間的社交關系對推薦結果的影響。單純的社交推薦利用了用戶之間的社交關系，卻忽略了用戶的興趣往往和用戶好友的興趣并不一致。本文就是通過利用這兩種數(shù)據(jù)，在所構建的顯式和隱式社交網(wǎng)絡圖中分別采用相同的算法來計算用戶對物品的興趣程度。

2.3.1 信任度計算

由于現(xiàn)實生活中，好友的熟悉程度存在很大差別，為了更真實模擬現(xiàn)實生活，本文認為用戶之間的熟悉程度和信任程度正相關。用戶間共同好友越多，則兩個用戶之間更加信任彼此，且信任可以在網(wǎng)絡中進行傳播[7]。針對社交網(wǎng)絡圖，通過以下方法來計算用戶間的信任度：

(1) 在所構建的顯式社交網(wǎng)絡圖G(V,E,W)中，首先對所有相連的邊分配一個初始的權重Tij=0.5來表示用戶間的信任程度；對沒有邊相連的用戶，我們認為用戶之間初始的信任程度為0。在隱式社交網(wǎng)絡圖G′(V,E,W)中，初始邊的權重即上文中計算的用戶間相似度。(2) 在社交網(wǎng)絡圖G(V,E,W)和G′(V,E,W)中，用戶節(jié)點之間路徑大致分為單路徑和多路徑。單路徑意味著只有一條從ai到as的路徑，圖1表示從ai到as唯一的一條路徑。對單路徑用戶之間信任程度的計算方法為:

Tis=∏(m,n)∈path(i,s)Tmn

(2)

圖1 單路徑信任傳播

通常，所構造的社交網(wǎng)絡圖中，用戶節(jié)點之間的路徑不止一條。圖2表示從ai到as有兩條路徑。Path(ai，as)={((ai，aj)，(aj，ak)，(ak，as))，((ai，ar)，(ar，as))}。

圖2 多路徑信任傳播

為了計算多路徑用戶之間的信任程度，采用如下的計算方法，這種方法通過用戶Ui的所有鄰居節(jié)點采用加權平均的方法來計算。計算方法如下：

(3)

其中N(i)為Ui的所有鄰居節(jié)點。

2.3.2 預測評分

當預測用戶對某物品p的興趣時，從目標用戶節(jié)點首先訪問直接相連的用戶，但是有時這個相鄰節(jié)點并沒有對物品p的評價或者用戶之間具有較低的信任值，所以需要訪問不相鄰的其他用戶節(jié)點。本文采用如下公式來預測用戶對物品p的興趣：

P(a,p) =∑b∈V(a)TabRbp

(4)

其中V(a)是分別在顯式或隱式網(wǎng)絡圖中，從目標用戶Ua能訪問到的所有用戶節(jié)點。Tab是用戶Ua和Ub的信任度，Rbp是用戶Ub對物品p的興趣度，由用戶的行為數(shù)據(jù)來確定，而P(a,p)是預測用戶Ua對物品p的興趣度。

2.3.3 SNA_SPFA算法

為了計算從用戶Ua能訪問到的所有用戶節(jié)點，我們采用一種SNA_FPFA算法。該算法分別在顯式和隱式社交網(wǎng)絡圖中尋找符合一定信任度的用戶節(jié)點，并返回相應的信任度。

在現(xiàn)實生活中，我們總是向有限的朋友尋求推薦，所以為了和現(xiàn)實中場景更加相似，本文中V(a)并不是社交網(wǎng)絡圖中所有用戶節(jié)點。SNA_SPFA算法設定了2個全局限制參數(shù)：trust_threshold和max_nodes。trust_threshold定義了節(jié)點間最小信任度閾值，max_nodes定義了計算過程中從目標用戶節(jié)點訪問的最大節(jié)點數(shù)。

在計算目標用戶對物品興趣的過程中，本文所采用的SNA_SPFA算法計算過程類似于SPFA算法，采用深度優(yōu)先遍歷的方法來逐層訪問其他用戶節(jié)點，遍歷過程中采用優(yōu)先隊列來存儲訪問到的節(jié)點。

算法:SNA_SPFA

輸入：圖G(V，E，W)或G′(V,E,W)，目標起始節(jié)點OriginNode

輸出：目標用戶感興趣的物品集

1:InitQueue(Que);

//Que是一個優(yōu)先隊列

2:A=getAdjacentNodes(OriginNode);

//獲得目標節(jié)點的相鄰節(jié)點

3:for every node i in A do

4:EnQueue(Que,i);

//插入相鄰節(jié)點到隊列中

5:end for

6:while(!Que.Empty()){

7:DeQueue(Que,u);

//彈出隊列中頭元素u

8:if((++visitedNodes)>max_nodes)

return false;

9:if((u.rating!=NULL)&&(GetTrust(OriginNode,u)>=trust_threshold)){

//節(jié)點u滿足條件

10:u.visited = TRUE;

//標記u已被訪問過

11:return Response(rating)}

//返回起始目標節(jié)點感興趣的物品和興趣度12:else{

13:A= getAdjacentNodes (u);

14:for every node i in A do

15: if((!i.visited)&&(i!= OriginNode))

//節(jié)點i沒被訪問過且不是原始目標節(jié)點

16: EnQueue(Que,i);

17:end for}}

2.4 混合推薦方法

首先分別在顯式社交網(wǎng)絡和隱式社交網(wǎng)絡中按照上文算法得到目標用戶Ua最感興趣的前N個物品集合，分別記為Rc和Rs。對Rc中的任一物品p1，目標用戶對它的興趣度為P(a,p1);對Rs中的任一物品p2，目標用戶對它的興趣度為P(a,p2)。然后對由兩種社交網(wǎng)絡中得的推薦結果，按一定權重混合用戶對物品p的興趣度，混合公式如下：

(5)

混合方法對只在Rc中的物品p1，興趣度按權重α計算；對只在Rs中的物品p2，興趣度按權重(1-α)計算；對同時出現(xiàn)在Rc和Rs中物品，則分別按照權重α和(1-α)混合后相加。最后按照混合后用戶對物品的興趣度排序，取前N個興趣度高的物品得到最終的推薦結果。

3 實驗評估

3.1 實驗設計

本文采用的數(shù)據(jù)集是ACM第5次推薦系統(tǒng)大會公開的last.fm數(shù)據(jù)集，該數(shù)據(jù)集收集了last.fm在線音樂網(wǎng)站上1892位用戶的歷史行為數(shù)據(jù)。該數(shù)據(jù)集包括1892位用戶和17 632首音樂、12 717對用戶之間的朋友關系、92 834條用戶聽歌記錄，11 946個標簽和186 479條用戶對歌曲所打的標簽記錄。

該數(shù)據(jù)集中，用戶對音樂只記錄了聽歌次數(shù)而沒有直接的評分。本文將用戶對音樂的收聽次數(shù)轉換為間接評分來進行實驗，其中收聽次數(shù)越多則間接評分越高。實驗中將數(shù)據(jù)集隨機分為8份，其中訓練集占7份，測試集占1份。為了保證測評指標不是過擬合的結果，需要進行8次實驗，每次使用不同的測試集，最后將8次實驗測出的評測指標的平均值作為最終的評測指標。每次實驗中通過直接的朋友關系構造顯式社交網(wǎng)絡，通過標簽來構建隱式社交網(wǎng)絡，根據(jù)好友對物品的間接評分來預測目標用戶對物品的興趣度。為了比較實驗效果，將本文所采用的混合社交推薦方法與傳統(tǒng)協(xié)同過濾和社交網(wǎng)絡推薦進行對比。

3.2 評估標準

預測準確度是衡量一個推薦系統(tǒng)或推薦算法預測用戶行為的能力。由于離線的推薦算法有不同的研究方向，預測準確度主要有兩個指標：一是評分預測，主要通過均方差和平均絕對誤差來評價；二是TopN推薦，主要通過準確率和召回率來度量。為了比較三種方法的好壞，本文采用準確率(precision)、召回率(recall)和F1值來度量。

準確率描述的是最終推薦列表中有多少比例是已經(jīng)發(fā)生過的用戶-物品評分記錄。召回率描述的是算法推薦的物品有多少包含在最終的推薦列表中。而F1值是準確率和召回率的一種加權平均。算法對用戶Ua推薦N個物品(記為R(a)),令用戶Ua在測試集上喜歡的物品集合為T(a)。則準確率、召回率和F1值通過以下公式計算：

(6)

(7)

(8)

3.3 實驗結果及分析

在本文算法中，主要有二個參數(shù)對實驗影響較大，分別是最大節(jié)點數(shù)max_nodes(分別對應其他兩種方法中相似用戶數(shù)K和好友數(shù)K)和α。在本文的混合推薦中，參數(shù)α決定了顯式和隱式社交網(wǎng)絡推薦的權重。從圖3中實驗發(fā)現(xiàn)，當α=0.7時，實驗效果較好，這說明并不是顯式社交推薦所占權重越大越好，也驗證了顯式社交網(wǎng)絡中朋友關系并不是基于共同興趣而產(chǎn)生的。而協(xié)同過濾中相似用戶K和傳統(tǒng)社交推薦中最熟悉的好友數(shù)K也是實驗的重要參數(shù)。所以，本文詳細比較了不同K值下三種推薦方法的推薦質量。

圖3 在不同α值下混合推薦的F1值

圖4表示三種方法中準確率隨最近鄰個數(shù)K的變化曲線，圖5表示三種方法中召回率隨最近鄰個數(shù)K的變化曲線，圖6的結果由圖4和圖5中數(shù)據(jù)來決定，但它反映了實驗的總體效果。從圖6中可以看出，當K=10時，三種方法在該數(shù)據(jù)集上的F1值都達到最大。這同時也啟示我們可以對歷史行為較少的用戶導入少量社交信息，從而在一定程度上解決用戶冷啟動問題(用戶冷啟動指新用戶到來時，由于缺少用戶的行為數(shù)據(jù)而無法預測其興趣，也就無法給用戶做個性化推薦)。從實驗結果可以看出，本文提出的方法要優(yōu)于傳統(tǒng)的協(xié)同過濾和社交網(wǎng)絡推薦。

圖4 在不同K值下三種方法的準確率

圖5 在不同K值下三種方法的召回率

圖6 在不同K值下三種方法的F1值

4 結 語

本文提出利用標簽數(shù)據(jù)來擴展用戶的好友關系，進一步挖掘用戶的社交信息，然后分別在所構建的顯式和隱式社交網(wǎng)絡中進行推薦，最后按一定權重混合兩種推薦結果。實驗結果表明，本文方法要優(yōu)于傳統(tǒng)的推薦方法，但也存在一些不足之處，具有一定提升空間。未來將進一步研究隱式社交網(wǎng)絡的構建和相應的推薦方法。

[1] 項亮.推薦系統(tǒng)實踐[M].北京:人民郵電出版社,2012.

[2] Xing Z,Wang X X,Wang Y.Enhancing collaborative filtering music recommendation by balancing exploration and exploitation [C]//Proceedings of the 15th Conference on the International Society for Music Information Retrieval (ISMIR 2014),2014:445-450.

[3] Sinha R,Swearingen K.Comparing Recommendations Made by Online Systems and Friends[C]//DELOS workshop:personalisation and recommender systems in digital libraries,2001.

[4] Konstas I,Stathopoulos V,Jose J M.On social networks and collaborative recommendation[C]//Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval.ACM,2009:195-202.

[5] Yang L,Gopalakrishnan A K.A collaborative filtering recommendation based on user profile and user behavior in online social networks[C]//2014 International Computer Science and Engineering Conference (ICSEC).IEEE,2014:273-277.

[6] 羅辛，歐陽元新，熊璋,等． 通過相似度支持度優(yōu)化基于K 近鄰的協(xié)同過濾算法[J]．計算機學報，2010，33( 8):1437-1445.

[7] He C B,Tang Y,Chen G H,et al.Collaborative Recommendation Model Based on Social Network and Its Application[J].Journal of Convergence Information Technology,2012,7(2):253-261.

[8] Han J W,Kamber M,Pei J.Data mining:concepts and techniques:concepts and techniques [M].Amsterdam:Elsevier,2011.

[9] 俞琰，邱廣華．用戶興趣變化感知的重啟動隨機游走推薦算法研究[J]．現(xiàn)代圖書情報技術，2012,28(4):48 -53.

[10] 馮勇，李軍平，徐紅艷，等． 基于社會網(wǎng)絡分析的協(xié)同推薦方法改進[J]．計算機應用，2013，33( 3):841-844.

[11] Yang X W,Steck H,Liu Y.Circle-based recommendation in online social networks[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM,2012:1267-1275.

[12] Yan Y,Qiu G H.Algorithm of Friend Recommendation in Online Social Networks Based on Local Random Walk [J].Systems Engineering,2013,31(2):47-54.

[13] Chen H C,Chen A L P.A music recommendation system based on music data grouping and user interests[C]//Proceedings of the tenth international conference on Information and knowledge management.ACM,2001:231-238.

MIXED RECOMMENDATION BASED ON EXPLICIT AND IMPLICIT SOCIAL NETWORKS

Wang Shuai Lan Shaohua

(SchoolofComputerScienceandEngineering,NanjingUniversityofScienceandTechnology，Nanjing210094，Jiangsu,China)

Traditional social networks recommendation usually relies on friendships between users,but the friendships are not based on common interests.In light of this situation,we propose to expand users’ friendships by emotion and interest expressed in users’ tags,and to form the mixed recommendation based on users’ friendships and common interests.First,we use direct friendship between users to construct an explicit social network,and use tag data to construct an implicit social network.Then we apply the proposed SNA_SPFA algorithm to explicit and implicit social graphs respectively to get recommendation result.Finally,we mix the two recommendation results according to a certain weight.Experiments show that this method is superior to traditional collaborative filtering methods and social network recommendations.

Social networks Tag Emotion Mixed recommendation

2015-08-15。國家自然科學基金項目(61170035)。王帥，碩士生，主研領域：推薦系統(tǒng)，社交網(wǎng)絡，網(wǎng)絡安全。蘭少華，教授。

TP391

A

10.3969/j.issn.1000-386x.2016.11.009