汪 祥，賈 焰，周 斌，陳儒華，韓 毅

（1.國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙410073；2.北京大學(xué)信息科學(xué)技術(shù)學(xué)院，北京100871）

1 引言

近年來(lái)，以用戶社區(qū)貢獻(xiàn)內(nèi)容為核心的社交網(wǎng)絡(luò)飛速發(fā)展，Youtube、Flickr和新浪微博等是其典型代表。在這些社交媒體中，用戶可以自由地上傳個(gè)性化的文字、圖片、視頻等內(nèi)容，并且其可以使用一些描述性的關(guān)鍵詞（即標(biāo)簽）對(duì)這些內(nèi)容進(jìn)行標(biāo)記，以方便自己和其他用戶閱讀所上傳的內(nèi)容。這些描述性標(biāo)簽的上傳，不僅讓用戶可以更好地組織和訪問(wèn)上傳的內(nèi)容，也方便了系統(tǒng)對(duì)用戶所分享內(nèi)容的檢索。

新浪微博自從2009年8月推出以后，迅速成為中國(guó)訪問(wèn)量最大的微博網(wǎng)站之一，其占中國(guó)微博活動(dòng)總量的87%。截至2012年12月底，新浪微博注冊(cè)用戶已超5億，占中國(guó)微博用戶總量的57%。在新浪微博中，用戶可以給自己打標(biāo)簽，以對(duì)自己的興趣、特點(diǎn)進(jìn)行標(biāo)識(shí)。圖1是前Google中國(guó)區(qū)總裁李開(kāi)復(fù)給自己打的標(biāo)簽。這些標(biāo)簽表明了用戶本身的特點(diǎn)，可以讓別的用戶更好地了解自己和區(qū)別于別人，也給網(wǎng)絡(luò)營(yíng)銷、系統(tǒng)推薦和廣告推送等商業(yè)應(yīng)用提供了良好的契機(jī)。

Figure 1 Lee Kai-fu and his tags圖1 李開(kāi)復(fù)及其標(biāo)簽

在新浪微博中，雖然很多用戶給自己定義了標(biāo)簽，但是也有很多用戶沒(méi)有給自己定義標(biāo)簽。我們使用Sina微博的API爬取了144 210 854個(gè)用戶及其標(biāo)簽并分析了用戶標(biāo)簽數(shù)目的特點(diǎn)。圖2表明了用戶給自己定義的標(biāo)簽數(shù)目和用戶數(shù)目之間的關(guān)系。從圖2中可以看出，沒(méi)有標(biāo)簽的用戶數(shù)目最多，占總用戶總數(shù)的78.2%，標(biāo)簽數(shù)小于5的用戶占用戶總數(shù)的93.8%。如何給沒(méi)有標(biāo)簽或標(biāo)簽較少的用戶進(jìn)行標(biāo)簽預(yù)測(cè)是一個(gè)重要的問(wèn)題。

Figure 2 Statistics of user tags圖2 用戶標(biāo)簽數(shù)目分布

傳統(tǒng)的標(biāo)簽預(yù)測(cè)方法一般分為基于內(nèi)容的標(biāo)簽預(yù)測(cè)方法和與內(nèi)容無(wú)關(guān)的標(biāo)簽預(yù)測(cè)方法，前者主要基于文檔的內(nèi)容進(jìn)行標(biāo)簽預(yù)測(cè)，而后者主要依賴于用戶的歷史標(biāo)簽記錄等。但是，在新興的社交網(wǎng)絡(luò)中，用戶之間通過(guò)關(guān)注／粉絲（好友）關(guān)系、回復(fù)、轉(zhuǎn)發(fā)和提及關(guān)系等構(gòu)成了復(fù)雜的鏈接關(guān)系。Aggarwal C C等人［1］在其文章中指出，如何利用社交網(wǎng)絡(luò)中豐富的鏈接關(guān)系是社交網(wǎng)絡(luò)研究的重要內(nèi)容。本文基于新浪微博中用戶之間的強(qiáng)交互關(guān)系，即用戶之間的轉(zhuǎn)發(fā)和提及關(guān)系構(gòu)建其用戶之間的鏈接關(guān)系，并基于用戶之間的這種鏈接關(guān)系對(duì)用戶的標(biāo)簽進(jìn)行預(yù)測(cè)。

