支持向量机文本分类的关键问题研究

摘要

随着计算机网络、数据库、多媒体等技术的飞速发展和日益普及，因特网上的可用信息以惊人的速度增加，仅Google搜索引擎能索引到的网页就高达80亿张以上。因特网信息表现为文本、声频、图象和视频等，其中文本类信息占绝大多数。为了更好地处理这些数量庞大、结构不确定的文本类信息，人们迫切需要一些高效的文本检索、查询和过滤系统，而文本分类正是实现这些系统所需的一项关键技术。 文本分类是指一个把自然语言的文本按其内容归入一个或多个预先定义好的类别的过程。由于网上信息数量巨大而且存在形式多样，因此传统的由专家进行手工分类的方法已无法满足现阶段应用的需要。自动文本分类是在给定的分类体系下，由特定的算法根据文本的内容确定与之相关联的类别。自动文本分类是人工智能技术和信息获取技术相结合的研究领域，是进行基于文本内容的自动信息处理的核心技术。 支持向量机是在上世纪末发展起来的一种基于结构风险最小化准则的分类学习机模型。它通过构造并求解目标函数来获得两类样本数据之间的决策超平面，以保证最小的分类错误率。从实际分类效果来看，支持向量机在解决小样本、非线性及高维的模式识别问题时是目前己知的分类器中效果最好的，而这些问题恰是文本分类问题所面临的困难。因此，支持向量机和文本分类问题有着良好的结合点。 虽然支持向量机的训练算法本身就可以克服特征词向量维数过高的问题，但针对文本样本的特征提取步骤仍是不可或缺的，这是因为当大量特征词与分类无关时，只会使支持向量机“过分适应于”训练样本而降低推广性能。此外，传统的基于词频统计的特征提取方法也无法体现词与词之间的相互联系。针对这一问题，本文的第二章将潜在语义索引和粗糙集特征提取结合起来，提出了一种在潜在语义空间利用粗糙集进行特征提取的方法，试验结果表明采用新方法提取特征可以明显改善支持向量机的推广性能。 在分类问题广泛应用的允许训练误差的高斯核函数的支持向量机中，核参数σ2和折衷参数C对于支持向量机的分类性能有着至关重要的影响。模型选择，即如何选择恰当的训练参数，一直是支持向量机研究的一个重要课题。本文的第三章对这一问题进行了分析，并提出了判断参数选择恰当与否的简化评价指标，并在此基础上提出了一种两步骤的选择恰当参数的方法。第三章的试验表明，简化计算方法可以快速而准确地计算推广误差评价指标，参数选择算法可以搜索到最佳的训练参数。 传统支持向量机最大的困难在于当训练样本数量较大时，支持向量机的训练时间较长。这是因为采用分解法时，训练复杂度与样本数量的平方成正比。如何降低支持向量机的训练复杂度一直都是一个棘手的问题，本文的第四章根据预选取支持向量的思路对上述问题进行了分析，将粗糙集的概念引入了支持向量的预选分析过程中。第四章提出的新算法选取两类样本的上近似集的交集作为支持向量的候选集，并对两类样本上近似集交集的一致性进行了证明。试验表明，训练样本的上近似集的交集可以代替全部训练集进行训练，从而提高训练速度。 支持向量机的基本模型是针对两类样本集提出的，在处理多类样本集的分类问题时，目前效果最好的方法是训练一系列针对两类样本的子分类器。尽管这种方法可以获得令人满意的分类效果，但其训练时间比较长。我们认为，在多数情况下，并不是所有的子分类器都值得训练，部分子分类器是冗余的。本文的第五章对训练子分类器的必要性进行了分析，并提出一种采用主动学习策略的多类别支持向量机，新算法按子分类器的重要程度逐渐训练子分类器。实验证明，这一算法可以在几乎不降低分类性能的基础上，显著减少子分类器的个数。 直推式支持向量机是直推式学习理论和支持向量机的结合，它是目前分类效果最好的支持向量机。但它的分类效果极其依赖于事先指定的正样本数量Np的选择。当Np与实际情况相差较大时，直推式支持向量机的分类性能甚至还不如普通的支持向量机。本文的第六章着重讨论了直推式支持向量机对Np的值过分敏感的问题，提出了逐个判定准则来调整测试集松弛变量的类别标签，从而使Np的值在训练过程中可变。实验结果表明，改进后的方法使直推式支持向量机不再对事先指定的Np的选择敏感，能稳定地获得较好的分类效果。 网页是带有特定结构信息并说明链接关系的文本，与纯文本相比，网页的信息量更大、样本与样本之间的联系更紧密，但也比纯文本分类问题更加难以处理，要考虑更多因素。本文的第七章在分析了模糊直推式支持向量机在网页处理方面不足的基础上，从超链接分析的过程和利用网页重要性信息这两方面对其进行了改进。基于网页数据的试验表明，新算法有更强的适应性和更高的准确性。 综上所述，本文的主要创新包括如下几方面的内容： 1.根据文本分类领域的特征，改进了留一错误的评价指标和模型选择算法，显著提高了模型选择的效率； 2.提出了基于粗糙集的支持向量预选方法，缩短了训练的时间； 3.针对多类别分类问题，提出了采用主动学习策略的多类别支持向量机，可以在几乎不降低分类性能的条件下，减少子分类器的个数； 4.提出了更恰当的直推式支持向量机松弛变量标签调整准则，从而能稳定地获得较好的分类效果。 此外，本论文还在特征词的提取方法和网页分类等方面进行了研究和改进，使特征提取和网页分类的性能都有所提高。

目录

文摘

英文文摘

上海交通大学学位论文原创性声明及版权使用授权书

第一章绪论

第二章文本向量的特征提取

第三章选择支持向量机模型

第四章支持向量的预选取

第五章多类别分类问题

第六章改进的直推式支持向量机

第七章网页分类

第八章结束语

参考文献

攻读博士学位期间以第一作者发表的论文

致谢