1、文本分类综述,郑亚斌清华大学自然语言处理组2008-11-15,部分内容copy自王斌老师ppt,报告内容,文本分类的定义和应用文本分类的方法文本分类的评估指标文本分类的一些新方向参考文献和资源,文本分类的定义和应用,定义,给定分类体系，将文本分到某个或者某几个类别中。分类体系一般人工构造政治、体育、军事中美关系、恐怖事件分类系统可以是层次结构，如yahoo!分类模式2类问题，属于或不属于(binary)多类问题，多个类别(multi-class)，可拆分成2类问题一个文本可以属于多类(multi-label)这里讲的分类主要基于内容很多分类体系: Reuters分类体系、中图分类,应用,垃圾
2、邮件的判定(spam or not spam)类别 spam, not-spam新闻出版按照栏目分类类别 政治,体育,军事,词性标注类别 名词,动词,形容词,词义排歧类别 词义1,词义2,计算机论文的领域类别 ACM systemH: information systemsH.3: information retrieval and storage,文本分类的方法,人工方法和自动方法,人工方法结果容易理解足球 and 联赛体育类费时费力难以保证一致性和准确性(40%左右的准确率)专家有时候凭空想象知识工程的方法建立专家系统(80年代末期)自动的方法(学习)结果可能不易理解快速准确率相对高(准确
3、率可达60%或者更高)来源于真实文本，可信度高,文本分类的过程,特征抽取,预处理去掉html一些tag标记(英文)禁用词(stop words)去除、词根还原(stemming)(中文)分词、词性标注、短语识别、词频统计TFi,j: 特征i在文档j中出现次数，词频(Term Frequency)DFi:所有文档集合中出现特征i的文档数目，文档频率(Document Frequency)数据清洗：去掉不合适的噪声文档或文档内垃圾数据文本表示向量空间模型(Vector Space Model)降维技术特征选择(Feature Selection)特征重构(Re-parameterisation，如
4、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元组：中国 国人 人民 民银 银行某种规律性模式：比如某个窗口中出现的固定模式中文文本分类使用那
5、种粒度？,Term粒度中文,词特征 V.S. Bigram特征中文分词？更困难的学术问题Bigram？简单粗暴假设分词100%准确在低维度达到更好的结果现实中不可能的,Term粒度中文,ICTCLAS分词V.S. Bigram低维度：词 Bigram高维度 ：Bigram 词词的数目有限Bigram特征数目更多，可以提供更多的特征So, 实用性角度：分词研究角度：Bigram,权重计算方法,布尔权重(Boolean weighting)aij=1(TFij0) or (TFij=0)0TFIDF型权重TF: aij=TFijTF*IDF: aij=TFij*log(N/DFi)TFC: 对上面
6、进行归一化LTC: 降低TF的作用基于熵概念的权重(Entropy weighting)称为term i的某种熵如果term分布极度均匀：熵等于-1只在一个文档中出现：熵等于0,特征选择(1),基于DF Term的DF小于某个阈值去掉(太少，没有代表性)Term的DF大于某个阈值也去掉(太多，没有区分度) 信息增益(Information Gain, IG)：该term为整个分类所能提供的信息量(不考虑任何特征的熵和考虑该特征后的熵的差值),特征选择(2),term的某种熵：该值越大，说明分布越均匀，越有可能出现在较多的类别中(区分度差)；该值越小，说明分布越倾斜，词可能出现在较少的类别中(区
7、分度好)相对熵(not 交叉熵)：也称为KL距离(Kullback-Leibler divergence) ，反映了文本类别的概率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。,特征选择(3),2 统计量：度量两者(term和类别)独立性的缺乏程度， 2 越大，独立性越小，相关性越大(若ADBC,则类和词独立, N=A+B+C+D)互信息(Mutual Information)：MI越大t和c共现程度越大,特征选择(4),Robertson & Sparck Jones公式其他Odds: Term Strength:,特征选择方法性能比较
8、,特征选择方法性能比较,Yiming Yang and Xin Liu. 1999. “A re-examination of text categorization methods.” 22ndAnnual International SIGIR99,特征重构,隐性语义索引(Latent Semantic Index)奇异值分解(SVD)：A=(aij)=UVTAM*N, UM*R, R*R(对角阵), VN*R, R Topic表示,自动文本分类方法,Rocchio方法Nave BayeskNN方法决策树方法decision treeDecision Rule ClassifierThe
9、Widrow-Hoff Classifier神经网络方法Neural Networks支持向量机SVM基于投票的方法(voting method),Rocchio方法,可以认为类中心向量法是它的特例Rocchio公式分类,Nave Bayes,参数计算,Bayes公式,kNN方法,一种Lazy Learning, Example-based Learning,新文本,k=1, A类,k=4，B类,k=10，B类,带权重计算，计算权重和最大的类。k常取3或者5。,决策树方法,构造决策树CARTC4.5 (由ID3发展而来)CHAID决策树的剪枝(pruning),Decision Rule Le
10、arning,wheat & form WHEATwheat & commodity WHEATbushels & export WHEATwheat & agriculture WHEATwheat & tonnes WHEATwheat & winter & soft WHEAT,(粗糙集)RoughSet 逻辑表达式(AQ11算法),学习到如下规则,The Widrow-Hoff Classifier,Online Learning,Neural Network,.,.,.,.,.,c1,c2,cn,Input Layer,Hidden Layer,Output Layer,Backpr
11、opagation,支持向量机Support Vector Machine,Support Vector,Optimal Separating Hyperplane,基于投票的方法,Bagging方法训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别Boosting方法类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率(加大对错分样本的学习能力)A
12、daBoost,文本分类的评估指标,分类方法的评估,邻接表每个类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-recallF=(2+1)p.r/(2p+r)Break Even Point, BEP, p=r的点如果多类排序输出，采用interpolated 11 point average precision所有类：宏平均:对每个类求值，然后平均微平均:将所有
13、文档一块儿计算，求值,其他分类方法,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 Bag
14、ging (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：加入人工的因素基本上文本分类作为检验新的机器学习方法的平台,新方向,短文本分类最大的问题：信
15、息缺失Ask Google Snippet代价太高，仅供研究，不实用,短文本分类,利用Topic Model补充缺失信息,语义信息补充,现今的文本分类算法未考虑词的语义信息英文中：短语拆开成了单词Machine Learning, Statistical Learning, and Data Mining are related subjectsMachine Learning Machine + Learning,Concepts,Terms,开方测试问题,论文中的指标都是在封闭训练测试上计算Web上的文本错综复杂，不可能有统一的分类体系在训练集合A上的模型，自适应的转移到集合B中的文本分布
16、？Transfer Learning主要问题在于成本较高,其他一些问题,多类别数目分类问题：比如类别数有成百上千的情况SVM？训练时一般采用One V.S. One方法如果一定要选，Nave Bayes方法更鲁棒分类速度：实用的角度不可能采用paper中的方法一般在速度和效果中寻求Tradeoff,参考文献,文献及其他资源,PapersK. Aas and L. Eikvil. Text categorisation: A survey. Technical report, Norwegian Computing Center, June 1999 http:/ Su， “Text categ
17、orization”，Lesson PresentationYiming Yang and Xin Liu. 1999. A re-examination of text categorization methods. 22ndAnnual International SIGIRA Survey on Text Categorization, NLP Lab, Korean U.庞剑峰，基于向量空间模型的自反馈的文本分类系统的研究与实现，中科院计算所硕士论文，2001 黄萱菁等，独立于语种的文本分类方法，中文信息学报，2000年第6期Software:Rainbow http:/www-2.c
18、s.cmu.edu/mccallum/bow/BoosTexter http:/ http:/ilk.kub.nl/software.html#timbl C4.5 http:/www.cs.uregina.ca/dbd/cs831/notes/ml/dtrees/c4.5/tutorial.htmlCorpushttp:/www.cs.cmu.edu/textlearning Google,文献及其他资源,F. Sebastiani, Machine Learning in Automated Text Categorization, ACM Computing Surveys, 34(1)
19、: 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 06Pu Wang, Carlotta Domeniconi. Building Semantic Kernels for Text Classification using Wikipedia. KDD 08Xuan-Hieu Phan,Le-Minh
20、Nguyen, Susumu Horiguchi. Learning to Classify Short and Sparse Text & Web with Hidden Topics from Large-scale Data Collections. WWW 08W.Y. Dai, G.R. Xue, Q. Yang and Y. Yu, Transferring Naive Bayes Classifiers for Text Classification, AAAI 07C.Do, A. Ng, Transfer Learning for text classification. NIPS 05 F. Mouro, L. Rocha, et al., Understanding Temporal Aspects in Document Classification, WSDM 07,谢谢！,