2 相關(guān)工作

在標(biāo)簽系統(tǒng)中，用戶以關(guān)鍵詞或者短語(yǔ)的形式向某種資源添加描述數(shù)據(jù)。Golder S和 Huberman B A［2］分析了標(biāo)簽的特點(diǎn)和不同的用法，將標(biāo)簽分為描述資源主題的標(biāo)簽、描述資源類別的標(biāo)簽、描述資源特征的標(biāo)簽和個(gè)性化分類標(biāo)簽等。Halpin H等人［3］對(duì)資源標(biāo)簽的演化過(guò)程進(jìn)行了分析，發(fā)現(xiàn)一個(gè)資源的熱門標(biāo)簽不會(huì)隨著時(shí)間的改變而改變，標(biāo)簽的使用服從冪律分布。

標(biāo)簽推薦技術(shù)一般可以分為基于內(nèi)容的標(biāo)簽推薦技術(shù)和與內(nèi)容無(wú)關(guān)的標(biāo)簽推薦技術(shù)［4］，也有研究者嘗試將兩者融合在一起以提高算法的性能。在基于內(nèi)容的標(biāo)簽推薦技術(shù)中，Ohkura T等人［5］基于文本分類的方法進(jìn)行標(biāo)簽推薦，使用SVM方法判斷標(biāo)簽是否屬于某文檔，該方法被應(yīng)用于基于標(biāo)簽的網(wǎng)頁(yè)瀏覽輔助系統(tǒng)。Katakis I等人［6］用層次式分類算法進(jìn)行標(biāo)簽推薦，其中每個(gè)標(biāo)簽被認(rèn)為是一個(gè)類別。在與內(nèi)容無(wú)關(guān)的標(biāo)簽推薦技術(shù)中，Xu Z等人［7］提出一種類似于HITS算法的方法，該方法為每個(gè)用戶指定一個(gè)權(quán)威指標(biāo)，以便描述用戶歷史標(biāo)記行為的質(zhì)量。這種方法的結(jié)果通常可以覆蓋多個(gè)層面的信息，其推薦的標(biāo)簽具有較高的使用頻率。Hotho A等人［8］提出的FolkRank算法也被應(yīng)用于標(biāo)簽推薦中［9］，其模擬用戶在資源正文與用戶信息等頁(yè)面之間的跳轉(zhuǎn)過(guò)程，其核心思想是被重要的用戶使用重要的標(biāo)簽標(biāo)注的資源，其自身也是重要的。張斌［9］等嘗試將與內(nèi)容無(wú)關(guān)的標(biāo)簽推薦技術(shù)和基于內(nèi)容的標(biāo)簽推薦技術(shù)融合在一起，提出了一種基于LDA的標(biāo)簽系統(tǒng)生成模型TSM／Forc，用于融合描述標(biāo)簽系統(tǒng)中對(duì)象間關(guān)系和資源的內(nèi)容特征。

Pennacchiotti M 等人［10］提出了一種在社交媒體Twitter上進(jìn)行用戶分類的方法。首先基于機(jī)器學(xué)習(xí)的方法從用戶的描述信息、用戶的發(fā)帖特征和博文內(nèi)容等信息中對(duì)用戶的特征進(jìn)行標(biāo)記；然后基于用戶之間的好友關(guān)系對(duì)得到的標(biāo)記進(jìn)行更新。

