基于用戶簽到行為的群組興趣點推薦模型

陶永才，丁 鑫，石 磊，衛 琳

1(鄭州大學 信息工程學院, 鄭州 450001)

2(鄭州大學 軟件技術學院, 鄭州 450002)

1 引 言

近年來，互聯網的發展促使人們從信息匱乏的時代進入信息過載的時代[1].推薦系統通過挖掘用戶與項目之間的關系，分析用戶的興趣分布，幫助用戶從海量數據中發現符合其興趣的項目，滿足用戶的個性化需求[2].

隨著基于位置的社交網絡的快速發展，為用戶推薦其可能感興趣的地點成為一個研究熱點.現有的推薦系統主要關注如何為單個用戶提供個性化推薦服務，而在實際生活中人們通常是以群組的形式參加各種活動，因此推薦系統更需要考慮如何向群組推薦，使推薦結果能夠滿足群組的需求并使所有群組成員都均衡滿意.除了要準確獲取組內成員的個體偏好外，群組推薦系統還需要考慮如何將多位組員的個體偏好融合為群組偏好[2]，因此偏好融合策略，成為群組推薦研究的關鍵.現有的偏好融合策略都有各自的優點和不足，例如均值策略[3]在組內成員偏好非常相似時得到的聚合效果較好，但如果組內成員的喜好差別很大，那么結果將變得較差.最開心策略將群組成員中的最高評分做為群組評分，但易產生"痛苦"問題.最小痛苦策略能避免"痛苦"問題，但無法解決惡意評分的問題.基于此，本文在GPUC模型中使用一種加權混合融合策略以彌補單一融合策略的不足.考慮到不同的用戶對群組偏好的影響不同，在進行偏好融合時應該為用戶分配不同的權重，GPUC模型根據用戶的活躍度來分配權重.然后根據群組偏好的差異度選擇不同的融合策略.與文獻[5]提出的HAaB算法的對比實驗表明，采用了加權混合融合策略的GPUC模型推薦準確度提高了4.03%.

2 相關工作

2.1 推薦算法

目前常用的推薦算法有基于鄰域的算法，隱語義模型，基于圖的模型，混合推薦算法等.基于鄰域的算法包括基于用戶的協同過濾算法和基于內容的協同過濾算法.基于用戶的協同過濾算法根據用戶評分比較用戶間的相似性，并向目標用戶推薦相似用戶感興趣的項目[16].基于內容的協同過濾算法是從待推薦對象中選擇與用戶已經選擇的對象有相似特征的項目做為推薦結果[17].隱語義模型是一種基于機器學習的方法，通過優化特定的指標建立最優的模型.找到用戶興趣和項目之間的隱含特征聯系.具有較好的理論基礎.推薦系統中常用的模型和方法有LDA模型，隱含類別模型，矩陣分解等.基于圖的模型將用戶和項目的二元關系抽象為圖，將用戶和項目抽象為圖中的點，用戶對項目的行為抽象為邊，利用圖上的算法進行推薦.混合推薦算法是為了彌補單個推薦算法的不足綜合上述方法中的兩種或更多來進行推薦.例如文獻[14]提出的HLB混合推薦算法針對用戶的長短期興趣的差異，對用戶的長期閱讀興趣采用基于內容的協同過濾推薦算法，短期閱讀興趣則采用基于用戶的協同過濾推薦算法[14].

2.2 群組推薦的偏好融合

在進行群組偏好融合時要考慮使用哪種偏好融合方法和融合策略.

