文本特徵選擇

在做文本分類聚類的任務時，常常需要從文本中提取特徵，提取出對學習有價值的分類，而不是把所有的詞都用上，那樣會造成維度災難。因此一些詞對分類的作用不大，比如「的、是、在、了」等停用詞。這裡介紹三種常用的特徵選擇方法：

無監督方法：

• TF-IDF

監督方法：

• 卡方
• 信息增益
• 互信息

一、TF-IDF

一個容易想到的思路，就是找到出現次數最多的詞。如果某個詞很重要，它應該在這篇文章中多次出現。於是，我們進行"詞頻"（Term Frequency，縮寫為TF）統計。

結果你肯定猜到了，出現次數最多的詞是----"的"、"是"、"在"----這一類最常用的詞。它們叫做「停用詞」（stop words），表示對找到結果毫無幫助、必須過濾掉的詞。

假設我們把它們都過濾掉了，只考慮剩下的有實際意義的詞。這樣又會遇到了另一個問題，我們可能發現"中國"、"蜜蜂"、"養殖"這三個詞的出現次數一樣多。這是不是意味著，作為關鍵詞，它們的重要性是一樣的？

顯然不是這樣。因為"中國"是很常見的詞，相對而言，"蜜蜂"和"養殖"不那麼常見。如果這三個詞在一篇文章的出現次數一樣多，有理由認為，"蜜蜂"和"養殖"的重要程度要大於"中國"，也就是說，在關鍵詞排序上面，"蜜蜂"和"養殖"應該排在"中國"的前面。

所以，我們需要一個重要性調整係數，衡量一個詞是不是常見詞。如果某個詞比較少見，但是它在這篇文章中多次出現，那麼它很可能就反映了這篇文章的特性，正是我們所需要的關鍵詞。

用統計學語言表達，就是在詞頻的基礎上，要對每個詞分配一個"重要性"權重。最常見的詞（"的"、"是"、"在"）給予最小的權重，較常見的詞（"中國"）給予較小的權重，較少見的詞（"蜜蜂"、"養殖"）給予較大的權重。這個權重叫做"逆文檔頻率"（Inverse Document Frequency，縮寫為IDF），它的大小與一個詞的常見程度成反比。

知道了"詞頻"（TF）和"逆文檔頻率"（IDF）以後，將這兩個值相乘，就得到了一個詞的TF-IDF值。某個詞對文章的重要性越高，它的TF-IDF值就越大。所以，排在最前面的幾個詞，就是這篇文章的關鍵詞。

第一步，計算詞頻。

考慮到文章有長短之分，為了便於不同文章的比較，進行"詞頻"標準化。

或者

如果一個詞越常見，那麼分母就越大，逆文檔頻率就越小越接近0。分母之所以要加1，是為了避免分母為0（即所有文檔都不包含該詞）。log表示對得到的值取對數。

第二步，計算逆文檔頻率。

這時，需要一個語料庫（corpus），用來模擬語言的使用環境。

如果一個詞越常見，那麼分母就越大，逆文檔頻率就越小越接近0。分母之所以要加1，是為了避免分母為0（即所有文檔都不包含該詞）。log表示對得到的值取對數。

第三步，計算TF-IDF。

可以看到，TF-IDF與一個詞在文檔中的出現次數成正比，與該詞在整個語言中的出現次數成反比。所以，自動提取關鍵詞的演算法就很清楚了，就是計算出文檔的每個詞的TF-IDF值，然後按降序排列，取排在最前面的幾個詞。

還是以《中國的蜜蜂養殖》為例，假定該文長度為1000個詞，"中國"、"蜜蜂"、"養殖"各出現20次，則這三個詞的"詞頻"（TF）都為0.02。然後，搜索Google發現，包含"的"字的網頁共有250億張，假定這就是中文網頁總數。包含"中國"的網頁共有62.3億張，包含"蜜蜂"的網頁為0.484億張，包含"養殖"的網頁為0.973億張。則它們的逆文檔頻率（IDF）和TF-IDF如下：

從上表可見，"蜜蜂"的TF-IDF值最高，"養殖"其次，"中國"最低。（如果還計算"的"字的TF-IDF，那將是一個極其接近0的值。）所以，如果只選擇一個詞，"蜜蜂"就是這篇文章的關鍵詞。

除了自動提取關鍵詞，TF-IDF演算法還可以用於許多別的地方。比如，信息檢索時，對於每個文檔，都可以分別計算一組搜索詞（"中國"、"蜜蜂"、"養殖"）的TF-IDF，將它們相加，就可以得到整個文檔的TF-IDF。這個值最高的文檔就是與搜索詞最相關的文檔。

