一種基于用戶反饋的時間感知推薦方法

邢 星 ，賈志淳 ，2，楊玉強

1.渤海大學 信息科學與技術學院，遼寧 錦州 121013

2.美國新墨西哥大學 計算機科學系，美國 87131

1 引言

社交網(wǎng)絡中的用戶興趣信息會隨著時間發(fā)生變化，用戶之間的朋友關系也隨著時間的變化而變化。社交網(wǎng)絡是在不斷演化的，用戶興趣也是不斷變化的，如何為社交網(wǎng)絡中的個人用戶提供即時感興趣的項目推薦成為社交網(wǎng)絡推薦方法研究的新要求和新挑戰(zhàn)[1-2]。傳統(tǒng)的推薦方法只考慮用戶是否點擊了項目，對項目是否感興趣，并沒有考慮用戶點擊項目的時間因素[3-4]。因此，在實際的社交網(wǎng)絡推薦場景中，如果時間因素對用戶興趣影響較大，那么傳統(tǒng)的推薦方法無法為社交網(wǎng)絡用戶提供高質(zhì)量的推薦[5]。

上下文背景信息（context information）中除了時間因素，用戶的反饋信息也可以用來提高推薦方法的推薦質(zhì)量[2，6-7]。傳統(tǒng)的推薦方法只考慮用戶的正反饋信息，即用戶─項目的點擊數(shù)據(jù)[8]。另一類反饋信息，如推薦系統(tǒng)推薦給用戶的項目中，用戶沒有點擊的項目，這類反饋信息稱為負反饋信息。負反饋信息從另一個方面反映了用戶的興趣，也可以用來分析用戶興趣偏好。將負反饋信任融入到基于用戶興趣的推薦方法中，提高社交網(wǎng)絡推薦方法的推薦質(zhì)量[9]。

針對上述問題，本文提出一種基于用戶反饋時間感知推薦方法。通過對社交網(wǎng)絡的動態(tài)性建模，將時間因素引入到社交興趣網(wǎng)絡中。將用戶反饋信息建模為正反饋信息和負反饋信息，建立用戶興趣的時間衰變函數(shù)刻畫用戶興趣變化隨時間衰減的影響，綜合利用兩種反饋信息和用戶興趣衰變函數(shù)建立用戶興趣的動態(tài)模型。根據(jù)用戶興趣的動態(tài)模型為社交網(wǎng)絡中用戶提供時間感知的推薦。

2 社交網(wǎng)絡和用戶反饋表示

在社交網(wǎng)絡推薦方法研究和應用領域，人們只關注挖掘用戶與項目之間的二元關系[10]，較少考慮用戶與項目所處的上下文背景信息，如時間、社交網(wǎng)絡朋友關系、用戶反饋等信息[11-14]。但是，在許多應用場景下，僅僅依靠用戶與項目之間的二元關系并不能生成有效推薦[15-16]。

為了考慮時間因素對社交網(wǎng)絡推薦方法的影響，首先給出動態(tài)社交網(wǎng)絡的形式化表示。

定義1（動態(tài)社交網(wǎng)絡）給定目標用戶u，動態(tài)社交網(wǎng)絡可以表示為GS=(V,follow,T,u)，其中，

（1）V是動態(tài)社交網(wǎng)絡中用戶U={u1,u2,…,un}結點的非空有限集合；

（2）follow?U×U，是用戶─用戶的關注關系，代表社交網(wǎng)絡的朋友關系代表社交網(wǎng)絡中的關注關系（followship）；

（3）T代表社交網(wǎng)絡中用戶之間建立關注關系的時間集合。

動態(tài)社交網(wǎng)絡Gs與傳統(tǒng)社交網(wǎng)絡G的定義不同之處在于動態(tài)社交網(wǎng)絡考慮了關注關系建立的時間。在此基礎上，給定時間t和目標用戶u，定義社交網(wǎng)絡中朋友（被關注者）集合：

其中，tu,u′是目標用戶u關注用戶u′的時間。

