中文搜索引擎之文本分类

中文搜索引擎之文本分类  2007/06/04 

作者：Kelvin from Hour41 (www.hour41.com )

文本分类就是根据预先定义的主题类别，按照一定的规则将文档集合中未知类别的文本自动确定一个类别，涉及数据挖掘、计算语义学、信息学、人工智能等个学科，是自然语言处理的一个重要应用领域。 目前，越来越多的统计分类方法、机器学习方法、数据挖掘技术和其它的新技术被应用到文本自动分类领域中，如：回归模型、最近邻分类器、规则学习算法、相关反馈技术、专家投票分类法、人工神经网络等。 这些方法都能对一个预先分好类的文本集进行学习，获取每个类别的特征，自动生成分类规则，建立一个文本分类器。

1. 文本分类的一般过程

一个完整的文本分类过程主要包括以下几部分：首先是预处理，根据采用的分类模型将文档集表示成易于计算机处理的形式；其次是项权重的计算，根据适宜的权重计算方法表示文档中各项的重要性；再次是根据预处理的训练集（已预知类别的文档）学习建模，构建出分类器；最后利用测试集文档按一定的测试方法测试建立好的分类器的性能，并不断反馈、学习提高该分类器性能，直至达到预定的目标。

2. 文本的预处理

由于通常文本都是非结构化的，计算机很难直接对其进行处理，因而在分类之前要对文本做一定的预处理，将非结构化的文档转换为适合于学习算法以及分类任务的表示形式。一般采用的方法是词袋表示法，该方法把文本看成是若干个词构成的集合，其中每个词称为一项特征，根据文本的长度、其出现的频率不同，词的重要性也有所不同，在向量空间模型中这种重要性被称为权重；权重的计算主要依据下面两个方面：
1）一个项在某文档中出现的次数越多，它和该文档的主题就越相关。
2）一个项在选取的文档集中出现的次数越多，它刻画某个特定文档特征的能力就越弱。
常用的权重计算方法有：布尔加权法、词频加权法、tf × idf 和熵加权法。

3. 降维技术

文本分类的一个核心难题就是特征空间的高维性，一个文档集中的特征项动辄就是上万维，这么高的维数特征不仅带来极高的计算复杂度，产生维度灾难，也给分类过程带来了大量的噪音，且容易产生过度拟合的问题，因而有必要简化原始的特征集，这种简化技术就是降维技术。 降维技术主要分成两大类：特征选择和特征提取。

特征选择又称独立评估法，其目的是滤除携带信息量较少的词，只保留对分类贡献较大的词。 在特征选择时一般都是利用某种评价函数，独立地对每个原始特征项进行评分，然后按分值的高低将它们排序，从中选取若干个分值最高的特征项，以达到减少总特征数的目的。 因此，评价函数的好坏是影响特征选择的关键问题。特征选择一般有：文档频率、信息增益、期望交叉熵、互信息、文本证据权、奇率、x2 统计量等。

特征提取又称综合评估法，它是将原有的特征集T 加以联系和转化以构建新特征集T'的过程，一般| T' |《| T | ，因而可达到降维的效果；特征提取的思想是：由于一词多义、多词一义的现象大量存在于文本信息中，导致文本的原始项可能不是文档内容表示的最佳维度。特征提取就是试图通过重构新项来避免上述问题。 一般有项聚类、潜在语义索引（LSI）、多维尺度变换、自组织特征映射等。

4. 传统文本分类模型

A、k 近邻分类模型
k 近邻分类模型，是最著名的模式识别统计学方法之一，它在很早就被用于文本分类研究，而且是取得最好结果的文本分类算法之一。

kNN 分类模型的原理如下：给定一个待分类的测试文档，考察和待分类文本最相似的k 篇文本，根据这k 篇文本的类别来判断待分类文本的类别值。k 近邻法没有离线训练阶段，所有的计算都是在线进行的。 因此这种方法的实时性不好，计算的时间复杂性是O（ L*N），其中L 是待分类文本向量中非0 的分量个数，而N 是训练集的文本数量。

B、朴素贝叶斯模型
朴素贝叶斯分类算法是一种最常用的有指导意义的方法，它以贝叶斯理论为基础，是一种在已知先验概率与条件概率的情况下的模式识别方法。 朴素贝叶斯分类算法基于独立性假设，即一个属性对给定类的影响独立于其它属性。

