基于超圖隨機游走標(biāo)簽擴充的微博推薦方法?

馬慧芳 , 張 迪 , 趙衛(wèi)中 , 史忠植

1(西北師范大學(xué) 計算機科學(xué)與工程學(xué)院,甘肅 蘭州 730070)

2(廣西可信軟件重點實驗室(桂林電子科技大學(xué)),廣西 桂林 541004)

3(華中師范大學(xué) 計算機學(xué)院,湖北 武漢 430079)

4(中國科學(xué)院 計算技術(shù)研究所 智能信息處理重點實驗室,北京 100190)

隨著網(wǎng)絡(luò)的普及發(fā)展和電子產(chǎn)品的不斷更新,全球互聯(lián)網(wǎng)已進入互聯(lián)互通的春天.在網(wǎng)絡(luò)融合的背景下,以微博為代表的各種新技術(shù)、新應(yīng)用相繼涌現(xiàn),其通過文字、圖片、視頻等多媒體形式實現(xiàn)信息發(fā)布、互動交流,兼具社交屬性與媒體屬性,快速聚集了龐大的用戶群體.這些社交應(yīng)用的發(fā)展給人們生產(chǎn)生活方式以及信息傳播途徑都帶來了翻天覆地的變化.

微博平臺中的內(nèi)容涉及很多方面,從用戶的日常生活到國內(nèi)外的時事新聞,且微博用戶數(shù)量龐大,每分鐘就有幾十萬條微博發(fā)出,微博已經(jīng)成為人們?nèi)粘Ｉ钪胁豢扇鄙俚男畔碓春徒涣髌脚_,它是Web 2.0 的一個重要組成部分.微博具有兩個典型的特點.

?第一,它能夠被所有的網(wǎng)絡(luò)用戶創(chuàng)建,這些用戶不分背景、身份,都可以創(chuàng)建自己的微博.例如,工人、學(xué)生、教師等各行各業(yè)的人都可以參與進來,發(fā)表自己的微博.

?其次,微博用戶發(fā)表的內(nèi)容質(zhì)量參差不齊,描述語言豐富多彩,有書面的、口語的以及時下流行的網(wǎng)絡(luò)語言.而這些用戶產(chǎn)生的大量信息中可能含有高質(zhì)量的內(nèi)容,也可能含有低質(zhì)量的垃圾信息[1].

通常情況下,微博平臺使用時間線排序的方式向微博用戶展示其關(guān)注用戶的信息流,即將用戶關(guān)注的最新信息展示在個人信息頁面的最頂部.用戶要想遍歷微博信息并且從中獲取自己需要的信息,不但需要花費大量的時間,而且還不一定能夠找到自己感興趣的內(nèi)容,隨之產(chǎn)生的問題就是用戶體驗下降、用戶流失等.因而,如何從海量的微博數(shù)據(jù)中挖掘出用戶感興趣的內(nèi)容并精準地推薦給目標(biāo)用戶,已經(jīng)成為微博推薦相關(guān)研究的熱點.

本文提出一種新的微博推薦框架,以向微博用戶推薦高質(zhì)量的微博.該框架包括微博用戶標(biāo)簽擴充、微博用戶興趣建模以及微博推薦這3 部分:微博用戶標(biāo)簽擴充的目的是抽取用戶微博文本中的關(guān)鍵詞,增加用戶標(biāo)簽數(shù)量,這些標(biāo)簽可以用來為用戶推薦高質(zhì)量的微博;微博用戶興趣建模的目的是為了使系統(tǒng)“在對的時間以對的方式做對的事情”,也就是為了給用戶帶來最好的體驗[2].

本文的貢獻有以下幾點.

(1)提出了一種微博標(biāo)簽擴充方案.該方案將微博視為超邊,微博中的詞視為超點構(gòu)建超圖,并對超邊和超點進行加權(quán),通過在超圖上隨機游走,得到一定數(shù)量的關(guān)鍵詞對微博用戶標(biāo)簽進行擴充.

(2)設(shè)計了一種微博用戶興趣表示模型,采用相關(guān)性標(biāo)簽權(quán)重加權(quán)方案,構(gòu)建用戶-標(biāo)簽矩陣,利用標(biāo)簽之間的概率相關(guān)性,構(gòu)造標(biāo)簽相似性矩陣對用戶-標(biāo)簽矩陣更新,解決了用戶標(biāo)簽矩陣稀疏的問題.

(3)利用真實數(shù)據(jù)集驗證了所提出的微博推薦方法的有效性和高效性.

本文在第1 節(jié)介紹相關(guān)工作,包括微博用戶興趣模型以及微博個性化推薦的相關(guān)理論技術(shù).第2 節(jié)介紹本文提出的基于超圖隨機游走標(biāo)簽擴充的方法.第3 節(jié)介紹本文提出的基于標(biāo)簽概率相關(guān)性的微博推薦方法.第4節(jié)中,通過實驗數(shù)據(jù)集來驗證算法的性能.最后總結(jié)全文,并對未來的研究方向進行展望.

1 相關(guān)工作

實現(xiàn)微博個性化的信息推薦[3-5],理解用戶的興趣或需求是前提和關(guān)鍵.目前,在微博背景下發(fā)掘用戶興趣模型已經(jīng)有了一些研究工作,一部分研究人員從微博用戶發(fā)布的微博內(nèi)容中抽取若干個代表用戶個性化特征的關(guān)鍵詞作為對用戶興趣愛好的描述[6,7].由于微博內(nèi)容形式多樣,既有即時所見所聞的情感表達,又有轉(zhuǎn)發(fā)的新聞時事,導(dǎo)致微博內(nèi)容具有隨意性、碎片化等特點.以上方法提取的關(guān)鍵詞并不能很好地表征用戶的興趣愛好.另一部分研究人員利用外部知識庫對微博語義進行擴充[8,9],之后引入概率主題模型,更好地表達文本的語義.還有一部分研究人員將用戶所發(fā)的微博整合成一個長的文本文檔,然后利用潛在狄利克雷分配模型發(fā)現(xiàn)用戶潛在的興趣[10].這種方法雖然在實際應(yīng)用中能夠有效地向用戶推薦微博,但是仍然不能滿足用戶的個性化需求.

