案例推理编程:文本分类与聚类(text categorization and clustering)

source: http://blog.rexian.net.cn/?uid-103964-action-viewspace-itemid-346301

1. 概述
        广义的分类（classification或者categorization）有两种含义：一种含义是有领导的学习（supervised learning）过程，另一种是无领导的学习（unsupervisedlearning）过程。通常前者称为分类，后者称为聚类（clustering），后文中提到的分类都是指有指点的学习过程。
        给定分类系统，将文本集中的每个文本分到某个或者某几个类别中，这个过程称为文本分类（textcategorization）。将文本聚集分组成多个类或簇，使得在同一个簇中的文本内容具有较高的相似度，而不同簇中的文本内容差异较大，这个过程称为文本聚类（text clustering）。
        [Berry, 2003]具体描写了文本发掘技巧。[Sebastiani, 2002]供给了对文本分类的综述。[Xu & Wunsch, 2005]对聚类算法做了全面的描写，[He, 1999]则重点讲述了聚类算法在IR中的利用。

2. 文本分类
        文本分类过程可以分为手工分类和主动分类。前者最著名的实例是yahoo的网页分类系统，是由专家定义了分类系统，然后人工将网页分类。这种方法须要大批人力，现实中已经采用的很少了。自动文本分类（automatic textcategorization）算法大致可以分为两类：知识工程（knowledge engineering）方法和机器学习（machinelearning）方法。知识工程方法指的是由专家为每个类别定义一些规矩，这些规矩代表了这个类别的特点，主动把符合规矩的文档划分到相应的种别中。这方面最有名的体系是CONSTRUE。上个世纪90年代之后，机器学习方法成为主导。机器学习方法与知识工程方法相比，能够到达类似的准确度，但是减少了大批的人工参与。我们下面重要介绍基于机器学习方法的文本分类。

2.1 文天分类的步骤
典范的文本分类进程可以分为三个步骤：
1. 文本表现（Text Representation）
这一过程的目标是把文本表示成分类器能够处理的情势。最常用的方法是向量空间模型，即把文本集表示成词－文档矩阵，矩阵中每个元素代表了一个词在相应文档中的权重。选取哪些词来代表一个文本，这个过程称为特点选择。常见的特征选择方法有文档频率、信息增益、互信息、期看交叉熵等等，[Yang &Pedersen , 1997 ]对这几种方法做了比较。为了下降分类过程中的计算量，经常还需要进行降维处理，比如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 crossvalidation的方式，即把所有标志的数据划分成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系统的查全率，导航/组织电子资源，等等。www.vivisimo.com是一个成熟的文本聚类体系。
        依据聚成的簇的特色，聚类技术通常分为层次聚类（hierarchical clustering）和划分聚类（partitionalclustering）。前者比拟典范的例子是凝集层次聚类算法，后者的典范例子是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-means算法复杂度低，而且轻易实现，但是对例外和噪声文本比较敏感。另外一个问题是，没有一个好的措施断定k的取值。相干文献参见[Forgy, 1965][Xu & Wunsch, 2005]。
3．基于密度的办法
为了发明任意外形的聚类成果，提出了基于密度的方法。这类方法将簇看作是数据空间中被低密度区域分割开的高密度区域。常见的基于密度的方法有DBSCAN,OPTICS, DENCLUE等等，参考文献见[Han & Kamber, 2006]。
4．神经网络方式
神经网络方法将每个簇描写为一个标本，标本作为聚类的"原型"，不必定对应一个特定的数据,依据某些间隔度量，新的对象被分配到与其最类似的簇中。比拟有名的神经网络聚类算法有:竞争学习（competitive learing）和自组织特点映射（self-organizingmap）[Kohonen, 1990]。神经网络的聚类方法须要较长的处理时光和庞杂的数据庞杂性，所以不实用于大型数据的聚类。
其他常见的方法包括基于图论的聚类算法[Jain & Dubes, 1988]、基于核的聚类算法[müller, Mika, R?tsch,et. al, 2001]、含混聚类算法[H?ppner, 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.htm
MICMOD: http://www-math.univ-fcomte.fr/mixmod/index.php
The Semantic Indexing Project: http://www.knowledgesearch.org/
JUNG: http://jung.sourceforge.net/
CompLearn: http://complearn.org/
目前还没有专门为文本聚类设计的数据集，一般可以采取文本分类的数据集（前面有先容）。

阐明：本文转载自网络http://fusion.grids.cn/wiki/pages/viewpage.action?pageId=1033

练习数据集汇总网址
http://kdd.ics.uci.edu/summary.data.type.html（直接分类下载）
http://jeffdai.blogbus.com/logs/37909800.html（分类链接）