基于活動的社交網絡中的群組推薦算法設計①

朱成純,張 謐

(復旦大學 計算機科學技術學院,上海 200203)

基于活動的社交網絡中的群組推薦算法設計①

朱成純,張 謐

(復旦大學 計算機科學技術學院,上海 200203)

在基于活動的社交網絡(EBSN)中,群組中聚集了具有相似興趣的用戶,并為用戶組織并舉辦線下活動,在社區的發展中起到了至關重要的作用,因而理解用戶加入群組的原因和群組形成的過程在社交網絡的研究中是一個重要的議題.本文通過基于活動的社交網絡中的一些相關內容信息,比如社交網絡中的標簽信息和地理位置信息,來輔助推薦系統更好地為用戶預測對于群組的偏好.本文提出了SEGELER(pair-wiSE Geo-social Event-based LatEnt factoR)模型,并使用這些社交網絡中的信息,來為用戶的興趣進行預測.通過在真實的EBSN數據集上進行實驗與驗證,本文的模型不僅可以有效提升對于用戶偏好的預測,也可以緩解冷啟動問題.

社交網絡;推薦系統;群組推薦;貝葉斯個性化排序;潛在因子

在社交網絡中,群組是一個基本的組成部分,并在用戶社交行為的參與中起到了非常重要的作用.Charles Horton Cooley提出,線下的社交群組可以被歸類為一級組,二級組和用組,而對于線上的社交網絡而言,由于其相對更快速的用戶變化和活動舉辦,對線上群組的分類是一個更加復雜的問題.在線上社交網絡中,用戶可以以不同的興趣和理由加入不同的群組.例如,用戶會加入一個產品交流討論組來為想購買的產品尋求建議和討論,而同時用戶也因自己的閱讀興趣而加入了閱讀小組.而關于群組形成的研究[1,2],以及預測用戶對群組偏好的研究[3]在社交網絡中已經成為了非常重要的研究課題.

本文研究在特定社交網絡——基于活動的社交網絡(EBSN)中預測用戶對群組偏好.用戶,群組,活動是EBSN中三種最基本的實體.用戶可以加入不同的群組,并且參加由不同群組舉辦的不同活動.所以在EBSN中,用戶之間的關系和聯系也通過用戶加入的群組和參與的群組活動所建立.因而在EBSN中,預測用戶對群組的偏好對于幫助用戶發現自己的興趣和想參加的活動是非常有幫助的.

EBSN研究中很重要的一方面就是納入并應用相關的信息.很多相關的研究提出了一些使用相關信息的方法,比如具有普適性的相關信息應用方法[4,5],和針對特定相關信息的應用方法,例如地點推薦研究[6]和活動推薦研究[7,8].其他一些研究標簽信息的相關工作的效果[3]和活動位置信息[9]的效果也被研究與提出,但這些方法并沒有考慮到活動的情況,因而無法很好的使用這些相關信息.

在ESBN社交網絡中擁有很多相關信息,例如標簽信息、地理位置信息、時間信息等等,其中地理位置信息作為ESBN中的重要信息,用于幫助判斷用戶活動范圍;而標簽信息作為對用戶和群組的補充描述也有助于了解用戶的興趣.本文同時納入并使用了兩種社交網絡中的相關信息——用戶和群組的標簽信息和地理位置的活動信息,來幫助更好的預測用戶對EBSN社交群組的偏好.本文提出了基于ESBN社交網絡中地理位置信息和標簽信息的SEGELER (pairwiSE Geo-social Event-based LatEnt factoR)模型,通過利用標簽信息和地理位置信息來判斷用戶的行為.標簽的語義相似度信息和近鄰影響在模型中被考慮,而pairwise的目標函數也被提出用于最大化用戶對群組的偏好.對于EBSN經常受缺少負例的影響,例如只有用戶參與群組的信息被記錄下來,而用戶討厭或不喜歡群組的信息則會相對而言較少甚至缺失,本文也提出了有效的算法來解決這一問題.

本文通過在真實的EBSN大數據集meetup上進行實驗驗證得出SEGELER模型比其他的算法有明顯的提升,而推薦系統中冷啟動問題也可以通過使用這些社交網絡中的信息來得到緩解.

1 符號定義