然而,以上這些方法僅僅考慮了從微博文本的角度挖掘用戶興趣,事實上,除了微博內(nèi)容能夠反映用戶興趣外,用戶自己標(biāo)注的個性化標(biāo)簽也能體現(xiàn)用戶的喜好特征.標(biāo)簽是用戶綜合自己的工作性質(zhì)、年齡群體以及興趣愛好等因素的關(guān)鍵詞集合,涵蓋了豐富且價值很大的信息,其對表征用戶用戶興趣特點和關(guān)注領(lǐng)域具有不可估量的作用.然而,現(xiàn)有關(guān)于微博用戶標(biāo)簽的研究相對較少.已有的工作僅僅只是針對用戶標(biāo)注標(biāo)簽的行為[11],標(biāo)簽內(nèi)容的特點以及標(biāo)簽與其他用戶信息(如微博內(nèi)容、關(guān)注關(guān)系)之間的聯(lián)系進行研究[12].針對微博推薦的研究,盡管已有研究者采用標(biāo)簽來進行微博推薦[13-15],但是卻并未充分考慮利用微博內(nèi)容對用戶標(biāo)簽進行擴充,更是很少有人將之與標(biāo)簽間的概率相關(guān)性結(jié)合進行微博推薦,而這將是本文所研究的主要問題.

基于對以上研究的分析可知,要想更加準確地研究個性化微博推薦,必須將微博內(nèi)容與用戶標(biāo)簽進行結(jié)合.本文提出一種結(jié)合超圖隨機游走標(biāo)簽擴充與標(biāo)簽概率相關(guān)性的微博推薦方法.具體來說,首先,該方法將微博視為超邊,微博中的詞視為超點來構(gòu)建超圖,通過在超圖上隨機游走,得到一定數(shù)量的關(guān)鍵詞對用戶標(biāo)簽進行擴充;然后采用相關(guān)性標(biāo)簽權(quán)重加權(quán)方案,構(gòu)建用戶-標(biāo)簽矩陣,利用標(biāo)簽之間的概率相關(guān)性,構(gòu)造標(biāo)簽相似性矩陣對用戶-標(biāo)簽矩陣更新.上述方法有效解決了用戶標(biāo)簽矩陣的稀疏問題,不僅使更新后的矩陣包含了微博用戶的興趣信息,而且還融合了標(biāo)簽標(biāo)簽間的相關(guān)性關(guān)系,如圖1 所示.與未考慮微博內(nèi)容和標(biāo)簽與標(biāo)簽關(guān)系的推薦算法相比,本文提出的微博用戶興趣表示模型更能表征用戶的興趣特征,微博推薦性能得到提升.

Fig.1 Research framework for microblog recommendation based on tag extension and tag probability correlation圖1 基于標(biāo)簽擴充與標(biāo)簽概率相關(guān)性的微博推薦研究框架

2 基于超圖隨機游走的標(biāo)簽擴充

超圖學(xué)習(xí)是對普通圖學(xué)習(xí)的泛化和擴展,在超圖中一條邊可以包含任意數(shù)量的頂點,則超邊是一條包含該超邊中所有頂點的簡單閉合曲線.因而相對于普通圖而言,超圖具備描述多元關(guān)系的能力,這使得超圖具有更好的性能表現(xiàn).假設(shè)V=(v1,v2,…,vn)是一個有限集,ei≠?(i=1,2,…,m)和,則稱HG(V,E)是一個普通超圖,其中,V中的元素v1,v2,…,vn稱為超圖的頂點,即超點;E={e1,e2,…,ei,…,em}為超圖的邊集合,E中的元素ei={vi1,vi2,…,vij}(1≤j≤n)稱為超圖HG(V,E)中的超邊.一個普通超圖可以用指示矩陣H|V|×|E|來表示.若v∈e,矩陣中的元素h(v,e)=1;否則,h(v,e)=0.從定義可知,當(dāng)且僅當(dāng)超邊E中的任一超邊e包含2 個節(jié)點時,普通超圖將退化為普通圖,故可將普通圖看作是超圖的特例.

本文所提出的基于超圖隨機游走的微博關(guān)鍵詞提取算法,首先,根據(jù)微博用戶所發(fā)布的微博內(nèi)容為每一個微博用戶都構(gòu)建一個超圖;其次,從微博的時間因子和微博的人氣指數(shù)這兩方面對超邊加權(quán),通過詞語之間的關(guān)聯(lián)度以及詞語在特定微博下的共現(xiàn)距離對超點加權(quán).在構(gòu)建超圖模型的過程中,超邊是不同的微博文本,超點是微博中不同詞語.本質(zhì)上,該模型將每一篇微博視為一個由不同關(guān)鍵詞所組成的詞袋模型.而這些微博的集合即為本文所定義的詞匯超圖.

2.1 加權(quán)超圖模型的構(gòu)建

給定微博用戶集合U={u1,u2,…,ui,…,uN},N為用戶的個數(shù).用戶ui所發(fā)布的微博集合為,Mi為用戶ui所發(fā)布的微博個數(shù).其中,1≤i≤N,則所有用戶發(fā)布的微博集合為;用戶ui的微博集合Di中的詞集為mi為詞集Li中詞語的個數(shù)且mi>>Mi,則所有用戶的微博詞語集合為;Di進一步被劃分為;Li進一步被劃分為,它們分別與相對應(yīng).本文標(biāo)簽擴充和用戶興趣建模這兩個部分都是在上進行,而微博推薦部分則是在上進行.

設(shè)WHG(V,E,w(e),w(vi,ei))為一個加權(quán)超圖,其中,w(e):e→R+代表超邊e的權(quán)重,w(vi,ei):(vi,ei)→R+代表超點vi在特定超邊ei上的權(quán)重.一個帶權(quán)重的超圖指示矩陣Hw|V|×|E|中的元素定義如下.

