文本分类算法研究和数据挖掘摘要：文本分类是文本数据挖掘领域的重要技术之一。

从分类算法对文本语义信息的利用程度这一角度出发，将文本分类划分为基于词形的算法和基于语义的算法两类，对每类算法进行了描述，并对当今文本数据的多样性及文本分类算法改进的可选方向进行了研究。

关键词：文本分类；机器学习；语义信息；数据挖掘0引言文本分类是指在带有类别标签的文本集合中，根据每个类别的文本子集合的共同特点，找出一个分类模型，以便在后续过程中将未标识文本映射到已有类别的过程。

文本分类是一种文本处理手段，能较好地解决大量文档信息归类的问题进而应用到很多场景中，如基于受控词典的文档自动索引、文档过滤、元数据的自动生成、词义辨别、资源层次分类等，同时，它也是很多信息管理任务的重要组成部分^[1]。

自动分类的研究可以追溯到上世纪50年代；上世纪80年代末之前，自动分类问题大多采用知识工程的方法，即利用专家规则来进行分类；上世纪90年代以后，统计方法和机器学习的方法被引入到文本自动分类中，取得了丰硕的成果并逐渐取代了知识工程方法。

文本分类的一般流程为文本预处理、特征抽取、构建分类器和分类结果评价。

目前，针对文本分类的算法主要集中在特征抽取和分类器构建这两个方面。

本文主要介绍文本分类中的几种常用算法。

对于分类算法的分类方式目前没有统一的结论^[12]，鉴于各分类算法对文本语义信息的利用程度不同，可以考虑将其分为基于词形的文本分类和基于语义的文本分类两大类别。

1基于词形的文本分类基于词形的方法倾向于将文本视为无意义无联系的字或词的集合，几乎没有利用文本的语义信息。

1.1贝叶斯分类贝叶斯分类算法以贝叶斯理论为基础，是一种利用先验概率与条件概率进行文本分类的算法，具有实现简单、准确率高、速度快的特点。

贝叶斯算法基于独立性假设，即一个属性对给定类的影响独立于其它属性的值。

独立性假设的约束过于强，在实际应用中经常是不成立的，因此在很多情况下其分类准确率并不能保证^[3]。

1.2决策树本文将决策树视为一种基于规则学习的算法，其目的是学习一系列分类规则，即属性与类别的关系。

在决策树算法中，分类规则可用从根节点到任一叶节点的路径表示，具有很强的可理解性和可用性。

该算法涉及两个核心问题：决策树的建立和决策树的剪枝。

常见决策树算法包括CART、ID3、C4.5、CHAID等。

其中影响最大的是ID3^[4]，该算法由Quinlan于1986年提出，算法的理论清晰、方法简单，但只对较小的数据集有效，且对噪声敏感，在测试属性选择时，它倾向于选择取值较多的属性。

C4.5算法是对ID3的改进，主要解决了ID3 算法选择偏向取值较多的属性问题。

1.3k最近邻k最近邻算法是一种基于实例的消极学习算法。

该算法的思想是：统计一个样本在特征空间中的k个最相似的样本类别，进而采用加权投票的方式确定待分类样本的类别。

KNN分类器只存储实例，对于每个未知输入都要遍历训练样本，因而在应对大量待分类数据时其算法效率很低。

1.4Rocchio算法Rocchio算法是20世纪70年代左右在Salton的SMART系统中引入并广泛流传的一种分类算法，它通过构造类别的中心向量及相应类域的方式进行分类。

该方法的优点是简单且直观，缺点是对线性不可分的数据及含噪声的数据分类效果差。

1.5支持向量机支持向量机（Support Vector Machines，SVM）方法是由V.Vapnik 与其领导的贝尔实验室小组一起开发出来的一种机器学习技术。

SVM是一种线性分类器，采用结构风险最小化原则，其特点是能够同时最小化经验误差且最大化几何边缘区，最终将分类问题转化为求解最优决策超平面问题。

该方法属于研究小样本情况下机器学习规律的统计学习理论范畴，对小样本情况具有较好的适应性，克服了“过学习”现象，具有相对优良的性能指标。

影响SVM 的分类性能最重要的两个因素是误差惩罚参数和核函数。

1.6神经网络神经网络是对神经系统的一种模拟。

在文本分类中，神经网络由一组神经元组成，其输入单元通常代表词项，输出单元表示类别或类别兴趣度，神经元的连接权重表示条件依赖关系。

对于文本分类，文档向量权重通常作为输入。

其训练通常用BP算法来进行，时间开销一般很大。

最简单的用于文本分类的神经网络为感知器。

感知器实际上是一种线性分类器，它将分类问题转化为对错误分类的修正问题，通过对所有训练实例进行多次迭代和更新的方式来使错误分类的数量低于某一阈值，从而求得各个输入分量连接到感知机的权量。

最近，一种新兴的多层神经网络学习算法——深度学习引起了机器学习领域的广泛关注。

深度学习算法通过组合低层特征形成更加抽象的高层表示属性类别或特征，以发现数据的分布式特征表示。

目前，深度学习已经在计算机视觉、语音识别等领域获得一定程度的应用，但在自然语言处理方面尚未获得系统性突破。

1.7线性最小平方拟合线性最小平方拟合是一种线性模型的参数估计方法，它将分类问题转为拟合问题。

