屠守中，閆 洲，衛(wèi)玲蔚，朱小燕

(1.清華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084；2.中國科學(xué)院信息工程研究所，北京 100093)

隨著移動(dòng)互聯(lián)網(wǎng)的飛速發(fā)展，社交網(wǎng)絡(luò)(Social Network Service, SNS)漸漸地滲透到人們的日常生活中。近幾年，社交網(wǎng)絡(luò)的發(fā)展出現(xiàn)了新的趨勢：①用戶節(jié)點(diǎn)兩極分化；②社交平臺(tái)內(nèi)容化，內(nèi)容平臺(tái)社交化。文獻(xiàn)[1]指出，社交網(wǎng)絡(luò)具有Scale-free的特性，極少量的用戶擁有較多的關(guān)系連接，而大量的用戶具有少量的關(guān)系。以微博為例，由于明星、媒體機(jī)構(gòu)等擁有巨大影響力的超級(jí)節(jié)點(diǎn)出現(xiàn)，用戶的分化愈發(fā)明顯，網(wǎng)絡(luò)社區(qū)也逐漸向超級(jí)節(jié)點(diǎn)匯聚。超級(jí)節(jié)點(diǎn)經(jīng)常發(fā)布高質(zhì)量的信息內(nèi)容，制造熱點(diǎn)話題，是社交網(wǎng)絡(luò)中的重要信息制造者和傳播者；而廣大普通用戶則更多的是關(guān)注、參與這些話題討論，自己主動(dòng)發(fā)布的信息很少。因此，社交模式已由用戶之間的交互逐漸轉(zhuǎn)變?yōu)樾畔?nèi)容的傳播和接收。

然而，現(xiàn)有的社交網(wǎng)絡(luò)研究方法建立在節(jié)點(diǎn)地位平等、關(guān)系相似的基礎(chǔ)上，在面對(duì)高度分化的用戶，如果直接進(jìn)行分析計(jì)算，則可能最終的結(jié)果就不夠精確，甚至與實(shí)際網(wǎng)絡(luò)關(guān)系形態(tài)大相徑庭。筆者重點(diǎn)針對(duì)社交網(wǎng)絡(luò)節(jié)點(diǎn)分化的特性，提出了一種基于社交關(guān)系在大規(guī)模異構(gòu)網(wǎng)絡(luò)中挖掘用戶興趣的方法。一方面，充分利用機(jī)構(gòu)媒體、明星等超級(jí)節(jié)點(diǎn)發(fā)布的高質(zhì)量信息內(nèi)容提取話題；另一方面，利用社交關(guān)系研究話題的傳播，從而推斷普通用戶的興趣，解決普通用戶不活躍、信息少的問題。該文章主要貢獻(xiàn)點(diǎn)如下：

(1)針對(duì)異構(gòu)社交網(wǎng)絡(luò)中節(jié)點(diǎn)和關(guān)系分化的特性，提出一種基于社交關(guān)系的興趣挖掘通用算法框架。

(2)用無監(jiān)督的矩陣分解算法分析超級(jí)節(jié)點(diǎn)的內(nèi)容得到興趣話題，大量減少了人工標(biāo)注和訓(xùn)練工作。

(3)引入標(biāo)簽傳播算法計(jì)算興趣話題在普通用戶之間的傳播，在異構(gòu)網(wǎng)絡(luò)中快速構(gòu)建大規(guī)模用戶群體的興趣圖譜。

1 相關(guān)研究

由于社交網(wǎng)絡(luò)的迅猛發(fā)展，人們?cè)絹碓搅?xí)慣于從社交平臺(tái)上獲得其感興趣的話題或消息，這也就使得用戶個(gè)性化推薦成為重要的一項(xiàng)網(wǎng)絡(luò)服務(wù)。因此，挖掘用戶的潛在興趣話題并推薦相關(guān)信息具有重大的研究價(jià)值。一些學(xué)者通過分析用戶內(nèi)容的話題分布，從而推斷用戶興趣，如文獻(xiàn)[2]研究了結(jié)合用戶瀏覽的行為和信息內(nèi)容挖掘興趣的方法。文獻(xiàn)[3]也提出了用戶交互行為和標(biāo)簽信息相結(jié)合的方法對(duì)新浪微博用戶的興趣進(jìn)行挖掘。語義理解是常用的用戶興趣挖掘方法，如結(jié)合詞頻和逆文檔頻率指數(shù)和TextRank的關(guān)鍵詞抽取方法[4]以及分析和識(shí)別文本外鏈信息的方法[5]。文獻(xiàn)[6]提出了一種摘要樹模型(the UIP tree model)，通過用戶信息和行為挖掘潛在興趣。文獻(xiàn)[7]先用Wikipedia把Twitter上的名人用戶劃分為不同類別，再把關(guān)注這些名人的用戶歸類到對(duì)應(yīng)的興趣上。

