1、21021064 程伟基于机器学习算法的文本分类方法综述基于机器学习算法的文本分类方法综述摘要：文本分类是机器学习领域新的研究热点。基于机器学习算法的文本分类方法比传统的文本分类方法优势明显。本文综述了现有的基于机器学习的文本分类方法，讨论了各种方法的优缺点，并指出了文本分类方法未来可能的发展趋势。1.1.引言引言随着计算机技术、数据库技术，网络技术的飞速发展，Internet 的广泛应用，信息交换越来越方便，各个领域都不断产生海量数据，使得互联网数据及资源呈现海量特征，尤其是海量的文本数据。如何利用海量数据挖掘出有用的信息和知识，方便人们的查阅和应用，已经成为一个日趋重要的问题。因此，基于文
2、本内容的信息检索和数据挖掘逐渐成为备受关注的领域。文本分类(text categorization，TC)技术是信息检索和文本挖掘的重要基础技术，其作用是根据文本的某些特征，在预先给定的类别标记(label)集合下，根据文本内容判定它的类别。传统的文本分类模式是基于知识工程和专家系统的，在灵活性和分类效果上都有很大的缺陷。例如卡内基集团为路透社开发的 Construe 专家系统就是采用知识工程方法构造的一个著名的文本分类系统，但该系统的开发工作量达到了 10 个人年，当需要进行信息更新时，维护非常困难。因此，知识工程方法已不适用于日益复杂的海量数据文本分类系统需求1。20 世纪 90 年代以来
3、，机器学习的分类算法有了日新月异的发展，很多分类器模型逐步被应用到文本分类之中，比如支持向量机(SVM，Support Vector Machine)2-4、最近邻法(Nearest Neighbor)5、决策树(Decision tree)6、朴素贝叶斯(Naive Bayes)7等。逐渐成熟的基于机器学习的文本分类方法，更注重分类器的模型自动挖掘和生成及动态优化能力，在分类效果和灵活性上都比之前基于知识工程和专家系统的文本分类模式有所突破，取得了很好的分类效果。本文主要综述基于机器学习算法的文本分类方法。首先对文本分类问题进行概述，阐述文本分类的一般流程以及文本表述、特征选择方面的方法，然
4、后具体研究基于及其学习的文本分类的典型方法，最后指出该领域的研究发展趋势。2 2文本自动分类概述文本自动分类概述文本自动分类可简单定义为：给定分类体系后，根据文本内容自动确定文本关联的类别。从数学角度来看，文本分类是一个映射过程，该映射可以是一一映射，也可以是一对多映射过程。文本分类的映射规则是，系统根据已知类别中若干样本的数据信息总结出分类的规律性，建立类别判别公式或判别规则。当遇到新文本时，根据总结出的类别判别规则确定文本所属的类别。也就是说自动文本分类通过监督学习自动构建出分类器，从而实现对新的给定文本的自动归类。文本自动分类一般包括文本表达、特征选取、分类器的选择与训练、分类等几个步骤
5、，其中文本表达和特征选取是文本分类的基础技术，而分类器的选择与训练则是文本自动分类技术的重点，基于机器学习的文本分来就是通过将机器学习领域的分类算法用于文本分类中来8。图 1 是文本自动分类的一般流程。21021064 程伟图 1 文本自动分类一般流程82.12.1 文本表述文本表述至今，计算机还不能像人类那样阅读完文章之后，根据自身的理解能力对文章的内容产生一定的认识。要使计算机能够高效率、高性能地处理自然文本，就需要有一个文本表示的过程，文本表示是将非结构化的文本文档表示为机器易于处理的形式的过程。文本表示通常包括文本预处理和文本模型表示等步骤，其中文本预处理为建立文本表示模型做必要的准备
6、工作。具体的文本标识方法有很多种模型，如布尔模型、布尔模型性、向量空间模型等。词包(Bag of Words)表示法是目前文本分类的标准模式。把文本看成是段落的集合，或者是句子的集合，也可以看成是单或字母的集合，而单词是组成文本的一个基本单位，研究者通常把一个文本当作是一系列单词的集合来表示，即所谓的词包表示法，它通过特征处理和统计学习算法的基础上获得对文本语义内容及类别信息的估计与预测。实际应用中空间向量模型(vector Space Modal,VSM)是常见的文本表示模型。在这种表示方式中，每篇文档表示成形如的向量，其中表示词条项，表示在文档 d 中的权值。如图 2 所示是向量空间模型。
7、向量空间模型已经在信息检索、文本分类等应用中取得了成功。除 VSM 外，还有基于概率分布、基于二维视图等模型。这些非VSM 的表示方法需要通过理论以及应用实践上的进一步验证。图 2 向量空间模型21021064 程伟2.22.2 特征提取特征提取特征提取是在初始全特征集基础上提取出一个特征子集的过程，能够起到降低向量空间维数、简化计算、防止过拟合作用。首先根据特征提取算法对特征的重要性进行评估，然后进行重要度排序，最后根据提取阈值或提取比率完成提取。提取后的特征集将用于之后的训练和分类过程。常用特征提取算法有文档频数(Document Frequency)、信息增益(informationGa
8、in)、期望交叉熵(expected cross entropy)、互信息(Mutual Information)、统计等。3 3基于机器学习的文本分类方法基于机器学习的文本分类方法3.13.1 基于朴素贝叶斯法的文本分类基于朴素贝叶斯法的文本分类朴素贝叶斯方法是最早用于文本分类的分类器算法，是一种统计学分类方法，它基于贝叶斯决策论并且基于此项独立的假设，几不同属性对分类结果的影响是独立的。假设 d 为待分类文档的表示向量，它属于文档类别集合中某一类。根据贝叶斯公式有：,j=1,2,n其中表示类别在样本集中的比重，由概率密度函数计算得出。分类时，值最大情况对应的类别为待分类文档类别。基于上述假
9、设的概率分类器一般称为贝叶斯分类器。贝叶斯分类器容易理解，计算简单而且比较实用，其分类效果基本能满足要求，但其关于词项独立性的假设受到了质疑。3.23.2 基于决策树法的文本分类基于决策树法的文本分类决策树学习是应用最广泛的归纳推理算法之一，它是一种逼近离散值函数的方法，对噪声数据有很好的健壮性且能够学习析取表达式。决策树着眼于从一组无次序无规则的事例中推理出决策树表示形式的分类规则，它通过把实例从根结点排序到某个叶子结点来分类实例，叶子结点即为实例所属的分类。在构造分类模型时，树上的每个结点指定了对实例属性集测试后选择出的属性，并且该结点的每一个后继分支对应于该属性的一个可能值。分类实例的时
10、候，就是从树的结点开始，测试这个结点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动，之后在新的结点上重复这个过程直到叶子结点，即获得分类。一般来说，决策树算法主要围绕两大核心问题展开：第一，决策树的生长问题，即利用训练样本集，完成决策树的建立过程；第二，决策树的剪枝问题，即利用检验样本集对形成的决策树进行优化处理。决策树的构建是一种自上而下、分而治之的归纳过程，本质是贪心算法。各种算法建树的基本过程相似，是一个递归的过程。设数据样本集为 S，算法框架如下：(1)如果数据样本集S 中所有样本都属于同一类或者满足其他终止准则，则 S不再划分，形成叶节点：(2)否则，根据某种策略选择一个属
11、性，按照属性的各个取值，对 S 进行划分，得到 n个子样本集，记为，再对每个迭代执行步骤(1)。经过 n 次递归，最后生成决策树。从根到叶节点的一条路径对应着一条规则，整棵决策21021064 程伟树就对应着一组析取表达式规则。为了防止决策树和训练样本集的过度拟合，特别是存在噪声数据或不规范属性时更为突出，需要对决策树进行剪枝。剪枝的算法通常利用统计方法决定是否将一个分支变为一个节点。通常采用两种方法进行决策树的剪枝，即在决策树生长过程完成前就进行剪枝的事前修剪法和在决策树生长过程完成后才进行剪枝的事后修剪法。决策树分类算法自提出以来，出现了很多种，早期的是 CLS 学习算法和 CART 算法
12、，最有影响的是 1986 年 Quinlan 提出的 ID3 算法。ID3 算法体现了决策树分类的优点：算法的理论清晰、方法简单，学习能力较强。缺点是：只对比较小的数据集有效，且对噪声比较敏感。在 ID3 算法的基础上，Quinlan 又发展了具有重要影响的 C4.5 算法，它继承并改进了ID3 算法，使用非常广泛。为了适应处理大规模数据集的需要，后来学者又提出了若干改进的算法，取得了较好的效果。决策树文本分类法分类精度较好，并且可以很好的抵抗噪声，但缺点是在处理大规模数据集的情况下效率不高。3.33.3 基于基于 K K 最近邻法的文本分类最近邻法的文本分类K 最近邻算法(k Nearest
13、 Neighbor,KNN)分类算法是传统的基于统计的模式识别方法，在文本分类领域使用较多。其算法思想是对于一篇待分类文档，在训练集中找到 K 个最相近的邻居。取这 K 个邻居的类别为该文档的候选类别，该文档与 K 个邻居之间的相似度为候选类别的权重，然后使用设定的相似度阈值就可以得到该文档的最终分类。KNN 算法也是基于向量空间模型的分类算法之一，最初由 Cover 和 Hart 于 1968 年提出，是一个理论上比较成熟的方法。采用 kNN 方法进行文档分类可以定义为：对于给定的文档集 D，把 D 中所有的文本内容形式化为特征空间中的加权特征向量 D，其中向量 D 表示为。对于某一给定的测
14、试文档 d，通过计算它与每个训练文档的相似度，找出 k 个最相似的文档。在此基础上，给每个文档类别加权打分，根据加权距离和判断测试文本所属的类别。根据上述表述，可以把 KNN 文本分类法归结为以下步骤：根据各种规则将文本内容变换成文本特征向量。根据相似度公式计算测试文本与每个训练文本的相似度，计算公式如下：其中，m 是特征向量维数，K 表示近邻个数，其具体数值的确定目前还没有很好的方法，一般采用先定一个初始值，然后通过实验测试调整 K 值，一般初始值定为几百到几千之间，但是要小于训练文档总数。从(2)的结果中选出 k 个相似度最大的训练集文档，计算分类权重，计算公式为：其中 d 表示文本特征向
15、量，即如果文档属于该类别值为 l，反之为 0。为阈值，对于某一特定类来说，是一个有待优化选择的值，可以通过一个验证文档集来进行调整。KNN 算法足向量空间模型下最好的分类算法之一，优点是易于快速实现，在基于统计的模式识别中非常有效，有较好的分类准确性和稳定性，尤其对于未知和非正态分布可以取得较高的分类准确率。KNN 可以较好地避免样本的不平衡问题，对于类域的交叉或重叠较多的待分样本集和样本容量较大的类域的分类较为适合，并且，它对训练数据中的噪声有很好的健壮性，当给定足够大的训练集合时也非常有效。总体来说 KNN 优于贝叶斯、决策树。然而作为一种懒散的学习算法，它也存在一些限制：一是空间开销大。
16、因为要事先存储全部训练样例，当训练样例增大时存储空间也随之增大。二是计算相似度时，实例间的距离是根据实例的所有属性来计算的，这与那些只选择全部实例属性的一个子集的方法不同，例如决策树。有些属性与分类相关性不大或无关时，可能会误导近邻算法的分类，近邻间的距离会21021064 程伟被大量的不相关属性所支配。这种由于存在很多不相关属性所导致的难题，有时被称为唯度灾难9。最近邻方法对这个问题特别敏感。解决的方法一般有两种，一是在计算两个实例间的距离时对每个属性加权，二是从实例空间中完全消除最不相关的属性。3.4 基于中心向量法的文本分类基于中心向量法的文本分类还有一类分类速度较快的基于向量空间模型的
17、文本分类算法是基于中心向量的分类法，又称为 Rocchio 算法10。中心向量法最初用于信息检索，现在已经被广泛应用于文本分类。中心向量法的基本思想是通过对训练集进行训练得到每一个已知类别的中心，称之为类中心向量，分类过程中将待分类文档与已知的类中心向量进行相似度比较，判定规则为相似度最大的类中心向量所代表的类别为待分类文档的类别。假设令表示训练集包含的 m 个类，则基于中心向量的文本分类过程为：对每一个类，计算该类中所有文档向量的算术平均作为该类的类中心向量；对于一个待分类文档 d，计算 d 与所有类中心向量的相似度并且返回相似度最大的类别最为结果。这里相似度的计算同 3.3 中步骤(2)的
18、相似度激素那方法相同。中心向量法适合于训练集中各类别大小相对均衡，且同类别文档分布稠密的情况，此时分类效果较好，但当训练集中各类别间大小不均衡且同类别文档分布稀疏时，分类效果较差。3.5 基于支持向量机的文本分类基于支持向量机的文本分类支持向量机(Support Vector Machines,SVM)是由 Vapnik 与其领导的贝尔实验室研究小组在 1995 年据统计学理论提出的一种用于解决二分类模式识别问题的学习方法。Joachims是最早将 SVM 方法用于文本分类中的，并且取得非常理想的分类效果。SVM 方法将文本分类问题变成了一系列二分类问题。SVM 算法是建立在统计学习理论的 V
19、C 维理论和结构风险最小原理基础上的，它将降维和分类结合在一起，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，这里模型的复杂性代表对特定训练样本的学习精度，而学习能力代表无错误的识别任意样本的能力。支持向量机算法的目的在于寻找一个超平面 H，该超平面可以将训练集中的数据分开，且与类别边界的沿垂直于该超平面方向的距离最大，故SVM 法也被称为最大边缘算法。样本集中的大部分样本不是支持向量，移去或者减少这些样本对分类结果没有影响，这样只用各类别边界样本的类别来决定分类结果的做法，具有较强的适应能力和较高的准确率。总结起来，SVM 算法的分类思想是从训练样本中寻找能够确定一个最优超平面
20、的支持向量。假设有大小为 m 的训练样本集，如果它是一个二分类任务，则分类标识为，那么任务的决策函数可用下式表示：如此，支持向量机就需要解决由下式表示的优化问题：另外，上式需要满足如下限制：,此处训练向量通过函数被映射到高维空间中，然后支持向量机将在这个高维空间中寻找一个带有最大间隔的线性可分超平面。可以使用拉格朗日优化方法将最优分类面问题转化为一个对偶最优化问题。在计算过程中可以通过引入核函数进行降维，核函数可以是线性函数、多项式函数、径向基函数、多层感知函数等，从而在计算时只需要计算这些核函数，而不用21021064 程伟去直接计算复杂的高维空间中的非线性函数，这样就可以有效的避免了特征空
21、间维数灾难问题。由于支持向量机坚实的理论基础和它在很多领域表现出良好的推广性能，国际上支持向量机方法的研究很多。研究者们相继开发出了很多 SVM 快速训练算法，其中最典型的是John Plat 提出的 SMO(Sequential Minimal Optimization)算法，使得 SVM 在文本分类领域取得了很大的成功。SMO 方法是一种简单的算法，它能快速求解 SVM 的二次规划问题，从而提高训练 SVM 的速度。按照 Osuna 的理论，在保证收敛的情况下，把 SVM 的二次规划问题分解成一系列子问题来解决，其他算法相比，SMO 方法的优点在于，优化问题只有两个拉格朗日乘子，它用分析的
22、方法即可解出，从而完全避免了复杂的数值解法。另外，它不需要巨大的矩阵存储，即使是很大的 SVM 学习问题，也可在 PC 机上实现。目前关于 SVM的研究成果很多，在传统的 SVM 的基础上，学者们还提出了多类支持向量机和模糊支持向量机(FSVM)。总之，SVM 是一类重要的学习分类算法，在文本分类中有重要的应用。基于 SVM 的文本分类法适合大样本集的文本分类，而且由于SVM 算法不受样本趋于无穷大理论的限制，它对小样本的自动分类同样有着较高的精度。SVM 分类器的文本分类效果很好，具有其他机器学习技术难以比拟的优越性。SVM 的主要缺点就在于难以针对具体问题选择合适的函数，另外 SVM 训练
23、速度受到训练集规模的较大影响，计算开销较大。4 发展趋势发展趋势本文所阐述的文本分类法都是与单一的机器学习算法相结合的方法，在实际应用中，由于应用的复杂性和数据的多样性通常使单一的分类方法不够有效，因此未来基于机器学习的文本分类法必然要向多种分类器融合的方法发展。目前学者们在多种分类方法的融合方面也已经进行了广泛的研究，同时也取得了一系列的研究成果，如贝叶斯方法和遗传编程的结合。另外，文本分类方法会更加注重潜在语义索引方法，通过将机器学习方法和潜在语义分类模型相结合产生新的分类器。目前潜在语义已被证明是对传统的向量空间技术的一种改良，可以消除词之间的相关性，从而化简文档向量。5 总结总结随着全
24、球信息化和网络化的迅速发展，文本分类已成为多个领域研究者的热门研究课题，它吸引着越来越多的研究者的关注。本文详细阐述了文本分类的定义、文本表示、特征提取等，并重点介绍了基于朴素贝叶斯算法、决策树、KNN、中心向量以及 SVM 算法的文本分类方法，指出了它们的优缺点，最后指出了基于机器学习算法的文本分类方法可能的发展趋势。即使文本分类方法目前还存在着不少问题，但文本分类技术有着广泛的应用。随着人工智能、机器学习、数据挖掘等领域的发展，分类方法将向着更高级、更综合化和更多样化的方向发展。参考文献参考文献1 Sebastiani F.Machine learning in automated tex
25、t categorization.Journal of ACM ComputingSurveys,2002,34(1):1-4721021064 程伟2 Joachims T.Text categorization with support vector machines:learning with many relevantfeatures.In Proceedings of the 10th European Conference on Machine Learning,Berlin,Germany,1998:137-1423 孙晋文,肖建国基于 SVM 的中文文本分类反馈学习技术的研究J
26、.控制与决策,2004,19(8)：927-9304 Kim H，Howland P,Park H.Dimension reduction in text classification with support vectormachines.Journal of Machine Learning Research,2005,6:37-53.5 Yang Y.An evaluation of statistical approaches to text categorization.Journal of InformationRetrieval,1999,1:69-906 Apte C,Dame
27、rau F,Weiss S.Text mining with decision rules and decision trees.InProceedings of the Conference on Automated Learning and Discovery,Pittsburgh,USA,1998:62-687 Robertson S E,Harding P.Probabilistic automatic indexing by learning from human indexers.Journal of Documentation,1984,40(4):264-2708 杨挚诚.基于机器学习的文本分类算法研究D.广西大学计算机应用专业硕士学位论文，20079 边肇祺,张学工.模式识别(第 2 版)M.北京:清华大学出版社,2000:296-30510 Joachims T.A probabilistic analysis of the Rocchio algorithm with TFIDF for textcategorization.International Conference on Machine Learning,1997:143-152