群組推薦的偏好融合方法根據融合發生的階段分為：模型融合和推薦融合.模型融合發生在推薦形成之前，首先將群組成員個體偏好模型融合形成群組偏好模型，然后基于群組偏好模型為群組進行推薦.推薦融合則是在組內成員個人推薦生成后，將所有成員的推薦結果根據一定的融合策略進行融合得到群組推薦結果.電影組推薦系統HappyMovie[10]，音樂組推薦系統MusicFX[8]均采用推薦融合方法，而旅游組推薦系統CATS[9]則采用模型融合方法.目前對于具體應該采用哪種偏好融合方法并沒有統一的定論.偏好融合方法的選擇往往是根據實際情況得出的.文獻[13]提出"群組偏好與個人偏好具有相似性"，并利用該結論提出一種改進的偏好融合組推薦方法，將模型融合和推薦融合統一.偏好融合策略則是指將單個組員的個體偏好融合為群組偏好的方法.在實際應用中，為了滿足滿意度、公平性和可理解性等要求，常常會根據不同的情境選擇不同的融合策略.常用的組推薦融合策略有公平策略、均值策略、痛苦避免均值策略、最小痛苦策略、最開心策略.文獻[11]對經典常用的偏好融合策略進行了研究討論.分析了上述策略的優點和不足之處，例如最開心策略可能會引起個別群組成員的不滿，產生所謂的"痛苦"問題；痛苦均值避免策略解決了"痛苦"問題，但其融合策略與閾值的選擇有很大關系.

2.3 群組推薦的研究現狀

群組推薦正受到越來越多的關注.ACM推薦系統大會在2011年以"家庭群組電影推薦"為主題舉辦了推薦挑戰賽[7].旅游組推薦系統CATS[9]、音樂組推薦系統MusicFX[8]是目前存在的典型商業組推薦系統.群組推薦一般包括兩個步驟：一是融合組內成員偏好形成群組偏好；二是根據群組偏好對項目進行預測并生成推薦列表.Fernando Ortega等的研究表明組推薦系統的性能根據群組的大小有所不同，而基于矩陣分解和協同過濾技術的組推薦系統在其實驗數據集上表現最好[4].文獻[6]采用模型融合的方法，基于用戶的社交網絡關系構建群體偏好模型為群組用戶進行視頻推薦，取得了較好的推薦效果.文獻[12]在SVD中加入用戶的社交行為和社交關注關系特征，將其用于個體推薦并通過對個體推薦列表的融合獲取群組推薦.文獻[5]則假定推薦列表是根據用戶評分排列，提出一種列表融合方法HAaB，將均值策略和波達計數結合使用，得到了較好的推薦效果.

3 基于用戶簽到行為的群組興趣點推薦模型

由于推薦融合的方法具有更高的靈活度且推薦結果更易于解釋，GPUC模型采用推薦融合的方法，首先為組內成員進行個體推薦，然后根據加權融合策略融合組員的推薦列表.在進行融合時要考慮到不同組員對群組偏好的影響也不同，例如比較活躍的用戶對群組偏好的影響應該比不活躍的用戶影響大，因此應為不同的用戶分配不同的權重，同時為了彌補傳統偏好融合策略的不足，本文采用一種混合融合策略，根據組內成員偏好的差異度采用不同的融合策略.

圖1為GPUC模型推薦過程的流程圖.

圖1 推薦流程示意圖Fig.1 Recommended flow diagram

1)抓取用戶數據，形成用戶-興趣點簽到頻數矩陣.

2)將矩陣向量化，找到與目標用戶有相似興趣的最近鄰集合，通過基于用戶的協同過濾為目標用戶推薦其可能感興趣的項目.基于TF-IDF的思想預測用戶對推薦項目的評分.從而得到用戶個人推薦列表.

3)通過用戶-興趣點簽到矩陣計算用戶的權重，同時根據用戶個人推薦列表生成群組-推薦地點評分矩陣.根據群組評分的分歧度選取合適的融合策略融合組內成員偏好，并將融合后得分最高的地點推薦給用戶.

3.1 個人推薦列表

1)獲取用戶-興趣點頻數矩陣

為用戶進行推薦首先要獲取用戶的偏好，進行組推薦則首先要獲取組內所有成員的偏好.一般的用戶偏好獲取方法分為顯式獲取和隱式獲取.顯式獲取模式根據用戶對項目的評分獲取用戶偏好.但現實中很難要求用戶對每一個項目都進行評分，因此顯式獲取的方式易出現稀疏性問題.隱式獲取模式則不需要用戶提供偏好信息，而是根據用戶的歷史行為來挖掘用戶偏好.采用隱式獲取用戶興趣的方法更有利于保護用戶的隱私.因此本文采用隱式獲取的方法，提取用戶的歷史簽到記錄，得到以下的用戶-興趣點簽到頻數矩陣.

