一種基于用戶互動(dòng)話題的微博推薦算法

魯驍 ，李鵬 ，王斌 ，李應(yīng)博，房婧

(1. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京，100029；2. 中國(guó)科學(xué)院大學(xué)，北京 100049；3. 中國(guó)科學(xué)院 信息工程研究所，北京 100093)

一種基于用戶互動(dòng)話題的微博推薦算法

(1. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京，100029；2. 中國(guó)科學(xué)院大學(xué)，北京 100049；3. 中國(guó)科學(xué)院 信息工程研究所，北京 100093)

隨著社交網(wǎng)絡(luò)的發(fā)展，微博逐漸成為人們獲取信息的重要來(lái)源。然而隨著用戶的增多，微博中的信息過(guò)載問(wèn)題也越來(lái)越嚴(yán)重，如何快速準(zhǔn)確地為用戶推薦感興趣的微博已經(jīng)成為研究的熱點(diǎn)。與傳統(tǒng)的推薦技術(shù)不同，微博中的用戶具有天然的社交關(guān)系，這為推薦算法提供了額外的用戶信息，因此，融合了用戶社交關(guān)系的社會(huì)化推薦方法日益受到重視。但是，現(xiàn)有的方法大多只利用了固定的用戶社交關(guān)系或簡(jiǎn)單的互動(dòng)行為，事實(shí)上，用戶互動(dòng)行為的出發(fā)點(diǎn)必然是用戶與好友的共同興趣，具有明顯的話題相關(guān)性。該文從話題層面來(lái)分析用戶的互動(dòng)關(guān)系，提出了度量互動(dòng)關(guān)系在話題上強(qiáng)弱度的方法，通過(guò)有效地融合互動(dòng)關(guān)系的話題特征，最終提出了改進(jìn)的微博推薦模型IBCF。實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有的社會(huì)化推薦方法相比，該文提出的新方法在MAP和NDCG等指標(biāo)上取得了更好的推薦效果，而且為推薦結(jié)果提供了更明確的可解釋性。

互動(dòng)關(guān)系，互動(dòng)話題，社會(huì)化推薦，協(xié)同過(guò)濾，微博推薦

1 引言

隨著社交網(wǎng)絡(luò)的發(fā)展，微博成為了近年來(lái)發(fā)展最快的熱門(mén)互聯(lián)網(wǎng)應(yīng)用之一。根據(jù)CNNIC于2013年1月發(fā)布的第31次《中國(guó)互聯(lián)網(wǎng)發(fā)展統(tǒng)計(jì)報(bào)告》顯示，截至2012年12月底，我國(guó)微博用戶規(guī)模為3.09億，較2011年底增長(zhǎng)了5 873萬(wàn)，增幅達(dá)到23.5%。網(wǎng)民中的微博用戶比例較上年底提升了六個(gè)百分點(diǎn)，達(dá)到54.7%。報(bào)告顯示，微博已經(jīng)成為中國(guó)網(wǎng)民使用的主流應(yīng)用，人們?nèi)找嬉蕾噺奈⒉┥汐@取最新的信息。新浪微博的數(shù)據(jù)顯示，用戶平均每天的在線時(shí)長(zhǎng)達(dá)到60分鐘，該平臺(tái)上每天的微博發(fā)布數(shù)量超過(guò)一億，微博上的信息已經(jīng)非常巨大。

信息量的膨脹，給用戶帶來(lái)了嚴(yán)重的信息過(guò)載問(wèn)題，如何有效地為用戶提供更有價(jià)值的內(nèi)容，已經(jīng)越來(lái)越具有挑戰(zhàn)性，這不僅具有巨大的商業(yè)前景，同時(shí)擁有的學(xué)術(shù)價(jià)值也不容小覷。近年來(lái)，針對(duì)社交網(wǎng)絡(luò)的研究日益豐富，TREC從2011年起提出了專門(mén)針對(duì)微博的信息檢索任務(wù)，SIGIR、CIKM等會(huì)議中關(guān)于微博的研究論文越來(lái)越多，KDD CUP 2012上，騰訊提供了從騰訊微博中提取出來(lái)的部分?jǐn)?shù)據(jù)，包括1000萬(wàn)個(gè)用戶，五萬(wàn)個(gè)項(xiàng)目(人、機(jī)構(gòu)、群)，三億條推薦記錄以及大約300萬(wàn)個(gè)社會(huì)網(wǎng)絡(luò)的關(guān)注行為等，用來(lái)支持用戶推薦的研究任務(wù)。

推薦技術(shù)能夠?yàn)槿藗兲峁└嗟倪x擇，不需要輸入任何檢索信息，利用推薦技術(shù)來(lái)自動(dòng)為用戶提供更感興趣的好友或內(nèi)容，例如，Twitter推出的“郵件精選”、“好友推薦”、“熱門(mén)趨勢(shì)”等服務(wù)，都是利用推薦技術(shù)來(lái)為用戶推送。國(guó)內(nèi)的新浪微博也提供了類似的“好友推薦”、“熱門(mén)話題”等服務(wù)?？梢钥闯?，利用推薦技術(shù)實(shí)現(xiàn)的主動(dòng)推送更適合于微博平臺(tái)。傳統(tǒng)的推薦方法，主要從物品內(nèi)容及用戶對(duì)物品的打分記錄出發(fā)，試圖挖掘用戶的興趣。而在微博中進(jìn)行個(gè)性化推薦，除了用戶的興趣之外，還需要考慮多種影響因素，包括內(nèi)容質(zhì)量、作者影響力等，除此之外，用戶之間的社交關(guān)系也是研究的重點(diǎn)。在微博中，用戶之間具有明顯的關(guān)系屬性，很多研究從這些關(guān)系出發(fā)，提出了融合用戶社交關(guān)系的推薦模型。

