面向用戶興趣與社區(qū)關(guān)系的微博話題檢測(cè)方法

劉志雄，賈彩燕

(1.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044； 2.北京交通大學(xué) 交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044)

?

面向用戶興趣與社區(qū)關(guān)系的微博話題檢測(cè)方法

劉志雄1,2，賈彩燕1,2

(1.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044； 2.北京交通大學(xué) 交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044)

摘要：微博話題檢測(cè)是一種特殊形式的話題檢測(cè)，傳統(tǒng)的話題檢測(cè)方法并不能取得很好的效果。提出了一種面向微博用戶社區(qū)的話題檢測(cè)方法。該方法首先在用戶發(fā)表的微博文本上，利用LDA主題模型分析用戶的興趣分布。接著，結(jié)合微博用戶關(guān)系網(wǎng)絡(luò)與用戶興趣對(duì)用戶進(jìn)行社區(qū)劃分，使得同一社區(qū)的用戶不僅具有較稠密的鏈接關(guān)系，還具有相似的興趣。然后，面向用戶社區(qū)，在每個(gè)社區(qū)內(nèi)部檢測(cè)用戶關(guān)心的話題，給出了一種面向用戶社區(qū)的、融合詞重要度與ε近鄰圖的微博話題發(fā)現(xiàn)方法。該算法能夠有效地去除微博噪聲、快速準(zhǔn)確檢測(cè)出每個(gè)用戶社區(qū)內(nèi)關(guān)心的話題并對(duì)話題進(jìn)行熱度排行。

關(guān)鍵詞：微博；社區(qū)；網(wǎng)絡(luò)；文本；話題；興趣；噪聲；主題

在信息爆炸時(shí)代，從海量數(shù)據(jù)中挖掘出有用的信息顯得格外重要。隨著Web2.0的興起，微博客即微博，這種基于用戶關(guān)系與短文本特性的信息分享、傳播以及獲取的平臺(tái)也隨之興起。微博用戶可以通過PC端、手機(jī)端以及其他客戶端組建個(gè)人社區(qū)，以140字左右的文字更新信息，并實(shí)現(xiàn)即時(shí)分享。微博成為典型的Web2.0應(yīng)用之一。

在現(xiàn)實(shí)世界中，有很多系統(tǒng)都可以抽象為網(wǎng)絡(luò)，這些網(wǎng)絡(luò)中包含著一些潛在的社區(qū)結(jié)構(gòu)，具有社區(qū)內(nèi)部節(jié)點(diǎn)鏈接稠密、社區(qū)之間節(jié)點(diǎn)鏈接稀疏的特點(diǎn)。通常，社區(qū)內(nèi)部的節(jié)點(diǎn)具有相似的特性，在網(wǎng)絡(luò)中扮演著相似的角色。對(duì)于微博用戶關(guān)系網(wǎng)而言：同一社區(qū)內(nèi)的用戶往往具有相同或者相似的興趣與愛好。

目前對(duì)于微博的研究大多是對(duì)用戶關(guān)系的分析或者微博內(nèi)容的分析。在用戶關(guān)系研究領(lǐng)域，主要研究其社區(qū)特性。大體思路是：以用戶ID為節(jié)點(diǎn)，用戶關(guān)注關(guān)系為邊構(gòu)建用戶關(guān)系網(wǎng)絡(luò)圖，然后采用社區(qū)劃分算法將其劃分為若干社區(qū)。往往同一社區(qū)內(nèi)的用戶擁有共同的興趣與愛好。在微博內(nèi)容分析方面，致力于研究微博話題發(fā)現(xiàn)方法。大體思路是：以詞為特征使用VSM[3]模型將微博文本轉(zhuǎn)化為空間向量，并且使用TF-IDF算法計(jì)算每一維的權(quán)重，然后使用聚類方法將相同話題下的微博文本聚集成一個(gè)個(gè)微博話題簇。例如：周剛等[4]提出了一種基于組合相似度的微博話題發(fā)現(xiàn)方法MB-SinglePass來提升聚類效果，他們將余弦相似度、雅各比相似度、語義相似度以一定的權(quán)值融合，改進(jìn)了微博相似度的計(jì)算方法；鄭斐然等[5]提出了一種基于詞聚類的新聞話題發(fā)現(xiàn)方法；方然等[6]提出了一種基于情感的微博話題檢測(cè)方法，他們認(rèn)為傾向消極的詞更加具有話題表現(xiàn)力，從而依據(jù)詞的情感分?jǐn)?shù)改善了話題檢測(cè)效果。然而微博文本被嚴(yán)格限制在140字以內(nèi)，單純地使用VSM[3]空間向量模型對(duì)微博文本進(jìn)行建模，存在嚴(yán)重的特征稀疏和維度過高問題。更嚴(yán)重的是聚類結(jié)果還受到微博噪聲的影響，導(dǎo)致話題檢測(cè)的效果不理想。

