文本分类方法总结

  • 格式:doc
  • 大小:9.58 MB
  • 文档页数:43

文本分类方法总结

李荣陆

(复旦大学计算机与信息技术系,上海,200433)

E-mail: lironglu@

一、Swap-1方法

1,特点:

 特征选择:将只在某一类中出现的词或短语作为这一类的特征,词频作为权重。

二、n-gram方法

1,N-Gram-Based Text Categorization

(1)特点:

 n-gram项的生成:为了得到字符串中结尾部分的字符串,对不够n的字符串追加空格。如:Text的3-gram项为_Te、Tex、ext、xt_、t__。

 类的表示:先计算类别中所有训练文本的n-gram项的词频,然后按词频对其由大到小进行排序,最后保留从第n(实验中等于300)项开始的k个n-gram项作为此类的特征值。

 相似度计算:

(2)优点:容错性强,可以允许文本中有拼写错误等噪声。

(3)用途:

 区分测试文档是何种语言,即语言分类;

 自动文本分类

2,CAN Bayes(Chain Augmented Naive Bayes)

Bayes分类器是一个性能很好的线性分类器,但是它假设文档的每个分类特征属性间是相互独立的,这显然是不成立的。假设di={wi1,wi2,…,win}为一任意文档,它属于文档类C={c1,

c2,…, ck}中的某一类cj。根据Bayes分类器有:

)()|()()()|()|(jjiijjiijcPcdPdPcPcdPdcP,其中rkjikjicwPcdP1)|()|(。

如果使用Bayes网络来描述特征属性间的联系,则失去了Bayes模型的简单性和线性特征。我们使用了统计语言学中的N-Gram模型,它假设一个词在文档中某个位置出现的概率仅与它之前的n-1个词有关,即:

)|()|(11121ininiiiiwwwwPwwwwP。

我们可以得到在某个类别c的文档集中,w1,w2,…,wT出现的概率为:

TiiicTcwwwwPwwwP112121)|()(。

那么,Bayes的分类决策函数就可以变为:

})|()({maxarg)}()|({maxarg1121*TiiicjCcjjiCcwwwwPcPcPcdPcjj。

这样放松了Bayes模型中每个特征属性相互独立的假设,在计算一个文档在某个类别中的概率时考虑了文本中一些特征属性间的相互联系。对于文档中的特征属性wi,我们使用N-Gram的方法进行生成,这样使特征属性生成的过程独立于领域、与时间和词典无关,分类器对词法方面的噪声不敏感。

直观地来说,概率)|(121iiwwwwP的最大似然估计可以从语料中N-gram项的观察频率得到:

)(#)(#)|(11111iniiniiniiwwwwwwwP

其中,#(.)代表特定N-Gram项在训练语料中的观察频率。但是,许多n-gram项在训练语料中没有出现过,即数据稀疏问题,这时我们不能简单地将这些n-gram项对应的概率值置为0,需要使用一些平滑技术来估计这些概率以处理数据稀疏问题,常用的方法是使用“回退”评估。

otherwisewwwPwwwwifwwwPwwwPiniiiniiniiniiinii),|()(0)(#),|()|(111111111

其中,

)(#)(#)|(11111iniiniiniiwwwwdiscountwwwP

是一个折扣概率,)(11iniww是一个归一化因子,可以使用下式计算: )(12)(11111111)|(1)|(1)(xwwxinixwwxiniiniiniiniwwxPwwxPww

折扣概率)|(11iniiwwwP可以通过不同的平滑方法来计算,如:线性平滑、绝对平滑、Good-Turing平滑和Witten-Bell平滑。

(1) 绝对平滑(Absolute smoothing)

)(#)(#)|(11111iniiniiniiwwbwwwwwP

其中,b是一个常数,定义为2112nnnb,ni是训练集中发生了i次的事件数。

(2) 线性平滑(Linear smoothing)

)(#)(#)1()|(111111iniiniiniiwwwwZnwwwP

其中,Z是训练集中所有唯一n-gram项的数目。

(3) Good-Turing平滑(Good-Turing smoothing)

)(#)|(11)(#111iniwwiniiwwGTwwwPini,其中,rrrnnrGT1)1(。

(4) Witten-Bell平滑(Witten-Bell smoothing)

WwwwwwwwPiniiniinii)(#)(#)|(11111,

其中,W是能够跟在11iniww后的唯一的特征词,对于n-gram来说,对应于整个词表的大小。(W is the number of distinct words that can follow 11iniww in the training data.

In the uni-gram model, this corresponds to the size of vocabulary.)

(5) 拉普拉斯平滑(Laplace smoothing)

awwawwwwwPiniiiniinii)(#)(#)|(11111,其中iiaa

3,使用N-Gram项作为中文文本分类特征

假设训练文档库D有ND个文档,每个文档平均包含Ns个句子,而句子的平均长度为Ls,则这个训练文档库包含的N-Gram最多达NDNsLs(Ls+1)/2。由此可见,文档中包含的N-Gram项非常丰富。这提醒我们,在用N-Gram项进行文档分类时,必须有所选择。从另一方面来看,文档分类是面向语义的操作,因此,用于文档分类的文档属性应该能够尽可能地表现文档的语义。显然,并不是所有出现在文档中的N-Gram项都对分类有用。一个N-Gram项对分类的有用性,或者说分辨能力,可以从三个方面来衡量:频度、分散度和集中度。下面分别给出它们的定义。

定义1 在文档d中,N-Gram项t的频度用它在d中出现的次数tf表示。

定义2 在文档类c中,N-Gram项t的分散度用c中包含t的文档数目df表示。df越大,则t在c中越分散;反之,越不分散。

定义3 在文档集D中,N-Gram项t的集中度用D中包含t的文档类数目cf表示。cf越小,则t在D中的越集中;反之,越不集中。

直观地,对于N-Gram项t,其在文档中的频度越高、在文档类里的分散度越大、在训练文档集内的集中度越强,则它对分类越有用,即分辨度越强。不过,目前还没有找到很好的数学方法来综合频度、分散度和集中度这三个因素,使得选出的文档属性能够获得最优分类效果。为了减少提取不必要的N-Gram项,在提取N-Gram项时加如下两个约束条件:

约束1 对于预先给定的最小频度值min-tf,在文档d中某一N-Gram项t被提取的先决条件是它在d中的tf min-tf。

约束2 对于预先给定的最小分散度值min-df,在文档类c中某一N-Gram项t被提取的先决条件是它在c中的df min-df。

在实验中,我们一般取min-tf和min-df为2。

一种直接的N-Gram项提取方法是只扫描一遍文档,一次性将所有满足上述两个约束条件的N-Gram项取出。由于只需扫描一遍文档,这种方法对于较小的训练文档库是有效的。但对于大训练库,则需要很大的内存空间。否则,就得在内存和外存之间不断交换中间结果。这里采用一种分步提取的方法,其基本思想是:先提取符合约束条件的1-Gram项;从选择得到的1-Gram项构造候选2-Gram项,剔除其中不符合约束条件的候选项,得到真正需要的2-Gram项。依此方法,提取其它N-Gram(N=3,4,…)项。

为了说明N-Grams提取算法,先给出一个定义和引理。

定义4(子项) 若有i-Gram和j-Gram(i  j),且j-Gram包含在i-Gram中,则称j-Gram为i-Gram的子项,记为j-Gram  i-Gram。

性质1 若有i-Gram满足约束1和2,则i-Gram的所有子项都满足约束1和约束2。

性质1构成了分步提取N-Gram项的算法基础。算法1:N-Gram项生成算法[14]

输入:文档库D、min-tf、min-df和max-N(N的最大值)。

输出:满足约束条件1和2的N-Gram项的集合S(N=1max-N)。

1. 求1-Gram项集合S1:逐个扫描文档库D中的文档,提取所有1-Gram项,抛弃不满足约束1和约束2的项,得到1-Gram项集合S1;

2. 求2-Gram项集合S2:将S1中的项两两组合,得到候选2-Gram项集合C2。抛弃C2中不满足约束1和约束2的项,得到2-Gram项集合S2;

3. 求i-Gram项集合Si(i=3max-M):

a) 由Si-1 (i=2-max-M)求候选i-Gram项集合Ci;

b) 对于Si-1中的任意两项tm、tn,tm (k)和tn (k) (k=1 (i-1))分别表示tm和tn中的第k个字。若tm (k+1)=tn(k)(k=1(i-2)),则Ci =Ci tm tn(i-1);

c) 抛弃Ci中不满足约束1和约束2的项,得到i-Gram项集合Si。

使用N-Gram项进行文本分类,最基本的要求是所选择的N-Gram项能够覆盖文档中的词。因此,并非N-Gram项越多越好。这就涉及如何选择参数N的问题。根据对中文文档中词的字数构成与分布的统计分析,发现中文文档中主要词条为1字、2字、3字和4字词条,因此,用这些词条可以比较完整地表达文档语义。这样意味着在用N-Gram进行文档分类时,只需取1-Gram、2-Gram、3-Gram和4-Gram项,即最大的N值取4。