文本分类综述 王 斌 中国科学院计算技术研究所 2002年12月

报告内容 文本分类的定义和应用 文本分类的方法 文本分类的评估指标 参考文献和资源

文本分类的定义和应用

定义 给定分类体系，将文本分到某个或者某几个类别中。 分类体系一般人工构造 分类系统可以是层次结构，如yahoo! 分类模式 政治、体育、军事 中美关系、恐怖事件 分类系统可以是层次结构，如yahoo! 分类模式 2类问题，属于或不属于(binary) 多类问题，多个类别(multi-class)，可拆分成2类问题 一个文本可以属于多类(multi-label) 这里讲的分类主要基于内容 很多分类体系: Reuters分类体系、中图分类

应用 垃圾邮件的判定(spam or not spam) 新闻出版按照栏目分类 词性标注 词义排歧 计算机论文的领域 类别 {spam, not-spam} 新闻出版按照栏目分类 类别 {政治,体育,军事,…} 词性标注 类别 {名词,动词,形容词,…} 词义排歧 类别 {词义1,词义2,…} 计算机论文的领域 类别 ACM system H: information systems H.3: information retrieval and storage

文本分类的方法

人工方法和自动方法 人工方法 自动的方法(学习) 结果容易理解 费时费力 难以保证一致性和准确性(40%左右的准确率) 专家有时候凭空想象 足球 and 联赛体育类 费时费力 难以保证一致性和准确性(40%左右的准确率) 专家有时候凭空想象 知识工程的方法建立专家系统(80年代末期) 自动的方法(学习) 结果可能不易理解 快速 准确率相对高(准确率可达60%或者更高) 来源于真实文本，可信度高

文本分类的过程 文本表示 训练过程 分类过程 训练文本 统计 统计量 特征表示 学习 分类器 新文本 문서特征表示 类别

特征抽取(feature extraction) 预处理 去掉html一些tag标记 禁用词(stop words)去除、词根还原(stemming) (中文)分词、词性标注、短语识别、… 词频统计 TFi,j: 特征i在文档j中出现次数，词频(Term Frequency) DFi:所有文档集合中出现特征i的文档数目，文档频率(Document Frequency) 数据清洗：去掉不合适的噪声文档或文档内垃圾数据 文本表示 向量空间模型 降维技术 特征选择(Feature Selection) 特征重构(Re-parameterisation，如LSI)

文本表示 向量空间模型(Vector Space Model) M个无序标引项ti (特征)，词根/词/短语/其他 每个文档dj可以用标引项向量来表示 (a1j,a2j,…,aMj) 权重计算，N个训练文档 AM*N= (aij) 相似度比较 Cosine计算 内积计算

Term的粒度 Character，字：中 Word，词：中国 Phrase，短语：中国人民银行 Concept，概念 同义词：开心 高兴 兴奋 相关词cluster，word cluster：葛非/顾俊 N-gram，N元组：中国 国人 人民 民银 银行 某种规律性模式：比如某个window中出现的固定模式 David Lewis等一致地认为：(英文分类中)使用优化合并后的 Words比较合适

权重计算方法 布尔权重(boolean weighting) TFIDF型权重 基于熵概念的权重(Entropy weighting) aij=1(TFij>0) or (TFij=0)0 TFIDF型权重 TF: aij=TFij TF*IDF: aij=TFij*log(N/DFi) TFC: 对上面进行归一化 LTC: 降低TF的作用 基于熵概念的权重(Entropy weighting) 称为term i的某种熵 如果term分布极度均匀：熵等于-1 只在一个文档中出现：熵等于0

特征选择(1) 基于DF Term的DF小于某个阈值去掉(太少，没有代表性) Term的DF大于某个阈值也去掉(太多，没有区分度) 信息增益(Information Gain, IG)：该term为整个分类所能提供的信息量(不考虑任何特征的熵和考虑该特征后的熵的差值)

特征选择(2) term的某种熵：该值越大，说明分布越均匀，越有可能出现在较多的类别中；该值越小，说明分布越倾斜，词可能出现在较少的类别中 相对熵(not 交叉熵)：也称为KL距离(Kullback-Leibler divergence) ，反映了文本类别的概率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。

特征选择(3) χ2 统计量(念xi)：度量两者(term和类别)独立性的缺乏程度， χ2 越大，独立性越小，相关性越大(若AD<BC,则类和词独立, N=A+B+C+D) 互信息(Mutual Information)：MI越大t和c共现程度越大 A B C D t ~t c ~c

特征选择(4) Robertson & Sparck Jones公式 其他 Odds: Term Strength:

特征选择方法的性能比较(1)

特征选择方法的性能比较(2)

