朱成純,張 謐
(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海 200203)
基于活動(dòng)的社交網(wǎng)絡(luò)中的群組推薦算法設(shè)計(jì)①
朱成純,張 謐
(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海 200203)
在基于活動(dòng)的社交網(wǎng)絡(luò)(EBSN)中,群組中聚集了具有相似興趣的用戶,并為用戶組織并舉辦線下活動(dòng),在社區(qū)的發(fā)展中起到了至關(guān)重要的作用,因而理解用戶加入群組的原因和群組形成的過(guò)程在社交網(wǎng)絡(luò)的研究中是一個(gè)重要的議題.本文通過(guò)基于活動(dòng)的社交網(wǎng)絡(luò)中的一些相關(guān)內(nèi)容信息,比如社交網(wǎng)絡(luò)中的標(biāo)簽信息和地理位置信息,來(lái)輔助推薦系統(tǒng)更好地為用戶預(yù)測(cè)對(duì)于群組的偏好.本文提出了SEGELER(pair-wiSE Geo-social Event-based LatEnt factoR)模型,并使用這些社交網(wǎng)絡(luò)中的信息,來(lái)為用戶的興趣進(jìn)行預(yù)測(cè).通過(guò)在真實(shí)的EBSN數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)與驗(yàn)證,本文的模型不僅可以有效提升對(duì)于用戶偏好的預(yù)測(cè),也可以緩解冷啟動(dòng)問(wèn)題.
社交網(wǎng)絡(luò);推薦系統(tǒng);群組推薦;貝葉斯個(gè)性化排序;潛在因子
在社交網(wǎng)絡(luò)中,群組是一個(gè)基本的組成部分,并在用戶社交行為的參與中起到了非常重要的作用.Charles Horton Cooley提出,線下的社交群組可以被歸類(lèi)為一級(jí)組,二級(jí)組和用組,而對(duì)于線上的社交網(wǎng)絡(luò)而言,由于其相對(duì)更快速的用戶變化和活動(dòng)舉辦,對(duì)線上群組的分類(lèi)是一個(gè)更加復(fù)雜的問(wèn)題.在線上社交網(wǎng)絡(luò)中,用戶可以以不同的興趣和理由加入不同的群組.例如,用戶會(huì)加入一個(gè)產(chǎn)品交流討論組來(lái)為想購(gòu)買(mǎi)的產(chǎn)品尋求建議和討論,而同時(shí)用戶也因自己的閱讀興趣而加入了閱讀小組.而關(guān)于群組形成的研究[1,2],以及預(yù)測(cè)用戶對(duì)群組偏好的研究[3]在社交網(wǎng)絡(luò)中已經(jīng)成為了非常重要的研究課題.
本文研究在特定社交網(wǎng)絡(luò)——基于活動(dòng)的社交網(wǎng)絡(luò)(EBSN)中預(yù)測(cè)用戶對(duì)群組偏好.用戶,群組,活動(dòng)是EBSN中三種最基本的實(shí)體.用戶可以加入不同的群組,并且參加由不同群組舉辦的不同活動(dòng).所以在EBSN中,用戶之間的關(guān)系和聯(lián)系也通過(guò)用戶加入的群組和參與的群組活動(dòng)所建立.因而在EBSN中,預(yù)測(cè)用戶對(duì)群組的偏好對(duì)于幫助用戶發(fā)現(xiàn)自己的興趣和想?yún)⒓拥幕顒?dòng)是非常有幫助的.
EBSN研究中很重要的一方面就是納入并應(yīng)用相關(guān)的信息.很多相關(guān)的研究提出了一些使用相關(guān)信息的方法,比如具有普適性的相關(guān)信息應(yīng)用方法[4,5],和針對(duì)特定相關(guān)信息的應(yīng)用方法,例如地點(diǎn)推薦研究[6]和活動(dòng)推薦研究[7,8].其他一些研究標(biāo)簽信息的相關(guān)工作的效果[3]和活動(dòng)位置信息[9]的效果也被研究與提出,但這些方法并沒(méi)有考慮到活動(dòng)的情況,因而無(wú)法很好的使用這些相關(guān)信息.
在ESBN社交網(wǎng)絡(luò)中擁有很多相關(guān)信息,例如標(biāo)簽信息、地理位置信息、時(shí)間信息等等,其中地理位置信息作為ESBN中的重要信息,用于幫助判斷用戶活動(dòng)范圍;而標(biāo)簽信息作為對(duì)用戶和群組的補(bǔ)充描述也有助于了解用戶的興趣.本文同時(shí)納入并使用了兩種社交網(wǎng)絡(luò)中的相關(guān)信息——用戶和群組的標(biāo)簽信息和地理位置的活動(dòng)信息,來(lái)幫助更好的預(yù)測(cè)用戶對(duì)EBSN社交群組的偏好.本文提出了基于ESBN社交網(wǎng)絡(luò)中地理位置信息和標(biāo)簽信息的SEGELER (pairwiSE Geo-social Event-based LatEnt factoR)模型,通過(guò)利用標(biāo)簽信息和地理位置信息來(lái)判斷用戶的行為.標(biāo)簽的語(yǔ)義相似度信息和近鄰影響在模型中被考慮,而pairwise的目標(biāo)函數(shù)也被提出用于最大化用戶對(duì)群組的偏好.對(duì)于EBSN經(jīng)常受缺少負(fù)例的影響,例如只有用戶參與群組的信息被記錄下來(lái),而用戶討厭或不喜歡群組的信息則會(huì)相對(duì)而言較少甚至缺失,本文也提出了有效的算法來(lái)解決這一問(wèn)題.
本文通過(guò)在真實(shí)的EBSN大數(shù)據(jù)集meetup上進(jìn)行實(shí)驗(yàn)驗(yàn)證得出SEGELER模型比其他的算法有明顯的提升,而推薦系統(tǒng)中冷啟動(dòng)問(wèn)題也可以通過(guò)使用這些社交網(wǎng)絡(luò)中的信息來(lái)得到緩解.
基于活動(dòng)的社交網(wǎng)絡(luò)(EBSN)通常擁有標(biāo)簽信息與地理位置的活動(dòng)信息,EBSN的數(shù)據(jù)可以被定義為集合{U,G,E,T,L},其中分別代表了群組集合,用戶集合,活動(dòng)集合,標(biāo)簽集合與地點(diǎn)集合.活動(dòng)E可以被群組G舉辦,而用戶U可以參與不同的群組G,并根據(jù)自己的興趣參加群組舉辦的活動(dòng).對(duì)于用戶u,他/她所加入的群組的集合記為而他/她不感興趣的群組的集合記為其中用戶u和群組g所擁有的標(biāo)簽分別記為用戶u所居住的地點(diǎn)記為表示群組g舉辦的活動(dòng)集合,表示用戶u參與的活動(dòng)集合,活動(dòng)e的地點(diǎn)記為用戶,群組和活動(dòng)通常由其用戶ID,群組ID和活動(dòng)ID來(lái)表示,而標(biāo)簽由有意義的描述用戶和群組的詞語(yǔ)組成,地點(diǎn)則由其經(jīng)緯度來(lái)表示.圖1展示了一個(gè)EBSN的數(shù)據(jù)結(jié)構(gòu).
圖1 基于活動(dòng)的社交網(wǎng)絡(luò)基本結(jié)構(gòu)
本文定義每一個(gè)用戶和群組的活動(dòng)范圍為用戶和群組去過(guò)的地點(diǎn)的集合:
對(duì)于預(yù)測(cè)用戶感興趣的群組的問(wèn)題而言,準(zhǔn)確預(yù)測(cè)用戶最感興趣的前幾位群組是非常重要的,因而本文使用排序的目標(biāo)函數(shù)來(lái)優(yōu)化此問(wèn)題,即需要把用戶感興趣的群組排序高于用戶不感興趣的群組.
對(duì)于排序問(wèn)題而言之前的研究提出了許多排序的方法,例如 pairwise 排序[10]和 listwise[11]排序.由于在本問(wèn)題中只需要將感興趣的群組排序靠前,本文使用pairwise排序的方法使用戶感興趣的群組排序高于用戶不感興趣的群組.即對(duì)于每一個(gè)用戶u,以及u感興趣的群組集合和不感興趣的群組集合需要使的排序高于.本文基于貝葉斯個(gè)性化排序(BPR)[12]方法提出本文的pairwise排序目標(biāo)函數(shù)來(lái)提取用戶對(duì)群組的偏好特征,通過(guò)最大化如下的后驗(yàn)概率(MAP):
其中θ表示相關(guān)的模型參數(shù),這些參數(shù)會(huì)在后面的章節(jié)進(jìn)行詳細(xì)解釋表示用戶u對(duì)群組g的估計(jì)偏好值,此值越大表示用戶u對(duì)群組g的偏好越大.是 sigmoid 函數(shù)Pr(θ)表示SEGELER模型中參數(shù)的高斯先驗(yàn)概率分布,這部分會(huì)在后面進(jìn)行詳述.用戶感興趣的群組與不感興趣的群組之間的預(yù)測(cè)值之間的差距應(yīng)當(dāng)變大.下一章將會(huì)詳細(xì)地闡述的具體模型.
潛在因子模型(LFM)假設(shè)用戶和群組對(duì)每一個(gè)隱式因子都有偏好.對(duì)于每一個(gè)用戶u和群組g,代表u與g的隱式向量表示,即u與g在這個(gè)隱式因子下的偏好.的乘積表示用戶u對(duì)群組g的偏好即u對(duì)于g的偏好可以表示為:
考慮標(biāo)簽信息和活動(dòng)范圍信息之后,本文提出公式(3)以更好的預(yù)測(cè)用戶對(duì)群組的偏好:
此外,David[13]提出擁有相似標(biāo)簽/活動(dòng)范圍的用戶更有可能出現(xiàn)在相同的群組中,因此本文定義另兩個(gè)隱式向量表示以考慮用戶的近鄰對(duì)用戶的影響:
將公式(6)合并入公式(2),用戶對(duì)群組偏好的式子可以延伸為:
為求得公式(1)中的參數(shù),本文采用了SGD(隨機(jī)梯度下降)算法來(lái)最大化公式(1).在每一輪SGD迭代中,通過(guò)隨機(jī)選擇一個(gè)用戶u,用戶感興趣的正例群組gp,與用戶不感興趣的負(fù)例群組gn,組成一個(gè)三元組{u,gp,gn},并使用梯度下降法來(lái)求解參數(shù)θ:
在SGD學(xué)習(xí)的過(guò)程中,對(duì)于每一個(gè)用戶,本文只隨機(jī)選取一小部分的負(fù)例(u,gn)來(lái)減少計(jì)算的復(fù)雜度,這樣算法的計(jì)算復(fù)雜度為O(|D|(|L|+|T|)),其中|D|是訓(xùn)練集的大小.在實(shí)驗(yàn)中,對(duì)于每一個(gè)用戶u和u感興趣的正例群組gp,本文選取c個(gè)u不感興趣的負(fù)例群組gn,加入訓(xùn)練集.c 值越大,模型訓(xùn)練與收斂時(shí)間越長(zhǎng),效果越好.通過(guò)平衡訓(xùn)練時(shí)間與最后的模型效果,最終本文設(shè)置參數(shù)c=5作為選取負(fù)例的數(shù)量.
在EBSN中,負(fù)例即用戶不喜歡的群組很少被記錄下來(lái),這對(duì)SEGELER模型的學(xué)習(xí)和參數(shù)優(yōu)化提出了很大的挑戰(zhàn).本文提出了一個(gè)有效的策略來(lái)選擇潛在負(fù)例.此外,考慮到標(biāo)簽w和標(biāo)簽t之間擁有語(yǔ)義相似度,本文為入了一個(gè)相應(yīng)的先驗(yàn)概率,標(biāo)簽u和標(biāo)簽t之間的語(yǔ)義相似度由WordNet計(jì)算得到,表示和標(biāo)簽t相似度高的標(biāo)簽集合.
由于用戶加入不感興趣的群組的概率較低,可以把一些偏好值較低的群組{(u,g)}作為負(fù)例,本文提出了如下的相似度計(jì)算方法來(lái)得到用戶對(duì)群組的的偏好值:
這個(gè)策略在試驗(yàn)中被證明十分有效,并比其他的策略效果,比如 Kabbur[14]和 Cheng[6]更好.本文在實(shí)驗(yàn)中設(shè)定ξ=0.015作為選取負(fù)例的閾值.
本文在真實(shí)的EBSN大數(shù)據(jù)集Meetup[15]中驗(yàn)證了模型的效果,Meetup是一個(gè)在線社交活動(dòng)網(wǎng)站,幫助用戶發(fā)布和參與到線下的活動(dòng)中.由于只有1.7%的活動(dòng)是跨城市的活動(dòng),本文從Meetup中選取了三個(gè)大城市 LA(洛杉磯),SF(舊金山)和 NYC(紐約)作為三個(gè)數(shù)據(jù)集來(lái)驗(yàn)證SEGELER模型.
本文采用并實(shí)現(xiàn)了六個(gè)推薦系統(tǒng)領(lǐng)域的算法作為對(duì)比算法.
基于用戶的協(xié)同過(guò)濾算法(UBCF)通過(guò)將用戶的鄰居信息考慮其中來(lái)預(yù)測(cè)用戶對(duì)群組的偏好.由于在EBSN中,用戶行為容易受到鄰居影響,UBCF很適合作為這個(gè)問(wèn)題的對(duì)比算法.
SVD++把用戶的隱式反饋加入了考慮中,在矩陣分解中提供了額外的考慮信息.在EBSN中,用戶的隱式反饋對(duì)于預(yù)測(cè)群組偏好也是很有幫助.
概率矩陣分解(PMF)是一個(gè)基于概率的因子算法,在EBSN中效果很好并被廣泛應(yīng)用.
NSVD是一個(gè)基于物品-物品因子的協(xié)同過(guò)濾算法,NSVD使用了用戶的過(guò)往記錄和相關(guān)信息.
BPR-MF是一個(gè)潛在因子協(xié)同過(guò)濾算法,通過(guò)使用BPR優(yōu)化來(lái)針對(duì)個(gè)性化的排序問(wèn)題.
PTARMIGAN(PTA)是一個(gè)pairwise的基于標(biāo)簽信息和特征的矩陣分解算法,PTA使用了諸如標(biāo)簽信息和地理位置信息的相關(guān)信息來(lái)預(yù)測(cè)用戶對(duì)群組的偏好,PTA也是為EBSN進(jìn)行特定設(shè)計(jì)的預(yù)測(cè)算法.
本文使用了三個(gè)評(píng)價(jià)指標(biāo)——準(zhǔn)確率(precision),召回率(recall)以及NDCG,來(lái)為所有方法的top-k預(yù)測(cè)進(jìn)行衡量與評(píng)價(jià).
對(duì)于每一個(gè)數(shù)據(jù)集,本文隨機(jī)選擇了80%的用戶和與之相關(guān)的群組/活動(dòng)/標(biāo)簽作為訓(xùn)練集,而將剩下的作為測(cè)試集.公式(1)中的λ在[0,0.02]中取值,所有模型的實(shí)驗(yàn)都經(jīng)過(guò)了交叉驗(yàn)證.
本文在三個(gè)數(shù)據(jù)集LA,SF和NYC上將SEGELER模型與六個(gè)對(duì)照模型進(jìn)行了比對(duì).圖2與圖3列出了所有模型的準(zhǔn)確率,召回率以及NDCG值.
圖3的結(jié)果可以得出,SEGELER模型在三個(gè)數(shù)據(jù)集下的NDCG值的評(píng)價(jià)指標(biāo)下明顯超過(guò)了其他的對(duì)照算法.例如,SEGELER模型在LA數(shù)據(jù)集上的NDCG值相較其他對(duì)照算法至少17%.而圖2中準(zhǔn)確率和召回率的結(jié)果也驗(yàn)證了SEGELER模型相較其他模型擁有非常大的提升.這說(shuō)明通過(guò)利用好標(biāo)簽信息和地理位置信息.并且最大化用戶喜歡的群組和不喜歡的群組間的不同,SEGELER模型可以將用戶喜歡的群組排序更高,從而得到更好的預(yù)測(cè)結(jié)果.
圖2 各個(gè)模型的 Precision 和 Recall值
圖3 各個(gè)模型的 NDCG 值
本文也同樣針對(duì)冷啟動(dòng)用戶的預(yù)測(cè)效果進(jìn)行了實(shí)驗(yàn)研究.在此實(shí)驗(yàn)中,本文將參與群組數(shù)較少的用戶定義為“冷啟動(dòng)用戶”.由于在數(shù)據(jù)集中,每一個(gè)用戶平均參與了40個(gè)群組,本文中將參與少于10個(gè)群組的用戶和少于15個(gè)群組的用戶定義為兩種情況下的“冷啟動(dòng)用戶”.圖4展示了在LA數(shù)據(jù)集上top-3準(zhǔn)確率上不同算法的結(jié)果.從圖4中可以看出,在兩種情況下,SEGELER模型都比其他對(duì)照算法效果更好,并取得了至少48.21%的提升.這說(shuō)明通過(guò)對(duì)于相關(guān)標(biāo)簽信息和地理位置信息的挖掘,SEGELER算法可以更好的幫助新用戶來(lái)選擇感興趣的群組.
最后本文比較不同的負(fù)例選擇方法對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生的影響.本文將本文提出的負(fù)例選擇算法與隨機(jī)負(fù)例選擇法,只通過(guò)標(biāo)簽信息計(jì)算得到的標(biāo)簽策略,只通過(guò)活動(dòng)信息計(jì)算得到的活動(dòng)策略,以及只通過(guò)地理位置信息計(jì)算得到的地點(diǎn)策略進(jìn)行比較.圖5展示了在LA數(shù)據(jù)集上不同負(fù)例選擇方法的效果,從圖5中可以得知,本文的負(fù)例選擇算法相較其他算法對(duì)最后結(jié)果有更大的提升.這也說(shuō)明了在EBSN中,用戶通常更喜歡更相似的群組,這個(gè)相似度可以通過(guò)不同方面來(lái)計(jì)算,諸如相似的標(biāo)簽或相似的地點(diǎn).
圖4 SEGELER 模型在冷啟動(dòng)用戶上的 Precision
圖5 不同負(fù)例選取策略的 Precision 值
本文研究在社交網(wǎng)絡(luò)中為用戶預(yù)測(cè)對(duì)群組的偏好的問(wèn)題,并利用了EBSN中的標(biāo)簽信息以及地理位置信息來(lái)提升預(yù)測(cè)的效果.本文提出了SEGELER(pairwiSE Geo-social Event-based LatEnt factoR)模型將這些相關(guān)信息進(jìn)行使用來(lái)更好地分析用戶偏好,并提出了基于貝葉斯個(gè)性化排序的目標(biāo)函數(shù)來(lái)優(yōu)化預(yù)測(cè)用戶在社交網(wǎng)絡(luò)中喜歡的群組對(duì)于社交網(wǎng)絡(luò)中負(fù)例缺失的問(wèn)題,本文提出了有效的算法來(lái)解決這一問(wèn)題.通過(guò)EBSN數(shù)據(jù)集Meetup上的實(shí)驗(yàn),驗(yàn)證了提出的算法在效果上的提升,同時(shí)可以緩解冷啟動(dòng)問(wèn)題.在未來(lái)工作中,作者會(huì)繼續(xù)分析并納入更多社交網(wǎng)絡(luò)中相關(guān)信息,諸如時(shí)間信息和情感信息,來(lái)提升預(yù)測(cè)的效果.同時(shí)除了預(yù)測(cè)準(zhǔn)確度之外,其他的評(píng)價(jià)標(biāo)準(zhǔn)諸如預(yù)測(cè)區(qū)分度也將進(jìn)行研究.
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
朱成純,張謐.基于活動(dòng)的社交網(wǎng)絡(luò)中的群組推薦算法設(shè)計(jì).計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(9):103–108.http://www.c-s-a.org.cn/1003-3254/5940.html
2016-12-14;采用時(shí)間:2017-01-16