文本分類綜述

1、文本分類綜述,鄭亞斌清華大學(xué)自然語言處理組2008-11-15,部分內(nèi)容copy自王斌老師ppt,報告內(nèi)容,文本分類的定義和應(yīng)用文本分類的方法文本分類的評估指標(biāo)文本分類的一些新方向參考文獻(xiàn)和資源,文本分類的定義和應(yīng)用,,定義,給定分類體系，將文本分到某個或者某幾個類別中。分類體系一般人工構(gòu)造政治、體育、軍事中美關(guān)系、恐怖事件分類系統(tǒng)可以是層次結(jié)構(gòu)，如yahoo!分類模式2類問題，屬于或不屬于(binary)多類

2、問題，多個類別(multi-class)，可拆分成2類問題一個文本可以屬于多類(multi-label)這里講的分類主要基于內(nèi)容很多分類體系: Reuters分類體系、中圖分類,應(yīng)用,垃圾郵件的判定(spam or not spam)類別 {spam, not-spam}新聞出版按照欄目分類類別 {政治,體育,軍事,…}詞性標(biāo)注類別 {名詞,動詞,形容詞,…}詞義排歧類別 {詞義1,詞義2,…}計算機論文的領(lǐng)域類

3、別 ACM systemH: information systemsH.3: information retrieval and storage,文本分類的方法,,人工方法和自動方法,人工方法結(jié)果容易理解足球 and 聯(lián)賽?體育類費時費力難以保證一致性和準(zhǔn)確性(40%左右的準(zhǔn)確率)專家有時候憑空想象知識工程的方法建立專家系統(tǒng)(80年代末期)自動的方法(學(xué)習(xí))結(jié)果可能不易理解快速準(zhǔn)確率相對高(準(zhǔn)確率可達(dá)60%或者更

4、高)來源于真實文本，可信度高,文本分類的過程,特征抽取,預(yù)處理去掉html一些tag標(biāo)記(英文)禁用詞(stop words)去除、詞根還原(stemming)(中文)分詞、詞性標(biāo)注、短語識別、…詞頻統(tǒng)計TFi,j: 特征i在文檔j中出現(xiàn)次數(shù)，詞頻(Term Frequency)DFi:所有文檔集合中出現(xiàn)特征i的文檔數(shù)目，文檔頻率(Document Frequency)數(shù)據(jù)清洗：去掉不合適的噪聲文檔或文檔內(nèi)垃圾數(shù)據(jù)文本

5、表示向量空間模型(Vector Space Model)降維技術(shù)特征選擇(Feature Selection)特征重構(gòu)(Re-parameterisation，如LSI、LDA),文本表示,向量空間模型(Vector Space Model)M個無序標(biāo)引項ti (特征)，詞根/詞/短語/其他假設(shè)所有特征獨立每個文檔dj可以用標(biāo)引項向量來表示(a1j,a2j,…,aMj)權(quán)重計算，N個訓(xùn)練文檔AM*N= (aij)相

6、似度比較Cosine計算內(nèi)積計算,Term的粒度,Character，字：中Word，詞：中國Phrase，短語：中國人民銀行Concept，概念同義詞：開心 高興 興奮相關(guān)詞cluster，word cluster：鳥巢/水立方/奧運N-gram，N元組：中國 國人 人民 民銀 銀行某種規(guī)律性模式：比如某個窗口中出現(xiàn)的固定模式中文文本分類使用那種粒度？,Term粒度—中文,詞特征 V.S. Bigram特征中文分