然而，現(xiàn)有的方法[1-4]一般只利用了固定的用戶社交關(guān)系或簡(jiǎn)單利用了用戶的互動(dòng)、影響力等因素，這種簡(jiǎn)單的社交關(guān)系是一種單質(zhì)的屬性，只能描述用戶是否具有關(guān)系，而無(wú)法描述關(guān)系的強(qiáng)弱，更無(wú)法解釋用戶關(guān)系的基礎(chǔ)。本文提出一種新的方法來(lái)定義用戶之間的關(guān)系，通過(guò)分析用戶與好友之間的互動(dòng)行為的頻率及內(nèi)容，來(lái)衡量用戶關(guān)系的話題屬性及關(guān)系強(qiáng)弱度，并將這種新的用戶關(guān)系定義方法用在推薦模型中以改善推薦的效果。

本文主要貢獻(xiàn)如下: (1)根據(jù)用戶互動(dòng)行為來(lái)分析用戶與好友的關(guān)系，從話題層面來(lái)定義關(guān)系，提出度量這種關(guān)系強(qiáng)弱的方法；(2)在互動(dòng)關(guān)系中引入時(shí)間因素，提出互動(dòng)關(guān)系的時(shí)間衰減模型，更有效地模擬真實(shí)的用戶關(guān)系發(fā)展情況；(3)在推薦模型中引入關(guān)系的話題分布作為特征，與用戶興趣特征及微博內(nèi)容特征融合在一起，改進(jìn)推薦模型的效果。實(shí)驗(yàn)效果表明，這種分析用戶關(guān)系的方法，從話題層面上有效解釋了微博用戶的關(guān)系與行為，不僅能有效提高推薦的效果，也能為推薦結(jié)果提供更明確的可解釋性。

本文后續(xù)內(nèi)容安排如下: 第二節(jié)主要介紹傳統(tǒng)的推薦方法及社會(huì)化推薦的相關(guān)研究進(jìn)展；第三節(jié)闡述用戶互動(dòng)關(guān)系的定義，及在此基礎(chǔ)上提出的推薦模型；第四節(jié)展示在新浪微博數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)結(jié)果，并對(duì)結(jié)果進(jìn)行比較分析；第五節(jié)是本文結(jié)論及未來(lái)工作。

2 相關(guān)工作

傳統(tǒng)的推薦方法主要分為兩種，基于記憶的方法和基于模型的方法，通過(guò)挖掘用戶的歷史行為來(lái)分析出用戶的興趣，從而為用戶推薦可能感興趣的物品。協(xié)同過(guò)濾的基本假設(shè)是不同的用戶具有不同的興趣，從而對(duì)物品產(chǎn)生不同的喜好，如果兩個(gè)用戶都喜歡同一組物品，則說(shuō)明這兩個(gè)用戶具有相似的興趣，從而被稱為“鄰居”，鄰居的喜好物品成為用戶可能感興趣的物品。

隨著社交網(wǎng)絡(luò)的發(fā)展，越來(lái)越多的因素被應(yīng)用于推薦系統(tǒng)中。很多研究者對(duì)用戶關(guān)系在推薦中的應(yīng)用做了探索，例如，在推薦中考慮用戶好友關(guān)系、用戶信任關(guān)系等，并提出了較好的模型及方法。Sinha[5]在三組書(shū)籍和電影數(shù)據(jù)集中做了推薦效果的評(píng)估實(shí)驗(yàn)，分別為用戶提供來(lái)自好友和來(lái)自系統(tǒng)的推薦物品，用于比較系統(tǒng)推薦和好友推薦對(duì)用戶的影響，實(shí)驗(yàn)結(jié)果表明來(lái)自好友的推薦相對(duì)于傳統(tǒng)的推薦系統(tǒng)而言，通常會(huì)具有更高的質(zhì)量，說(shuō)明用戶的好友關(guān)系在推薦中具有很強(qiáng)的影響力，如何在推薦中引入好友關(guān)系已經(jīng)成為研究的重要方向。

Konstas[1]利用用戶的好友關(guān)系及社會(huì)化標(biāo)簽信息，構(gòu)建了社交關(guān)系圖模型，并提出了一種隨機(jī)游走模型RWR，來(lái)整合用戶好友關(guān)系及社會(huì)化標(biāo)簽，從而有效提高了推薦的效果。Ma[2]提出一種概率矩陣分解模型SoRec，通過(guò)將用戶社交關(guān)系和用戶打分記錄映射到同一個(gè)隱含特征空間上，來(lái)整合用戶的社交關(guān)系及打分記錄，從而緩解數(shù)據(jù)稀疏性問(wèn)題，并提高推薦精度。Mohsen[3]在此基礎(chǔ)上更進(jìn)一步，提出SocialMF模型，每個(gè)用戶的隱特征空間都受到其鄰居的影響，從而引入了用戶的信任關(guān)系傳導(dǎo)。Peng[6]利用排序?qū)W習(xí)，整合了用戶社交關(guān)系的特征來(lái)進(jìn)行用戶推薦，Chen[4]提出了基于協(xié)同排序來(lái)進(jìn)行微博內(nèi)容推薦的方法，融合了多種特征，包括微博內(nèi)容話題、內(nèi)容質(zhì)量、用戶社交關(guān)系以及作者影響力等因素，其中用戶關(guān)系主要包括共同好友數(shù)量、相互關(guān)注等。

