高性能文本分类算法研究

论文摘要

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

论文目录

• 摘要
• Research on High-Performance Text Categorization
• 第一章 引言
• 1.1 研究背景
• 1.2 研究意义
• 1.2.1 信息组织
• 1.2.2 信息过滤
• 1.2.3 邮件分类
• 1.2.4 话题跟踪
• 1.2.5 新信息检测
• 1.3 研究历史
• 1.4 研究现状
• 1.4.1 特征选择与压缩
• 1.4.2 分类器组合
• 1.4.3 小样本问题
• 1.4.4 层次文本分类
• 1.4.5 样本不均衡问题
• 1.5 研究内容
• 第二章 文本分类方法总结
• 2.1 文本的表示与计算
• 2.1.1 文本特征的表示
• 2.1.2 文本相似度计算模型
• 2.1.3 向量空间模型
• 2.2 文本分类算法总结
• 2.2.1 统计方法
• 2.2.2 规则方法
• 2.3 评价指标
• 2.3.1 召回率与精确率
• 2.3.2 BEP 与F-Measure
• 2.3.3 微平均与宏平均
• 2.4 文本分类语料库
• 2.4.1 Reuter
• 2.4.2 NewsGroup
• 2.4.3 IndustrySector
• 2.4.4 WebKB
• 2.4.5 TDT
• 2.4.6 OHSUMED
• 2.4.7 TanCorp
• 第三章 基于粗集理论的文本特征选择算法
• 3.1 粗集理论简介
• 3.2 基于粗集理论的特征选择算法
• 3.3 已有特征选择算法总结
• 3.3.1 文档频次
• 3.3.2 互信息
• 3.3.3 信息增益
• 3.3.4 CHI 统计量
• 3.3.5 交叉熵
• 3.3.6 优势率
• 3.3.7 词强度
• 3.4 实验测评
• 3.4.1 实验设计
• 3.4.2 比较与分析
• 3.5 本章小结
• 第四章 基于拉推策略的文本分类器修正算法
• 4.1 分类器偏差
• 4.2 相关研究
• 4.2.1 Bagging
• 4.2.2 Boosting
• 4.2.3 查询学习
• 4.2.4 纠错输出编码
• 4.2.5 Wu 的优化策略
• 4.3 拉推策略
• 4.3.1 基本原理
• 4.3.2 应用到中心分类器
• 4.3.3 应用到贝叶斯分类器
• 4.3.4 应用到最近邻分类器
• 4.3.5 与已有工作进行比较
• 4.4 实验测评
• 4.4.1 实验设计
• 4.4.2 比较与分析
• 4.5 本章小结
• 第五章 拉推策略的改进与推广
• 5.1 基于Margin 的拉推策略
• 5.1.1 拉推策略的不足
• 5.1.2 基于Margin 的拉推策略
• 5.1.3 实验测评
• 5.2 结合层次结构的拉推策略
• 5.2.1 层次分类的优势
• 5.2.2 把拉推策略引入到层次结构
• 5.2.3 实验测评
• 5.3 本章小结
• 第六章 概念索引的改进与推广
• 6.1 概念索引的改进
• 6.1.1 概念索引
• 6.1.2 概念索引的不足
• 6.1.3 修正的概念索引
• 6.1.4 实验测评
• 6.2 分类器索引
• 6.2.1 概念索引的推广
• 6.2.2 分类器索引
• 6.2.3 实验测评
• 6.3 本章小结
• 第七章 基于近似Margin 的分类器全局优化策略
• 7.1 Margin 思想的由来
• 7.1.1 统计学习理论
• 7.1.2 支持向量机
• 7.2 基于近似Margin 的全局优化函数
• 7.3 基于近似Margin 的全局优化算法
• 7.3.1 梯度修正公式
• 7.3.2 两个修正算法
• 7.4 实验测评
• 7.4.1 实验设计
• 7.4.2 比较与分析
• 7.5 本章小结
• 第八章 结束语
• 8.1 本文主要贡献与创新
• 8.2 下一步研究工作
• 参考文献
• 致谢
• 作者简历