TF-IDF演算法的優點是簡單快速，結果比較符合實際情況。缺點是，單純以"詞頻"衡量一個詞的重要性，不夠全面，有時重要的詞可能出現次數並不多。而且，這種演算法無法體現詞的位置信息，出現位置靠前的詞與出現位置靠後的詞，都被視為重要性相同，這是不正確的。（一種解決方法是，對全文的第一段和每一段的第一句話，給予較大的權重。）

TF-IDF演算法可以用於無監督學習，不需要知道文檔的類別，但是對同一個詞來說，它在不同的文檔中有不同的TF-IDF值，我這裡處理的策略是每篇文檔取top K，然後做一個去重。

二、卡方檢驗

開方檢驗其實是數理統計中一種常用的檢驗兩個變數獨立性的方法。

開方檢驗最基本的思想就是通過觀察實際值與理論值的偏差來確定理論的正確與否。具體做的時候常常先假設兩個變數確實是獨立的（行話就叫做「原假設」），然後觀察實際值（也可以叫做觀察值）與理論值（這個理論值是指「如果兩者確實獨立」的情況下應該有的值）的偏差程度，如果偏差足夠小，我們就認為誤差是很自然的樣本誤差，是測量手段不夠精確導致或者偶然發生的，兩者確確實實是獨立的，此時就接受原假設；如果偏差大到一定程度，使得這樣的誤差不太可能是偶然產生或者測量不精確所致，我們就認為兩者實際上是相關的，即否定原假設，而接受備擇假設。

那麼用什麼來衡量偏差程度呢？假設理論值為E（這也是數學期望的符號哦），實際值為x，如果僅僅使用所有樣本的觀察值與理論值的差值x-E之和

來衡量，單個的觀察值還好說，當有多個觀察值x1，x2，x3的時候，很可能x1-E，x2-E，x3-E的值有正有負，因而互相抵消，使得最終的結果看上好像偏差為0，但實際上每個都有偏差，而且都還不小！此時很直接的想法便是使用方差代替均值，這樣就解決了正負抵消的問題，即使用

這時又引來了新的問題，對於500的均值來說，相差5其實是很小的（相差1%），而對20的均值來說，5相當於25%的差異，這是使用方差也無法體現的。因此應該考慮改進上面的式子，讓均值的大小不影響我們對差異程度的判斷

上面這個式子已經相當好了。實際上這個式子就是開方檢驗使用的差值衡量公式。當提供了數個樣本的觀察值x1，x2，……xi，……xn之後，代入到式（1）中就可以求得開方值，用這個值與事先設定的閾值比較，如果大於閾值（即偏差很大），就認為原假設不成立，反之則認為原假設成立。

在文本分類問題的特徵選擇階段，我們主要關心一個詞t（一個隨機變數）與一個類別c（另一個隨機變數）之間是否相互獨立？如果獨立，就可以說詞t對類別c完全沒有表徵作用，即我們根本無法根據t出現與否來判斷一篇文檔是否屬於c這個分類。但與最普通的開方檢驗不同，我們不需要設定閾值，因為很難說詞t和類別c關聯到什麼程度才算是有表徵作用，我們只想借用這個方法來選出一些最最相關的即可。

此時我們仍然需要明白對特徵選擇來說原假設是什麼，因為計算出的開方值越大，說明對原假設的偏離越大，我們越傾向於認為原假設的反面情況是正確的。我們能不能把原假設定為「詞t與類別c相關「？原則上說當然可以，這也是一個健全的民主主義社會賦予每個公民的權利（笑），但此時你會發現根本不知道此時的理論值該是多少！你會把自己繞進死胡同。所以我們一般都使用」詞t與類別c不相關「來做原假設。選擇的過程也變成了為每個詞計算它與類別c的開方值，從大到小排個序（此時開方值越大越相關），取前k個就可以（k值可以根據自己的需要選，這也是一個健全的民主主義社會賦予每個公民的權利）。

好，原理有了，該來個例子說說到底怎麼算了。

比如說現在有N篇文檔，其中有M篇是關於體育的，我們想考察一個詞「籃球」與類別「體育」之間的相關性（任誰都看得出來兩者很相關，但很遺憾，我們是智慧生物，計算機不是，它一點也看不出來，想讓它認識到這一點，只能讓它算算看）。我們有四個觀察值可以使用：

1. 包含「籃球」且屬於「體育」類別的文檔數，命名為A

2. 包含「籃球」但不屬於「體育」類別的文檔數，命名為B

3. 不包含「籃球」但卻屬於「體育」類別的文檔數，命名為C

4. 既不包含「籃球」也不屬於「體育」類別的文檔數，命名為D

