面向BBS短文本的特征提取研究.doc

1、 面向 BBS 短文本的特征提取研究 张柱山，叶允明 ，许钺 (哈尔滨工业大学深圳研究生院 计算机科学与技术学科部 广东省 深圳市 518055） 摘要： 作为发表自由言论、表达民意的重要信息平台， BBS 在网络信息流中的地位日益突出，对于其内容的话题检测与跟踪有着十分重要的意义。然而， BBS 短文本固有的关键词词频低、存在大量同音词、同义词及新词等特点，使得难以直接使用现有面向长文本的聚类算法。 本文通过分析 BBS 其文本组织形式及其短文本的内在特性，提出一种 BSDFS(BBS Short Document Feature Selection)特征提取算法。实验结果表明，相对于传统的

2、特征提取方法如 TF*IDF，本文的算法能够得到更好的 BBS 短文本聚类效果。 关键词： 网络论坛； 短文本； 文本聚类； 特征提取 中图分类号： TP319 0 引言 随着网络的迅速发展，互联网已成为海量信息的载体，尤其 用户创建的内容正成为互联网上的一个重要数据源。作为一种典型的用户创建内容的应用，网络论坛 (Web Forum,又称为公告板、讨论板或 BBS1)在全世界非常流行。 2009年 6月底 BBS论坛网民规模已达 10,275万，使 用率达 30.7%，增长率 12.9%2，是互联网中非常活跃的一部分。 每天有无数个针对能够想象到的所有话题或问题的帖子被互联网用户创建，论坛

3、数据 俨然成为了 一个巨大的 汇聚了 人类知识 的数据集。为了 及时掌握各个时期民众关心的热点话题 ， 对 BBS进行舆情监控是十分迫切。 BBS热点话题检测 , 它涉及到针对 其文本内容的采集、信息抽取 、 文本与处理、聚类 等关键技术 。 其中 ,聚类是实现话题检测 的一个主要手段 。 传统的文本挖掘处理的文本通常是长文本，在形式上显然与 BBS短文本不同，因此，现有数据挖掘领域已取得较大的文本聚类算法还难 以直接引用 。 BBS短文本聚类面临的主要难点有： 1）关键词词频过低，这一方面导致无法 使用现有文本处理中常用的特征提取算法（如 TF*IDF）来计算特征词权重； 2）存在大量同音词

4、、同义词 ，这一方面导致 BBS短文本的表示不够准确，影响聚类结果。 本文给出一种面向 BBS文本的特征表示方法 , 提出一种 BSDFS(BBS Short Document Feature Selection)特征提取算法 ,采用 增量 聚类进行 BBS 的话题检测。使用该话题检测 系统 ，以 BBS的 文本信息 (帖子标题、首贴内容 )作为处理对象 ,具有 数据量大、数据源多、各数据源流量不均衡、短文篇幅小等特点 ,通过系统能找出最近一段时间的热门话题。 1. 相关研究 1.1 BBS 文本数据特性 BBS站点中 通常包含了这样一些元素： 3 论坛版块：通常是 BBS的入口，包含各个子版

5、块（特定内容讨论区域）的入口； 帖子线索：通常由主帖和相应回帖组成，所有这些帖子基本上都是在讨论同一个话题。帖子线索的结构可以看作是树结构，其主帖是根，回帖都是相应帖子的子节点 ； 帖子：帖子 是作者对于某主题发表的内容，分为 主帖和回帖。主帖指该帖子线索的第一个帖子，由帖子作者发出；回帖指帖 子线索中相应帖子（主帖或回帖）的回应 ； 作者：发布帖子的人； 读者：阅读帖子的人，可以是会员或者游客。 本文的研究目的是从 BBS的内容 中检测出话题， 在话题特征提取过程中，选取了帖子线索的标题和主帖作为特征。 1.2 文本表示模型 向量空间模型 (VSM)是最简便有效的文本表示模型之一，向量空间模

6、型是由 Salton及其学生在六十年代末到七十年代初期提出并发展起来的 4。其基 本思想：将给定的文本 (文章、查询、或文章中的一段等 )转换成一个维数很高的向量。它的最大特点是可以方便地计算出任意两个向量的近似程度，即向量 所对应的文本间的相似性。如果两个向量是相近的，则其对应的文本是语义相关的。 在向量空间模型中，每一个文档被表示特征空间的一个向量。目前常用的办法是将所有文本文件中出现的 m 个词语做为特征，每个文档 dj 包含 m 维，每一个测试文档同样被表示成由以上 m 个词语作为特征的特征向量。 如式 1-1 所示。 (1-1) 1.3 特征权重的表示方法 在向量空间模型中，常通过特

7、征项的权重综合反映该特征项对标识文本内容的贡献度和文本之间的区分能力。下面介绍计算权重 的常见方法： TFIDF 方法是目前广泛采用的权重计算公式之一，是由 Salton 在 1988 年提出的 5。主要 思想是：如果一个特征在一个文档中出现次数很多，那么应该给该特征分配较高的权值；如果一个特征在训练集其他的文档中出现的次数也很多，那么应该给该特征分配较小的权值。词 i 在文档j 中的 TF*IDF 值计算公式如式 2-2 所示。 (1-2) 式中， w(i,j)代表词 i在文档 j中的权重， tf(i,j)代表词 i在文档 j中的词频， idf(i,j)是词 i 的逆文档频数。 n 是文档集

8、合的大小， n(i)是词 i 的文档频数。可见词 i 在文档 j 中的 TF*IDF 值，与它在文档 j 中出现的词频成正比，与它的文档频度成反比。 TF*IDF 算法适用于具 备恰当的回朔文集、单信源、对识别和检测的实时性要求较高的系统。 某些用于话题提取系统中使用了 TF * PDF ( Term Frequency * Proportional Document Frequency) 算法 6 ,7 计算词汇权重 ,该算法兼顾考虑了词出现的频率和词来源的广泛性。在TF * PDF 算法中不需要构造特定的回朔文集 ,它适用于信源数量众多、信源重 要性相等的系统。对 TF * PDF 算法的

9、具体讨论参见文献 8。 本文的词频权值计算以 TF*PDF算法为基础，根据 BBS文本组织形式进行了改进。 2. BBS 特征提取算法设计与实现 2.1 BBS 热点 话题检测总体结构 根据话题检测系统的功能需求，将 BBS 话题检测系统分为数据库交互模块、 BBS 爬虫采集模块、文本预处理模块、话题检测模块、话题热度评分等五个部分。 BBS 话题检测系统的架构如图 2-1 所示： 数 据 预 处 理模 块B B S 数 据 仓 库数 据 库 交 互模 块话 题 检 测模 块话 题 热 度 评 分模 块爬 虫 采 集 及 信 息 抽 取模 块图 2-1 BBS 话题检测系统架构 各个模块 的功

10、能及相互关系描述如下： 数据库交互模块：对数据库相关表进行各项操作。系统运行初期从帖子表中读取数据，本系统为基于内容分析，所以选取帖子的标题字段和主帖字段为原始数据。系统运行后期，将话题检测模块的运行结果插入数据库的话题表 (Topic)。 爬虫采集及信息抽取模块：通过本实验室开发的 BBS 爬虫对种子论坛站点进行帖子页面爬取并保存在本地文件目录中，接着抽取帖子相关信息存入 BBS 数据仓库。 数据预处理模块：在程序运行前期，对从数据库帖子表中读出的原始数据进行预处理，即对帖子标题和主帖内容进行分词和去中文停用词 。输入数据为文本形式的文档，输出数据为向量形式的文档。 话题检测模块：从数据预处

11、理模块得到输入数据，经过话题检测算法之后，形成若干个文本集合，每一个集合对应一个话题。 话题热度评分模块：综合话题包含的各项信息 ,对相应的话题进行热度评分 ,最后输出得分最高的若干个话题 ,即为热点话题。 2.2 BBS 文本的特征表示 数据预处理模块主要完成针对 BBS 文本数据的预处理工作，包括对文本的中文分词、 去除中文停用词 以及 词权重计算等。 中文分词功能采用自然语言处理中常见的前项最大匹配(FMM)分词方法。取出中文停用词以中文停 用词词典为依据取出分词结果中的停用词。词权重计算模块采用 特征选择算法 。预处理后的的文档为 VSM 形式，作为后续 BBS 话题检测模块的输入数据

12、形式。 数据预处理模块内部流程图如图 2-2 所示。 中 文 分 词模 块权 重 计 算模 块B B S 数 据B B S 话 题 检 测 模块去 停 用 词模 块图 2-2 数据预处理模块流程图 本文在研究 TF*PDF 的基础上，结合 BBS 文本内容的组织形式，提出了 BSDFS(BBS Short Document Feature Selection)来进行 帖子文本 特征提取。由于我们的 BBS 数据来源于各大论坛， 而且每个论坛所讨论 的热点话题可能也不一致，因此，这些数据具有数据源多且流量不均衡的特点。 TF*PDF 算法倾向于给在各数据源均有出现的特征词赋予更高的权重。同时，针

13、对 BBS 帖子线索中，发帖人表达的语言具有一定的随意性，导致出现一些同音词、同义词。针对这些特点， BSDFS 算法考虑了词汇语义相关度对词汇权重的因素。 最后，我们根据 BBS短文本的特性给出了增益函数 f ( t , d)来 增加 特征项在文档中的权重。 按照前面叙述的算法设计思想 ,设计 BSDFS 算法如公式 (1) 、 (2) 、 (3) 所示 : 1e xp( )cD jcj jcc cnWF N (1) 211* ( ( , ) * ( , ) )ckKjckjc kKkckF f t d p S im k jFF(2) ( , ) ( , ) * ( , ) * ( , )f

14、 t d O c c u r r e n c e t d p o s t C o u n t t d p l a c e t d (3) 其中 jW 为词 j 的权值 , jcn 为数据源 C中包含词 j 的短文数 , cN 为数据源 C的短文总数 , c 为数据源的数目 , jcF 为词 j 在数据源 c 中未考虑词汇语义相似度的权重 ; cK 为数据源 C 中相异词的总数 , kcF 为词 k 在数据源 C 中未考虑词汇语义相似度的权重 , ( , )Simk j 是词 k 和词 j 的相 似度 ; (, )f t d 是 BBS 文本内 容 的增益 因子。( , )Occurrence

15、t d为特征项 t 在帖子线索 d 中的出现次数 ; ( , )postCount t d为 d 中包含 t 的帖子数目 ; ( , )place t d 对应于 t 在 d 中的出现位置 ,在标题出现过的词对应的值为 3; 通过 公式 (1) 可以看出 ,词 j 的权重是在所有信源中词 j权重的和 , 它说明 在大多数信源中出现的词将被赋予更高的权重。词 j 在信源 C 中的权重与信源 C 中包含词 j 的文档在信源 C 中所占的比例成指数关系 ,也就是说出现在更多文档中的词拥有更高的权重。为了加强这种趋势 ,算法使词的权重以指数的速度增长。 这体现所抽取的特征 次具有广泛代表性。 通过公式

16、 (2)可以看出，算法 BSDFS 在计算某个信源中词的权重时 ,考虑了同义词和近义词的影响。 如果没有加入词汇语义相似度的考虑 ,在计算权重时同义词或 同音 词将作为相互正交的词进行处理 ,这样处理显然准确性不高。 这保证聚类结果不被 BBS 文本的不规范影响。 通过公式 (3)可以看出，算法 BSDFS 考虑了 BBS 帖子组织结构的特性，把标题、主帖和回帖的因素都考虑在内。这有助于提高特征词代表文本的特征准确性。 2.3 话题检测模块 BBS 话题检测模块的主要功能是处理文本向量集合，基于增量聚类算法对预处理 之后的文本向量进行聚类，产生若干个文档集合，每一个文档集合代表一个话题。 BB

17、S 增量聚类模块的主要流程包括： (1) 依次读取预处理后的帖子文本； (2) 如果这是第一个帖子，则直接将此帖子当作第一个话题； (3) 与已经生成的话题质心依次计算相似度； (4) 取最大相似度与阈值相比较； (5) 如果大于等于阈值，则把这个帖子加入相应话题的文档集合，并更新相应 话题的质心； (6) 如果小于阈值，则把这个帖子当作新话题的质心； (7) 结果插入数据库。 其中，从 BBS 数据仓库中读出的帖子，经过预处理模块得到预处理后的文档。经过文本过滤和权重计算，得到文档的 词和词权重向量。进入增量聚类流程。增量聚类的结果得到若干个文档簇，对文档簇的规模进行判别，选择出可以代表话题

18、的文档簇。最终形成了话题文档簇集合。 BBS 话题检测模块系统框架图如图 2-3 所示。 增 量 聚 类话 题 文 档 簇集 合预 处 理 后 的文 档标 题 词 加权词 权 重 计算B B S 数 据 仓 库帖 子文 本 过 滤话 题 筛 选图 2-3 BBS 话题检测 模块框架图 3. 实验结果 3.1 数据集 为了验证 BSDFS 算法的有效性，本文选择 深圳论坛 和 奥一论坛 作为 BBS 实例，通过本实验室开发的 BBS爬虫采集帖子数据进行话题检测实验。抽取 2010 年 3月 25日至 3 月 31日论坛帖子 2660 篇。通过对文档集进行预处理，包括帖子内容信息抽取、去停用词、分

19、词等，得到有效实验帖子数 2568 篇。本实验采用 2.3 节中提到的 Single-Pass 增量聚类算法，相似度阀值设为 0.10，最小帖子数为 10。 通过聚类，共产生 21 个话题，我们抽取其中三个话题作为实验比较。 3.2 实验结果及分析 在第一 组实验中 ,采用标准 TF*IDF 算法计算词汇权重。在标准 TF*IDF 算法中 ,没有对短文篇幅小的特点进行优化 ,没有考虑 BBS 帖子文本结构的特点 ， 实验结果如表 1 所示 : 表一 -采用标准 TF*IDF 算 法计算词汇权重 话题 相关帖子 关键词及权重 让我们参战退役老兵生活得更有尊严 ! 奥一论坛 -有话问市长 _p_1

20、547_深圳市李峰副市长接见参战老兵代表并重视老兵诉求 退役 : 14.08 老兵 : 14.39 优抚对象 : 14.08 参战 : 15.13退役军人 : 14.38 抚恤 : 13.73 下岗 : 11.90 优抚 : 12.96 优待 : 12.28 伤病 : 10.30 深圳市委 : 10.57 副市长 : 10.72 保卫边疆 : 12.28 战友 : 11.88 奥一论坛 -有话问市长 _p_1451_让我们参战退役老兵生活更有尊严 奥一论坛 -有话问市长 _p_1853_请给深圳的优抚对象免费乘坐公交等最实际的关怀 深圳填海区豪宅沉降最高深达 12厘米 奥一论坛 -深圳视点 _

21、p_2087_房价不降，房架降啦。哈哈 建筑质量 : 12.62 沉降 : 16.64 地表 : 13.16 地砖 : 13.10 下陷 : 10.30 海岸 : 12.26 西岸 : 12.65 填海 : 12.28 波浪 : 12.08 西侧 : 12.01 塌陷 : 12.08 罗田 : 13.68 厘米 : 12.94 奥一论坛 -有话问市长 _p_1465_深圳楼盘沉降 12厘米政府竟然称质量没问题 奥一论坛 -深圳视点 _p_2077_深圳填海区豪宅沉降最高深达 12厘米 我们的目的是：迫使政府建立新的公车管理制度 深圳论坛 -第一现场 _p_1_公车门房某回应：周末开公车是去办公

22、事 调查组 : 10.54 机动车辆 : 10.92 调查结果 : 10.19 公干 : 12.65政府制定 : 10.30 政府建立 : 13.68所属部门 : 10.30 调度 : 12.87 基层官员 : 10.92公务用车 : 11.24 外出办公 : 10.92公车管理 : 12.65 深圳论坛 -第一现场 _p_2302_深圳街道办副主任房艳公车周末带上哥哥和侄仔仨人去公干 深圳论坛 -第一现场 _p_214_我们的目的是：迫使政府建立新的公车管理制度 在第 二 组实验中 ,采用 本文提出的 BSDFS 算法计算词汇权重。在该 算法中 ,对 BBS 短文篇幅小的特点进行优化 ,考虑

23、多数据源、帖子文本结构的特点 ,实验结果如表 2 所示 : 表二 -采用 本文提出的 BSDFS 算法计算词汇权重 话题 相关帖子 关键词及权重 让我们参战退役 老兵生活得更有尊严 ! 奥一论坛 -有话问市长 _p_1547_深圳市李峰副市长接见参战老兵代表并重视老兵诉求 退役 : 14.51 老兵 : 21.88 优抚对象 : 14.88 参战 : 15.67退役军人 : 14.38 抚恤 : 13.73 下岗 : 11.90 优抚对象 : 14.08 优待 : 12.28 伤病 : 10.30 深圳 : 20.57 副市长 : 11.92 保卫边疆 : 12.28 战友 : 11.88 深

24、圳论坛 -第一现场 _p_186_让我们参战退役老兵生活得更有尊严 奥一论坛 -有话问市长 _p_1853_请给深圳的优抚对象免费乘坐公交等最实际的关怀 深圳填海区豪宅沉降最高深达 12厘米 奥一论坛 -深圳视点 _p_2087_房价不降，房架降啦。哈哈 后海： 18.26 填海区： 17.56 沉降 : 19.99 豪宅： 13.21 塌陷 : 12.08 海景 : 10.92 中心区 : 11.72 地砖 : 13.10 建筑质量 : 12.62 地表 : 13.16 波浪 : 12.08 最深处 : 14.34 地面下陷 : 10.92 楼盘 :11.45 厘米 : 13.45 深圳论坛

25、 -第一现场 _p_1734_第一现场 100407播出：后海填海区路面是波浪栏杆在扭腰 奥一论坛 -深圳视点 _p_2077_深圳填海区豪宅沉降最高深达 12厘米 疑 偏 袒 公 车 门 官员，深圳网民上监察局讨说法 深圳论坛 -第一现场 _p_1_公车门房某回应：周末开公车是去办公事 调查组 : 11.26 机动车辆 : 10.92调查结果 : 10.19 公干 : 12.65政府制定 : 10.30 迫使 : 13.48 政府建立 : 16.10 调度 : 12.87 所属部门 : 10.30 公车： 22.14 基层官员 : 10.92 公务用车 :11.24外出办公 :10.92 公

26、车管理 :14.88死猪不怕开水烫 : 17.23 奥一论坛 -深圳视点 _p_1877_公车门调查组死猪不怕开水烫 奥一论坛 -深圳视点 _p_1966_疑偏袒公车门官员，深圳网民上监察局讨说法 通过实验结果对比，我们可以发现同样的话题，其相关帖子以及关键词的权重都发生了变化 。由于 BSDFS 算法考虑了来自不同数据源的影响，出现在不同数据源的关键词的权重将指数级增长 ，因此，来自不 同数据源的帖子更容易地聚到同一个话题 。同时，出现在帖子标题的关键词权重也得到提高 ，其对聚类结果的影响也相应提高 。实验表明，通过 BSDFS 算法进行特征提取，BBS 话题检测聚类结果 更加准确、更加有效

27、。 4. 结束语 本文从分析 BBS 热点话题检测入手， 针对 BBS 短文本特征提取 进行了深入细致的探讨和研究。在基于 TF*PDF 的基础上，我们提出 BSDFS(BBS Short Document Feature Selection)算法， 它适用于多数据源、短文篇幅小、文本内容不规范的 BBS 短文本特征提取。实验结果表明 ,该算法可以 有效挖掘 BBS 上的热点话题。 通过有效地提取特征形成有效代表帖子的文本向量 ，在 BBS 热点话题检测 的精度与效率方面有较大提高。 然而系统中各 聚类算法、参数和阈值的 选择 仍是值得研究的问题。 参考文献： 1 Internet Forum

28、 Software. http:/en.wikipedia.org/wiki/category:internet_forum_software 2 中国互联网信息中心 .第 24次中国互联网络发展状况统计报告 3 YOU Lan , DU Yong2ping , GE Jia2yin , et al . BBS based hot topic ret rieval using back2propagation neural network CP P Proceedings of the 1st International Symposium on Natural Language Proces

29、sing ( IJCNL P 04 ) . Hainan, China :LNAI 3248 , 2004 :139 2148 4 Kobayashi N, Iida R, Inui K et a1. Opinion mining as extraction of attribute-value relations. New Frontiers in Artificial Intelligence, 2006, 4012: 470481 5 Zhang Y, Li Z, Ren F et a1. Semi-automatic emotion recognition from textual i

30、nput based on the constructed emotion thesaurus. IEEE, 2005: 571576 6 YANG Y, PEDERSEN JP. Feature Selection in Statistical Learning of Text CategorizationA . The 14th Inc Conf ,On Machine learning ,1997. 412 - 420. 7 JOACHIM T. A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text C

31、ategorizationA . Processing of ICML297 ,14th Interna2 tional Conference on Machine LearningC ,1996. 143 151 8 庞剑锋 ,卜东波 ,白硕 .基于向量空间模型的文本自动分类系统的研究与实现 J . 计算机应用研究 ,2001 ,18 (9) :23 - 26 BBS Short Document Feature Selection Zhu-shan ZHANG1， Yun-ming YE1 (1. Harbin Institute of Technology Shenzhen Gradua

32、te School, Shenzhen, 518055, China) Abstract: BBS users contribute millions of topics with highly valuable information, thus, forum data is actually a tremendous data source of human knowledge and its very meaningful to research the TDT of BBS contents. However, the traditional text clustering algor

33、ithm cant meet the requirement of the BBS text because the keywords frequency is low and there are a large number of homonyms, synonyms, and new words, etc. In this paper, we propose a feature extraction algorithm BSDFS (BBS Short Document Feature Selection) by analyzing the organization of BBS and the inherent characteristics of the short document. Experimental results show that this algorithm can get better results than the traditional feature extraction methods such as TF * IDF. Key words: Web Forum; Short Document; Text clustering; Feature Selection