微博噪聲過濾和話題檢測

奚浩瀚，劉 云，熊 菲

（1.北京交通大學 電子信息工程學院，北京 100044；2.北京交通大學 通信與信息系統北京市重點實驗室，北京 100044）

微博噪聲過濾和話題檢測

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

（1.北京交通大學 電子信息工程學院，北京 100044；2.北京交通大學 通信與信息系統北京市重點實驗室，北京 100044）

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

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

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

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

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

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

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

1 預處理

本文的預處理包括數據提取，分詞和詞性標注幾個步驟。通過新浪微博的開放 API進行原始數據采集，并使用中科院研制的 ICTCLAS 分詞系統進行中文分詞和詞性標注。

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

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

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

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

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

根據對各個分類屬性信息增益率的計算，可以構建一棵由決策節點，決策分支和葉節點組成的決策樹。

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

3 文本模型化和特征值權重計算

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

其中，ti是特征項，wi是 ti對應的權重。

在傳統的 TDT（Topic Detection and Tracking）技術中，計算特征值權重主要采用兩種方法：TFIDF 權重計算法和布爾權重法[5]。

TF-IDF 方法的計算公式如式（2）：

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

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

本文采用布爾權重法來計算特征值權重，公式如式（3）：

其中，tfij為特征項 ti在微博 Dj中出現的頻度。

4 基于特征值的計分過濾方法

如果一個詞條在數據集中出現的次數越多，那么這個詞就可能是熱點話題的關鍵詞[7]。基于上述理論，本文提出了一個噪聲微博過濾的記分方法。

根據特征選取的結果，可以生成向量FV，計算公式如式（4）：

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

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

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

5 文本相似度計算

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

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

引入了時間參數的相似度計算公式如式（7）：

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

6 聚類算法描述

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

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

7 實驗結果

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

對于噪聲微博過濾，采用的評測標準是漏檢率（PMiss）和誤檢率（PFA）[11]，其中，漏檢率是未被檢測出來的噪聲微博的數量和總的噪聲微博數量的比值，誤檢率是錯誤歸為噪聲微博的數量和總的非噪聲微博數量的比值。實驗結果如表2和表3所示。

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

表3 基于特征值的計分過濾方法測評結果

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

對于聚類算法模塊，采用的測評標準是傳統的精確度（Precision），召回率（Recall）和 Fβ值[12]。其中，Fβ值是精確度和召回率的調和平均，用于綜合評價實驗結果的好壞。Fβ值越大表示系統的綜合性能越好。

實驗結果如表4所示。

表4 引入了時間參數的增量聚類算法測評結果比對

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

8 結束語

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

[1] 鄭斐然，苗奪謙，張志飛，高 燦 . 一種中文微博新聞話題檢測的方法 [J].計算機科學，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] 邱 洋 . 微博數據提取及話題檢測方法研究 [D].大連：大連理工大學，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] 陸 旭 .文本挖掘中若干關鍵問題研究 [M]. 合肥 : 中國科學技術大學出版社，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].天津：南開大學，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].計算機科學，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]. 北京：科學出版社，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.

責任編輯 陳 蓉

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）；中央高校基本科研業務費（2014-JBM018)。

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