在社交媒體Flickr中，圖片可以被標(biāo)記上多個(gè)標(biāo)簽，這些標(biāo)簽是無(wú)序的。很多研究嘗試在Flickr上進(jìn)行標(biāo)簽推薦和基于標(biāo)簽的圖片搜索等。Liu等人［11］嘗試在Flickr中對(duì)無(wú)序的標(biāo)簽進(jìn)行排序，使得標(biāo)簽以不同的權(quán)值表示圖片的內(nèi)容，他們將排序后的標(biāo)簽應(yīng)用于基于標(biāo)簽的圖片檢索、標(biāo)簽推薦、群組推薦等應(yīng)用中，取得的效果比標(biāo)簽沒(méi)有排序時(shí)更好。Xiao等人［12］提出了一種對(duì)圖片的標(biāo)簽進(jìn)行排序的方法，使用潛在語(yǔ)義索引模型來(lái)分析標(biāo)簽之間的相關(guān)性，使用圖形圖像的方法來(lái)分析圖片之間的相關(guān)性，然后使用隨機(jī)游走的方法得到圖片標(biāo)簽的權(quán)值，并依據(jù)此權(quán)值對(duì)標(biāo)簽進(jìn)行排序。

Heymann P 等 人［13］在 圖 書(shū) 標(biāo) 簽 網(wǎng) 站 （del.icio.us）上對(duì)圖書(shū)的標(biāo)簽進(jìn)行預(yù)測(cè)，發(fā)現(xiàn)使用圖書(shū)頁(yè)面的文本內(nèi)容、鏈接描述信息以及臨近圖書(shū)標(biāo)簽信息等就足以對(duì)圖書(shū)的標(biāo)簽進(jìn)行預(yù)測(cè)，其它信息并不能顯著地提高標(biāo)簽預(yù)測(cè)的性能。

在社交網(wǎng)絡(luò)中，不同的用戶對(duì)其他用戶的影響程度是不同的，很多文獻(xiàn)對(duì)用戶之間影響力的計(jì)算方法進(jìn)行了研究。Ding等人［14］嘗試在Twitter中發(fā)現(xiàn)影響力最強(qiáng)的個(gè)體，其在回復(fù)、轉(zhuǎn)發(fā)、評(píng)論和閱讀的多關(guān)系網(wǎng)絡(luò)中進(jìn)行隨機(jī)游走，以衡量一個(gè)用戶的影響力。Cha等人［15］比較了使用入度、轉(zhuǎn)發(fā)和提及計(jì)算用戶影響力的方法，發(fā)現(xiàn)用戶的影響力不是自發(fā)或偶然獲取的，而是通過(guò)不同的努力獲取的。

3 基于用戶交互關(guān)系的標(biāo)簽預(yù)測(cè)方法

3.1 用戶交互關(guān)系圖的構(gòu)建

在新浪微博中，用戶之間的關(guān)系包括關(guān)注／粉絲關(guān)系、評(píng)論關(guān)系、轉(zhuǎn)發(fā)關(guān)系、提及關(guān)系（＠某用戶），其中關(guān)注／粉絲關(guān)系屬于靜態(tài)關(guān)系，而評(píng)論關(guān)系、轉(zhuǎn)發(fā)關(guān)系和提及關(guān)系屬于用戶交互而產(chǎn)生的關(guān)系，具有動(dòng)態(tài)性。用戶之間的這種交互關(guān)系是一種比關(guān)注／粉絲關(guān)系更強(qiáng)的關(guān)系，反映了用戶之間對(duì)某特定話題的共同興趣。在標(biāo)簽推薦方法中，我們認(rèn)為標(biāo)簽可以借助這種反映用戶之間共同興趣的交互關(guān)系而得到傳播。

為了研究方便，我們使用一個(gè)加權(quán)有向圖G＝（V，E，W）來(lái)表示用戶之間的交互關(guān)系構(gòu)成的交互圖。對(duì)于一個(gè)特定的用戶ui，在新浪微博中會(huì)有不超過(guò)十個(gè)標(biāo)簽來(lái)對(duì)用戶的特征進(jìn)行描述，如圖1中李開(kāi)復(fù)的標(biāo)簽。本文使用Tui來(lái)表示用戶ui的標(biāo)簽集合，使用wuitj來(lái)表示用戶ui和標(biāo)簽tj之間的相關(guān)度，其中tj∈Tui。在初始情況下，用戶標(biāo)簽的初始權(quán)值都相等，為1／Tui。本文使用Wui來(lái)表示用戶ui的所有標(biāo)簽與ui的相關(guān)程度的集合，那么，在交互圖G ＝ （V，E，W）中，一個(gè)頂點(diǎn)vi（vi∈V）可以表示為vi＝ （ui，Tui，Wui）。

