朱彥杰

（許昌學(xué)院，河南 許昌 461000）

美國著名的第三方調(diào)查機構(gòu)尼爾森調(diào)查了影響用戶相信某個推薦的因素[1]，調(diào)查結(jié)果顯示，90%的用戶相信朋友對他們的推薦，70%的用戶相信網(wǎng)上其他用戶對廣告商品的評論。從該調(diào)查可以看到，好友的推薦對于增加用戶對推薦結(jié)果的信任度非常重要。在社交網(wǎng)站中，可以通過好友給自己過濾信息，只關(guān)注與閱讀和自己有共同興趣好友分享來的信息，從而避免了很多無關(guān)的信息，自然地減輕了信息過載問題。

在社交網(wǎng)站方面，國外以Facebook 和Twitter 為代表，國內(nèi)社交網(wǎng)站，以QQ 空間、人人網(wǎng)、朋友網(wǎng)、新浪微博等為代表；這些社交網(wǎng)站形成了兩類社交網(wǎng)絡(luò)結(jié)構(gòu)。一種是，好友一般都是自己在現(xiàn)實社會中認(rèn)識的人，比如同事、同學(xué)、親戚等，并且這種好友關(guān)系是需要雙方確認(rèn)的，如Facebook、QQ 空間，這種社交網(wǎng)絡(luò)稱為社交圖譜。另一種是，好友往往都是現(xiàn)實中自己不認(rèn)識的，而只是出于對對方言論的興趣而建立好友關(guān)系，好友關(guān)系也是單向的關(guān)注關(guān)系，如Twitter、新浪微博，這種社交網(wǎng)絡(luò)稱為興趣圖譜。同時，也必須指出，任何一個社會化網(wǎng)站都不是單純的社交圖譜或興趣圖譜。在QQ 空間中大多數(shù)用戶聯(lián)系基于社交圖譜，而在微博上大多數(shù)用戶聯(lián)系基于興趣圖譜。在微博中，也會關(guān)注現(xiàn)實中的親朋好友，在QQ 中也會和部分好友有共同興趣。

1 社交網(wǎng)絡(luò)及其數(shù)據(jù)分類

在社交網(wǎng)絡(luò)中，需要表示用戶之間的聯(lián)系，可以用圖G(V，E，w)定義一個社交網(wǎng)絡(luò)，其中V 是頂點集合，每個頂點代表一個用戶，E 是邊集合，如果用戶va 和vb 有社交網(wǎng)絡(luò)關(guān)系，那么就有一條邊e(va，vb)連接這兩個用戶，w(va，vb)用來定義邊的權(quán)重。前面提到基于社交圖譜或興趣圖譜的兩種社交網(wǎng)絡(luò)，基于社交圖譜的朋友關(guān)系是需要雙向確認(rèn)的，因而可以用無向邊連接有社交網(wǎng)絡(luò)關(guān)系的用戶；基于興趣圖譜的朋友關(guān)系是單向的，可以用有向邊代表這種社交網(wǎng)絡(luò)上的用戶關(guān)系。對圖G 中的用戶頂點u，定義out(u)為頂點u 指向的頂點集合（也就是用戶u 關(guān)注的用戶集合），定義in(u)為指向頂點u 的頂點集合（也就是關(guān)注用戶u 的用戶集合）。顯然在無向社交網(wǎng)絡(luò)中out(u)=in(u)。一般來說，有3 種不同的社交網(wǎng)絡(luò)數(shù)據(jù)[2]。

雙向確認(rèn)的社交網(wǎng)絡(luò)數(shù)據(jù)：在以Facebook 和人人網(wǎng)為代表的社交網(wǎng)絡(luò)中，用戶A 和B 之間形成好友關(guān)系需要通過雙方的確認(rèn)。因此，這種社交網(wǎng)絡(luò)一般可以通過無向圖表示。

單向關(guān)注的社交網(wǎng)絡(luò)數(shù)據(jù)：在以Twitter 和新浪微博為代表的社交網(wǎng)絡(luò)中，用戶A 可以關(guān)注用戶B 而不需要得到用戶B 的允許，因此這種社交網(wǎng)絡(luò)中的用戶關(guān)系是單向的，可以通過有向圖表示。

基于社區(qū)的社交網(wǎng)絡(luò)數(shù)據(jù)：還有一種社交網(wǎng)絡(luò)數(shù)據(jù)，用戶之間并沒有明確的關(guān)系，但是這種數(shù)據(jù)包含了用戶屬于不同社區(qū)的數(shù)據(jù)。比如豆瓣小組，屬于同一個小組可能代表了用戶興趣的相似性。

2 基于社交網(wǎng)絡(luò)的推薦算法

2.1 基于鄰域的社會化推薦算法

