奚浩瀚，劉 云，熊 菲

（1.北京交通大學(xué) 電子信息工程學(xué)院，北京 100044；2.北京交通大學(xué) 通信與信息系統(tǒng)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044）

微博噪聲過濾和話題檢測

奚浩瀚1,2，劉 云1,2，熊 菲1,2

（1.北京交通大學(xué) 電子信息工程學(xué)院，北京 100044；2.北京交通大學(xué) 通信與信息系統(tǒng)北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044）

針對微博中充斥著的大量廣告信息和其它的噪聲微博，本文提出了基于C4.5決策樹分類算法的用戶分類過濾機(jī)制和基于特征值的計(jì)分過濾方法。利用微博文本的實(shí)時性和微博話題的時效性，還提出了一個基于時間參數(shù)的相似度計(jì)算方法。實(shí)驗(yàn)結(jié)果表明，該方法能提高對噪聲過濾和話題檢測的準(zhǔn)確率和效率。

噪聲過濾；C4.5決策樹；特征值；相似度計(jì)算

微博是一種通過關(guān)注機(jī)制分享簡短實(shí)時信息的廣播式社交網(wǎng)絡(luò)平臺。用戶可以通過發(fā)布 140 字以內(nèi)的文字來進(jìn)行狀態(tài)更新、日常生活描述，或者是發(fā)表對社會問題的感想、分享有趣的事情，與好友互動交流[1]。微博作為新型媒體平臺的出現(xiàn)，它的許多新特性給我們帶來了全新的思考和挑戰(zhàn)。

根據(jù) 2010 年官方公布數(shù)據(jù)顯示，新浪微博每天發(fā)送微博數(shù)超過 2 500 萬條，微博總數(shù)累計(jì)超過 20億條。截至 2014 年 3 月，微博的月活躍用戶已達(dá) 1.438億， 日 活 躍 用 戶 6 660 萬[2]。 在 微 博 的 廣 泛 應(yīng) 用 和海量信息下，蘊(yùn)含著大量毫無輿情價值的信息。噪聲微博數(shù)量龐大，極大地增加了文本聚類的復(fù)雜性，這給話題檢測帶來了諸多影響和不便。如何過濾這些噪聲也成了我們工作的重中之重。

微博話題具有很強(qiáng)的時效性，通常來說，一個熱點(diǎn)話題的持續(xù)時間長則數(shù)周，短則幾天。當(dāng)話題的熱度峰值過去之后，它被用戶討論的頻度就會急劇降低。由此可以推論，如果 2條微博的發(fā)布時間相近，那么它們有可能屬于同一個話題[3]。如果把這一特性應(yīng)用在文本的相似度計(jì)算上，則可大大提升聚類的效率。

本文提出的噪聲過濾和話題檢測流程如圖1所示。

圖1 噪聲過濾和話題檢測流程圖

1 預(yù)處理

本文的預(yù)處理包括數(shù)據(jù)提取，分詞和詞性標(biāo)注幾個步驟。通過新浪微博的開放 API進(jìn)行原始數(shù)據(jù)采集，并使用中科院研制的 ICTCLAS 分詞系統(tǒng)進(jìn)行中文分詞和詞性標(biāo)注。

2 基于C4.5決策樹分類算法的分類過濾機(jī)制

利用微博用戶的特點(diǎn)作為測試屬性如表1所示，本文采用 C4.5 決策樹分類算法，把微博用戶分為廣告用戶和非廣告用戶兩大類。

表1 微博用戶分類測試屬性

C4.5 算法是對經(jīng)典的 ID3 算法的改進(jìn)，它使用了信息增益率代替信息增益來進(jìn)行分類計(jì)算[4]。公式如式（1）：

其中， A 表示用于分類的屬性，D 表示數(shù)據(jù)集。Dj表示的是數(shù)據(jù)集 D 根據(jù)屬性 A 劃分而成的子集。

根據(jù)對各個分類屬性信息增益率的計(jì)算，可以構(gòu)建一棵由決策節(jié)點(diǎn)，決策分支和葉節(jié)點(diǎn)組成的決策樹。

如果一個用戶在一天內(nèi)發(fā)布的微博數(shù)大于 a條（a為設(shè)定的閾值），就要將其視為潛在的廣告用戶進(jìn)行用戶驗(yàn)證；根據(jù)所生成的決策樹和該用戶所滿足的測試屬性，就能對其進(jìn)行分類預(yù)測。如果一個用戶被判定為廣告用戶，那么他發(fā)布的所有微博將視為廣告微博，然后直接濾除。

3 文本模型化和特征值權(quán)重計(jì)算

本文采用 VSM（Vector Space Model）對文本進(jìn)行模型化處理。對文本 Dj，它的向量空間模型表示為：

其中，ti是特征項(xiàng)，wi是 ti對應(yīng)的權(quán)重。

在傳統(tǒng)的 TDT（Topic Detection and Tracking）技術(shù)中，計(jì)算特征值權(quán)重主要采用兩種方法：TFIDF 權(quán)重計(jì)算法和布爾權(quán)重法[5]。