在加權(quán)超圖中,超點的度d(v)與超邊的度d(e)定義如下.

超點的度被定義為其所在超邊權(quán)重的和,超邊的度被定義為在該超邊上所有超點的權(quán)重和.本節(jié)將詳細介紹對超邊和超點加權(quán)的具體策略.值得注意的是,下文中提及到的與e同義,皆代表某條特定的超邊.

2.1.1 超邊加權(quán)策略

對微博用戶而言,微博內(nèi)容所反映出的用戶興趣是隨著時間的變化而變化的.提出微博時間因子來表征隨著微博發(fā)表時間的增長,其內(nèi)容對用戶重要性的變化.則用戶ui的某一篇微博的時間因子如公式(4)所示.

其中,curtime是當(dāng)前時間,是微博的發(fā)布時間,表示用戶ui從發(fā)布第1 篇微博到目前的時間跨度.離當(dāng)前時間越近的微博,其時間因子越大,這條微博就越能表征用戶最近的興趣愛好.

Q是衰減率參數(shù),取值范圍為0

顯然,一篇微博的評論數(shù)、轉(zhuǎn)發(fā)數(shù)以及點贊數(shù)越多,這篇微博就越能體現(xiàn)微博用戶的興趣愛好.因此,提出微博人氣指數(shù)(microblog popularity index,簡稱MPI)來表征微博對用戶的重要程度.微博人氣指數(shù)由微博的評論數(shù)Scomment、微博的轉(zhuǎn)發(fā)數(shù)Sforward以及微博的被點贊數(shù)Slike等子屬性衡量,則用戶ui的某一篇微博的人氣指數(shù)如公式(5)所示.

其中,λ1～λ3分別表示相應(yīng)子屬性的權(quán)重比例.本文中,假定微博的評論數(shù)、轉(zhuǎn)發(fā)數(shù)和點贊數(shù)對微博來說同等重要,它們的和為1.

通過結(jié)合微博時間因子和微博人氣指數(shù)計算用戶ui的某篇微博的權(quán)重,如公式(6)所示.

其中,α為值域在(0,1)之間的平滑因子,用它來調(diào)節(jié)Ftime與MPI的比重.α的值越大,代表更注重微博的時效性;相反,則更注重微博的人氣指數(shù).后續(xù)實驗中,將通過分析α在不同取值下的實驗結(jié)果來確定α的值.最終的表示用戶某一條超邊的權(quán)重.

2.1.2 超點加權(quán)策略

在本文的超圖模型中,超點是微博文本中的不同詞語,通過計算詞語之間的共現(xiàn)度[16]、關(guān)聯(lián)度以及在特定微博中的共現(xiàn)距離對超點加權(quán).表1 為加權(quán)過程中所用到的符號定義.

Table 1 Notations used for hyper-vertex weighting表1 超點加權(quán)階段各符號的定義

公式(7)考慮了vi與vj的共現(xiàn)距離.其中,共現(xiàn)距離是詞語vi與vj共同出現(xiàn)時,中間間隔的詞語個數(shù);是vi與vj在微博中共現(xiàn)的次數(shù).

基于vi與vj的共現(xiàn)度co(vi,vj),可進一步求解vi與vj的關(guān)聯(lián)度.由于該關(guān)聯(lián)度是非對稱的,因此分別求解vi與vj的單邊關(guān)聯(lián)度,如公式(8)所示.

公式(9)可以求出vi的單邊關(guān)聯(lián)度,公式的前半部分體現(xiàn)了詞語vi出現(xiàn)時,詞語vj出現(xiàn)的概率.Nnei(vj)表示與詞語vj共現(xiàn)過的詞語的個數(shù),該值越小越好.這是因為,若vj相對于vi而言是重要的,則vj必然很少與除vi之外的其他詞共同出現(xiàn).公式的后半部分(idf部分)懲罰了那些和很多詞都共現(xiàn)過的vj.同理,可求出vj的單邊關(guān)聯(lián)度.

vi與vj的關(guān)聯(lián)度Rel(vi,vj)實質(zhì)上就是vi與vj的單邊關(guān)聯(lián)度的均值.

傳統(tǒng)的加權(quán)方式所求得的詞頻對微博短文本而言意義不大,因此本文考慮了詞語的關(guān)聯(lián)權(quán)重.關(guān)聯(lián)權(quán)重反映了在給定微博中詞語的主題指示性,若詞語vi的關(guān)聯(lián)權(quán)重越高,則意味著當(dāng)vi出現(xiàn)時,其他頂點隨之出現(xiàn)的概率也就越高.換言之,與vi具有強關(guān)聯(lián)的vj越多,vi與微博主題的相關(guān)性就越大.給定一個含有|Li|個超點的超圖后,每個超點都會有確定的初始權(quán)重iw(vi),則超點vi在超邊中的關(guān)聯(lián)權(quán)重定義如公式(10)所示.

其中,iw(vi)代表超點vi的初始權(quán)重,其值是vi在微博中的詞頻.

超點的權(quán)重不僅應(yīng)該考慮該點與其他超點的關(guān)聯(lián)性權(quán)重,而且還應(yīng)該考慮詞語對微博的標(biāo)識度.即某個詞語在這篇微博中出現(xiàn),但是卻很少在其他微博中出現(xiàn),則認為此詞語對該微博是重要的.所以綜合詞語的關(guān)聯(lián)性權(quán)重和全局統(tǒng)計權(quán)重對其進行加權(quán),超點vi的權(quán)重定義如公式(11)所示.

2.2 標(biāo)簽擴充方法

為了給超圖中的頂點排序,Bellaachia 等人將隨機游走的方法在超圖上進行了推廣[17].本文中,基于加權(quán)超圖的隨機游走過程如下:首先選定起始超點u,根據(jù)超邊權(quán)重w(e)選擇一條包含當(dāng)前超點u的特定超邊e;然后,在已經(jīng)選中的這條超邊中,根據(jù)超點權(quán)重選擇轉(zhuǎn)移頂點v.設(shè)P為隨機游走的轉(zhuǎn)移概率矩陣,其計算方法如公式(12)所示.

