文本分類綜述王斌

《文本分類綜述王斌》由會員分享，可在線閱讀，更多相關(guān)《文本分類綜述王斌（38頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,*,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,文本分類綜述,王 斌,中國科學(xué)院計算技術(shù)研究所,2013,年,10,月,報告內(nèi)容,文本分類的定義和應(yīng)用,文本分類的方法,文本分類的評估指標(biāo),參考文獻(xiàn)和資源,文本分類的定義和應(yīng)用,定義,給定分類體系，將文本分到某個或者某幾個類別中。,分類體系一般人工構(gòu)造,政治、體育、軍事,中美關(guān)系、恐怖事件,分類系統(tǒng)可以是層次結(jié)構(gòu)，如,yahoo!,分類模式,2,類問題，屬于或不屬于,(binary),多類問題，多個類別,(multi-

2、class),，可拆分成,2,類問題,一個文本可以屬于多類,(multi-label),這里講的分類主要基于內(nèi)容,很多分類體系,:Reuters,分類體系、中圖分類,應(yīng)用,垃圾郵件的判定,(spam or not spam),類別,spam,not-spam,新聞出版按照欄目分類,類別,政治,體育,軍事,詞性標(biāo)注,類別,名詞,動詞,形容詞,詞義排歧,類別,詞義,1,詞義,2,計算機(jī)論文的領(lǐng)域,類別,ACM system,H:information systems,H.3:information retrieval and storage,文本分類的方法,人工方法和自動方法,人工方法,結(jié)果容易理

3、解,足球,and,聯(lián)賽,體育類,費(fèi)時費(fèi)力,難以保證一致性和準(zhǔn)確性,(40%,左右的準(zhǔn)確率,),專家有時候憑空想象,知識工程的方法建立專家系統(tǒng),(80,年代末期,),自動的方法,(,學(xué)習(xí),),結(jié)果可能不易理解,快速,準(zhǔn)確率相對高,(,準(zhǔn)確率可達(dá),60%,或者更高,),來源于真實文本，可信度高,文本分類的過程,文本表示,訓(xùn)練過程,分類過程,訓(xùn)練文本,統(tǒng)計,統(tǒng)計量,特征表示,學(xué)習(xí),分類器,新文本,特征表示,類別,特征抽取,(feature extraction),預(yù)處理,去掉,html,一些,tag,標(biāo)記,禁用詞,(stop words),去除、詞根還原,(stemming),(,中文,),分詞、詞

4、性標(biāo)注、短語識別、,詞頻統(tǒng)計,TF,i,j,:,特征,i,在文檔,j,中出現(xiàn)次數(shù)，詞頻,(Term Frequency),DF,i,:,所有文檔集合中出現(xiàn)特征,i,的文檔數(shù)目，文檔頻率,(Document Frequency),數(shù)據(jù)清洗：去掉不合適的噪聲文檔或文檔內(nèi)垃圾數(shù)據(jù),文本表示,向量空間模型,降維技術(shù),特征選擇,(Feature Selection),特征重構(gòu),(Re-parameterisation,，如,LSI),文本表示,向量空間模型,(Vector Space Model),M,個無序標(biāo)引項,t,i,(,特征,),，詞根,/,詞,/,短語,/,其他,每個文檔,d,j,可以用標(biāo)引項

5、向量來表示,(a,1j,a,2j,a,Mj,),權(quán)重計算，,N,個訓(xùn)練文檔,A,M*N,=(a,ij,),相似度比較,Cosine,計算,內(nèi)積計算,Term,的粒度,Character,，字：中,Word,，詞：中國,Phrase,，短語：中國人民銀行,Concept,，概念,同義詞：開心 高興 興奮,相關(guān)詞,cluster,，,word cluster,：葛非,/,顧俊,N-gram,，,N,元組：中國 國人 人民 民銀 銀行,某種規(guī)律性模式：比如某個,window,中出現(xiàn)的固定模式,David Lewis,等一致地認(rèn)為,：,(,英文分類中,),使用優(yōu)化合并后的,Words,比較合適,權(quán)重計

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

7、沒有區(qū)分度,),信息增益,(Information Gain,IG),：該,term,為整個分類所能提供的信息量,(,不考慮任何特征的熵,和,考慮該特征后的熵,的差值,),特征選擇,(2),term,的某種熵：該值越大，說明分布越均勻，越有可能出現(xiàn)在較多的類別中；該值越小，說明分布越傾斜，詞可能出現(xiàn)在較少的類別中,相對熵,(not,交叉熵,),：也稱為,KL,距離,(Kullback-Leibler divergence),，反映了文本類別的概率分布和在出現(xiàn)了某個特定詞匯條件下的文本類別的概率分布之間的距離，該值越大，詞對文本類別分布的影響也大。,特征選擇,(3),2,統(tǒng)計量,(,念,xi),