在交互圖G＝（V，E，W）中，頂點(diǎn)之間的邊為用戶之間的交互關(guān)系，即評(píng)論、轉(zhuǎn)發(fā)和提及關(guān)系。一個(gè)用戶ui如果評(píng)論、轉(zhuǎn)發(fā)或者提及了用戶uj，那么我們認(rèn)為在圖G中有一條從用戶uj到用戶ui的有向邊，在交互圖G中即一條從vj到vi的有向邊eji（vj→vi）。邊的權(quán)值的大小反映了標(biāo)簽從一個(gè)頂點(diǎn)轉(zhuǎn)移到另一個(gè)頂點(diǎn)的概率，轉(zhuǎn)移概率的計(jì)算方法將在下一節(jié)詳細(xì)討論。

3.2 標(biāo)簽在交互圖中的傳播

在交互圖G＝（V，E，W）中，用戶之間通過(guò)交互關(guān)系構(gòu)建起了兩者之間的連接。用戶之間的交互關(guān)系說(shuō)明了用戶之間有共同感興趣的話題，用戶ui評(píng)論、轉(zhuǎn)發(fā)和提及用戶uj說(shuō)明用戶ui受到了用戶uj的影響，那么，是用戶uj的標(biāo)簽向用戶ui傳播呢？還是用戶ui的標(biāo)簽向用戶uj傳播呢？本文認(rèn)為，如果用戶ui評(píng)論、轉(zhuǎn)發(fā)和提及用戶uj，可以認(rèn)為用戶uj影響了用戶ui，即用戶uj的標(biāo)簽可以向用戶ui傳播。另外，如果ui評(píng)論、轉(zhuǎn)發(fā)和提及用戶uj，也可以認(rèn)為用戶ui的標(biāo)簽驗(yàn)證了用戶uj的標(biāo)簽，即標(biāo)簽可以從用戶ui傳播到用戶uj。從上面的論述可以看出，如果用戶ui評(píng)論、轉(zhuǎn)發(fā)和提及用戶uj，那么標(biāo)簽既可以從用戶ui傳播到用戶uj，也可以從用戶uj傳播到用戶ui，還可以在兩者之間進(jìn)行雙向傳播。本文在后面的實(shí)驗(yàn)中嘗試了上述三種傳播方向，以論證哪種傳播方法是最有效的。

本文將討論如何計(jì)算節(jié)點(diǎn)間的標(biāo)簽轉(zhuǎn)移概率。在交互圖G中，使用用戶之間的評(píng)論、轉(zhuǎn)發(fā)和提及關(guān)系數(shù)計(jì)算邊eji（vj→vi）的權(quán)值。邊eji（vj→vi）的權(quán)值反映了用戶之間的影響強(qiáng)度，如果用戶ui評(píng)論、轉(zhuǎn)發(fā)和提及用戶uj的次數(shù)越多，則ui對(duì)uj的影響強(qiáng)度越大，即ui和uj的標(biāo)簽有更大的概率在彼此之間進(jìn)行傳播。在計(jì)算標(biāo)簽從用戶ui轉(zhuǎn)移到uj的轉(zhuǎn)移概率tran（uj→ui）時(shí)，用戶之間的評(píng)論、轉(zhuǎn)發(fā)和提及關(guān)系都認(rèn)為是相同的關(guān)系而不加區(qū)分。

本文采用兩種方法來(lái)計(jì)算用戶間標(biāo)簽的轉(zhuǎn)移概率。第一種方法的計(jì)算公式如式（1）所示：

其中，fcomm（ui，uj）表示用戶ui評(píng)論、轉(zhuǎn)發(fā)和提及用戶uj的總次數(shù)，commSet（ui）表示所有被ui評(píng)論、提及和轉(zhuǎn)發(fā)的用戶集合。從式（1）中可知tran（vj→vi）滿足0≤tran（uj→ui）≤1。

第二種方法的計(jì)算公式如式（2）所示：