基于活動的社交網絡(EBSN)通常擁有標簽信息與地理位置的活動信息,EBSN的數據可以被定義為集合{U,G,E,T,L},其中分別代表了群組集合,用戶集合,活動集合,標簽集合與地點集合.活動E可以被群組G舉辦,而用戶U可以參與不同的群組G,并根據自己的興趣參加群組舉辦的活動.對于用戶u,他/她所加入的群組的集合記為而他/她不感興趣的群組的集合記為其中用戶u和群組g所擁有的標簽分別記為用戶u所居住的地點記為表示群組g舉辦的活動集合,表示用戶u參與的活動集合,活動e的地點記為用戶,群組和活動通常由其用戶ID,群組ID和活動ID來表示,而標簽由有意義的描述用戶和群組的詞語組成,地點則由其經緯度來表示.圖1展示了一個EBSN的數據結構.

圖1 基于活動的社交網絡基本結構

本文定義每一個用戶和群組的活動范圍為用戶和群組去過的地點的集合:

2 SEGELER 模型

對于預測用戶感興趣的群組的問題而言,準確預測用戶最感興趣的前幾位群組是非常重要的,因而本文使用排序的目標函數來優化此問題,即需要把用戶感興趣的群組排序高于用戶不感興趣的群組.

對于排序問題而言之前的研究提出了許多排序的方法,例如 pairwise 排序[10]和 listwise[11]排序.由于在本問題中只需要將感興趣的群組排序靠前,本文使用pairwise排序的方法使用戶感興趣的群組排序高于用戶不感興趣的群組.即對于每一個用戶u,以及u感興趣的群組集合和不感興趣的群組集合需要使的排序高于.本文基于貝葉斯個性化排序(BPR)[12]方法提出本文的pairwise排序目標函數來提取用戶對群組的偏好特征,通過最大化如下的后驗概率(MAP):

其中θ表示相關的模型參數,這些參數會在后面的章節進行詳細解釋表示用戶u對群組g的估計偏好值,此值越大表示用戶u對群組g的偏好越大.是 sigmoid 函數Pr(θ)表示SEGELER模型中參數的高斯先驗概率分布,這部分會在后面進行詳述.用戶感興趣的群組與不感興趣的群組之間的預測值之間的差距應當變大.下一章將會詳細地闡述的具體模型.

2.1 算法設計

潛在因子模型(LFM)假設用戶和群組對每一個隱式因子都有偏好.對于每一個用戶u和群組g,代表u與g的隱式向量表示,即u與g在這個隱式因子下的偏好.的乘積表示用戶u對群組g的偏好即u對于g的偏好可以表示為:

考慮標簽信息和活動范圍信息之后,本文提出公式(3)以更好的預測用戶對群組的偏好:

此外,David[13]提出擁有相似標簽/活動范圍的用戶更有可能出現在相同的群組中,因此本文定義另兩個隱式向量表示以考慮用戶的近鄰對用戶的影響:

將公式(6)合并入公式(2),用戶對群組偏好的式子可以延伸為:

2.2 參數學習

為求得公式(1)中的參數,本文采用了SGD(隨機梯度下降)算法來最大化公式(1).在每一輪SGD迭代中,通過隨機選擇一個用戶u,用戶感興趣的正例群組gp,與用戶不感興趣的負例群組gn,組成一個三元組{u,gp,gn},并使用梯度下降法來求解參數θ:

在SGD學習的過程中,對于每一個用戶,本文只隨機選取一小部分的負例(u,gn)來減少計算的復雜度,這樣算法的計算復雜度為O(|D|(|L|+|T|)),其中|D|是訓練集的大小.在實驗中,對于每一個用戶u和u感興趣的正例群組gp,本文選取c個u不感興趣的負例群組gn,加入訓練集.c 值越大,模型訓練與收斂時間越長,效果越好.通過平衡訓練時間與最后的模型效果,最終本文設置參數c=5作為選取負例的數量.

在EBSN中,負例即用戶不喜歡的群組很少被記錄下來,這對SEGELER模型的學習和參數優化提出了很大的挑戰.本文提出了一個有效的策略來選擇潛在負例.此外,考慮到標簽w和標簽t之間擁有語義相似度,本文為入了一個相應的先驗概率,標簽u和標簽t之間的語義相似度由WordNet計算得到,表示和標簽t相似度高的標簽集合.

2.3 負例選擇

由于用戶加入不感興趣的群組的概率較低,可以把一些偏好值較低的群組{(u,g)}作為負例,本文提出了如下的相似度計算方法來得到用戶對群組的的偏好值:

這個策略在試驗中被證明十分有效,并比其他的策略效果,比如 Kabbur[14]和 Cheng[6]更好.本文在實驗中設定ξ=0.015作為選取負例的閾值.

3 實驗與分析

3.1 數據集介紹