假設(shè)給定一個社交網(wǎng)絡(luò)及其用戶行為數(shù)據(jù)集，社交網(wǎng)絡(luò)列出了用戶之間的好友關(guān)系，用戶行為數(shù)據(jù)集給出了不同用戶的歷史行為和興趣數(shù)據(jù)，在這種情況，給用戶推薦好友喜歡的物品集合，其算法思想：

用戶u 對物品i 的興趣pui可以通過如下公式（1）計算：其中out(u)是用戶u 的好友集合，如果用戶v 喜歡物品i，則rvi=1，否則rvi=0。另外，要注意的是，在用戶u 的好友中，不同的好友和用戶u 的熟悉程度和興趣相似度也是不同的。因而，應(yīng)該在推薦算法中考慮好友和用戶的熟悉程度以及興趣相似度，由公式（2）所示：wui由兩部分相似度構(gòu)成，一部分是用戶u和用戶v 的熟悉程度，另一部分是用戶u 和用戶v 的興趣相似度。

用戶u 和用戶v 的熟悉程度主要描述用戶u 和v 在現(xiàn)實生活中的熟悉程度。這里熟悉度依據(jù)用戶之間的共同好友比例來度量。熟悉程度由公式（3）表示。用戶u 和用戶v 的興趣相似度的度量方法是：如果兩個用戶喜歡的物品集合重合度很高，兩個用戶的興趣相似度就很高。興趣相似度由公式（4）表示。其中N(u)是用戶u 喜歡的物品集合。

2.2 基于圖的社會化推薦算法

社交網(wǎng)站中存在兩種關(guān)系，一種是用戶對物品的興趣關(guān)系，一種是用戶之間的社交網(wǎng)絡(luò)關(guān)系。通過圖模型來表示這兩種關(guān)系，便于對用戶進行個性化推薦。用社交網(wǎng)絡(luò)圖來表示用戶的社交關(guān)系，用戶物品二分圖來描述用戶對物品的行為，這兩個圖可以合并成一個圖。如圖1，該圖上有用戶頂點（圓圈）和物品頂點（方塊）兩種頂點。若用戶u對物品i 產(chǎn)生過行為，那么兩個節(jié)點之間就有邊相連。圖1 中用戶A對物品a、e 產(chǎn)生過行為。如果用戶u 和v 是好友，有一條邊連接這兩個用戶，圖中用戶A 和B、D 是好友。

在社交網(wǎng)絡(luò)中，除了常見的、用戶和用戶之間直接的社交網(wǎng)絡(luò)關(guān)系，還有一種關(guān)系，即兩個用戶屬于同一個社群?？梢约尤胍环N節(jié)點表示社群（如圖2，最左邊一列的節(jié)點，六邊框），而如果用戶屬于某一社群，圖中就有一條邊聯(lián)系用戶對應(yīng)的節(jié)點和社群對應(yīng)的節(jié)點。

圖1 社交網(wǎng)絡(luò)圖和用戶物品二分圖的結(jié)合

圖2 融合兩種社交網(wǎng)絡(luò)信息的圖模型

在定義完圖中的頂點和邊后，需要定義邊的權(quán)重，其中用戶和用戶之間邊的權(quán)重可以定義為用戶之間的相似度的α倍（包括熟悉程度和興趣相似度），而用戶和物品之間的權(quán)重可以定義為用戶對物品喜歡程度的α倍。α 和β 需要根據(jù)應(yīng)用的需求確定。如果希望用戶好友的行為對推薦結(jié)果產(chǎn)生比較大的影響，就選擇比較大的α，相反，如果希望用戶的歷史行為對推薦結(jié)果產(chǎn)生比較大的影響，就選擇比較大的β。

在定義完圖中的頂點、邊和邊的權(quán)重后，可以利用PersonalRank算法[3]度量圖中任兩個頂點之間的相關(guān)性，從而給每個用戶生成推薦結(jié)果。具體如下：假設(shè)要給用戶u 進行個性化推薦，可以從用戶u 對應(yīng)的節(jié)點vu開始在用戶物品二分圖上進行隨機游走，游走到任何一個節(jié)點時，首先按照概率α 決定是繼續(xù)游走，還是停止這次游走并從vu節(jié)點開始重新游走。如果決定繼續(xù)游走，那么就從當(dāng)前節(jié)點指向的節(jié)點中按照均勻分布隨機選擇一個節(jié)點作為游走下次經(jīng)過的節(jié)點。這樣，經(jīng)過很多次隨機游走后，每個物品節(jié)點被訪問到的概率會收斂到一個數(shù)。最終的推薦列表中物品的權(quán)重就是物品節(jié)點的訪問概率。

3 實際系統(tǒng)中的社會化推薦算法