當推薦系統(tǒng)為用戶推薦項目時，記錄了用戶點擊的項目，同時也記錄了推薦列表中用戶沒有點擊的項目。一方面，用戶點擊的項目反映了用戶興趣偏好，可以直接用來計算用戶興趣的相似度。另一方面，用戶沒有點擊的項目也反映了用戶的興趣，也可以用來分析用戶興趣偏好。將這類數(shù)據(jù)融入到基于用戶興趣的推薦方法中，通過分析反饋信息準確刻畫用戶興趣偏好，可以進一步提供推薦方法的推薦質(zhì)量。

根據(jù)用戶是否點擊推薦項目，將用戶反饋信息分為兩類：正反饋信息和負反饋信息，定義表示如下：

定義2（正反饋表示）給定目標用戶u，正反饋可以表示為圖的形式G+=(V,click,T,u)，其中，

（1）V=I∪U代表結點的非空有限集合，I={i1,i2,…,im}代表社交網(wǎng)絡中的項目集合，U={u1,u2,…,un}代表用戶集合。

（2）click?U×I是用戶─項目的點擊關系，代表用戶的正反饋信息。

（3）T代表用戶點擊項目的時間集合。

給定時間t和G+，目標用戶u點擊的項目集合可以表示如下形式：

其中，tu,i是目標用戶u點擊項目i的時間。

定義3（負反饋表示）給定目標用戶u，負反饋可以表示為圖的形式G-=(V,unclick,T,u)，其中，

（1）V=I∪U代表結點的非空有限集合，I={i1,i2,…,im}代表社交網(wǎng)絡中的項目集合，U={u1,u2,…,un}代表用戶集合。

（2）unclick?U×I指在推薦給用戶項目時候，用戶沒有選擇點擊的推薦項目，代表用戶的負反饋信息。

（3）T代表用項目推薦給用戶但是沒有被用戶點擊的時間集合。

與式（2）的定義相似，在給定時間t和G-的情況下，目標用戶u沒有點擊的項目集合定義如下：

其中，tu,i是目標用戶u沒有選擇點擊項目i的時間。

式（2）和式（3）分別計算目標用戶在給定時間內(nèi)的正反饋信息和負反饋信息，兩者從兩個不同方面反映了用戶在特定時間的興趣。結合用戶的正反饋和負反饋信息，定義用戶的推薦項目集合如下：

其中，I+(u,t)由式（2）計算得到，I-(u,t)由式（3）計算得到。

最后，定義基于時間感知和用戶反饋的社交網(wǎng)絡項目推薦的目標函數(shù)F如下：

其中，i∈Irec(u,t),u∈U 。

目標函數(shù)F通過對社交網(wǎng)絡中影響目標用戶點擊推薦項目的正反饋信息，負反饋信息和時間因素進行分析，將基于目標用戶u上下文背景信息生成的推薦項目映射到實數(shù)范圍，根據(jù)目標函數(shù)的函數(shù)值大小來預測目標用戶對推薦項目的喜好程度。

3 基于用戶反饋時間感知推薦方法

3.1 基于用戶反饋的相似度計算

在傳統(tǒng)的推薦方法中，用戶之間的相似度是分析用戶之間點擊相同項目的個數(shù)和用戶分別點擊項目的個數(shù)計算而得到的[3]，計算公式如下：

其中，I(u)代表用戶u點擊的項目集合，I(u′)代表用戶u′點擊的項目集合。

為了將時間因素和用戶反饋信任融入到推薦方法中，擴展式（6）的用戶相似度計算方法。給定時間t，用戶之間的相似度計算公式如下所示：

t′u,i是用戶u沒有選擇點擊推薦項目i的時間；同樣地，t′u′,i是用戶u′沒有選擇點擊推薦項目i的時間，且滿足t′u,i≤t，t′u′,i≤t。

weight(tu,i-tu′,i)是時間加權函數(shù)，值域為[0，1]；通過對用戶u和用戶u′點擊項目i的不同時間間隔加權，刻畫時間因素對推薦方法的影響。

α是調(diào)和參數(shù)，將用戶的正反饋信息和負反饋信息對用戶相似度的影響調(diào)和在一起，參數(shù)α的取值通過實驗得到。

在式（7）中，如果將參數(shù)設為α=1，那么只有用戶的正反饋信息起作用，影響用戶的相似度計算。

