文本分类聚类

《文本分类聚类》由会员分享，可在线阅读，更多相关《文本分类聚类（3页珍藏版）》请在装配图网上搜索。

1、文本分类与聚类(text categorization and clustering)1. 概述广义的分类(classification或者categorization)有两种含义：一种含义是有领导的学习(supervised learning) 过程，另一种是无领导的学习(unsupervised learning)过程。通常前者称为分类，后者称为聚类(clustering)， 后文中提到的分类都是指有指点的学习过程。给定分类系统，将文本集中的每个文本分到某个或者某几个类别中，这个过程称为文本分类( text categorization)。将文本聚集分组成多个类或簇，使得在同一个簇中的文本

2、内容具有较高的相似度，而不同 簇中的文本内容差异较大，这个过程称为文本聚类(t ext clustering)02. 文本分类2.1文本分类的步骤典范的文本分类进程可以分为三个步骤：1. 文本表现(Text Representation)这一过程的目标是把文本表示成分类器能够处理的情形。最常用的方法是向量空间模型，即把文本集表示 成词一文档矩阵，矩阵中每个元素代表了一个词在相应文档中的权重。选取哪些词来代表一个文本，这个 过程称为特点选择。常见的特征选择方法有文档频率、信息增益、互信息、期看交叉熵等等。为了减少分 类过程中的计算量，经常还需要进行降维处理，比如LSI。2. 分类器构建(Clas

3、sifier Construction)这一步骤的目标是选择或设计构建分类器的方法。没有一种通用的方法可以实用所有情形。不同的方法有 各自的优缺点和实用条件，要依据问题的特色来选择一个分类器。后面专门讲述常用的方法。选定方法之 后，在训练集上为每个种别构建分类器，然后把分类器利用于测试集上，得到分类结果。3. 后果评估(Classifier Evaluation)在分类过程完成之后，需要对分类后果进行评估。评估过程运用于测试集(而不是训练集)上的文本分类 结果，常用的评估尺度由IR范畴继续而来，包括查全率、查准率、F1值等等。对于某一类别i，查全率 ri=li/ni，其中ni为所有测试文档中，

4、属于第i类的文档个数；li是经分类系统输出分类结果为第i类且结 果准确的文档个数。查准率pi=li/mi，其中mi是经分类体系输出分类结果为第i类的文档个数，li是经分 类系统输出分类结果为第i类且结果准确的文档个数。F1值为查全率和查准率的协调均匀数，即：。相对于最简略的练习集一测试集评估办法而言，还有一种称为k-fold cross validation的方式，即把所有标 志的数据划分成k个子集，对于每个子集，把这个子集当作训练集，把其余子集作为测试集；这样履行k 次，取各次评估成果的均匀值作为最后的评估结果。2.2常见的文本分类方法1. Rocchio 方法每一类断定一个中心点(cent

5、roid)，计算待分类的文档与各类代表元间的间隔，并作为判定是否属于该类 的判据。Rocchio方法最早由Hull, 1994引进文本分类范畴，后来又有很多文章进行了改良。Rocchio方法 的特点是轻易实现，效力高。缺点是受文本集分布的影响，比如计算出的中心点可能落在相应的类别之外 Sebastiani, 2002。2. 朴实贝叶斯(naive bayes)方式将概率论模型利用于文档主动分类，是一种简略有效的分类方法。应用贝叶斯公式，通过先验概率和类别 的条件概率来估量文档对某一类别的后验概率，以此实现对此文档所属类别的断定。Lewis, 1998介绍了 朴实贝叶斯方法的发展和各种变体及特点

6、。3. K 近邻(K-Nearest Neightbers, KNN)办法从训练集中找出与待分类文档最近的k个邻居(文档)，根据这k个邻居的类别来决议待分类文档的类别。 KNN方法的长处是不需要特征选取和训练，很轻易处理类别数目多的情形，缺陷之一是空间复杂度高。 KNN方法得到的分类器是非线性分类器。此方法最早由Yang & Chute, 1994提出。4. 支撑向量机(SVM)方法对于某个类别，找出一个分类面，使得这个种别的正例和反例落在这个分类面的两侧，而且这个分类面满 足：到最近的正例和反例的间隔相等，而且是所有分类面中与正例(或反例)距离最大的一个分类面。SVM 方法最早由Joachi

7、ms, 1998引进到文本分类中。SVM方法的长处是应用很少的练习集，计算量小；毛病是 太依附于分类面邻近的正例和反例的地位，具有较大的偏执。其他常用的方法还包含决策树方法和神经网络方法，详见文献Sebastiani, 2002。2.3常用源码和数据集Weka是一个开源的机器学习软件，集成了数据预处置、机器学习算法、可视化功效，实现了大部分常见 的机器学习算法，包含分类。Weka是国外有名教材Data Mining: Practical Machine Learning Tools and Techniques (Second Edition)所采取的试验平台。与Weka相竞争的另一个开源的机

