文本分類綜述課件

文本分類綜述王斌中國科學(xué)院計(jì)算技術(shù)研究所2013年10月文本分類綜述王斌報(bào)告內(nèi)容文本分類的定義和應(yīng)用文本分類的方法文本分類的評估指標(biāo)參考文獻(xiàn)和資源報(bào)告內(nèi)容文本分類的定義和應(yīng)用文本分類的定義和應(yīng)用文本分類的定義和應(yīng)用定義給定分類體系，將文本分到某個(gè)或者某幾個(gè)類別中。分類體系一般人工構(gòu)造政治、體育、軍事中美關(guān)系、恐怖事件分類系統(tǒng)可以是層次結(jié)構(gòu)，如yahoo!分類模式2類問題，屬于或不屬于(binary)多類問題，多個(gè)類別(multi-class)，可拆分成2類問題一個(gè)文本可以屬于多類(multi-label)這里講的分類主要基于內(nèi)容很多分類體系:Reuters分類體系、中圖分類定義給定分類體系，將文本分到某個(gè)或者某幾個(gè)類別中。應(yīng)用垃圾郵件的判定(spamornotspam)類別{spam,not-spam}新聞出版按照欄目分類類別{政治,體育,軍事,…}詞性標(biāo)注類別{名詞,動(dòng)詞,形容詞,…}詞義排歧類別{詞義1,詞義2,…}計(jì)算機(jī)論文的領(lǐng)域類別ACMsystemH:informationsystemsH.3:informationretrievalandstorage應(yīng)用垃圾郵件的判定(spamornotspam)文本分類的方法文本分類的方法人工方法和自動(dòng)方法人工方法結(jié)果容易理解足球and聯(lián)賽體育類費(fèi)時(shí)費(fèi)力難以保證一致性和準(zhǔn)確性(40%左右的準(zhǔn)確率)專家有時(shí)候憑空想象知識(shí)工程的方法建立專家系統(tǒng)(80年代末期)自動(dòng)的方法(學(xué)習(xí))結(jié)果可能不易理解快速準(zhǔn)確率相對高(準(zhǔn)確率可達(dá)60%或者更高)來源于真實(shí)文本，可信度高人工方法和自動(dòng)方法人工方法文本分類的過程文本表示訓(xùn)練過程分類過程訓(xùn)練文本統(tǒng)計(jì)統(tǒng)計(jì)量特征表示學(xué)習(xí)分類器新文本??特征表示類別文本分類的過程文本表示訓(xùn)練過程分類過程訓(xùn)練文本統(tǒng)計(jì)統(tǒng)計(jì)量特征特征抽取(featureextraction)預(yù)處理去掉html一些tag標(biāo)記禁用詞(stopwords)去除、詞根還原(stemming)(中文)分詞、詞性標(biāo)注、短語識(shí)別、…詞頻統(tǒng)計(jì)TFi,j:特征i在文檔j中出現(xiàn)次數(shù)，詞頻(TermFrequency)DFi:所有文檔集合中出現(xiàn)特征i的文檔數(shù)目，文檔頻率(DocumentFrequency)數(shù)據(jù)清洗：去掉不合適的噪聲文檔或文檔內(nèi)垃圾數(shù)據(jù)文本表示向量空間模型降維技術(shù)特征選擇(FeatureSelection)特征重構(gòu)(Re-parameterisation，如LSI)特征抽取(featureextraction)預(yù)處理文本表示向量空間模型(VectorSpaceModel)M個(gè)無序標(biāo)引項(xiàng)ti(特征)，詞根/詞/短語/其他每個(gè)文檔dj可以用標(biāo)引項(xiàng)向量來表示(a1j,a2j,…,aMj)權(quán)重計(jì)算，N個(gè)訓(xùn)練文檔AM*N=(aij)相似度比較Cosine計(jì)算內(nèi)積計(jì)算文本表示向量空間模型(VectorSpaceModel)Term的粒度Character，字：中Word，詞：中國Phrase，短語：中國人民銀行Concept，概念同義詞：開心高興興奮相關(guān)詞cluster，wordcluster：葛非/顧俊N-gram，N元組：中國國人人民民銀銀行某種規(guī)律性模式：比如某個(gè)window中出現(xiàn)的固定模式DavidLewis等一致地認(rèn)為：(英文分類中)使用優(yōu)化合并后的