如果有些特點你沒看出來，那我說一說，首先，A+B+C+D=N（這，這不廢話嘛）。其次，A+C的意思其實就是說「屬於體育類的文章數量」，因此，它就等於M，同時，B+D就等於N-M。

好，那麼理論值是什麼呢？以包含「籃球」且屬於「體育」類別的文檔數為例。如果原假設是成立的，即「籃球」和體育類文章沒什麼關聯性，那麼在所有的文章中，「籃球」這個詞都應該是等概率出現，而不管文章是不是體育類的。這個概率具體是多少，我們並不知道，但他應該體現在觀察結果中（就好比拋硬幣的概率是二分之一，可以通過觀察多次拋的結果來大致確定），因此我們可以說這個概率接近

（因為A+B是包含「籃球」的文章數，除以總文檔數就是「籃球」出現的概率，當然，這裡認為在一篇文章中出現即可，而不管出現了幾次）而屬於體育類的文章數為A+C，在這些個文檔中，應該有

篇包含「籃球」這個詞（數量乘以概率嘛）。

但實際有多少呢？考考你（讀者：切，當然是A啦，表格里寫著嘛……）。

此時對這種情況的差值就得出了（套用式（1）的公式），應該是

同樣，我們還可以計算剩下三種情況的差值D12，D21，D22，聰明的讀者一定能自己算出來（讀者：切，明明是自己懶得寫了……）。有了所有觀察值的差值，就可以計算「籃球」與「體育」類文章的開方值

把D11，D12，D21，D22的值分別代入並化簡，可以得到

詞t與類別c的開方值更一般的形式可以寫成

實際上式（2）還可以進一步化簡，注意如果給定了一個文檔集合（例如我們的訓練集）和一個類別，則N，M，N-M（即A+C和B+D）對同一類別文檔中的所有詞來說都是一樣的，而我們只關心一堆詞對某個類別的開方值的大小順序，而並不關心具體的值，因此把它們從式（2）中去掉是完全可以的，故實際計算的時候我們都使用

針對英文純文本的實驗結果表明：作為特徵選擇方法時，開方檢驗和信息增益的效果最佳（相同的分類演算法，使用不同的特徵選擇演算法來得到比較結果）；文檔頻率方法的性能同前兩者大體相當，術語強度方法性能一般；互信息方法的性能最差（文獻[17]）。

但開方檢驗也並非就十全十美了。回頭想想A和B的值是怎麼得出來的，它統計文檔中是否出現詞t，卻不管t在該文檔中出現了幾次，這會使得他對低頻詞有所偏袒（因為它誇大了低頻詞的作用）。甚至會出現有些情況，一個詞在一類文章的每篇文檔中都只出現了一次，其開方值卻大過了在該類文章99%的文檔中出現了10次的詞，其實後面的詞才是更具代表性的，但只因為它出現的文檔數比前面的詞少了「1」，特徵選擇的時候就可能篩掉後面的詞而保留了前者。這就是開方檢驗著名的「低頻詞缺陷「。因此開方檢驗也經常同其他因素如詞頻綜合考慮來揚長避短。

三、信息增益

在信息增益中，重要性的衡量標準就是看特徵能夠為分類系統帶來多少信息，帶來的信息越多，該特徵越重要。

因此先回憶一下資訊理論中有關信息量（就是「熵」）的定義。說有這麼一個變數X，它可能的取值有n多種，分別是x1，x2，……，xn，每一種取到的概率分別是P1，P2，……，Pn，那麼X的熵就定義為：

意思就是一個變數可能的變化越多（反而跟變數具體的取值沒有任何關係，只和值的種類多少以及發生概率有關），它攜帶的信息量就越大。

信息增益是針對一個一個的特徵而言的，就是看一個特徵t，系統有它和沒它的時候信息量各是多少，兩者的差值就是這個特徵給系統帶來的信息量，即增益。系統含有特徵t的時候信息量很好計算，就是剛才的式子，它表示的是包含所有特徵時系統的信息量。

問題是當系統不包含t時，信息量如何計算？我們換個角度想問題，把系統要做的事情想像成這樣：說教室里有很多座位，學生們每次上課進來的時候可以隨便坐，因而變化是很大的（無數種可能的座次情況）；但是現在有一個座位，看黑板很清楚，聽老師講也很清楚，於是校長的小舅子的姐姐的女兒托關係（真輾轉啊），把這個座位定下來了，每次只能給她坐，別人不行，此時情況怎樣？對於座次的可能情況來說，我們很容易看出以下兩種情況是等價的：（1）教室里沒有這個座位；（2）教室里雖然有這個座位，但其他人不能坐（因為反正它也不能參與到變化中來，它是不變的）。