训练数据用输入/输出向量对表示，其中输入向量用传统向量空间模型表示的文档（词和权重），输出向量则是文档对应的分类（带有二元权重）。

通过求解这些向量对的线性最小平方拟合，可以得到一个单词分类的回归系数矩阵^[5]。

1.8Ngram方法Ngram是一种依赖于上下文环境的字（词）的概率分布的统计语言模型。

该方法将文本视为N元字（词）链的集合而非“词袋”，并由马尔可夫链模型来表征。

其特征选取方式为：将文本内容视为单词序列并进行大小为N的滑动窗口操作，形成新的长度为N的单词片断序列，每个N元单词片断即为一个特征。

由于中英文的不同，在设计基于N元语言模型的中文文本分类器时，首要问题是选择基于字级还是基于词级的N元语言模型，其次是选取合适的N值。

基于字级的Ngram算法对拼写错误的容错能力强且不需要词典和规则，但因其需要选择较大的N值，算法复杂度较高；而词的表达能力要强于字，所以基于词级的Ngram可以选取较小的N值，算法效率相对较高。

1.9多分类器组合多分类器组合是一种用来提高弱分类算法准确度的多算法集成框架，它将强分类器的获取问题转化为多个弱分类器的融合问题，其核心步骤是基分类器的生成与组合策略的选择。

多分类器组合的思想来源于Valiant在1984年提出的PAC （Probably Approximately Correct）模型。

PAC模型将识别准确率仅比随机猜测略高的算法称为弱学习算法，而识别准确率很高且能在多项式时间内完成的算法则被称为强学习算法。

同时，Valiant也提出了弱学习算法和强学习算法的等价性问题，即将弱学习算法提升为强学习算法。

1990年，Schapire构造出一种多项式算法，对该问题做了肯定的证明，这就是经典的Boosting算法^[6]。

但Boosting 算法需要事先知道弱学习算法识别准确率的下限，因而其在实际应用上存在一定困难。

针对这一问题，Freund和Schapire于1995年提出了AdaBoost（Adaptive Boosting）算法^[7]，该算法在实现过程中不需要任何关于弱学习算法的先验知识。

多分类器组合包含两个核心步骤：一个是基分类器的生成阶段，即如何生成多个不同的基分类器；另外一个是组合阶段，即如何使用基分类器来对测试实例进行分类，综合形成一个最终的分类结果。

2基于语义语法的文本分类基于语义语法的方法将文本视为有意义有联系的概念集合，利用知识工程方面的部分内容对特征向量做了不同程度的优化，从而相对充分地利用了文本的语义信息。

2.1基于概念的模型基于概念的模型假设文本是由意义相关的概念串联起来的。

与基于词形的方法不同，基于概念的模型研究是文档中概念的分布，其思想是利用知识库构造概念空间，进而从语义层面对文本进行分类。

常用的知识库有WordNet、Cyc、ConceptNet等，其中WordNet 的应用最广泛。

WordNet是美国Princeton大学研发的一个英语词汇语义知识库，或者概念知识库，它是语义学研究最权威的知识库之一。

WordNet中最基本的单位是概念，概念在WordNet里被抽象为一个同义词集合。

因此，WordNet不仅是一部词典，还是一个同义词词林。

本体是知识库的一种重要表现形式。

所谓本体，是指某一领域的概念化描述，包括概念及其关系，在应用中，本体是结构化的概念集^[8]。

基于词形的分类器其进化过程主要通过增量学习的方式，而基于本体的分类模型除了增量学习的方式外，还可以通过本体进化的方式实现分类器的进化。

文本分类中对知识库的应用主要集中在以下几个方面：①获取分类知识，分类问题中的类别体系是预先确定的，而知识库最基本的组织形式正是分类；②识别同义词，利用词义的等价表达可以简化文本向量空间，而同义词属于知识范畴；③语义消歧，在知识层面利用上下文信息确定多义词的准确概念。

2.2基于主题的模型在主题模型中，主题表示一个概念，其表现形式为一系列相关的单词构成的特征向量。

主题模型是从生成的角度看待文本的，即一篇文档通过一定概率选择某个主题，又在这个主题中以一定概率选择某个词语。

因此，文本词汇矩阵可以表示为文本主题矩阵与主题词汇矩阵的乘积。

主题模型主要分为PLSA（Probabilistic Latent Semantic Analysis）和LDA（Latent Dirichlet Allocation）两种。

2.3基于语法的模型基于主题的模型是以文档为单位的粗粒度的识别，而基于语法的模型则是以句子为单位的细粒度的识别。

它将文档看作一系列含有中心词的句子集合，通过词性标注来识别中心词，因而词性标注与中心词识别是该类算法的核心^[9]。

3结语分类算法的一般规律是利用训练集的数据特征，在假设空间中找出或者构建出一个模型或假设，使其计算结果尽可能地接近文档的真实分类。

所构建或学习的模型或假设可以用多种形式表示，如分类规则、决策树、数学公式或神经网络。

在文本分类器的实际应用中往往要面对各种各样的数据，比如小语种文本、短文本、海量文本、邮件、文献、html文档等。

这些数据或者特征提取难度大，或者对分类器效率要求高，或者存在语义信息之外的链接和结构信息。

因此，不存在一款通用分类器可以对各种数据都达到很好的分类效果。