本文在真實的EBSN大數據集Meetup[15]中驗證了模型的效果,Meetup是一個在線社交活動網站,幫助用戶發布和參與到線下的活動中.由于只有1.7%的活動是跨城市的活動,本文從Meetup中選取了三個大城市 LA(洛杉磯),SF(舊金山)和 NYC(紐約)作為三個數據集來驗證SEGELER模型.

3.2 對比算法介紹

本文采用并實現了六個推薦系統領域的算法作為對比算法.

基于用戶的協同過濾算法(UBCF)通過將用戶的鄰居信息考慮其中來預測用戶對群組的偏好.由于在EBSN中,用戶行為容易受到鄰居影響,UBCF很適合作為這個問題的對比算法.

SVD++把用戶的隱式反饋加入了考慮中,在矩陣分解中提供了額外的考慮信息.在EBSN中,用戶的隱式反饋對于預測群組偏好也是很有幫助.

概率矩陣分解(PMF)是一個基于概率的因子算法,在EBSN中效果很好并被廣泛應用.

NSVD是一個基于物品-物品因子的協同過濾算法,NSVD使用了用戶的過往記錄和相關信息.

BPR-MF是一個潛在因子協同過濾算法,通過使用BPR優化來針對個性化的排序問題.

PTARMIGAN(PTA)是一個pairwise的基于標簽信息和特征的矩陣分解算法,PTA使用了諸如標簽信息和地理位置信息的相關信息來預測用戶對群組的偏好,PTA也是為EBSN進行特定設計的預測算法.

3.3 評價指標介紹

本文使用了三個評價指標——準確率(precision),召回率(recall)以及NDCG,來為所有方法的top-k預測進行衡量與評價.

對于每一個數據集,本文隨機選擇了80%的用戶和與之相關的群組/活動/標簽作為訓練集,而將剩下的作為測試集.公式(1)中的λ在[0,0.02]中取值,所有模型的實驗都經過了交叉驗證.

3.4 SEGELER實驗結果分析

本文在三個數據集LA,SF和NYC上將SEGELER模型與六個對照模型進行了比對.圖2與圖3列出了所有模型的準確率,召回率以及NDCG值.

圖3的結果可以得出,SEGELER模型在三個數據集下的NDCG值的評價指標下明顯超過了其他的對照算法.例如,SEGELER模型在LA數據集上的NDCG值相較其他對照算法至少17%.而圖2中準確率和召回率的結果也驗證了SEGELER模型相較其他模型擁有非常大的提升.這說明通過利用好標簽信息和地理位置信息.并且最大化用戶喜歡的群組和不喜歡的群組間的不同,SEGELER模型可以將用戶喜歡的群組排序更高,從而得到更好的預測結果.

圖2 各個模型的 Precision 和 Recall值

圖3 各個模型的 NDCG 值

3.5 冷啟動問題分析

本文也同樣針對冷啟動用戶的預測效果進行了實驗研究.在此實驗中,本文將參與群組數較少的用戶定義為“冷啟動用戶”.由于在數據集中,每一個用戶平均參與了40個群組,本文中將參與少于10個群組的用戶和少于15個群組的用戶定義為兩種情況下的“冷啟動用戶”.圖4展示了在LA數據集上top-3準確率上不同算法的結果.從圖4中可以看出,在兩種情況下,SEGELER模型都比其他對照算法效果更好,并取得了至少48.21%的提升.這說明通過對于相關標簽信息和地理位置信息的挖掘,SEGELER算法可以更好的幫助新用戶來選擇感興趣的群組.

3.6 負例選取方法實驗分析

最后本文比較不同的負例選擇方法對實驗結果產生的影響.本文將本文提出的負例選擇算法與隨機負例選擇法,只通過標簽信息計算得到的標簽策略,只通過活動信息計算得到的活動策略,以及只通過地理位置信息計算得到的地點策略進行比較.圖5展示了在LA數據集上不同負例選擇方法的效果,從圖5中可以得知,本文的負例選擇算法相較其他算法對最后結果有更大的提升.這也說明了在EBSN中,用戶通常更喜歡更相似的群組,這個相似度可以通過不同方面來計算,諸如相似的標簽或相似的地點.

圖4 SEGELER 模型在冷啟動用戶上的 Precision

圖5 不同負例選取策略的 Precision 值

4 結語

本文研究在社交網絡中為用戶預測對群組的偏好的問題,并利用了EBSN中的標簽信息以及地理位置信息來提升預測的效果.本文提出了SEGELER(pairwiSE Geo-social Event-based LatEnt factoR)模型將這些相關信息進行使用來更好地分析用戶偏好,并提出了基于貝葉斯個性化排序的目標函數來優化預測用戶在社交網絡中喜歡的群組對于社交網絡中負例缺失的問題,本文提出了有效的算法來解決這一問題.通過EBSN數據集Meetup上的實驗,驗證了提出的算法在效果上的提升,同時可以緩解冷啟動問題.在未來工作中,作者會繼續分析并納入更多社交網絡中相關信息,諸如時間信息和情感信息,來提升預測的效果.同時除了預測準確度之外,其他的評價標準諸如預測區分度也將進行研究.

