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

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

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

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

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

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

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

1 相關(guān)研究

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

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

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

2 算法總體框架

2.1 用戶潛在興趣挖掘模型

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

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

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

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

(1)

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

2.2 初始興趣向量的生成

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

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

min‖X-QGT‖ ,

(2)

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

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

(3)

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

2.3 興趣話題的傳播

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

(4)

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

(5)

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

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

(6)

3 實驗設(shè)計及結(jié)果分析

3.1 實驗設(shè)計

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

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

3.1.2 對比實驗

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

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

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

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

3.1.3 評價標(biāo)準(zhǔn)

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

(7)

(8)

(9)

3.2 實驗結(jié)果及分析

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

圖1 參數(shù)α對實驗結(jié)果的影響

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

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

表1 對比實驗結(jié)果 %

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

4 結(jié)束語

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

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