(1)

其中m表示數據集中的用戶數，n表示數據集中有用戶簽到的興趣點的總數.Vi,j表示第i位用戶在興趣點j處簽到的次數.

2)最近鄰集合

兩個用戶簽到地點越相似則這兩位用戶的興趣分布越相似.矩陣中每一行代表一個用戶的興趣分布，可以表示為向量形式，例如Vi={vi,1,vi,2,…,vi,n-1,vi,n}表示用戶i的興趣分布，則兩位用戶之間的相似度計算如式(2)所示.

(2)

其中sim(ui,uj)表示用戶i和用戶j(i,j=1,2,…,m)之間的相似度.將用戶按照和目標用戶i的相似程度排序，取前K位用戶組成用戶i的最近鄰集合Ni.將K位最近鄰簽過到的興趣點做為目標用戶的待推薦項目.

3)評分預測

基于用戶的簽到信息只能獲取用戶的興趣點和簽到頻次，無法得到用戶對興趣點的評分.TF-IDF是一種評價字詞對文件重要程度的算法，該算法在考慮字詞重要性的同時也兼顧了字詞的普遍性[15].在預測用戶對興趣點的喜好程度時可以借用TF-IDF算法思想：用戶在某一地點簽到次數越多，說明用戶對該地點更感興趣，但若數據集中的用戶在該地點簽到頻數較高則說明對該地點的推薦缺乏新穎性，使用TF-IDF來計算用戶對某一興趣點的喜好程度如式(3)所示.

(3)

其中deg(ui,pa)表示用戶i對興趣點a的喜好程度.n(i,a)表示用戶i在興趣點a處簽到的次數，num(i)表示用戶i簽到總數，Tu表示數據集中用戶的總數，Nu(a)表示在地點a簽過到的用戶數. 對于用戶i簽過到的興趣點可以使用公式(4)得到一個0到1之間的數字做為用戶i對興趣點a的評分.

(4)

其中deg(ui,p)表示用戶i對所有興趣點的平均喜好程度，rat(ui,pa)表示用戶i對興趣點a的評分.

公式(4)可以用于為用戶簽過到的興趣點評分，對于用戶未簽到的地點則使用協同過濾的方法，根據在該地簽過到的最近鄰用戶的評分生成預測評分.如果最近鄰用戶j對興趣點a的評分為rat(uj,pa)，則目標用戶對該地點的評分如式(5)所示.

(5)

對組內用戶推薦過程如算法1所示：

算法1.組內用戶個體推薦算法

輸入：matrix，數據集上用戶-興趣點簽到頻次矩陣；

G，待推薦組用戶集合；

N，計劃推薦給用戶的項目數；

輸出：每個組內用戶的推薦列表.

1.foreach useruiin G

2.calculate similarity betweenuianduj

//利用公式(1)計算兩用戶間的相似度

3. make the first kth users as neighbors[]

4.foreach neighbor in neighbors[]

5.forpain neighbor′s sign-in collection

6. calculate deg(neighbor，pa)

//利用公式(3)

7.if(uihas been signed inpa)

8. rat[a]=rat(ui,pa);

//已簽到地利用公式(4)

9.else

10. rat[a]=rat(ui,pa);

//未簽到地利用公式(5)

11.endif;

12.endfor;

13.endfor

14.sort the rat[] in descending order;

15.while(count!= N){

16.recommend_list[count++]=pj}

17.}

18.end

3.2 偏好融合策略

傳統的偏好融合策略忽略了不同的群組成員對群組偏好的影響，在一個群組中，由于每位成員的活躍度不同，對群組偏好的影響也不同，在進行偏好融合時，活躍度高的用戶的偏好更具有參考價值.基于此，本文考慮根據用戶的活躍度來計算用戶在群組中的權重，而用戶在不同的地方簽到次數越多則說明用戶越活躍，該用戶對群組興趣的影響越大.設計權重的計算如式(6)所示：

(6)

