王雪婷，黃文亮

(河海大學(xué)計算機與信息學(xué)院，江蘇 南京 211100)

0 引言

隨著近十年來Web 2.0技術(shù)的發(fā)展與普及，人們的日常生活越來越受到社會網(wǎng)絡(luò)的影響。社會網(wǎng)絡(luò)不僅僅是人們通常說的社會性網(wǎng)絡(luò)服務(wù)，凡是能夠連接人與人的媒介，都可以稱為社會網(wǎng)絡(luò)，其中以Facebook、Twitter、新浪微博、人人等為代表，吸引了眾多人的眼球。根據(jù)尼爾森2010年的報告，用戶在互聯(lián)網(wǎng)上近22%的時間花費在社會網(wǎng)站和社交媒體上。雖然現(xiàn)在社會網(wǎng)絡(luò)已成為互聯(lián)網(wǎng)上最熱門的應(yīng)用，擁有龐大的流量和海量的數(shù)據(jù)，但是如何從中盡可能多地提取出對用戶有意義的信息仍然是一個非常巨大的挑戰(zhàn)。將推薦系統(tǒng)技術(shù)與社會網(wǎng)絡(luò)相結(jié)合，利用推薦技術(shù)解決社會信息過載的問題成為科研工作者的研究熱點［1］。本文正是在這樣的研究背景下，通過利用社會網(wǎng)絡(luò)信息對用戶建模來產(chǎn)生推薦。

1 相關(guān)工作

1.1 問題描述

在社會標(biāo)注系統(tǒng)中，如何向用戶推薦項的問題，主要利用社會標(biāo)注系統(tǒng)中的2類數(shù)據(jù)［2-3］:用戶之間的朋友關(guān)系數(shù)據(jù)、用戶對項的所打的標(biāo)簽數(shù)據(jù)。

用戶之間的關(guān)系可以用矩陣表示，當(dāng)矩陣中值為1時表示用戶之間有朋友關(guān)系，如表1所示。用戶對項的所打的標(biāo)簽數(shù)據(jù)可以用三元組＜用戶、項、標(biāo)簽＞來表示，將該數(shù)據(jù)表示成三維張量的形式，本文將三維矩陣分別映射到二維平面上，得到＜用戶、項＞＜用戶、標(biāo)簽＞＜項、標(biāo)簽＞3個二維矩陣。這里用表2表示，其中橫軸Um表示用戶m、縱軸In表示項n、矩陣中的值Tmn表示用戶m對項n所打標(biāo)簽的集合。

本文基于以上數(shù)據(jù)，針對推薦技術(shù)如何與社會網(wǎng)絡(luò)應(yīng)用結(jié)合的問題，分析社會網(wǎng)絡(luò)中的用戶、標(biāo)簽、項之間的關(guān)系，以及如何利用用戶間及用戶與項之間的關(guān)系進行社會化推薦。在表3中，給出了本文需要使用的縮寫和概念。

表1 用戶-朋友矩陣

表2 用戶-項-標(biāo)簽矩陣

表3 概念和描述

1.2 用戶標(biāo)記數(shù)據(jù)預(yù)處理

傳統(tǒng)協(xié)同過濾推薦系統(tǒng)的標(biāo)簽數(shù)據(jù)集存在如下缺陷:二值評分矩陣不能提供足夠的有效信息。如表1所示，用戶僅對喜歡的項做標(biāo)記(標(biāo)為1)，不能很好地表示用戶的喜惡。文獻［4］提出了一種利用標(biāo)簽數(shù)據(jù)平滑評分矩陣的方法，利用標(biāo)簽數(shù)據(jù)平滑評分矩陣中的0－1值是更具有表達力的實數(shù)值。

文獻［4］給出了2個參數(shù)來平滑數(shù)據(jù):置信度(saving confidence)和似然度(saving likelihood)。似然度用來估計用戶標(biāo)記項的概率，置信度反映了這種似然的可靠程度。最終用戶u標(biāo)記項i的概率pu，i表示為置信度 cu，i和似然度 lu，i的乘積，如公式(1):

則用戶對項的似然度如公式(2):

其中，p(i|t)表示用戶使用標(biāo)簽t時，項為i的概率。

利用公式(3)可計算出用戶-項的概率矩陣，即利用該矩陣進行項的推薦。本文將該過程作為對標(biāo)記矩陣的預(yù)處理，用于社會正則化模型。

1.3 用戶相似度計算