由于很多情況下，用戶沒(méi)有明顯的好友關(guān)系，所以很多研究者從用戶的評(píng)分?jǐn)?shù)據(jù)出發(fā)，來(lái)評(píng)估用戶之間可能的關(guān)系。Pitsilis[7-8]提出基于用戶評(píng)分差異度的用戶信任關(guān)系計(jì)量方法，該方法通過(guò)對(duì)用戶A與用戶B在所有評(píng)分交集上的誤差絕對(duì)值求和，來(lái)計(jì)算用戶之間的信任度。Donovan[9]提出根據(jù)評(píng)分錯(cuò)誤比例進(jìn)行計(jì)算的方法，首先定義了用戶之間評(píng)分的正確性評(píng)估方法，通過(guò)設(shè)定誤差的閾值，將用戶在同一物品上的評(píng)分劃分為正確和不正確的二值問(wèn)題，然后通過(guò)評(píng)估正確評(píng)分的比例來(lái)計(jì)算用戶之間的信任度。Lathia[10]擴(kuò)展了該方法，并提出非二值性的評(píng)判方法，他引入誤差懲罰因子，用戶之間的信任度由評(píng)分值的均值計(jì)算得到。

然而這些研究大都集中在用戶關(guān)系的定義和使用方面，通過(guò)直接的用戶關(guān)系或間接計(jì)算的用戶關(guān)系，來(lái)改進(jìn)推薦效果，但對(duì)于用戶關(guān)系本身未作更深入的研究。例如，用戶A雖然關(guān)注了好友B，但并非會(huì)對(duì)B發(fā)布的所有消息都感興趣，從用戶的轉(zhuǎn)發(fā)行為上尤其可以看出這種傾向，本文從這點(diǎn)出發(fā)，首次提出基于用戶關(guān)系話題分布的推薦方法。

Yang[11]與我們的工作比較接近，他在Epinion數(shù)據(jù)集上利用用戶興趣的類別來(lái)劃分用戶的好友圈，提出了基于興趣圈子的推薦方法，從而實(shí)現(xiàn)在已知物品類別屬性的情況下，尋找與用戶具有相似興趣的好友來(lái)改善推薦效果。但這個(gè)工作是在固定的物品類別信息上進(jìn)行的，有較強(qiáng)的局限性，而且在微博中并沒(méi)有類別信息可以直接利用。

本文主要從微博用戶的行為出發(fā)，分析用戶與好友互動(dòng)行為的內(nèi)容在話題上的分布，以此來(lái)重新定義用戶的好友關(guān)系。本文認(rèn)為用戶與好友的關(guān)系建立在共同話題的基礎(chǔ)上，并且在不同的話題上具有不同的關(guān)系強(qiáng)弱度，從而提出基于用戶關(guān)系話題分布的推薦模型，此模型能夠更好地契合微博環(huán)境，更深層次地解釋用戶關(guān)系，并提供較好的微博內(nèi)容推薦結(jié)果。

3 本文工作

在微博中，用戶之間最直接的關(guān)系就是社交關(guān)系，包括關(guān)注以及由相互關(guān)注所建立的好友關(guān)系。大多數(shù)基于用戶關(guān)系的研究都集中在這個(gè)方面。然而，用戶在使用微博的過(guò)程中，不斷地制造內(nèi)容、消費(fèi)內(nèi)容，通過(guò)這些行為，用戶與其好友之間建立起了更深層次的互動(dòng)關(guān)系。這些行為的數(shù)量及內(nèi)容都為用戶的好友關(guān)系提供了更多的信息，對(duì)微博的個(gè)性化推薦非常有價(jià)值。本文從這個(gè)角度出發(fā)，從用戶的行為數(shù)據(jù)中挖掘用戶深層次關(guān)系，并融入到微博推薦模型中來(lái)。

3.1 互動(dòng)關(guān)系建模3.1.1 互動(dòng)關(guān)系的話題模型

本文在微博語(yǔ)料環(huán)境下，假設(shè)用戶對(duì)微博的興趣都是基于對(duì)話題本身的興趣，將微博的隱含話題作為隱參數(shù)來(lái)進(jìn)行推薦預(yù)測(cè)。不同于以往其他的社會(huì)化推薦模型，本文認(rèn)為用戶在轉(zhuǎn)發(fā)微博的行為中，除了考慮微博本身的話題因素以外，對(duì)微博的作者也有考慮。有一些研究試圖分析過(guò)類似因素，包括作者影響力、用戶與作者的好友關(guān)系等，本文則主要從用戶與好友的互動(dòng)行為上來(lái)分析用戶的關(guān)系，本文認(rèn)為用戶之間的關(guān)系有其本身的動(dòng)機(jī)，用戶對(duì)好友的關(guān)系是建立在話題基礎(chǔ)上的，而表現(xiàn)出來(lái)的現(xiàn)象就是在特定話題上，用戶通常會(huì)選擇性地轉(zhuǎn)發(fā)某些固定好友的消息，這也能解釋用戶更傾向于轉(zhuǎn)發(fā)已轉(zhuǎn)發(fā)過(guò)的好友的內(nèi)容這個(gè)現(xiàn)象。如圖1所示，是用戶互動(dòng)關(guān)系的圖模型表示。

