文本挖掘主要技术研究

文本挖掘主要技术研究摘要：Web 技术的发展日新月异，与此同时，因特网上的文本信息愈积愈多，浩如烟海。如何从这些海量文本数据挖掘出潜在的、有价值的信息，已经成为越来越多人的研究重点。本文主要介绍了文本挖掘的基本方法，包括文本特征提取、特征子集选取、文本分类、文本聚类等，并对这些方法的改进进行了分析。在此基础上，介绍了文本挖掘在当今一些领域的应用。关键词：文本挖掘 特征提取 特征子集选取 文本分类 文本聚类 应用Research of Major Technologies in Text Mining【Abstract】With the rapid development of Web technology, text information on the Internet has a tremendous growth. How to dig out the potential and valuable information from the text information on the Internet has become the focus of many peoples research. This paper describes the basic methods of text mining, including text feature extraction, feature subset selection, text categorization, text clustering, etc., it makes some analysis on how to improve some of these methods. In addition, it introduces the application in some fields with text mining technology. 【Key words】text mining, feature extraction, feature subset selection, text categorization, text clustering, application1、 文 本 挖 掘 概 述文本挖掘 1( Text Mining,TM)，又称为文本数据挖掘 (Text Data Mining,TDM) 或文本知识发现 ( Knowledge Discovery in Texts , KDT) , 是指为了发现知识，从大规模文本库中抽取隐含的、以前未知的、潜在有用的模式的过程 2。它的主要用途是从原本未经使用的文本中提取出未知的知识。但是文本挖掘也是一项非常困难的工作，因为它必须处理那些本来就模糊而且非结构化的文本数据，所以它是一个多学科混杂的领域，涵盖了信息技术、文本分析、模式识别、统计学 、数据可视化 、数据库技术、机器学习以及数据挖掘等技术 3。本文主要从文本挖掘的特征提取、文本分类、聚类等方面对文本挖掘技术进行全面的分析。2、 文 本 特 征 提 取与数据库中的结构化数据相比， Web文档具有有限的结构，或者根本就没有结构。即使具有一些结构，也是着重于格式，而非文档内容。不同类型文档的结构也不一致。此外，文档的内容是人类所使用的自然语言，计算机很难处理其语义。 文本信息源的这些特殊性使得现有的数据挖掘技术无法直接应用于其上。 我们需要对文本进行预处理，抽取代表其特征的元数据。这些特征可以用结构化的形式保存，作为文档的中间表示形式。文本特征指的是关于文本的元数据，分为描述性特征，例如文本的名称、日期、大小、类型等 ; 以及语义性特征，例如文本的作者、机构、标题、内容等。描述性特征易于获得，而语义性特征则较难得到。 W3C近来制定的XML4、 RDF5等规范提供了对 Web文档资源进行描述的语言和框架。 在此基础上，我们可以从半结构化的 Web文档中抽取作者、机构等特征。特征表示 6是指以一定的特征项 ( 如词条或描述 )来代表文档信息 , 特征表示模型有多种 , 常用的有布尔逻辑型、向量空间型、概率型等。近年来应用较多且效果较好的特征表示法是向量空间模型 ( Vector Space Model, VSM) 法 7。在 VSM 中 , 将每个文本文档 d 看成是一组词条 ( T 1, T 2, , T n) 构成 , 对于每一词条 Ti，都根据其在文档 d中的重要程度赋予一定的权值Wi，可以将其看成一个 n维坐标系，W1， W2Wn为对应的坐标值 , 因此每一篇文档都可以映射为由一组词条矢量张成的向量空间中的一点，对于所有待挖掘的文档都用词条特征矢量 ( T 1, W1( d) , T 2, W2( d ) T n, Wn( d) ) 表示。这种向量空间模型的表示方法，可以将 d中出现的所有单词作为 Ti，也可以将 d中出现的所有短语作为 Ti，从而提高特征表示的准确性。Wi ( d )一般被定义为 Ti在 d中出现率 tfi ( d) 的函数 ,常用的有布尔函数，平方根函数，对数函数，TFIDF函数等。3、 文 本 特 征 子 集 选 取构成文本的词汇数量是相当大的， 因此表示文本的向量空间的维数也相当大， 可以达到几万维， 因此需要进行维数压缩的工作。目前对 WWW 文档特征所采用的特征子集 8选取算法一般是构造一个评价函数，对特征集中的每一个特征进行独立的评估， 这样每个特征都获得一个评估分，然后对所有的特征按照其评估分的大小进行排序， 选取预定数目的最佳特征作为结果的特征子集。一般用的评估函数 9有几率比 ( Odds ratio) 、信息增益 ( Information Gain) 、期望交叉熵 ( Expect ed CrossEntropy) 、互信息 ( Mutual Information) 、词频 ( Word Frequency) 等，限于篇幅，本文并不详细介绍。4、 文 本 分 类分类 10(Categorization or Classification)就是按照某种标准给对象贴标签 (label)，再根据标签来区分归类。分类是事先定义好类别，类别数不变。分类器需要由人工标注的分类训练语料训练得到，属于有指导学习范畴。本文介绍了常用的分类算法，其中对朴素贝叶斯和 KNN算法进行了详细的介绍。4.1 朴素贝叶斯贝叶斯分类是一种统计学分类方法，它基于贝叶斯定理，公式如下： )(|)(APBABP图 1 朴素贝叶斯分类流程图它可以用来预测类成员关系的可能性，给出文本属于某特定类别的概率，分类时根据预测结果将该样本分到概率最高的类别中去即可。朴素贝叶斯分类模型训练的过程其实就是统计每一个特征在各类中出现规律的过程，从理论上，讲贝叶斯分类的出错率最小，就试验结果来看，朴素贝叶斯在大型的数据集上表现出来难得的速度和准确度。朴素贝叶斯分类的正式定义如下：1、设 为一个待分,.21max类项，而每个 a 为 x 的一个特征属性。2、有类别集合 。,.21nyC3、计算。)|()|(,21 xPxyPn4、如果 ,.ma)|21yxnk，则 。ky朴素贝叶斯分类器 (native Bayes)假设特征对于给定类的影响独立于其它特征，即特征独立性假设。对文本分类来说，它假设各个单词 Wi 和 Wj 之间两两独立。设训练样本集分为 k 类，记为 C =C1， C2， ， Ck，则每个类 Ci 的先验概率为 P(Ci)， i =1 ， 2， ， k ，其值为 Ci 类的样本数除以训练集总样本数 n 。对于新样本 d ，其属于 Ci 类的条件概率是 。)|(dCPi根据贝叶斯定理， Ci 类的后验概率为 ；)|(CPi)(|dPCdii（1）P(d)对于所有类均为常数，可以忽略， 则式 (1)简化为：)(|)(iiCPdCP（2）为避免 P(Ci)等于 0 ，采用拉普阿斯概率估计 :（3）|1)(ciiDCP式中 : C 为训练集中类的数目，DCi 为训练集中属于类 Ci 的文档数，DC 为训练集包含的总文档数。在特殊情况下，训练样本集中各类样本数相等 ，此时类的先验概率相等 ，式(2) 可以简化：（4 ）)|()(iiCdPCP朴素贝叶斯分类器将未知样本归于类 i的依据如下 :.,21),(|maxrg)|(kjCPddCPjji（5）文档 d 由其包含的特征词表示， 即 d =(w1， wj，w m) ，m 是 d 的特征词个数 d， wj 是第 j 个特征词，由特征独立性假设 ，则得 mjiimi CPPC121 )|(),.()|（6）式中: 表示分类器预测单)|(ijCP词 wj 在类 Ci 的文档中发生的概率 。 因此式(2) 可转换为|1)()|(djijii CPCdCP（7）为避免式(7)中 等于 0，可)|(ijCP以采用拉普拉斯概率估计。有两种方法计算 ， 即文档)|(ijCP型计算公式和词频型计算公式。(1)文档型: 不考虑单词在文档中的出现频次，仅考虑单词在文档中是否出现，0 表示未出现，1 表示出现，依式 (8)计算:|2)(1)|(cijijDCwdoNCwP（8）式中 : 为 Ci 类文)(ijCwdoN本中出现特征 wj 的文本数 。(2)词频型: 考虑单词在文档中出现的频次，依式(9)计算 :|1),()|(vkikjij CwTFVCwP（9）式中: V 表示特征词表中总单词数， TF(wj， Ci)表示单词 wj 在类 Ci 的所有文档中出现的频次之和。114.2 K 近邻分类 K-nearest neighbor图 2 KNN 决策过程图KNN 分类算法的主要思想是：先计算待分类样本与已知类别的训练样本之间的距离或相似度 ，找到距离或相似度与待分类样本数据最近的 K 个邻居;再根据这些邻居所属的类别来判断待分类样本数据的类别。如果待分类样本数据的 K 个邻居都属于一个类别 ，那么待分类样本也属于这个类别。否则 ，对每一个候选类别进行评分 ，按照某种规则来确定待分类样本数据的类别12。我们采用欧氏距离来确定样本的相似性。欧氏距离的计算公式为：niyxyxd12)(),(KNN 以简单和高鲁棒性而被广泛应用于机器学习和数据挖掘领域，被证实是向量空间模型(VSM)下最好的文本分类方法之一。然而 KNN 算法有其固有的缺点，当训练样本集过大或特征过多时，KNN 算法的效率会明显下降13。鉴于此，卜凡军等提出了基于向量投影的 PKNN 算法14 。 4.3 KNN 改进算法 PKNNKNN 算法的计算量主要花费在分类阶段：每次对一个待分类样本分类时，都要计算其与所有训练样本的距离，如果对大量高维数据进行分类，那么计算开销将是非常大的。因此，基于 iDistance15降维思想和向量投影理论的改进 KNN 的 PKNN 算法，能够快速准确地选取很小的训练样本库，可以大大提高效率。PKNN 算法流程(1)读入训练样本 Yi(i = 1，2，n)：由式(3)求出训练样本的中心 M。(2)根据式(1) 计算各训练样本点与中心点 M 的欧氏距离，可得距离 M 的最远点 Ymax。(3)根据文中的方法求出各训练样本点在 MYmax 上的投影距离 Di(i = 1，2，n)，(-|MYmax|Di|MYmax|)，并对 Di排序。(4)读入一个待分类点 x，求 x 在向量 max 上的投影距离 Dx。(5)采用二分搜索的方法搜索获得训练样本中 Di 与 Dx 最近的 n1 个点。(6)通过计算这 n1 个点与 x 的欧氏距离获得最近的 K 个点，根据这 k 个点的类别属性得出 x 所属的类。(7)读入下一个待分类点，循环步骤(4)(6)。4.4 决策树 Decision Tree决策树( Decision T ree) 是用于分类和预测的主要技术， 它着眼于从一组无规则的事例推理出决策树表示形式的分类规则，采用自顶向下的递归方式， 在决策树的内部节点进行属性值的比较， 并根据不同属性判断从该节点向下分支， 在决策树的叶节点得到结论。 因此，从根节点到叶节点就对应着一条合理规则， 整棵树就对应着一组表达式规则。 基于决策树算法的一个最大的优点是它在学习过程中不需要使用者了解很多背景知识， 只要训练事例能够用属性即结论的方式表达出来， 就能使用该算法进行学习16。5、 文 本 聚 类5.1 聚类概述聚类是根据数据的不同特征 ，将其划分为不同的数据类。它的目的是使得属于同一类别的个体之间的距离尽可能的小 ，而不同类别上的个体间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法17。聚类流程如下：图 3 聚类流程图185.2 文本聚类概述文本聚类主要是依据著名的聚类假设 :同类的文档相似度较大，而不同类的文档相似度较小。作为一种无监督的机器学习方法，它在给定的某种相似性度量下把对象集合进行分组 ，使彼此相近的对象分到同一个组内。文本聚类根据文档的某种联系或相关性对文档集合进行有效的组织、摘要和导航，方便人们从文档集中发现相关的信息。文本聚类方法通常先利用向量空间模型把文档转换成高维空间中的向量，然后对这些向量进行聚类。由于中文文档没有词的边界，所以一般先由分词软件对中文文档进行分词，然后再把文档转换成向量，通过特征抽取后形成样本矩阵，最后再进行聚类，文本聚类的输出一般为文档集合的一个划分。5.3 文本聚类的算法5.3.1 基于层次的方法一个层次的聚类算法19将数据对象组织成一棵聚类的树。根据层次分解是自底向上还是自顶向下形成，层次的聚类算法可以进一步分为凝聚的(agglomerative)和分裂的(divisive)层次聚类。凝聚的层次聚类，首先将每个文本对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者终止条件满足。分裂的层次聚类，与凝聚的层次聚类相反，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者终止条件满足。对于给定的文档集合 D = d1， di， dn ，层次凝聚法的过程如下:(1)将 D 中的每个文本 di 看作是具有单个成员的类 ci = di ，这些类构成了 D 的一个聚类 C = c1，ci， cn ;(2)计算 C 中每对类( ci，cj )之间的相似度 sim ( ci，cj ) ;(3)选取具有最大相似度的类对，并将ci 和 cj 合并为一个新的类 ck ，从而构成了 D 的一个新的聚类 C = c1， ci， ， cn - 1 ;(4)重复上述步骤，直到 C 中剩下一个类为止。5.3.2 基于划分的方法（k-means 及其改进算法）k - means (K - 平均)是一种典型的基于划分的方法。是一种基于质心的聚类技术，其基本原理是首先选择 k 个文档作为初始的聚类点，然后根据簇中对象的平均值，将每个文档( 重新) 赋给最类似的簇，并更新簇的平均值，然后重复这一过程，直到簇的划分不再发生变化20。k- means 的算法复杂度为 O ( kln) ，其中 l 为迭代次数，n 为文档个数， k 为类别个数。kmeans 算法描述：输入：簇的数目 k，包含 n 个文本的特征向量。输出：k 个簇，使平方误差准则最小。步骤：(1)任意选择 k 个对象作为初始的簇中心；(2) repeat；(3)根据簇中对象的平均值，将每个对象(重新) 赋给最类似的簇；(4)更新簇的平均值；(5) until 不再发生变化。本文通过 C+实现了 k-means 算法，划分结果示例截图如下：图 4 k-means 算法聚类示例图由上述算法可知， k - means 具有高效率，并有效处理大文本集的优点。k - means 算法本质上是一种贪心算法。可以保证局部最小，但是很难保证全局最小。传统的 k-means 算法对初始聚类中心敏感，不同的初始中心往往对应着不同的聚类结果。袁方等21提出了一种优化初始聚类中心的改进 k-means 算法。优化初始聚类中心改进 k-means 算法描述如下：输入：聚类个数 k 以及包含 n 个数据对象的数据集；输出：满足目标函数值最小的 k 个聚类。(1)计算任意两个数据对象间的距离；),(jixd(2)计算每个数据对象的密度参数，把处于低密度区域的点删除，得到处于高密度区域的数据对象的集合 D；(3)把处于最高密度区域的数据对象作为第 1 个中心 z1；(4)把 z1 距离最远的数据对象作为第 2 个初始中心 z2，z2D ；(5)令 z3 为满足nizxdii,.1),(max(21的数的数据对象 ， ；iD3(6)令 z4 为满足nizxdzxdiii,.21),()(ma321的数的数据对象 ， ；iD4(7)令 zk 为满足1,.21;,.21)(maxnkjizdi的数据对象 ， ；iDk(8)从这 k 个聚类中心出发，应用 k-means 聚类算法，得到聚类结果。经改进的 k-means 算法与原算法准确率比较结果如下：图 5 k-means 算法与改进 k-means 算法的比较图可见在多数数据集中，改进算法要比原 k-means 算法的准确率高。6、 文 本 挖 掘 应 用文本挖掘最大的动机是来自于潜藏于电子形式中的大量的文本数据。利用数据挖掘技术处理公司大量的文本数据, 将给企业带来巨大的商业价值。另外人们对于文本挖掘的感兴趣的原因还在于：人们有时候并不知道他们到底要找什么, 而挖掘能够从数据库中抽取出许多有用的信息。目前，文本挖掘在搜索引擎、舆情分析、用户推荐等各个领域都有所应用，本文简单介绍下其在舆情分析下22的应用。6.1 网络舆情分析6.1.1 对网络舆情进行描述通过对网络舆情信息的文本挖掘， 可以生成有关网上针对某一社会公共事件存在的不同的民众情绪、态度、观点即网络舆情的总体概括的描述性信息。如利用文本特征提取可以了解舆情信息涉及的具体社会问题、发现并追踪社会热点和焦点内容、利用文本分类技术可以判断该事件反映哪类社会问题。6.1.2 对网络舆情的关联性进行分析文本挖掘可以从时间与空间分析事件之间的关联性， 发现从时空角度关联事件的发展规律及发展趋势。如通过文本挖掘分析法可以明确舆情信息产生者与舆情信息特征之间的关联性， 这样就能通过分析舆情信息的特征来追溯舆情信息的来源。网络信息的主题检测和追踪技术可以在海量网络信息中， 自动发现突发事件的舆情信息流主题。文本挖掘技术可跟踪突发事件的相关信息， 实现网络舆情热点焦点信息的自动发现，可以有效的辅助发现并预警不良信息，起到辅助决策支持的作用。6.1.3 真实性进行判断分析，意图倾向推论 网上虚假信息和不良信息会引发错误舆情导向， 需要通过文本挖掘对其进行判定和掌控。网络舆情信息在大多数情况下真实地表达出了民众的态度和情绪， 如通过网站所发布的对时政问题的讨论， 可以推断其观点和立场。6.1.4 对网络舆情的产生原因进行分析文本挖掘技术利用多维分析对舆情信息进行跨时间、跨空间的综合分析，描述起因事件发生的全貌及产生的影响。网络还大量存在着歪曲、偏激地反映社会现实、现代社会的价值观念的舆情信息， 甚至还有别有用心的人，在网上散布虚假信息。在这种情况下，通过文本挖掘分析法，可以比较网络舆情信息与社会现实状况， 对虚假信息追根溯源， 及时消除其不良影响。6.1.5 预测和推论网络舆情信息的产生和变化趋势舆情一经产生，便处在动态变化之中，对网络舆情变动趋势的预测， 对于管理决策者有着重要的意义23。7、 结 束 语本文对文本挖掘的主要技术进行了详细的介绍和分析，并对相关技术的改进算法进行了探讨。目前文本挖掘尤其是中文文本挖掘，还是有很大的研究空间。现有的一些中文文本挖掘对语义理解方面做的还不够多，当然，这与中文的博大精深有一定的关系。笔者导师的研究方向是 Web 海量信息处理和垂直搜索。目前笔者导师的团队在做垂直搜索引擎的过程中，一直都涉及文本处理、文本挖掘、文本分析等方面，现有的文本挖掘技术虽然比较成熟，但是在特定项目中，还是存在覆盖面不够的情况。各类 Web 文本挖掘技术，技术虽然成熟，但大部分成果都是基于统计，很少有基于理论的，笔者希望在今后的研究道路上，能够对相关技术进行进一步的探讨与改进，尤其期盼在基于理论的文本挖掘技术方面能够有一些出彩的成果。 参考文献1谌志群, 张国煊. 文本挖掘研究进展J. 模式识别与人工智能, 2005:65-74.2谌志群, 张国煊 . 文本挖掘与中文文本挖掘模型研究J. 情报科学, 2007, (7):1046-1051.3 梅馨, 邢桂芬. 文本挖掘技术综述 J. 江苏大学学报：自然科学版, 2003, (5):72-76.4 Bray T, Paoli J, Sperberg -McQu een C M. Ext ens ibl e Markup Language ( XML ) 1. 0 specifi cati on. World Wide Web Cons ortium Recommendati on. 1998. h t tp: / /ww w . w 3. org / TR /REC-xml /5 Las sila O, Sw ick R R. Res ource Des crip tion Fram ew ork ( RDF ) Model and Syn tax Speci fication. World Wide Web Cons ortiumRecommendati on. 1999. h t tp: / /ww w . w 3. org / TR /REC-rdf-syn tax /6 张卫丰, 徐宝文, 周晓宇. Web 搜索引擎综述 J . 计算机科学,2001, 28( 9) : 24- 28.7 Salt on G, Wong A, Yang C S. A vect or s pace model fo r aut omatic indexing. Commu ni cati ons of the ACM , 1975, 18( 5): 613 6208 许高建. 基于 Web 的文本挖掘技术研究J. 计算机技术与发展, 2007, (6):187-190.9 杨炳儒. 知识工程与知识发现 M. 北京: 冶金工业出版社, 2000: 5- 20.10 Han Jiawei, Kamber M. Data Mining: Concept and