大多數(shù)基于標(biāo)簽的推薦系統(tǒng)都是統(tǒng)計用戶-標(biāo)簽共同出現(xiàn)的次數(shù)來表示用戶對該標(biāo)簽的權(quán)重。但是，這種不考慮用戶對項所打標(biāo)簽數(shù)目的方法是不公平的。本文提出一種標(biāo)簽加權(quán)方法，如公式(4):

其中，Sut表示用戶u中標(biāo)簽t的權(quán)重，Mui表示用戶u對項i所打標(biāo)簽集合，|Mui|表示用戶u對項i所打標(biāo)簽數(shù)。對于該加權(quán)方法的形式化描述為:對于目標(biāo)用戶u，需要計算其對標(biāo)簽t的權(quán)重。

綜上給出結(jié)合平滑后的用戶-標(biāo)記矩陣和經(jīng)過加權(quán)后的用戶-標(biāo)簽矩陣來計算用戶間相似度的方法。計算公式如下:

其中，vss(x，y)用來計算向量x、y之間的相似度或相關(guān)性，本文使用余弦距離作為向量間相似度的度量方法［5］。vss(Ri'，Rj')表示平滑后的用戶標(biāo)記向量之間的余弦距離，vss(Si'，Sj')表示加權(quán)后的用戶標(biāo)簽向量余弦距離。

1.4 用戶-項關(guān)聯(lián)度計算

傳統(tǒng)協(xié)同過濾算法中，利用評分矩陣可以很方便地計算用戶之間、項之間的相似度，而對用戶和項之間的相關(guān)性往往無法評估。本文提出一種用戶和項關(guān)聯(lián)度的計算策略:將用戶、項同時映射到標(biāo)簽空間，在標(biāo)簽空間中利用公式(6)來計算它們之間的關(guān)聯(lián)度:

其中，Su為利用上文中所述進行標(biāo)簽加權(quán)后的用戶-標(biāo)簽矩陣中用戶u的標(biāo)簽向量。這里對項-標(biāo)簽矩陣Ti也進行標(biāo)簽權(quán)值的計算，具體如公式(7):

其中，Tit表示項i中標(biāo)簽t的權(quán)重，Mui表示用戶u對項i所打標(biāo)簽集合，|Mui|表示用戶u對項i所打標(biāo)簽數(shù)。對于該加權(quán)方法的形式化描述為:對于目標(biāo)項i，需要計算其對標(biāo)簽t的權(quán)重。

2 基于社會正則化的推薦模型

文獻［6］提出了一種融合朋友關(guān)系的社會正則化模型，該模型利用朋友關(guān)系來約束矩陣分解中用戶特征向量。本文基于該思路，提出在社會標(biāo)注框架下的社會正則化模型，該模型不僅考慮用戶間的朋友關(guān)系，并且將用戶和項的關(guān)系融入模型中以提高推薦的精確度。

2.1 基于平均的社會正則化

在現(xiàn)實世界中，當(dāng)無法決定該看什么電影或該去什么地方的游玩時，人們常常尋求朋友的意見。有時會咨詢很多朋友，然后綜合朋友們的建議來做決定。通常人們傾向于與自己有相同愛好或品味的朋友，以及在需要咨詢的問題上較有權(quán)威的朋友。

基于以上觀點，本文采用如下矩陣分解模型［7-10］:

其中，Rij表示訓(xùn)練集中用戶i對項j有評分;Ui表示用戶i的特征向量，Vj表示項j的特征向量;‖.表示Frobenius norm，α為模型參數(shù)，值大于0;F(i)表示用戶i的朋友列表。

上述目標(biāo)函數(shù)中引入了社會正則化項為:

其中，l(j，f)表示項j與用戶f的關(guān)聯(lián)度，該關(guān)聯(lián)函數(shù)可以讓正則化項對于不同項區(qū)別對待用戶的朋友。

這種正則化方法的潛在假設(shè)為:每個用戶的愛好接近他所有朋友愛好的平均。但在現(xiàn)實生活中，這種情況往往是不成立的。因此，本文在上述模型的基礎(chǔ)上加上用戶間的相似度來區(qū)別對待用戶的朋友，目標(biāo)函數(shù)以及式中的社會正則化項可以改為以下公式:

其中，S(i，f)表示用戶i與用戶f的相似度，該相似函數(shù)可以讓正則化項區(qū)別地對待用戶的朋友。

2.2 基于個體的社會正則化

