|
原博客地址：http://www./zhenandaci/category/31868.html?Show=All 文本分類入門(一)文本分類問題的定義 文本分類系列文章,，從文本分類問題的定義開始,，主要講解文本分類系統(tǒng)的構(gòu)成，主流的統(tǒng)計學(xué)習(xí)方法以及較為優(yōu)秀的SVM算法及其改進,。 一個文本（以下基本不區(qū)分“文本”和“文檔”兩個詞的含義）分類問題就是將一篇文檔歸入預(yù)先定義的幾個類別中的一個或幾個,，而文本的自動分類則是使用計算機程序來實現(xiàn)這樣的分類,。通俗點說，就好比你拿一篇文章,，問計算機這文章要說的究竟是體育,，經(jīng)濟還是教育，計算機答不上就打它的屁屁（……）,。 注意這個定義當(dāng)中著重強調(diào)的兩個事實,。 第一，用于分類所需要的類別體系是預(yù)先確定的,。例如新浪新聞的分類體系,，Yahoo!網(wǎng)頁導(dǎo)航的分類層次。這種分類層次一旦確定,，在相當(dāng)長的時間內(nèi)都是不可變的,，或者即使要變更，也要付出相當(dāng)大的代價（基本不亞于推倒并重建一個分類系統(tǒng)）,。 第二,，一篇文檔并沒有嚴格規(guī)定只能被分配給一個類別。這與分類這個問題的主觀性有關(guān),，例如找10個人判斷一篇文章所陳述的主題究竟屬于金融,，銀行還是財政政策領(lǐng)域，10個人可能會給出11個不同的答案（聰明的讀者,，您應(yīng)該能看出來并沒有11個答案,，這只是一種修辭方法，笑）,，因此一篇文章很可能被分配到多個類別當(dāng)中,，只不過分給某些類別讓人信服，而有些讓人感覺模棱兩可罷了（說的專業(yè)點,，置信度不一樣）,。 八股是一種寫文章的格式，過去用于科舉,，現(xiàn)在用于科研,，總之，和科學(xué)有點關(guān)系的文章就得八股,，鑒于我正鍛煉自己寫論文的能力,，所以按照標(biāo)準的格式，陳述了文本分類問題的定義之后,，我要說說它的應(yīng)用范圍,。 現(xiàn)在一說到文本分類，大部分人想當(dāng)然的將這個問題簡化為判斷一篇文章說的是什么,，這只是文本分類的一小部分應(yīng)用,，我們可以稱之為“依據(jù)主題的分類”,。實際上，文本分類還可以用于判斷文章的寫作風(fēng)格,，作者態(tài)度（積極？消極,？）,，甚至判斷作者真?zhèn)危ɡ缈纯础都t樓夢》最后二十回到底是不是曹雪芹寫的）?？偠灾?，凡是與文本有關(guān)，與分類有關(guān),，不管從什么角度出發(fā),，依據(jù)的是何特征，都可以叫做文本分類,。 當(dāng)然,，目前真正大量使用文本分類技術(shù)的，仍是依據(jù)文章主題的分類,，而據(jù)此構(gòu)建最多的系統(tǒng),，當(dāng)屬搜索引擎,。內(nèi)里的原因當(dāng)然不言自明,，我只是想給大家提個醒，文本分類還不完全等同于網(wǎng)頁分類,。網(wǎng)頁所包含的信息遠比含于其中的文字（文本）信息多得多,，對一個網(wǎng)頁的分類,，除了考慮文本內(nèi)容的分類以外，鏈入鏈出的鏈接信息,，頁面文件本身的元數(shù)據(jù),，甚至是包含此網(wǎng)頁的網(wǎng)站結(jié)構(gòu)和主題，都能給分類提供莫大的幫助（比如新浪體育專欄里的網(wǎng)頁毫無疑問都是關(guān)于體育的）,，因此說文本分類實際上是網(wǎng)頁分類的一個子集也毫不為過,。當(dāng)然，純粹的文本分類系統(tǒng)與網(wǎng)頁分類也不是一點區(qū)別都沒有,。文本分類有個重要前提：即只能根據(jù)文章的文字內(nèi)容進行分類,，而不應(yīng)借助諸如文件的編碼格式，文章作者,，發(fā)布日期等信息,。而這些信息對網(wǎng)頁來說常常是可用的，有時起到的作用還很巨大,！因此純粹的文本分類系統(tǒng)要想達到相當(dāng)?shù)姆诸愋Ч?，必須在本身的理論基礎(chǔ)和技術(shù)含量上下功夫,。 除了搜索引擎，諸如數(shù)字圖書館,，檔案管理等等要和海量文字信息打交道的系統(tǒng),，都用得上文本分類。另外,，我的碩士論文也用得上（笑）,。 下一章和大家侃侃與文本分類有關(guān)的具體方法概覽，有事您說話,。 文本分類入門(二)文本分類的方法 文本分類問題與其它分類問題沒有本質(zhì)上的區(qū)別,，其方法可以歸結(jié)為根據(jù)待分類數(shù)據(jù)的某些特征來進行匹配，當(dāng)然完全的匹配是不太可能的,，因此必須（根據(jù)某種評價標(biāo)準）選擇最優(yōu)的匹配結(jié)果,，從而完成分類。 因此核心的問題便轉(zhuǎn)化為用哪些特征表示一個文本才能保證有效和快速的分類（注意這兩方面的需求往往是互相矛盾的）,。因此自有文本分類系統(tǒng)的那天起,，就一直是對特征的不同選擇主導(dǎo)著方法派別的不同。 最早的詞匹配法僅僅根據(jù)文檔中是否出現(xiàn)了與類名相同的詞（頂多再加入同義詞的處理）來判斷文檔是否屬于某個類別,。很顯然,，這種過于簡單的方法無法帶來良好的分類效果。 后來興起過一段時間的知識工程的方法則借助于專業(yè)人員的幫助,，為每個類別定義大量的推理規(guī)則,，如果一篇文檔能滿足這些推理規(guī)則，則可以判定屬于該類別,。這里與特定規(guī)則的匹配程度成為了文本的特征,。由于在系統(tǒng)中加入了人為判斷的因素，準確度比詞匹配法大為提高,。但這種方法的缺點仍然明顯,，例如分類的質(zhì)量嚴重依賴于這些規(guī)則的好壞，也就是依賴于制定規(guī)則的“人”的好壞,；再比如制定規(guī)則的人都是專家級別,，人力成本大幅上升常常令人難以承受；而知識工程最致命的弱點是完全不具備可推廣性,，一個針對金融領(lǐng)域構(gòu)建的分類系統(tǒng),，如果要擴充到醫(yī)療或社會保險等相關(guān)領(lǐng)域，則除了完全推倒重來以外沒有其他辦法,，常常造成巨大的知識和資金浪費,。 后來人們意識到，究竟依據(jù)什么特征來判斷文本應(yīng)當(dāng)隸屬的類別這個問題，就連人類自己都不太回答得清楚,，有太多所謂“只可意會,，不能言傳”的東西在里面。人類的判斷大多依據(jù)經(jīng)驗以及直覺,，因此自然而然的會有人想到何讓機器像人類一樣自己來通過對大量同類文檔的觀察來自己總結(jié)經(jīng)驗,，作為今后分類的依據(jù)。 這便是統(tǒng)計學(xué)習(xí)方法的基本思想（也有人把這一大類方法稱為機器學(xué)習(xí),，兩種叫法只是涵蓋范圍大小有些區(qū)別,，均無不妥）。 統(tǒng)計學(xué)習(xí)方法需要一批由人工進行了準確分類的文檔作為學(xué)習(xí)的材料（稱為訓(xùn)練集,，注意由人分類一批文檔比從這些文檔中總結(jié)出準確的規(guī)則成本要低得多），計算機從這些文檔重挖掘出一些能夠有效分類的規(guī)則,，這個過程被形象的稱為訓(xùn)練,，而總結(jié)出的規(guī)則集合常常被稱為分類器。訓(xùn)練完成之后,，需要對計算機從來沒有見過的文檔進行分類時,，便使用這些分類器來進行。 現(xiàn)如今,，統(tǒng)計學(xué)習(xí)方法已經(jīng)成為了文本分類領(lǐng)域絕對的主流,。主要的原因在于其中的很多技術(shù)擁有堅實的理論基礎(chǔ)（相比之下，知識工程方法中專家的主觀因素居多）,，存在明確的評價標(biāo)準,，以及實際表現(xiàn)良好。 下一章就深入統(tǒng)計學(xué)習(xí)方法,，看看這種方法的前提,，相關(guān)理論和具體實現(xiàn)。 文本分類入門(三)統(tǒng)計學(xué)習(xí)方法 前文說到使用統(tǒng)計學(xué)習(xí)方法進行文本分類就是讓計算機自己來觀察由人提供的訓(xùn)練文檔集,，自己總結(jié)出用于判別文檔類別的規(guī)則和依據(jù),。理想的結(jié)果當(dāng)然是讓計算機在理解文章內(nèi)容的基礎(chǔ)上進行這樣的分類，然而遺憾的是,，我們所說的“理解”往往指的是文章的語義甚至是語用信息,，這一類信息極其復(fù)雜，抽象,，而且存在上下文相關(guān)性,，對這類信息如何在計算機中表示都是尚未解決的問題（往大里說，這是一個“知識表示”的問題,，完全可以另寫一系列文章來說了）,，更不要說讓計算機來理解。 利用計算機來解決問題的標(biāo)準思路應(yīng)該是：為這種問題尋找一種計算機可以理解的表示方法，或曰建立一個模型（一個文檔表示模型）,；然后基于這個模型,，選擇各方面滿足要求的算法來解決。用譚浩強的話說,，程序,，就是數(shù)據(jù)+算法。（啥,？你不知道譚浩強是誰,？上過學(xué)么？學(xué)過C么,？這搗什么亂,？） 既然文本的語義和語用信息很難轉(zhuǎn)換成計算機能夠理解的表示形式，接下來順理成章的,，人們開始用文章中所包含的較低級別的詞匯信息來表示文檔,，一試之下，效果居然還不錯,。 統(tǒng)計學(xué)習(xí)方法進行文本分類（以下就簡稱為“統(tǒng)計學(xué)習(xí)方法”,，雖然這個方法也可以應(yīng)用到除文本分類以外的多個領(lǐng)域）的一個重要前提由此產(chǎn)生，那就是認為：文檔的內(nèi)容與其中所包含的詞有著必然的聯(lián)系,，同一類文檔之間總存在多個共同的詞,，而不同類的文檔所包含的詞之間差異很大[1]。 進一步的,，不光是包含哪些詞很重要,，這些詞出現(xiàn)的次數(shù)對分類也很重要。 這一前提使得向量模型（俗稱的VSM,，向量空間模型）成了適合文本分類問題的文檔表示模型,。在這種模型中，一篇文章被看作特征項集合來看,，利用加權(quán)特征項構(gòu)成向量進行文本表示,，利用詞頻信息對文本特征進行加權(quán)。它實現(xiàn)起來比較簡單,，并且分類準確度也高,，能夠滿足一般應(yīng)用的要求。[5] 而實際上,，文本是一種信息載體,，其所攜帶的信息由幾部分組成：如組成元素本身的信息（詞的信息）、組成元素之間順序關(guān)系帶來的信息以及上下文信息（更嚴格的說,，還包括閱讀者本身的背景和理解）[12],。 而VSM這種文檔表示模型，基本上完全忽略了除詞的信息以外所有的部分，這使得它能表達的信息量存在上限[12],，也直接導(dǎo)致了基于這種模型構(gòu)建的文本分類系統(tǒng)（雖然這是目前絕對主流的做法）,，幾乎永遠也不可能達到人類的分類能力。后面我們也會談到,，相比于所謂的分類算法,，對特征的選擇，也就是使用哪些特征來代表一篇文檔,，往往更能影響分類的效果,。 對于擴充文檔表示模型所包含的信息量，人們也做過有益的嘗試,，例如被稱為LSI（Latent Semantic Index潛在語義索引）的方法,，就被實驗證明保留了一定的語義信息（之所以說被實驗證明了，是因為人們還無法在形式上嚴格地證明它確實保留了語義信息,，而且這種語義信息并非以人可以理解的方式被保留下來）,，此為后話。 前文說到（就不能不用這種老舊的說法,？換換新的，比如Previously on "Prison Break",，噢,，不對，是Previously on Text Categorizaiton……）統(tǒng)計學(xué)習(xí)方法其實就是一個兩階段的解決方案,，（1）訓(xùn)練階段,，由計算機來總結(jié)分類的規(guī)則；（2）分類階段,，給計算機一些它從來沒見過的文檔,，讓它分類（分不對就打屁屁）。 下一章就專門說說訓(xùn)練階段的二三事,。 文本分類入門(四)訓(xùn)練Part 1 訓(xùn)練,，顧名思義，就是training（汗,，這解釋）,，簡單的說就是讓計算機從給定的一堆文檔中自己學(xué)習(xí)分類的規(guī)則（如果學(xué)不對的話，還要,，打屁屁,？）。 開始訓(xùn)練之前,，再多說幾句關(guān)于VSM這種文檔表示模型的話,。 舉個例子，假設(shè)說把我正在寫的“文本分類入門”系列文章的第二篇抽出來當(dāng)作一個需要分類的文本，則可以用如下的向量來表示這個文本,，以便于計算機理解和處理,。 w2=（文本，5,，統(tǒng)計學(xué)習(xí),，4，模型,，0,，……） 這個向量表示在w2所代表的文本中，“文本”這個詞出現(xiàn)了5次（這個信息就叫做詞頻）,，“統(tǒng)計學(xué)習(xí)”這個詞出現(xiàn)了4次,，而“模型”這個詞出現(xiàn)了0次，依此類推,，后面的詞沒有列出,。 而系列的第三篇文章可以表示為 w3=（文本，9,，統(tǒng)計學(xué)習(xí),，4，模型,，10,，……） 其含義同上。如果還有更多的文檔需要表示,，我們都可以使用這種方式,。 只通過觀察w2和w3我們就可以看出實際上有更方便的表示文本向量的方法，那就是把所有文檔都要用到的詞從向量中抽離出來,，形成共用的數(shù)據(jù)結(jié)構(gòu)（也可以仍是向量的形式）,，這個數(shù)據(jù)結(jié)構(gòu)就叫做詞典，或者特征項集合,。 例如我們的問題就可以抽離出一個詞典向量 D=（文本,，統(tǒng)計學(xué)習(xí)，模型,，……） 所有的文檔向量均可在參考這個詞典向量的基礎(chǔ)上簡化成諸如 w2=（5,，4，0,，……） w3=（9,，4，10,，……） 的形式,，其含義沒有改變,。 5，4,，10這些數(shù)字分別叫做各個詞在某個文檔中的權(quán)重,，實際上單單使用詞頻作為權(quán)重并不多見，也不十分有用,，更常見的做法是使用地球人都知道的TF/IDF值作為權(quán)重,。（關(guān)于TF/IDF的詳細解釋，Google的吳軍研究員寫了非常通俗易懂的文章,，發(fā)布于Google黑板報,，鏈接地址是http:///2006/06/blog-post_27.html，有興趣不妨一讀）TF/IDF作為一個詞對所屬文檔主題的貢獻程度來說,，是非常重要的度量標(biāo)準,，也是將文檔轉(zhuǎn)化為向量表示過程中的重要一環(huán)。 在這個轉(zhuǎn)化過程中隱含了一個很嚴重的問題,。注意看看詞典向量D,，你覺得它會有多大？或者說,，你覺得它會包含多少個詞,？ 假設(shè)我們的系統(tǒng)僅僅處理漢語文本,，如果不做任何處理，這個詞典向量會包含漢語中所有的詞匯,，我手頭有一本商務(wù)印書館出版的《現(xiàn)代漢語詞典》第5版（2005年5月出版），其中收錄了65，000個詞,，D大致也應(yīng)該有這么大，也就是說，D是一個65,，000維的向量,，而所有的文本向量w2,w3,wn也全都是65,，000維的?。ㄟ@是文本分類這一問題本身的一個特性,，稱為“高維性”）想一想，大部分文章僅僅千余字,，包含的詞至多幾百,，為了表示這樣一個文本,，卻要使用65,，000維的向量,，這是對存儲資源和計算能力多大的浪費呀！（這又是文本分類問題的另一個特性,，稱為“向量稀疏性”,，后面會專門有一章討論這些特性,，并指出解決的方法,，至少是努力的方向） 中國是一個人口眾多而資源稀少的國家,，我們不提倡一味發(fā)展粗放型的經(jīng)濟,，我們所需要的可持續(xù)發(fā)展是指資源消耗少,，生產(chǎn)效率高,，環(huán)境污染少……跑題了…… 這么多的詞匯當(dāng)中，諸如“體育”,，“經(jīng)濟”,，“金融”，“處理器”等等,，都是極其能夠代表文章主題的,，但另外很多詞，像“我們”,，“在”,，“事情”，“里面”等等,，在任何主題的文章中都很常見,，根本無法指望通過這些詞來對文本類別的歸屬作個判斷。這一事實首先引發(fā)了對文本進行被稱為“去停止詞”的預(yù)處理步驟（對英文來說還有詞根還原,，但這些與訓(xùn)練階段無關(guān),，不贅述，會在以后講述中英文文本分類方法區(qū)別的章節(jié)中討論）,，與此同時,，我們也從詞典向量D中把這些詞去掉。 但經(jīng)過停止詞處理后剩下的詞匯仍然太多,，使用了太多的特征來表示文本,，就是常說的特征集過大，不僅耗費計算資源,，也因為會引起“過擬合問題”而影響分類效果[22],。 這個問題是訓(xùn)練階段要解決的第一個問題，即如何選取那些最具代表性的詞匯（更嚴格的說法應(yīng)該是,，那些最具代表性的特征,，為了便于理解，可以把特征暫時當(dāng)成詞匯來想象）,。對這個問題的解決,，有人叫它特征提取，也有人叫它降維,。 特征提取實際上有兩大類方法,。一類稱為特征選擇（Term Selection），指的是從原有的特征（那許多有用無用混在一起的詞匯）中提取出少量的,，具有代表性的特征,，但特征的類型沒有變化（原來是一堆詞，特征提取后仍是一堆詞，數(shù)量大大減少了而已）,。另一類稱為特征抽?。═erm Extraction）的方法則有所不同，它從原有的特征中重構(gòu)出新的特征（原來是一堆詞,，重構(gòu)后變成了別的,，例如LSI將其轉(zhuǎn)為矩陣，文檔生成模型將其轉(zhuǎn)化為某個概率分布的一些參數(shù)）,，新的特征具有更強的代表性,，并耗費更少的計算資源。（特征提取的各種算法會有專門章節(jié)討論） 訓(xùn)練階段,，計算機根據(jù)訓(xùn)練集中的文檔,，使用特征提取找出最具代表性的詞典向量（仍然是不太嚴格的說法），然后參照這個詞典向量把這些訓(xùn)練集文檔轉(zhuǎn)化為向量表示,，之后的所有運算便都使用這些向量進行,，不再理會原始的文本形式的文檔了（換言之，失寵了,，后后）,。 下一章繼續(xù)訓(xùn)練，咱們之間還沒完,。（怎么聽著像要找人尋仇似的） 文本分類入門(五)訓(xùn)練Part 2 將樣本數(shù)據(jù)成功轉(zhuǎn)化為向量表示之后,，計算機才算開始真正意義上的“學(xué)習(xí)”過程。 再重復(fù)一次,，所謂樣本,，也叫訓(xùn)練數(shù)據(jù)，是由人工進行分類處理過的文檔集合,，計算機認為這些數(shù)據(jù)的分類是絕對正確的,，可以信賴的（但某些方法也有針對訓(xùn)練數(shù)據(jù)可能有錯誤而應(yīng)對的措施）。接下來的一步便是由計算機來觀察這些訓(xùn)練數(shù)據(jù)的特點,，來猜測一個可能的分類規(guī)則（這個分類規(guī)則也可以叫做分類器,，在機器學(xué)習(xí)的理論著作中也叫做一個“假設(shè)”，因為畢竟是對真實分類規(guī)則的一個猜測）,，一旦這個分類滿足一些條件,，我們就認為這個分類規(guī)則大致正確并且足夠好了，便成為訓(xùn)練階段的最終產(chǎn)品——分類器,！再遇到新的,，計算機沒有見過的文檔時，便使用這個分類器來判斷新文檔的類別,。 舉一個現(xiàn)實中的例子,，人們評價一輛車是否是“好車”的時候,，可以看作一個分類問題。我們也可以把一輛車的所有特征提取出來轉(zhuǎn)化為向量形式,。在這個問題中詞典向量可以為： D=（價格,，最高時速，外觀得分,，性價比，稀有程度） 則一輛保時捷的向量表示就可以寫成 vp=（200萬,，320,，9.5，3,，9） 而一輛豐田花冠則可以寫成 vt=（15萬,，220，6.0,，8,，3） 找不同的人來評價哪輛車算好車，很可能會得出不同的結(jié)論,。務(wù)實的人認為性價比才是評判的指標(biāo),，他會認為豐田花冠是好車而保時捷不是；喜歡奢華的有錢人可能以稀有程度來評判,，得出相反的結(jié)論,；喜歡綜合考量的人很可能把各項指標(biāo)都加權(quán)考慮之后才下結(jié)論。 可見,，對同一個分類問題,，用同樣的表示形式（同樣的文檔模型），但因為關(guān)注數(shù)據(jù)不同方面的特性而可能得到不同的結(jié)論,。這種對文檔數(shù)據(jù)不同方面?zhèn)戎氐牟煌瑢?dǎo)致了原理和實現(xiàn)方式都不盡相同的多種方法,，每種方法也都對文本分類這個問題本身作了一些有利于自身的假設(shè)和簡化，這些假設(shè)又接下來影響著依據(jù)這些方法而得到的分類器最終的表現(xiàn),，可謂環(huán)環(huán)相連,，絲絲入扣，冥冥之中自有天意呀（這都什么詞兒……）,。 比較常見,，家喻戶曉，常年被評為國家免檢產(chǎn)品（,？?。┑姆诸愃惴ㄓ幸淮蠖眩裁礇Q策樹,，Rocchio,，樸素貝葉斯，神經(jīng)網(wǎng)絡(luò)，支持向量機,，線性最小平方擬合,，kNN，遺傳算法,，最大熵,，Generalized Instance Set等等等等（這張單子還可以繼續(xù)列下去）。在這里只挑幾個最具代表性的算法侃一侃,。 Rocchio算法 Rocchio算法應(yīng)該算是人們思考文本分類問題時最先能想到,，也最符合直覺的解決方法?；镜乃悸肥前岩粋€類別里的樣本文檔各項取個平均值（例如把所有“體育”類文檔中詞匯“籃球”出現(xiàn)的次數(shù)取個平均值,，再把“裁判”取個平均值，依次做下去）,，可以得到一個新的向量,，形象的稱之為“質(zhì)心”，質(zhì)心就成了這個類別最具代表性的向量表示,。再有新文檔需要判斷的時候,，比較新文檔和質(zhì)心有多么相像（八股點說，判斷他們之間的距離）就可以確定新文檔屬不屬于這個類,。稍微改進一點的Rocchio算法不盡考慮屬于這個類別的文檔（稱為正樣本）,，也考慮不屬于這個類別的文檔數(shù)據(jù)（稱為負樣本），計算出來的質(zhì)心盡量靠近正樣本同時盡量遠離負樣本,。Rocchio算法做了兩個很致命的假設(shè),，使得它的性能出奇的差。一是它認為一個類別的文檔僅僅聚集在一個質(zhì)心的周圍,，實際情況往往不是如此（這樣的數(shù)據(jù)稱為線性不可分的）,；二是它假設(shè)訓(xùn)練數(shù)據(jù)是絕對正確的，因為它沒有任何定量衡量樣本是否含有噪聲的機制,，因而也就對錯誤數(shù)據(jù)毫無抵抗力,。 不過Rocchio產(chǎn)生的分類器很直觀，很容易被人類理解,，算法也簡單,，還是有一定的利用價值的（做漢奸狀），常常被用來做科研中比較不同算法優(yōu)劣的基線系統(tǒng)（Base Line）,。 樸素貝葉斯算法（Naive Bayes） 貝葉斯算法關(guān)注的是文檔屬于某類別概率,。文檔屬于某個類別的概率等于文檔中每個詞屬于該類別的概率的綜合表達式。而每個詞屬于該類別的概率又在一定程度上可以用這個詞在該類別訓(xùn)練文檔中出現(xiàn)的次數(shù)（詞頻信息）來粗略估計,，因而使得整個計算過程成為可行的,。使用樸素貝葉斯算法時,，在訓(xùn)練階段的主要任務(wù)就是估計這些值。 樸素貝葉斯算法的公式只有一個
其中P(d| Ci)=P(w1|Ci) P(w2|Ci) …P(wi|Ci) P(w1|Ci) …P(wm|Ci) （式1） P(wi|Ci)就代表詞匯wi屬于類別Ci的概率,。 這其中就蘊含著樸素貝葉斯算法最大的兩個缺陷,。 首先，P(d| Ci)之所以能展開成（式1）的連乘積形式,，就是假設(shè)一篇文章中的各個詞之間是彼此獨立的,，其中一個詞的出現(xiàn)絲毫不受另一個詞的影響（回憶一下概率論中變量彼此獨立的概念就可以知道），但這顯然不對,，即使不是語言學(xué)專家的我們也知道,，詞語之間有明顯的所謂“共現(xiàn)”關(guān)系，在不同主題的文章中,，可能共現(xiàn)的次數(shù)或頻率有變化，但彼此間絕對談不上獨立,。 其二,，使用某個詞在某個類別訓(xùn)練文檔中出現(xiàn)的次數(shù)來估計P(wi|Ci)時，只在訓(xùn)練樣本數(shù)量非常多的情況下才比較準確（考慮扔硬幣的問題,，得通過大量觀察才能基本得出正反面出現(xiàn)的概率都是二分之一的結(jié)論,，觀察次數(shù)太少時很可能得到錯誤的答案），而需要大量樣本的要求不僅給前期人工分類的工作帶來更高要求（從而成本上升）,，在后期由計算機處理的時候也對存儲和計算資源提出了更高的要求,。 kNN算法 kNN算法則又有所不同，在kNN算法看來,，訓(xùn)練樣本就代表了類別的準確信息（因此此算法產(chǎn)生的分類器也叫做“基于實例”的分類器）,，而不管樣本是使用什么特征表示的。其基本思想是在給定新文檔后,，計算新文檔特征向量和訓(xùn)練文檔集中各個文檔的向量的相似度,，得到K篇與該新文檔距離最近最相似的文檔，根據(jù)這K篇文檔所屬的類別判定新文檔所屬的類別（注意這也意味著kNN算法根本沒有真正意義上的“訓(xùn)練”階段）,。這種判斷方法很好的克服了Rocchio算法中無法處理線性不可分問題的缺陷,，也很適用于分類標(biāo)準隨時會產(chǎn)生變化的需求（只要刪除舊訓(xùn)練文檔，添加新訓(xùn)練文檔,，就改變了分類的準則）,。 kNN唯一的也可以說最致命的缺點就是判斷一篇新文檔的類別時，需要把它與現(xiàn)存的所有訓(xùn)練文檔全都比較一遍,，這個計算代價并不是每個系統(tǒng)都能夠承受的（比如我將要構(gòu)建的一個文本分類系統(tǒng),，上萬個類，每個類即便只有20個訓(xùn)練樣本,，為了判斷一個新文檔的類別,，也要做20萬次的向量比較?。Ｒ恍┗趉NN的改良方法比如Generalized Instance Set就在試圖解決這個問題,。 下一節(jié)繼續(xù)講和訓(xùn)練階段有關(guān)的話題,，包括概述已知性能最好的SVM算法。明兒見?。ū本┤藘?，呵呵） 文本分類入門(六)訓(xùn)練Part 3 SVM算法 支持向量機(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本,、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢,，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學(xué)習(xí)問題中[10]。 支持向量機方法是建立在統(tǒng)計學(xué)習(xí)理論的VC 維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的,，根據(jù)有限的樣本信息在模型的復(fù)雜性（即對特定訓(xùn)練樣本的學(xué)習(xí)精度,，Accuracy）和學(xué)習(xí)能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷，以期獲得最好的推廣能力[14]（或稱泛化能力）,。 SVM 方法有很堅實的理論基礎(chǔ),，SVM 訓(xùn)練的本質(zhì)是解決一個二次規(guī)劃問題（Quadruple Programming，指目標(biāo)函數(shù)為二次函數(shù),，約束條件為線性約束的最優(yōu)化問題）,，得到的是全局最優(yōu)解，這使它有著其他統(tǒng)計學(xué)習(xí)技術(shù)難以比擬的優(yōu)越性,。SVM 分類器的文本分類效果很好,，是最好的分類器之一。同時使用核函數(shù)將原始的樣本空間向高維空間進行變換,，能夠解決原始樣本線性不可分的問題,。其缺點是核函數(shù)的選擇缺乏指導(dǎo)，難以針對具體問題選擇最佳的核函數(shù),；另外SVM 訓(xùn)練速度極大地受到訓(xùn)練集規(guī)模的影響,，計算開銷比較大，針對SVM 的訓(xùn)練速度問題,，研究者提出了很多改進方法,，包括Chunking 方法、Osuna 算法,、SMO 算法和交互SVM 等等[14],。 SVM分類器的優(yōu)點在于通用性較好，且分類精度高,、分類速度快,、分類速度與訓(xùn)練樣本個數(shù)無關(guān)，在查準和查全率方面都優(yōu)于kNN及樸素貝葉斯方法[8],。 與其它算法相比,，SVM算法的理論基礎(chǔ)較為復(fù)雜,，但應(yīng)用前景很廣，我打算專門寫一個系列的文章,，詳細的討論SVM算法,，stay tuned！ 介紹過了幾個很具代表性的算法之后,，不妨用國內(nèi)外的幾組實驗數(shù)據(jù)來比較一下他們的優(yōu)劣,。 在中文語料上的試驗，文獻[6]使用了復(fù)旦大學(xué)自然語言處理實驗室提供的基準語料對當(dāng)前的基于詞向量空間文本模型的幾種分類算法進行了測試,，這一基準語料分為20個類別,，共有9804篇訓(xùn)練文檔，以及9833篇測試文檔,。在經(jīng)過統(tǒng)一的分詞處理,、噪聲詞消除等預(yù)處理之后，各個分類方法的性能指標(biāo)如下,。
其中F1 測度是一種綜合了查準率與召回率的指標(biāo),，只有當(dāng)兩個值均比較大的時候，對應(yīng)的F1測度才比較大,，因此是比單一的查準或召回率更加具有代表性的指標(biāo),。 由比較結(jié)果不難看出,，SVM和kNN明顯優(yōu)于樸素貝葉斯方法（但他們也都優(yōu)于Rocchio方法,，這種方法已經(jīng)很少再參加評測了）。 在英文語料上,，路透社的Reuters-21578 “ModApt′e”是比較常用的測試集,，在這個測試集上的測試由很多人做過，Sebastiani在文獻[23]中做了總結(jié),，相關(guān)算法的結(jié)果摘錄如下： 分類算法在Reuters-21578 “ModApt′e”上的F1測度: Rocchio 0.776 樸素貝葉斯 0.795 kNN 0.823 SVM 0.864 僅以F1測度來看,，kNN是相當(dāng)接近SVM算法的，但F1只反映了分類效果（即分類分得準不準）,，而沒有考慮性能（即分類分得快不快）,。綜合而論，SVM是效果和性能均不錯的算法,。 前面也提到過,，訓(xùn)練階段的最終產(chǎn)物就是分類器，分類階段僅僅是使用這些分類器對新來的文檔分類而已,，沒有過多可說的東西,。 下一章節(jié)是對到目前為止出現(xiàn)過的概念的列表及簡單的解釋，也會引入一些后面會用到的概念,。再之后會談及分類問題本身的分類（繞口）,，中英文分類問題的相似與不同之處以及幾種特征提取算法的概述和比較,，路漫漫…… 文本分類入門(七)相關(guān)概念總結(jié) 學(xué)習(xí)方法：使用樣例（或稱樣本，訓(xùn)練集）來合成計算機程序的過程稱為學(xué)習(xí)方法[22],。 監(jiān)督學(xué)習(xí)：學(xué)習(xí)過程中使用的樣例是由輸入/輸出對給出時,，稱為監(jiān)督學(xué)習(xí)[22]。最典型的監(jiān)督學(xué)習(xí)例子就是文本分類問題,，訓(xùn)練集是一些已經(jīng)明確分好了類別文檔組成,，文檔就是輸入，對應(yīng)的類別就是輸出,。 非監(jiān)督學(xué)習(xí)：學(xué)習(xí)過程中使用的樣例不包含輸入/輸出對,，學(xué)習(xí)的任務(wù)是理解數(shù)據(jù)產(chǎn)生的過程 [22]。典型的非監(jiān)督學(xué)習(xí)例子是聚類,，類別的數(shù)量,，名稱，事先全都沒有確定,，由計算機自己觀察樣例來總結(jié)得出,。 TSR（Term Space Reduction）：特征空間的壓縮，即降維,，也可以叫做特征提取,。包括特征選擇和特征抽取兩大類方法。 分類狀態(tài)得分（CSV,，Categorization Status Value)：用于描述將文檔歸于某個類別下有多大的可信度,。 準確率（Precision）：在所有被判斷為正確的文檔中，有多大比例是確實正確的,。 召回率（Recall）：在所有確實正確的文檔中,，有多大比例被我們判為正確。 假設(shè)：計算機對訓(xùn)練集背后的真實模型（真實的分類規(guī)則）的猜測稱為假設(shè),?？梢园颜鎸嵉姆诸愐?guī)則想像為一個目標(biāo)函數(shù)，我們的假設(shè)則是另一個函數(shù),，假設(shè)函數(shù)在所有的訓(xùn)練數(shù)據(jù)上都得出與真實函數(shù)相同（或足夠接近）的結(jié)果,。 泛化性：一個假設(shè)能夠正確分類訓(xùn)練集之外數(shù)據(jù)（即新的，未知的數(shù)據(jù)）的能力稱為該假設(shè)的泛化性[22],。 一致假設(shè)：一個假設(shè)能夠?qū)λ杏?xùn)練數(shù)據(jù)正確分類,，則稱這個假設(shè)是一致的[22]。 過擬合：為了得到一致假設(shè)而使假設(shè)變得過度復(fù)雜稱為過擬合[22],。想像某種學(xué)習(xí)算法產(chǎn)生了一個過擬合的分類器,，這個分類器能夠百分之百的正確分類樣本數(shù)據(jù)（即再拿樣本中的文檔來給它，它絕對不會分錯），但也就為了能夠?qū)颖就耆_的分類,，使得它的構(gòu)造如此精細復(fù)雜,，規(guī)則如此嚴格，以至于任何與樣本數(shù)據(jù)稍有不同的文檔它全都認為不屬于這個類別,！ 超平面（Hyper Plane）：n維空間中的線性函數(shù)唯一確定了一個超平面,。一些較直觀的例子，在二維空間中,，一條直線就是一個超平面,；在三維空間中，一個平面就是一個超平面,。 線性可分和不可分：如果存在一個超平面能夠正確分類訓(xùn)練數(shù)據(jù),，并且這個程序保證收斂，這種情況稱為線形可分,。如果這樣的超平面不存在,，則稱數(shù)據(jù)是線性不可分的[22]。 正樣本和負樣本：對某個類別來說,，屬于這個類別的樣本文檔稱為正樣本,；不屬于這個類別的文檔稱為負樣本。 規(guī)劃：對于目標(biāo)函數(shù),，等式或不等式約束都是線性函數(shù)的問題稱為線性規(guī)劃問題,。對于目標(biāo)函數(shù)是二次的，而約束都是線性函數(shù)的最優(yōu)化問題稱為二次規(guī)劃問題[22],。 對偶問題： 給定一個帶約束的優(yōu)化問題 目標(biāo)函數(shù)：min f(x) 約束條件：C(x) ≥0 可以通過拉格朗日乘子構(gòu)造拉格朗日函數(shù) L(x,λ)=f(x)- λTC(x) 令g(λ)= f(x)- λTC(x) 則原問題可以轉(zhuǎn)化為 目標(biāo)函數(shù)：max g(λ) 約束條件：λ≥0 這個新的優(yōu)化問題就稱為原問題的對偶問題（兩個問題在取得最優(yōu)解時達到的條件相同）,。 文本分類入門(八)中英文文本分類的異同 從文本分類系統(tǒng)的處理流程來看，無論待分類的文本是中文還是英文,，在訓(xùn)練階段之前都要經(jīng)過一個預(yù)處理的步驟,，去除無用的信息,，減少后續(xù)步驟的復(fù)雜度和計算負擔(dān),。 對中文文本來說，首先要經(jīng)歷一個分詞的過程,，就是把連續(xù)的文字流切分成一個一個單獨的詞匯（因為詞匯將作為訓(xùn)練階段“特征”的最基本單位）,，例如原文是“中華人民共和國今天成立了”的文本就要被切分成“中華／人民／共和國／今天／成立／了”這樣的形式。而對英文來說,，沒有這個步驟（更嚴格的說,，并不是沒有這個步驟，而是英文只需要通過空格和標(biāo)點便很容易將一個一個獨立的詞從原文中區(qū)分出來）,。中文分詞的效果對文本分類系統(tǒng)的表現(xiàn)影響很大,，因為在后面的流程中，全都使用預(yù)處理之后的文本信息,，不再參考原始文本,，因此分詞的效果不好,，等同于引入了錯誤的訓(xùn)練數(shù)據(jù)。分詞本身也是一個值得大書特書的問題,，目前比較常用的方法有詞典法,，隱馬爾科夫模型和新興的CRF方法。 預(yù)處理中在分詞之后的“去停止詞”一步對兩者來說是相同的,，都是要把語言中一些表意能力很差的輔助性文字從原始文本中去除,，對中文文本來說，類似“我們”,，“在”,，“了”，“的”這樣的詞匯都會被去除,，英文中的“ an”,，“in”，“the”等也一樣,。這一步驟會參照一個被稱為“停止詞表”的數(shù)據(jù)（里面記錄了應(yīng)該被去除的詞,，有可能是以文件形式存儲在硬盤上，也有可能是以數(shù)據(jù)結(jié)構(gòu)形式放在內(nèi)存中）來進行,。 對中文文本來說,，到此就已初審合格，可以參加訓(xùn)練了（笑）,。而英文文本還有進一步簡化和壓縮的空間,。我們都知道，英文中同一個詞有所謂詞形的變化（相對的,，詞義本身卻并沒有變）,，例如名詞有單復(fù)數(shù)的變化，動詞有時態(tài)的變化,，形容詞有比較級的變化等等,，還包括這些變化形式的某種組合。而正因為詞義本身沒有變化,，僅僅詞形不同的詞就不應(yīng)該作為獨立的詞來存儲和和參與分類計算,。去除這些詞形不同，但詞義相同的詞,，僅保留一個副本的步驟就稱為“詞根還原”,，例如在一篇英文文檔中，經(jīng)過詞根還原后,，“computer”,，“compute”，“computing”，“computational”這些詞全都被處理成“compute”（大小寫轉(zhuǎn)換也在這一步完成,，當(dāng)然,，還要記下這些詞的數(shù)目作為compute的詞頻信息）。 經(jīng)過預(yù)處理步驟之后,，原始文檔轉(zhuǎn)換成了非常節(jié)省資源,，也便于計算的形式，后面的訓(xùn)練階段大同小異（僅僅抽取出的特征不同而已,，畢竟,，一個是中文詞匯的集合，一個是英文詞匯的集合嘛）,。 下一章節(jié)侃侃分類問題本身的分類,。 文本分類入門(九)文本分類問題的分類 開始之前首先說說分類體系?；貞浺幌?，分類體系是指事先確定的類別的層次結(jié)構(gòu)以及文檔與這些類別間的關(guān)系。 其中包含著兩方面的內(nèi)容： 一,，類別之間的關(guān)系,。一般來說類別之間的關(guān)系都是可以表示成樹形結(jié)構(gòu)，這意味著一個類有多個子類,，而一個子類唯一的屬于一個父類,。這種類別體系很常用，卻并不代表它在現(xiàn)實世界中也是符合常識的,，舉個例子,，“臨床心理學(xué)”這個類別應(yīng)該即屬于“臨床醫(yī)學(xué)”的范疇，同時也屬于“心理學(xué)”,，但在分類系統(tǒng)中卻不便于使用這樣的結(jié)構(gòu),。想象一下，這相當(dāng)于類別的層次結(jié)構(gòu)是一個有環(huán)圖,，無論遍歷還是今后類別的合并,，比較，都會帶來無數(shù)的麻煩,。 二,，文檔與類別間的關(guān)系,。一般來說,，在分類系統(tǒng)中，我們傾向于讓一篇文檔唯一的屬于一個類別（更嚴格的說,，是在同一層次中僅屬于一個類別,，因為屬于一個類別的時候，顯然也屬于這個類別的父類別），這使得我們只適用一個標(biāo)簽就可以標(biāo)記這個文檔的類別,，而一旦允許文檔屬于多個類別,，標(biāo)簽的數(shù)目便成為大小不定的變量，難于設(shè)計成高效的數(shù)據(jù)結(jié)構(gòu),。這種“屬于多個”類的想法更糟的地方在于文檔類別表示的語義方面,，試想，如果姚明給災(zāi)區(qū)捐款的新聞即屬于災(zāi)區(qū)新聞,，也屬于體育新聞的話（這在現(xiàn)實中倒確實是合情合理的）,，當(dāng)用戶使用這個系統(tǒng)來查找文檔，指定的條件是要所有“屬于災(zāi)區(qū)新聞但不屬于體育新聞的新聞”（有點拗口,，不過正好練嘴皮子啦,，笑）的時候，這篇姚明的報道是否應(yīng)該包含在查詢結(jié)果中呢,？這是一個矛盾的問題,。 文本分類問題牽涉到如此多的主題，本身又含有如此多的屬性,，因此可以從多個角度對文本分類問題本身進行一下分類,。 分類系統(tǒng)使用何種分類算法是分類系統(tǒng)的核心屬性。如果一個分類算法在一次分類判斷時,，僅僅輸出一個真假值用來表示待分類的文檔是否屬于當(dāng)前類別的話,，這樣的系統(tǒng)就可以叫做基于二元分類器的分類系統(tǒng)。有些分類算法天然就是獨立二元的,，例如支持向量機,，它只能回答這個文檔是或不是這個類別的。這種分類算法也常常被稱為“硬分類”的算法（Hard Categorization）,。而有的算法在一次判斷后就可以輸出文檔屬于多個類別的得分（假設(shè)說,，得分越大，則說明越有可能屬于這個類別）,，這類算法稱為“排序分類”的算法（Ranking Categorization）,，也叫做m元分類算法。kNN就是典型的m元分類算法（因為kNN會找出與待分類文檔最相近的訓(xùn)練樣本,，并記錄下這些樣本所屬的分類）,。 文本分類入門（十）特征選擇算法之開方檢驗 前文提到過，除了分類算法以外,，為分類文本作處理的特征提取算法也對最終效果有巨大影響,，而特征提取算法又分為特征選擇和特征抽取兩大類，其中特征選擇算法有互信息,，文檔頻率,，信息增益,，開方檢驗等等十?dāng)?shù)種，這次先介紹特征選擇算法中效果比較好的開方檢驗方法,。 大家應(yīng)該還記得,，開方檢驗其實是數(shù)理統(tǒng)計中一種常用的檢驗兩個變量獨立性的方法。（什么,？你是文史類專業(yè)的學(xué)生,，沒有學(xué)過數(shù)理統(tǒng)計？那你做什么文本分類,？在這搗什么亂,？） 開方檢驗最基本的思想就是通過觀察實際值與理論值的偏差來確定理論的正確與否。具體做的時候常常先假設(shè)兩個變量確實是獨立的（行話就叫做“原假設(shè)”）,，然后觀察實際值（也可以叫做觀察值）與理論值（這個理論值是指“如果兩者確實獨立”的情況下應(yīng)該有的值）的偏差程度,，如果偏差足夠小，我們就認為誤差是很自然的樣本誤差,，是測量手段不夠精確導(dǎo)致或者偶然發(fā)生的,，兩者確確實實是獨立的，此時就接受原假設(shè),；如果偏差大到一定程度,，使得這樣的誤差不太可能是偶然產(chǎn)生或者測量不精確所致，我們就認為兩者實際上是相關(guān)的,，即否定原假設(shè),，而接受備擇假設(shè)。 那么用什么來衡量偏差程度呢,？假設(shè)理論值為E（這也是數(shù)學(xué)期望的符號哦）,，實際值為x，如果僅僅使用所有樣本的觀察值與理論值的差值x-E之和
來衡量,，單個的觀察值還好說,，當(dāng)有多個觀察值x1，x2,，x3的時候,，很可能x1-E，x2-E,，x3-E的值有正有負,，因而互相抵消，使得最終的結(jié)果看上好像偏差為0,，但實際上每個都有偏差,，而且都還不小,！此時很直接的想法便是使用方差代替均值,，這樣就解決了正負抵消的問題,，即使用
這時又引來了新的問題,，對于500的均值來說,，相差5其實是很小的（相差1%），而對20的均值來說,，5相當(dāng)于25%的差異,，這是使用方差也無法體現(xiàn)的。因此應(yīng)該考慮改進上面的式子,，讓均值的大小不影響我們對差異程度的判斷
上面這個式子已經(jīng)相當(dāng)好了,。實際上這個式子就是開方檢驗使用的差值衡量公式。當(dāng)提供了數(shù)個樣本的觀察值x1,，x2,，……xi ，……xn之后,，代入到式（1）中就可以求得開方值,，用這個值與事先設(shè)定的閾值比較，如果大于閾值（即偏差很大）,，就認為原假設(shè)不成立,，反之則認為原假設(shè)成立。 在文本分類問題的特征選擇階段,，我們主要關(guān)心一個詞t（一個隨機變量）與一個類別c（另一個隨機變量）之間是否相互獨立,？如果獨立，就可以說詞t對類別c完全沒有表征作用,，即我們根本無法根據(jù)t出現(xiàn)與否來判斷一篇文檔是否屬于c這個分類,。但與最普通的開方檢驗不同，我們不需要設(shè)定閾值,，因為很難說詞t和類別c關(guān)聯(lián)到什么程度才算是有表征作用,，我們只想借用這個方法來選出一些最最相關(guān)的即可。 此時我們?nèi)匀恍枰靼讓μ卣鬟x擇來說原假設(shè)是什么,，因為計算出的開方值越大,，說明對原假設(shè)的偏離越大，我們越傾向于認為原假設(shè)的反面情況是正確的,。我們能不能把原假設(shè)定為“詞t與類別c相關(guān)“,？原則上說當(dāng)然可以，這也是一個健全的民主主義社會賦予每個公民的權(quán)利（笑）,，但此時你會發(fā)現(xiàn)根本不知道此時的理論值該是多少,！你會把自己繞進死胡同。所以我們一般都使用”詞t與類別c不相關(guān)“來做原假設(shè),。選擇的過程也變成了為每個詞計算它與類別c的開方值,，從大到小排個序（此時開方值越大越相關(guān)）,，取前k個就可以（k值可以根據(jù)自己的需要選，這也是一個健全的民主主義社會賦予每個公民的權(quán)利）,。 好,，原理有了，該來個例子說說到底怎么算了,。 比如說現(xiàn)在有N篇文檔,，其中有M篇是關(guān)于體育的，我們想考察一個詞“籃球”與類別“體育”之間的相關(guān)性（任誰都看得出來兩者很相關(guān),，但很遺憾,，我們是智慧生物，計算機不是,，它一點也看不出來,，想讓它認識到這一點，只能讓它算算看）,。我們有四個觀察值可以使用： 1. 包含“籃球”且屬于“體育”類別的文檔數(shù),，命名為A 2. 包含“籃球”但不屬于“體育”類別的文檔數(shù)，命名為B 3. 不包含“籃球”但卻屬于“體育”類別的文檔數(shù),，命名為C 4. 既不包含“籃球”也不屬于“體育”類別的文檔數(shù),，命名為D 如果有些特點你沒看出來，那我說一說,，首先,，A+B+C+D=N（這，這不廢話嘛）,。其次,，A+C的意思其實就是說“屬于體育類的文章數(shù)量”，因此,，它就等于M,，同時，B+D就等于N-M,。 好,，那么理論值是什么呢？以包含“籃球”且屬于“體育”類別的文檔數(shù)為例,。如果原假設(shè)是成立的,，即“籃球”和體育類文章沒什么關(guān)聯(lián)性，那么在所有的文章中,，“籃球”這個詞都應(yīng)該是等概率出現(xiàn),，而不管文章是不是體育類的。這個概率具體是多少,，我們并不知道,，但他應(yīng)該體現(xiàn)在觀察結(jié)果中（就好比拋硬幣的概率是二分之一,，可以通過觀察多次拋的結(jié)果來大致確定），因此我們可以說這個概率接近
（因為A+B是包含“籃球”的文章數(shù),，除以總文檔數(shù)就是“籃球”出現(xiàn)的概率,，當(dāng)然，這里認為在一篇文章中出現(xiàn)即可,，而不管出現(xiàn)了幾次）而屬于體育類的文章數(shù)為A+C,，在這些個文檔中,，應(yīng)該有
篇包含“籃球”這個詞（數(shù)量乘以概率嘛）,。 但實際有多少呢？考考你（讀者：切,，當(dāng)然是A啦,，表格里寫著嘛……）。 此時對這種情況的差值就得出了（套用式（1）的公式）,，應(yīng)該是
同樣,，我們還可以計算剩下三種情況的差值D12，D21,，D22,，聰明的讀者一定能自己算出來（讀者：切，明明是自己懶得寫了……）,。有了所有觀察值的差值,，就可以計算“籃球”與“體育”類文章的開方值
把D11，D12,，D21,，D22的值分別代入并化簡，可以得到 詞t與類別c的開方值更一般的形式可以寫成
接下來我們就可以計算其他詞如“排球”,，“產(chǎn)品”,，“銀行”等等與體育類別的開方值，然后根據(jù)大小來排序,，選擇我們需要的最大的數(shù)個詞匯作為特征項就可以了,。 實際上式（2）還可以進一步化簡，注意如果給定了一個文檔集合（例如我們的訓(xùn)練集）和一個類別,，則N,，M，N-M（即A+C和B+D）對同一類別文檔中的所有詞來說都是一樣的,，而我們只關(guān)心一堆詞對某個類別的開方值的大小順序,，而并不關(guān)心具體的值，因此把它們從式（2）中去掉是完全可以的,，故實際計算的時候我們都使用
好啦,，并不高深對不對,？ 針對英文純文本的實驗結(jié)果表明：作為特征選擇方法時，開方檢驗和信息增益的效果最佳（相同的分類算法,，使用不同的特征選擇算法來得到比較結(jié)果）,；文檔頻率方法的性能同前兩者大體相當(dāng)，術(shù)語強度方法性能一般,；互信息方法的性能最差（文獻[17]）,。 但開方檢驗也并非就十全十美了?；仡^想想A和B的值是怎么得出來的,，它統(tǒng)計文檔中是否出現(xiàn)詞t，卻不管t在該文檔中出現(xiàn)了幾次,，這會使得他對低頻詞有所偏袒（因為它夸大了低頻詞的作用）,。甚至?xí)霈F(xiàn)有些情況，一個詞在一類文章的每篇文檔中都只出現(xiàn)了一次,，其開方值卻大過了在該類文章99%的文檔中出現(xiàn)了10次的詞,，其實后面的詞才是更具代表性的，但只因為它出現(xiàn)的文檔數(shù)比前面的詞少了“1”,，特征選擇的時候就可能篩掉后面的詞而保留了前者,。這就是開方檢驗著名的“低頻詞缺陷“。因此開方檢驗也經(jīng)常同其他因素如詞頻綜合考慮來揚長避短,。 好啦,，關(guān)于開方檢驗先說這么多，有機會還將介紹其他的特征選擇算法,。 附：給精通統(tǒng)計學(xué)的同學(xué)多說幾句,，式（1）實際上是對連續(xù)型的隨機變量的差值計算公式，而我們這里統(tǒng)計的“文檔數(shù)量“顯然是離散的數(shù)值（全是整數(shù)）,，因此真正在統(tǒng)計學(xué)中計算的時候,，是有修正過程的，但這種修正仍然是只影響具體的開方值,，而不影響大小的順序,，故文本分類中不做這種修正。 文本分類入門（十一）特征選擇方法之信息增益 從以上討論中可以看出,，信息增益也是考慮了特征出現(xiàn)和不出現(xiàn)兩種情況,，與開方檢驗一樣，是比較全面的,，因而效果不錯,。但信息增益最大的問題還在于它只能考察特征對整個系統(tǒng)的貢獻，而不能具體到某個類別上，這就使得它只適合用來做所謂“全局”的特征選擇（指所有的類都使用相同的特征集合）,，而無法做“本地”的特征選擇（每個類別有自己的特征集合,，因為有的詞，對這個類別很有區(qū)分度,，對另一個類別則無足輕重）,。 看看，導(dǎo)出的過程其實很簡單,，沒有什么神秘的對不對,。可有的學(xué)術(shù)論文里就喜歡把這種本來很直白的東西寫得很晦澀,，仿佛只有讀者看不懂才是作者的真正成功,。 咱們是新一代的學(xué)者，咱們沒有知識不怕被別人看出來，咱們有知識也不怕教給別人。所以咱都把事情說簡單點,，說明白點,，大家好，才是真的好,。 前文提到過,，除了開方檢驗（CHI）以外，信息增益（IG,，Information Gain）也是很有效的特征選擇方法,。但凡是特征選擇，總是在將特征的重要程度量化之后再進行選擇,，而如何量化特征的重要性,，就成了各種方法間最大的不同。開方檢驗中使用特征與類別間的關(guān)聯(lián)性來進行這個量化,，關(guān)聯(lián)性越強,，特征得分越高，該特征越應(yīng)該被保留,。 在信息增益中,，重要性的衡量標(biāo)準就是看特征能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多,，該特征越重要,。 因此先回憶一下信息論中有關(guān)信息量（就是“熵”）的定義。說有這么一個變量X,，它可能的取值有n多種,，分別是x1，x2，……,，xn,，每一種取到的概率分別是P1，P2,，……,，Pn，那么X的熵就定義為： 意思就是一個變量可能的變化越多（反而跟變量具體的取值沒有任何關(guān)系,，只和值的種類多少以及發(fā)生概率有關(guān)）,，它攜帶的信息量就越大（因此我一直覺得我們的政策法規(guī)信息量非常大，因為它變化很多,，基本朝令夕改,，笑）。 對分類系統(tǒng)來說,，類別C是變量,，它可能的取值是C1，C2,，……,，Cn，而每一個類別出現(xiàn)的概率是P(C1),，P(C2),，……，P(Cn),，因此n就是類別的總數(shù),。此時分類系統(tǒng)的熵就可以表示為： 有同學(xué)說不好理解呀，這樣想就好了,，文本分類系統(tǒng)的作用就是輸出一個表示文本屬于哪個類別的值,，而這個值可能是C1，C2,，……,，Cn，因此這個值所攜帶的信息量就是上式中的這么多,。 信息增益是針對一個一個的特征而言的,，就是看一個特征t，系統(tǒng)有它和沒它的時候信息量各是多少,，兩者的差值就是這個特征給系統(tǒng)帶來的信息量,，即增益。系統(tǒng)含有特征t的時候信息量很好計算,，就是剛才的式子,，它表示的是包含所有特征時系統(tǒng)的信息量。 問題是當(dāng)系統(tǒng)不包含t時，信息量如何計算,？我們換個角度想問題,，把系統(tǒng)要做的事情想象成這樣：說教室里有很多座位，學(xué)生們每次上課進來的時候可以隨便坐,，因而變化是很大的（無數(shù)種可能的座次情況）,；但是現(xiàn)在有一個座位，看黑板很清楚,，聽老師講也很清楚,，于是校長的小舅子的姐姐的女兒托關(guān)系（真輾轉(zhuǎn)啊）,，把這個座位定下來了,，每次只能給她坐，別人不行,，此時情況怎樣,？對于座次的可能情況來說，我們很容易看出以下兩種情況是等價的：（1）教室里沒有這個座位,；（2）教室里雖然有這個座位,，但其他人不能坐（因為反正它也不能參與到變化中來，它是不變的）,。 對應(yīng)到我們的系統(tǒng)中,，就是下面的等價：（1）系統(tǒng)不包含特征t；（2）系統(tǒng)雖然包含特征t,，但是t已經(jīng)固定了，不能變化,。 我們計算分類系統(tǒng)不包含特征t的時候,，就使用情況（2）來代替，就是計算當(dāng)一個特征t不能變化時,，系統(tǒng)的信息量是多少,。這個信息量其實也有專門的名稱，就叫做“條件熵”,，條件嘛,，自然就是指“t已經(jīng)固定“這個條件。 但是問題接踵而至,，例如一個特征X,，它可能的取值有n多種（x1，x2,，……,，xn），當(dāng)計算條件熵而需要把它固定的時候，要把它固定在哪一個值上呢,？答案是每一種可能都要固定一下,，計算n個值，然后取均值才是條件熵,。而取均值也不是簡單的加一加然后除以n,，而是要用每個值出現(xiàn)的概率來算平均（簡單理解，就是一個值出現(xiàn)的可能性比較大,，固定在它上面時算出來的信息量占的比重就要多一些）,。 因此有這樣兩個條件熵的表達式： 這是指特征X被固定為值xi時的條件熵， 這是指特征X被固定時的條件熵,，注意與上式在意義上的區(qū)別,。從剛才計算均值的討論可以看出來，第二個式子與第一個式子的關(guān)系就是：
具體到我們文本分類系統(tǒng)中的特征t,，t有幾個可能的值呢,？注意t是指一個固定的特征，比如他就是指關(guān)鍵詞“經(jīng)濟”或者“體育”,，當(dāng)我們說特征“經(jīng)濟”可能的取值時,，實際上只有兩個，“經(jīng)濟”要么出現(xiàn),，要么不出現(xiàn),。一般的，t的取值只有t（代表t出現(xiàn)）和 因此固定t時系統(tǒng)的條件熵就有了，為了區(qū)別t出現(xiàn)時的符號與特征t本身的符號,，我們用T代表特征,，而用t代表T出現(xiàn)，那么： 與剛才的式子對照一下,，含義很清楚對吧,，P(t)就是T出現(xiàn)的概率,，就是T不出現(xiàn)的概率。這個式子可以進一步展開,，其中的 另一半就可以展開為： 因此特征T給系統(tǒng)帶來的信息增益就可以寫成系統(tǒng)原本的熵與固定特征T后的條件熵之差： 公式中的東西看上去很多,，其實也都很好計算,。比如P(Ci),，表示類別Ci出現(xiàn)的概率，其實只要用1除以類別總數(shù)就得到了（這是說你平等的看待每個類別而忽略它們的大小時這樣算,，如果考慮了大小就要把大小的影響加進去）。再比如P(t),，就是特征T出現(xiàn)的概率，只要用出現(xiàn)過T的文檔數(shù)除以總文檔數(shù)就可以了,，再比如P(Ci|t)表示出現(xiàn)T的時候,，類別Ci出現(xiàn)的概率,，只要用出現(xiàn)了T并且屬于類別Ci的文檔數(shù)除以出現(xiàn)了T的文檔數(shù)就可以了。 從以上討論中可以看出,，信息增益也是考慮了特征出現(xiàn)和不出現(xiàn)兩種情況，與開方檢驗一樣,，是比較全面的，因而效果不錯,。但信息增益最大的問題還在于它只能考察特征對整個系統(tǒng)的貢獻,，而不能具體到某個類別上,，這就使得它只適合用來做所謂“全局”的特征選擇（指所有的類都使用相同的特征集合），而無法做“本地”的特征選擇（每個類別有自己的特征集合,，因為有的詞，對這個類別很有區(qū)分度,，對另一個類別則無足輕重）,。 看看，導(dǎo)出的過程其實很簡單,，沒有什么神秘的對不對,。可有的學(xué)術(shù)論文里就喜歡把這種本來很直白的東西寫得很晦澀,，仿佛只有讀者看不懂才是作者的真正成功,。 咱們是新一代的學(xué)者,，咱們沒有知識不怕被別人看出來，咱們有知識也不怕教給別人,。所以咱都把事情說簡單點,，說明白點，大家好,，才是真的好,。 文本分類入門（番外篇）特征選擇與特征權(quán)重計算的區(qū)別 在文本分類的過程中，特征（也可以簡單的理解為“詞”）從人類能夠理解的形式轉(zhuǎn)換為計算機能夠理解的形式時,，實際上經(jīng)過了兩步驟的量化——特征選擇階段的重要程度量化和將具體文本轉(zhuǎn)化為向量時的特征權(quán)重量化。初次接觸文本分類的人很容易混淆這兩個步驟使用的方法和各自的目的,，因而我經(jīng)常聽到讀者有類似“如何使用TFIDF做特征選擇”或者“卡方檢驗量化權(quán)重后每篇文章都一樣”等等困惑,。 文本分類本質(zhì)上也是一個模式識別的問題，因此我想借用一個更直觀的例子來說說特征選擇和權(quán)重量化到底各自是什么東西,，當(dāng)然,，一旦解釋清楚，你馬上就會覺得文本分類這東西實在白癡,，實在沒什么技術(shù)含量,，你也就不會再繼續(xù)看我的技術(shù)博客，不過我不擔(dān)心,，因為你已經(jīng)踏上了更光明的道路（笑）,，我高興還來不及。 想想通過指紋來識別一個人的身份,，只看一個人的指紋,，當(dāng)然說不出他姓甚名誰，識別的過程實際上是比對的過程,，要與已有的指紋庫比較,，找出相同的，或者說相似到一定程度的那一個,。 首要的問題是,，人的指紋太復(fù)雜，包含太多的位置和幾何形狀,，要完全重現(xiàn)一個人的指紋,，存儲和計算都是大麻煩。因此第一步總是一個特征選擇的問題,，我們把全人類的指紋都統(tǒng)計一下,，看看哪幾個位置能夠最好的區(qū)分不同的人。顯然不同的位置效果很不一樣,，在有的位置上,，我的指紋是是什么形狀，其他人也大都是這個形狀,，這個位置就不具有區(qū)分度，或者說不具有表征性,，或者說，對分類問題來說,，它的重要程度低。這樣的位置我們就傾向于在識別的時候根本不看它,，不考慮它。 那怎么看誰重要誰不重要呢,？這就依賴于具體的選擇方法如何來量化重要程度，對卡方檢驗和信息增益這類方法來說,，量化以后的得分越大的特征就越重要（也就是說，有可能有些方法,，是得分越小的越重要）。 比如說你看10個位置,，他們的重要程度分別是： 1 2 3 4 5 6 7 8 9 10 （20，5,，10，20,，30，15,，4，3,，7， 3） 顯然第1,，第3,，4,，5，6個位置比其他位置更重要,，而相對的，第1個位置又比第3個位置更重要,。 識別時,，我們只在那些重要的位置上采樣。當(dāng)今的指紋識別系統(tǒng),，大都只用到人指紋的5個位置（驚訝么？只要5個位置的信息就可以區(qū)分60億人）,，這5個位置就是經(jīng)過特征選擇過程而得以保留的系統(tǒng)特征集合。假設(shè)這個就是剛才的例子,，那么該集合應(yīng)該是： （第1個位置,，第3個位置，第4個位置,，第5個位置，第6個位置） 當(dāng)然,，具體的第3個位置是指紋中的哪個位置你自己總得清楚。 確定了這5個位置之后,，就可以把一個人的指紋映射到這個只有5個維度的空間中,，我們就把他在5個位置上的幾何形狀分別轉(zhuǎn)換成一個具體的值,，這就是特征權(quán)重的計算。依據(jù)什么來轉(zhuǎn)換,，就是你選擇的特征權(quán)重量化方法，在文本分類中,，最常用的就是TFIDF。 我想一定是“權(quán)重“這個詞誤導(dǎo)了所有人,，讓大家以為TFIDF計算出的值代表的是特征的重要程度，其實完全不是,。例如我們有一位男同學(xué)，他的指紋向量是： （10,，3，4,，20，5） 你注意到他第1個位置的得分（10）比第3個位置的得分（3）高,，那么能說第1個位置比第3個位置重要么？如果再有一位女同學(xué),，她的指紋向量是： （10,，20,，4，20,，5） 看看，第1個位置得分（10）又比第3個位置（20）低了,，那這兩個位置到底哪個更重要呢,？答案是第1個位置更重要，但這不是在特征權(quán)重計算這一步體現(xiàn)出來的,，而是在我們特征選擇的時候就確定了，第1個位置比第3個位置更重要,。 因此要記住，通過TFIDF計算一個特征的權(quán)重時,，該權(quán)重體現(xiàn)出的根本不是特征的重要程度,！ 那它代表什么,？再看看兩位同學(xué)的指紋，放到一起： （10,， 3,，4,，20，5） （10,，20，4,，20,，5） 在第三個位置上女同學(xué)的權(quán)重高于男同學(xué)，這不代表該女同學(xué)在指紋的這個位置上更“優(yōu)秀“（畢竟,，指紋還有什么優(yōu)秀不優(yōu)秀的分別么,，笑），也不代表她的這個位置比男同學(xué)的這個位置更重要,，3和20這兩個得分，僅僅代表他們的”不同“,。 在文本分類中也是如此，比如我們的系統(tǒng)特征集合只有兩個詞： （經(jīng)濟,，發(fā)展） 這兩個詞是使用卡方檢驗（特征選擇）選出來的,，有一篇文章的向量形式是 （2，5） 另一篇 （3,，4） 這兩個向量形式就是用TFIDF算出來的，很容易看出兩篇文章不是同一篇,，為什么？因為他們的特征權(quán)重根本不一樣,，所以說權(quán)重代表的是差別,，而不是優(yōu)劣。想想你說“經(jīng)濟這個詞在第二篇文章中得分高,，因此它在第二篇文章中比在第一篇文章中更重要“,，這句話代表什么意義呢？你自己都不知道吧（笑）,。 所以,，當(dāng)再說起使用TFIDF來計算特征權(quán)重時，最好把“權(quán)重“這個字眼忘掉,，我們就把它說成計算得分好了（甚至”得分“也不太好,，因為人總會不自覺的認為，得分高的就更重要）,，或者就僅僅說成是量化,。 如此，你就再也不會拿TFIDF去做特征選擇了,。 小Tips：為什么有的論文里確實使用了TFIDF作特征選擇呢,？ 嚴格說來并不是不可以，而且嚴格說來只要有一種方法能夠從一堆特征中挑出少數(shù)的一些,，它就可以叫做一種特征選擇方法,，就連“隨機選取一部分“都算是一種,，而且效果并沒有差到驚人的地步哦！還是可以分對一大半的哦,！所以有的人就用TFIDF的得分來把特征排排序,，取得分最大的幾個進入系統(tǒng)特征集合,，效果也還行（畢竟,，連隨機選取效果也都還行）,，怎么說呢,，他們愿意這么干就這么干吧,。就像咱國家非得實行戶口制度,，這個制度說不出任何道理，也不見他帶來任何好處,，但不也沒影響二十一世紀成為中國的世紀么，呵呵,。 |
|
|