本文提出了一種面向用戶興趣與社區(qū)關(guān)系的微博話題檢測(cè)方法,首先應(yīng)用LDA[1]主題模型對(duì)微博文本進(jìn)行降維，以用戶微博在主題上的分布來表征用戶的興趣與愛好；然后，結(jié)合用戶興趣特征對(duì)用戶關(guān)系網(wǎng)進(jìn)行社區(qū)劃分，使得同一社區(qū)內(nèi)的用戶不僅具有稠密鏈接的社區(qū)關(guān)系，還具有相似的興趣；最后，使用了一種融合詞重要度與ε近鄰圖[2]的微博話題檢測(cè)方法得出每個(gè)社區(qū)(主題)對(duì)應(yīng)的話題，并實(shí)現(xiàn)相關(guān)社區(qū)內(nèi)的話題熱度排行。實(shí)驗(yàn)結(jié)果顯示，該算法有效地對(duì)微博特征空間進(jìn)行了降維、微博去噪，使得相似度的計(jì)算更加容易；實(shí)現(xiàn)了社區(qū)內(nèi)的微博話題檢測(cè)，以挖掘出社區(qū)內(nèi)的用戶共同關(guān)心的話題，話題檢測(cè)結(jié)果更加迎合社區(qū)內(nèi)的用戶興趣與愛好，便于進(jìn)行面向社區(qū)興趣的話題推薦和排行。

1基于用戶社區(qū)興趣的話題發(fā)現(xiàn)方法

本文提出的微博話題檢測(cè)方法以中文微博為處理對(duì)象，分為如下4個(gè)步驟：數(shù)據(jù)預(yù)處理、網(wǎng)絡(luò)建模、用戶社區(qū)發(fā)現(xiàn)、微博話題檢測(cè)(流程如圖1)。其中，數(shù)據(jù)預(yù)處理主要對(duì)微博數(shù)據(jù)進(jìn)行篩選和切詞，并且過濾掉停用詞以及微博平臺(tái)常見的噪聲。例如：“轉(zhuǎn)發(fā)微博”、“分享圖片”、“視頻”等，然后采用基于吉布斯采樣[7]的LDA[1]主題模型對(duì)用戶微博進(jìn)行降維處理，以得到用戶的興趣分布。網(wǎng)絡(luò)建模是以用戶ID為節(jié)點(diǎn)，用戶關(guān)注關(guān)系為邊，構(gòu)建網(wǎng)絡(luò)模型。用戶社區(qū)發(fā)現(xiàn)主要結(jié)合LDA模型提取的用戶興趣特征，對(duì)用戶關(guān)系網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，使得找到的社區(qū)內(nèi)的用戶對(duì)相似的話題感興趣。話題發(fā)現(xiàn)：利用社區(qū)劃分結(jié)果，對(duì)社區(qū)內(nèi)微博進(jìn)行話題檢測(cè)，挖掘出社區(qū)內(nèi)關(guān)心的話題，并對(duì)社區(qū)內(nèi)的話題進(jìn)行熱度排行。

圖1　算法流程Fig.1　flow of algorithm

1.1數(shù)據(jù)預(yù)處理

微博是一種非結(jié)構(gòu)化數(shù)據(jù)，攜帶信息具有碎片化的特征。并且，攜帶著大量的垃圾信息(噪聲)，使得對(duì)微博數(shù)據(jù)的預(yù)處理是微博數(shù)據(jù)分析的重要前提。主要分為以下2個(gè)方面：1)針對(duì)微博用戶的處理規(guī)則，2)針對(duì)微博文本內(nèi)容的處理規(guī)則。

1)針對(duì)微博用戶

由于某些用戶發(fā)表微博數(shù)目較少，并不能很好地反映用戶的興趣，故選取發(fā)表微博總長(zhǎng)度大于5 000的用戶及其關(guān)注關(guān)系作為我們的數(shù)據(jù)集。

2)針對(duì)微博內(nèi)容

