文本分类综述课件

文本分类综述王斌中国科学院计算技术研究所2013年10月文本分类综述王斌报告内容文本分类的定义和应用文本分类的方法文本分类的评估指标参考文献和资源报告内容文本分类的定义和应用文本分类的定义和应用文本分类的定义和应用定义给定分类体系，将文本分到某个或者某几个类别中。分类体系一般人工构造政治、体育、军事中美关系、恐怖事件分类系统可以是层次结构，如yahoo!分类模式2类问题，属于或不属于(binary)多类问题，多个类别(multi-class)，可拆分成2类问题一个文本可以属于多类(multi-label)这里讲的分类主要基于内容很多分类体系:Reuters分类体系、中图分类定义给定分类体系，将文本分到某个或者某几个类别中。应用垃圾邮件的判定(spamornotspam)类别{spam,not-spam}新闻出版按照栏目分类类别{政治,体育,军事,…}词性标注类别{名词,动词,形容词,…}词义排歧类别{词义1,词义2,…}计算机论文的领域类别ACMsystemH:informationsystemsH.3:informationretrievalandstorage应用垃圾邮件的判定(spamornotspam)文本分类的方法文本分类的方法人工方法和自动方法人工方法结果容易理解足球and联赛体育类费时费力难以保证一致性和准确性(40%左右的准确率)专家有时候凭空想象知识工程的方法建立专家系统(80年代末期)自动的方法(学习)结果可能不易理解快速准确率相对高(准确率可达60%或者更高)来源于真实文本，可信度高人工方法和自动方法人工方法文本分类的过程文本表示训练过程分类过程训练文本统计统计量特征表示学习分类器新文本문서特征表示类别文本分类的过程文本表示训练过程分类过程训练文本统计统计量特征特征抽取(featureextraction)预处理去掉html一些tag标记禁用词(stopwords)去除、词根还原(stemming)(中文)分词、词性标注、短语识别、…词频统计TFi,j:特征i在文档j中出现次数，词频(TermFrequency)DFi:所有文档集合中出现特征i的文档数目，文档频率(DocumentFrequency)数据清洗：去掉不合适的噪声文档或文档内垃圾数据文本表示向量空间模型降维技术特征选择(FeatureSelection)特征重构(Re-parameterisation，如LSI)特征抽取(featureextraction)预处理文本表示向量空间模型(VectorSpaceModel)M个无序标引项ti(特征)，词根/词/短语/其他每个文档dj可以用标引项向量来表示(a1j,a2j,…,aMj)权重计算，N个训练文档AM*N=(aij)相似度比较Cosine计算内积计算文本表示向量空间模型(VectorSpaceModel)Term的粒度Character，字：中Word，词：中国Phrase，短语：中国人民银行Concept，概念同义词：开心高兴兴奋相关词cluster，wordcluster：葛非/顾俊N-gram，N元组：中国国人人民民银银行某种规律性模式：比如某个window中出现的固定模式DavidLewis等一致地认为：(英文分类中)使用优化合并后的

Words比较合适Term的粒度Character，字：中权重计算方法布尔权重(booleanweighting)aij=1(TFij>0)or(TFij=0)0TFIDF型权重TF:aij=TFijTF*IDF:aij=TFij*log(N/DFi)TFC:对上面进行归一化LTC:降低TF的作用基于熵概念的权重(Entropyweighting)称为termi的某种熵如果term分布极度均匀：熵等于-1只在一个文档中出现：熵等于0权重计算方法布尔权重(booleanweighting)特征选择(1)基于DFTerm的DF小于某个阈值去掉(太少，没有代表性)Term的DF大于某个阈值也去掉(太多，没有区分度)

信息增益(InformationGain,IG)：该term为整个分类所能提供的信息量(不考虑任何特征的熵和考虑该特征后的熵的差值)特征选择(1)基于DF特征选择(2)term的某种熵：该值越大，说明分布越均匀，越有可能出现在较多的类别中；该值越小，说明分布越倾斜，词可能出现在较少的类别中相对熵(not交叉熵)：也称为KL距离(Kullback-Leiblerdivergence)