Words比較合適Term的粒度Character，字：中權(quán)重計(jì)算方法布爾權(quán)重(booleanweighting)aij=1(TFij>0)or(TFij=0)0TFIDF型權(quán)重TF:aij=TFijTF*IDF:aij=TFij*log(N/DFi)TFC:對上面進(jìn)行歸一化LTC:降低TF的作用基于熵概念的權(quán)重(Entropyweighting)稱為termi的某種熵如果term分布極度均勻：熵等于-1只在一個(gè)文檔中出現(xiàn)：熵等于0權(quán)重計(jì)算方法布爾權(quán)重(booleanweighting)特征選擇(1)基于DFTerm的DF小于某個(gè)閾值去掉(太少，沒有代表性)Term的DF大于某個(gè)閾值也去掉(太多，沒有區(qū)分度)

信息增益(InformationGain,IG)：該term為整個(gè)分類所能提供的信息量(不考慮任何特征的熵和考慮該特征后的熵的差值)特征選擇(1)基于DF特征選擇(2)term的某種熵：該值越大，說明分布越均勻，越有可能出現(xiàn)在較多的類別中；該值越小，說明分布越傾斜，詞可能出現(xiàn)在較少的類別中相對熵(not交叉熵)：也稱為KL距離(Kullback-Leiblerdivergence)