分詞：漢語中詞是最小、能獨(dú)立活動(dòng)、有意義的語言成分，但不像英語或者其他語言中詞語之間有明顯的空格加以區(qū)分。因此分詞是微博內(nèi)容處理的關(guān)鍵一步，分詞的方法有多種，如基于字符串匹配的分詞方法、基于統(tǒng)計(jì)的分詞方法等。本文采用一種基于最大匹配算法的中文單詞識(shí)別系統(tǒng)(a word identification system for mandarin chinese text based on two variants of the maximum matching algorithm，MMSEG)進(jìn)行分詞，MMSEG算法是一種簡(jiǎn)單、高效的基于詞典的中文分詞算法。

去停用詞：停用詞是指在自然語言中具有一定功能但又沒有什么實(shí)際意義的詞。這些詞往往以較高的頻率出現(xiàn)，會(huì)對(duì)文本處理造成一定干擾。另外，微博文本中常會(huì)出現(xiàn)一些高頻詞，如：“轉(zhuǎn)發(fā)”、“微博”、“分享”、“圖片”等，這些高頻詞會(huì)對(duì)話題檢測(cè)產(chǎn)生較強(qiáng)的干擾，也需要和停用詞一起加以過濾。

經(jīng)過以上預(yù)處理步驟，我們過濾掉了一部分噪聲。但即便如此，以詞來表征微博文本的特征向量的維度也是巨大的，會(huì)嚴(yán)重影響微博文本相似度計(jì)算的效率以及有效性。

3)基于微博文本的用戶興趣特征抽取

為了學(xué)習(xí)用戶的興趣特征，如果以用戶發(fā)表的微博文本上的詞為特征，則會(huì)面臨維數(shù)災(zāi)難，我們將一個(gè)用戶發(fā)表的所有微博合并為一個(gè)長(zhǎng)的文本，用以表征用戶的興趣，采用基于吉布斯采樣法[7]的LDA[1]主題模型進(jìn)行降維。將用戶的興趣表示為其在有限個(gè)主題上的分布向量。

1.2網(wǎng)絡(luò)建模

1.2.1建模

本文使用有向無權(quán)圖表示用戶關(guān)系網(wǎng)。每一個(gè)用戶作為圖中的一個(gè)節(jié)點(diǎn)，為每一個(gè)節(jié)點(diǎn)都分配一個(gè)ID，ID值從1～n，用戶之間的關(guān)注關(guān)系作為圖的邊。如果用戶i(ID為i的用戶)關(guān)注了用戶j，則有一條由節(jié)點(diǎn)i指向節(jié)點(diǎn)j的有向邊。

1.2.2相似度構(gòu)造方式

1) 鏈接屬性相似度度量

文獻(xiàn)[19]提出了一種采用信號(hào)傳遞方法將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)換成一個(gè)N維歐式空間上的幾何向量結(jié)構(gòu)，N是網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。我們以該幾何向量作為節(jié)點(diǎn)的鏈接屬性向量。

2) 內(nèi)容屬性相似度度量

用戶微博通過LDA[1]主題模型降維后，可以得到一個(gè)該用戶對(duì)應(yīng)微博文檔在主題上的分布向量，以該向量表示節(jié)點(diǎn)的內(nèi)容特征向量。

3) 聯(lián)合相似度

本文采用余弦相似度計(jì)算兩個(gè)節(jié)點(diǎn)的鏈接和內(nèi)容相似度，公式為

(1)

如果將鏈接相似度表示為simt(simt由鏈接屬性向量采用式(1)求得)，將內(nèi)容相似度表示為simc(simc由內(nèi)容特征向量采用式(1)求得)，那么鏈接與內(nèi)容相結(jié)合的聯(lián)合相似度可表示為simu，simu計(jì)算公式為

(2)

式中α∈[0，1]表示鏈接相似度在聯(lián)合相似度中占的比例。由于參數(shù)α的選取通常很困難，故在社區(qū)劃分過程中采用投票機(jī)制來規(guī)避這一缺陷，詳情見文獻(xiàn)[8]。

1.3用戶社區(qū)劃分

以用戶ID為節(jié)點(diǎn)構(gòu)建的用戶關(guān)系網(wǎng)中，同一社區(qū)內(nèi)的用戶，通常具有相同或相似的愛好。因此，結(jié)合用戶的鏈接關(guān)系和用戶的興趣分布，對(duì)用戶進(jìn)行聚類，也稱為用戶社區(qū)劃分。

本文延用我們?cè)O(shè)計(jì)的社區(qū)劃分方法KRLC[8]對(duì)微博用戶進(jìn)行社區(qū)劃分。具體過程如下：

