文本分類方法介紹N-gram

N-gram技術曾被廣泛地用來進行文本壓縮、檢查拼寫錯誤、加速字符串查找等。後來該技術又應用在自然語言處理自動化處理，例如自動分類、自動索引、超鏈的自動生成、文獻檢索、文本的切分等。

目前N-gram最為有用的就是自然語言的自動分類功能。基於n-gram的自動分類方法有兩大類，一類是人工幹預的分類（Classification），又稱分類;一類是無人工幹預的分類（Clustering），又稱聚類。人工幹預的分類，是指人工預先分好類，然後計算機根據特定算法自動地將新添加到資料庫的文獻劃歸某一類。這類方法缺點是，人們須預先具備關於整個文獻庫和分類的知識。無人工幹預的分類，是指計算機自動地識別文獻組（集合），人們勿需預先具備關於整個文獻庫和分類的知識。

（1）特點：N-gram項的生成：為了得到字符串中結尾部分的字符串，對不夠n的字符串追加空格。如：Text的3-gram項為_Te、Tex、ext、xt_、t__。類的表示：先計算類別中所有訓練文本的n-gram項的詞頻，然後按詞頻對其由大到小進行排序，最後保留從第n（實驗中等於300）項開始的k個n-gram項作為此類的特徵值。Note: These profiles are for explanatory purpose only and do not reflect real n-gram frequency statistics.
（2）優點：容錯性強，可以允許文本中有拼寫錯誤等噪聲。
（3）用途：區分測試文檔是何種語言，即語言分類；自動文本分類Bayes分類器是一個性能很好的線性分類器，但是它假設文檔的每個分類特徵屬性間是相互獨立的，這顯然是不成立的。假設di={wi1,wi2,…,win}為一任意文檔，它屬於文檔類C={c1, c2,…, ck}中的某一類cj。根據Bayes分類器有：如果使用Bayes網絡來描述特徵屬性間的聯繫，則失去了Bayes模型的簡單性和線性特徵。我們使用了統計語言學中的N-Gram模型，它假設一個詞在文檔中某個位置出現的概率僅與它之前的n-1個詞有關，即：我們可以得到在某個類別c的文檔集中，w1,w2,…,wT出現的概率為：這樣放鬆了Bayes模型中每個特徵屬性相互獨立的假設，在計算一個文檔在某個類別中的概率時考慮了文本中一些特徵屬性間的相互聯繫。對於文檔中的特徵屬性wi，我們使用N-gram的方法進行生成，這樣使特徵屬性生成的過程獨立於領域、與時間和詞典無關，分類器對詞法方面的噪聲不敏感。直觀地來說，概率 定義1在文檔d中，N-gram項t的頻度用它在d中出現的次數tf表示。定義2在文檔類c中，N-gram項t的分散度用c中包含t的文檔數目df表示。df越大，則t在c中越分散；反之，越不分散。定義3在文檔集D中，N-gram項t的集中度用D中包含t的文檔類數目cf表示。cf越小，則t在D中的越集中；反之，越不集中。直觀地，對於N-gram項t，其在文檔中的頻度越高、在文檔類裡的分散度越大、在訓練文檔集內的集中度越強，則它對分類越有用，即分辨度越強。不過，目前還沒有找到很好的數學方法來綜合頻度、分散度和集中度這三個因素，使得選出的文檔屬性能夠獲得最優分類效果。為了減少提取不必要的N-Gram項，在提取N-gram項時加如下兩個約束條件：約束1對於預先給定的最小頻度值min-tf，在文檔d中某一N-gram項t被提取的先決條件是它在d中的tf ³min-tf。約束2對於預先給定的最小分散度值min-df，在文檔類c中某一N-gram項t被提取的先決條件是它在c中的df ³min-df。在實驗中，我們一般取min-tf和min-df為2。一種直接的N-gram項提取方法是只掃描一遍文檔，一次性將所有滿足上述兩個約束條件的N-gram項取出。由於只需掃描一遍文檔，這種方法對於較小的訓練文檔庫是有效的。但對於大訓練庫，則需要很大的內存空間。否則，就得在內存和外存之間不斷交換中間結果。這裡採用一種分步提取的方法，其基本思想是：先提取符合約束條件的1-gram項；從選擇得到的1-gram項構造候選2-gram項，剔除其中不符合約束條件的候選項，得到真正需要的2-gram項。依此方法，提取其它N-gram（N=3,4,…）項。為了說明N-grams提取算法，先給出一個定義和引理。定義4（子項） 若有i-Gram和j-Gram（i ³ j），且j-Gram包含在i-Gram中，則稱j-Gram為i-Gram的子項，記為j-Gram Í i-Gram。性質1若有i-Gram滿足約束1和2，則i-Gram的所有子項都滿足約束1和約束2。輸入：文檔庫D、min-tf、min-df和max-N(N的最大值)。輸出：滿足約束條件1和2的N-Gram項的集合S（N=1~max-N）。1.       求1-Gram項集合S1：逐個掃描文檔庫D中的文檔，提取所有1-Gram項，拋棄不滿足約束1和約束2的項，得到1-Gram項集合S1；2.       求2-Gram項集合S2：將S1中的項兩兩組合，得到候選2-Gram項集合C2。拋棄C2中不滿足約束1和約束2的項，得到2-Gram項集合S2；3.       求i-Gram項集合Si(i=3~max-M)：a)      由Si-1(i=2-max-M)求候選i-Gram項集合Ci；b)     對於Si-1中的任意兩項tm、tn，tm (k)和tn(k) (k=1~ (i-1))分別表示tm和tn中的第k個字。若tm (k+1)=tn(k)(k=1~(i-2))，則Ci =CiÈ tm tn(i-1)；c)      拋棄Ci中不滿足約束1和約束2的項，得到i-Gram項集合Si。使用N-Gram項進行文本分類，最基本的要求是所選擇的N-Gram項能夠覆蓋文檔中的詞。因此，並非N-Gram項越多越好。這就涉及如何選擇參數N的問題。根據對中文文檔中詞的字數構成與分布的統計分析，發現中文文檔中主要詞條為１字、２字、３字和４字詞條，因此，用這些詞條可以比較完整地表達文檔語義。這樣意味著在用N-Gram進行文檔分類時，只需取1-Gram、2-Gram、3-Gram和4-Gram項，即最大的N值取4。