，反映了文本类别的概率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。特征选择(2)term的某种熵：该值越大，说明分布越均匀，越特征选择(3)χ2统计量(念xi)：度量两者(term和类别)独立性的缺乏程度，χ2越大，独立性越小，相关性越大(若AD<BC,则类和词独立,N=A+B+C+D)互信息(MutualInformation)：MI越大t和c共现程度越大ABCDt~tc~c特征选择(3)χ2统计量(念xi)：度量两者(term和类特征选择(4)Robertson&SparckJones公式其他Odds:TermStrength:特征选择(4)Robertson&SparckJone特征选择方法的性能比较(1)特征选择方法的性能比较(1)特征选择方法的性能比较(2)特征选择方法的性能比较(2)特征选择方法的性能比较(3)YangYi-ming特征选择方法的性能比较(3)YangYi-ming特征重构隐性语义索引(LSI)奇异值分解(SVD)：A=(aij)=UΣVTAM*N,UM*R,ΣR*R(对角阵),VN*R,

R<=MIN(M,N)取Σ对角上的前k个元素，得ΣkAk=

UkΣkVkT,Uk由U的前k列组成，Vk由V的前k列组成文档d在LSI对应的向量d’=dTUkΣ-1在已有的LSI中增加新的word或者document，不需要重新计算Folding-in方法SVD-updating方法特征重构隐性语义索引(LSI)自动文本分类方法Rocchio方法NaïveBayeskNN方法决策树方法decisiontreeDecisionRuleClassifierTheWidrow-HoffClassifier神经网络方法NeuralNetworks支持向量机SVM基于投票的方法(votingmethod)自动文本分类方法Rocchio方法Rocchio方法可以认为类中心向量法是它的特例Rocchio公式分类类C中心向量的权重训练样本中正例个数文档向量的权重Rocchio方法可以认为类中心向量法是它的特例类C中心向量NaïveBayes参数计算Bayes公式NaïveBayes参数计算Bayes公式kNN方法一种LazyLearning,Example-basedLearning新文本k=1,A类k=4，B类k=10，B类带权重计算，计算权重和最大的类。k常取3或者5。kNN方法一种LazyLearning,Example-决策树方法构造决策树CARTC4.5(由ID3发展而来)CHAID决策树的剪枝(pruning)决策树方法构造决策树DecisionRuleLearningwheat&formWHEATwheat&commodityWHEATbushels&exportWHEATwheat&agricultureWHEATwheat&tonnesWHEATwheat&winter&~softWHEAT(粗糙集)RoughSet逻辑表达式(AQ11算法)学习到如下规则DecisionRuleLearningwheat&TheWidrow-HoffClassifierOnlineLearning类c向量的第j个分量xi的第j个分量LearningRateTargetValue(0or1)TheWidrow-HoffClassifierOnliNeuralNetwork.....c1c2cn……InputLayerHiddenLayerOutputLayerBackpropagationNeuralNetwork.....c1c2cn……Inp支持向量机

SupportVectorMachineSupportVectorOptimalSeparatingHyperplane支持向量机

SupportVectorMachineSu基于投票的方法Bagging方法训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别Boosting方法类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率AdaBoostAdaBoostMH基于投票的方法Bagging方法文本分类的评估指标文本分类的评估指标分类方法的评估邻接表每个类Precision=a/(a+b),Recall=a/(a+c),fallout=b/(b+d)=falsealarmrate,accuracy=(a+d)/(a+b+c+d),error=(b+c)/(a+b+c+d)=1-accuracy,missrate=1-recallF=(β2+1)p.r/(β2p+r)BreakEvenPoint,BEP,p=r的点如果多类排序输出，采用interpolated11pointaverageprecision所有类：宏平均:对每个类求值，然后平均微平均:将所有文档一块儿计算，求值真正对的错误标YESab标NOcd分类方法的评估邻接表真正对的错误标YESab标NOcd效果评估方法N交叉测试：将训练集合分成N份，其中N-1份作为训练集，其余1份作为测试集。循环N次，将N次的结果平均。开放测试训练在某个集合中进行，而测试集采用另外事先未知的集合。效果评估方法N交叉测试：其他分类方法RegressionbasedonLeastSquaresFit(1991)NearestNeighborClassification(1992)*BayesianProbabilisticModels(1992)*SymbolicRuleInduction(1994)DecisionTree(1994)*NeuralNetworks(1995)Rocchioapproach(traditionalIR,1996)*SupportVectorMachines(1997)BoostingorBagging(1997)*HierarchicalLanguageModeling(1998)First-Order-LogicRuleInduction(1999)MaximumEntropy(1999)HiddenMarkovModels(1999)Error-CorrectingOutputCoding(1999)...其他分类方法RegressionbasedonLeas小结训练对训练文档进行处理，得到每篇文档的原始空间表示采用特征选择方法(DF/IG/MI等)选择好的特征，将原始空间转换到特征空间采用某个分类器进行学习，得到分类器的参数分类/测试对新文本进行相同的特征表示过程输入上述分类器得到分类结果采用N交叉测试或者其他方式得到分类器的效果小结训练参考文献参考文献文献及其他资源PapersK.AasandL.Eikvil.Textcategorisation:Asurvey.Technicalreport,NorwegianComputingCenter,June1999/aas99text.htmlXiaomengSu，“Textcategorization”，LessonPresentationYimingYangandXinLiu.1999."Are-examinationoftextcategorizationmethods."22ndAnnualInternationalSIGIR/~yiming/publications.htmlASurveyonTextCategorization,NLPLab,KoreanU.庞剑峰，基于向量空间模型的自反馈的文本分类系统的研究与实现，中科院计算所硕士论文，2001

黄萱菁等，独立于语种的文本分类方法，中文信息学报，2000年第6期Software:Rainbow/~mccallum/bow/BoosTexter/~schapire/BoosTexter/TiMBLhttp://ilk.kub.nl/software.html#timblC4.5http://www.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.htmlCorpus/~textlearning文献及其他资源Papers谢谢！Wangbin@/~wangbin谢谢！Wangbin@文本分类综述王斌中国科学院计算技术研究所2013年10月文本分类综述王斌报告内容文本分类的定义和应用文本分类的方法文本分类的评估指标参考文献和资源报告内容文本分类的定义和应用文本分类的定义和应用文本分类的定义和应用定义给定分类体系，将文本分到某个或者某几个类别中。分类体系一般人工构造政治、体育、军事中美关系、恐怖事件分类系统可以是层次结构，如yahoo!分类模式2类问题，属于或不属于(binary)多类问题，多个类别(multi-class)，可拆分成2类问题一个文本可以属于多类(multi-label)这里讲的分类主要基于内容很多分类体系:Reuters分类体系、中图分类定义给定分类体系，将文本分到某个或者某几个类别中。应用垃圾邮件的判定(spamornotspam)类别{spam,not-spam}新闻出版按照栏目分类类别{政治,体育,军事,…}词性标注类别{名词,动词,形容词,…}词义排歧类别{词义1,词义2,…}计算机论文的领域类别ACMsystemH:informationsystemsH.3:informationretrievalandstorage应用垃圾邮件的判定(spamornotspam)文本分类的方法文本分类的方法人工方法和自动方法人工方法结果容易理解足球and联赛体育类费时费力难以保证一致性和准确性(40%左右的准确率)专家有时候凭空想象知识工程的方法建立专家系统(80年代末期)自动的方法(学习)结果可能不易理解快速准确率相对高(准确率可达60%或者更高)来源于真实文本，可信度高人工方法和自动方法人工方法文本分类的过程文本表示训练过程分类过程训练文本统计统计量特征表示学习分类器新文本문서特征表示类别文本分类的过程文本表示训练过程分类过程训练文本统计统计量特征特征抽取(featureextraction)预处理去掉html一些tag标记禁用词(stopwords)去除、词根还原(stemming)(中文)分词、词性标注、短语识别、…词频统计TFi,j:特征i在文档j中出现次数，词频(TermFrequency)DFi:所有文档集合中出现特征i的文档数目，文档频率(DocumentFrequency)数据清洗：去掉不合适的噪声文档或文档内垃圾数据文本表示向量空间模型降维技术特征选择(FeatureSelection)特征重构(Re-parameterisation，如LSI)特征抽取(featureextraction)预处理文本表示向量空间模型(VectorSpaceModel)M个无序标引项ti(特征)，词根/词/短语/其他每个文档dj可以用标引项向量来表示(a1j,a2j,…,aMj)权重计算，N个训练文档AM*N=(aij)相似度比较Cosine计算内积计算文本表示向量空间模型(VectorSpaceModel)Term的粒度Character，字：中Word，词：中国Phrase，短语：中国人民银行Concept，概念同义词：开心高兴兴奋相关词cluster，wordcluster：葛非/顾俊N-gram，N元组：中国国人人民民银银行某种规律性模式：比如某个window中出现的固定模式DavidLewis等一致地认为：(英文分类中)使用优化合并后的

Words比较合适Term的粒度Character，字：中权重计算方法布尔权重(booleanweighting)aij=1(TFij>0)or(TFij=0)0TFIDF型权重TF:aij=TFijTF*IDF:aij=TFij*log(N/DFi)TFC:对上面进行归一化LTC:降低TF的作用基于熵概念的权重(Entropyweighting)称为termi的某种熵如果term分布极度均匀：熵等于-1只在一个文档中出现：熵等于0权重计算方法布尔权重(booleanweighting)特征选择(1)基于DFTerm的DF小于某个阈值去掉(太少，没有代表性)Term的DF大于某个阈值也去掉(太多，没有区分度)

信息增益(InformationGain,IG)：该term为整个分类所能提供的信息量(不考虑任何特征的熵和考虑该特征后的熵的差值)特征选择(1)基于DF特征选择(2)term的某种熵：该值越大，说明分布越均匀，越有可能出现在较多的类别中；该值越小，说明分布越倾斜，词可能出现在较少的类别中相对熵(not交叉熵)：也称为KL距离(Kullback-Leiblerdivergence)

，反映了文本类别的概率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。特征选择(2)term的某种熵：该值越大，说明分布越均匀，越特征选择(3)χ2统计量(念xi)：度量两者(term和类别)独立性的缺乏程度，χ2越大，独立性越小，相关性越大(若AD<BC,则类和词独立,N=A+B+C+D)互信息(MutualInformation)：MI越大t和c共现程度越大ABCDt~tc~c特征选择(3)χ2统计量(念xi)：度量两者(term和类特征选择(4)Robertson&SparckJones公式其他Odds:TermStrength:特征选择(4)Robertson&SparckJone特征选择方法的性能比较(1)特征选择方法的性能比较(1)特征选择方法的性能比较(2)特征选择方法的性能比较(2)特征选择方法的性能比较(3)YangYi-ming特征选择方法的性能比较(3)YangYi-ming特征重构隐性语义索引(LSI)奇异值分解(SVD)：A=(aij)=UΣVTAM*N,UM*R,ΣR*R(对角阵),VN*R,

R<=MIN(M,N)取Σ对角上的前k个元素，得ΣkAk=

UkΣkVkT,Uk由U的前k列组成，Vk由V的前k列组成文档d在LSI对应的向量d’=dTUkΣ-1在已有的LSI中增加新的word或者document，不需要重新计算Folding-in方法SVD-updating方法特征重构隐性语义索引(LSI)自动文本分类方法Rocchio方法NaïveBayeskNN方法决策树方法decisiontreeDecisionRuleClassifierTheWidrow-HoffClassifier神经网络方法NeuralNetworks支持向量机SVM基于投票的方法(votingmethod)自动文本分类方法Rocchio方法Rocchio方法可以认为类中心向量法是它的特例Rocchio公式分类类C中心向量的权重训练样本中正例个数文档向量的权重Rocchio方法可以认为类中心向量法是它的特例类C中心向量NaïveBayes参数计算Bayes公式NaïveBayes参数计算Bayes公式kNN方法一种LazyLearning,Example-basedLearning新文本k=1,A类k=4，B类k=10，B类带权重计算，计算权重和最大的类。k常取3或者5。kNN方法一种LazyLearning,Example-决策树方法构造决策树CARTC4.5(由ID3发展而来)CHAID决策树的剪枝(pruning)决策树方法构造决策树DecisionRuleLearningwheat&formWHEATwheat&commodityWHEATbushels&exportWHEATwheat&agricultureWHEATwheat&tonnesWHEATwheat&winter&~softWHEAT(粗糙集)RoughSet逻辑表达式(AQ11算法)学习到如下规则DecisionRuleLearningwheat&TheWidrow-HoffClassifierOnlineLearning类c向量的第j个分量xi的第j个分量LearningRateTargetValue(0or1)TheWidrow-HoffClassifierOnliNeuralNetwork.....c1c2cn……InputLayerHiddenLayerOutputLayerBackpropagationNeuralNetwork.....c1c2cn……Inp支持向量机

SupportVectorMachineSupportVectorOptimalSeparatingHyperplane支持向量机

SupportVectorMachineSu基于投票的方法Bagging方法训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别Boosting方法类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率AdaBoostAdaBoostMH基于投票的方法Bagging方法文本分类的评估指标文本分类的评估指标分类方法的评估邻接表每个类Precision=a/(a+b),Recall=a/(a+c),fallout=b/(b+d)=falsealarmrate,accuracy=(a+d)/(a+b+c+d),error=(b+c)/(a+b+c+d)=1-accuracy,missrate=1-recallF=(β2+1)p.r/(β2p+r)BreakEvenPoint,BEP,p=r的点如果多类排序输出，采用interpolated11pointaverageprecision所有类：宏平均:对每个类求值，然后平均微平均:将所有文档一块儿计算，求值真正对的错误标YESab标NOcd分类方法的评估邻接表真正对的错误标YESab标NOcd效果评估方法N交叉测试：将训练集合分成N份，其中N-1份作为训练集，其余1份作为测试集。循环N次，将N次的结果平均。开放测试训练在某个集合中进行，而测试集采用另外事先未知的集合。效果评估方法N交叉测试：其他分类方法RegressionbasedonLeastSquaresFit(1991)NearestNeighborClassification(1992)*BayesianProbabilisticModels(1992)*SymbolicR