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

面向 BBS 短文本的特征提取研究张柱山，叶允明，许钺(哈尔滨工业大学深圳研究生院 计算机科学与技术学科部 广东省 深圳市 518055）摘要： 作为发表自由言论、表达民意的重要信息平台，BBS 在网络信息流中的地位日益突出，对于其内容的话题检测与跟踪有着十分重要的意义。然而，BBS 短文本固有的关键词词频低、存在大量同音词、同义词及新词等特点，使得难以直接使用现有面向长文本的聚类算法。本文通过分析 BBS 其文本组织形式及其短文本的内在特性，提出一种 BSDFS(BBS Short Document Feature Selection)特征提取算法。实验结果表明，相对于传统的特征提取方法如 TF*IDF，本文的算法能够得到更好的 BBS 短文本聚类效果。关键词： 网络论坛；短文本； 文本聚类； 特征提取中图分类号：TP3190 引言随着网络的迅速发展，互联网已成为海量信息的载体，尤其用户创建的内容正成为互联网上的一个重要数据源。作为一种典型的用户创建内容的应用，网络论坛(Web Forum,又称为公告板、讨论板或BBS 1)在全世界非常流行。2009年6月底BBS论坛网民规模已达10,275万，使用率达30.7%，增长率12.9% 2，是互联网中非常活跃的一部分。每天有无数个针对能够想象到的所有话题或问题的帖子被互联网用户创建，论坛数据俨然成为了一个巨大的汇聚了人类知识的数据集。为了及时掌握各个时期民众关心的热点话题，对BBS进行舆情监控是十分迫切。BBS热点话题检测, 它涉及到针对其文本内容的采集、信息抽取、文本与处理、聚类等关键技术。其中,聚类是实现话题检测的一个主要手段。传统的文本挖掘处理的文本通常是长文本，在形式上显然与BBS 短文本不同，因此，现有数据挖掘领域已取得较大的文本聚类算法还难以直接引用。 BBS短文本聚类面临的主要难点有：1）关键词词频过低，这一方面导致无法使用现有文本处理中常用的特征提取算法（如TF*IDF）来计算特征词权重；2）存在大量同音词、同义词，这一方面导致BBS短文本的表示不够准确，影响聚类结果。本文给出一种面向BBS文本的特征表示方法 , 提出一种BSDFS(BBS Short Document Feature Selection)特征提取算法,采用增量聚类进行 BBS 的话题检测。使用该话题检测系统，以BBS的文本信息(帖子标题、首贴内容)作为处理对象 ,具有数据量大、数据源多、各数据源流量不均衡、短文篇幅小等特点 ,通过系统能找出最近一段时间的热门话题。1. 相关研究1.1 BBS文本数据特性BBS站点中通常包含了这样一些元素： 3论坛版块：通常是BBS的入口，包含各个子版块（特定内容讨论区域）的入口；帖子线索：通常由主帖和相应回帖组成，所有这些帖子基本上都是在讨论同一个话题。帖子线索的结构可以看作是树结构，其主帖是根，回帖都是相应帖子的子节点；帖子：帖子是作者对于某主题发表的内容，分为主帖和回帖。主帖指该帖子线索的第一个帖子，由帖子作者发出；回帖指帖子线索中相应帖子（主帖或回帖）的回应；作者：发布帖子的人；读者：阅读帖子的人，可以是会员或者游客。本文的研究目的是从BBS的内容中检测出话题，在话题特征提取过程中，选取了帖子线索的标题和主帖作为特征。1.2 文本表示模型向量空间模型(VSM)是最简便有效的文本表示模型之一，向量空间模型是由Salton及其学生在六十年代末到七十年代初期提出并发展起来的4。其基本思想：将给定的文本(文章、查询、或文章中的一段等)转换成一个维数很高的向量。它的最大特点是可以方便地计算出任意两个向量的近似程度，即向量所对应的文本间的相似性。如果两个向量是相近的，则其对应的文本是语义相关的。在向量空间模型中，每一个文档被表示特征空间的一个向量。目前常用的办法是将所有文本文件中出现的 m 个词语做为特征，每个文档 dj 包含 m 维，每一个测试文档同样被表示成由以上 m 个词语作为特征的特征向量。如式 1-1 所示。(1-1)=1,2,3,1.3 特征权重的表示方法在向量空间模型中，常通过特征项的权重综合反映该特征项对标识文本内容的贡献度和文本之间的区分能力。下面介绍计算权重的常见方法：TFIDF 方法是目前广泛采用的权重计算公式之一，是由 Salton 在 1988 年提出的 5。主要思想是：如果一个特征在一个文档中出现次数很多，那么应该给该特征分配较高的权值；如果一个特征在训练集其他的文档中出现的次数也很多，那么应该给该特征分配较小的权值。词 i 在文档 j 中的 TF*IDF 值计算公式如式 2-2 所示。(1-2)(,)=(,)(,)=(,)log()式中，w(i,j)代表词 i 在文档 j 中的权重，tf(i,j)代表词 i 在文档 j 中的词频，idf(i,j)是词 i 的逆文档频数。n 是文档集合的大小，n(i)是词 i 的文档频数。可见词 i 在文档 j 中的 TF*IDF 值，与它在文档 j 中出现的词频成正比，与它的文档频度成反比。TF*IDF 算法适用于具备恰当的回朔文集、单信源、对识别和检测的实时性要求较高的系统。某些用于话题提取系统中使用了TF * PDF ( Term Frequency * Proportional Document Frequency) 算法 6 ,7 计算词汇权重,该算法兼顾考虑了词出现的频率和词来源的广泛性。在TF * PDF 算法中不需要构造特定的回朔文集,它适用于信源数量众多、信源重要性相等的系统。对TF * PDF 算法的具体讨论参见文献 8。本文的词频权值计算以TF*PDF算法为基础，根据BBS文本组织形式进行了改进。2. BBS特征提取算法设计与实现2.1 BBS热点话题检测总体结构根据话题检测系统的功能需求，将 BBS 话题检测系统分为数据库交互模块、BBS 爬虫采集模块、文本预处理模块、话题检测模块、话题热度评分等五个部分。BBS 话题检测系统的架构如图 2-1 所示： 数 据 预 处 理模 块B B S 数 据 仓 库数 据 库 交 互模 块话 题 检 测模 块话 题 热 度 评 分模 块爬 虫 采 集 及 信 息 抽 取模 块图 2-1 BBS 话题检测系统架构各个模块的功能及相互关系描述如下：数据库交互模块：对数据库相关表进行各项操作。系统运行初期从帖子表中读取数据，本系统为基于内容分析，所以选取帖子的标题字段和主帖字段为原始数据。系统运行后期，将话题检测模块的运行结果插入数据库的话题表(Topic)。爬虫采集及信息抽取模块：通过本实验室开发的 BBS 爬虫对种子论坛站点进行帖子页面爬取并保存在本地文件目录中，接着抽取帖子相关信息存入 BBS 数据仓库。数据预处理模块：在程序运行前期，对从数据库帖子表中读出的原始数据进行预处理，即对帖子标题和主帖内容进行分词和去中文停用词。输入数据为文本形式的文档，输出数据为向量形式的文档。话题检测模块：从数据预处理模块得到输入数据，经过话题检测算法之后，形成若干个文本集合，每一个集合对应一个话题。话题热度评分模块：综合话题包含的各项信息,对相应的话题进行热度评分,最后输出得分最高的若干个话题,即为热点话题。2.2 BBS 文本的特征表示数据预处理模块主要完成针对 BBS 文本数据的预处理工作，包括对文本的中文分词、去除中文停用词以及词权重计算等。中文分词功能采用自然语言处理中常见的前项最大匹配(FMM)分词方法。取出中文停用词以中文停用词词典为依据取出分词结果中的停用词。词权重计算模块采用特征选择算法。预处理后的的文档为 VSM 形式，作为后续 BBS 话题检测模块的输入数据形式。 数据预处理模块内部流程图如图 2-2 所示。中文分词模块权重计算模块B B S 数据B B S 话题检测模块去停用词模块图 2-2 数据预处理模块流程图本文在研究 TF*PDF 的基础上，结合 BBS 文本内容的组织形式，提出了 BSDFS(BBS Short Document Feature Selection)来进行帖子文本特征提取。由于我们的 BBS 数据来源于各大论坛，而且每个论坛所讨论的热点话题可能也不一致，因此，这些数据具有数据源多且流量不均衡的特点。TF*PDF 算法倾向于给在各数据源均有出现的特征词赋予更高的权重。同时，针对 BBS 帖子线索中，发帖人表达的语言具有一定的随意性，导致出现一些同音词、同义词。针对这些特点，BSDFS 算法考虑了词汇语义相关度对词汇权重的因素。最后，我们根据 BBS 短文本的特性给出了增益函数 f ( t , d)来增加特征项在文档中的权重。按照前面叙述的算法设计思想,设计 BSDFS 算法如公式(1) 、(2) 、(3) 所示:(1)1exp()cDjcjjnWFN(2)211*(,)*(,)ckKjcjc kcftdSimjF(3)(,)(,)*(,)*(,)ftdOcurentdpostCuntdplacet其中 为词 j 的权值, 为数据源 C 中包含词 j 的短文数, 为数据源 C 的jWjc cN短文总数, c 为数据源的数目, 为词 j 在数据源 c 中未考虑词汇语义相似度的权重; jF为数据源 C 中相异词的总数, 为词 k 在数据源 C 中未考虑词汇语义相似度的权cK kc重, 是词 k 和词 j 的相似度; 是 BBS 文本内容的增益因子。()Simj (,)ftd为特征项 t 在帖子线索 d 中的出现次数 ; 为 d 中包含,Ocurentd (,)postuntt 的帖子数目 ; 对应于 t 在 d 中的出现位置 ,在标题出现过的词对应的值为(,)place3; 通过公式(1) 可以看出,词 j 的权重是在所有信源中词 j 权重的和, 它说明在大多数信源中出现的词将被赋予更高的权重。词 j 在信源 C 中的权重与信源 C 中包含词 j 的文档在信源 C 中所占的比例成指数关系,也就是说出现在更多文档中的词拥有更高的权重。为了加强这种趋势,算法使词的权重以指数的速度增长。这体现所抽取的特征次具有广泛代表性。通过公式(2)可以看出，算法 BSDFS 在计算某个信源中词的权重时,考虑了同义词和近义词的影响。如果没有加入词汇语义相似度的考虑,在计算权重时同义词或同音词将作为相互正交的词进行处理,这样处理显然准确性不高。这保证聚类结果不被 BBS 文本的不规范影响。通过公式(3)可以看出，算法 BSDFS 考虑了 BBS 帖子组织结构的特性，把标题、主帖和回帖的因素都考虑在内。这有助于提高特征词代表文本的特征准确性。2.3 话题检测模块BBS 话题检测模块的主要功能是处理文本向量集合，基于增量聚类算法对预处理之后的文本向量进行聚类，产生若干个文档集合，每一个文档集合代表一个话题。BBS 增量聚类模块的主要流程包括：(1)依次读取预处理后的帖子文本； (2)如果这是第一个帖子，则直接将此帖子当作第一个话题；(3)与已经生成的话题质心依次计算相似度；(4)取最大相似度与阈值相比较；(5)如果大于等于阈值，则把这个帖子加入相应话题的文档集合，并更新相应话题的质心；(6)如果小于阈值，则把这个帖子当作新话题的质心；(7)结果插入数据库。其中，从 BBS 数据仓库中读出的帖子，经过预处理模块得到预处理后的文档。经过文本过滤和权重计算，得到文档的词和词权重向量。进入增量聚类流程。增量聚类的结果得到若干个文档簇，对文档簇的规模进行判别，选择出可以代表话题的文档簇。最终形成了话题文档簇集合。BBS 话题检测模块系统框架图如图 2-3 所示。增量聚类话题文档簇集合预处理后的文档标题词加权词权重计算B B S 数据仓库帖子文本过滤话题筛选图 2-3 BBS 话题检测模块框架图3. 实验结果3.1 数据集为了验证 BSDFS 算法的有效性，本文选择 深圳论坛和奥一论坛作为 BBS 实例，通过本实验室开发的 BBS 爬虫采集帖子数据进行话题检测实验。抽取 2010 年 3 月 25 日至 3 月 31 日论坛帖子 2660 篇。通过对文档集进行预处理，包括帖子内容信息抽取、去停用词、分词等，得到有效实验帖子数 2568 篇。本实验采用 2.3 节中提到的 Single-Pass 增量聚类算法，相似度阀值设为 0.10，最小帖子数为 10。通过聚类，共产生 21 个话题，我们抽取其中三个话题作为实验比较。3.2 实验结果及分析在第一组实验中,采用标准 TF*IDF 算法计算词汇权重。在标准 TF*IDF 算法中,没有对短文篇幅小的特点进行优化,没有考虑 BBS 帖子文本结构的特点，实验结果如表 1 所示:表一-采用标准 TF*IDF 算法计算词汇权重话题 相关帖子 关键词及权重奥一论坛-有话问市长_p_1547_深圳市李峰副市长接见参战老兵代表并重视老兵诉求奥一论坛-有话问市长_p_1451_让我们参战退役老兵生活更有尊严奥一论坛-有话问市长_p_1853_请给深圳的优抚对象免费乘坐公交等最实际的关怀让我们参战退役老兵生活得更有尊严!退役: 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_2087_房价不降，房架降啦。哈哈奥一论坛-有话问市长_p_1465_深圳楼盘沉降12厘米政府竟然称质量没问题奥一论坛-深圳视点_p_2077_深圳填海区豪宅沉降最高深达12厘米深圳填海区豪宅沉降最高深达 12 厘米建筑质量: 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_1_公车门房某回应：周末开公车是去办公事我们的目的是：迫使政府建立新的公车管理制度 深圳论坛-第一现场_p_2302_深圳街道办副主任房艳公车周末带上哥哥和侄仔仨人去公干调查组: 10.54 机动车辆: 10.92 调查结果 : 10.19 公干: 12.65政府制定: 10.30 政府建立: 13.68所属部门: 10.30 调度: 12.87 基层官员: 10.92公务用车: 11.24 外出办公: 深圳论坛-第一现场_p_214_我们的目的是：迫使政府建立新的公车管理制度10.92公车管理: 12.65 在第二组实验中,采用本文提出的 BSDFS 算法计算词汇权重。在该算法中,对 BBS 短文篇幅小的特点进行优化,考虑多数据源、帖子文本结构的特点,实验结果如表 2 所示: 表二-采用本文提出的 BSDFS 算法计算词汇权重话题 相关帖子 关键词及权重奥一论坛-有话问市长_p_1547_深圳市李峰副市长接见参战老兵代表并重视老兵诉求深圳论坛-第一现场_p_186_让我们参战退役老兵生活得更有尊严奥一论坛-有话问市长_p_1853_请给深圳的优抚对象免费乘坐公交等最实际的关怀让我们参战退役老兵生活得更有尊严!退役: 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奥一论坛-深圳视点_p_2087_房价不降，房架降啦。哈哈深圳论坛-第一现场_p_1734_第一现场100407播出：后海填海区路面是波浪栏杆在扭腰奥一论坛-深圳视点_p_2077_深圳填海区豪宅沉降最高深达12厘米深圳填海区豪宅沉降最高深达 12 厘米后海：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 深圳论坛-第一现场_p_1_公车门房某回应：周末开公车是去办公事奥一论坛-深圳视点_p_1877_公车门调查组死猪不怕开水烫奥一论坛-深圳视点_p_1966_疑偏袒公车门官员，深圳网民上监察局讨说法疑偏袒公车门官员，深圳网民上监察局讨说法调查组: 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 公车管理:14.88 死猪不怕开水烫: 17.23通过实验结果对比，我们可以发现同样的话题，其相关帖子以及关键词的权重都发生了变化。由于 BSDFS 算法考虑了来自不同数据源的影响，出现在不同数据源的关键词的权重将指数级增长，因此，来自不同数据源的帖子更容易地聚到同一个话题。同时，出现在帖子标题的关键词权重也得到提高，其对聚类结果的影响也相应提高。实验表明，通过 BSDFS 算法进行特征提取，BBS 话题检测聚类结果更加准确、更加有效。4. 结束语本文从分析 BBS 热点话题检测入手，针对 BBS 短文本特征提取进行了深入细致的探讨和研究。在基于 TF*PDF 的基础上，我们提出 BSDFS(BBS Short Document Feature Selection)算法，它适用于多数据源、短文篇幅小、文本内容不规范的 BBS 短文本特征提取。实验结果表明,该算法可以有效挖掘 BBS 上的热点话题。通过有效地提取特征形成有效代表帖子的文本向量，在 BBS 热点话题检测的精度与效率方面有较大提高。然而系统中各聚类算法、参数和阈值的选择仍是值得研究的问题。参考文献：1 Internet Forum Software. /wiki/category:internet_forum_software2 中国互联网信息中心.第 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 Processing ( IJCNL P 04 ) . Hainan, China :LNAI 3248 , 2004 :139 21484 Kobayashi N, Iida R, Inui K et a1. Opinion mining as extraction of attribute-value relations. New Frontiers in Artificial Intelligence, 2006, 4012: 4704815 Zhang Y, Li Z, Ren F et a1. Semi-automatic emotion recognition from textual input based on the constructed emotion thesaurus. IEEE, 2005: 5715766 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 CategorizationA . Processing of ICML297 ,14th Interna2 tional Conference on Machine LearningC ,1996. 143 1518 庞剑锋,卜东波 ,白硕.基于向量空间模型的文本自动分类系统的研究与实现J . 计算机应用研究,2001 ,18 (9) :23 - 26BBS Short Document