用戶對項目的選擇是有時間效應的。一般情況下，用戶對最近選擇的東西比較感興趣，而會忽視很早以前選擇的東西，不同時間下的用戶的項目選擇信息對推薦預測的貢獻是不一樣的。

應用文獻[17]中的時間加權方法計算時間因素對用戶興趣的影響。令Δt=tu,i-tu′,i表示用戶u和用戶u′點擊項目i的時間間隔，時間加權函數(shù)定義為：

其中，λ是時間衰變參數(shù)，控制著用戶興趣衰變的速率。

式（8）定義的時間加權函數(shù)在Δt≥0的條件下，是一個單調(diào)遞減函數(shù)，在Δt=0的時候，函數(shù)取最大值1，在Δt→+∞的時候，函數(shù)取最小值0。

參數(shù)λ控制時間加權函數(shù)函數(shù)值曲線下降的速率，λ的值越大，曲線下降的越快。這符合用戶興趣時間因素加權的要求：時間間隔較近的用戶點擊行為對項目的推薦作用獲得較高的貢獻度。同樣用式（8）分析用戶沒有選擇推薦項目數(shù)據(jù)對項目推薦結果帶來的影響。

3.2 推薦算法

基于時間感知和用戶反饋的推薦算法如下所示，其中，參數(shù)α和λ需要通過實驗分析確定參數(shù)的最優(yōu)值。

算法1基于時間感知和用戶反饋的推薦算法

通過上面的分析，利用社交網(wǎng)絡目標用戶鄰居節(jié)點的項目點擊信息來預測目標用戶未來點擊項目的概率，求解式（5）中推薦任務的目標函數(shù)F。

4 實驗

4.1 數(shù)據(jù)來源

應用新浪微博所提供的數(shù)據(jù)訪問接口抽取推薦數(shù)據(jù)，通過記錄用戶推薦項目列表和用戶點擊的推薦項目計算用戶反饋信息。抽取到數(shù)據(jù)的時間跨度從2011年10月12日到2011年11月12日，共計744個小時的數(shù)據(jù)。數(shù)據(jù)集中共有6 101個用戶，2 343個項目，954 015條帶時間信息的用戶-項目點擊日志記錄（user-item clicked log），1 203 421條用戶沒有選擇點擊推薦項目的日志記錄（user-item unclick log），132 747個關注關系。

4.2 實驗設置

將數(shù)據(jù)集劃分為訓練集和測試集，在訓練集上訓練基于時間感知和用戶反饋的推薦方法中的參數(shù)，在測試集上評估提出推薦方法的推薦質(zhì)量。時間采樣窗口設置為1小時，共采樣745次。

采用下面兩個常用的評價指標來評估基于用戶反饋的時間感知推薦方法的推薦質(zhì)量：

（1）前k個推薦項目的平均準確率AP@k。

（2）前k個推薦項目平均準確率的平均值MAP。

其中，將k分別設置為k=5，k=10，k=15和k=20。

對比實驗中的基線方法（Baseline）采用基于項目的推薦方法（item-based recommendation method）。如文獻[4]中所示，項目i和項目j之間的相似度sim(i,j)計算如下：

其中，U(i)代表點擊項目i的用戶集合，U(j)代表點擊項目j的用戶集合。

4.3 推薦質(zhì)量與分析

圖1給出了參數(shù)λ和α的不同設置對前k個推薦項目平均準確率的平均值MAP值。實驗結果表明，當α=0.8且λ=0.005時，基于時間感知和用戶反饋推薦方法的推薦質(zhì)量最高，前k個推薦項目平均準確率的平均值MAP為0.243 5。因此，將參數(shù)α設定為0.8，進行下面的對比實驗。

圖1 參數(shù)λ和α的不同設置對推薦質(zhì)量的影響

將參數(shù)λ設置為0.5，0.01和0.005，評價不同參數(shù)λ設置對基于時間感知和用戶反饋的推薦方法帶來的影響，將該方法與基線方法（baseline）做比較，實驗結果如圖2所示?；€方法的前k個推薦項目平均準確率的平均值MAP為0.170 5。當λ=0.005時，基于時間感知和用戶反饋的推薦方法的MAP取值最大，為0.243 5。與基線方法相比，基于時間感知和用戶反饋的推薦方法在前k個推薦項目平均準確率的平均值MAP上提高了近30%。

