文本分类与聚类(text categorization and clustering)1.概述广义的分类（classification或者categorization）有两种含义：一种含义是有领导的学习（supervised learning）过程，另一种是无领导的学习（unsupervised learning）过程。

通常前者称为分类，后者称为聚类（clustering），后文中提到的分类都是指有指点的学习过程。

给定分类系统，将文本集中的每个文本分到某个或者某几个类别中，这个过程称为文本分类（text categorization）。

将文本聚集分组成多个类或簇，使得在同一个簇中的文本内容具有较高的相似度，而不同簇中的文本内容差异较大，这个过程称为文本聚类（text clustering）。

2. 文本分类2.1 文本分类的步骤典范的文本分类进程可以分为三个步骤：1. 文本表现（Text Representation）这一过程的目标是把文本表示成分类器能够处理的情形。

最常用的方法是向量空间模型，即把文本集表示成词－文档矩阵，矩阵中每个元素代表了一个词在相应文档中的权重。

选取哪些词来代表一个文本，这个过程称为特点选择。

常见的特征选择方法有文档频率、信息增益、互信息、期看交叉熵等等。

为了减少分类过程中的计算量，经常还需要进行降维处理，比如LSI。

2. 分类器构建（Classifier Construction）这一步骤的目标是选择或设计构建分类器的方法。

没有一种通用的方法可以实用所有情形。

不同的方法有各自的优缺点和实用条件，要依据问题的特色来选择一个分类器。

后面专门讲述常用的方法。

选定方法之后，在训练集上为每个种别构建分类器，然后把分类器利用于测试集上，得到分类结果。

3. 后果评估（Classifier Evaluation）在分类过程完成之后，需要对分类后果进行评估。

评估过程运用于测试集（而不是训练集）上的文本分类结果，常用的评估尺度由IR范畴继续而来，包括查全率、查准率、F1值等等。

对于某一类别i，查全率ri=li/ni，其中ni为所有测试文档中，属于第i类的文档个数；li是经分类系统输出分类结果为第i类且结果准确的文档个数。

查准率pi=li/mi，其中mi是经分类体系输出分类结果为第i类的文档个数，li是经分类系统输出分类结果为第i类且结果准确的文档个数。

F1值为查全率和查准率的协调均匀数，即：。

相对于最简略的练习集－测试集评估办法而言，还有一种称为k-fold cross validation的方式，即把所有标志的数据划分成k个子集，对于每个子集，把这个子集当作训练集，把其余子集作为测试集；这样履行k 次，取各次评估成果的均匀值作为最后的评估结果。

2.2 常见的文本分类方法1. Rocchio方法每一类断定一个中心点（centroid），计算待分类的文档与各类代表元间的间隔，并作为判定是否属于该类的判据。

Rocchio方法最早由[Hull, 1994]引进文本分类范畴，后来又有很多文章进行了改良。

Rocchio方法的特点是轻易实现，效力高。

缺点是受文本集分布的影响，比如计算出的中心点可能落在相应的类别之外[Sebastiani, 2002]。

2. 朴实贝叶斯（naive bayes）方式将概率论模型利用于文档主动分类，是一种简略有效的分类方法。

应用贝叶斯公式，通过先验概率和类别的条件概率来估量文档对某一类别的后验概率，以此实现对此文档所属类别的断定。

[Lewis, 1998]介绍了朴实贝叶斯方法的发展和各种变体及特点。

3. K近邻(K-Nearest Neightbers, KNN)办法从训练集中找出与待分类文档最近的k个邻居（文档），根据这k个邻居的类别来决议待分类文档的类别。

KNN方法的长处是不需要特征选取和训练，很轻易处理类别数目多的情形，缺陷之一是空间复杂度高。

KNN方法得到的分类器是非线性分类器。

此方法最早由[Yang & Chute, 1994]提出。

4. 支撑向量机（SVM）方法对于某个类别，找出一个分类面，使得这个种别的正例和反例落在这个分类面的两侧，而且这个分类面满足：到最近的正例和反例的间隔相等，而且是所有分类面中与正例（或反例）距离最大的一个分类面。

SVM 方法最早由[Joachims, 1998]引进到文本分类中。

SVM方法的长处是应用很少的练习集，计算量小；毛病是太依附于分类面邻近的正例和反例的地位，具有较大的偏执。

其他常用的方法还包含决策树方法和神经网络方法，详见文献[Sebastiani, 2002]。

2.3 常用源码和数据集Weka是一个开源的机器学习软件，集成了数据预处置、机器学习算法、可视化功效，实现了大部分常见的机器学习算法，包含分类。

Weka 是国外有名教材《Data Mining: Practical Machine Learning Tools and Techniques (Second Edition)》所采取的试验平台。

与Weka相竞争的另一个开源的机器学习软件是Yale，自称实现了Weka的所有算法，兼容Weka的数据格局。

现在已经商业化。