或者直接用矩陣的形式來表示轉(zhuǎn)移概率矩陣P.

其中,hw(v,e)是目的頂點v在超邊e中的權(quán)重;Dv是超點度的對角線矩陣,矩陣中元素的計算方法如公式(2)所示;H是普通超圖的指示矩陣;We為超邊權(quán)重的對角線矩陣;De是超邊度的對角線矩陣,矩陣中元素的計算方法如公式(3)所示;Hw是加權(quán)超圖的指示矩陣.值得注意的是,計算所得的轉(zhuǎn)移概率矩陣P是行歸一化后的結(jié)果.

隨機游走過程剛開始時,將初始分布向量v0∈R|V|×1視為等概率的,即其每一個元素值都為1/|V|,這些元素之和為1.首先,將轉(zhuǎn)移矩陣P的轉(zhuǎn)置矩陣PT(轉(zhuǎn)置的目的是實現(xiàn)列歸一化)與初始向量v0相乘,得到v1=PTv0;然后,對此過程進行迭代,直至向量v不再變化.將概率分布向量v與矩陣PT相乘可以得到下一步的概率分布x=PTv0.原因如下:設(shè)xi為當(dāng)前位于節(jié)點i的概率,其中,vj代表預(yù)設(shè)節(jié)點,pij為從節(jié)點j跳轉(zhuǎn)到節(jié)點i的概率.

隨機游走在經(jīng)過n步之后,若所有節(jié)點已被遍歷,則概率分布向量v不再發(fā)生變化.隨機游走遍歷所有節(jié)點需滿足以下兩個條件:馬爾可夫鏈是不可約的和非周期性的.為了保證這兩個條件,在此使用PageRank 算法來實現(xiàn)隨機游走過程,該算法加入了心靈轉(zhuǎn)移的思想.所謂心靈轉(zhuǎn)移,就是在任何一條超邊的超點都有可能以一個較小的概率瞬間轉(zhuǎn)移到另外一條超邊上.當(dāng)然,這兩條超點可能不存在連邊,因此不可能真的直接轉(zhuǎn)移過去.本文中這個小概率用阻尼因子β來表示,如公式(13)所示.

其中,n是超圖中超點的個數(shù),e∈Rn×1是超圖中長度為n的單位向量.(1-β)PTv表示隨機游走將從當(dāng)前超點選擇一條超邊跳轉(zhuǎn)到另外一個超點上.βe/n表示隨機游走將以β/n的概率跳轉(zhuǎn)到任意的其他超點.根據(jù)經(jīng)驗[18,19],本文中β的取值為0.15.

當(dāng)隨機游走的過程停止,即向量v不再發(fā)生變化時,對向量v中各頂點按權(quán)重由大到小依次排序.通常,選取對用戶重要程度最高的Top-Q個詞項作為用戶的標(biāo)簽,與用戶原有的標(biāo)簽合并,組成新的微博用戶標(biāo)簽集合Ti=,ni代表用戶ui最終的標(biāo)簽個數(shù).所有標(biāo)簽的集合為,且標(biāo)簽集合T中標(biāo)簽的總數(shù)為K.至此,微博用戶的標(biāo)簽得到擴充,接下來將采用標(biāo)簽概率相關(guān)性對微博進行推薦.

3 基于標(biāo)簽概率相關(guān)性的微博推薦

3.1 概率相關(guān)性構(gòu)建標(biāo)簽相似性矩陣

縱覽用戶標(biāo)簽集合,標(biāo)簽與標(biāo)簽之間并不是完全獨立的,它們彼此間存在著一定程度的關(guān)聯(lián)性,這種潛在的關(guān)聯(lián)性使得每個標(biāo)簽對不同用戶的重要性是不一樣的.此外,標(biāo)簽的多義性常常使得標(biāo)簽在表征用戶特征時出現(xiàn)歧義,例如某用戶的部分標(biāo)簽集{“蘋果”,“美食”,“果粉”,…},在該標(biāo)簽集中,標(biāo)簽“蘋果”就具有多義性,無法確定該標(biāo)簽表示的是一種水果還是一種通信設(shè)備.但是通過計算標(biāo)簽間的概率相關(guān)性[20],可以得到用戶的傾向性.

3.1.1 標(biāo)簽概率相關(guān)性

從整體觀測,假如任意兩個標(biāo)簽經(jīng)常一同被用戶標(biāo)記,則可以推測這兩個標(biāo)簽之間有很大概率的關(guān)聯(lián)性.從局部觀測,假如因某一標(biāo)簽被用戶標(biāo)記后,另一標(biāo)簽被用戶標(biāo)記的概率也很大,那么推測這兩個標(biāo)簽存在較強的共現(xiàn)關(guān)系,定義如公式(14)所示.

其中,分母代表標(biāo)簽tj出現(xiàn)的概率,分子代表標(biāo)簽ti和標(biāo)簽tj共同出現(xiàn)的概率,即p(titj)≈uf(titj)/N,uf(titj)表是同時標(biāo)注標(biāo)簽ti和標(biāo)簽tj的用戶數(shù).

從公式(14)可以看出,標(biāo)簽ti與標(biāo)簽tj之間的條件概率是一個非對稱的值.然而,標(biāo)簽與標(biāo)簽之間的相似性是對稱關(guān)系.因此,對標(biāo)簽之間的共現(xiàn)關(guān)系進行改進,具體辦法如公式(15)所示.

綜合公式(14)和公式(15),標(biāo)簽ti與標(biāo)簽tj之間的概率相關(guān)性被改寫為

3.1.2 標(biāo)簽相似性矩陣