TF-IDF 方法的計(jì)算公式如式（2）：

其中，TF（Term Frequency）即詞頻，指的是特征值在文本中出現(xiàn)的頻率。IDF（Inverse Document Frequency）即倒排文檔頻率，指的是特征值在整個文本集中出現(xiàn)的頻率倒數(shù)。

微博文本內(nèi)容通常很短，單個詞條出現(xiàn)的次數(shù)大多為 0 或 1，因此 TF 對于特征項(xiàng)的權(quán)重意義不大。IDF 使得在文檔集中出現(xiàn)頻率較低的特征值具有較高的權(quán)重，以便區(qū)分文本。然而對話題檢測而言，出現(xiàn)頻率較高的詞反而更有可能是一個話題的主題詞，因此 TF-IDF 方法并不適用于微博中的話題檢測[6]。

本文采用布爾權(quán)重法來計(jì)算特征值權(quán)重，公式如式（3）：

其中，tfij為特征項(xiàng) ti在微博 Dj中出現(xiàn)的頻度。

4 基于特征值的計(jì)分過濾方法

如果一個詞條在數(shù)據(jù)集中出現(xiàn)的次數(shù)越多，那么這個詞就可能是熱點(diǎn)話題的關(guān)鍵詞[7]?；谏鲜隼碚?，本文提出了一個噪聲微博過濾的記分方法。

根據(jù)特征選取的結(jié)果，可以生成向量FV，計(jì)算公式如式（4）：

其中，df(ti)是特征詞條 ti在數(shù)據(jù)集中出現(xiàn)的次數(shù)，boost(ti)是根據(jù) ti的詞性所設(shè)置的一個權(quán)重。通常一條微博中的關(guān)鍵詞包括名詞、動詞、形容詞、時間和數(shù)字等，這些詞對話題表達(dá)的貢獻(xiàn)程度較大，相對而言，助詞、代詞、介詞、語氣詞等對話題表征的貢獻(xiàn)度較小。因此，需要根據(jù)貢獻(xiàn)度的不同來相應(yīng)地設(shè)置權(quán)重[8]。

對微博文本 Dj，計(jì)分公式如式（5）：

當(dāng)一條微博含有 fv較大的特征詞時，則代表它更有可能是話題相關(guān)的，所得的分?jǐn)?shù)也應(yīng)較高；當(dāng)微博不包含特征詞或所包含特征詞的 fv 值較小時，代表它不太可能是話題相關(guān)的，相應(yīng)所得的分?jǐn)?shù)也應(yīng)較低。基于以上的計(jì)分方法，將計(jì)分低于某個給定閾值的微博視為噪聲微博，然后直接濾除。

5 文本相似度計(jì)算

考慮到時間在微博話題檢測中的作用，本文在計(jì)算文本相似度時引入了一個時間參數(shù)，該參數(shù)以天為單位，計(jì)算公式如下[9]：

其中，TDj是文本 Dj發(fā)布的時間，TCf是第一條關(guān)于話題 C 的微博的發(fā)布時間，TCl是最近一條關(guān)于話題C的微博的發(fā)布時間。

引入了時間參數(shù)的相似度計(jì)算公式如式（7）：

其中，sim(d, c) 為夾角余弦距， α和β為預(yù)設(shè)的常量， α+β=1。

6 聚類算法描述

本文采用的是更新質(zhì)心的增量聚類算法。算法描述如下[10]：

