中包含该特征项的文档数目越多，则该特征权重越小。
对tfidf(tk,dj)的规范化处理如下式所示：
wkj?tfidf(tk,dj)?2(tfidf(t,d))iji?1T (3-10)
其中，|T|表示特征向量的维数。
第四章 文本分类算法
4.1引言
文本分类算法作为自动文本分类技术的核心，一直处于重点研究与不断发展当中。多年来的研究积累了很多经典的分类算法，如Naive Bayes[32,33]、k近邻[30]、决策树[34]等，也涌现出了不少新算法和改进的分类算法[35-45]。这些研究基本都致力于改进训练和分类的速度和精度。
目前文本分类的算法有很多种，包括k近邻法、朴素贝叶斯算法、决策树算法、决策规则算法、回归模型、在线算法、Rocchio算法、神经网络算法、支持向量机算法、最小二乘拟合与分类器组方法等。文本分类算法基本来源于机器学习与信息论领域，总体来说分类算法大致可分为两大类：基于统计的方法和基于规则的方法。朴素贝叶斯算法是经典的基于统计的算法，决策树则是基于规则的方法中的典型。
为分类系统选择分类算法时需要考虑以下几个方面的问题：第一，分类算法本质上是两类算法还是多类算法，例如支持向量机是两类分类算法，而k近邻则可以用于多类分类，如果使用两类算法进行多类分类，则需要首先把多类分类任务分解为若干个两类分类任务后，再进行训练；第二，分类算法使用的是局部特征还是全局特征，所谓局部特征是指训练与分类时每个类别分别采用不同的特征空间，全局特征是指训练与分类时所有类别采用相同的特征空间，大部分分类算法使用全局特征与局部特征均可，但有些算法如朴素贝叶斯只能采用全局特征；第三，训练与分类的时间复杂度，一个好的分类系统应该对文本能够快速准确地分类，训练时间较长通常可以忍受，但如果分类时间过长则往往让人难以接受，例如k近邻法在大规模文本分类问题中就存在时间灾难的问题。
虽然已经出现了一些性能不错的文本分类算法，但由于各个算法在不同应用中的表现差异较大，因此仍然有很多学者致力于更为高效的算法的研究。
4.2文本分类算法
目前的文本分类领域已经有了一些比较成熟的文本分类算法，下面我们介绍几个常用算法。
4.2.1朴素贝叶斯算法
朴素贝叶斯(Naive Bayes, NB)算法是机器学习领域中常用的一种基于概率的分类算法，非常简单有效。NB算法基于这样一个朴素的基本假设（称作贝叶斯假设）：假设文本中各个特征的出现是相互独立的 [125]。该算法的关键是计算文本dj属于类别ci的后验概率，根据贝叶斯公式(4-1)，把后验概率的计算转化为先验概率的计算，然后取后验概率最大的一个或几个类别作为文本最终类别。显然，NB法是个多类算法，并可直接应用于多标号分类问题中。
??P(dj|ci)?P(ci)?P(ci|dj)? (4-1) P(dj)??其中，P(ci|dj)表示文本dj属于类别ci的后验概率，P(dj)表示文本dj在训练集?中的概率，P(dj|ci)表示类别ci中dj的先验概率，P(ci)表示训练集中类别ci的先?验概率。由于如果dj确定，那么对所有类别P(dj)为常数，因此有
??argmaxP(ci|dj)?argmaxP(dj|ci)?P(ci) (4-2)
cici?接下来的问题就是如何估计P(dj|ci)和P(ci)。目前存在两种计算模型，多
变量贝努利模型(Multi-variate Bernoulli Model)与多项式模型(Multinomial Model)。假定训练集的特征空间为T?{t1,t2,...,t|T|}， tk表示第k个特征，|T|表示特征空间的维数，下面对这两种模型分别进行介绍。 1.多变量贝努利模型
多变量贝努利模型中，特征向量采用二进制权重，在文档中出现过的特征权重为1，未在文档中出现过的特征权重为0。该模型是贝叶斯网络中的传统方法，已被广泛应用于文本分类中[10,102,126]。在整个计算过程中，未考虑特征在文档中
?出现的次序。由于贝叶斯假设认为文档中各特征间是相互独立的，所以P(dj|ci)可由下式计算：
|T|?P(dj|ci)??P(tk|ci) (4-3)
k?1其中，P(tk|ci)表示类别ci中特征tk出现的概率。
计算P(tk|ci)时，把文档看作是一组独立的贝努利实验，每个特征对应一个贝努利实验，用DFki表示类别ci中包含特征项tk的文档数，|ci|表示类别ci中包含的所有文档数，那么P(tk|ci)的计算公式如下：
P(tk|ci)?1?DFki (4-4) |ci|类别ci的先验概率P(ci)采用最大似然估计法计算，公式如下：
P(ci)?|ci| |D| (4-5)
其中，|D|代表训练集D中的所有文档数。 2.多项式模型
与多变量贝努利模型采用二进制权重不同，多项式模型考虑了文档中特征出现的频率，在该模型中，文本的特征向量权重由特征tk在文本dj中的出现次数TFkj表示。和多变量贝努利模型一样，多项式模型也忽略了特征在文档中出现的
?次序。在该模型中，P(dj|ci)和P(tk|ci)的计算公式如下：
TF|T|???P(tk|ci)kjP(dj|ci)?P(|dj|)?|dj|!? (4-6)
TFkjk?11??TFkjP(tk|ci)?j?1|ci||T|???TFsjs?1j?1|T||ci| (4-7)
在式(4-7)中，分子表示类别ci中特征tk出现的次数，分母表示类别cj中所有特征出现的总次数，为避免出现零概率，对分子和分母进行了平滑处理。
Andrew McCallum等人对多变量贝努利模型和多项式模型进行了比较，认为多项式模型在文本分类中的性能要优于多变量贝努利模型[128]，其主要原因是多项式模型考虑了文档中特征出现的频率，因此包含了更多文档信息的缘故。
另外，所有的模型都是基于贝叶斯假设的，该假设虽然大大简化了贝叶斯分类器的计算，但是也导致了其分类质量不是很理想的状况。
4.2.2 k近邻法
k近邻法(k-Nearest Neighbor, kNN)[30,31]又称为基于实例(Example-based, Instance-bases)的算法，其基本思想相当直观：把未知文本d与训练集中的每篇文本进行比较，找出最邻近的k篇文本，用这k篇文本的类别来判断未知文本的类别。类别判断方法如下：对找到的k篇文本，为每个类别打分，然后排序，只
?有分值超过指定阈值的类别才判定为文本d的类别。每个类别的分值score(d,ci)的计算公式如下：
?score(d,ci)????sim(d,dj)y(dj,ci)?bi (4-8) ??dj?kNN??其中，d为待分类文本d的特征向量；dj为最近邻的k篇文本之一dj的特征向????量；sim(d,dj)为d与dj的相似度，相似度的计算见本文3.3.4的介绍，通常使用????余弦相似度；y(dj,ci)为文本dj在类别ci中的权重，通常dj属于ci时取1，dj不
属于ci时取0；bi为事先设定的阈值，可以在确认集(validation set)上通过训练得
?到。所有使得score(d,ci)?0的类别均判定为文本d的类别，因而kNN算法可以用于多类多标号文本分类问题。
kNN算法的一个关键问题是k值的选择，k值过大会包含较多错误类别的文本，k值过小又会使得边缘文本难以被正确判断。另外，kNN算法无须训练，但需要在分类时把待分类文本与训练集中所有文本进行比较，因此对于小规模文本分类问题，使用kNN不失为一个有效的办法，但对于大规模文本分类问题，kNN需要耗费大量的分类时间。该算法的分类效率非常低，但是在分类精度上，是效果最好的分类器之一，并且，性能也比较稳定[29]。
4.2.3 Rocchio法
Rocchio法来源于信息检索系统，后来最早由Hull在1994年应用于分类[74]，从那以后，Rocchio方法就在文本分类中广泛应用起来。Rocchio方法可能是文本分类领域唯一一个植根于信息检索领域而不是机器学习领域的分类器，该方法
?在训练阶段为每个类别ci建立一个代表向量ci?(w1i,w2i,...,w|T|i)，其中|T|表示训
??练集中的特征总数。在对文本d分类时计算d与ci的相似度，取相似度最大的一
个或几个类别作为文本d的类别。
?类别ci的代表向量ci的第k维值wki由公式(4-9)计算：
wki???dj?ciwkj|ci|???dj?ciwkjN?|ci| (4-9)
其中，β为训练样本中正例的控制参数，γ为训练样本中反例的控制参数，|ci|表示训练样本中正例的数目，N表示训练样本的文档总数，正例指属于类别ci的文本，反例指不属于类别ci的文本。β和γ是两个控制参数，可以通过提高β降低γ来削弱反例的影响。
?进行分类时，待分类文档d?(w1,w2,...,w|T|)与类别ci的距离度量公式为：
??sim(d,ci)??wwkk?1|T|2kk?1|T|ki?w?wk?1|T| (4-10)
2ki?当β＝1，γ＝0时，类别代表向量ci成为正例的质心。
Rocchio方法容易实现，分类速度快，尤其适合于大规模文本处理。但是，对于一个包含几个互不相交的簇的类别，例如，“运动”类包含“篮球”和“爬山”两个不相干的簇，该类别的质心则可能会落在所有簇的外面，如果使用Rocchio法分类将导致大部分正例被误分的情况发生。