8、器学习软件是Yale，自称实现了 Weka的所有算法，兼容Weka的数据格 局。现在已经商业化。与Weka和Yale不同，Bow是专门为文本处理设计的开源包。Bow包括三个部分：Rainbow (文本分类)、 Arrow (文本检索)和Crossbow (文本聚类)。文本分类常用的数据集有REUTERS,20NEWSGROUP,OHSUMED等语料库。3.文本聚类文本聚类有很多运用，比如进步IR系统的查全率，导航/组织电子资源，等等。是一个 成熟的文本聚类体系。依据聚成的簇的特色，聚类技术通常分为层次聚类( hierarchical clustering)和划分聚类(partitional c

9、lustering)0前者比拟典范的例子是凝集层次聚类算法，后者的典范例子是k-means算法。近年来呈现了一 些新的聚类算法，它们基于不同的理论或技巧，比如图论，含混集理论，神经网络以及核技术(kernel techniques)等等。3.1文本聚类的步骤与文本分类相似，文本聚类过程可以分为3个步骤：1. 文本表现(Text Representation)把文档表现成聚类算法可以处置的情势。所采取的技巧请参见文本分类部分。2. 聚类算法选择或设计(Clustering Algorithms)算法的选择，往往需要考虑相似度计算方法。在文本发掘中，最常用的相似度计算方法是余弦相似度。聚 类算法有

10、很多种，但是没有一个通用的算法可以解决所有的聚类问题。因此，须要认真研讨要解决的问题 的特色，以选择适合的算法。后面会有对各种文本聚类算法的内容。3. 聚类评估(Clustering Evaluation)由于没有训练文档聚集，所以评测聚类后果是比较艰苦的。常用的方法是：选择人工已经分好类或者做 好标志的文档聚集作为测试集合，聚类停止后，将聚类结果与已有的人工分类结果进行比较。常用评测指 标也是查全率、查准率及F1值。3.2常见的文本聚类算法1. 层次聚类方法层次聚类可以分为两种：凝集(agglomerative)层次聚类和划分(divisive)层次聚类。凝集方法把每个文 本作为一个初始簇，

11、经过不断的合并进程，最后成为一个簇。划分方法的进程正好与之相反。划分方法在 现实中采用较少，有关阐述请见Kaufman & Rousseeuw, 1990。层次聚类可以得到层次化的聚类成果，但 是计算复杂度高，不能处置大批的文档。近年来呈现了新的层次聚类算法，包含CUREGuha, Rastogi & Shim, 1998, ROCKGuha, Rastogi & Shim, 2000, ChameleonKarypis, Han & V. Kumar, 1999和 BIRCHZhang, Ramakrishnan & Livny, 1996。2. 划分方法k-means算法是最常见的划分方法

12、。给定簇的个数k，随机选定k个文本作为k个初始簇，然后遍历剩下的 所有文档，分别计算与这k个文档的相似度(如量化为距离)。将其他的文本加入到最近的簇中，并更新 簇的中心点，然后再根据新的中心点对文本重新划分；当簇不再变更时或经过一定次数的迭代之后，算法 结束。k-means算法复杂度低，而且轻易实现，但是对例外和噪声文本比较敏感。另外一个问题是，没有 一个好的措施断定k的取值。相干文献参见Forgy, 1965Xu & Wunsch, 2005。3. 基于密度的办法为了发现任意形状的非均匀分布的聚类，提出了基于密度的方法。这类方法将簇看作是数据空间中被低密 度区域分割开的高密度区域。常见的基于

13、密度的方法有DBSCAN,OPTICS, DENCLUE等等，参考文献见 Han & Kamber, 2006。4. 神经网络方式神经网络方法将每个簇描写为一个标本，标本作为聚类的原型”，不必定对应一个特定的数据依据某些间 隔度量，新的对象被分配到与其最类似的簇中。比较有名的神经网络聚类算法有：竞争学习(competitive learing)和自组织特点映射(self-organizing map) Kohonen, 1990。神经网络的聚类方法须要较长的处理 时间和庞大的数据庞杂性，所以不实用于大型数据的聚类。其他常见的方法包括基于图论的聚类算法Jain & Dubes, 1988、基于核

14、的聚类算法muller, Mika, R?tsch, et. al, 2001、混合聚类算法Hoppner, Klawonn & Kruse, 1999，等等。3.3常用的源码包和数据集前面提到的Weka、Yale、Bow这三个工具已经包括了常用的聚类算法，下面再介绍几个专门的聚类软件：Scipy: http:/www.scipy.org/The open source clustering softwares: http:/bonsai.ims.u-tokyo.ac.jp/mdehoon/software/cluster/software.htmMICMOD: http:/www-math.univ-fcomte.fr/mixmod/index.phpThe Semantic Indexing Project: http:/www.knowledgesearch.org/JUNG: CompLearn: http:/complearn.org/目前还没有专门为文本聚类设计的数据集，一般可以采取文本的数据集REUTERS,20NEWSGROUP, OHSUMED等语料库)。说明：本文转载地址已失效。练习数据集汇总网址http:/kdd.ics.uci.edu/summary.data.type.html （直接分类下载） （分类链接）