在上文中提出的社會正則化矩陣分解模型中，用戶的愛好被限定為接近他所有朋友愛好的均值。但是，如果某個用戶的朋友的愛好分布很分散，那么就會出現(xiàn)信息丟失以導(dǎo)致模型不準(zhǔn)確。于是，本節(jié)提出一種基于個體的社會正則化方法，代替上文中所述的批量式正則化方法，采用增量式的正則化方法。正則化項公式如下:

其中，α ＞0，β ＞0，l(j，f)表示項 j與用戶 f的關(guān)聯(lián)度，S(i，f)表示用戶i與用戶f的相似度。于是，基于個體的社會正則化矩陣分解的目標(biāo)函數(shù)如下式:

本文將社會正則化目標(biāo)函數(shù)的優(yōu)化算法命名為OPT_SR算法，該算法中需要優(yōu)化的目標(biāo)函數(shù)如公式(10)和公式(13)所示。利用梯度下降法［11-13］尋找用戶和項的特征向量，R、α、β、L、S|U|×|U|、l|U|×|V|作為輸入數(shù)據(jù)，U|U|×ku，V|V|×kv作為輸出數(shù)據(jù)。其中:

(1)R為通過公式(1)平滑后的用戶-項矩陣;

(2)L為需要優(yōu)化的目標(biāo)函數(shù)，如公式(10)和公式(13);

(3)α、β為正則化參數(shù)，如公式(10)和公式(13);

(4)S|U|×|U|為通過公式(5)計算出的用戶相似度;

(5)l|U|×|V|為通過公式(6)計算出的用戶、項的關(guān)聯(lián)度;

(6)U|U|×ku、V|V|×kv為算法需要學(xué)習(xí)的用戶、項特征空間向量。其中，|U|為用戶數(shù)，|V|為項數(shù)，ku、kv分別為用戶、項的特征維度。

3 實驗結(jié)果及分析

本文所使用的數(shù)據(jù)集來自于社會標(biāo)簽網(wǎng)站Delicious系統(tǒng)，該數(shù)據(jù)集包含社會網(wǎng)絡(luò)信息、書簽(項)信息、標(biāo)簽信息。社會網(wǎng)絡(luò)信息包含1867個用戶之間的15328條的連接關(guān)系，數(shù)據(jù)稀疏度為0.4398%。用戶標(biāo)記信息包含64305條標(biāo)簽名、69225條項信息、1867個用戶信息、437593條標(biāo)記信息(＜用戶、項、標(biāo)簽＞為一條標(biāo)記信息)。

在實驗評價中，本文采用精度(precision)、召回率(recall)等評價指標(biāo)來衡量上文所述模型的推薦質(zhì)量的優(yōu)劣。對于用戶u，令Ru為給定用戶u的長度為N的推薦列表，該表包含用戶會打標(biāo)簽的項。令Tu為用戶實際上打過標(biāo)簽的項集，則準(zhǔn)確率、召回率分別表示如下:

在實驗評價中，筆者采用 P-1、P-3、P-5、R-5這幾種評價指標(biāo)，分別定義為:向用戶推薦1個項時系統(tǒng)的準(zhǔn)確率值、向用戶推薦3個項時系統(tǒng)的準(zhǔn)確率值、向用戶推薦5個項時系統(tǒng)的準(zhǔn)確率值、向用戶推薦5個項時系統(tǒng)的召回率值。

本文選擇進行以下3組實驗:

(1)最熱門推薦算法。該算法流程為:統(tǒng)計每個用戶最常用的標(biāo)簽;對于每個標(biāo)簽，統(tǒng)計具有這些標(biāo)簽最熱門的項;對于目標(biāo)用戶，首先找到他最常用的標(biāo)簽，然后找到具有這些標(biāo)簽的最熱門項推薦給用戶。這里“熱門”利用上文所述的用戶-標(biāo)簽權(quán)重算法和項-標(biāo)簽權(quán)重算法來計算。

(2)傳統(tǒng)的協(xié)同過濾推薦算法［14］，本文使用基于用戶相似度的協(xié)同過濾推薦算法。這里用戶間的相似度計算方法利用上文中所述的基于用戶-項和用戶-標(biāo)簽相似度計算的加權(quán)方法。當(dāng)用戶間的相似度高時，表示他們擁有更多相同的愛好。