圖1 用戶互動(dòng)關(guān)系話題圖模型

如圖1所示，對(duì)于每一對(duì)互動(dòng)關(guān)系r1，2，其在話題上的分布θ～Dirichlet(α)，詞語(yǔ)到話題的分布φ～Dirichlet(β)，從而可以將關(guān)系到話題的分布表示為詞語(yǔ)到話題分布的混合。以zi,j表示用戶關(guān)系的話題分布，其計(jì)算式如式(1)所示。

(1)

其中，W是關(guān)系ri,j的內(nèi)容中包含的所有詞項(xiàng)。zi,j∈Rk是k維特征向量，代表著用戶互動(dòng)關(guān)系的話題分布特征向量。

另外，由于微博的短文本特點(diǎn)，直接利用LDA模型來(lái)計(jì)算話題分布，往往效果不佳。本文采用Hong[12]提出的USER scheme方法對(duì)微博內(nèi)容進(jìn)行處理，從而訓(xùn)練LDA模型，步驟如下：

(1) 對(duì)訓(xùn)練集中所有的微博按照作者進(jìn)行整合，將每個(gè)用戶發(fā)表的全部微博表示為單篇文檔u-profile，所有用戶的u-profile構(gòu)成了訓(xùn)練語(yǔ)料集；

(2) 對(duì)整合后的語(yǔ)料集進(jìn)行LDA模型訓(xùn)練；

(3) 訓(xùn)練集中所有的轉(zhuǎn)發(fā)微博，每個(gè)用戶與微博的原作者構(gòu)成一個(gè)關(guān)系對(duì)r，按照r將所有訓(xùn)練數(shù)據(jù)整合為r-profile；

(4) 將訓(xùn)練集中所有的單條微博、測(cè)試集中所有的單條微博及根據(jù)關(guān)系對(duì)r整合的r-profile數(shù)據(jù)作為新文檔，利用訓(xùn)練得到的模型，來(lái)處理這些文檔，獲取每個(gè)新文檔話題分布；

(5) 每個(gè)r-profile文檔的話題分布即為關(guān)系對(duì)r的話題分布；

這種方法有幾個(gè)好處，首先，合并后的單篇文檔的內(nèi)容變得較為豐富，能提高模型的準(zhǔn)確性；另外，整合后文檔數(shù)量大幅度減少，從而有效縮短了模型的訓(xùn)練時(shí)間；而且，整合之后每篇文檔都代表著一個(gè)作者的全部?jī)?nèi)容，從而文檔的話題分布也就代表著作者的興趣話題分布，而每個(gè)用戶的興趣話題數(shù)量相對(duì)而言規(guī)模較小，所以能夠在較小的話題規(guī)模上完成模型的訓(xùn)練。

3.1.2 互動(dòng)關(guān)系的強(qiáng)度

另一方面，根據(jù)本文對(duì)用戶關(guān)系的定義，關(guān)系本身將具有話題屬性，由于互動(dòng)內(nèi)容在各話題上的分布不同，所以用戶關(guān)系在各話題上的強(qiáng)弱也會(huì)有所區(qū)別，物理意義即為: 用戶對(duì)于好友在不同話題上的信任度不同。這可以解釋為用戶是由于某些共同興趣才與好友建立了關(guān)系，而不是對(duì)好友的所有話題都感興趣。

令微博d在話題tk上的概率分布表示為p(tk|d)，根據(jù)用戶j中被用戶i轉(zhuǎn)發(fā)過(guò)的微博，可以得到用戶i對(duì)用戶j在話題tk上的關(guān)系強(qiáng)弱度，其計(jì)算方法如式(2)所示。

(2)

其中，Di,j表示用戶i轉(zhuǎn)發(fā)過(guò)的用戶j的微博集合，Dj表示用戶j發(fā)表的全部微博集合。τi,j(tk)代表著在用戶互動(dòng)關(guān)系的每一維話題特征上的互動(dòng)關(guān)系權(quán)重。

3.1.3 時(shí)間因素

由于用戶的互動(dòng)行為存在時(shí)間因素，這也從另一方面反映出用戶關(guān)系的時(shí)效性，本文假設(shè)用戶傾向于信任時(shí)間上較近的好友，我們給互動(dòng)關(guān)系的強(qiáng)度引入了簡(jiǎn)單的隨時(shí)間指數(shù)衰減的變量，具體計(jì)算方法如式(3)所示。

(3)

其中，β是調(diào)整關(guān)系強(qiáng)弱隨時(shí)間衰減速度的參數(shù)，隨著時(shí)間的增加，用戶與好友的每條交互歷史所帶來(lái)的權(quán)重將逐漸減弱，通過(guò)衰減函數(shù)，能夠使交互時(shí)間較新的好友獲得更強(qiáng)的關(guān)系權(quán)重。

3.2 IBCF推薦模型

通過(guò)上述的用戶關(guān)系分析，我們獲得了用戶與好友互動(dòng)關(guān)系的話題分布，以及在不同話題維度上的關(guān)系強(qiáng)弱度權(quán)重。接下來(lái)，本文在RSVD模型[13]的基礎(chǔ)上，融合了用戶互動(dòng)關(guān)系的這些特性，提出改進(jìn)的推薦模型。