1 Sun YZ,Tang J,Han JW,et al.Co-evolution of multi-typed objects in dynamic star networks.IEEE Trans.on Knowledge and Data Engineering,2014,26(12):2942–2955.[doi:10.1109/TKDE.2013.103]

2 Dong YX,Zhang J,Tang J,et al.CoupledLP:Link prediction in coupled networks.Proc.of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Sydney,NSW,Australia.2015.199–208.

3 Zheng N,Li QD,Liao SC,et al.Flickr group recommendation based on tensor decomposition.Proc.of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval.Geneva,Switzerland.2010.737–738.

4 Rendle S,Gantner Z,Freudenthaler C,et al.Fast contextaware recommendations with factorization machines.Proc.of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.Beijing,China.2011.635–644.

5 Pham TAN,Li XT,Cong G,et al.A general graph-based model for recommendation in event-based social networks.Proc.of 2015 IEEE the 31st International Conference on Data Engineering.Seoul,South Korea.2015.567–578.

6 Cheng C,Yang HQ,Lyu M R,et al.Where you like to go next:Successive point-of-interest recommendation.Proc.of the 23rd International Joint Conference on Artificial Intelligence.Beijing,China.2013.2605–2611

7 Ji XC,Qiao Z,Xu MZ,et al.Online event recommendation for event-based social networks.Proc.of the 24th International Conference on World Wide Web.Florence,Italy.2015.45–46.

8 Qiao Z,Zhang P,Cao YN,et al.Combining heterogenous social and geographical information for event recommendation.Proc.of the 28th AAAI Conference on Artificial Intelligence.Québec City,Québec,Canada.2014.145–151.

9 Zhang W,Wang JY.A collective bayesian poisson factorization model for cold-start local event recommendation.Proc.of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Sydney,NSW,Australia.2015.1455–1464.

10 Sellamanickam S,Garg P,Selvaraj SK.A pairwise ranking based approach to learning with positive and unlabeled examples.Proc.of the 20th ACM International Conference on Information and Knowledge Management.Glasgow,Scotland,UK.2011.663–672.

11 Cao Z,Qin T,Liu TY,et al.Learning to rank:From pairwise approach to listwise approach.Proc.of the 24th International Conference on Machine Learning.Corvalis,Oregon,USA.2007.129–136.

12 Rendle S,Freudenthaler C,Gantner Z,et al.BPR:Bayesian personalized ranking from implicit feedback.Proc.of the 25th Conference on Uncertainty in Artificial Intelligence.Montreal,Quebec,Canada.2012.452–461.

13 Crandall DJ,Backstrom L,Cosley D,et al.Inferring social ties from geographic coincidences.Proc.of the National Academy of Sciences of the United States of America,2010,107(52):22436–22441.[doi:10.1073/pnas.1006155107]

14 Kabbur S,Ning X,Karypis G.Fism:Factored item similarity models for top-n recommender systems.Proc.of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Chicago,Illinois,USA.2013.659–667.

15 Liu XJ,He Q,Tian YY,et al.Event-based social networks:Linking the online and offline social worlds.Proc.of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Beijing,China.2012.1032–1040.

Predicting User Preferences for Groups in Event-Based Social Networks

ZHU Cheng-Chun,ZHANG Mi
(School of Computer Science and Technology,Fudan University,Shanghai 200203,China)

In event-based social networks (EBSN),groups that aggregate users with similar interests for sharing events play important roles in community development.Understanding why people join a group and how groups are formed is particularly an interesting issue in social science.In this paper,we study predicting users’ preferences on social groups by considering content information in EBSN,i.e.,geographic-social event-based recommendation.Specifically,we consider two types of content information,i.e.,the tags and geographical event locations about users/events.We propose the SEGELER (pair-wiSE Geo-social Event-based LatEnt factoR)to model the users behavior considering the information.Experiments on a real-world EBSN social network validate the effectiveness of our proposed approach for both normal users and cold start users.

social network;recommender system;group recommendation;Bayesian personalized ranking;latent factor

朱成純,張謐.基于活動的社交網絡中的群組推薦算法設計.計算機系統應用,2017,26(9):103–108.http://www.c-s-a.org.cn/1003-3254/5940.html

2016-12-14;采用時間:2017-01-16