除此之外，還有部分學(xué)者基于內(nèi)容或好友相似度進(jìn)行建模，推薦用戶感興趣的信息或好友。文獻(xiàn)[8]通過對(duì)用戶的顯式興趣和隱式興趣進(jìn)行建模，設(shè)計(jì)實(shí)現(xiàn)了個(gè)性化推薦系統(tǒng)。文獻(xiàn)[9]提出了用社交話題模型發(fā)現(xiàn)并推薦用戶感興趣的地理信息。文獻(xiàn)[10-11]研究了如何利用個(gè)人信息、關(guān)鍵詞和社交關(guān)系計(jì)算不同用戶的興趣相似度。文獻(xiàn)[12]綜合考慮了用戶的長期興趣和短期行為，應(yīng)用馬爾科夫鏈解決稀疏數(shù)據(jù)集問題，實(shí)現(xiàn)順序的個(gè)性化推薦。文獻(xiàn)[13]提出了TWITOBI系統(tǒng)，通過概率模型向用戶推薦Top-k用戶和Top-K Tweets。而文獻(xiàn)[14]則基于文檔主題生成模型分析微博的主題分布和用戶的興趣取向，在流數(shù)據(jù)用滑動(dòng)窗口模型來實(shí)時(shí)搜尋和推薦熱門微博。

以上的研究方法重點(diǎn)都在于通過分析用戶相關(guān)信息來提取興趣，優(yōu)點(diǎn)是直接、相對(duì)簡單，但是往往受限于消息文本字?jǐn)?shù)少、用語不規(guī)范等特性，沒有充分考慮社交因素。此外，當(dāng)前社交網(wǎng)絡(luò)中存在大量不夠活躍、很少主動(dòng)發(fā)布信息的用戶，如何挖掘這些用戶的興趣也是一大挑戰(zhàn)。

2 算法總體框架

2.1 用戶潛在興趣挖掘模型

根據(jù)社交網(wǎng)絡(luò)的特點(diǎn)，把社交網(wǎng)絡(luò)的節(jié)點(diǎn)分為明星和機(jī)構(gòu)賬號(hào)等內(nèi)容發(fā)布節(jié)點(diǎn)以及普通用戶節(jié)點(diǎn)，節(jié)點(diǎn)間的關(guān)系則包括了單向的內(nèi)容傳播和雙向的信息交互等。據(jù)此，提出了以下兩條假設(shè)：

(1)用戶關(guān)注的明星和機(jī)構(gòu)等節(jié)點(diǎn)所發(fā)布的內(nèi)容反映了該用戶的興趣傾向。

(2)用戶和鄰接的好友節(jié)點(diǎn)具有相似的興趣。

在文中把用戶興趣分為顯式興趣和潛在興趣兩類。其中，顯式興趣能夠從用戶自身的信息(文字、標(biāo)簽等)直接得到，而基于以上兩條假設(shè)從社交關(guān)系間接推斷得到的則是潛在興趣。具體來說，對(duì)于一個(gè)社交網(wǎng)絡(luò)G=?V,E?，V由m個(gè)內(nèi)容發(fā)布節(jié)點(diǎn)(集合Ua)和n個(gè)普通用戶節(jié)點(diǎn)(集合Uf)組成，V=Ua∪Uf，其中，Ua∩Uf=?，|Ua|=m，|Uf|=n。設(shè)用戶興趣集合T共有k個(gè)分類，(t1,…,tk)表示興趣向量，每個(gè)分量代表對(duì)應(yīng)興趣類別的概率。用戶i的潛在興趣和顯式興趣向量分別用fi和ei表示，其社交關(guān)系則分為內(nèi)容發(fā)布節(jié)點(diǎn)集合Na?Ua和普通好友集合Nf?Uf，xj表示內(nèi)容發(fā)布節(jié)點(diǎn)j所發(fā)的文本信息，q是從xj中提取的興趣向量。則該用戶的潛在興趣概率為