一般通過向量空間模型構(gòu)建用戶-標(biāo)簽矩陣來表征用戶,矩陣中的每一個元素wij是用戶ui在第j個標(biāo)簽上的權(quán)重,標(biāo)簽也可以被視為是一個用戶向量[ui,1,ui,2,…,ui,N].對于用戶標(biāo)簽之間相似性的測量,傳統(tǒng)做法是計算用戶向量的相似程度.但是,受到用戶向量存在極度稀疏情況的限制,傳統(tǒng)方法并不能很好地測度標(biāo)簽間的相似性.因此,本文通過標(biāo)簽相關(guān)性向量來表征標(biāo)簽.

利用3.1.1 節(jié)計算得到的標(biāo)簽概率相關(guān)性,微博標(biāo)簽集合中的每一個標(biāo)簽ti都可以被表示成標(biāo)簽相關(guān)性向量[ti,1,ti,2,…,ti,n,…,ti,K],ti,n是標(biāo)簽ti和tn之間的概率相關(guān)性,定義如公式(17)所示.

采用余弦相似度計算標(biāo)簽間的相似程度,如公式(18)所示.

由標(biāo)簽相關(guān)性向量構(gòu)造標(biāo)簽相似性矩陣S,Sij表示標(biāo)簽向量ti和標(biāo)簽向量tj的余弦相似度,其計算公式如公式(19)所示.

矩陣中元素的取值范圍在(0,1]之間,Sij的取值等于1 時,表示兩個標(biāo)簽是一樣的,Sij的取值越接近1,則表明標(biāo)簽間的關(guān)聯(lián)性越顯著.在用戶標(biāo)簽集合中,標(biāo)簽之間都會存在一定程度的關(guān)聯(lián)性.因此,Sij的取值是非零的.

3.2 微博用戶興趣表示與推薦算法

標(biāo)簽作為用戶對身份特征、興趣愛好等綜合描述的簡單載體,其包含的豐富信息對構(gòu)建精準的用戶畫像具有重要作用.擁有相似標(biāo)簽越多的用戶,其博文類型也越相似.本節(jié)從相關(guān)性權(quán)重從發(fā),通過構(gòu)建精準的用戶興趣模型矩陣,進而進行個性化內(nèi)容推薦.

3.2.1 用戶標(biāo)簽權(quán)重

微博用戶為自己標(biāo)注的標(biāo)簽在整體上表現(xiàn)出冪率分布,即少量具有代表性的標(biāo)簽會時常被標(biāo)注,而其他個性化的標(biāo)簽通常很少被標(biāo)注,從而導(dǎo)致在傳統(tǒng)的標(biāo)簽權(quán)重加權(quán)方案中大多數(shù)標(biāo)簽的頻率為1.針對該情況,利用標(biāo)簽間的概率相關(guān)性,提出一種新的標(biāo)簽權(quán)重加權(quán)方案相關(guān)性權(quán)重.

微博用戶在為自身加注標(biāo)簽后,這些被標(biāo)注的標(biāo)簽之間就存在著一定的關(guān)聯(lián)性.假如用戶的某一標(biāo)簽與其他任一標(biāo)簽都具有較強的關(guān)聯(lián)度,則該標(biāo)簽對用戶具有較強的標(biāo)識度,定義如公式(20)所示.

其中,|ui|表示用戶ui的標(biāo)簽個數(shù),cor(tk,tj)表示標(biāo)簽tk和tj的概率相關(guān)性.標(biāo)簽的相關(guān)性權(quán)重是標(biāo)簽在標(biāo)簽集合中重要程度的體現(xiàn).標(biāo)簽具有的權(quán)重越高,其對用戶興趣愛好的描述能力就越好.

公式(20)僅僅從標(biāo)簽的局部特征出發(fā)計算出了標(biāo)簽對用戶的權(quán)重.一個全面的標(biāo)簽權(quán)重不僅要從局部考慮到其自身與其他標(biāo)簽的關(guān)系,而且還需要從整個微博集合上思考標(biāo)簽對用戶的標(biāo)識性,取名為逆用戶頻率IUF(inverse user frequency).具體思路是采用數(shù)據(jù)集中的用戶總數(shù)與加注某標(biāo)簽的用戶數(shù)的比值并取其對數(shù),定義如公式(21)所示.

其中,uf(tk)表示擁有標(biāo)簽tk的用戶數(shù).綜合標(biāo)簽的相關(guān)性權(quán)重和iuf值,則用戶ui中標(biāo)簽tk的權(quán)重定義如公式(22)所示.

3.2.2 用戶標(biāo)簽矩陣

針對用戶ui構(gòu)造一個標(biāo)簽權(quán)重向量Vi=(wi1,wi2,…,wiK)來存儲標(biāo)簽的權(quán)重[21],基于以上用戶權(quán)重向量,構(gòu)建N×K的用戶-標(biāo)簽矩陣M.

由于用戶-標(biāo)簽矩陣的列數(shù)為所有待加標(biāo)用戶的標(biāo)簽集合,并且該集合中的標(biāo)簽并不可能被所有用戶標(biāo)注,故該矩陣存在高維、稀疏的問題,并不能精準表征用戶興趣.考慮標(biāo)簽間的概率相關(guān)性,構(gòu)建標(biāo)簽-標(biāo)簽相似度矩陣,以此更新該用戶-標(biāo)簽矩陣,不僅可以解決原始矩陣的局限,而且還包含豐富的語義信息.公式(23)是更新后的用戶-標(biāo)簽矩陣.

其中,M是初始的用戶-標(biāo)簽矩陣,S是標(biāo)簽相似性矩陣,M′是更新后的用戶-標(biāo)簽矩陣,該矩陣可以更好地表示用戶興趣.為了更好的解釋更新后的矩陣稀疏問題得到緩解的問題,分解矩陣S如下.

標(biāo)簽與其自身的相似度是1,所以公式(24)的左半部分相乘結(jié)果為原始矩陣.此外,由于標(biāo)簽集合中的所有標(biāo)簽都存在一定的概率相關(guān)性,所以標(biāo)簽相似性矩陣中的元素都是非零的,這保證了公式(24)的右半部分是非零的.因此映射之后,每個用戶的標(biāo)簽向量的稀疏性將得到有效緩解.