，反映了文本類別的概率分布和在出現(xiàn)了某個(gè)特定詞匯條件下的文本類別的概率分布之間的距離，該值越大，詞對文本類別分布的影響也大。特征選擇(2)term的某種熵：該值越大，說明分布越均勻，越特征選擇(3)χ2統(tǒng)計(jì)量(念xi)：度量兩者(term和類別)獨(dú)立性的缺乏程度，χ2越大，獨(dú)立性越小，相關(guān)性越大(若AD<BC,則類和詞獨(dú)立,N=A+B+C+D)互信息(MutualInformation)：MI越大t和c共現(xiàn)程度越大ABCDt~tc~c特征選擇(3)χ2統(tǒng)計(jì)量(念xi)：度量兩者(term和類特征選擇(4)Robertson&SparckJones公式其他Odds:TermStrength:特征選擇(4)Robertson&SparckJone特征選擇方法的性能比較(1)特征選擇方法的性能比較(1)特征選擇方法的性能比較(2)特征選擇方法的性能比較(2)特征選擇方法的性能比較(3)YangYi-ming特征選擇方法的性能比較(3)YangYi-ming特征重構(gòu)隱性語義索引(LSI)奇異值分解(SVD)：A=(aij)=UΣVTAM*N,UM*R,ΣR*R(對角陣),VN*R,

R<=MIN(M,N)取Σ對角上的前k個(gè)元素，得ΣkAk=

UkΣkVkT,Uk由U的前k列組成，Vk由V的前k列組成文檔d在LSI對應(yīng)的向量d’=dTUkΣ-1在已有的LSI中增加新的word或者document，不需要重新計(jì)算Folding-in方法SVD-updating方法特征重構(gòu)隱性語義索引(LSI)自動(dòng)文本分類方法Rocchio方法Na?veBayeskNN方法決策樹方法decisiontreeDecisionRuleClassifierTheWidrow-HoffClassifier神經(jīng)網(wǎng)絡(luò)方法NeuralNetworks支持向量機(jī)SVM基于投票的方法(votingmethod)自動(dòng)文本分類方法Rocchio方法Rocchio方法可以認(rèn)為類中心向量法是它的特例Rocchio公式分類類C中心向量的權(quán)重訓(xùn)練樣本中正例個(gè)數(shù)文檔向量的權(quán)重Rocchio方法可以認(rèn)為類中心向量法是它的特例類C中心向量Na?veBayes參數(shù)計(jì)算Bayes公式Na?veBayes參數(shù)計(jì)算Bayes公式kNN方法一種LazyLearning,Example-basedLearning新文本k=1,A類k=4，B類k=10，B類帶權(quán)重計(jì)算，計(jì)算權(quán)重和最大的類。k常取3或者5。kNN方法一種LazyLearning,Example-決策樹方法構(gòu)造決策樹CARTC4.5(由ID3發(fā)展而來)CHAID決策樹的剪枝(pruning)決策樹方法構(gòu)造決策樹DecisionRuleLearningwheat&formWHEATwheat&commodityWHEATbushels&exportWHEATwheat&agricultureWHEATwheat&tonnesWHEATwheat&winter&~softWHEAT(粗糙集)RoughSet邏輯表達(dá)式(AQ11算法)學(xué)習(xí)到如下規(guī)則DecisionRuleLearningwheat&TheWidrow-HoffClassifierOnlineLearning類c向量的第j個(gè)分量xi的第j個(gè)分量LearningRateTargetValue(0or1)TheWidrow-HoffClassifierOnliNeuralNetwork.....c1c2cn……InputLayerHiddenLayerOutputLayerBackpropagationNeuralNetwork.....c1c2cn……Inp支持向量機(jī)

SupportVectorMachineSupportVectorOptimalSeparatingHyperplane支持向量機(jī)

SupportVectorMachineSu基于投票的方法Bagging方法訓(xùn)練R個(gè)分類器fi，分類器之間其他相同就是參數(shù)不同。其中fi是通過從訓(xùn)練集合中(N篇文檔)隨機(jī)取(取后放回)N次文檔構(gòu)成的訓(xùn)練集合訓(xùn)練得到的。對于新文檔d，用這R個(gè)分類器去分類，得到的最多的那個(gè)類別作為d的最終類別Boosting方法類似Bagging方法，但是訓(xùn)練是串行進(jìn)行的，第k個(gè)分類器訓(xùn)練時(shí)關(guān)注對前k-1分類器中錯(cuò)分的文檔，即不是隨機(jī)取，而是加大取這些文檔的概率AdaBoostAdaBoostMH基于投票的方法Bagging方法文本分類的評估指標(biāo)文本分類的評估指標(biāo)分類方法的評估鄰接表每個(gè)類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的點(diǎn)如果多類排序輸出，采用interpolated11pointaverageprecision所有類：宏平均:對每個(gè)類求值，然后平均微平均:將所有文檔一塊兒計(jì)算，求值真正對的錯(cuò)誤標(biāo)YESab標(biāo)NOcd分類方法的評估鄰接表真正對的錯(cuò)誤標(biāo)YESab標(biāo)NOcd效果評估方法N交叉測試：將訓(xùn)練集合分成N份，其中N-1份作為訓(xùn)練集，其余1份作為測試集。循環(huán)N次，將N次的結(jié)果平均。開放測試訓(xùn)練在某個(gè)集合中進(jì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小結(jié)訓(xùn)練對訓(xùn)練文檔進(jìn)行處理，得到每篇文檔的原始空間表示采用特征選擇方法(DF/IG/MI等)選擇好的特征，將原始空間轉(zhuǎn)換到特征空間采用某個(gè)分類器進(jìn)行學(xué)習(xí)，得到分類器的參數(shù)分類/測試對新文本進(jìn)行相同的特征表示過程輸入上述分類器得到分類結(jié)果采用N交叉測試或者其他方式得到分類器的效果小結(jié)訓(xùn)練參考文獻(xiàn)參考文獻(xiàn)文獻(xiàn)及其他資源PapersK.AasandL.Eikvil.Textcategorisation:Asurvey.Technicalreport,NorwegianComputingCenter,June1999/aas99text.htmlXiaomengSu，“Textcategorization”，LessonPresentationYimingYangandXinLiu.1999."Are-examinationoftextcategorizationmethods."22ndAnnualInternationalSIGIR/~yiming/publications.htmlASurveyonTextCategorization,NLPLab,KoreanU.龐劍峰，基于向量空間模型的自反饋的文本分類系統(tǒng)的研究與實(shí)現(xiàn)，中科院計(jì)算所碩士論文，2001

黃萱菁等，獨(dú)立于語種的文本分類方法，中文信息學(xué)報(bào)，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文獻(xiàn)及其他資源Papers謝謝！Wangbin@/~wangbin謝謝！Wangbin@文本分類綜述王斌中國科學(xué)院計(jì)算技術(shù)研究所2013年10月文本分類綜述王斌報(bào)告內(nèi)容文本分類的定義和應(yīng)用文本分類的方法文本分類的評估指標(biāo)參考文獻(xiàn)和資源報(bào)告內(nèi)容文本分類的定義和應(yīng)用文本分類的定義和應(yīng)用文本分類的定義和應(yīng)用定義給定分類體系，將文本分到某個(gè)或者某幾個(gè)類別中。分類體系一般人工構(gòu)造政治、體育、軍事中美關(guān)系、恐怖事件分類系統(tǒng)可以是層次結(jié)構(gòu)，如yahoo!分類模式2類問題，屬于或不屬于(binary)多類問題，多個(gè)類別(multi-class)，可拆分成2類問題一個(gè)文本可以屬于多類(multi-label)這里講的分類主要基于內(nèi)容很多分類體系:Reuters分類體系、中圖分類定義給定分類體系，將文本分到某個(gè)或者某幾個(gè)類別中。應(yīng)用垃圾郵件的判定(spamornotspam)類別{spam,not-spam}新聞出版按照欄目分類類別{政治,體育,軍事,…}詞性標(biāo)注類別{名詞,動(dòng)詞,形容詞,…}詞義排歧類別{詞義1,詞義2,…}計(jì)算機(jī)論文的領(lǐng)域類別ACMsystemH:informationsystemsH.3:informationretrievalandstorage應(yīng)用垃圾郵件的判定(spamornotspam)文本分類的方法文本分類的方法人工方法和自動(dòng)方法人工方法結(jié)果容易理解足球and聯(lián)賽體育類費(fèi)時(shí)費(fèi)力難以保證一致性和準(zhǔn)確性(40%左右的準(zhǔn)確率)專家有時(shí)候憑空想象知識(shí)工程的方法建立專家系統(tǒng)(80年代末期)自動(dòng)的方法(學(xué)習(xí))結(jié)果可能不易理解快速準(zhǔn)確率相對高(準(zhǔn)確率可達(dá)60%或者更高)來源于真實(shí)文本，可信度高人工方法和自動(dòng)方法人工方法文本分類的過程文本表示訓(xùn)練過程分類過程訓(xùn)練文本統(tǒng)計(jì)統(tǒng)計(jì)量特征表示學(xué)習(xí)分類器新文本??特征表示類別文本分類的過程文本表示訓(xùn)練過程分類過程訓(xùn)練文本統(tǒng)計(jì)統(tǒng)計(jì)量特征特征抽取(featureextraction)預(yù)處理去掉html一些tag標(biāo)記禁用詞(stopwords)去除、詞根還原(stemming)(中文)分詞、詞性標(biāo)注、短語識(shí)別、…詞頻統(tǒng)計(jì)TFi,j:特征i在文檔j中出現(xiàn)次數(shù)，詞頻(TermFrequency)DFi:所有文檔集合中出現(xiàn)特征i的文檔數(shù)目，文檔頻率(DocumentFrequency)數(shù)據(jù)清洗：去掉不合適的噪聲文檔或文檔內(nèi)垃圾數(shù)據(jù)文本表示向量空間模型降維技術(shù)特征選擇(FeatureSelection)特征重構(gòu)(Re-parameterisation，如LSI)特征抽取(featureextraction)預(yù)處理文本表示向量空間模型(VectorSpaceModel)M個(gè)無序標(biāo)引項(xiàng)ti(特征)，詞根/詞/短語/其他每個(gè)文檔dj可以用標(biāo)引項(xiàng)向量來表示(a1j,a2j,…,aMj)權(quán)重計(jì)算，N個(gè)訓(xùn)練文檔AM*N=(aij)相似度比較Cosine計(jì)算內(nèi)積計(jì)算文本表示向量空間模型(VectorSpaceModel)Term的粒度Character，字：中Word，詞：中國Phrase，短語：中國人民銀行Concept，概念同義詞：開心高興興奮相關(guān)詞cluster，wordcluster：葛非/顧俊N-gram，N元組：中國國人人民民銀銀行某種規(guī)律性模式：比如某個(gè)window中出現(xiàn)的固定模式DavidLewis等一致地認(rèn)為：(英文分類中)使用優(yōu)化合并后的

Words比較合適Term的粒度Character，字：中權(quán)重計(jì)算方法布爾權(quán)重(booleanweighting)aij=1(TFij>0)or(TFij=0)0TFIDF型權(quán)重TF:aij=TFijTF*IDF:aij=TFij*log(N/DFi)TFC:對上面進(jìn)行歸一化LTC:降低TF的作用基于熵概念的權(quán)重(Entropyweighting)稱為termi的某種熵如果term分布極度均勻：熵等于-1只在一個(gè)文檔中出現(xiàn)：熵等于0權(quán)重計(jì)算方法布爾權(quán)重(booleanweighting)特征選擇(1)基于DFTerm的DF小于某個(gè)閾值去掉(太少，沒有代表性)Term的DF大于某個(gè)閾值也去掉(太多，沒有區(qū)分度)

信息增益(InformationGain,IG)：該term為整個(gè)分類所能提供的信息量(不考慮任何特征的熵和考慮該特征后的熵的差值)特征選擇(1)基于DF特征選擇(2)term的某種熵：該值越大，說明分布越均勻，越有可能出現(xiàn)在較多的類別中；該值越小，說明分布越傾斜，詞可能出現(xiàn)在較少的類別中相對熵(not交叉熵)：也稱為KL距離(Kullback-Leiblerdivergence)

，反映了文本類別的概率分布和在出現(xiàn)了某個(gè)特定詞匯條件下的文本類別的概率分布之間的距離，該值越大，詞對文本類別分布的影響也大。特征選擇(2)term的某種熵：該值越大，說明分布越均勻，越特征選擇(3)χ2統(tǒng)計(jì)量(念xi)：度量兩者(term和類別)獨(dú)立性的缺乏程度，χ2越大，獨(dú)立性越小，相關(guān)性越大(若AD<BC,則類和詞獨(dú)立,N=A+B+C+D)互信息(MutualInformation)：MI越大t和c共現(xiàn)程度越大ABCDt~tc~c特征選擇(3)χ2統(tǒng)計(jì)量(念xi)：度量兩者(term和類特征選擇(4)Robertson&SparckJones公式其他Odds:TermStrength:特征選擇(4)Robertson&SparckJone特征選擇方法的性能比較(1)特征選擇方法的性能比較(1)特征選擇方法的性能比較(2)特征選擇方法的性能比較(2)特征選擇方法的性能比較(3)YangYi-ming特征選擇方法的性能比較(3)YangYi-ming特征重構(gòu)隱性語義索引(LSI)奇異值分解(SVD)：A=(aij)=UΣVTAM*N,UM*R,ΣR*R(對角陣),VN*R,

R<=MIN(M,N)取Σ對角上的前k個(gè)元素，得ΣkAk=

UkΣkVkT,Uk由U的前k列組成，Vk由V的前k列組成文檔d在LSI對應(yīng)的向量d’=dTUkΣ-1在已有的LSI中增加新的word或者document，不需要重新計(jì)算Folding-in方法SVD-updating方法特征重構(gòu)隱性語義索引(LSI)自動(dòng)文本分類方法Rocchio方法Na?veBayeskNN方法決策樹方法decisiontreeDecisionRuleClassifierTheWidrow-HoffClassifier神經(jīng)網(wǎng)絡(luò)方法NeuralNetworks支持向量機(jī)SVM基于投票的方法(votingmethod)自動(dòng)文本分類方法Rocchio方法Rocchio方法可以認(rèn)為類中心向量法是它的特例Rocchio公式分類類C中心向量的權(quán)重訓(xùn)練樣本中正例個(gè)數(shù)文檔向量的權(quán)重Rocchio方法可以認(rèn)為類中心向量法是它的特例類C中心向量Na?veBayes參數(shù)計(jì)算Bayes公式Na?veBayes參數(shù)計(jì)算Bayes公式kNN方法一種LazyLearning,Example-basedLearning新文本k=1,A類k=4，B類k=10，B類帶權(quán)重計(jì)算，計(jì)算權(quán)重和最大的類。k常取3或者5。kNN方法一種LazyLearning,Example-決策樹方法構(gòu)造決策樹CARTC4.5(由ID3發(fā)展而來)CHAID決策樹的剪枝(pruning)決策樹方法構(gòu)造決策樹DecisionRuleLearningwheat&formWHEATwheat&commodityWHEATbushels&exportWHEATwheat&agricultureWHEATwheat&tonnesWHEATwheat&winter&~softWHEAT(粗糙集)RoughSet邏輯表達(dá)式(AQ11算法)學(xué)習(xí)到如下規(guī)則DecisionRuleLearningwheat&TheWidrow-HoffClassifierOnlineLearning類c向量的第j個(gè)分量xi的第j個(gè)分量LearningRateTargetValue(0or1)TheWidrow-HoffClassifierOnliNeuralNetwork.....c1c2cn……InputLayerHiddenLayerOutputLayerBackpropagationNeuralNetwork.....c1c2cn……Inp支持向量機(jī)

SupportVectorMachineSupportVectorOptimalSeparatingHyperplane支持向量機(jī)

SupportVectorMachineSu基于投票的方法Bagging方法訓(xùn)練R個(gè)分類器fi，分類器之間其他相同就是參數(shù)不同。其中fi是通過從訓(xùn)練集合中(N篇文檔)隨機(jī)取(取后放回)N次文檔構(gòu)成的訓(xùn)練集合訓(xùn)練得到的。對于新文檔d，用這R個(gè)分類器去分類，得到的最多的那個(gè)類別作為d的最終類別Boosting方法類似Bagging方法，但是訓(xùn)練是串行進(jìn)行的，第k個(gè)分類器訓(xùn)練時(shí)關(guān)注對前k-1分類器中錯(cuò)分的文檔，即不是隨機(jī)取，而是加大取這些文檔的概率AdaBoostAdaBoostMH基于投票的方法Bagging方法文本分類的評估指標(biāo)文本分類的評估指標(biāo)分類方法的評估鄰接表每個(gè)類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的點(diǎn)如果多類排序輸出，采用interpolated11pointaverageprecision所有類：宏平均:對每個(gè)類求值，然后平均微平均:將所有文檔一塊兒計(jì)算，求值真正對的錯(cuò)誤標(biāo)YESab標(biāo)NOcd分類方法的評估鄰接表真正對的錯(cuò)誤標(biāo)YESab標(biāo)NOcd效果評估方法N交叉測試：將訓(xùn)練集合分成N份，其中N-1份作為訓(xùn)練集，其余1份作為測試集。循環(huán)N次，將N次的結(jié)果平均。開放測試訓(xùn)練在某個(gè)集合中進(jìn)行，而測試集采用另外事先未知的集合。效果評估方法N交叉測試：其他分類方法RegressionbasedonLeastSquaresFit(1991)NearestNeighborClassification(1992)*BayesianProbabilisticModels(1992)*SymbolicR