呂海燕，張杰，王麗娜

（海軍航空工程學(xué)院 山東 煙臺 264000）

基于聚類分析的微博用戶標(biāo)簽自動(dòng)生成

呂海燕，張杰，王麗娜

（海軍航空工程學(xué)院 山東 煙臺 264000）

基于用戶發(fā)表的微博內(nèi)容進(jìn)行標(biāo)簽的自動(dòng)生成，主要研究的是基于聚類分析的用戶標(biāo)簽自動(dòng)生成。本文首先介紹用到的關(guān)鍵技術(shù)：聚類技術(shù)和TextTank，提出了Baseline系統(tǒng)，接下來詳細(xì)說明了基于聚類分析的標(biāo)簽自動(dòng)生成方法，最后通過實(shí)驗(yàn)對該方法進(jìn)行了分析和評價(jià)。實(shí)驗(yàn)結(jié)果表明，該方法生成的用戶標(biāo)簽?zāi)軌蛴行У亟鉀Q同義標(biāo)簽的堆積問題，使得生成的標(biāo)簽?zāi)軌蛟诟嗟木S度上體現(xiàn)用戶的興趣。

微博用戶標(biāo)簽；TextRank；聚類分析；Baseline系統(tǒng)

近年來，微博已經(jīng)成為了一種流行的網(wǎng)絡(luò)信息傳播平臺，越來越多的人擁有自己的微博賬戶。微博文本短?。ㄒ话阆拗圃?40個(gè)字以內(nèi)），與手機(jī)、即時(shí)信息服務(wù)軟件的連接使得微博發(fā)布的門檻很低，用戶可以隨時(shí)隨地進(jìn)行更新。隨著我們關(guān)注的人數(shù)越多，信息量越來越大，使我們將面臨“信息過載”的問題。針對這種信息過載的問題，人們開始逐漸關(guān)注微博上的個(gè)性化。而微博用戶標(biāo)簽作為描述用戶興趣愛好、職業(yè)領(lǐng)域等特征的載體，在用戶組織和搜索，挖掘用戶興趣和實(shí)現(xiàn)用戶微博個(gè)性化等方面有著重要的作用[1]。微博用戶標(biāo)簽自動(dòng)生成便是從可利用的資源中自動(dòng)生成短文本例如詞語、短語來描述用戶關(guān)心的內(nèi)容和興趣點(diǎn)[2-4]。其生成方法從生成標(biāo)簽的不同粒度出發(fā)，主要有基于關(guān)鍵詞和基于類別兩種方法[5-8]。本文主要研究基于關(guān)鍵詞的微博用戶標(biāo)簽自動(dòng)生成中基于聚類分析的生成方法。

1 關(guān)鍵技術(shù)

1.1 聚類技術(shù)

聚類是一種將數(shù)據(jù)對象劃分成相似的集合（簇）的過程。常見的聚類技術(shù)可以分為：劃分方法例如K-Means、層次方法例如層次聚類、基于密度的方法、基于網(wǎng)格的方法等等[9]。本文選擇的是層次方法聚類技術(shù)。聚類的思路如下:首先需要對N個(gè)詞語進(jìn)行簇聚類，把每個(gè)詞語都當(dāng)作一個(gè)獨(dú)立的簇，所以初始的時(shí)候?qū)⒂蠳個(gè)簇等待聚類。接下來，對簇進(jìn)行兩兩合并至聚合成一個(gè)簇，合并的依據(jù)是簇之間的距離。通過上述聚類，可以得到一顆具有層次的聚類樹。最后選取聚類效果最好的簇。在進(jìn)行自底向上的層次聚類過程中關(guān)鍵問題是在兩兩逐一合并簇的過程中兩個(gè)簇之間的距離的度量方法。根據(jù)衡量方式的不同，層次聚類劃分為均值距離/平均距離算法、單連接算法、及全連接算法。本文采用的是單連接算法，也稱為最近鄰聚類算法。該算法使用兩個(gè)簇中最近對象的距離作為整個(gè)簇之間的距離，首先確定一個(gè)閥值，當(dāng)這個(gè)距離超過選定的閾值時(shí)候便終止聚類。距離的度量方法公式如（1）所示。其中，對象o1、o2分別屬于簇c1、c2。