RSVD模型是經(jīng)典的矩陣分解模型，有效融合了用戶和物品的偏置信息，式(4)給出了模型的計(jì)算方法。

(4)

本文將互動(dòng)關(guān)系的話題特征z作為隱性特征加入模型中，并為每一維話題特征引入權(quán)重因子τ，提出了基于用戶互動(dòng)關(guān)系的協(xié)同過(guò)濾模型 (Interaction-Based Collaborative Filtering)，以下簡(jiǎn)稱為IBCF模型，如式(5)所示。

(5)

為了將互動(dòng)關(guān)系的話題分布及關(guān)系強(qiáng)度融合起來(lái)，我們將用戶i對(duì)用戶j的互動(dòng)關(guān)系在所有話題上的強(qiáng)弱度表示為k×k對(duì)角矩陣，如式(6)所示。

(6)

其中，τi,j(tk)代表著在互動(dòng)關(guān)系ri,j在話題tk上的權(quán)重值。這樣通過(guò)εu,vzu,v的計(jì)算，能夠得到帶有權(quán)重的互動(dòng)關(guān)系的話題向量，即εu,vzu,v∈Rk，以此為用戶關(guān)系的話題特征向量。

3.4 最終模型

本文在進(jìn)行LDA模型訓(xùn)練的過(guò)程中，已經(jīng)根據(jù)u-profile和微博內(nèi)容得到了用戶的興趣話題分布及微博內(nèi)容的話題分布，在此處可以將它們作為顯性特征加入到模型的偏置中，從而得到最終的模型如式(7)所示。

(7)

其中，zu,zi∈Rk，分別代表用戶u和微博i的k維話題特征，bk(u)和bk(i)是它們的偏置參數(shù)，通過(guò)訓(xùn)練得到。

4 實(shí)驗(yàn)分析

4.1 數(shù)據(jù)集

本文的實(shí)驗(yàn)數(shù)據(jù)采集自新浪微博，由Zhang[14]提供，首先隨機(jī)挑選了100個(gè)用戶作為種子用戶，然后采集他們的關(guān)注用戶，以此類推進(jìn)行迭代采集，每個(gè)用戶采集他們最近發(fā)表的1 000條微博內(nèi)容。隨后，本文依照表1的條件對(duì)用戶進(jìn)行了篩選，選擇活躍的普通用戶，具體篩選條件如表1所示。

根據(jù)這些條件，經(jīng)過(guò)合并去重，我們挑選出538個(gè)用戶及26 271個(gè)關(guān)注好友，將這些用戶及他們關(guān)注的好友所發(fā)表的全部微博內(nèi)容作為整體數(shù)據(jù)集，其中，每個(gè)用戶關(guān)注好友的微博構(gòu)成了該用戶的瀏覽數(shù)據(jù)集。

表1 用戶篩選條件

另外，在構(gòu)建實(shí)驗(yàn)數(shù)據(jù)集的過(guò)程中，本文對(duì)微博內(nèi)容進(jìn)行了一些處理。

1) 擴(kuò)充微博內(nèi)容，將轉(zhuǎn)發(fā)的原文內(nèi)容與用戶轉(zhuǎn)發(fā)時(shí)的說(shuō)明進(jìn)行合并；

2) 過(guò)濾掉微博中包含的鏈接、@好友昵稱、標(biāo)點(diǎn)符號(hào)、停用詞等。

經(jīng)過(guò)這些處理，使得微博內(nèi)容能夠保持為高質(zhì)量的文本內(nèi)容。

為了構(gòu)建訓(xùn)練集和測(cè)試集，需要對(duì)微博進(jìn)行正負(fù)例標(biāo)記，在實(shí)驗(yàn)中，本文與Chen[4]、Yan[15]保持一致，將用戶對(duì)微博的打分考慮為二值情況，以用戶轉(zhuǎn)發(fā)過(guò)的微博作為正例，未轉(zhuǎn)發(fā)的微博作為反例，則用戶對(duì)微博的打分ru,i的計(jì)算方法如式(8)所示。

(8)

在實(shí)驗(yàn)過(guò)程中，需要對(duì)原始數(shù)據(jù)集進(jìn)行切分，得到訓(xùn)練集、驗(yàn)證集和測(cè)試集，為了模擬用戶的微博時(shí)間線，本文主要通過(guò)計(jì)算出切分時(shí)間點(diǎn)來(lái)對(duì)數(shù)據(jù)集進(jìn)行切分，具體的做法是首先對(duì)原始數(shù)據(jù)集按照時(shí)間進(jìn)行排序，對(duì)選中的538個(gè)用戶，單獨(dú)統(tǒng)計(jì)每個(gè)用戶轉(zhuǎn)發(fā)微博的數(shù)量，按照1∶5的切分比例計(jì)算出每個(gè)用戶的切分時(shí)間點(diǎn)；再對(duì)每個(gè)用戶的好友微博集合按照該時(shí)間點(diǎn)進(jìn)行切分，從而實(shí)現(xiàn)在切分時(shí)間點(diǎn)之后的數(shù)據(jù)為測(cè)試集，切分時(shí)間點(diǎn)之前的數(shù)據(jù)作為訓(xùn)練集；最后再用同樣的方法從訓(xùn)練集中按1∶5的比例切分出驗(yàn)證集。

4.2 評(píng)價(jià)指標(biāo)

