文本分类综述 郑亚斌 清华大学自然语言处理组 2008-11-15 部分内容copy自王斌老师ppt

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

文本分类的定义和应用

定义 给定分类体系，将文本分到某个或者某几个类别中。 分类体系一般人工构造 分类系统可以是层次结构，如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%或者更高) 来源于真实文本，可信度高

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

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

文本表示 向量空间模型(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元组：中国 国人 人民 民银 银行 某种规律性模式：比如某个窗口中出现的固定模式 中文文本分类使用那种粒度？

Term粒度—中文 词特征 V.S. Bigram特征 假设分词100%准确 中文分词？更困难的学术问题 Bigram？简单粗暴 在低维度达到更好 的结果 现实中不可能的

Term粒度—中文 ICTCLAS分词V.S. Bigram So, 实用性角度：分词 研究角度：Bigram 词的数目有限 Bigram特征数目更多， 可以提供更多的特征 So, 实用性角度：分词 研究角度：Bigram

权重计算方法 布尔权重(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 统计量：度量两者(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:

特征选择方法性能比较

特征选择方法性能比较 Yiming Yang and Xin Liu. 1999. “A re-examination of text categorization methods.” 22ndAnnual International SIGIR’99

特征重构 隐性语义索引(Latent Semantic Index) Latent Dirichlet allocation(LDA) 奇异值分解(SVD)：A=(aij)=UΣVT 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 Latent Dirichlet allocation(LDA) Topic Model Bag-Of-Words表示 -> Topic表示

自动文本分类方法 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

文本分类的评估指标

分类方法的评估 真正对的 错误 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) ...

Demo Show

文本分类的一些新方向

传统文本分类研究方向 特征选择 权重计算 不平衡数据集分类 训练集样本很少(半监督学习) Active-Learning：加入人工的因素 基本上文本分类作为检验新的机器学习方法的平台

新方向 短文本分类 最大的问题：信息缺失 Ask Google Snippet 代价太高，仅供研究，不实用

短文本分类 利用Topic Model补充缺失信息

语义信息补充 现今的文本分类算法未考虑词的语义信息 英文中：短语拆开成了单词 Machine Learning, Statistical Learning, and Data Mining are related subjects Machine Learning ≠ Machine + Learning Concepts Terms

开方测试问题 论文中的指标都是在封闭训练测试上计算 Web上的文本错综复杂，不可能有统一的分类体系 在训练集合A上的模型，自适应的转移到集合B中的文本分布？ Transfer Learning 主要问题在于成本较高

其他一些问题 多类别数目分类问题： 分类速度： 比如类别数有成百上千的情况 SVM？训练时一般采用One V.S. One方法 如果一定要选，Naïve Bayes方法更鲁棒 分类速度： 实用的角度不可能采用paper中的方法 一般在速度和效果中寻求Tradeoff

参考文献

文献及其他资源 Google 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 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 Google

文献及其他资源 F. Sebastiani, Machine Learning in Automated Text Categorization, ACM Computing Surveys, 34(1): pp. 1-47, 2002. Li J Y, Sun MS, Zhang X. A comparison and semi-quantitative analysis of words and character-bigrams as features in Chinese text categorization. COLING-ACL’ 06 Pu Wang, Carlotta Domeniconi. Building Semantic Kernels for Text Classification using Wikipedia. KDD 08’ Xuan-Hieu Phan,Le-Minh Nguyen, Susumu Horiguchi. Learning to Classify Short and Sparse Text & Web with Hidden Topics from Large-scale Data Collections. WWW’ 08 W.Y. Dai, G.R. Xue, Q. Yang and Y. Yu, Transferring Naive Bayes Classifiers for Text Classification, AAAI 07’ C.Do, A. Ng, Transfer Learning for text classification. NIPS’ 05 F. Mourão, L. Rocha, et al., Understanding Temporal Aspects in Document Classification, WSDM 07’

谢谢！