3.2.3 微博推薦算法描述

定義推薦算法排序函數(shù)f:給定用戶ui和微博dp,則排序函數(shù)f(ui,dp)的定義[21]如公式(25)所示.

其中,f(ui,dp)表示用戶ui與微博dp之間的相關(guān)性.ui=(wi1,wi2,…,wiK)為更新后的用戶ui的標(biāo)簽權(quán)重向量.微博dp可被表示為,若微博dp包含標(biāo)簽ti,則;否則,.將微博文本向量映射到標(biāo)簽語義空間S上,則.預(yù)先設(shè)定閾值μ,若該排序函數(shù)的值大于閾值μ,則微博dp將被推薦給用戶ui.算法的框架如算法1 所示.

算法1.基于超圖隨機游走標(biāo)簽擴充的微博推薦算法.

4 實 驗

本節(jié)首先介紹了實驗所用數(shù)據(jù)集以及評價標(biāo)準,然后設(shè)計實驗對本文的方法進行驗證并對實驗結(jié)果進行分析討論.

4.1 實驗數(shù)據(jù)集描述及評價指標(biāo)

目前,沒有同時包括微博用戶標(biāo)簽和微博相關(guān)信息(內(nèi)容、轉(zhuǎn)發(fā)數(shù)以及點贊數(shù)等)的公開可用數(shù)據(jù)集,通過監(jiān)視新浪博客的最近更新列表,下載程序間歇性地抓取了19 427 位用戶2015 年7 月16 日～2016 年8 月17 日發(fā)布的微博,并存儲在數(shù)據(jù)庫中.這些數(shù)據(jù)庫記錄包括了博文的標(biāo)簽、發(fā)布時間、微博內(nèi)容、微博轉(zhuǎn)發(fā)數(shù)、評論數(shù)及點贊數(shù)等信息.

對實驗數(shù)據(jù)進行預(yù)處理,首先過濾文本中的@用戶名、地址鏈接、和其他無意義字符等噪聲信息后,對其進行分詞,去除停用詞.其中,分詞采用python 開源分詞組件jieba,停用詞表采用新浪提供的1 208 個停用詞.實驗中隨機選取13 000 名用戶,刪除擁有少于4 個詞匯的微博以及擁有少于50 篇微博的用戶,得到最終的實驗數(shù)據(jù)集合.數(shù)據(jù)集中有用戶10 390 名,微博2 186 283 條,標(biāo)簽個數(shù)5 897 個.新浪微博允許用戶最多添加10 個關(guān)鍵詞對自己進行描述,表2 統(tǒng)計了數(shù)據(jù)集中添加不同標(biāo)簽數(shù)量的用戶分布,其中,48.3%的用戶至少添加了一個標(biāo)簽,而51.7%的用戶沒有為自己添加標(biāo)簽,這充分表明了標(biāo)簽擴充對進行微博推薦的必要性.

Table 2 Distribution of users with different number of tags in dataset表2 數(shù)據(jù)集中添加不同標(biāo)簽個數(shù)的用戶分布

為了驗證推薦算法的準確性,將微博數(shù)據(jù)集分為訓(xùn)練集和測試集:訓(xùn)練集用來學(xué)習(xí)推薦方法中的相關(guān)參數(shù),測試集用來驗證推薦算法的準確性.為了避免數(shù)據(jù)過擬合,本文采用十折交叉驗證的方法,將每個微博用戶的數(shù)據(jù)樣本隨機劃分成10 個大小相等的子樣本集,交叉驗證過程重復(fù)10 次.每次一個樣本集被保留作為測試集的驗證數(shù)據(jù),其余9 個樣本集作為訓(xùn)練數(shù)據(jù),其中,訓(xùn)練集中有1 967 655 條樣本,測試集中有218 628 條樣本.

本文實驗環(huán)境為:Windows 7 操作系統(tǒng),4GB 內(nèi)存,Intel Core(TM)2 Duo CPU 2.66GHz,實驗程序使用Java1.6語言開發(fā),數(shù)據(jù)庫為Mysql5.0.

準確率(precision)、召回率(recall)、F1 值(F-measure)和平均正確率(average precision,簡稱AP)是廣泛用于信息檢索和推薦領(lǐng)域的4 個度量值,用來評價結(jié)果的質(zhì)量.為了評估微博推薦質(zhì)量,本文采用前L條結(jié)果的準確率P@L、前L條結(jié)果的召回率R@L、前L條結(jié)果的F1 值F1@L以及前L條結(jié)果的平均正確率AP@L來評價微博推薦質(zhì)量.P@L,R@L,F1@L和AP@L定義如下.

其中,rel(k)是一個指示函數(shù),當(dāng)推薦返回結(jié)果的第k個位置為相關(guān)微博,rel(k)=1;否則,rel(k)=0.微博中沒有明確表明用戶喜好的數(shù)據(jù),本文中把用戶發(fā)布的微博都認為是用戶喜歡的微博.

4.2 實驗結(jié)果與相關(guān)分析

為了驗證本文方法的有效性及推薦結(jié)果的準確性,本節(jié)設(shè)計了4 個實驗,對本文提出的方法進行驗證并對實驗結(jié)果進行分析.一是通過改變參數(shù)α和閾值μ,比較微博推薦算法的性能,從而確定最優(yōu)參數(shù)值;二是在參數(shù)值確定的基礎(chǔ)上,驗證標(biāo)簽擴充個數(shù)對微博推薦性能的影響;三是通過比較標(biāo)簽擴充前后的內(nèi)容,展示標(biāo)簽擴充方法的性能;四是本文的微博推薦算法與其他算法的比較.

4.2.1 參數(shù)設(shè)置對方法性能的影響

下面將通過實驗來考察方法中涉及到的參數(shù)對算法性能的影響,它們分別是參數(shù)α和閾值μ.當(dāng)測試其中一個參數(shù)值對算法的影響時,另外一個參數(shù)值保持不變.