特征选择方法的性能比较(3) YangYi-ming

特征重构 隐性语义索引(LSI) 奇异值分解(SVD)：A=(aij)=UΣVT 取Σ对角上的前k个元素，得Σk AM*N, UM*R, ΣR*R(对角阵), VN*R, R<=MIN(M,N) 取Σ对角上的前k个元素，得Σk Ak= UkΣkVkT, Uk由U的前k列组成，Vk由V的前k列组成 文档d在LSI对应的向量d’=dTUkΣ-1 在已有的LSI中增加新的word或者document，不需要重新计算 Folding-in 方法 SVD-updating方法

自动文本分类方法 Rocchio方法 Naïve Bayes kNN方法 决策树方法decision tree Decision Rule Classifier The Widrow-Hoff Classifier 神经网络方法Neural Networks 支持向量机SVM 基于投票的方法(voting method)

Rocchio方法 可以认为类中心向量法是它的特例 Rocchio公式 分类 类C中心向量的权重 训练样本中正例个数 文档向量的权重

Naïve Bayes Bayes公式 参数计算

kNN方法 一种Lazy Learning, Example-based Learning k=1, A类 k=4，B类 k=10，B类 新文本 k=1, A类 k=4，B类 k=10，B类 带权重计算，计算权重和最大的类。k常取3或者5。

决策树方法 构造决策树 CART C4.5 (由ID3发展而来) CHAID 决策树的剪枝(pruning)

Decision Rule Learning 学习到如下规则 wheat & form  WHEAT wheat & commodity  WHEAT bushels & export  WHEAT wheat & agriculture  WHEAT wheat & tonnes  WHEAT wheat & winter & ~soft  WHEAT (粗糙集)RoughSet 逻辑表达式(AQ11算法)

The Widrow-Hoff Classifier Online Learning 类c向量的第j个分量 xi的第j个分量 Learning Rate Target Value ( 0 or 1)

Neural Network c1 . c2 . …… . . . cn Backpropagation Input Layer Output Layer Hidden Layer

支持向量机 Support Vector Machine Optimal Separating Hyperplane

基于投票的方法 Bagging方法 Boosting方法 训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。 对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别 Boosting方法 类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率 AdaBoost AdaBoost MH

文本分类的评估指标

分类方法的评估 真正对的 错误 a b c d 邻接表 标YES 标NO 每个类 所有类： Precision=a/(a+b), Recall=a/(a+c), fallout=b/(b+d)=false alarm rate, accuracy=(a+d)/(a+b+c+d), error=(b+c)/(a+b+c+d)=1-accuracy, miss rate=1-recall F=(β2+1)p.r/(β2p+r) Break Even Point, BEP, p=r的点 如果多类排序输出，采用interpolated 11 point average precision 所有类： 宏平均:对每个类求值，然后平均 微平均:将所有文档一块儿计算，求值 真正对的 错误 标YES a b 标NO c d

其他分类方法 Regression based on Least Squares Fit (1991) Nearest Neighbor Classification (1992) * Bayesian Probabilistic Models (1992) * Symbolic Rule Induction (1994) Decision Tree (1994) * Neural Networks (1995) Rocchio approach (traditional IR, 1996) * Support Vector Machines (1997) Boosting or Bagging (1997)* Hierarchical Language Modeling (1998) First-Order-Logic Rule Induction (1999) Maximum Entropy (1999) Hidden Markov Models (1999) Error-Correcting Output Coding (1999) ...

参考文献

文献及其他资源 Papers Software: Corpus K. Aas and L. Eikvil. Text categorisation: A survey. Technical report, Norwegian Computing Center, June 1999 http://citeseer.nj.nec.com/aas99text.html Xiaomeng Su， “Text categorization”，Lesson Presentation Yiming Yang and Xin Liu. 1999. "A re-examination of text categorization methods." 22ndAnnual International SIGIR http://www.cs.cmu.edu/~yiming/publications.html A Survey on Text Categorization, NLP Lab, Korean U. 庞剑峰，基于向量空间模型的自反馈的文本分类系统的研究与实现，中科院计算所硕士论文，2001 黄萱菁等，独立于语种的文本分类方法，中文信息学报，2000年第6期 Software: Rainbow http://www-2.cs.cmu.edu/~mccallum/bow/ BoosTexter http://www.research.att.com/~schapire/BoosTexter/ TiMBL http://ilk.kub.nl/software.html#timbl C4.5 http://www.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.html Corpus http://www.cs.cmu.edu/~textlearning

Wangbin@ict.ac.cn http://mtgroup.ict.ac.cn/~wangbin 谢谢！ Wangbin@ict.ac.cn http://mtgroup.ict.ac.cn/~wangbin