1.2 Baseline系統(tǒng)

本文采用TFIDF為候選關(guān)鍵詞排序的策略作為Baseline系統(tǒng)。排序公式如公式（2）所示。

其中，tf（t，u）表示用戶u的微博文本中詞t出現(xiàn)的頻率，U表示微博語料中用戶的總數(shù)，Ut表示微博文本中包含t的用戶數(shù)。

1.3 TextRank

TextRank算法是由Rada Mihalcea等人[10]于2004年提出的用來實(shí)現(xiàn)文本關(guān)鍵詞抽取的算法，其主要思想是一個(gè)詞的重要性由其它與其關(guān)聯(lián)的詞決定。TextRank將微博文檔中的一個(gè)個(gè)詞語類比成互聯(lián)網(wǎng)中的一頁頁網(wǎng)頁，而詞與詞之間的聯(lián)系則類比于網(wǎng)頁與網(wǎng)頁之間的鏈接關(guān)系。即算法將文本表示成是一個(gè)由詞語構(gòu)成的網(wǎng)絡(luò)，用圖來表示則是一個(gè)由詞語作為節(jié)點(diǎn)構(gòu)成的圖，圖中的邊是由詞語間的語義關(guān)系構(gòu)成的。在這樣的圖中越重要的詞越可能是要找的關(guān)鍵詞。每個(gè)節(jié)點(diǎn)vi的TextRank分?jǐn)?shù)計(jì)算如公式（1）-（3）所示。對每一個(gè)節(jié)點(diǎn)vi，In（vi）代表指向它的節(jié)點(diǎn)集合，out（vi）代表它指向的節(jié)點(diǎn)集合。wij代表vi和vj之間邊的權(quán)重。

2 生成方法

2.1 生成流程

基于聚類分析的方法自動(dòng)生成標(biāo)簽，簡單來說，流程大致如圖1所示。

圖1 基于聚類分析的標(biāo)簽自動(dòng)生成流程Fig.1 Automatic generation of micro-blog user tags based on cluster analysise

2.2 生成方法

2.2.1 用戶特征分析

微博用戶分為活躍用戶與不活躍用戶，其中活躍用戶的特征基本相同，即其關(guān)注人數(shù)、粉絲或者發(fā)布的微博數(shù)量都很少。而活躍用戶的特征則不全部相同，有的用戶是關(guān)注人數(shù)多，有的是發(fā)布的微博數(shù)量多。而用戶發(fā)布微博的數(shù)量則能在最大程度上體現(xiàn)其活躍程度，因此在對用戶微博進(jìn)行處理時(shí)以其所發(fā)布的微博數(shù)量作為依據(jù)。

2.2.2 標(biāo)簽生成方法

1）收集用戶發(fā)布的微博得到一個(gè)微博文本集合，對集合進(jìn)行過濾。過濾時(shí)采用如下策略：

2）對上述得到的候選關(guān)鍵（名）詞集合進(jìn)行聚類。聚類的方法有很多，有層次聚類、基于密度的方法和基于網(wǎng)格的方法等。本文采用自底向上的層次聚類對詞語進(jìn)行聚類，具體算法如圖2所示。聚類時(shí)選取的是Top300的能體現(xiàn)用戶絕大多數(shù)興趣詞語集合來作為待聚類的詞語集合。使用的是該Top300的詞語集合的TextRank權(quán)重。

圖2 詞語層次聚類算法Fig.2 Bottom-up agglomerative hierarchical clustering algorithm

3）對聚類生成的簇，選取相應(yīng)的簇代表詞，并進(jìn)行擴(kuò)展。