与Weka和Yale不同，Bow是专门为文本处理设计的开源包。

Bow包括三个部分：Rainbow（文本分类）、Arrow（文本检索）和Crossbow（文本聚类）。

文本分类常用的数据集有REUTERS,20NEWSGROUP,OHSUMED等语料库。

3. 文本聚类文本聚类有很多运用，比如进步IR系统的查全率，导航/组织电子资源，等等。

是一个成熟的文本聚类体系。

依据聚成的簇的特色，聚类技术通常分为层次聚类（hierarchical clustering）和划分聚类（partitional clustering）。

前者比拟典范的例子是凝集层次聚类算法，后者的典范例子是k-means算法。

近年来呈现了一些新的聚类算法，它们基于不同的理论或技巧，比如图论，含混集理论，神经网络以及核技术（kernel techniques）等等。

3.1 文本聚类的步骤与文本分类相似，文本聚类过程可以分为3个步骤：1. 文本表现（Text Representation）把文档表现成聚类算法可以处置的情势。

所采取的技巧请参见文本分类部分。

2. 聚类算法选择或设计（Clustering Algorithms）算法的选择，往往需要考虑相似度计算方法。

在文本发掘中，最常用的相似度计算方法是余弦相似度。

聚类算法有很多种，但是没有一个通用的算法可以解决所有的聚类问题。

因此，须要认真研讨要解决的问题的特色，以选择适合的算法。

后面会有对各种文本聚类算法的内容。

3. 聚类评估（Clustering Evaluation）由于没有训练文档聚集，所以评测聚类后果是比较艰苦的。

常用的方法是：选择人工已经分好类或者做好标志的文档聚集作为测试集合，聚类停止后，将聚类结果与已有的人工分类结果进行比较。

常用评测指标也是查全率、查准率及F1值。

3.2 常见的文本聚类算法1．层次聚类方法层次聚类可以分为两种：凝集（agglomerative）层次聚类和划分（divisive）层次聚类。

凝集方法把每个文本作为一个初始簇，经过不断的合并进程，最后成为一个簇。

划分方法的进程正好与之相反。

划分方法在现实中采用较少，有关阐述请见[Kaufman & Rousseeuw, 1990]。

层次聚类可以得到层次化的聚类成果，但是计算复杂度高，不能处置大批的文档。

近年来呈现了新的层次聚类算法，包含CURE[Guha, Rastogi & Shim, 1998], ROCK[Guha, Rastogi & Shim, 2000], Chameleon[Karypis, Han & V. Kumar, 1999]和BIRCH[Zhang, Ramakrishnan & Livny, 1996]。

2．划分方法k-means算法是最常见的划分方法。

给定簇的个数k，随机选定k个文本作为k个初始簇，然后遍历剩下的所有文档，分别计算与这k个文档的相似度（如量化为距离）。

将其他的文本加入到最近的簇中，并更新簇的中心点，然后再根据新的中心点对文本重新划分；当簇不再变更时或经过一定次数的迭代之后，算法结束。

k-means算法复杂度低，而且轻易实现，但是对例外和噪声文本比较敏感。

另外一个问题是，没有一个好的措施断定k的取值。

相干文献参见[Forgy, 1965][Xu & Wunsch, 2005]。

3．基于密度的办法为了发现任意形状的非均匀分布的聚类，提出了基于密度的方法。

这类方法将簇看作是数据空间中被低密度区域分割开的高密度区域。

常见的基于密度的方法有DBSCAN,OPTICS, DENCLUE等等，参考文献见[Han & Kamber, 2006]。

4．神经网络方式神经网络方法将每个簇描写为一个标本，标本作为聚类的"原型"，不必定对应一个特定的数据,依据某些间隔度量，新的对象被分配到与其最类似的簇中。

比较有名的神经网络聚类算法有:竞争学习（competitive learing）和自组织特点映射（self-organizing map）[Kohonen, 1990]。

神经网络的聚类方法须要较长的处理时间和庞大的数据庞杂性，所以不实用于大型数据的聚类。

其他常见的方法包括基于图论的聚类算法[Jain & Dubes, 1988]、基于核的聚类算法[müller, Mika, R?tsch, et. al, 2001]、混合聚类算法[Höppner, Klawonn & Kruse, 1999]，等等。

3.3 常用的源码包和数据集前面提到的Weka、Yale、Bow这三个工具已经包括了常用的聚类算法，下面再介绍几个专门的聚类软件：Scipy: /The open source clustering softwares: http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/software/cluster/software.htm MICMOD: http://www-math.univ-fcomte.fr/mixmod/index.phpThe Semantic Indexing Project: /JUNG: /CompLearn: /目前还没有专门为文本聚类设计的数据集，一般可以采取文本的数据集REUTERS,20NEWSGROUP, OHSUMED等语料库）。

说明：本文转载地址已失效。

练习数据集汇总网址/summary.data.type.html（直接分类下载）/logs/37909800.html（分类链接）。