(1)

式(1)之第一式將影響用戶的潛在興趣的因素總結(jié)為3項(xiàng)，前兩項(xiàng)分別為該用戶普通好友的潛在興趣和顯式興趣，第3項(xiàng)表示用戶關(guān)注的內(nèi)容發(fā)布節(jié)點(diǎn)的話題，3項(xiàng)因素的權(quán)重分別由α、β、γ決定。因此，文中提出的模型算法重點(diǎn)包括初始興趣向量的生成及興趣話題的傳播。這兩步的具體實(shí)現(xiàn)將在下文中進(jìn)行闡述。

2.2 初始興趣向量的生成

在社交網(wǎng)絡(luò)中，明星及新聞機(jī)構(gòu)等發(fā)布的內(nèi)容往往都包含了豐富的話題，這些節(jié)點(diǎn)也普遍是普通網(wǎng)民關(guān)注和感興趣的對(duì)象?？蓮挠脩絷P(guān)注的這些節(jié)點(diǎn)提取到諸多與用戶興趣向量有關(guān)的信息，再結(jié)合用戶自身發(fā)布信息所提取的顯示興趣，從而生成用戶的初始興趣向量。具體實(shí)現(xiàn)步驟如下：

(1)根據(jù)文本內(nèi)容挖掘潛在話題。需要在社交網(wǎng)絡(luò)G中對(duì)用戶關(guān)注的內(nèi)容發(fā)布節(jié)點(diǎn)(根據(jù)粉絲數(shù)、名字等特性來確定)進(jìn)行有效話題的提取。由于這些內(nèi)容絕大多數(shù)為文本內(nèi)容，因此需要一種合適的方法來對(duì)文本內(nèi)容進(jìn)行潛在話題的挖掘，從而為接下來初始向量的生成奠定基礎(chǔ)。最終通過使用文本聚類(Document-clustering)來對(duì)整個(gè)文本進(jìn)行壓縮與提取，從而形成有意義的話題以及對(duì)應(yīng)的特征向量。同時(shí)這是基于正交非負(fù)矩陣分解方法[15](Non-nagative Matrix Factorization, NMF)來找出內(nèi)容發(fā)布節(jié)點(diǎn)的內(nèi)容話題，即

min‖X-QGT‖ ,

(2)

其中，X是m×l的節(jié)點(diǎn)-文本矩陣，Q是m×k的節(jié)點(diǎn)-興趣話題矩陣，G是l×k的文本-興趣話題矩陣。通過分解求得Qm×k，每一行qi代表內(nèi)容發(fā)布節(jié)點(diǎn)i在k個(gè)興趣話題上的分布情況。根據(jù)這種方法來進(jìn)行文檔聚類的高效性已經(jīng)在文獻(xiàn)[16]中得到詳細(xì)的證明。

(2)挖掘普通用戶關(guān)注的興趣話題。根據(jù)普通用戶關(guān)注內(nèi)容發(fā)布節(jié)點(diǎn)的情況構(gòu)造矩陣An×m，其中，aij=1表示用戶i關(guān)注了內(nèi)容發(fā)布節(jié)點(diǎn)j；aij=0表示無關(guān)注關(guān)系。An×mQm×k能夠計(jì)算出普通用戶在k個(gè)話題上的興趣分布，這樣就得到了用戶關(guān)注節(jié)點(diǎn)對(duì)其初始興趣向量的影響。此外，考慮到用戶自身還有的顯式興趣En×k，最終普通用戶的興趣特征可以表示為兩者的加權(quán)平均：

(3)