對應到我們的系統中，就是下面的等價：（1）系統不包含特徵t；（2）系統雖然包含特徵t，但是t已經固定了，不能變化。

我們計算分類系統不包含特徵t的時候，就使用情況（2）來代替，就是計算當一個特徵t不能變化時，系統的信息量是多少。這個信息量其實也有專門的名稱，就叫做「條件熵」，條件嘛，自然就是指「t已經固定「這個條件。

但是問題接踵而至，例如一個特徵X，它可能的取值有n多種（x1，x2，……，xn），當計算條件熵而需要把它固定的時候，要把它固定在哪一個值上呢？答案是每一種可能都要固定一下，計算n個值，然後取均值才是條件熵。而取均值也不是簡單的加一加然後除以n，而是要用每個值出現的概率來算平均（簡單理解，就是一個值出現的可能性比較大，固定在它上面時算出來的信息量占的比重就要多一些）。

因此有這樣兩個條件熵的表達式：

這是指特徵X被固定為值xi時的條件熵。

這是指特徵X被固定時的條件熵，注意與上式在意義上的區別。從剛才計算均值的討論可以看出來，第二個式子與第一個式子的關係就是：

具體到我們文本分類系統中的特徵t，t有幾個可能的值呢？注意t是指一個固定的特徵，比如他就是指關鍵詞「經濟」或者「體育」，當我們說特徵「經濟」可能的取值時，實際上只有兩個，「經濟」要麼出現，要麼不出現。一般的，t的取值只有t（代表t出現）和t_cat（代表t不出現），注意系統包含t但t 不出現與系統根本不包含t可是兩回事。

因此固定t時系統的條件熵就有了，為了區別t出現時的符號與特徵t本身的符號，我們用T代表特徵，而用t代表T出現，那麼

因此特徵T給系統帶來的信息增益就可以寫成系統原本的熵與固定特徵T後的條件熵之差：

公式中的東西看上去很多，其實也都很好計算。比如P(Ci)，表示類別Ci出現的概率，其實只要用1除以類別總數就得到了（這是說你平等的看待每個類別而忽略它們的大小時這樣算，如果考慮了大小就要把大小的影響加進去）。再比如P(t)，就是特徵T出現的概率，只要用出現過T的文檔數除以總文檔數就可以了，再比如P(Ci|t)表示出現T的時候，類別Ci出現的概率，只要用出現了T並且屬於類別Ci的文檔數除以出現了T的文檔數就可以了。

從以上討論中可以看出，信息增益也是考慮了特徵出現和不出現兩種情況，與開方檢驗一樣，是比較全面的，因而效果不錯。但信息增益最大的問題還在於它只能考察特徵對整個系統的貢獻，而不能具體到某個類別上，這就使得它只適合用來做所謂「全局」的特徵選擇（指所有的類都使用相同的特徵集合），而無法做「本地」的特徵選擇（每個類別有自己的特徵集合，因為有的詞，對這個類別很有區分度，對另一個類別則無足輕重）。

四、互信息

一個常用的方法是計算文檔中的詞項t與文檔類別c的互信息MI，MI度量的是詞的存在與否給類別c帶來的信息量，互信息的基本定義如下：

應用到文本特徵選擇:

　U、C都是二值隨機變數，當文檔包含詞項t時，U的取值為et=1，否則et=0；當文檔屬於類別c時，C的取值ec=1，否則ec=0，用最大似然估計時，上面的概率值都是通過統計文檔中詞項和類別的數目阿里計算的。於是實際計算公式如下：　　

我們可以對每一個類計算各個詞項與其的互信息，並選取值最大的k個詞項，當然有可能兩個類會選取相同的特徵詞，去重一下即可。

　　互信息度量的是詞項是否被類別包含所帶來的信息量，如果某個詞項均勻的分布在各個類別，那麼I(U;C)=0，當某詞項總是出現在當前類別，而在其他類別中很少出現時，I(U;C)就會比較大。使用互信息能夠保留具有信息含量的詞項的同時，去掉那些沒有信息含量的詞項，從而提高正確率。

五、N-Gram

基於N-Gram的方法是把文章序列，通過大小為N的窗口，形成一個個Group，然後對這些Group做統計，濾除出現頻次較低的Group，把這些Group組成特徵空間，傳入分類器，進行分類。

reference

TF-IDF與餘弦相似性的應用（一）：自動提取關鍵詞 - 阮一峰的網路日誌

文本分類入門（十）特徵選擇演算法之開方檢驗 - Jasper's Java Jacal - BlogJava

文本分類入門（十一）特徵選擇方法之信息增益 - Jasper's Java Jacal - BlogJava

文本特徵選擇 - CodeMeals - 博客園