本文采用NDCG@n[16]和P@n以及MAP作為評(píng)價(jià)指標(biāo)，NDCG@n的計(jì)算如式(9)所示。

(9)

其中，U是測(cè)試集中所有用戶的集合，Nu表示用戶集合的大小，公式內(nèi)部第一個(gè)加和用來(lái)計(jì)算DCG的值，Zu表示對(duì)用戶u的完美排序結(jié)果的DCG值，用來(lái)進(jìn)行歸一化處理，外部第二個(gè)加和用來(lái)對(duì)各個(gè)用戶NDCG@n取平均值，從而得到最終的NDCG@n。

MAP的計(jì)算方法如式(10)所示。

(10)

其中，Iu是用戶u的推薦結(jié)果集中真正被u轉(zhuǎn)發(fā)過(guò)的微博集合，|Iu|表示該集合的大小，Piu是在i處的準(zhǔn)確率。

4.3 實(shí)驗(yàn)結(jié)果及分析

本文通過(guò)平方損失函數(shù)來(lái)評(píng)估算法的誤差，計(jì)算方法如式(11)所示。

(11)

其中S是存在評(píng)分的用戶-物品對(duì)集合。所以本文提出的IBCF模型其優(yōu)化目標(biāo)函數(shù)的計(jì)算公式如式(12)所示。

(12)

對(duì)以上損失函數(shù)，可以采用最小二乘法或梯度下降來(lái)求解參數(shù)。本文通過(guò)NelderMead方法[17]來(lái)訓(xùn)練步長(zhǎng)參數(shù)和正則化參數(shù)λ，實(shí)驗(yàn)過(guò)程中設(shè)定NelderMead的迭代次數(shù)為50次，在驗(yàn)證集來(lái)完成參數(shù)的訓(xùn)練，最后在測(cè)試集上用訓(xùn)練得到的參數(shù)進(jìn)行結(jié)果預(yù)測(cè)。

接下來(lái)，本文首先在驗(yàn)證集上分析了IBCF模型受話題數(shù)量和時(shí)間衰減參數(shù)的影響，然后在測(cè)試集上與其他模型進(jìn)行了最終的結(jié)果對(duì)比。

話題個(gè)數(shù)影響

由于本文中用戶互動(dòng)關(guān)系的話題特征數(shù)量直接與LDA話題數(shù)量的設(shè)定有關(guān)，所以我們?cè)隍?yàn)證集上評(píng)估了IBCF模型在不同話題數(shù)量上的表現(xiàn)，如圖2所示。 橫坐標(biāo)是話題的數(shù)量，縱坐標(biāo)是IBCF模型在指標(biāo)MAP上的值，從圖中可以看出話題數(shù)量過(guò)少時(shí)，由于話題的表現(xiàn)不明顯，導(dǎo)致模型效果很差，當(dāng)話題數(shù)量到達(dá)50之后，能有較好的表現(xiàn)。

圖2 IBCF在不同話題數(shù)量下的MAP表現(xiàn)

另外，本文的互動(dòng)關(guān)系能從話題中得到直觀的解釋。以微博用戶“1073599852”為例，根據(jù)u-profile的話題分布，可以看到他的興趣主要集中在話題9、13、17上，然后根據(jù)r-profile計(jì)算得到的各話題上的聯(lián)系最緊密的好友，如表2所示。

如表2所示，是微博用戶“1073599852”在各話題上互動(dòng)最緊密的好友列表，左側(cè)WORD是話題的代表性詞匯，數(shù)值是其話題概率，右側(cè)FRIEND是在該話題上聯(lián)系最緊密的好友ID，數(shù)值是用戶和該好友在話題上的關(guān)系強(qiáng)弱?？梢钥吹?，在同一個(gè)話題上，不同的好友具有不同的關(guān)系強(qiáng)弱值。值得注意的是，可以看到有一些好友在各個(gè)話題上都有較強(qiáng)的關(guān)系，例如，好友1577826897、1630461754、1752543513等，其主要原因是用戶與這部分好友的互動(dòng)次數(shù)較高，遠(yuǎn)超過(guò)其他好友，從而使其在計(jì)算關(guān)系強(qiáng)度時(shí)具有較多的相關(guān)文檔，這也可以解釋為用戶聯(lián)系最緊密的好友在各個(gè)話題上相比于其他普通好友都會(huì)都有較高的關(guān)系權(quán)重，符合微博中的實(shí)際使用情況。而且根據(jù)我們的模型，即使其相對(duì)具有較高的關(guān)系權(quán)重，但在不同的話題上關(guān)系的強(qiáng)度值依然是有明顯差異的，從而有利于對(duì)不同的話題進(jìn)行區(qū)別對(duì)待。

衰減速度影響

本文考慮了互動(dòng)關(guān)系的時(shí)間因素，將互動(dòng)關(guān)系的強(qiáng)度定義成隨時(shí)間逐步衰減。在實(shí)驗(yàn)過(guò)程中，有兩個(gè)因素需要考慮: 首先是時(shí)間窗口的設(shè)定，用來(lái)控制模型的粒度；其次是參數(shù)β的調(diào)整，用來(lái)調(diào)節(jié)隨時(shí)間衰減的速度。