1)選取中心節(jié)點(diǎn)

采用K-rank[9]算法選取初始中心節(jié)點(diǎn)，即中心節(jié)點(diǎn)不但要具有大的PageRank值，中心節(jié)點(diǎn)間的相似度要盡可能小。

2)社區(qū)劃分

采用K-means[11]算法進(jìn)行社區(qū)劃分，過程如下：

輸入用戶網(wǎng)絡(luò)G，用戶微博長(zhǎng)文本集LD，社區(qū)數(shù)K；

輸出劃分好的社區(qū)列表CommunityList。

①運(yùn)行Signal[19]方法將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)轉(zhuǎn)換成一個(gè)N維歐式空間上的幾何向量。

②運(yùn)行Gibbs-sampling-LDA[1]方法將節(jié)點(diǎn)的微博文檔映射到K維特征空間(表示用戶在K個(gè)主題上的興趣分布)；

③采用K-means[11]算法進(jìn)行社區(qū)劃分，將每個(gè)用戶節(jié)點(diǎn)分配得離它最近的中心所屬的類中，用戶間節(jié)點(diǎn)的相似性計(jì)算方法用式(2)的聯(lián)合相似性測(cè)度。

對(duì)于已經(jīng)劃分的社區(qū)，我們根據(jù)社區(qū)內(nèi)用戶所發(fā)表微博在主題上的興趣分布向量，可以求出該社區(qū)關(guān)心的主題，如下：

以t(i) = (t(i, 1), …, t(i, j), …, t(i, k))表示社區(qū)i在各個(gè)主題上的興趣分布向量，其中t(i, j)表示社區(qū)i在第j個(gè)主題上的分布值，則

(3)

式中：c(i)表示社區(qū)i，u(k)表示ID為k的用戶，t(k,j)表示用戶k在第j個(gè)主題上的分布值。最后，根據(jù)t(i)取主題分布值最大的3個(gè)分量對(duì)應(yīng)的主題作為社區(qū)i關(guān)心的主題。

1.4話題檢測(cè)

話題是討論、談話的中心，在整個(gè)微博上，用戶經(jīng)常會(huì)針對(duì)某一事件、觀點(diǎn)展開討論。對(duì)于有大量用戶參與討論的事件和話題，我們稱之為熱點(diǎn)話題。

本文提出了一種融合詞重要度與ε近鄰圖[2]的微博話題檢測(cè)方法來檢測(cè)話題。具體步驟如圖2所示。

圖2　話題檢測(cè)流程圖Fig.2　flow of topic detection

1.4.1提取重要詞

由話題的定義可知，與話題相關(guān)的詞語通常會(huì)具有更高的重要性。顯然，重要性過低的詞語，盡管能夠表達(dá)一定的含義，但并不能構(gòu)成話題，會(huì)對(duì)我們?cè)掝}檢測(cè)造成一定影響。因此需計(jì)算詞的重要性。

TextRank[12]算法是在Google的PageRank[10]算法啟發(fā)下，針對(duì)文本里的句子設(shè)計(jì)的權(quán)重算法。最初的目標(biāo)是對(duì)文章提取摘要，目前多用于給詞語打分，即計(jì)算詞語的重要度。本文采用TextRank[12]算法計(jì)算詞語重要度并過濾掉重要度過低的詞語，步驟如下:

1)將同一社區(qū)內(nèi)所有微博(已切詞)做拼接，構(gòu)成微博文檔D。

2) 采用TextRank[12]算法對(duì)微博文檔D求詞語

重要度分?jǐn)?shù)并逆序排序。

3)剔除重要度低于閾值θ的詞語。

經(jīng)過如上步驟，得到了微博文檔D對(duì)應(yīng)的重要詞庫(kù)，記為精英詞集elite。

1.4.2剪枝

將微博特征向量中不屬于重要詞匯庫(kù)elite的詞語剔除。若剔除后微博向量長(zhǎng)度過短，則將該微博從該社區(qū)剔除，本文設(shè)置長(zhǎng)度閾值為3。去除了微博內(nèi)與話題相關(guān)度很低的詞語，保留了與話題相關(guān)度較高的詞語。

1.4.3微博文本ε近鄰圖構(gòu)建

