文本分类综述.ppt

文本分类综述,报告内容,文本分类的定义和应用文本分类的方法文本分类的评估指标参考文献和资源,文本分类的定义和应用,定义,给定分类体系，将文本分到某个或者某几个类别中。分类体系一般人工构造政治、体育、军事中美关系、恐怖事件分类系统可以是层次结构，如yahoo!分类模式2类问题，属于或不属于(binary)多类问题，多个类别(multi-class)，可拆分成2类问题一个文本可以属于多类(multi-label)这里讲的分类主要基于内容很多分类体系:Reuters分类体系、中图分类,应用,垃圾邮件的判定(spam or not spam)类别 spam,not-spam新闻出版按照栏目分类类别 政治,体育,军事,词性标注类别 名词,动词,形容词,词义排歧类别 词义1,词义2,计算机论文的领域类别 ACM systemH:information systemsH.3:information retrieval and storage,文本分类的方法,人工方法和自动方法,人工方法结果容易理解足球 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)aij=1(TFij0)or(TFij=0)0TFIDF型权重TF:aij=TFijTF*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 越大，独立性越小，相关性越大(若ADBC,则类和词独立,N=A+B+C+D)互信息(Mutual Information)：MI越大t和c共现程度越大,特征选择(4),Robertson&Sparck Jones公式其他Odds:Term Strength:,特征选择方法的性能比较(1),特征选择方法的性能比较(2),特征选择方法的性能比较(3),YangYi-ming,特征重构,隐性语义索引(LSI)奇异值分解(SVD)：A=(aij)=UVTAM*N,UM*R,R*R(对角阵),VN*R,R=MIN(M,N)取对角上的前k个元素，得kAk=UkkVkT,Uk由U的前k列组成，Vk由V的前k列组成文档d在LSI对应的向量d=dTUk-1在已有的LSI中增加新的word或者document，不需要重新计算Folding-in 方法SVD-updating方法,自动文本分类方法,Rocchio方法Nave BayeskNN方法决策树方法decision treeDecision Rule ClassifierThe 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 Learning,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,Backpropagation,支持向量机Support Vector Machine,Support Vector,Optimal Separating Hyperplane,基于投票的方法,Bagging方法训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别Boosting方法类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率AdaBoostAdaBoost MH,文本分类的评估指标,分类方法的评估,邻接表每个类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所有类：宏平均:对每个类求值，然后平均微平均:将所有文档一块儿计算，求值,其他分类方法,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).,参考文献,文献及其他资源,PapersK.Aas and L.Eikvil.Text categorisation:A survey.Technical report,Norwegian Computing Center,June 1999 Xiaomeng Su，“Text categorization”，Lesson PresentationYiming Yang and Xin Liu.1999.A re-examination of text categorization methods.22ndAnnual International SIGIR http:/www.cs.cmu.edu/yiming/publications.htmlA Survey on Text Categorization,NLP Lab,Korean U.庞剑峰，基于向量空间模型的自反馈的文本分类系统的研究与实现，中科院计算所硕士论文，2001 黄萱菁等，独立于语种的文本分类方法，中文信息学报，2000年第6期Software:Rainbow http:/www-2.cs.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,谢谢！,http:/,