其中，fcomm（ui，uj）表示用戶ui評(píng)論、轉(zhuǎn)發(fā)和提及用戶uj的總次數(shù)，commSet′（uj）表示所有評(píng)論、提及和轉(zhuǎn)發(fā)了用戶uj的用戶集合。從式（2）可知tran（uj→ui）滿足0≤tran（uj→ui）≤1。

3.3 用戶標(biāo)簽的更新

在圖G＝（V，E，W）中，一個(gè)用戶ui可以和多名用戶之間產(chǎn)生交互關(guān)系，這些與之交互的用戶的標(biāo)簽將以一定的轉(zhuǎn)移概率傳播到用戶ui。假設(shè)與用戶ui擁有交互關(guān)系并將標(biāo)簽傳播到用戶ui的用戶集合為tranSet（ui），那么，傳播到用戶ui的標(biāo)簽集合tagSet（ui）滿足式（3）描述的條件：

如果用戶集合tranSet（ui）中的用戶數(shù)量很大，那么標(biāo)簽集合tagSet（ui）的數(shù)量將會(huì)非常大，因?yàn)槊總€(gè)用戶都有自己不同的標(biāo)簽。通常我們選取top-k個(gè)標(biāo)簽作為用戶ui的標(biāo)簽。標(biāo)簽的權(quán)值等于所有相關(guān)用戶當(dāng)前標(biāo)簽的權(quán)值乘以其轉(zhuǎn)移概率后所得值之和，標(biāo)簽tm（tm∈tagSet（ui））的權(quán)值采用式（4）進(jìn)行計(jì)算：

在實(shí)驗(yàn)中，我們將k的值設(shè)定為20，即只保留用戶的top-20個(gè)標(biāo)簽。

式（1）和式（2）給出了用戶之間標(biāo)簽轉(zhuǎn)移概率的計(jì)算方法。結(jié)合之前討論的標(biāo)簽的傳播方向的不同，得到以下幾種標(biāo)簽傳播方法：

（1）如果用戶ui轉(zhuǎn)發(fā)或提及了用戶uj，那么用戶uj的標(biāo)簽以根據(jù)式（1）計(jì)算得到的轉(zhuǎn)移概率傳播到用戶ui。

（2）如果用戶ui轉(zhuǎn)發(fā)或提及了用戶uj，那么用戶uj的標(biāo)簽以根據(jù)式（2）計(jì)算得到的轉(zhuǎn)移概率傳播到用戶ui。

（3）如果用戶ui轉(zhuǎn)發(fā)或提及了用戶uj，那么用戶ui的標(biāo)簽以根據(jù)式（1）計(jì)算得到的轉(zhuǎn)移概率傳播到用戶uj。

（4）如果用戶ui轉(zhuǎn)發(fā)或提及了用戶uj，那么用戶ui的標(biāo)簽以根據(jù)式（2）計(jì)算得到的轉(zhuǎn)移概率傳播到用戶uj，而且用戶uj的標(biāo)簽以根據(jù)式（2）計(jì)算得到的轉(zhuǎn)移概率傳播到用戶ui，這樣標(biāo)簽將在擁有交互關(guān)系的用戶之間雙向傳播。

（5）這種方法是目前最常用的方法，其將周邊所有用戶的標(biāo)簽作為自己的標(biāo)簽，我們將此方法作為Baseline方法。此方法可以描述如下：如果用戶ui轉(zhuǎn)發(fā)或提及了用戶uj，那么用戶ui的標(biāo)簽以1的轉(zhuǎn)移概率傳播到用戶uj，而且用戶uj的標(biāo)簽以1的轉(zhuǎn)移概率傳播到用戶ui，標(biāo)簽將在擁有交互關(guān)系的用戶之間雙向傳播。標(biāo)簽在傳播過(guò)程中不考慮標(biāo)簽在原用戶處的權(quán)值。

上述五種方法中標(biāo)簽在網(wǎng)絡(luò)中不斷迭代傳播，直至算法達(dá)到一個(gè)穩(wěn)定的狀態(tài)。

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

4.1 新浪微博數(shù)據(jù)集