簇的形成是按照語義相關(guān)度來得到的，即語義相關(guān)度較高的詞語將被聚成一個(gè)簇。接下來對每一個(gè)簇選擇合適的詞來代表它。如何選取簇代表詞，也有很多方法，本文采用的是依據(jù)計(jì)算出來TextRank分?jǐn)?shù)，即選取簇中擁有最高TextRank分?jǐn)?shù)的詞語作為簇代表詞。但是，如此選出來的代表詞還不能完全代表該簇，仍需要進(jìn)行進(jìn)一步的擴(kuò)展，本文采用的是按照TFIDF策略對詞進(jìn)行擴(kuò)展、合并。這里需要注意的是，與代表詞合并的詞語必須出現(xiàn)在同一個(gè)聚類簇中。對如此得到的簇的代表詞，就是本文要得到的自動(dòng)生成的用戶標(biāo)簽的序列。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文以隨機(jī)選擇的50位微博用戶發(fā)布的微博內(nèi)容23680余條作為本文的測試數(shù)據(jù)，他們發(fā)布的平均微博條數(shù)為512條。

3.2 評價(jià)方法

通過觀察微博用戶的標(biāo)簽可以看出，微博用戶為自己添加的標(biāo)簽如：“開朗”、“活潑”、“音樂”、“任性”等這些普遍型的標(biāo)簽，可能并未深入地體現(xiàn)用戶的興趣。瀏覽測試用戶的所有微博內(nèi)容，借助于用戶已經(jīng)為自己添加的標(biāo)簽等進(jìn)行評定。評定的準(zhǔn)則有兩條：一是生成的結(jié)果能否體現(xiàn)用戶的興趣；二是生成的結(jié)果是否適合作為用戶標(biāo)簽。本文為用戶自動(dòng)生成10個(gè)標(biāo)簽，并按照權(quán)重計(jì)算方式進(jìn)行排序。評價(jià)指標(biāo)采用信息檢索領(lǐng)域經(jīng)典的評價(jià)指標(biāo)P@N（如公式（4）所示），表示生成的前N個(gè)用戶標(biāo)簽結(jié)果的準(zhǔn)確率。由于評價(jià)過程比較主觀，因此本文采用兩位評價(jià)者分別對生成的標(biāo)簽進(jìn)行評定。

3.3 聚類終止的條件

聚類什么時(shí)候終止呢，即聚類終止的條件如何設(shè)定。本文采用的是距離閾值，即當(dāng)簇間的距離小于某個(gè)閾值時(shí)聚類停止。關(guān)鍵是如何確定這個(gè)閾值。將50位被測試用戶產(chǎn)生的詞對的互信息分?jǐn)?shù)進(jìn)行排序，通過從高到低的序列可以看出當(dāng)互信息得分不超過8時(shí)，詞對的語義關(guān)聯(lián)已經(jīng)較為微弱。所以，這個(gè)閾值被設(shè)為8、7、6、5、4、3、2、1逐一進(jìn)行比較。通過比較發(fā)現(xiàn)，當(dāng)閾值為6時(shí)，效果普遍較好。因此，本文將閾值K設(shè)為6。聚類效果如表1所示。

表1 詞語聚類示例Tab.1 Sample of the clustering results

3.4 標(biāo)簽自動(dòng)生成效果

表2 標(biāo)簽自動(dòng)生成效果（%）Tab.2 The effect of the automatic generation（%）

選取每個(gè)簇內(nèi)TextRank分?jǐn)?shù)最高的詞語作為該簇的代表詞，進(jìn)行擴(kuò)展。抽取的關(guān)鍵詞，若按照簇內(nèi)TextRank分?jǐn)?shù)加和排序，稱之為cluster-sum；若按照簇內(nèi)TextRank平均值排序，稱之為cluster-avg。

同時(shí)，選取baseline系統(tǒng)與其對照。標(biāo)簽自動(dòng)生成效果如表2所示。其中Pi，1≤i≤10分別代表自動(dòng)生成的每個(gè)標(biāo)簽的評價(jià)指標(biāo)P@N值。