綜上，根據(jù)用戶關(guān)注的內(nèi)容發(fā)布節(jié)點(diǎn)與其自身的發(fā)布內(nèi)容，進(jìn)行了文檔聚類，并將兩者所得結(jié)果綜合，最終得到了用戶的初始興趣向量矩陣Bn×k，其中每一行表示普通用戶i的興趣特征向量。

2.3 興趣話題的傳播

在得到用戶的初始興趣向量矩陣后，基于社交網(wǎng)絡(luò)用戶與鄰接好友之間具有相似興趣的設(shè)想，考慮到用戶在自己初始興趣的基礎(chǔ)上，必定會(huì)受到其鄰接好友對(duì)其興趣的影響。而這個(gè)影響顯然是會(huì)隨著網(wǎng)絡(luò)來進(jìn)行不斷傳播的，每一個(gè)點(diǎn)都會(huì)迭代地將其興趣信息傳遞給它的鄰居，想要的是網(wǎng)絡(luò)達(dá)到全局穩(wěn)定狀態(tài)時(shí)各個(gè)用戶的興趣向量矩陣，此時(shí)用戶的興趣向量矩陣顯然與初始興趣向量矩陣有所區(qū)別。

(4)

接下來給出對(duì)于文中的潛在興趣挖掘模型對(duì)應(yīng)于上式的具體含義。首先，在計(jì)算興趣的傳播過程中，只考慮由普通用戶節(jié)點(diǎn)組成的網(wǎng)絡(luò)，即鄰接矩陣Wn×n表示n個(gè)普通用戶節(jié)點(diǎn)之間的關(guān)系：

(5)

其中，Sim(i,j)是節(jié)點(diǎn)之間的聯(lián)系函數(shù)。在實(shí)際應(yīng)用中可以根據(jù)節(jié)點(diǎn)間的相似度(內(nèi)容、結(jié)構(gòu)等屬性)或者交互程度計(jì)算，取值越大，表明節(jié)點(diǎn)關(guān)系越緊密。而在式(4)中使用矩陣S，而不是矩陣W來進(jìn)行迭代，是為了之后的計(jì)算部分具有更好的收斂性。此外，用2.2節(jié)計(jì)算結(jié)果Bn×k作為初始用戶興趣矩陣Y，而F(t)則表示第t次迭代后的用戶-興趣矩陣。文獻(xiàn)[17]已證明，經(jīng)過不斷迭代，最終的傳播結(jié)果F(t)是收斂的，在傳播結(jié)束后可以得到，即最終的用戶興趣向量矩陣為

F*=(1-α′)(I-α′S)B。

(6)

3 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

文中將以知乎為平臺(tái)進(jìn)行實(shí)驗(yàn)。首先，通過網(wǎng)絡(luò)爬蟲獲取了1 041個(gè)知乎內(nèi)容發(fā)布者的粉絲、關(guān)注用戶以及其發(fā)布的文本內(nèi)容。并根據(jù)內(nèi)容發(fā)布者的粉絲列表，爬取其粉絲用戶的粉絲信息和關(guān)注信息，得到40 708個(gè)普通用戶的關(guān)注關(guān)系。并隨機(jī)抽取1 041個(gè)用戶，作為文中的測試集用戶。

3.1.2 對(duì)比實(shí)驗(yàn)

為了更好地評(píng)估文中算法的可行性及有效性，所采用的基線實(shí)驗(yàn)的細(xì)節(jié)如下：

(1)隱含狄利克雷分布(Latent Dirichlet Allocation, LDA)主題模型。在自然語言處理領(lǐng)域，關(guān)于興趣話題挖掘的研究備受關(guān)注，很多研究人員提出了不同的解決思路和方案，其中LDA是最典型的主題模型之一。通過LDA提取內(nèi)容發(fā)布者的潛在話題，構(gòu)建用戶的初始興趣向量，再用標(biāo)簽傳播算法得到普通用戶的興趣向量。

(2)支持向量機(jī)(Support Vector Machines, SVM)模型。對(duì)用戶興趣的挖掘本質(zhì)上是一種分類問題，因此，將選取較為典型的分類模型SVM與文中的興趣傳播算法進(jìn)行對(duì)比。在此實(shí)驗(yàn)中，將興趣這一多分類問題轉(zhuǎn)變?yōu)槎诸悊栴}，采用一對(duì)多(one-versus -rest)的方式構(gòu)建模型。