7、詞？更困難的學(xué)術(shù)問題Bigram？簡單粗暴假設(shè)分詞100%準(zhǔn)確在低維度達(dá)到更好的結(jié)果現(xiàn)實中不可能的?,Term粒度—中文,ICTCLAS分詞V.S. Bigram低維度：詞 > Bigram高維度 ：Bigram > 詞詞的數(shù)目有限Bigram特征數(shù)目更多，可以提供更多的特征So, 實用性角度：分詞研究角度：Bigram,權(quán)重計算方法,布爾權(quán)重(Boolean weighting)aij=1(T

8、Fij>0) or (TFij=0)0TFIDF型權(quán)重TF: aij=TFijTF*IDF: aij=TFij*log(N/DFi)TFC: 對上面進(jìn)行歸一化LTC: 降低TF的作用基于熵概念的權(quán)重(Entropy weighting)稱為term i的某種熵如果term分布極度均勻：熵等于-1只在一個文檔中出現(xiàn)：熵等于0,,,特征選擇(1),基于DF Term的DF小于某個閾值去掉(太少，沒有代表性)Ter

9、m的DF大于某個閾值也去掉(太多，沒有區(qū)分度) 信息增益(Information Gain, IG)：該term為整個分類所能提供的信息量(不考慮任何特征的熵和考慮該特征后的熵的差值),特征選擇(2),term的某種熵：該值越大，說明分布越均勻，越有可能出現(xiàn)在較多的類別中(區(qū)分度差)；該值越小，說明分布越傾斜，詞可能出現(xiàn)在較少的類別中(區(qū)分度好)相對熵(not 交叉熵)：也稱為KL距離(Kullback-Leibler dive

10、rgence) ，反映了文本類別的概率分布和在出現(xiàn)了某個特定詞匯條件下的文本類別的概率分布之間的距離，該值越大，詞對文本類別分布的影響也大。,特征選擇(3),χ2 統(tǒng)計量：度量兩者(term和類別)獨立性的缺乏程度， χ2 越大，獨立性越小，相關(guān)性越大(若AD<BC,則類和詞獨立, N=A+B+C+D)互信息(Mutual Information)：MI越大t和c共現(xiàn)程度越大,特征選擇(4),Robertson &am

11、p; Sparck Jones公式其他Odds: Term Strength:,特征選擇方法性能比較,特征選擇方法性能比較,Yiming Yang and Xin Liu. 1999. “A re-examination of text categorization methods.” 22ndAnnual International SIGIR’99,特征重構(gòu),隱性語義索引(Latent Semantic Index)

12、奇異值分解(SVD)：A=(aij)=UΣVTAM*N, UM*R, ΣR*R(對角陣), VN*R, R Topic表示,自動文本分類方法,Rocchio方法Naïve BayeskNN方法決策樹方法decision treeDecision Rule ClassifierThe Widrow-Hoff Classifier神經(jīng)網(wǎng)絡(luò)方法Neural Networks支持向量機SVM基于投票的方法(votin

13、g method),Rocchio方法,可以認(rèn)為類中心向量法是它的特例Rocchio公式分類,Naïve Bayes,參數(shù)計算,Bayes公式,kNN方法,一種Lazy Learning, Example-based Learning,,,,,,,,,,,,,,,,,,新文本,,k=1, A類,,,k=4，B類,,k=10，B類,,,,,,,,,帶權(quán)重計算，計算權(quán)重和最大的類。k常取3或者5。,決策樹方法,構(gòu)造決策

14、樹CARTC4.5 (由ID3發(fā)展而來)CHAID決策樹的剪枝(pruning),Decision Rule Learning,wheat & form ? WHEATwheat & commodity ? WHEATbushels & export ? WHEATwheat & agriculture ? WHEATwheat & tonnes ? WHEATwheat &a

15、mp; winter & ~soft ? WHEAT,(粗糙集)RoughSet 邏輯表達(dá)式(AQ11算法),學(xué)習(xí)到如下規(guī)則,The Widrow-Hoff Classifier,Online Learning,Neural Network,,,,,,.,.,.,.,.,,,,,,,c1,c2,cn,,,……,Input Layer,Hidden Layer,Output Layer,Backpropagation,支持向量機

