文本分类方法总结

《文本分类方法总结》由会员分享，可在线阅读，更多相关《文本分类方法总结（43页珍藏版）》请在金锄头文库上搜索。

1、文本分类方法总结文本分类方法总结李荣陆(复旦大学计算机与信息技术系，上海，200433)E-mail: 一、一、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 项的词频，然后按词频对其由大 到小进行

2、排序，最后保留从第 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 分类器有：，其中。)()|()()()|

3、()|(jji ijji ijcPcdPdPcPcdPdcP rkjikjicwPcdP1)|()|(如果使用 Bayes 网络来描述特征属性间的联系，则失去了 Bayes 模型的简单性和线性 特征。我们使用了统计语言学中的 N-Gram 模型，它假设一个词在文档中某个位置出现的 概率仅与它之前的 n-1 个词有关，即：。)|()|(11121ininiiiiwwwwPwwwwPLL我们可以得到在某个类别 c 的文档集中，w1,w2,wT出现的概率为：。 TiiicTcwwwwPwwwP112121)|()(LL那么，Bayes 的分类决策函数就可以变为：。 )|()(maxarg)()|(m

4、axarg1121* Tiiicj Ccjji CcwwwwPcPcPcdPcjjL这样放松了 Bayes 模型中每个特征属性相互独立的假设，在计算一个文档在某个类别 中的概率时考虑了文本中一些特征属性间的相互联系。对于文档中的特征属性 wi，我们使 用 N-Gram 的方法进行生成，这样使特征属性生成的过程独立于领域、与时间和词典无关， 分类器对词法方面的噪声不敏感。直观地来说，概率的最大似然估计可以从语料中 N-gram 项的观)|(121iiwwwwPL察频率得到：)(#)(#)|(111 11 iniini iniiwwwwwwwPLLL其中，#(.)代表特定 N-Gram 项在训练语

5、料中的观察频率。但是，许多 n-gram 项在训练语 料中没有出现过，即数据稀疏问题，这时我们不能简单地将这些 n-gram 项对应的概率值置 为 0，需要使用一些平滑技术来估计这些概率以处理数据稀疏问题，常用的方法是使用 “回退”评估。 otherwisewwwPwwwwifwwwPwwwPiniiiniiniinii inii),|()(0)(#),|()|(1111111 11LLLL) L其中，)(#)(#)|(111 11 iniini iniiwwwwdiscountwwwPLLL)是一个折扣概率，是一个归一化因子，可以使用下式计算：)(11iniwwL)(12)(11111111

6、 )|(1)|(1)(xwwxinixwwxiniiniiniini wwxPwwxPwwLL L)L)L折扣概率可以通过不同的平滑方法来计算，如：线性平滑、绝对平)|(11iniiwwwPL)滑、Good-Turing 平滑和 Witten-Bell 平滑。 （1）绝对平滑（Absolute smoothing）)(#)(#)|(111 11 iniini iniiwwbwwwwwPLLL)其中，b 是一个常数，定义为，ni是训练集中发生了 i 次的事件数。211 2nnnb（2）线性平滑（Linear smoothing）)(#)(#)1 ()|(1111 11 iniini iniiww

7、ww ZnwwwPLLL)其中，Z 是训练集中所有唯一 n-gram 项的数目。 （3）Good-Turing 平滑（Good-Turing smoothing），其中，。)(#)|(11)(# 111iniww iniiwwGTwwwPini LL)Lrr rnnrGT1) 1(（4）Witten-Bell 平滑（Witten-Bell smoothing），WwwwwwwwPiniini inii )(#)(#)|(111 11LLL)其中，W 是能够跟在后的唯一的特征词，对于 n-gram 来说，对应于整个词11iniwwL表的大小。 （W is the number of distin

8、ct words that can follow in the training data. 11iniwwLIn the uni-gram model, this corresponds to the size of vocabulary.） （5）拉普拉斯平滑（Laplace smoothing），其中awwawwwwwPiniiini inii )(#)(#)|(111 11LLL)iiaa3，使用，使用 N-Gram 项作为中文文本分类特征项作为中文文本分类特征假设训练文档库 D 有 ND个文档，每个文档平均包含 Ns个句子，而句子的平均长度为 Ls，则这个训练文档库包含的 N-Gra

9、m 最多达 NDNsLs(Ls+1)/2。由此可见，文档中包含的 N- Gram 项非常丰富。这提醒我们，在用 N-Gram 项进行文档分类时，必须有所选择。从另一 方面来看，文档分类是面向语义的操作，因此，用于文档分类的文档属性应该能够尽可能 地表现文档的语义。显然，并不是所有出现在文档中的 N-Gram 项都对分类有用。一个 N- Gram 项对分类的有用性，或者说分辨能力，可以从三个方面来衡量：频度、分散度和集中度。下面分别给出它们的定义。 定义定义 1 1 在文档 d 中，N-Gram 项 t 的频度用它在 d 中出现的次数 tf 表示。 定义定义 2 2 在文档类 c 中，N-Gra

10、m 项 t 的分散度用 c 中包含 t 的文档数目 df 表示。df 越 大，则 t 在 c 中越分散；反之，越不分散。 定义定义 3 3 在文档集 D 中，N-Gram 项 t 的集中度用 D 中包含 t 的文档类数目 cf 表示。cf 越小，则 t 在 D 中的越集中；反之，越不集中。 直观地，对于 N-Gram 项 t，其在文档中的频度越高、在文档类里的分散度越大、在训 练文档集内的集中度越强，则它对分类越有用，即分辨度越强。不过，目前还没有找到很 好的数学方法来综合频度、分散度和集中度这三个因素，使得选出的文档属性能够获得最 优分类效果。为了减少提取不必要的 N-Gram 项，在提取

11、N-Gram 项时加如下两个约束条 件： 约束约束 1 1 对于预先给定的最小频度值 min-tf，在文档 d 中某一 N-Gram 项 t 被提取的先决 条件是它在 d 中的 tf min-tf。 约束约束 2 2 对于预先给定的最小分散度值 min-df，在文档类 c 中某一 N-Gram 项 t 被提取 的先决条件是它在 c 中的 df min-df。 在实验中，我们一般取 min-tf 和 min-df 为 2。 一种直接的 N-Gram 项提取方法是只扫描一遍文档，一次性将所有满足上述两个约束 条件的 N-Gram 项取出。由于只需扫描一遍文档，这种方法对于较小的训练文档库是有效 的

12、。但对于大训练库，则需要很大的内存空间。否则，就得在内存和外存之间不断交换中 间结果。这里采用一种分步提取的方法，其基本思想是：先提取符合约束条件的 1-Gram 项；从选择得到的 1-Gram 项构造候选 2-Gram 项，剔除其中不符合约束条件的候选项，得 到真正需要的 2-Gram 项。依此方法，提取其它 N-Gram（N=3,4,）项。 为了说明 N-Grams 提取算法，先给出一个定义和引理。 定义定义 4 4（子项） 若有 i-Gram 和 j-Gram（i j） ，且 j-Gram 包含在 i-Gram 中，则称 j- Gram 为 i-Gram 的子项，记为 j-Gram i-

13、Gram。 性质性质 1 1 若有 i-Gram 满足约束 1 和 2，则 i-Gram 的所有子项都满足约束 1 和约束 2。 性质 1 构成了分步提取 N-Gram 项的算法基础。算法算法 1 1：N-Gram 项生成算法14 输入：输入：文档库 D、min-tf、min-df 和 max-N(N 的最大值)。 输出：输出：满足约束条件 1 和 2 的 N-Gram 项的集合 S（N=1max-N） 。 1.求 1-Gram 项集合 S1：逐个扫描文档库 D 中的文档，提取所有 1-Gram 项，抛弃不满足 约束 1 和约束 2 的项，得到 1-Gram 项集合 S1； 2.求 2-Gra

14、m 项集合 S2：将 S1中的项两两组合，得到候选 2-Gram 项集合 C2。抛弃 C2中 不满足约束 1 和约束 2 的项，得到 2-Gram 项集合 S2； 3.求 i-Gram 项集合 Si(i=3max-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 项

15、集合 Si。 使用 N-Gram 项进行文本分类，最基本的要求是所选择的 N-Gram 项能够覆盖文档中 的词。因此，并非 N-Gram 项越多越好。这就涉及如何选择参数 N 的问题。根据对中文文 档中词的字数构成与分布的统计分析，发现中文文档中主要词条为字、字、字和 字词条，因此，用这些词条可以比较完整地表达文档语义。这样意味着在用 N-Gram 进行 文档分类时，只需取 1-Gram、2-Gram、3-Gram 和 4-Gram 项，即最大的 N 值取 4。参考文献：参考文献： 1W. Cavnar and J. Trenkle. N-Gram-Based Text Categorization. In Proceedings of SDAIR-94, 1994. 2Fuchun Peng and Dale Schuurmans. Combining Naive Bayes and N-Gram Language Models for Text Classification. Proceedings of The 25th European Conference on Information Retrieval Research (ECIR03). April 14-16, 2003, Pisa, Italy. （附