文本文献自动分类综述分析课件.ppt

1、文本文献自动分类综述报告内容 文本分类的定义和应用 文本分类的方法 文本分类的评估指标 文本分类的一些新方向 参考文献和资源文本分类的定义和应用定义 给定分类体系，将文本分到某个或者某几个类别中。 分类体系一般人工构造 政治、体育、军事 中美关系、恐怖事件 分类系统可以是层次结构，如yahoo! 分类模式 2类问题，属于或不属于(binary) 多类问题，多个类别(multi-class)，可拆分成2类问题 一个文本可以属于多类(multi-label) 这里讲的分类主要基于内容 很多分类体系: Reuters分类体系、中图分类应用 垃圾邮件的判定(spam or not spam) 类别 s

2、pam, not-spam 新闻出版按照栏目分类 类别 政治,体育,军事, 词性标注 类别 名词,动词,形容词, 词义排歧 类别 词义1,词义2, 计算机论文的领域 类别 ACM system H: information systems H.3: information retrieval and storage文本分类的方法人工方法和自动方法 人工方法 结果容易理解 足球 and 联赛体育类 费时费力 难以保证一致性和准确性(40%左右的准确率) 专家有时候凭空想象 知识工程的方法建立专家系统(80年代末期) 自动的方法(学习) 结果可能不易理解 快速 准确率相对高(准确率可达60%或者更

3、高) 来源于真实文本，可信度高文本分类的过程文本表示训练过程分类过程训练文本统计统计量特征表示学习分类器新文本特征表示类别特征抽取 预处理 去掉html一些tag标记 (英文)禁用词(stop words)去除、词根还原(stemming) (中文)分词、词性标注、短语识别、 词频统计 TFi,j: 特征i在文档j中出现次数，词频(Term Frequency) DFi:所有文档集合中出现特征i的文档数目，文档频率(Document Frequency) 数据清洗：去掉不合适的噪声文档或文档内垃圾数据 文本表示 向量空间模型(Vector Space Model) 降维技术 特征选择(Feat

4、ure 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-

5、gram，N元组：中国 国人 人民 民银 银行 某种规律性模式：比如某个窗口中出现的固定模式 中文文本分类使用那种粒度？Term粒度中文 词特征 V.S. Bigram特征 中文分词？更困难的学术问题 Bigram？简单粗暴 假设分词100%准确 在低维度达到更好的结果 现实中不可能的Term粒度中文 ICTCLAS分词V.S. Bigram 低维度：词 Bigram 高维度 ：Bigram 词 词的数目有限 Bigram特征数目更多，可以提供更多的特征 So, 实用性角度：分词研究角度：Bigram权重计算方法 布尔权重(Boolean weighting) aij=1(TFij0) or

6、(TFij=0)0 TFIDF型权重 TF: aij=TFij TF*IDF: aij=TFij*log(N/DFi) TFC: 对上面进行归一化 LTC: 降低TF的作用 基于熵概念的权重(Entropy weighting) 称为term i的某种熵 如果term分布极度均匀：熵等于-1 只在一个文档中出现：熵等于0kkkjiijijDFNTFDFNTFa2)/log(*)/log(*kkkjiijijDFNTFDFNTFa2)/log(*)0 . 1log()/log(*)0 . 1log()log(log11*)0 . 1log(1NjiijiijijijDFTFDFTFNTFa特征选

7、择(1) 基于DF Term的DF小于某个阈值去掉(太少，没有代表性) Term的DF大于某个阈值也去掉(太多，没有区分度) 信息增益(Information Gain, IG)：该term为整个分类所能提供的信息量(不考虑任何特征的熵和考虑该特征后的熵的差值)|(log)|()( )|(log)|()( )(log)( ) Entropy(Expected)(EntropyGain(t)111tcPtcPtPtcPtcPtPcPcPSSiMiiiMiiiMiit特征选择(2) term的某种熵：该值越大，说明分布越均匀，越有可能出现在较多的类别中(区分度差)；该值越小，说明分布越倾斜，词可能

8、出现在较少的类别中(区分度好) 相对熵(not 交叉熵)：也称为KL距离(Kullback-Leibler divergence) ，反映了文本类别的概率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。iiitcPtcPtEntropy)|(log)|()(iiiicPtcPtcPtCE)()|(log)|()(特征选择(3) 2 统计量：度量两者(term和类别)独立性的缺乏程度， 2 越大，独立性越小，相关性越大(若ADBC,则类和词独立, N=A+B+C+D) 互信息(Mutual Information)：MI越大t和c共现程度越大

9、ABCDttcc)()()()(),(22DCBADBCACBADNct),()()(212imiiAVGctcPt),(max)(212imiMAXctt)(log)()|(log)()()(log),(BACANAtPctPcPtPctPctImiiiAVGctIcPtI1),()()(),()(max)(1iimiMAXctIcPtI特征选择(4) Robertson & Sparck Jones公式 其他 Odds: Term Strength: )|()|(log),(jjjjjctPctPtctcctRSJ的概率中出现非的概率中出现类文档个数的为出现jjjjctrctPctPrct

10、TSV,)|()|(log*),()|(log)|(1log()|(1log()|(logjjjjctPctPctPctP是相关的两篇文档yxxtytP,),|( 特征选择方法性能比较 特征选择方法性能比较Yiming Yang and Xin Liu. 1999. “A re-examination of text categorization methods.” 22ndAnnual International SIGIR99特征重构 隐性语义索引(Latent Semantic Index) 奇异值分解(SVD)：A=(aij)=UVT AM*N, UM*R, R*R(对角阵), VN*

11、R, R Topic表示自动文本分类方法 Rocchio方法 Nave Bayes kNN方法 决策树方法decision tree Decision Rule Classifier The Widrow-Hoff Classifier 神经网络方法Neural Networks 支持向量机SVM 基于投票的方法(voting method)Rocchio方法 可以认为类中心向量法是它的特例 Rocchio公式 分类CCiijCCiijjcjcnnxnxww类C中心向量的权重训练样本中正例个数文档向量的权重22cxw)(ijcjijcjiicxwxwdCSVNave Bayes)()|()()

12、()|()|(jjiijjiijcPcdPdPcPcdPdcP，独立性假设rkjikjicwPcdP1)|()|(参数计算Bayes公式1)(|)(1)()()(kkjkkjjjcNccNcNcNccP总文档个数的文档个数kkjijjjijiNNccwcwP不同词个数的次数类所有文档中出现的词在类别文档中出现的次数在1)|(kNN方法 一种Lazy Learning, Example-based Learning新文本k=1, A类k=4，B类k=10，B类带权重计算，计算权重和最大的类。k常取3或者5。决策树方法 构造决策树 CART C4.5 (由ID3发展而来) CHAID 决策树的剪枝

13、(pruning)Decision Rule Learningwheat & form WHEATwheat & commodity WHEATbushels & export WHEATwheat & agriculture WHEATwheat & tonnes WHEATwheat & winter & soft WHEAT(粗糙集)RoughSet 逻辑表达式(AQ11算法)学习到如下规则The Widrow-Hoff Classifier22cxw)(ijcjijcjiicxwxwdCSVOnline Learningijitcjtxywwcj)xw(2ic)()1(类c向量的第j个

14、分量xi的第j个分量Learning RateTarget Value ( 0 or 1)Neural Network.c1c2cnInput LayerHidden LayerOutput Layer支持向量机Support Vector MachineSupport VectorOptimal Separating Hyperplane基于投票的方法 Bagging方法 训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。 对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别 Bo

15、osting方法 类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率(加大对错分样本的学习能力) AdaBoost文本分类的评估指标分类方法的评估 邻接表 每个类 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 Eve

16、n 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 Netw

17、orks (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文本分类的一些新方向传统文本分类研究方

18、向 特征选择 权重计算 不平衡数据集分类 训练集样本很少(半监督学习) Active-Learning：加入人工的因素 基本上文本分类作为检验新的机器学习方法的平台新方向 短文本分类 最大的问题：信息缺失 Ask Google Snippet 代价太高，仅供研究，不实用短文本分类 利用Topic Model补充缺失信息语义信息补充 现今的文本分类算法未考虑词的语义信息 英文中：短语拆开成了单词Machine Learning, Statistical Learning, and Data Mining are related subjectsMachine Learning Machine +

19、 LearningConceptsTerms开方测试问题 论文中的指标都是在封闭训练测试上计算 Web上的文本错综复杂，不可能有统一的分类体系 在训练集合A上的模型，自适应的转移到集合B中的文本分布？ Transfer Learning 主要问题在于成本较高其他一些问题 多类别数目分类问题： 比如类别数有成百上千的情况 SVM？训练时一般采用One V.S. One方法 如果一定要选，Nave Bayes方法更鲁棒 分类速度： 实用的角度不可能采用paper中的方法 一般在速度和效果中寻求Tradeoff参考文献文献及其他资源PapersK. Aas and L. Eikvil. Text c

20、ategorisation: A survey. Technical report, Norwegian Computing Center, June 1999 http:/ Su， “Text categorization”，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.庞剑峰，基于

21、向量空间模型的自反馈的文本分类系统的研究与实现，中科院计算所硕士论文，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 Google

22、文献及其他资源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 06Pu Wang, Carlotta Domenic

23、oni. Building Semantic Kernels for Text Classification using Wikipedia. KDD 08Xuan-Hieu Phan,Le-Minh 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谢谢！