16、Support Vector Machine,Support Vector,,,,Optimal Separating Hyperplane,,基于投票的方法,Bagging方法訓(xùn)練R個分類器fi，分類器之間其他相同就是參數(shù)不同。其中fi是通過從訓(xùn)練集合中(N篇文檔)隨機取(取后放回)N次文檔構(gòu)成的訓(xùn)練集合訓(xùn)練得到的。對于新文檔d，用這R個分類器去分類，得到的最多的那個類別作為d的最終類別Boosting方法類似Baggi

17、ng方法，但是訓(xùn)練是串行進(jìn)行的，第k個分類器訓(xùn)練時關(guān)注對前k-1分類器中錯分的文檔，即不是隨機取，而是加大取這些文檔的概率(加大對錯分樣本的學(xué)習(xí)能力)AdaBoost,文本分類的評估指標(biāo),,分類方法的評估,鄰接表每個類Precision=a/(a+b), Recall=a/(a+c), fallout=b/(b+d)=false alarm rate, accuracy=(a+d)/(a+b+c+d), error=(b+

18、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 Squa

19、res 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) *Suppor

20、t 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)

21、...,Demo Show,,文本分類的一些新方向,,傳統(tǒng)文本分類研究方向,特征選擇權(quán)重計算不平衡數(shù)據(jù)集分類訓(xùn)練集樣本很少(半監(jiān)督學(xué)習(xí))Active-Learning：加入人工的因素基本上文本分類作為檢驗新的機器學(xué)習(xí)方法的平臺,新方向,短文本分類最大的問題：信息缺失Ask Google Snippet代價太高，僅供研究，不實用,,,短文本分類,利用Topic Model補充缺失信息,語義信息補充,現(xiàn)今的文本分類

22、算法未考慮詞的語義信息英文中：短語拆開成了單詞Machine Learning, Statistical Learning, and Data Mining are related subjectsMachine Learning ≠ Machine + Learning,,,Concepts,Terms,開方測試問題,論文中的指標(biāo)都是在封閉訓(xùn)練測試上計算Web上的文本錯綜復(fù)雜，不可能有統(tǒng)一的分類體系在訓(xùn)練集合A上的模型，

23、自適應(yīng)的轉(zhuǎn)移到集合B中的文本分布？Transfer Learning主要問題在于成本較高,其他一些問題,多類別數(shù)目分類問題：比如類別數(shù)有成百上千的情況SVM？訓(xùn)練時一般采用One V.S. One方法如果一定要選，Naïve Bayes方法更魯棒分類速度：實用的角度不可能采用paper中的方法一般在速度和效果中尋求Tradeoff,參考文獻(xiàn),,文獻(xiàn)及其他資源,PapersK. Aas and L. Eikvi

24、l. Text categorisation: A survey. Technical report, Norwegian Computing Center, June 1999 http://citeseer.nj.nec.com/aas99text.htmlXiaomeng Su， “Text categorization”，Lesson PresentationYiming Yang and Xin Liu. 1999. &q

25、uot;A re-examination of text categorization methods." 22ndAnnual International SIGIRA Survey on Text Categorization, NLP Lab, Korean U.龐劍峰，基于向量空間模型的自反饋的文本分類系統(tǒng)的研究與實現(xiàn)，中科院計算所碩士論文，2001 黃萱菁等，獨立于語種的文本分類方法，中文信息學(xué)報，2000年第

26、6期Software:Rainbow http://www-2.cs.cmu.edu/~mccallum/bow/BoosTexter http://www.research.att.com/~schapire/BoosTexter/TiMBL http://ilk.kub.nl/software.html#timbl C4.5 http://www.cs.uregina.ca/~dbd/cs831/notes/ml/dtre

27、es/c4.5/tutorial.htmlCorpushttp://www.cs.cmu.edu/~textlearning Google,文獻(xiàn)及其他資源,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

28、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 Wi

29、kipedia. KDD 08’Xuan-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,

30、Transferring Naive Bayes Classifiers for Text Classification, AAAI 07’C.Do, A. Ng, Transfer Learning for text classification. NIPS’ 05 F. Mourão, L. Rocha, et al., Understanding Temporal Aspects in Document Classi