APP下载

微博噪声过滤和话题检测

2015-06-28奚浩瀚

铁路计算机应用 2015年3期
关键词:决策树特征值聚类

奚浩瀚,刘 云,熊 菲

(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)。

奚浩瀚,在读硕士研究生;刘 云,教授。

猜你喜欢

决策树特征值聚类
一类内部具有不连续性的不定Strum-Liouville算子的非实特征值问题
一类带强制位势的p-Laplace特征值问题
基于一类特殊特征值集的扩散算子逆谱问题
单圈图关联矩阵的特征值
基于K-means聚类的车-地无线通信场强研究
决策树和随机森林方法在管理决策中的应用
基于高斯混合聚类的阵列干涉SAR三维成像
基于决策树的出租车乘客出行目的识别
基于Spark平台的K-means聚类算法改进及并行化实现
基于模糊关联规则和决策树的图像自动标注