文本分類(lèi)綜述

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

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

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

4、高)來(lái)源于真實(shí)文本，可信度高,文本分類(lèi)的過(guò)程,特征抽取,預(yù)處理去掉html一些tag標(biāo)記(英文)禁用詞(stop words)去除、詞根還原(stemming)(中文)分詞、詞性標(biāo)注、短語(yǔ)識(shí)別、…詞頻統(tǒng)計(jì)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個(gè)無(wú)序標(biāo)引項(xiàng)ti (特征)，詞根/詞/短語(yǔ)/其他假設(shè)所有特征獨(dú)立每個(gè)文檔dj可以用標(biāo)引項(xiàng)向量來(lái)表示(a1j,a2j,…,aMj)權(quán)重計(jì)算，N個(gè)訓(xùn)練文檔AM*N= (aij)相

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

7、詞？更困難的學(xué)術(shù)問(wèn)題Bigram？簡(jiǎn)單粗暴假設(shè)分詞100%準(zhǔn)確在低維度達(dá)到更好的結(jié)果現(xiàn)實(shí)中不可能的?,Term粒度—中文,ICTCLAS分詞V.S. Bigram低維度：詞 > Bigram高維度 ：Bigram > 詞詞的數(shù)目有限Bigram特征數(shù)目更多，可以提供更多的特征So, 實(shí)用性角度：分詞研究角度：Bigram,權(quán)重計(jì)算方法,布爾權(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: 對(duì)上面進(jìn)行歸一化LTC: 降低TF的作用基于熵概念的權(quán)重(Entropy weighting)稱為term i的某種熵如果term分布極度均勻：熵等于-1只在一個(gè)文檔中出現(xiàn)：熵等于0,,,特征選擇(1),基于DF Term的DF小于某個(gè)閾值去掉(太少，沒(méi)有代表性)Ter

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

10、rgence) ，反映了文本類(lèi)別的概率分布和在出現(xiàn)了某個(gè)特定詞匯條件下的文本類(lèi)別的概率分布之間的距離，該值越大，詞對(duì)文本類(lèi)別分布的影響也大。,特征選擇(3),χ2 統(tǒng)計(jì)量：度量?jī)烧?term和類(lèi)別)獨(dú)立性的缺乏程度， χ2 越大，獨(dú)立性越小，相關(guān)性越大(若AD<BC,則類(lèi)和詞獨(dú)立, 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),隱性語(yǔ)義索引(Latent Semantic Index)

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

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

14、樹(shù)CARTC4.5 (由ID3發(fā)展而來(lái))CHAID決策樹(shù)的剪枝(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,支持向量機(jī)

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

17、ng方法，但是訓(xùn)練是串行進(jìn)行的，第k個(gè)分類(lèi)器訓(xùn)練時(shí)關(guān)注對(duì)前k-1分類(lèi)器中錯(cuò)分的文檔，即不是隨機(jī)取，而是加大取這些文檔的概率(加大對(duì)錯(cuò)分樣本的學(xué)習(xí)能力)AdaBoost,文本分類(lèi)的評(píng)估指標(biāo),,分類(lèi)方法的評(píng)估,鄰接表每個(gè)類(lèi)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的點(diǎn)如果多類(lèi)排序輸出，采用interpolated 11 point average precision所有類(lèi)：宏平均:對(duì)每個(gè)類(lèi)求值，然后平均微平均:將所有文檔一塊兒計(jì)算，求值,其他分類(lèi)方法,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,,文本分類(lèi)的一些新方向,,傳統(tǒng)文本分類(lèi)研究方向,特征選擇權(quán)重計(jì)算不平衡數(shù)據(jù)集分類(lèi)訓(xùn)練集樣本很少(半監(jiān)督學(xué)習(xí))Active-Learning：加入人工的因素基本上文本分類(lèi)作為檢驗(yàn)新的機(jī)器學(xué)習(xí)方法的平臺(tái),新方向,短文本分類(lèi)最大的問(wèn)題：信息缺失Ask Google Snippet代價(jià)太高，僅供研究，不實(shí)用,,,短文本分類(lèi),利用Topic Model補(bǔ)充缺失信息,語(yǔ)義信息補(bǔ)充,現(xiàn)今的文本分類(lèi)

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

23、自適應(yīng)的轉(zhuǎn)移到集合B中的文本分布？Transfer Learning主要問(wèn)題在于成本較高,其他一些問(wèn)題,多類(lèi)別數(shù)目分類(lèi)問(wèn)題：比如類(lèi)別數(shù)有成百上千的情況SVM？訓(xùn)練時(shí)一般采用One V.S. One方法如果一定要選，Naïve Bayes方法更魯棒分類(lèi)速度：實(shí)用的角度不可能采用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.龐劍峰，基于向量空間模型的自反饋的文本分類(lèi)系統(tǒng)的研究與實(shí)現(xiàn)，中科院計(jì)算所碩士論文，2001 黃萱菁等，獨(dú)立于語(yǔ)種的文本分類(lèi)方法，中文信息學(xué)報(bào)，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