圖2 不同參數(shù)λ對推薦質(zhì)量的影響

此外，參數(shù)λ也影響基于時間感知推薦方法的推薦質(zhì)量，當λ=0.5時，推薦方法前k個推薦項目平均準確率的平均值為0.167 6，這個值比基線方法的0.170 5要低。因此，合適的參數(shù)選取對基于用戶反饋的時間感知推薦方法而言至關重要，直接關系到推薦方法的推薦質(zhì)量。

5 結束語

本文給出了動態(tài)社交網(wǎng)絡項目推薦問題的定義，將用戶反饋形式化表示為正反饋信息和負反饋信息。通過擴展用戶相似度計算方法，將時間因素，用戶反饋信息等影響推薦質(zhì)量的上下文信息融入到推薦方法中。應用時間加權函數(shù)刻畫時間因素對用戶興趣的影響，使時間間隔較近的用戶點擊行為對項目的推薦作用獲得較高的貢獻度，充分體現(xiàn)用戶興趣的時間效應特性。對社交網(wǎng)絡中鄰居節(jié)點點擊的項目來預測目標用戶未來點擊的項目，構建基于用戶反饋的時間感知推薦方法。數(shù)據(jù)來源于新浪微博中抽取到的實際數(shù)據(jù)，實驗表明通過選擇合適的參數(shù)，基于用戶反饋的時間感知推薦方法可以顯著提高推薦質(zhì)量。

[1]Biancalana C，Gasparetti F，Micarelli A，et al.An approach to social recommendation for context-aware mobile services[J].ACM Trans on Intell Syst Technol，2013，4（1）：1-31.

[2]Yang Xiwang，Steck H，Guo Yang，et al.On top-krecommendation using social networks[C]//Proceedings of the Sixth ACM Conference on Recommender Systems，2012：67-74.

[3]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.

[4]Deshpande M，Karypis G.Item-based top-n recommendation algorithms[J].ACM Transactions on Information Systems，2004，22（1）：143-177.

[5]王立才，孟祥武，張玉潔.上下文感知推薦系統(tǒng)[J].軟件學報，2012，23（1）：1-20.

[6]Yang Shuanghong，Long Bo，Smola A J，et al.Collaborative competitive filtering：learning recommender using context of user choice[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval，2011：295-304.

[7]Bakshy E，Hofman J M，Mason W A，et al.Everyone’s an influencer：quantifying influence on twitter[C]//Proceedings of the Fourth ACM International Conference on Web Search and Data Mining，2011：65-74.

[8]Sarwar B，Karypis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C]//Proceedings of the 10th International Conference on World Wide Web，2001：285-295.

[9]Moghaddam S，Jamali M，Ester M，et al.FeedbackTrust：using feedback effects in trust-based recommendation systems[C]//Proceedings of the Third ACM Conference on Recommender Systems，2009：269-272.

[10]吳湖，王永吉，王哲，等.兩階段聯(lián)合聚類協(xié)同過濾算法[J].軟件學報，2010（5）：1042-1054.

[11]Kuter U，Golbeck J.Using probabilistic confidence models for trust inference in web-based social networks[J].ACM Trans on Internet Technol，2010，10（2）：1-23.

[12]Hannon J，Bennett M，Smyth B.Recommending twitter users to follow using content and collaborative filtering approaches[C]//Proceedings of the Fourth ACM Conference on Recommender Systems，2010：199-206.

[13]Guy I，Zwerdling N，Ronen I，et al.Social media recommendation based on people and tags[C]//Proceedings of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval，2010：194-201.

[14]Ma Hao，King I，Lyu M R.Learning to recommend with social trust ensemble[C]//Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval，2009：203-210.

[15]Jahrer M，Toscher A，Legenstein R.Combining predictions for accurate recommender systems[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2010：693-702.

[16]Jamali M，Ester M.A matrix factorization technique with trust propagation for recommendation in social networks[C]//Proceedings of the Fourth ACM Conference on Recommender Systems，2010：135-142.

[17]Ding Yi，Li Xue.Time weight collaborative filtering[C]//Proceedings of the 14th ACM International Conference on Information and Knowledge Management，2005：485-492.