對超邊加權(quán)時,α用于調(diào)節(jié)微博時間因子和微博人氣指數(shù)的比重,其值越高,意味著用戶發(fā)布微博的時間對于用戶興趣的提取影響越大;其值越小,就意味著微博的評論數(shù)、轉(zhuǎn)發(fā)數(shù)等對于用戶興趣提取影響提高.為了計算參數(shù)α對于推薦結(jié)果的影響,本文分別對不同α取值下算法在微博推薦個數(shù)為L=5、L=10、L=15 及L=20 的推薦結(jié)果進行對比.設(shè)參數(shù)μ=0.5,分別在α取不同值時,比較方法的性能,圖2 展示了實驗結(jié)果.對比圖2 左、右兩圖,可以發(fā)現(xiàn)以下幾點.

(1)左圖中,當(dāng)L=15 時算法的準確率P@L達到最佳;在右圖中,當(dāng)L=20 時算法的召回率R@L達到最佳.這是由于召回率依賴于用戶測試樣本數(shù)目,隨著推薦數(shù)目的增加,算法召回率也逐漸增加.

(2)當(dāng)α=0.7 時,算法的準確率P@L和召回率R@L均達到最大值,算法的性能在各個微博推薦個數(shù)上都達到最佳狀態(tài).值得注意的是,當(dāng)α=1 時,算法的推薦性能在準確率和召回率上都優(yōu)于α=0 時,因此,微博時間因子對用戶興趣提取準確性的影響大于微博人氣指數(shù).在接下來的實驗中,設(shè)定α=0.7.

Fig.2 Impact of parameter α on recommendation algorithms圖2 參數(shù)α對推薦算法的影響

閾值μ的大小決定了推薦方法向用戶推薦微博數(shù)量的大小,閾值μ越小,則向用戶推薦的微博數(shù)量越多;閾值μ越大,則向用戶推薦的微博數(shù)量越少.為了清楚地了解閾值μ的取值對推薦算法的影響,令參數(shù)α=0.7,μ取不同的值,在測試數(shù)據(jù)集上計算方法取得的實驗結(jié)果如圖3 所示.

Fig.3 Impact of threshold μ on recommendation algorithms圖3 閾值μ對推薦算法的影響

從圖中可以看出,隨著閾值μ的增大,算法的準確率逐漸上升,而算法的召回率卻逐漸減小.這是因為隨著閾值μ的增大,方法要求所推薦微博與用戶的相似度也在不斷增大,因而推薦給用戶的微博越來越少.當(dāng)μ=0.4 或0.5 時,算法在F1 這一評價指標(biāo)上都達到了最佳.因此,本文又在綜合考慮μ=0.4 或0.5 時算法的準確率和召回率這兩個評價指標(biāo)后,確定μ=0.45.

4.2.2 不同標(biāo)簽擴充個數(shù)對推薦算法的影響

為了驗證標(biāo)簽擴充個數(shù)Top-Q對微博推薦方法的影響,分別選取{1,3,5,7,9,10}個關(guān)鍵詞對用戶標(biāo)簽進行擴充,計算在不同標(biāo)簽擴充個數(shù)的情況下本文算法的準確率,進而確定標(biāo)簽擴充個數(shù)Top-Q的值,如圖4 所示.從圖中可以看出,隨著標(biāo)簽擴充個數(shù)的增加,算法的準確率P@L也逐漸增加.當(dāng)標(biāo)簽擴充個數(shù)P>9 時,算法的準確率P@L不增反降.這是由于隨著標(biāo)簽擴充個數(shù)的增大,一些排名靠后的關(guān)鍵詞也被擴充到用戶標(biāo)簽集合中,這部分標(biāo)簽并不能很好地表征用戶的興趣愛好.從圖中可以看出,當(dāng)Q=7 或9 時,算法的準確率P@L并無明顯增加,算法的性能在各個微博推薦個數(shù)上都達到最佳狀態(tài).因此,取7 和9 的均值8 作為標(biāo)簽擴充個數(shù)Q的值.

Fig.4 Impact of the number of tag extensions on recommendation algorithms圖4 標(biāo)簽擴充個數(shù)對推薦算法的影響

4.2.3 標(biāo)簽擴充前后用戶標(biāo)簽詳情對比

限于篇幅,本部分只展示了10 位用戶自己添加的標(biāo)簽以及經(jīng)過超圖隨機游走算法為用戶添加的標(biāo)簽的情況,見表3.

Table 3 Comparison of user tag before and after the tag expansion表3 標(biāo)簽擴充前后用戶標(biāo)簽詳情對比

可以看到,少數(shù)的高頻詞出現(xiàn)在相當(dāng)多的微博用戶標(biāo)簽中,這些熱門標(biāo)簽的內(nèi)容多是大眾性的興趣愛好的描述,如“音樂”“電影”“美食”等;或者是對一些常見人群的描述,如“大學(xué)生”“90 后”“宅”.這些標(biāo)簽之所以被頻繁使用,一是因為這其中的一些標(biāo)簽在用戶添加標(biāo)簽的頁面作為系統(tǒng)推薦選項出現(xiàn),因此有更大的概率被用戶看到和選中,而不用手動輸入;二是此類標(biāo)簽對于新浪微博用戶具有普適性,即很多微博用戶都會發(fā)現(xiàn)這樣的標(biāo)簽在某種程度上符合對自己的描述.例如在實驗數(shù)據(jù)集中,有52.7%的用戶是大學(xué)生,“奮斗”“90 后”兩個標(biāo)簽非常符合對這些用戶的描述,因此成為高頻標(biāo)簽.

4.2.4 不同微博算法的性能比較