基于鄰域的社會化推薦算法比較簡單，在實際系統(tǒng)中卻是難以操作的，因為該算法需要事先獲得用戶所有好友的歷史行為數(shù)據(jù)，而這一操作在實際系統(tǒng)中是比較重的操作，因為大型網(wǎng)站中用戶數(shù)目非常龐大，用戶的歷史行為記錄也非常龐大，所以不太可能將用戶的所有行為都緩存在內(nèi)存中，只能在數(shù)據(jù)庫前做一個熱數(shù)據(jù)的緩存。如果需要比較實時的數(shù)據(jù)，這個緩存中的數(shù)據(jù)就要比較頻繁地更新，因此避免不了數(shù)據(jù)庫的查詢，然而，數(shù)據(jù)庫查詢一般是很慢的，特別是針對行為很多的用戶更是如此。因而，若一個算法再給一個用戶做推薦時，需要他所有好友的歷史行為數(shù)據(jù)，這在實際環(huán)境中是比較困難的。

為了讓它能夠具有比較快的響應(yīng)時間，需要改進基于鄰域的社會化推薦算法。改進的方法有兩種：一種是兩處截斷法，第一處截斷就是在拿用戶好友集合時并不拿出用戶所有的好友，而是只拿出和用戶相似度最高的N 個好友（N 取一個比較小的數(shù)），從而給該用戶做推薦時可以只查詢N 次用戶歷史行為接口。第一處截斷在查詢每個用戶的歷史行為時，可以只返回用戶最近1 個月的行為，這樣就可以在用戶行為緩存中緩存更多用戶的歷史行為數(shù)據(jù)，從而加快查詢用戶歷史行為接口的速度。另一種解決方法是重新設(shè)計數(shù)據(jù)庫。通過前面分析可以發(fā)現(xiàn)，社會化推薦中關(guān)鍵的操作就是獲得用戶所有好友的行為數(shù)據(jù)，然后通過一定的聚合展示給用戶。如果對照一下微博，就會發(fā)現(xiàn)微博中每個用戶都有個信息墻，這個墻上實時展示著用戶關(guān)注的所有好友的動態(tài)。因此，只要能夠?qū)崿F(xiàn)這個信息墻，就能夠?qū)崿F(xiàn)社會化推薦算法。Twitter 給每個用戶維護一個消息隊列，當(dāng)一個用戶發(fā)表一條微博時，所有關(guān)注他的用戶的消息隊列中都會加入這條微博。這樣用戶獲取信息墻時可以直接讀消息隊列，所有終端用戶的讀操作很快。Twitter 這種架構(gòu)思想[4]移植到社會化推薦系統(tǒng)中，其具體設(shè)計為：首先，為每個用戶維護一個消息隊列，用于存儲他的推薦列表；接著，當(dāng)一個用戶喜歡一個物品時，就將（物品ID、用戶ID 和時間）這條記錄寫入關(guān)注該用戶的推薦列表消息隊列中；最后，當(dāng)用戶訪問推薦系統(tǒng)時，讀出他的推薦列表消息隊列，對于這個消息隊列中的每個物品，重新計算該物品的權(quán)重。計算權(quán)重時需要考慮物品在隊列中出現(xiàn)的次數(shù)，物品對應(yīng)的用戶和當(dāng)前用戶的熟悉程度、物品的時間戳。同時計算出每個物品被哪些好友喜歡過，用這些好友作為物品的推薦解釋。

4 結(jié)束語

社會化推薦得到許多網(wǎng)站的重視，一方面好友推薦可以增加推薦的信任度，好友往往是用戶最信任的，用戶往往不一定信任計算機的智能，但會信任好朋友的推薦。另一方面，社交網(wǎng)絡(luò)可以解決冷啟動問題，當(dāng)一個新用戶通過微博或者Facebook 賬號登錄網(wǎng)站時，可以從社交網(wǎng)站中獲取用戶的好友列表，然后給用戶推薦好友在網(wǎng)站上喜歡的物品。從而可以在沒有用戶行為記錄時就給用戶提供較高質(zhì)量的推薦結(jié)果，部分解決了推薦系統(tǒng)的冷啟動問題。當(dāng)然，社會化推薦也有不足，其中最主要的是就是很多時候并不一定能提高推薦算法的離線精度（準(zhǔn)確率和召回率）。特別是在基于社交圖譜數(shù)據(jù)的推薦系統(tǒng)中，因為用戶的好友關(guān)系不是基于共同興趣產(chǎn)生的，所以用戶好友的興趣往往和用戶興趣并不一致。

［1］http：//blog.nielsen.com/nielsenwire/consumer/globe-advertising-consumers-trustreal-friends-and-virtual-strangers-the-most/[OL].

［2］項亮.推薦系統(tǒng)實踐[M].人民郵電出版社，2012，6.

［3］Fouss Francois，Pirotte Alain.Random-walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation [J].IEEE Transactions on Knowledge and Data Engineering，2007.

［4］http：//www.infoq.com/news/2009/06/Twitter-Architecture[OL].

［5］MaayanRoth，AssafBen-David.Suggesting Friends Using the Implicit Social Graph[J].ACM 2010.