(3)基于社會正則化的推薦算法，即本文提出的2種算法:基于平均的正則化以及基于個人的正則化。如上文所述:首先將用戶-項矩陣進行數(shù)據(jù)預(yù)處理，并利用用戶-項-標(biāo)簽之間的三元關(guān)系計算出用戶和項的關(guān)聯(lián)度及用戶間的相似度。然后將以上數(shù)據(jù)融入到社會正則化模型中，計算出用戶和項的特征空間向量。最后，利用用戶和項在特征空間中的低維表示進行內(nèi)積計算出用戶對項的感興趣程度進行推薦。

利用 Pop、UCF、SR-avg-k、SR-p-k 分別表示上述的方法:最熱門推薦算法、傳統(tǒng)協(xié)同過濾推薦算法、基于平均的正則化算法、基于個人的正則化算法。其中SR-avg-k、SR-p-k中的k值表示用戶、項的特征空間維度值。

上述4種算法的評價指標(biāo)的情況如表4所示。

表4 4種推薦算法精度對比

表4顯示的是4種推薦算法的P-1、P-3、P-5、R-5指標(biāo)的值，可以很直觀地看出本文所提出的社會正則化算法在各項指標(biāo)上取得較好的結(jié)果，改進后的推薦算法的精度高于傳統(tǒng)推薦算法的精度。

基于社會網(wǎng)絡(luò)的推薦系統(tǒng)主要解決的問題是社會信息的過載，通過推薦算法的精確度證明了本文提出的基于社會正則化的社會化推薦模型可用來解決社會信息冗余問題。

4 結(jié)束語

本文主要介紹利用社會網(wǎng)絡(luò)中的朋友關(guān)系等社會化信息進行推薦的社會正則化方法，首先利用標(biāo)簽信息平滑數(shù)據(jù)，然后利用用戶-項矩陣及用戶-標(biāo)簽矩陣進行用戶相似度計算，最后本文提出一種基于社會正則化的推薦算法，建立相應(yīng)的模型，然后將用戶之間的相似度信息及用戶與項之間的關(guān)聯(lián)度信息融入到傳統(tǒng)的矩陣分解模型中。實驗結(jié)果表明，該算法有效地提高了推薦算法的準(zhǔn)確率，使得社會化推薦系統(tǒng)較之傳統(tǒng)的推薦系統(tǒng)具有更好的推薦效果。

［1］Resnick P，Iacovou N，Suchak M，et al.GroupLens:An open architecture for collaborative filtering of netnews［C］//Proceedings of the 1994 ACM Conference on Computer Supported Cooperative Work.1994:175-186.

［2］Tso-SutterK H L，Marinho L B，Schmidt-Thieme L.Tagaware recommender systems by fusion of collaborative filtering algorithms［C］//Proceedings of the ACM Symposium on Applied Computing.2008:1995-1999.

［3］Marinho L B，Schmidt-Thieme L.Collaborative tag recommendations［C］//Data Analysis，Machine Learning and Applications.Springer Berlin Heidelberg，2008:533-540.

［4］Peng J，Zeng D.Topic-based Web page recommendation using tags［C］//IEEE International Conference on Intelligence and Security Informatics(ISI’09).2009:269-271.

［5］Kenney J F，Keeping E S.Mathematics of Statistics，Part 2［M］.Van Nostrand，1947.

［6］Ma H，Zhou D，Liu C，et al.Recommender systems with social regularization［C］//Proceedings of the Fourth ACM International Conference on Web Search and Data Mining.2011:287-296.

［7］Nguyen J，Zhu M.Content-boosted matrix factorization techniques for recommender systems［J］.Statistical Analysis and Data Mining，2013，6:286-301.

［8］Koren Y.Collaborative filtering with temporal dynamics［C］//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2009:447-456.

［9］Koren Y，Bell R，Volinsky C.Matrix factorization techniques for recommender systems［J］.Computer，2009，42(8):30-37.

［10］Rennie J D M，Srebro N.Fast maximum margin matrix factorization for collaborative prediction［C］//Proceedings of the 22nd International Conference on Machine Learning.2005:713-719.

［11］阿佛里耳(M·Avriel).非線性規(guī)劃:分析與方法［M］.李元熹，等譯.上海:上?？茖W(xué)技術(shù)出版社，1979.

［12］Jan A Snyman.Practical Mathematical Optimization:An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms［M］.Springer-Verlag New York Inc.，2005.

［13］劉穎超，張紀元.梯度下降法［J］.南京理工大學(xué)學(xué)報:自然科學(xué)版，1993(2):12-16，22.

［14］Adomavicius G，Tuzhilin A.Toward the next generation of recommender systems:A survey of the state-of-the-art and possible extensions［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17(6):734-749.