為了驗證該推薦算法的有效性,比較本文提出的 LeALpc 算法與基于標(biāo)簽關(guān)聯(lián)關(guān)系推薦算法(label correlation,簡稱LC)[13]、基于標(biāo)簽概率相關(guān)性推薦算法(label probability correlation,簡稱LPC)[14]、融合標(biāo)簽關(guān)系與用戶關(guān)系推薦算法(label correlation and user social relation,簡稱ILCAUSR)[15]、協(xié)同個性化微博推薦(collaborative personalized tweet recommendation,簡稱CTR)[3]、基于用戶嵌入的學(xué)術(shù)微博推薦(user embedding for scholarly microblog recommendation,簡稱 UEMR)[4]和基于背景和內(nèi)容的微博推薦(microblog recommendation based on profile and content,簡稱BPACMR)[22]的預(yù)測效果.選擇以上6 種算法作為對比算法是基于以下幾點考慮.

(1)本文算法是在LPC 算法的基礎(chǔ)上改進而來,LPC 算法與本文的算法最相似.

(2)LC 算法、ILCAUSR 算法、LPC 算法以及本文的算法都是基于標(biāo)簽進行微博推薦的.

(3)ILCAUSR 算法已被證明在微博推薦算法上優(yōu)于其他算法.

(4)由于前面3 種比較算法都是從標(biāo)簽角度出發(fā)的微博推薦算法,為了更好地驗證本文方法的有效性,采用從其他角度出發(fā)且具有較好性能的微博推薦算法(CTR 算法、UEMR 算法和BPACMR 算法)進行對比.

利用不同微博推薦列表長度L=5、L=10、L=15 及L=20 對以上算法進行實驗,比較在不同推薦列表長度的情形下,幾種推薦算法的準確率P@L、F1 值F1@L以及平均正確率AP@L,結(jié)果見表4.

Table 4 Comparison of different recommendation algorithms表4 不同推薦算法比較

從表中可以看出,本文提出的LeALpc 算法與從內(nèi)容角度出發(fā)的CTR 算法、UEMR 算法和BPACMR 算法以及從標(biāo)簽角度出發(fā)的LPC 算法、算法LC 和ILCAUSR 算法在平均準確率方面相比都更優(yōu)異.這是由于這些算法過分關(guān)注用戶的整體興趣而忽視了用戶的個性化興趣,導(dǎo)致推薦列表前幾位的命中率低.而LeALpc 算法結(jié)合了微博文本和用戶標(biāo)簽這兩個體現(xiàn)用戶興趣的重要方面,它更能展現(xiàn)用戶的個性化興趣.在實際應(yīng)用中,推薦正確的次序尤其重要,因為用戶不可能耐心瀏覽完所有推薦的微博.在其他評價指標(biāo)上,LeALpc 算法明顯高于除ILCAUSR 算法之外的5 種算法,但是與ILCAUSR 算法相比并沒有明顯優(yōu)勢.這是由于ILCAUSR 算法將用戶間社交關(guān)系融入到微博推薦算法中,較為準確地表示出了用戶的興趣.而本文尚未考慮,這也將是本文今后繼續(xù)研究的方向.

接著,為了進一步比較LeALpc 算法和其他6 種算法的推薦性能,從表4 中選取推薦性能(正確率P@L)最好情況(L=15)和最壞情況的(L=20)的正確率和平均正確率展開分析,分別是L=15 和L=20 時,7 種算法在不同評價指標(biāo)上10 次交叉驗證所得結(jié)果的分布情況,如圖5 所示.箱線圖是一種數(shù)據(jù)樣本統(tǒng)計圖,它可以看出數(shù)據(jù)是否具有對稱性以及數(shù)據(jù)分布的分散程度等信息.因此,從圖5 可以看出,

?在評價指標(biāo)AP@L上,無論是最好情況(L=15)還是最壞情況(L=20),本文提出的LeALpc 算法不但具有較高的平均值,而且10 次所得結(jié)果也比較穩(wěn)定.

?在評價指標(biāo)P@L上,在最好情況(L=15)下,本文提出的算法與ILCAUSR 算法相比,在平均值上雖然并沒有明顯優(yōu)勢,但是在結(jié)果分布上要優(yōu)于其他算法.

這更加驗證了根據(jù)微博用戶以往發(fā)布的微博內(nèi)容對其標(biāo)簽進行擴充以及根據(jù)標(biāo)簽概率相關(guān)性對用戶進行微博推薦這一方法的有效性.

Fig.5 Performance comparison among LeALpc algorithm and other baselines on L=15 and L=20圖5 LeALpc 算法與對比算法在L=15 和L=20 時的性能比較

5 結(jié)論與展望

隨著移動互聯(lián)網(wǎng)的快速發(fā)展以及社交網(wǎng)絡(luò)規(guī)模的不斷增大,個性化的信息推薦越來越受到信息接收者的青睞.為了提升用戶瀏覽信息的體驗度,面對海量復(fù)雜的微博消息,實現(xiàn)內(nèi)容精準推薦.本文從微博用戶標(biāo)簽入手,針對絕大多數(shù)微博用戶沒有給自己加注標(biāo)簽或標(biāo)簽較少的問題,提出一種結(jié)合標(biāo)簽擴充與標(biāo)簽概率相關(guān)性的微博推薦方法.首先,該方法將微博視為超邊,微博中的詞視為超點來構(gòu)建超圖,并以一定的加權(quán)策略對超邊和超點進行加權(quán),通過在超圖上隨機游走得到一定數(shù)量的關(guān)鍵詞對微博用戶標(biāo)簽進行擴充;然后,采用相關(guān)性標(biāo)簽權(quán)重加權(quán)方案,構(gòu)建用戶-標(biāo)簽矩陣,利用標(biāo)簽間的概率相關(guān)性,構(gòu)造標(biāo)簽相似性矩陣,對用戶-標(biāo)簽矩陣進行更新,更新后的用戶標(biāo)簽矩陣不僅稀疏性得到了有效緩解,而且還包含了豐富的標(biāo)簽關(guān)聯(lián)關(guān)系;最后,依據(jù)構(gòu)建的興趣模型對用戶進行信息推薦.在未來的工作中,將進一步對用戶與用戶之間的社交屬性進行研究,提升用戶模型的準確度,實現(xiàn)更加精準的推薦.