對每一種生成標(biāo)簽的方式，計(jì)算兩位評價(jià)者評價(jià)結(jié)果的一致性，用Cohen’s kappa系數(shù)衡量。Kappa值在-1到1之間，值越大則一致性越好。當(dāng)kappa值超過0.75時(shí)，則說明評定的結(jié)果的一致性是非常好的；kappa值在0.40與0.75之間時(shí)，則說明一致性一般；kappa值低于0.40時(shí)，則說明一致性很差。兩位評價(jià)者評價(jià)的一致性如表3所示。

表3 評價(jià)者1、2對標(biāo)簽生成結(jié)果評定的一致性Tab.3 The consistency of the two evaluations

4 結(jié)束語

微博用戶被允許使用自造的、長度不限的詞語或者短語來描述、標(biāo)識自己。這就是所謂的標(biāo)簽功能。本文從微博內(nèi)容分析的角度出發(fā)，研究了基于聚類分析的微博用戶標(biāo)簽自動(dòng)生成技術(shù)，旨在生成能夠體現(xiàn)用戶興趣的標(biāo)簽。實(shí)驗(yàn)結(jié)果表明，該方法解決了同義標(biāo)簽的堆積問題，使得生成的標(biāo)簽?zāi)軌蛟诟嗟木S度上體現(xiàn)用戶的興趣。

[1]Klaas Dellshaft，Steffen Staab.An Epistemic Dynamic Model for Tagging Systems [C]//In HT’08:Proceedings of the nineteenth ACM conference on Hypertext and hypermedia. 2008:71-78.

[2]Simo Overell，Borkur Sigurbjornsson，Roelof van Zwol. Classifying Tags Using Open Content Resources[C]//WSDM. 2009:64-73.

[3]Manish Gupta，Rui Li，Zhijun Yin，et al.Survey on Social Tagging Techniques[C]//Sigkdd Explorations，2010，12（1）: 58-72.

[4]Heymann P，Garcia Molinay H.Collaborative Creation of Communal Hierarchical Taxonomies in Social Tagging Systems [R].Technical Report InfoLab.Department of Computer Science，StanfordUniversity，Stanford，CA，USA. April，2006:1-5.

[5]Jilin Chen，Rowan Nairn，Les Nelson，et al.Short and tweet: Experiments on Recommending Content from Information Streams [C]//In:Proceedings of the 28th international conference on Human factors in computing systems（CHI’10），New York，NY，USA，ACM，2010:1185-1194.

[6]Hulth A.Improved automatic keyword extraction given more linguistic knowledge[C]//EMNLP.2003:216-223.

[7]劉知遠(yuǎn).基于文檔主題結(jié)構(gòu)的關(guān)鍵詞抽取方法研究[D].北京：清華大學(xué)，2011：6-7.

[8]靳延安.社會(huì)標(biāo)簽推薦技術(shù)與方法研究[D].武漢：華中科技大學(xué)，2011:12-15.

[9]Han J，Kamber M.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2007：206-209.

[10]Mihalcea R，TarauP.Text Rank:Bringing Order into Texts[C] //EMNLP.2004:404-411.

Automatic generation of m icro-blog user tags based on clustering analysis

LV Hai-yan，ZHANG Jie，WANG Li-na
（Naval Aeronautical and Astronautical University，Yantai 264000，China）

The main research is the automatic generation of micro-blog user tags based on cluster analysis.Key technologies used in this paper are introduced firstly；mainly include cluster technology and TextRank.A Baseline system is proposed in order to show the validity of the research proposed by this paper.Then the automatic generation method based on clustering analysis is illustrated detailedly.Finally analyze and evaluate the method by experiments.The experimental results show that the user tags generated by the method can solve the problem of synonymy tags stack，and the tags can reflect the users'interest in more dimensions.

tags for micro-blog users；TextRank；cluster analysis；Baseline system

TN37

A

1674－6236（2015）07-0067-03

2014-06-03 稿件編號：201406007

呂海燕（1983—），女，山東淄博人，碩士，工程師。研究方向：軟件工程。