英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
Comparison of Text Categorization Algorithms
摘要：本文总结了近年来常用的几种自动文本分类算法，分析比较了它们的优缺点。为在不同领域中使用适当的自动分类算法提供了线索。最后对这些算法的一些评价和总结进行了讨论，并指出了进一步的研究方向。
关键词：文本分类；朴素贝叶斯；KNN；SVM；神经网络
0 引言
对文本分类的研究可以追溯到M.E.Maron的工作。从那时起，该技术已经应用于信息检索，文档组织，文本过滤等等。1970年，Salton提出了VSM模型，由于其在统计方法学方面具有良好的基础，并且简洁地实现了文本特征的抽象描述，它已经成为文本分类处理的经典模型；直到80年代后期，在文本分类领域，以知识工程为基础的分类方法一直占据主导地位，其中最有名的系统是CONSTRUE，尽管该方法在分类方面取得了较好的效果，但在定制分类规则的构建上存在一些问题以及其落后的字符泛化，导致其难以大规模推广应用；90年代以来，随着互联网技术的飞速发展，对文本分类的研究进入了一个崭新的阶段，各种方法连续得到发展，包括机器学习技术，已经成为文本分类的主流形式，如贝叶斯分类，KNN，SVM，神经网络和Boosting等。其中一些算法已经在实际系统中得到实现和使用，并取得了很好的效果。本文第2节总结了几种常用的文本分类算法，并对不同算法的优缺点进行了比较分析。第三部分对这些算法进行评价和总结，指出了文本分类的发展方向。
1 常用文本分类算法的比较
常用的文本分类算法大致分为以下几类：与朴素贝叶斯相关的算法，与潜在语义指标相关的算法，KNN，支持向量机和神经网络。
1.1 与朴素贝叶斯相关的算法
最早的贝叶斯方法是在已知先验概率和类别条件概率下的一种模块分类，其基本思想是计算文本所属的概率。文本所属类别的概率等于文本中词汇术语的概率的组合表达式，具体算法如下：
①计算特征词属于对应类的概率向量（w1，w2，...，wn）；
②当新文本出现时，根据特征词用下列公式计算文本di属于Cj类的概率：
分母p(di)显然可以忽略，因为它对于给定的文本是固定的，而不影响P(Cj|di）。其中p(Wk|Cj)是无偏估计p(Wk|Cj)。
③比较文本所属的所有类的概率，并将文本分配给最大概率的类。
朴素贝叶斯快速，准确，能够反映出所有属性产生的对最终结论的影响，且算法的实现相对简单，只需扫描一次数据集，适合于在线模型的构建。另外它也是一种非常强大的算法，它具有较强的抗干扰能力，因此越来越多的专家给予关注。然而，朴素贝叶斯是一种基于两个假设的概率分类模型：①它要求给定类别中的所有属性都取独立的值，这意味着任何属性都不应该依赖于其他属性；②文本的长度与其类别无关。这些假设在实际应用中很少遇到，这是贝叶斯有时具有的低精度的主要原因。例如在Yang的比较实验中，该方法得到最差的分类。
在观察贝叶斯强假设时，产生了几种改进算法。Michael提出了一种组合属性的方法，它使用统计方法来评估属性在给定类别中的关联度，将高度相关的属性对结合到一个新的属性，并用新的属性替换朴素贝叶斯公式原本的值。但是该方法仍然没有完全解决属性关联关系大于二的问题，该方法只解决了部分高维相关问题。Christian Borgelt提出了一种模糊聚类与朴素贝叶斯相结合的方法，这种方法最大的优点是不需要假设属性是独立的，因为这种方法所使用的模糊分割矩阵是一个完整的协方差矩阵，所以它考虑了属性之间的依赖关系（在这一点上，在协方差矩阵中，并不是所有的非对角元素都是0，但如果它们是独立的，则所有非对角元素都是0）。Y.Shen根据文档不同部分的分类贡献提出了另一种分解方法，该方法将文档X划分为C个部分（例如，一个新闻可以分为标题和正文），那么每个部分的长度分别为N1，N2，hellip;，Nc，所以先验概率为：
其中，beta;c，c=1，2，hellip;，C是常量向量。
1.2 K-最近邻（KNN）及相关算法
KNN是一种基于实例的文本分类算法，它首先将一个测试文本特征转为向量，然后计算测试文本与训练集中每个样本文本之间角度的余弦值以得到相似度，取根据它们的相似性选择k最相近的训练文本，然后根据这些相似性为每个类别产生一个分数，分数值是训练集中文本的相似度的总和，并且属于同一范畴。然后将这些分数按顺序排序。测试文本属于最大分数的类别。然而，k的确定还没有得到很好的解决，所以通常先取一个初始值，然后根据实验结果调整k值，为了得到合理的分类，其初始值从几百到几千，所以一个阈值是必要的，如果测试文本的值超过阈值，测试文本可能属于几个类别。表达式为：
其中Sim（dx，di）在dx和di之间是相似的：
其中b是阈值，需要进行优化；knndoc是由k个训练集中相似度最相近的训练文本组成的训练子集；当训练文本di属于Cj类别时，g（di，Cj）取1，否则为0.通常可以通过另一个训练集来调整。
根据以上分析，KNN的本质是将特征权重作为特征空间中的坐标，首先计算坐标系中测试集与训练集之间的余弦距离，然后根据测试集之间的距离确定类别。显然，该距离没有考虑到特征属性相关性和共生因素等等的影响。在相似性方面，如果将这些因素考虑在内，KNN的效果会更好。针对上述问题，一些改进算法出现了并取得了一些成效。E.H. Han提出了一种WAKNN加权方法，对各个权重值进行测试，直到得到最有效的一个。WAKNN方法取得了一些效果，但计算也在很大程度上增加。L.H.Sun.也对KNN的弱点进行了改进，该方法主要考虑特征属性与相似效应的相关性和共现性，采用匹配系数来调整两个文档之间的距离，其本质是对相似性的一种加权，在特征选择和特征向量方面未作何改进。张晓辉提出了一种改进的算法，采用特征聚类算法，该算法利用CHI概率统计来计算特征对分类的贡献，对分类贡献相同的文本特征进行聚类。 将它们的共同分类贡献模式替换为单个词的一维维度。该算法扩大了稀有词的分类贡献和相关词的分类效果。
此外，对k类最相似文本的良好选择也对分类结果有较大影响。根据模式识别理论，类别样本之间的距离越大，类别内的距离越小，误判率越低。但在实际应用中，样本一般具有以下特点：①同一类别样本具有多峰分布，因此同一类别样本间的距离可能大于不同类别间的距离；②当样本分布不是非常紧凑时，那么很多样本将接近这些类别的边界，那么将出现很多错误分类的案例；③KNN算法只对最近的样本进行分类决策，这样算法在很多情况下会导致不准确。因此，KNN算法无法有效解决类别边界重叠的问题。刘冰等人提出了一种基于核心的KNN，它使用聚类方法得到每个类别的几个子集，让这些子集的中心作为类别的呈现点，并将这些点称为类别的核心。这些核可以表示样本内类别的多峰分布，可以根据样本到类别中心的余弦距离来处理边界样本的干扰，因此该方法可以更好地解决多峰分布和边界重叠的问题。
1.3 支持向量机及相关算法
SVM理论是1963年V.Vapnic提出的，它是一种非常有效的模式识别方法，它在解决小样本，非线性形状和高维模式识别问题方面展现出很多独特的优势，并在国际机器学习领域成为新的研究热点。1998年，T. Joachims首先将SVM引入到文本分类中。
SVM是一种基于统计学习理论的分类方法。 主要基于以下三点考虑：①通过最小化函数集的VC维来最小化结构风险，以控制机器学习的结构风险，从而使其具有更强的泛化能力；②通过最大化类之间的距离（找到可选的分类超平面）来实现对VC维度的控制，这可以通过统计学习理论的相关定理来保证；③SVM在技术上采用核心技术，根据泛函分析中的Mercer定理，通过将样本空间的乘积转化为变换空间，避免在非线性形状映射中寻找解，从而在内积空间中找到一个函数（称为核心函数）。
与传统的分类方法相比，SVM在避免过拟合，计算速度慢，结果粗略的情况下具有明显的优势。但是SVM还存在一些不足之处，主要表现在以下几个方面：
1）核函数的选择和构造。
SVM的超高性能主要取决于核函数，最近几种常用的核函数和函数的功能的参数的选取都是基于人为的经验，具有一定的自由度，因此存在局限性。 S. Amari提出了一种利用地理信息修改核函数的方法作为改进，即所谓的动态内核，但增加了计算时间且效率低下。李等人利用误差样本都接近边界表面的特性，将SVM与KNN结合起来，当样本与SVM可选超平面之间的距离大于给定阈值时使用VSM分类，否则使用KNN对测试样本进行分类，而在使用KNN时，通过这种方式将支持向量作为各类别的代表点，只增加了少量的计算量，但分类精确度得到提高，同时较好地解决了选择内核参数的问题。
2）多值分类器的构建
SVM实际上是一个二元分类器，但实际中很多问题是多值分类问题，所以SVM不能直接用于求解多类分类问题。如何利用VSM构造多值分类器，引起了研究者的广泛兴趣。
最近，多值分类器的VSM的构造主要有两种，一种是1998年由Weston提出的多值分类算法。该算法基于经典支持向量机理论，重构多分类模块，利用SV方法优化新模块的对象函数，实现了多值分类。但是，该算法选择了非常复杂的目标函数，难以实现，计算复杂度也很高。另一种算法是基于多个二值分类器进行组合来构造一个多值分类器，通常有两种构造：如1到1，或1到多个映射。代表性的算法有Vapnik的竞争淘汰算法和Eddy的多值分类算法。上述算法各有优缺点，但都没有摆脱最优超平面，对可视化说来说，多分类SVM相当于将数据空间划分为多个超平面，每种数据都被一个超平面围成一个区域。中国大陆的ZhuMei-liu提出了一种通过使用一种超球来划分类别数据的方法。这样一来，数据空间就由多个3维超球组成，看上去好像有许多泡泡一样。该算法在计算复杂度和数据规模上都具有优势。
3）速度和规模的问题
SVM方法无论在训练阶段还是测试阶段都有较好的性能，只有训练集的规模较小时，支持向量才大量增加，同时文本集规模较大，使得SVM分类的复杂度大大增加，分类速度也大大降低。因此，提高SVM分类速度和减少训练样本是亟待解决的问题。 C. Burges提出了降低集方法来提高SVM分类速度；G. Cauwenberghs使用增量学习来减少分类的计算。针对更多训练样本的问题，Liu Hong提出了一种组合SVM主动学习策略，在学习者查询标记样本的同时集成了更多的样本信息，它可以进一步减少所需的标记样本，达到相同的分类精度，这种方法已将其样本缩小到原来的1/10-1/15。
4）噪音问题
在SVM理论中，由于分类器的标准函数仅仅依赖于训练集中的一些支持向量，导致分类器对噪声数据比较敏感，在很多情况下会严重影响分类精度。因此，如何建立有效的支持噪声的SVM多值分类器已经成为SVM分类算法研究的重点之一。 Zhang建议将类别中心与边界的距离减至最小，通过取类别中心的平均噪声来降低噪声，从而提高分类精度。但是这种简单引入类别平均值的算法在处理复杂分布样本集方面仍然有一定的局限性。Xiao引入了主成分分析（PCA）算法，并采用非正交映射PCA分类算法对训练集进行预处理，并取得了较好的效果。
1.4 神经网络
将神经网络应用于分类的基本思想是将整套可行模式存储在网络内部。通过外部提示，这些模式可以被激发，利用这一特性，即使从“外部”提供的数据不够，该模式仍然可以从其内部重构。当提取一个文本的关键字并作为输入时，输出的是用户提供的评估值。 通过训练，网络可以实现从文本向量到评估值的映射，并将不同的特征向量映射到不同大小的不同评估值，通过不同的值来实现不同主题的分类。
在图1中，X =（x1，x2，...，xn）表示文本特征向量，可以通过设置过滤值进行分类。对于每个主题，都有一个阈值，k个阈值可以相等或不相等，如果某个文本的第j个评估值大于第j个阈值，那么文本适合第j个主题。有时，同一个文本可能适合两个或更多的主题。
图1 神经网络模型
最简单的神经网络分类器是一种感知，它是一个线性分类器。 Wiener开发出了另一种线性神经网络分类器，它利用了一种逻辑回归形式，并取得了较好的效果。将非线性神经网络分类器和线性的进行比较，分类结果差别不大。
神经网络最大的优点是具有很强的自学习功能和自适应能力，具有一定的宽容性和灵活性，使得它在人为干扰减少的情况下，实现系统自我修正和自我完善。但在实际应用中，上述介绍的神经网络分类模型很难得到较好的分类效果。其原因至少有以下两点：
全文共6520字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[10760]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