(3)鄰居投票算法。鄰居投票算法通過每個(gè)鄰居節(jié)點(diǎn)對(duì)新加入節(jié)點(diǎn)的興趣所屬狀態(tài)進(jìn)行投票，然后對(duì)各個(gè)票數(shù)進(jìn)行加權(quán)統(tǒng)計(jì)，若票數(shù)大于某一閾值，則判定該節(jié)點(diǎn)具有某興趣。

3.1.3 評(píng)價(jià)標(biāo)準(zhǔn)

本次實(shí)驗(yàn)的評(píng)價(jià)標(biāo)準(zhǔn)計(jì)算方式主要由兩部分構(gòu)成。首先，構(gòu)建測試集中普通用戶的評(píng)價(jià)體系(查準(zhǔn)率和查全率)。計(jì)算測試集中普通用戶的平均標(biāo)準(zhǔn)，得到平均查準(zhǔn)率(Pm)、平均查全率(Rm)，并計(jì)算相應(yīng)的F1(衡量分類問題的一個(gè)指標(biāo))值綜合評(píng)估算法的性能。具體計(jì)算公式為

(7)

(8)

(9)

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

結(jié)合知乎話題特點(diǎn)，文中選取K=10，通過調(diào)節(jié)式(4)中的參數(shù)α進(jìn)行實(shí)驗(yàn)，結(jié)果如圖1所示。

圖1 參數(shù)α對(duì)實(shí)驗(yàn)結(jié)果的影響

當(dāng)α=0.3時(shí)，文中算法的綜合性能表現(xiàn)最佳。實(shí)驗(yàn)的結(jié)果驗(yàn)證了文中提出的假設(shè)和算法模型，即在一定程度上，普通用戶關(guān)注的內(nèi)容發(fā)布者的文本內(nèi)容可以反映該用戶的興趣，同時(shí)普通用戶與好友之間往往具有相似的興趣愛好。

采用在不同基線算法的實(shí)驗(yàn)結(jié)果如表1所示。

表1 對(duì)比實(shí)驗(yàn)結(jié)果 %

由實(shí)驗(yàn)結(jié)果可知，在一定的條件下，文中提出的基于NMF的標(biāo)簽傳播算法相比LDA和鄰居投票算法雖然在查準(zhǔn)率上提升較小(約為0～17%)，但是在查全率上有大幅提升，最大提升約為42%；作為查準(zhǔn)率和查全率的調(diào)和平均數(shù)，F(xiàn)1值也有所提升，最大提升達(dá)到了33%。而在本次實(shí)驗(yàn)中，SVM并未表現(xiàn)出較好的效果，也說明單純依靠用戶關(guān)注的內(nèi)容并不能很好地推測用戶的興趣特征，還需要考慮該用戶鄰接好友的興趣情況。

4 結(jié)束語

文中通過對(duì)現(xiàn)有社交網(wǎng)絡(luò)節(jié)點(diǎn)分化的特性進(jìn)行分析，提出了一種基于社交關(guān)系在大規(guī)模異構(gòu)網(wǎng)絡(luò)中發(fā)現(xiàn)用戶興趣的方法，通過引入標(biāo)簽傳播算法，計(jì)算興趣話題在普通用戶之間的傳播，在異構(gòu)網(wǎng)絡(luò)中快速構(gòu)建大規(guī)模用戶群體的興趣圖譜。此外，文中采用無監(jiān)督的矩陣分解算法分析超級(jí)節(jié)點(diǎn)的內(nèi)容得到興趣話題，使得人工標(biāo)注和訓(xùn)練工作大大減少。

最后，以知乎為研究平臺(tái)，與LDA主題模型、鄰居投票機(jī)制、SVM模型進(jìn)行對(duì)比分析，結(jié)果表明，文中算法雖然查準(zhǔn)率提升較小，但在查全率上較基線方法提升約42%，從而使得算法的綜合性能提高，F(xiàn)1值最大提升約為33%。同時(shí)，文中也為社交網(wǎng)絡(luò)中不活躍用戶的興趣挖掘提供了很好的思路。