新浪微博是基于用戶關(guān)系的信息分享、傳播以及獲取信息的平臺(tái)，是目前國(guó)內(nèi)訪問(wèn)量最大的網(wǎng)站之一。新浪微博開(kāi)放平臺(tái)提供了訪問(wèn)新浪微博平臺(tái)的API接口，用戶可以通過(guò)API接口獲取網(wǎng)站內(nèi)容。本文基于新浪微博的API接口爬取了新浪微博的轉(zhuǎn)發(fā)、提及關(guān)系以及用戶的標(biāo)簽等信息，統(tǒng)計(jì)如表1所示。

Table 1 Statistics of sina weibo dataset表1 新浪微博數(shù)據(jù)集統(tǒng)計(jì)

圖3顯示了本數(shù)據(jù)集中標(biāo)簽出現(xiàn)的頻次與標(biāo)簽個(gè)數(shù)之間的關(guān)系。從圖3可以看出，絕大部分的標(biāo)簽出現(xiàn)的頻次較少，而出現(xiàn)頻次較多的標(biāo)簽的數(shù)目也很少。78.87%的用戶標(biāo)簽只出現(xiàn)了一次，93.84%的用戶標(biāo)簽出現(xiàn)的次數(shù)不大于5，所以在新浪微博中只有很少一部分標(biāo)簽是大家都采用的標(biāo)簽。

圖4顯示了本數(shù)據(jù)中用戶轉(zhuǎn)發(fā)、提及其他用戶的數(shù)目與用戶個(gè)數(shù)之間關(guān)系的特征。從圖4可以發(fā)現(xiàn)，絕大多數(shù)用戶轉(zhuǎn)發(fā)、提及其他用戶的數(shù)目較少。71.2%的用戶轉(zhuǎn)發(fā)、提及其他用戶的數(shù)目不大于5，而75.45%的用戶轉(zhuǎn)發(fā)、提及其他用戶的數(shù)目不大于10。

4.2 MapReduce并行處理框架和測(cè)試集的構(gòu)建

從表1中可以看出，待處理的數(shù)據(jù)集非常大，節(jié)點(diǎn)數(shù)超過(guò)了1.4億，用戶邊數(shù)超過(guò)了30億，單機(jī)處理如此龐大的數(shù)據(jù)對(duì)于普通的機(jī)器來(lái)說(shuō)難以實(shí)現(xiàn)，我們采用MapReduce并行處理框架來(lái)實(shí)現(xiàn)本文提出的算法。實(shí)驗(yàn)采用了24個(gè)節(jié)點(diǎn)的Hadoop集群，Hadoop集群中的每個(gè)節(jié)點(diǎn)采用的是Intel（R）Xeon（R）4核處理器和32GB內(nèi)存。

本文構(gòu)建了測(cè)試集來(lái)測(cè)試算法的性能。測(cè)試集的構(gòu)建方法是將一定數(shù)量的標(biāo)簽數(shù)大于8的用戶的標(biāo)簽刪去，用本文提出的方法來(lái)給這些刪除標(biāo)簽的用戶打上標(biāo)簽，最后將算法得到的標(biāo)簽與用戶自己標(biāo)記的原始標(biāo)簽進(jìn)行比較。本文選取了三組測(cè)試集，每組數(shù)據(jù)集都包含3 000個(gè)用戶。為了保證測(cè)試集數(shù)據(jù)選取的隨機(jī)性，采用隨機(jī)數(shù)的方法來(lái)判定某一符合條件的數(shù)據(jù)是否加入測(cè)試集中。第一組測(cè)試集包含3 000個(gè)轉(zhuǎn)發(fā)（或提及）其他用戶的總數(shù)在50～60之間且被其他用戶轉(zhuǎn)發(fā)（或提及）的總數(shù)也在50～60之間的用戶；第二組測(cè)試集包含3 000個(gè)轉(zhuǎn)發(fā)（或提及）其他用戶的總數(shù)在100～150之間且被其他用戶轉(zhuǎn)發(fā)（或提及）的總數(shù)也在100～150之間的用戶；第三組測(cè)試集包含3 000個(gè)轉(zhuǎn)發(fā)（或提及）其他用戶的總數(shù)在300以上且被其他用戶轉(zhuǎn)發(fā)（或提及）的總數(shù)也在300以上的用戶。

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