傳統(tǒng)的微博相似度計(jì)算方法主要是對(duì)微博集合中每一條微博的詞進(jìn)行TF-IDF的計(jì)算，并將微博中各個(gè)詞表示成VSM[3]空間向量，然后采用余弦相似度計(jì)算兩條微博之間的相似度。但考慮到微博具有短文本高維、稀疏的特點(diǎn)，采用傳統(tǒng)的TF-IDF向量表示法計(jì)算得到的相似性(趨于0)不能反映兩個(gè)微博文本的真實(shí)相似性。故本文以詞語的重要度代替TF-IDF值作為詞的特征權(quán)重。由于經(jīng)過社區(qū)劃分以及微博剪枝之后，社區(qū)內(nèi)微博特征已相對(duì)稠密，故可采用基于VSM[3]空間向量模型的余弦相似度計(jì)算方法來計(jì)算兩條微博之間的相似度，公式為

(4)

式中：sim(A,B)表示微博A與微博B之間的相似度，score(wi)表示詞wi的重要度分?jǐn)?shù)。

我們給每一條微博分配一個(gè)ID，ID從1到n′，然后以微博為節(jié)點(diǎn)，微博之間的相似度為邊，構(gòu)建一張ε近鄰圖[2]。若微博i與微博j的相似度大于閾值ε，則微博i與微博j之間存在一條邊，且該邊權(quán)重為sim(i,j)。

1.4.4微博聚類

本文采用社區(qū)劃分的方法對(duì)微博文本進(jìn)行聚類。由于社區(qū)具有社區(qū)內(nèi)部節(jié)點(diǎn)連接稠密、社區(qū)之間節(jié)點(diǎn)連接稀疏的特點(diǎn)，故社區(qū)(話題簇)內(nèi)微博相似度更大，社區(qū)(話題簇)間微博相似度更小。故對(duì)微博ε近鄰圖進(jìn)行社區(qū)劃分，并選取社區(qū)節(jié)點(diǎn)數(shù)最多的T個(gè)社區(qū)作為社區(qū)內(nèi)關(guān)心的話題。本文采用經(jīng)典社區(qū)劃分算法BGLL[13]對(duì)微博ε近鄰圖進(jìn)行社區(qū)劃分。

1.4.5話題檢測(cè)

本文以主題詞來描述話題，提出了一種以主題度來選取主題詞的方法。本方法以topic(wi,j) 表示詞wi在話題簇j內(nèi)的主題度，計(jì)算公式如下：

(5)

式中：fre(wi,j)表示詞wi在話題簇j內(nèi)的詞頻，score(wi)表示詞wi的重要度，num(j)表示話題簇j包含的微博數(shù)目，則主題選取過程如下：

1)對(duì)于所有話題簇，在話題簇內(nèi)計(jì)算所有詞的主題度；

2)在話題簇內(nèi)按主題度對(duì)詞進(jìn)行逆序排序，并保留主題度最大的15個(gè)詞；

3)將所有話題簇內(nèi)所保留的詞加入集合s；

4) 遍歷集合s，對(duì)于詞wi，遍歷所有社區(qū)，若wi在社區(qū)t內(nèi)的主題度最高，則wi∈tw(t)。tw(t)表示話題簇t對(duì)應(yīng)的主題詞集合。

1.4.6話題熱度排行

話題的熱度表現(xiàn)在多個(gè)方面，本文以主題度來表征話題的熱度。計(jì)算公式為

(6)

式中：heat(j)表示話題簇j對(duì)應(yīng)話題熱度，m(j)表示話題簇j對(duì)應(yīng)主題詞集合包含詞語個(gè)數(shù)。

最后按話題熱度對(duì)話題進(jìn)行逆序排序。

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

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

本實(shí)驗(yàn)數(shù)據(jù)采用自主抓取的新浪微博數(shù)據(jù)，該數(shù)據(jù)集于2013年9月—2013年12月采用自主開發(fā)的面向新浪微博的網(wǎng)絡(luò)爬蟲爬取。數(shù)據(jù)集包括用戶基本信息、用戶關(guān)系信息、用戶發(fā)表微博等3部分。

2.2實(shí)驗(yàn)過程與結(jié)果

2.2.1用戶社區(qū)劃分實(shí)驗(yàn)與結(jié)果

