文本分类算法

文本分类大致有两种方法：一种是基于训练集的文本分类方法；另一种是基于分类词表的文本分类方法。两种方法出自不同角度的研究者，训练集法更多的来自计算机或人工智能研究领域，而分类表法则更多地来自突出情报领域。本文主要介绍前一种。

基于训练集的文本分类是一种典型的有教师的机器学习问题，一般分为训练和分类两个阶段，具体过程如下：

训练阶段：

1）定义类别集合 ，这些类别可是是层次式的，也可以是并列式的。

2）给出训练文档集合 ，每个训练文档 被标上所属的类别标识 。

3）统计 中所有文档的特征矢量 ，确定代表 中每个类别的特征矢量 。

分类阶段：

1）对于测试文档集合 中的每个待分类文档，计算其特征矢量 与每个 之间的相似度 。

2）选取相似度最大的一个类别 作为的类别。

有时也可以为 指定多个类别，只要与这些类别之间的相似度超过某个预定的阈值。如果与所有类别的相似度均低于阈值，那么通常将文档放在一边，有用户来做最终决定。如果这种情况经常发生，则说明需要修改预定义的类别，然后重新进行上述训练与分类工程。

从训练集中得出分类模式的方法很多，有基于文本特征向量相关性的方法、基于神经网络技术的方法、基于遗传算法的方法、基于关联的方法、基于EM算法的方法等。

§3.1朴素贝叶斯算法

朴素贝叶斯（NaiveBayes）算法的基本思路是计算文本属于类别的概率，文本属于类别的概率等于文本中每个词属于类别的概率的综合表达式。具体算法步骤如下：

1) 计算特征词属于每个类别的概率向量（ ）。

其中， =

2）对于新文本 ，按下面的公式计算该文本属于类的概率：

其中， ， 为相似含义， 为类别总数， 为 为特征词总数。

3）比较新文本属于所有类的概率，将文本分到概率最大的那个类别中。

§3.2向量空间距离测度分类算法

该算法的思路十分简单，根据算术平均为每类文本集生成一个代表该类的中心向量，然后在新文本来到时，确定新文本向量，计算该向量与每类中心向量间的距离（相似度），最后判定文本属于与文本距离最近的类，具体步骤如下：

训练阶段：

1）首先定义类别集合这些类别可以是层次式的，也可以是并列式的；

2）然后给出训练文本集合，每个训练文本都被标上所属的类别标识 ；

3）提取训练文本集合S中所有文本的特征矢量，并采用一定的原测来确定代表C中每个类别的特征矢量 ；

分类阶段：

1）对于测试文本集合 中的每一个待分类文本，计算其特征矢量 与每一个 之间的相似度 ，可以用前面所提到的余弦法。

2）选取相似度最大的一个类别 作为的类别。

§3.3K最邻近分类算法

该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的K篇文本，根据这K篇文本所属的类别判断新文本所属的类别，具体算法步骤如下：

1）根据特征项集合重新描述训练文本向量；

2）将新文本表示为特征向量；

3）在训练文本集中选出与新文本最相似的K个文本，计算方法仍为余弦法：

来源：(http://blog.sina.com.cn/s/blog_5ae7a1de0100g8at.html)- 文本分类算法_scarlett_新浪博客

其中，K值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据试验测试的结果调整K值，一般初始值定为几百到数千之间。

4）在新文本的K个邻居中，依次计算每类的权重，计算公式为

其中， 函数，即，如果 属于类，那么函数值为1，否则为0。

5）比较类的权重，将文本分到权重最大的那个类别中。

§3.4支持向量机

支持向量机（Support VectorMachine，SVM）最初是由Vapnik提出的，是一种相对较新的机器学习方法。支持向量机的基本实现思想是：通过某种事先选择的非线性影射把输入向量x映射到一个高维特征空间Z,在这个空间中构造最优分类超平面。也就是SVM采用输入向量的非线性变换，在特征空间中，在现行决策规则集合上按照正规超平面权值的模构造一个结构，然后选择结构中最好的元素和这个元素中最好的函数，以达到最小化错误率的目标，实现了结构风险最小化原则。具体算法细节将在下一章作详细介绍。

§3.5神经网络算法

它是采用感知算法进行分类，在此种模型中，分类知识被隐式地存储在连接

的权值上，使用迭代算法来确定权值向量，当网络输出判别正确时。权值向量保

持不变，否则进行增加或降低的调整，因此也称奖惩法。一般在神经网络分类法中包括两个部分训练部分和测试部分，以样本的特征项构造输入神经元，特征的数量即为输入神经元的数量，至于隐含层数量和该层神经元的数目要视实际而定。在训练部分通过对相当数量的训练样本的训练得到训练样本输入与输出之间的关系即在不断的迭代调整过程中得到连接权值矩阵。测试部分则是针对用户输入的待测样本的特征得到输出值即该样本的所属的类。

§3.6决策树分类算法

决策树是被广泛使用的归纳学习方法之一。决策树是用样本的属性作为根节点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进行分析和归纳产生的。决策树的根节点是所有样本中信息量最大的属性。树的中间节点是以该节点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶节点是样本的类别值。决策树用于对新样本的分类，即通过决策树对新样本属性值的测试，从树的根节点开始，按照样本属性的取值，逐渐沿着决策树向下，直到树的叶节点，该叶节点表示的类别就是新样本的类别。决策树方法是数据挖掘中非常有效的分类方法，它排除噪音的强壮性以及学习反义表达的能力使其更适合于文本分类[31]。比较著名的决策树算法是ID3算法以及它的后继C4.5、C5等。基本的ID3算法是通过自顶向下构造决策树的。其主算法步骤如下：

1）从训练集中随机选择一个既含正例又含反例的子集（称为“窗口”）；

2）用“建树算法”对当前窗口形成一棵决策树；

3）对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；

4）若存在错判的例子，把它们插入窗口，重复步骤2），否则结束。

建树算法：

1）对当前例子集合，计算各特征的互信息；

2）选择互信息最大的特征 ；

3）把在 处取值相同的例子归于同一子集，取几个值就得到几个子集；

4）对既含正例又含反例的子集，递归调用建树算法；

若子集仅含正例或反例，对应分支标上的P或N，返回调用处。

§3.7其它的分类算法

许多研究者研究了将多种分类方法联合成一种分类器的技术，这个过程称为Voting，联合分类基本思想是将一组分类器结合起来，以表决的形式进行模式分类。选举算法可以分为2个类型：Bagging(Bootstrapaggregation)算法和Boosting算法。

Bagging算法：

训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。

对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别。

Boosting算法：

类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率.

§3.8 小结

本章主要介绍了当前文本分类领域常用的几种文本分类算法及其原理，包括贝叶斯算法、向量距离测度算法、决策树算法、KNN算法、支持向量机、神经网络等。其中KNN算法、决策树算法中的ID3算法和支持向量机会在第四章的中文文本分类的实验中得到应用。