（1）廣告用戶和噪聲數(shù)據(jù)濾除后，剩余的微博集為 D0；（2）forDj=(t1,w1Dj; t2, w2Dj;…; tn, tn, wnDj) ∈D0；（ 3 ） if Dj已 經(jīng) 被 歸 類 為某 話 題 簇 C ；（ 4 ） go to（ 1 ），處理下一條微博；（5） 設(shè) Vcenter=(w1Djw2Dj,…,wnDj) ，Vcenter為話題質(zhì)心；（6） forD'j∈ D ，且 D'j未被歸至任何話題簇 C ；（7） if dis(Vcenter, D'j)〈? ，? 為所設(shè)定閾值；（8） 將 D'j歸至 Dj的同一話題簇，標(biāo)記為 D'j已歸類；（9） 更新 Vcenter；（10）設(shè)置 Vcenter代表 Dj所在的話題簇；（11）輸出話題簇結(jié)果。

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

先抽取 100 個廣告用戶作為 C4.5 算法的原始數(shù)據(jù)集，生成決策樹。然后對從新浪微博中隨機(jī)抽取的 10 000 條微博進(jìn)行實(shí)驗(yàn)。

對于噪聲微博過濾，采用的評測標(biāo)準(zhǔn)是漏檢率（PMiss）和誤檢率（PFA）[11]，其中，漏檢率是未被檢測出來的噪聲微博的數(shù)量和總的噪聲微博數(shù)量的比值，誤檢率是錯誤歸為噪聲微博的數(shù)量和總的非噪聲微博數(shù)量的比值。實(shí)驗(yàn)結(jié)果如表2和表3所示。

表2 基于C4.5決策樹分類的用戶分類過濾測評結(jié)果

表3 基于特征值的計(jì)分過濾方法測評結(jié)果

由此可見，在噪聲過濾模塊，我們的方法能以較高的準(zhǔn)確率過濾掉大部分的廣告微博和其它噪聲微博。

對于聚類算法模塊，采用的測評標(biāo)準(zhǔn)是傳統(tǒng)的精確度（Precision），召回率（Recall）和 Fβ值[12]。其中，F(xiàn)β值是精確度和召回率的調(diào)和平均，用于綜合評價實(shí)驗(yàn)結(jié)果的好壞。Fβ值越大表示系統(tǒng)的綜合性能越好。

實(shí)驗(yàn)結(jié)果如表4所示。

表4 引入了時間參數(shù)的增量聚類算法測評結(jié)果比對

由此可見，在文本聚類模塊，引入的時間參數(shù)能在一定程度上提高聚類的精確度和召回率，使算法的綜合性能更好。

8 結(jié)束語

本文針對微博中存在的大量廣告信息提出了基于 C4.5 決策樹分類的用戶分類過濾機(jī)制，針對微博中的噪聲微博提出了基于特征值的計(jì)分過濾方法。利用微博話題的時效性，還提出了一個基于時間參數(shù)的相似度計(jì)算方法。在以后的工作中，還要繼續(xù)優(yōu)化相關(guān)的噪聲過濾和文本挖掘方法，進(jìn)一步提升文本聚類的效率，以達(dá)到更好的話題檢測效果。

[1] 鄭斐然，苗奪謙，張志飛，高 燦 . 一種中文微博新聞話題檢測的方法 [J].計(jì)算機(jī)科學(xué)，2012，39（1）.

[2] Shota Ishikawa, Yutaka Arakawa, Shigeaki Tagashira, Akira Fukuda. Hot Topic Detection in Local Areas Using Twitter and Wikipedia [J]. ARCS Workshops (ARCS), 28-29 Feb. 2012.

[3] 邱 洋 . 微博數(shù)據(jù)提取及話題檢測方法研究 [D].大連：大連理工大學(xué)，2013.

[4] Yukino Ikegami, Kenta Kawai, Yoshimi Namihira, Setsuo Tsuruta. Topic and Opinion Classif i cation based Information Credibility Analysis on Twitter[C]. 2013 IEEE International Conference on Systems, Man, and Cybernetics, 13-16 Oct. 2013.

[5] 陸 旭 .文本挖掘中若干關(guān)鍵問題研究 [M]. 合肥 : 中國科學(xué)技術(shù)大學(xué)出版社，2008.

[6] Hao Tu, Jin Ding. An Eff i cient Clustering Algorithm for Microblogging Hot Topic Detec-tion. Computer Science & Service System (CSSS)[C]. 2012 International Conference on Computer Science and Service System, 11-13 Aug. 2012.

[7] 劉 濤 . 用于文本分類和文本聚類的特征選擇和特征抽取方法的研究 [D].天津：南開大學(xué)，2004.

[8] Jing Xie, Gongshen Liu, Wei Ning. A Topic Detection Method for Chinese Microblog[C]. 2012 Fourth International Symposium on Information Science and Engineering, 14-16 Dec. 2012.

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

[10] Feifei Peng, Xu Qian, Hui Meng, Dan Zhou. Research on Algorithm of Extracting Micro-blog’s Hot Topics. Electronics[C]. Communications and Control (ICECC), 2011 International Conference on Communications and Control, 9-11 Sept. 2011.

[11] 程顯毅，朱 倩 .文本挖掘原理 [M]. 北京：科學(xué)出版社，2010.

[12] Xiangying Dai, Qingcai Chen, Xiaolong Wang, Jun xu. Online Topic Detection and Track-ing of Financial News based on Hierarchical Clustering[C]. Proceedings of the Ninth Interna-tional Conference on Machine Learning and Cybernetics, Qingdao, 11-14 July 2010.

責(zé)任編輯 陳 蓉

Micro-blog noise f i ltering and topic detection

XI Haohan1,2, LIU Yun1,2, XIONG Fei1,2
( 1.School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China; 2.Key Laboratory of Communication and Information Systems, Beijing Jiaotong University, Beijing 100044, China )

Aiming at the big amount of advertising messages and other noise tweets, the paper proposed a user classif i cation f i ltering mechanism based on C4.5 Decision Tree Classif i cation Algorithm and a scoring f i ltering method based on characteristic value. Taking advantage of the instantaneity of micro-blog text and timeliness of microblog topic, the paper put forward a similarity calculation method based on time parameter. Experiments showed that this mechanism could detect topics and f i lter noise with better accuracy and eff i ciency compared to the traditional approach.

noise f i ltering; C4.5 Decision Tree; characteristic value; similarity calculation

U285∶TP39

：A

1005-8451（2015）03-0019-04

2014-09-25

國家自然基金（61172072）；中央高校基本科研業(yè)務(wù)費(fèi)（2014-JBM018)。

奚浩瀚，在讀碩士研究生；劉 云，教授。