根據(jù)新浪微博首頁熱門微博分類版塊，選取10個(gè)類別作為主題，分別為親子、體育、公益、娛樂、文藝、時(shí)尚、時(shí)政、生活、科技、財(cái)經(jīng)。然后將每個(gè)用戶發(fā)表的微博拼接成微博文檔，選取微博文檔長(zhǎng)度大于5 000字的3 490個(gè)用戶作為實(shí)驗(yàn)數(shù)據(jù)，并進(jìn)行網(wǎng)絡(luò)建模。采用信號(hào)傳遞算法[19]對(duì)用戶關(guān)系網(wǎng)求鏈接屬性向量，并采用該向量求節(jié)點(diǎn)鏈接相似度；采用LDA[1]主題模型對(duì)微博文檔求主題分布向量(內(nèi)容特征向量)，并采用該向量求節(jié)點(diǎn)內(nèi)容相似度。然后采用KRLC算法[8]對(duì)用戶進(jìn)行社區(qū)劃分，最后采用式(3)求出社區(qū)對(duì)應(yīng)興趣分布，具體結(jié)果如表1。

表　1使用KRLC劃分的社區(qū)興趣分布

2.2.2社區(qū)內(nèi)話題檢測(cè)結(jié)果

根據(jù)劃分的10個(gè)社區(qū)，在社區(qū)內(nèi)檢測(cè)話題，檢測(cè)算法如2.4所示。本文選取了2013.11.10—2013.11.12共3天的微博作為話題檢測(cè)數(shù)據(jù)。其中詞語重要度閾值θ設(shè)為40%，即保留重要度最高的40%詞語，相似度閾值ε設(shè)為0.15。由于親子、文藝、時(shí)尚等3個(gè)主題出現(xiàn)話題幾率較小，故本文沒有在這3個(gè)社區(qū)內(nèi)檢測(cè)話題。部分主題對(duì)應(yīng)社區(qū)內(nèi)話題檢測(cè)結(jié)果如表2所示。

表2　部分社區(qū)內(nèi)微博話題檢測(cè)結(jié)果

根據(jù)表2我們可以看出，面向用戶社區(qū)的話題檢測(cè)方法，可以針對(duì)社區(qū)內(nèi)的用戶興趣找到用戶感興趣的話題，使得話題推薦和排行具有社區(qū)興趣個(gè)性化。

2.3局部算法對(duì)照試驗(yàn)

由于本文提出的面向用戶興趣與社區(qū)關(guān)系的微博話題檢測(cè)與已有研究不同，一是方法不同，二是研究數(shù)據(jù)不同，因此我們沒有和已發(fā)表方法進(jìn)行對(duì)比。但我們對(duì)已選取的社區(qū)劃分方法的差異而造成的結(jié)果差異，進(jìn)行了一些分析。

除了使用BGLL算法[13]對(duì)微博ε近鄰圖[2]進(jìn)行話題分割，我們采用被廣泛使用的圖聚類方法metis[17]、經(jīng)典社區(qū)劃分算法infomap[20]、基于模塊度的快速社區(qū)劃分算法fastnewman[16]對(duì)微博ε近鄰圖進(jìn)行話題分割。為了更全面地分析我們的實(shí)驗(yàn)結(jié)果，選取了CV[18]值作為評(píng)價(jià)指標(biāo)(表3中CV值為該社區(qū)內(nèi)所有話題CV值的平均值)，該評(píng)價(jià)指標(biāo)由Mimno[18]基于評(píng)估話題質(zhì)量而提出。

給定一個(gè)話題t和它的描述主題詞V(t) = (v1(t),v2(t),…,vM(t))，則CV值定義為

(7)

式中：D(v)為包含詞v的文檔頻次，D(v,v′)為同時(shí)包含詞v和v′的文檔頻次。CV值基于描述同一話題的詞往往同時(shí)出現(xiàn)于同一文檔中。CV值越小，所得話題簇的一致性越好。

實(shí)驗(yàn)結(jié)果如表3所示。由表3可以知道，選擇不同的方法對(duì)微博ε近鄰圖進(jìn)行話題聚類，會(huì)得到不同的結(jié)果。在本實(shí)驗(yàn)中，metis方法的效果總體上好于BGLL方法，但本文的方法只是面向用戶興趣和社區(qū)關(guān)系的話題檢測(cè)框架的一個(gè)嘗試，這類方法都可以找到用戶群興趣個(gè)性化的話題。

表3BGLL算法與metis、infomap、fastnewman算法對(duì)照試驗(yàn)結(jié)果

Table 3The controlled Trials result of BGLL with metis、infomap、fastnewman

劃分算法體育公益娛樂時(shí)政生活科技財(cái)經(jīng)bgll-15.8-6.3-16.3-22.3-14.3-15.3-14.0metis-17.3-0.5-17.3-8.8-17.0-8.0-7.0infomap-4.0-4.2-8.0-3.2-8.4-6.0-3.2fastnewman-7.2-5.2-6.2-5.2-5.8-5.4-4.4

