高性能文本分类算法研究

因特网上的文本信息的爆炸式增长给文本分类的精度与速度提出了新的标准与挑战。这就要求文本分类在提高精度的同时,还要进一步提升训练与分类速度。为了面对时代的挑战,作者从特征选择与学习算法两个角度展开了深入的研究,取得了一系列突破性进展。 作者从基于分辨矩阵的粗糙集属性约简中受到启发,提出了一系列基于粗集理论的文本特征选择算法,即DB1、DB2、LDB。实验结果表明,DB2与LDB极为稳定,达到了与信息增益相当的精度;当特征数较少时,DB2与LDB的精度要明显高于信息增益。同时,在时间上也具有相当的优势,DB2与LDB的时间代价与文档频次、互信息、CHI统计大体相当,但明显低于信息增益。 “没有免费的午餐定理”表明:任何一种模式分类算法都不存在“与生俱来”的优越性。换句话说,所有分类器都存在一定程度上的“分类器偏差”。原因很简单,因为所有分类器都建立在某种假设(模型)之上。通常,这个偏差会导致训练集与测试集错误率增大。很自然地,作者就考虑采用训练集错分样本来在线修正分类器模型。这便是拉推策略的基本思想。作者将拉推策略应用到三个基本的分类器,即中心法、贝叶斯、最近邻,于是得到三个修正的分类器,即RCC、RNB、RKNN。其中RCC的性能最为卓越。实验结果表明算法RCC取得了逼近SVM的分类精度,但运行时间需求却与问题规模成线性关系,因此实际运行时间要远远低于SVM。 但是,拉推策略只是降低了经验误差,还没有有效地降低推广误差。作者的一个非常直接的想法就是,不但要求训练样本与正确类别的相似度大于所有与其它类别的相似度,而且要至少存在一个间隔,即近似Margin。算法的具体做法就是,不但对误分样本要修正相应类代表,而且对Margin较小的样本也要修正相应类代表。实验结果表明该算法既能降低训练集误差,又能在一定程度上降低推广误差。并且,分类质量要比拉推策略高出1个百分点。 考虑到层次化分类的实用性与有效性。作者将拉推策略推广到层次化分类。作者给出了两种将拉推策略推广到层次模型的方法。其一是选取整棵树进行拉推修正。其二是选取每个非叶子节点进行拉推修正。实验结果表明,层次拉推策略的分类质量与非层次拉推策略基本相当,但运行时间上具有明显的优越性。 概念索引采用类中心作为压缩空间的坐标。但是,简单地采用类中心来代表一个类别,往往受到类中样本分布情况的影响。因此,为了提高类中心的表达能力,作者借助于拉推策略来修正类中心。然后再把修正的类中心作为压缩空间的坐标。实验结果表明,修正的概念索引在精度上要明显优于普通的概念索引。同时,修正的概念索引在与SVM分类器的兼容性方面表现得更为出色。