其中w(ui)表示用戶i在群組中的權重.fi表示用戶i簽到總次數，qi表示用戶i成為其他用戶近鄰的次數，由公式(6)可以看出隨著fi，qi的增加，用戶權重也呈現增長趨勢.對兩個參數進行調和則可以全面反應用戶在群組中的權重，對公式(6)進行化簡，得到最終權重公式如式(7)所示.

(7)

融合策略的效果與組內成員偏好差距有關，例如當組內成員偏好差距較小時，均值策略的效果會比較好，但當成員偏好差別較大時均值策略會對評分較少的群組成員產生不公平現象.本文考慮組內成員偏好的差異度同時結合用戶在組內的權重.當群組成員對一個項目的評分差異較小時，采用加權均值策略，取群組成員對該項目的加權平均分做為群組評分.當群組成員對一個項目的評分差異較大時采用最尊者策略，權重最大的組員即為最尊者，將最尊者的評分作為群組評分.加權混合融合策略的評分計算如式(8)所示.

(8)

其中rat(ui,pa)表示用戶i對推薦地點a的評分，diff(pa)表示群組用戶對待推薦地點a評分的分歧程度.分歧方差計算如式(9)所示.

(9)

其中ave(G,pa)是群組中的用戶對待推薦地點a預測評分的平均值.

基于加權混合融合策略的群組推薦過程如算法2所示：

算法2.群組推薦算法

輸入：matrix，數據集上用戶-簽到頻數矩陣；

Vi，群組用戶-推薦集合評分矩陣；

G, 組用戶集合；

輸出：群組推薦結果.

1.foreach useruiin G

2. calculate weight w(ui)

3.endfor

4.foreachpainvi

5. if(diff(pa)>α)

6. for(i in G)

7. {

8. if(w(i) is the most weighted)

9. GR[j]=rat(ui,pa)

10. }

11. else if(diff(pa)<α)

12. GR[j]=average(G,pj)

13.endfor

14.sort the GR[j] in descending order;

15.make the GR[0] as recommendation result

16.end

4 實 驗

4.1 實驗數據集

Gowalla是著名的基于位置的社交網絡站點，為用戶提供了基于位置的簽到服務，本文采用的數據集1是由斯坦福大學的研究學者通過Gowalla網站的公共接口獲取的.數據集共包含兩個文件，分別記錄簽到信息和用戶關系信息，均以txt文件格式存放.簽到記錄中共收集了6442890個簽到記錄，每個基本數據項包含用戶ID、簽到時間、簽到經緯度、簽到地點ID等數據項.在選擇用戶組時首先將兩份文件導入數據庫并利用用戶ID將兩表連接，過濾掉簽到頻數過低或朋友關系過少的用戶.最后將數據集按照8：2的比例劃分為訓練集和測試集.

4.2 算法評價標準

基于用戶簽到行為的群組興趣點推薦分為個體推薦和群組推薦兩步.

準確率和召回率是TOP-N推薦的重要評價標準.在興趣點的推薦中，準確率表示在推薦給用戶的項目中，用戶簽到的地點數占推薦數量的比例.召回率是用戶簽到的興趣點中被推薦地點所占的比率.F值是準確率和召回率的調和平均值.本文利用F值來度量個體推薦結果的精確度.對于用戶u，令Ru作為模型推薦的地點集合,Tu作為測試集中用戶u簽到的地點的集合,其推薦準確率P、召回率R、以及F值的計算分別為:

(10)

(11)

(12)

而群組通常是由多個個體組成的，一位成員的選擇不能代表群組的選擇，因此上述評價標準不適用于對群組推薦效果的評價.而RMSE(平方根誤差)通過計算預測評分與真實評分之間的誤差來評價推薦系統的推薦效果.本文將RMSE改進后做為群組推薦結果的評價標準.群組推薦評價標準RMSE計算公式如式(13)所示.

(13)

其中r(ui,pa)表示用戶i對推薦地點a的評分,G(pa)表示群組G對推薦地點a的評分.N表示該組用戶在推薦地點a簽到總次數，Gn代表群組成員個數.

4.3 實驗方案

實驗設置情況如下：

1) 比較不同的相似鄰居個數k的值對個體推薦準確率的影響.