綜上所述，本文提出的算法面向用戶興趣檢測(cè)話題，基于詞重要度的詞過濾方法使得社區(qū)內(nèi)的特征向量維度更低、更稠密，有效地解決了微博話題檢測(cè)過程中出現(xiàn)的特征稀疏問題。與普通話題檢測(cè)方法相比，該算法所檢測(cè)話題更有可能被社區(qū)內(nèi)用戶所關(guān)注，提高用戶活躍度。并且，本文采用主題度計(jì)算話題熱度并排序，使話題展示順序更加合理。

3結(jié)束語

本文提出了一種基于用戶興趣與社區(qū)關(guān)系的微博話題檢測(cè)方法，該方法能夠快速準(zhǔn)確地在社區(qū)內(nèi)部檢測(cè)話題，并對(duì)話題按熱度進(jìn)行排行。并且，該方法巧妙融合了新浪微博的社區(qū)特性與文本特性，檢測(cè)的話題更加迎合用戶的興趣。

本文以主題詞的形式來表現(xiàn)微博話題，但是本文對(duì)主題詞采用硬劃分，導(dǎo)致同一主題詞只能屬于唯一主題。但在真實(shí)情況下，可能多個(gè)話題含有同一主題詞，如何實(shí)現(xiàn)將主題詞劃入多個(gè)話題，有待進(jìn)一步研究。另外，以主題詞表現(xiàn)話題并不是特別直觀，如何實(shí)現(xiàn)以詞組或句子表達(dá)主題，也有待進(jìn)一步研究。

參考文獻(xiàn):

[1]BLEI D M, NG A Y, JORDAN M I. Latent dirichlet allocation[J]. The journal of machine learning research, 2003, 3(4-5): 993-1002.

[2]VON LUXBURG U. A tutorial on spectral clustering[J]. Statistics and computing, 2007, 17(4): 395-416.

[3]郭慶琳, 李艷梅, 唐琦. 基于VSM的文本相似度計(jì)算的研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2008, 25(11): 3256-3258.

GUO Qinglin, Li Yanmei, TANG Qi. Similarity computing of documents based on VSM[J]. Application research of computers, 2008, 25(11): 3256-3258.

[4]周剛, 鄒鴻程, 熊小兵, 等. MB-SinglePass: 基于組合相似度的微博話題檢測(cè)[J]. 計(jì)算機(jī)科學(xué), 2012, 39(10): 198-202.

ZHOU Gang, ZOU Hongcheng, XIONG Xiaobing, et al. MB-SinglePass: microblog topic detection based on combined similarity[J]. Computer science, 2012, 39(10): 198-202.

[5]鄭斐然, 苗奪謙, 張志飛, 等. 一種中文微博新聞話題檢測(cè)的方法[J]. 計(jì)算機(jī)科學(xué), 2012, 39(1): 138-141.

ZHENG Feiran, MIAO Duoqian, ZHANG Zhifei, et al. News topic detection approach on Chinese microblog[J]. Computer science, 2012, 39(1): 138-141.

[6]方然, 苗奪謙, 張志飛. 一種基于情感的中文微博話題檢測(cè)方法[J]. 智能系統(tǒng)學(xué)報(bào), 2013, 8(3): 208-213.

FANG Ran, MIAO Duoqian, ZHANG Zhifei, et al. An emotion-based method of topic detection from Chinese microblogs[J]. CAAI transactions on intelligent systems, 2013, 8(3): 004: 208-213.

[7]Heinrich G. Parameter estimation for text analysis[R]. Technical report, Darmstadt, Germany: Fraunhofer IGD, 2004.

[8]喬健. 面向新浪微博的鏈接和內(nèi)容相結(jié)合的社區(qū)劃分方法[D]. 北京: 北京交通大學(xué), 2015.

QIAO Jian. Community detection by using link and content and it’s application in sina microblog[D]. Beijing: Beijing Jiaotong University, 2015.

[9]JIANG Yawen, JIA Caiyan, YU Jian. An efficient community detection method based on rank centrality[J]. Physica A: statistical mechanics and its applications, 2013, 392(9): 2182-2194.

[10]PAGE L, BRIN S, MOTWANI R, et al. The PageRank citation ranking: bringing order to the Web[R]. Stanford InfoLab, 1999: 189-194.

[11]KOJIMA K. Proceedings of the fifth Berkeley symposium on mathematical statistics and probability[J]. American journal of human genetics, 1969, 21(4): 407-408.