選擇合適的時(shí)間窗口直接關(guān)系到模型的粒度，時(shí)間窗口越短，計(jì)算的粒度就越小，時(shí)間敏感度也就越強(qiáng)。但并非越短越好，過(guò)短的時(shí)間窗口會(huì)導(dǎo)致計(jì)算量的急速增大，例如，選30分鐘為時(shí)間窗口長(zhǎng)度，則每隔30分鐘都需要重新計(jì)算微博的時(shí)間衰減值，而當(dāng)窗口長(zhǎng)度選擇為一天時(shí)，每天內(nèi)的微博時(shí)間衰減值一致。另外，從現(xiàn)實(shí)角度考慮，也可以看到微博中用戶與好友的關(guān)系應(yīng)當(dāng)是緩慢變化的過(guò)程，一段關(guān)系一般會(huì)維持較長(zhǎng)的時(shí)間。本文在實(shí)驗(yàn)中選擇以一天為時(shí)間窗口的長(zhǎng)度。

表2 用戶的話題表示及該話題上相關(guān)好友的關(guān)系強(qiáng)弱

另一方面，參數(shù)β調(diào)節(jié)著關(guān)系強(qiáng)度的衰減速度，由于本文假設(shè)用戶關(guān)系較為穩(wěn)定，隨時(shí)間的衰減較慢，所以需要將衰減速度控制在較小范圍內(nèi)。β的值與數(shù)據(jù)集聯(lián)系比較緊密，在本文實(shí)驗(yàn)中，由于選擇了以一天為時(shí)間窗口的長(zhǎng)度，則時(shí)間差的分布在1～365，所以在實(shí)驗(yàn)過(guò)程中，我們選取了較小的β值，測(cè)試了β值從0～0.02之間以0.001為步長(zhǎng)的20個(gè)數(shù)值，并在驗(yàn)證集上分析了IBCF在這些β值上的MAP表現(xiàn)，實(shí)驗(yàn)效果如圖3所示。

圖3 不同衰減參數(shù)下IBCF在MAP上的表現(xiàn)

從圖3中可以看到，在β值較小的情況下，IBCF模型表現(xiàn)較為穩(wěn)定，在β值接近0.02后效果有明顯下降，可能的原因是由于衰減過(guò)快，導(dǎo)致用戶關(guān)系強(qiáng)度比較弱，最終只有最近的幾個(gè)好友能產(chǎn)生明顯的互動(dòng)關(guān)系影響，有效的互動(dòng)歷史數(shù)據(jù)過(guò)于稀疏，從而使得模型效果有所下降。

模型效果比較

為了驗(yàn)證IBCF模型在微博推薦中的效果提升，本文將IBCF同以下幾個(gè)經(jīng)典模型進(jìn)行了實(shí)驗(yàn)比較。

(1) Item-based KNN: 基于共同打分項(xiàng)的經(jīng)典協(xié)同過(guò)濾模型，本文選用余弦相似度作為相似度的度量。

(2) LDA: 通過(guò)LDA模型計(jì)算每條微博的話題分布，然后根據(jù)用戶以往轉(zhuǎn)發(fā)微博與新微博的話題距離來(lái)計(jì)算用戶對(duì)新微博的興趣，計(jì)算方法如式(13)所示。

(13)

其中，Vu表示用戶u轉(zhuǎn)發(fā)的所有微博集合。

(3) RSVD: 考慮了偏置的SVD分解模型，能夠有效融合全局偏置、用戶偏置和物品偏置。

(4) SocialMF: 經(jīng)典的社會(huì)化推薦模型，在矩陣分解模型中引入了用戶社交關(guān)系，并考慮了用戶關(guān)系的傳遞。

這些模型在測(cè)試集上的表現(xiàn)如圖4所示。左側(cè)是各模型在P@n及MAP指標(biāo)上的表現(xiàn)，右側(cè)是在NDCG指標(biāo)上的表現(xiàn)，可以看出基于共同打分項(xiàng)的Item-based KNN算法表現(xiàn)較差，主要原因應(yīng)該在于微博中數(shù)據(jù)極其稀疏，大多數(shù)微博內(nèi)容都只有很少的轉(zhuǎn)發(fā)，從而導(dǎo)致共同打分項(xiàng)數(shù)據(jù)較少。LDA模型由于考慮了微博的內(nèi)容話題，推薦精度有所提高，RSVD通過(guò)矩陣分解使得MAP達(dá)到0.3259，SocialMF模型由于融合了用戶的社交關(guān)系，其表現(xiàn)相對(duì)較好，MAP指標(biāo)達(dá)到了0.3973。相比之下，本文提出的IBCF模型在矩陣分解模型的基礎(chǔ)上，融合了用戶互動(dòng)關(guān)系的話題特征、內(nèi)容特征、用戶興趣特征，在MAP指標(biāo)上達(dá)到了0.4758，相比于傳統(tǒng)的RSVD矩陣分解模型提高了45.99%，相比于基于用戶社交關(guān)系的SocialMF模型也提高了19.75%。另外從NDCG指標(biāo)表現(xiàn)上也可以看出IBCF模型相對(duì)于其他模型具有更好的表現(xiàn)。

圖4 IBCF模型與各模型推薦結(jié)果比較

5 總結(jié)和展望

本文主要研究了微博用戶的互動(dòng)行為在話題上的分布，提出了話題相關(guān)的用戶互動(dòng)關(guān)系的度量方法，并將此方法應(yīng)用到微博推薦中，提出基于互動(dòng)話題的微博推薦模型IBCF。實(shí)驗(yàn)結(jié)果表明，通過(guò)挖掘用戶好友的關(guān)系話題，IBCF模型能較好地提高微博推薦的效果。