C、支持向量机
支持向量机（Support Vector Machines：SVM）理论，用于解决二分类模式识别问题。 它基于结构风险最小化原则，在向量空间中找到一个决策面（decision surface），这个面能“最好”地分割两个分类中的数据点。

目前，比较有效的SVM 实现方法包括Joachims 的SVMlight系统和Platt 的序列最小优化算法。

5. 文本分类的一些新模型

A、 基于RBF 网络的文本分类模型
基于RBF 网络的文本分类模型把监督方法和非监督方法相结合，通过两层映射关系对文本进行分类，首先利用非监督聚类方法根据文本本身的相似性聚出若干个簇，使得每个簇内部的相似性尽可能高而簇之间的相似性尽可能低，并由此产生第一层映射关系，即文本到簇的映射，然后通过监督学习方法构造出第二层映射关系，即簇集到目标类集合的映射。然后为每一个簇定义一个相应的径向基函数（Radial Ba-sis Function，RBF），并确定这些基函数的中心和宽度，利用这些径向基函数的线形组合来拟合训练文本，利用矩阵运算得到线性组合中的权值，在计算权值时，为了避免产生过度拟合的现象，采用了岭回归技术，即在代价函数中加入包含适当正规化参数的权值惩罚项，从而保证网络输出函数具有一定的平滑度。

B、基于模糊- 粗糙集的文本分类模型
文本分类过程中由于同义词、多义词、近义词的存在导致许多类并不能完全划分开来，造成类之间的边界模糊。此外交叉学科的发展，使得类之间出现重叠，于是造成许多文本信息并非绝对属于某个类。这两种情况均会导致分类有偏差。利用粗糙- 模糊集理论结合kNN 方法来处理在文本分类问题中出现的这些偏差。 模糊- 粗糙集理论有机的结合了模糊集理论与粗糙集理论在处理不确定信息方面的能力。 粗糙集理论体现了由于属性不足引起集合中对象间的不可区分性，即由于知识的粒度而导致的粗糙性；而模糊集理论则对集合中子类边界的不清晰定义进行了模型化，反映了由于类别之间的重叠体现出的隶属边界的模糊性。它们处理的是两种不同类别的模糊和不确定性。 将两者结合起来的模糊- 粗糙集理论能更好地处理不完全知识。

C、潜在语义分类模型
在语义分类模型（Latent Semantic Classification：LSC），与LSI 模型类似，从原始文档空间中得到一个语义空间；然而不同的是，通过第二类潜在变量的加入，把训练集文档的类别信息引入到了语义空间中。 也就是在尽量保留训练集文档的词信息的同时，通过对词信息和类别信息联合建模，把词和类别之间的关联考虑进来。 这样，就可以得到比LSI 模型的语义空间更适合文本分类的语义空间。

D、基于核方法的潜在语义文本分类模型
基于核方法学习最初以SVM 的形式出现，用于解决分类中遇到的一些问题。 后来，Joachims T。 把SVM运用到文本分类中取得了非常好的性能。 在信息检索领域，文本的向量空间等表示形式为构造Mercer核提供了一个理想的特征映射。受核方法的启示，为了提高分类性能，通过引入核函数给出了一种非线性的潜在语义文本分类模型，即基于核方法的潜在语义文本分类模型。

E、基于潜在语义的多类文本分类
基于扩展的潜在语义多类分类算法，在考虑文档特征信息的同时，又考虑文档的多类别信息，这实际上是过滤掉对分类贡献不大的词，而只保留那些对于分类贡献大的词。 这些词虽然在整个文档集中不是重要的词，但是对于分类却是重要的。 这样，既能较好的解决文档中同义词和多义词的问题，又能解决多类属分类问题。

F、基于投影寻踪回归的文本模型
基于投影寻踪回归的文本分类模型的思想是：将文本表示为向量形式，然后将此高维数据投影到低维子空间上，并寻找出最能反映原高维数据的结构和特征的投影方向，然后将文本投影到这些方向，并用岭函数进行拟合，通过反复选取最优投影方向，增加岭函数有限项个数的方法使高维数据降低维数，最后采用普通的文本分类算法进行分类。

6. 概述

目前文本分类在许多场合中都扮演着非常重要的角色，如文本索引、文本过滤、自动产生文档元数据、单词语义消歧、web 资源的按层次分类组织，此外，所有需要进行文档自动整理、自动选择和发送文档的应用系统也都需要文本分类技术。