[12]MIHALCEA R, TARAU P. TextRank: bringing order into texts[C]//Proceedings of EMNLP 2004: association for computational linguistics. Barcelona, Spain, 2004.

[13]CHATURVEDI P, DHARA M, ARORA D. community detection in complex network via BGLL algorithm[J]. International journal of computer applications, 2012, 48(1): 32-42.

[14]ZANGHI H, VOLANT S, AMBROISE C. Clustering based on random graph model embedding vertex features[J]. Pattern recognition letters, 2010, 31(9): 830-836.

[15]XU Zhiqiang, KE Yiping, WANG Yi, et al. A model-based approach to attributed graph clustering[C]//Proceedings of the 2012 ACM SIGMOD international conference on management of data. New York, NY, USA, 2012: 505-516.

[16]NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical review E, 2004, 69(6): 066133.

[17]KARYPIS G, KUMAR V. Metis-unstructured graph partitioning and sparse matrix ordering system, version 2.0[Z]. Minnesota: University of Minnesota, Department of Computer, 1995: 202-205.

[18]MIMNO D, WALLACH H M, TALLEY E, et al. Optimizing semantic coherence in topic models[C]//Proceedings of the conference on empirical methods in natural language processing. Stroudsburg, PA, USA, 2011: 262-272.

[19]HU Yanqing, LI Menghui, ZHANG Peng, et al. Community detection by signaling on complex networks[J]. Physical review E, 2008, 78(1): 016115.

[20]BURK C F, HORTON F W. Infomap: a complete guide to discovering corporate information resources[J]. Lincoln: Prentice Hall, 1988.

劉志雄，1990年生，男，碩士研究生，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、復(fù)雜網(wǎng)絡(luò)。

賈彩燕，1976年生,女,副教授,博士生導(dǎo)師,中國(guó)人工智能學(xué)會(huì)粗糙集與軟計(jì)算專業(yè)委員會(huì)委員,主要研究方向?yàn)閿?shù)據(jù)挖掘、社會(huì)計(jì)算、文本挖掘及生物信息學(xué)。近年來主持國(guó)家自然科學(xué)基金面上項(xiàng)目、青年基金面上項(xiàng)目各1項(xiàng)；參加國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目、科技重大專項(xiàng)、北京市自然科學(xué)基金各1項(xiàng)；獲湖南省科學(xué)技術(shù)進(jìn)步二等獎(jiǎng)1項(xiàng)。

中文引用格式：劉志雄，賈彩燕.面向用戶興趣與社區(qū)關(guān)系的微博話題檢測(cè)方法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(3): 294-300.

英文引用格式：LIU Zhixiong，JIA Caiyan.Micro-blog topic detection based on users’ interests and communities[J]. CAAI transactions on intelligent systems, 2016,11(3): 294-300.

Micro-blog topic detection based on users’ interests and communities

LIU Zhixiong1,2， JIA Caiyan1,2

(1. School of Computer and Information Technology, University of Beijing Jiaotong, Beijing 100044, China; 2.University of Beijing Jiaotong Beijing Key Lab of Traffic Data Analysis and Mining, Beijing 100044, China)

Abstract：Microblog topic detection is a special type of topic detection. The traditional topic detection algorithms do not work well in special situations for Chinese microblogs. In this paper, a topic detection method cater to the user community of microblogs is proposed. Firstly, the users' interests were analyzed by using the LDA(Latent Dirichlet Allocation) topic model on the text of microblogs generated by users/bloggers. Then the user/follower network associated with users' interests was created and partitioned into different communities so that the users in the same group were not only densely connected but also shared similar interests. Then, the topics of interest in each community were detected. Together, this provides a microblog topic finding method that faces a user's community and combines the importance of words as well as an ε neighboring graph. The experimental tests show that the method can effectively eliminate microblog noise, compute the importance of words, and rapidly and accurately obtain the topics of interest of each community.

Keywords：microblog; community; network; text; topic; interest; noise; theme

作者簡(jiǎn)介：

中圖分類號(hào)：TP393

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-4785(2016)03-0294-06

通信作者：劉志雄. E-mail：523129791@qq.com.

基金項(xiàng)目：國(guó)家自然科學(xué)基金面上項(xiàng)目(61473030)、中央高校基本科研業(yè)務(wù)專項(xiàng)基金項(xiàng)目(2014JBM031).

收稿日期：2016-03-19.網(wǎng)絡(luò)出版日期：2016-05-13.

DOI:10.11992/tis.201603341

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0919.014.html