從實(shí)驗(yàn)結(jié)果中，可以說(shuō)明本文提出的基于用戶互動(dòng)關(guān)系話題特征的推薦模型IBCF能夠有效提高社會(huì)化推薦模型的精度。這個(gè)結(jié)果也驗(yàn)證了用戶互動(dòng)關(guān)系在社交網(wǎng)絡(luò)中的重要性，因?yàn)榛?dòng)的行為能更準(zhǔn)確地反映出用戶與好友的共同興趣。

本文接下來(lái)的主要工作是考慮將互動(dòng)關(guān)系和用戶社交關(guān)系融合起來(lái)，進(jìn)一步提高推薦效果。

[1] Konstas I,Stathopoulos V,Jose J M. On social networks and collaborative recommendation[C]//Proceedings of the 32nd international ACM SIGIR conference on research and development in information retrieval. ACM,2009: 195-202.

[2] Ma H,Yang H,Lyu M R,et al. Sorec: social recommendation using probabilistic matrix factorization[C]//Proceedings of the 17th ACM conference on information and knowledge management. ACM,2008: 931-940.

[3] Jamali M,Ester M. A matrix factorization technique with trust propagation for recommendation in social networks[C]//Proceedings of the 4th ACM conference on recommender systems. ACM,2010: 135-142.

[4] Chen K,Chen T,Zheng G,et al. Collaborative personalized tweet recommendation[C]//Proceedings of the 35th international ACM SIGIR conference on research and development in information retrieval. ACM,2012: 661-670.

[5] Sinha R R,Swearingen K. Comparing Recommendations Made by Online Systems and Friends[C]//Proceedings of DELOS workshop: personalisation and recommender systems in digital libraries. 2001: 106.

[6] 彭澤環(huán),孫樂(lè),韓先培. 基于排序?qū)W習(xí)的微博用戶推薦[J]. 中文信息學(xué)報(bào),2013,27(4): 96-102.

[7] Pitsilis G,Marshall L F. A model of trust derivation from evidence for use in recommendation systems[M]. University of Newcastle upon Tyne,Computing Science,2004.

[8] Pitsilis G,Marshall L. Trust as a key to improving recommendation systems[M]. Springer,2005.

[9] O’Donovan J,Smyth B. Trust in recommender systems[C]//Proceedings of the 10th international conference on intelligent user interfaces. ACM,2005: 167-174.

[10] Lathia N,Hailes S,Capra L. Trust-based collaborative filtering[M]//Trust Management II. Springer US,2008: 119-134.

[11] Yang X,Steck H,Liu Y. Circle-based recommendation in online social networks[C]//Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining. ACM,2012: 1267-1275.

[12] Hong L,Davison B D. Empirical study of topic modeling in twitter[C]//Proceedings of the First Workshop on Social Media Analytics. ACM,2010: 80-88.

[13] Paterek A. Improving regularized singular value decomposition for collaborative filtering[C]//Proceedings of KDD cup and workshop. 2007,2007: 5-8.

[14] Zhang J,Liu B,Tang J,et al. Social influence locality for modeling retweeting behaviors[J]. IJCAI’13,2013.

[15] Yan R,Lapata M,Li X. Tweet recommendation with graph co-ranking[C]//Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Long Papers-Volume 1. Association for Computational Linguistics,2012: 516-525.

[16] J?rvelin K,Kek?l?inen J. Cumulated gain-based evaluation of IR techniques[J]. ACM Transactions on Information Systems (TOIS),2002,20(4): 422-446.

[17] Lagarias J C,Reeds J A,Wright M H,et al. Convergence properties of the Nelder--Mead simplex method in low dimensions[J]. SIAM Journal on Optimization,1998,9(1): 112-147.

A User Interaction Topic Based Microblog Recommendation Algorithm

LU Xiao1,2，LI Peng3，WANG Bin3,LI Yingbo1,FANG Jing1

(1. National Computer Network Emergency Response Technical Team/CoordinationCenter of China, Beijing 100029，China；2. University of Chinese Academy of Sciences，Beijing 100049，China；3. Institute of Information Engineering，Chinese Academy of Sciences，Beijing 100093，China)

In contrast to the existing social relationship based micorblog recommendation,this paper analyzes the topic level of user interaction,and proposes a new method to measure the strength of this relationship. We infer the topic of the interaction relationship,and propose IBCF as an improved microblog recommendation model. Experimental results show that,compared with the current popular social recommendation methods,the proposed method performs better according to MAP and NDCG,generating more reasonable recommended results.

interaction relationship,Interaction topic,social recommendation,collaborative filtering,microblog recommendation

魯驍(1986—)，博士，工程師，主要研究領(lǐng)域?yàn)樾畔z索、個(gè)性化推薦。E?mail：luxiao@cert．gov．cn李鵬(1985—)，博士，助理研究員，主要研究領(lǐng)域?yàn)樾畔z索、社交網(wǎng)絡(luò)分析。E?mail：lipeng@iie．a(chǎn)c．cn王斌(1972—)，博士，研究員，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)樾畔z索。E?mail：wangbin@iie．a(chǎn)c．cn

2013-02-17 定稿日期： 2014-03-31

國(guó)家自然科學(xué)基金青年基金(61402466)

1003-0077(2016)03-0187-09

TP391

A