8、：度量兩者,(term,和類別,),獨(dú)立性的缺乏程度，,2,越大，獨(dú)立性越小，相關(guān)性越大,(,若,ADBC,則類和詞獨(dú)立,N=A+B+C+D),互信息,(Mutual Information),：,MI,越大,t,和,c,共現(xiàn)程度越大,A,B,C,D,t,t,c,c,特征選擇,(4),Robertson&Sparck Jones,公式,其他,Odds:,Term Strength:,特征選擇方法的性能比較,(1),特征選擇方法的性能比較,(2),特征選擇方法的性能比較,(3),YangYi-ming,特征重構(gòu),隱性語義索引,(LSI),奇異值分解,(SVD),：,A=(a,ij,)=U,V,T

9、,A,M*N,U,M*R,R*R,(,對角陣,),V,N*R,R=MIN(M,N),取,對角上的前,k,個元素，得,k,A,k,=,U,k,k,V,k,T,U,k,由,U,的前,k,列組成，,V,k,由,V,的前,k,列組成,文檔,d,在,LSI,對應(yīng)的向量,d=d,T,U,k,-1,在已有的,LSI,中增加新的,word,或者,document,，不需要重新計算,Folding-in,方法,SVD-updating,方法,自動文本分類方法,Rocchio,方法,Nave Bayes,kNN,方法,決策樹方法,decision tree,Decision Rule Classifier,The

10、 Widrow-Hoff Classifier,神經(jīng)網(wǎng)絡(luò)方法,Neural Networks,支持向量機(jī),SVM,基于投票的方法,(voting method),Rocchio,方法,可以認(rèn)為類中心向量法是它的特例,Rocchio,公式,分類,類,C,中心向量的權(quán)重,訓(xùn)練樣本中正例個數(shù),文檔向量的權(quán)重,Nave 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)造決策樹,

11、CART,C4.5(,由,ID3,發(fā)展而來,),CHAID,決策樹的剪枝,(pruning),Decision Rule Learning,wheat&form,WHEAT,wheat&commodity WHEAT,bushels&export WHEAT,wheat&agriculture WHEAT,wheat&tonnes WHEAT,wheat&winter&soft WHEAT,(,粗糙集,)RoughSet,邏輯表達(dá)式,(AQ11,算法,),學(xué)習(xí)到如下規(guī)則,The Widrow-Hoff Classifier,Online Learning,類,c,向量的第,j,個分量,x,i,

12、的第,j,個分量,Learning Rate,Target Value(0 or 1),Neural Network,.,.,.,.,.,c,1,c,2,c,n,Input Layer,Hidden Layer,Output Layer,Backpropagation,支持向量機(jī),Support Vector Machine,Support Vector,Optimal,Separating,Hyperplane,基于投票的方法,Bagging,方法,訓(xùn)練,R,個分類器,f,i,，分類器之間其他相同就是參數(shù)不同。其中,f,i,是通過從訓(xùn)練集合中,(N,篇文檔,),隨機(jī)取,(,取后放回,)N,次

13、文檔構(gòu)成的訓(xùn)練集合訓(xùn)練得到的。,對于新文檔,d,，用這,R,個分類器去分類，得到的最多的那個類別作為,d,的最終類別,Boosting,方法,類似,Bagging,方法，但是訓(xùn)練是串行進(jìn)行的，第,k,個分類器訓(xùn)練時關(guān)注對前,k-1,分類器中錯分的文檔，即不是隨機(jī)取，而是加大取這些文檔的概率,AdaBoost,AdaBoost MH,文本分類的評估指標(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+c)/(a+b

14、+c+d)=1-accuracy,miss rate=1-recall,F=(,2,+1)p.r/(,2,p+r),Break Even Point,BEP,p=r,的點(diǎn),如果多類排序輸出，采用,interpolated 11 point average precision,所有類：,宏平均,:,對每個類求值，然后平均,微平均,:,將所有文檔一塊兒計算，求值,真正對的,錯誤,標(biāo),YES,a,b,標(biāo),NO,c,d,效果評估方法,N,交叉測試：,將訓(xùn)練集合分成,N,份，其中,N-1,份作為訓(xùn)練集，其余,1,份作為測試集。循環(huán),N,次，將,N,次的結(jié)果平均。,開放測試,訓(xùn)練在某個集合中進(jìn)行，而測試集

15、采用另外事先未知的集合。,其他分類方法,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 Baggin

16、g(1997)*,Hierarchical Language Modeling(1998),First-Order-Logic Rule Induction(1999),Maximum Entropy(1999),Hidden Markov Models(1999),Error-Correcting Output Coding(1999),.,小結(jié),訓(xùn)練,對訓(xùn)練文檔進(jìn)行處理，得到每篇文檔的原始空間表示,采用特征選擇方法,(DF/IG/MI,等,),選擇好的特征，將原始空間轉(zhuǎn)換到特征空間,采用某個分類器進(jìn)行學(xué)習(xí)，得到分類器的參數(shù),分類,/,測試,對新文本進(jìn)行相同的特征表示過程,輸入上述分類器得到分類結(jié)果,采用,N,交叉測試或者其他方式得到分類器的效果,參考文獻(xiàn),文獻(xiàn)及其他資源,Papers,K.Aas and L.Eikvil.,Text categorisation:A survey,.Technical report,Norwegian Computing Center,June 1999,Xiaomeng Su,，“,Text categorization”,，,Lesson Pr