文本分类综述课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,文本分类综述,王 斌,中国科学院计算技术研究所,2013,年,10,月,文本分类综述王 斌,报告内容,文本分类的定义和应用,文本分类的方法,文本分类的评估指标,参考文献和资源,报告内容文本分类的定义和应用,文本分类的定义和应用,文本分类的定义和应用,定义,给定分类体系，将文本分到某个或者某几个类别中。,分类体系一般人工构造,政治、体育、军事,中美关系、恐怖事件,分类系统可以是层次结构，如,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,应用垃圾邮件的判定(spam or not spam),文本分类的方法,文本分类的方法,人工方法和自动方法,人工方法,结果容易理解,足球,and,联赛,体育类,费时费力,难以保证一致性和准确性,(40%,左右的准确率,),专家有时候凭空想象,知识工程的方法建立专家系统,(80,年代末期,),自动的方法,(,学习,),结果可能不易理解,快速,准确率相对高,(,准确率可达,60%,或者更高,),来源于真实文本，可信度高,人工方法和自动方法人工方法,文本分类的过程,文本表示,训练过程,分类过程,训练文本,统计,统计量,特征表示,学习,分类器,新文本,特征表示,类别,文本分类的过程文本表示训练过程分类过程训练文本统计统计量特征,特征抽取,(feature extraction),预处理,去掉,html,一些,tag,标记,禁用词,(stop words),去除、词根还原,(stemming),(,中文,),分词、词性标注、短语识别、,词频统计,TF,i,j,:,特征,i,在文档,j,中出现次数，词频,(Term Frequency),DF,i,:,所有文档集合中出现特征,i,的文档数目，文档频率,(Document Frequency),数据清洗：去掉不合适的噪声文档或文档内垃圾数据,文本表示,向量空间模型,降维技术,特征选择,(Feature Selection),特征重构,(Re-parameterisation,，如,LSI),特征抽取(feature extraction)预处理,文本表示,向量空间模型,(Vector Space Model),M,个无序标引项,t,i,(,特征,),，词根,/,词,/,短语,/,其他,每个文档,d,j,可以用标引项向量来表示,(a,1j,a,2j,a,Mj,),权重计算，,N,个训练文档,A,M*N,= (a,ij,),相似度比较,Cosine,计算,内积计算,文本表示向量空间模型(Vector Space Model),Term,的粒度,Character,，字：中,Word,，词：中国,Phrase,，短语：中国人民银行,Concept,，概念,同义词：开心 高兴 兴奋,相关词,cluster,，,word cluster,：葛非,/,顾俊,N-gram,，,N,元组：中国 国人 人民 民银 银行,某种规律性模式：比如某个,window,中出现的固定模式,David Lewis,等一致地认为,：,(,英文分类中,),使用优化合并后的,Words,比较合适,Term的粒度Character，字：中,权重计算方法,布尔权重,(boolean weighting),a,ij,=1(TF,ij,0) or (TF,ij,=0)0,TFIDF,型权重,TF: a,ij,=TF,ij,TF*IDF: a,ij,=TF,ij,*log(N/DF,i,),TFC:,对上面进行归一化,LTC:,降低,TF,的作用,基于熵概念的权重,(Entropy weighting),称为,term i,的某种熵,如果,term,分布极度均匀：熵等于,-1,只在一个文档中出现：熵等于,0,权重计算方法布尔权重(boolean weighting),特征选择,(1),基于,DF,Term,的,DF,小于某个阈值去掉,(,太少，没有代表性,),Term,的,DF,大于某个阈值也去掉,(,太多，没有区分度,),信息增益,(Information Gain, IG),：该,term,为整个分类所能提供的信息量,(,不考虑任何特征的熵,和,考虑该特征后的熵,的差值,),特征选择(1)基于DF,特征选择,(2),term,的某种熵：该值越大，说明分布越均匀，越有可能出现在较多的类别中；该值越小，说明分布越倾斜，词可能出现在较少的类别中,相对熵,(not,交叉熵,),：也称为,KL,距离,(Kullback-Leibler divergence),，反映了文本类别的概率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。,特征选择(2)term的某种熵：该值越大，说明分布越均匀，越,特征选择,(3),2,统计量,(,念,xi),：度量两者,(term,和类别,),独立性的缺乏程度，,2,越大，独立性越小，相关性越大,(,若,ADBC,则类和词独立, N=A+B+C+D),互信息,(Mutual Information),：,MI,越大,t,和,c,共现程度越大,A,B,C,D,t,t,c,c,特征选择(3)2 统计量(念xi)：度量两者(term和类,特征选择,(4),Robertson & Sparck Jones,公式,其他,Odds:,Term Strength:,特征选择(4)Robertson & Sparck Jone,特征选择方法的性能比较,(1),特征选择方法的性能比较(1),特征选择方法的性能比较,(2),特征选择方法的性能比较(2),特征选择方法的性能比较,(3),YangYi-ming,特征选择方法的性能比较(3)YangYi-ming,特征重构,隐性语义索引,(LSI),奇异值分解,(SVD),：,A=(a,ij,)=U,V,T,A,M*N, U,M*R, ,R*R,(,对角阵,),V,N*R,R=MIN(M,N),取,对角上的前,k,个元素，得,k,A,k,=,U,k,k,V,k,T,U,k,由,U,的前,k,列组成，,V,k,由,V,的前,k,列组成,文档,d,在,LSI,对应的向量,d=d,T,U,k,-1,在已有的,LSI,中增加新的,word,或者,document,，不需要重新计算,Folding-in,方法,SVD-updating,方法,特征重构隐性语义索引(LSI),自动文本分类方法,Rocchio,方法,Nave Bayes,kNN,方法,决策树方法,decision tree,Decision Rule Classifier,The Widrow-Hoff Classifier,神经网络方法,Neural Networks,支持向量机,SVM,基于投票的方法,(voting method),自动文本分类方法Rocchio方法,Rocchio,方法,可以认为类中心向量法是它的特例,Rocchio,公式,分类,类,C,中心向量的权重,训练样本中正例个数,文档向量的权重,Rocchio方法可以认为类中心向量法是它的特例类C中心向量,Nave Bayes,参数计算,Bayes,公式,Nave Bayes参数计算Bayes公式,kNN,方法,一种,Lazy Learning, Example-based Learning,新文本,k=1, A,类,k=4,，,B,类,k=10,，,B,类,带权重计算，计算权重和最大的类。,k,常取,3,或者,5,。,kNN方法一种Lazy Learning, Example-,决策树方法,构造决策树,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,算法,),学习到如下规则,Decision Rule Learningwheat &,The Widrow-Hoff Classifier,Online Learning,类,c,向量的第,j,个分量,x,i,的第,j,个分量,Learning Rate,Target Value ( 0 or 1),The Widrow-Hoff ClassifierOnli,Neural Network,.,.,.,.,.,c,1,c,2,c,n,Input Layer,Hidden Layer,Output Layer,Backpropagation,Neural Network.c1c2cnInp,支持向量机,Support Vector Machine,Support Vector,Optimal,Separating,Hyperplane,支持向量机Support Vector MachineSu,基于投票的方法,Bagging,方法,训练,R,个分类器,f,i,，分类器之间其他相同就是参数不同。其中,f,i,是通过从训练集合中,(N,篇文档,),随机取,(,取后放回,)N,次文档构成的训练集合训练得到的。,对于新文档,d,，用这,R,个分类器去分类，得到的最多的那个类别作为,d,的最终类别,Boosting,方法,类似,Bagging,方法，但是训练是串行进行的，第,k,个分类器训练时关注对前,k-1,分类器中错分的文档，即不是随机取，而是加大取这些文档的概率,AdaBoost,AdaBoost MH,基于投票的方法Bagging方法,文本分类的评估指标,文本分类的评估指标,分类方法的评估,邻接表,每个类,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/(,2,p+r),Break Even Point, BEP, p=r,的点,如果多类排序输出，采用,interpolated 11 point average precision,所有类：,宏平均,:,对每个类求值，然后平均,微平均,:,将所有文档一块儿计算，求值,真正对的,错误,标,YES,a,b,标,NO,c,d,分类方法的评估邻接表真正对的错误标YESab标NOcd,效果评估方法,N,交叉测试：,将训练集合分成,N,份，其中,N-1,份作为训练集，其余,1,份作为测试集。循环,N,次，将,N,次的结果平均。,开放测试,训练在某个集合中进行，而测试集采用另外事先未知的集合。,效果评估方法N交叉测试：,其他分类方法,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),.,其他分类方法Regression based on Leas,小结,训练,对训练文档进行处理，得到每篇文档的原始空间表示,采用特征选择方法,(DF/IG/MI,等,),选择好的特征，将原始空间转换到特征空间,采用某个分类器进行学习，得到分类器的参数,分类,/,测试,对新文本进行相同的特征表示过程,输入上述分类器得到分类结果,采用,N,交叉测试或者其他方式得到分类器的效果,小结训练,参考文献,参考文献,文献及其他资源,Papers,K. Aas and L. Eikvil.,Text categorisation: A survey,. Technical report, Norwegian Computing Center, June 1999, 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,