本文對(duì)3.3節(jié)中描述的五種方法進(jìn)行了實(shí)驗(yàn)，并采用前N條結(jié)果的準(zhǔn)確率P＠N和前N條結(jié)果的召回率R＠N來(lái)對(duì)算法的性能進(jìn)行評(píng)價(jià)。

表2～表4分別顯示了這五種方法在第一組、第二組和第三組測(cè)試集上的性能評(píng)價(jià)結(jié)果。由于新浪微博中用戶最多允許的標(biāo)簽數(shù)為10，因此在P＠N 上只選取了P＠1／P＠3／P＠6和P＠10，在召回率上只選取了R＠20作為評(píng)測(cè)指標(biāo)。

Table 2 Performance of algorithms in dataset 1表2 算法在第一組測(cè)試集上的性能

Table 3 Performance of algorithms in dataset 2表3 算法在第二組測(cè)試集上的性能

Table 4 Performance of algorithms in dataset 3表4 算法在第三組測(cè)試集上的性能

從表2～表4可以看出，方法（4）在三組數(shù)據(jù)集上的各項(xiàng)評(píng)價(jià)指標(biāo)都獲得了最好的結(jié)果。Baseline方法（方法（5））比方法（4）在所有測(cè)試集的各項(xiàng)參數(shù)上都要差，但是比方法（1）和方法（3）都要好。方法（2）并不是在所有測(cè)試集上都比Baseline方法差（方法（5）），如在交互關(guān)系較多的第三組測(cè)試集上的P＠1和P＠3比Baseline方法好。

圖5顯示了五種方法在一個(gè)特定評(píng)價(jià)指標(biāo)（P＠1、P＠3、P＠6、P＠10、R＠20）上的變化趨勢(shì)，從圖5和表2、表3、表4的數(shù)據(jù)中發(fā)現(xiàn)，從測(cè)試集1到測(cè)試集3，除了方法3不是很明顯之外，其余算法的各項(xiàng)評(píng)價(jià)指標(biāo)顯示的性能都在下降。我們知道，從測(cè)試集1到測(cè)試集3，用戶與其他用戶交互的總數(shù)在不斷提高，從交互的用戶總數(shù)為50～60，到100～150，再到最后300以上。算法結(jié)果顯示，性能的提高并不與同用戶交互的用戶數(shù)目的多少成正比，除了方法（3）不明顯外，其余算法的各項(xiàng)評(píng)價(jià)指標(biāo)的性能隨著交互關(guān)系的遞增而變差。從圖3可知，只有6.18%的用戶標(biāo)簽的使用頻率在5次以上，93.84%的用戶標(biāo)簽都少于5人使用。絕大部分標(biāo)簽被很少的用戶使用，導(dǎo)致了交互關(guān)系越多的用戶接收到“噪音”標(biāo)簽的機(jī)會(huì)越大，這也就是導(dǎo)致算法在交互關(guān)系越多的用戶上反而性能下降的原因。

5 結(jié)束語(yǔ)

Figure 5 Performance transformation of five algorithms圖5 五種方法性能變化趨勢(shì)

本文針對(duì)新浪微博中絕大多數(shù)用戶沒(méi)有給自己打標(biāo)簽或標(biāo)簽較少的問(wèn)題，提出了基于用戶交互行為的微博用戶標(biāo)簽預(yù)測(cè)方法?；谟脩艚换バ袨檗D(zhuǎn)發(fā)、提及而形成的強(qiáng)用戶關(guān)系，提出了基于用戶交互圖的標(biāo)簽預(yù)測(cè)算法，分析了多種基于用戶交互行為的用戶標(biāo)簽預(yù)測(cè)方法，并在真實(shí)的大數(shù)據(jù)集上對(duì)算法性能進(jìn)行了測(cè)試。結(jié)果顯示，本文所提方法取得了良好的效果，比當(dāng)前常用的將周邊所有用戶的標(biāo)簽作為用戶標(biāo)簽的方法取得了更好的性能。由于新浪微博中絕大部分的用戶標(biāo)簽使用頻率非常低而導(dǎo)致在標(biāo)簽預(yù)測(cè)過(guò)程中“噪音”標(biāo)簽很多，算法的性能并沒(méi)有隨著用戶與其它用戶交互行為的增多而提高，在多個(gè)算法中，算法的性能反而隨著用戶交互行為的增多而下降。