2) 調整差異度閾值α使推薦效果達到最優.

3) 將加權混合融合策略的推薦效果與其它融合策略的推薦效果進行比較.

4.3.1 相似鄰居個數

為了使群組推薦效果達到最優，要盡可能準確的獲取組內成員的個人偏好.而對個體用戶進行協同過濾推薦時，相似的鄰居個數k的值對推薦結果有一定的影響，實驗對比了不同的k值對個體推薦結果準確率的影響.結果如圖2所示.由圖2可以看出在實驗數據集上，當鄰居個數k的值為15，推薦個數為20時，推薦的準確率最高.

4.3.2 差異度閾值α

差異度閾值α影響著融合策略的選擇，實驗以7人群組為推薦對象，每次實驗分別設置不同的α值，對推薦結果進行評價，實驗結果如表1所示.由表1可以看出當差異度閾值取0.4時，推薦精度更高.

1http://snap.standford.edu/data/loc-gowalla.html

圖2 用戶鄰居數對個人推薦準確率的影響Fig.2 Precision of different numbers of neighbors

表1 不同差異度閾值α的實驗結果表Table 1 Result of different threshold α

為了得到本文提出的加權混合融合策略的最佳條件，反復調整群組規模和差異度閾值α，實驗結果如圖3所示.由圖3可以看出根據群組大小不同，α的取值也應該有所不同，在群組人數較少時，α取較小的值可以提高推薦質量，而當群組規模較大時，閾值α也應該適當增大.實驗結果表明在Gowalla數據集上，當目標群組人數為7，差異度閾值α取0.4時，推薦效果最好.

圖3 不同群組人數及α值的推薦結果Fig.3 Result in different group size and threshold α

4.3.3 加權混合融合策略和其他融合策略的比較

為了驗證GPUC模型中采用的加權混合融合策略的有效性，實驗選擇和傳統的單一融合策略平均滿意度策略，最尊者策略以及文獻[5]中提出的HAaB策略進行比較.由于HAaB策略在群組成員偏好相似度較高的情況下推薦效果較好，而加權混合融合策略通過差異度閾值α的調和，對群組差異度不敏感，推薦準確度相對穩定.為了驗證該策略在不同群組中的有效性，實驗設置兩組由7名用戶組成的群組做為目標群組.其中一組為偏好相似度較高的群組，由隨機挑選的一位目標用戶及其最近鄰集合中的前6位組合而成.另一組則為低相似群組，由隨機挑選的7名用戶組成，在挑選的過程中將互為最近鄰的用戶去掉，直到群組中沒有互為最近鄰的用戶為止.在使用GPUC模型推薦時，將差異度閾值α設為0.4.實驗結果如圖4所示.由圖4可以看出，平均滿意度策略，最尊者策略以及HAaB策略的推薦效果與群組偏好相似度的大小關系較大，對偏好相似度較高、偏好差異較小的群組的推薦效果要優于相似度較低的群組.而無論群組差異度大小，GPUC模型通過差異度閾值α的調和使得模型可以根據具體情況選擇具體的融合策略，充分發揮各個融合策略的優勢，因此對群組偏好差異度大小不敏感，推薦效果只與群組人數及差異度閾值α的選則有關，保證了模型在群組偏好相似度較高或者較低時都有較好的推薦效果，在對偏好差異較大的群組進行推薦的準確度交HAaB提高了4.03%，對偏好差異較小的群組進行推薦的準確度提高了1.31%.

圖4 不同融合策略的實驗結果Fig.4 Results in different aggregation strategies

5 總結與展望

由于人類的社會性，群組推薦逐漸成為了推薦系統的研究熱點.本文提出了基于用戶簽到行為的群組興趣點推薦模型GPUC.模型中采用了加權混合偏好融合策略融合群組成員的個人偏好，該策略既考慮了不同用戶對群組偏好的影響，同時也彌補了傳統的單一融合策略的不足，通過差異度閾值α的調和使GPUC模型在相似度較高的群組和相似度較低的群組中都有較好的推薦效果.相較與傳統的單一融合策略以及HAaB，本文提出的偏好融合策略能為用戶產生更準確的推薦.