在本文中，我們只研究用戶之間的交互關(guān)系，在以后的研究中，我們將進(jìn)一步考慮用戶之間的靜態(tài)關(guān)注／粉絲關(guān)系。

致謝 感謝湖南蟻坊軟件公司為本文實(shí)驗(yàn)提供的Hadoop集群實(shí)驗(yàn)環(huán)境，感謝蟻坊軟件公司李錦澤、汪云、諶志雄等提供的寶貴建議和技術(shù)支持。向?qū)Ρ疚牡墓ぷ鹘o予支持和建議的同行，尤其是國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院國(guó)產(chǎn)基礎(chǔ)軟件工程研究中心681教研室的老師和同學(xué)表示感謝。

［1］ Aggarwal C C，Wang H X.Text mining in social networks［M］∥Social Network Data Analytics，NY：Springer，2011：353-378.

［2］ Golder S，Huberman B A.The structure of collaborative tagging systems［J］.Journal of Information Science，2006，32（2）：198-208.

［3］ Halpin H，Robu V，Shepherd H.The complex dynamics of collaborative tagging［C］∥Proc of the 16th International Conference on World Wide Web，2007：211-220.

［4］ Si Xian-ce.Content-based recommendation and analysis of social tags［D］.Beijing：Tsinghua University，2010.（in Chinese）

［5］ Ohkura T，Kiyota Y，Nakagawa H.Browsing system for weblog articles based on automated folksonomy［C］∥Proc of the 3rd European on the Semantic Web：Research and Applications，2006：1.

［6］ Katakis I，Tsoumakas G，Vlahavas I.Multilabel text classification for automated tag suggestion［C］∥Proc of the ECML／PKDD-08Workshop on Discovery Challenge，2008：1.

［7］ Xu Z，F(xiàn)u Y，Mao J，et al.Towards the semantic web：Collaborative tag suggestions［C］∥Proc of the Collaborative Web Tagging Workshop at WWW2006，2006：5.

［8］ Hotho A，J?chke R，Schmitz C，et al.Information retrieval in folksonomies：Search and ranking［C］∥Proc of the 3rd European on the Semantic Web：Research and Applications，2006：411-426.

［9］ Zhang Bin，Zhang Yi，Gao Ke-ning，et al.Combining relation and content analysis for social tagging recommendation［J］.Journal of Software，2012，23（3）：476-488.（in Chinese）

［10］ Pennacchiotti M，Popescu A-M.Democrats，republicans and starbucks afficionados：User classification in Twitter［C］∥Proc of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2011：430-438.

［11］ Liu D，Hua X-S，Yang L，et al.Tag ranking［C］∥Proc of of the 18th International Conference on World Wide Web，2009：351-360.

［12］ Xiao J，Zhou W，Tian Q.Exploring tag relevance for image tag reranking［C］∥Proc of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval，2012：1069-1070.

［13］ Heymann P，Ramage D，Garcia-Molina H.Social tag prediction［C］∥Proc of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2008：531-538.

［14］ Ding Zhao-yun，Yan Jia，Bin Zhou，et al.Mining topical influencers based on the multi-relational network in microblogging sites［J］.China Communications，2013，10（1）：93-104.

［15］ Cha M，Haddadi H，Benevenuto F，et al.Measuring user influence in Twitter：The million follower fallacy［C］∥Proc of the 4th International Conference on Weblogs and Social Media，2010：11-13.

附中文參考文獻(xiàn)：

［4］ 司憲策.基于內(nèi)容的社會(huì)標(biāo)簽推薦與分析研究 ［D］.北京：清華大學(xué)，2010.

［9］ 張斌，張引，高克寧，等.融合關(guān)系與內(nèi)容分析的社會(huì)標(biāo)簽推薦 ［J］.軟件學(xué)報(bào)，2012，23（3）：476-488.