基於搜索的短文本分類算法研究-AET

0 引言

文本分類(Text Classification)是指在給定的分類體系下，由計算機通過某種分類算法將未知類別的文本進行自動歸類的過程。最近十幾年，文本分類得到了迅速的發展，並且被廣泛應用到許多領域，包括：數字圖書館、網頁分類、垃圾電子郵件過濾等。到目前為止，已經有許多基於統計學理論和機器學習的文本分類方法，如決策樹（Decision Tree）、貝葉斯方法、KNN、神經網絡、支持向量機(SVM)等^[1]。然而，這些分類方法的研究和應用都是基於長文本的，而目前短文本在網絡上使用越來越普遍。最近新興起的微博客的最大的特點就是“微”，一般發佈的消息只能是隻言片語。著名流量統計網站ALEXA的數據顯示，Twitter日均訪問量已近2 000萬人次，在美國、英國、加拿大等地的網站排名中均列前15位。在專業或者垂直搜索領域，由於資源限制，無法對全文進行處理，轉而根據文章標題或文章摘要進行分類。這些應用場合都需要短文本分類技術。針對實際的需求以及傳統方法的不足，本文提出了一種新的分類方法，利用搜索實現基於類似NaiveBayes的文本分類方法。對比實驗表明，在短文本的分類上，此方法比傳統的分類方法提高了準確率和分類速度。

1 相關工作介紹

在過去的四十多年中，許多關於文本分類的研究工作都是圍繞著Salton提出的向量空間模型(VSM)展開的，向量空間模型的基本思想是以向量來表示文本：(W₁，W₂，…，W_n)，首先將文本進行分詞，由這些詞作為向量的維數，用詞頻來表示特徵項對應的向量分量，詞頻計算方法主要運用TF-IDF公式。對於向量空間法的研究工作主要集中在特徵選取和特徵權重的調整上來提高分類的性能，如陸玉昌先生在特徵選取中利用評估函數代替TF-IDF公式進行權值調整^[2]。

神經網絡學習算法在文本分類中的研究和應用也非常廣泛，其中最流行的神經網絡算法是1986年由RUMELHARD D E和MCCLELLAND J L提出的後向傳播算法(簡稱BP算法)^[3]。由於BP算法存在收斂速度慢、容易陷入局部極小值等問題，後人對BP算法進行了多方面的改進，如李曉峰提出了BP神經網絡動態全參數自動調整學習算法^[4]。神經網絡擁有很好的對噪音數據的承受能力和文本分類能力，但是需要大量的參數，這些通常主要靠經驗確定。另外神經網絡需要很長的訓練時間，因此它適用於有足夠長訓練時間的應用。

王建會等提出了基於互依賴和等效半徑、簡單但高效的分類算法SECTILE^[5]，該方法提出互依賴（Mutual Dependence，MD）模型，並將其與N-gram結合起來進行特徵屬性選擇，提高了屬性選擇的準確性，實現了有效地降維。引入等效半徑(Equivalent Radius，ER)的概念,用基於等效半徑的相對距離代替傳統的歐氏距離，提高了分類精度。SECTILE分類算法計算複雜度低，分類模型容易更新，適用於大規模信息樣本分類場合。

石志偉等提出了向量空間法和k近鄰的組合分類方法^[6]，該方法將整個實例空間劃分為正實例、負實例和混合實例三部分，根據查詢實例落入不同的區域調用不同的分類算法。該方法充分利用了向量空間法分類速度快和k近鄰方法分類精度高的優勢。

以上提到的各種分類方法都適用於長文本的分類，由於短文本相對於長文本要短得多，文本中的特徵數很少，並且文本之間很少含有相同的特徵，因此傳統的文本分類方法並不適合短文本分類。目前專門研究短文本分類的工作還較少，大致分為兩種研究方向：一種是通過外部資源來增加文本之間共享的特徵，豐富文本的上下文，例如Wikipedia被作為外部資源引入短文本分類中

蒲強等提出基於獨立分量分析（Independent Component Analysis，ICA）和潛在語義分析（Latent Semantic Analysis，LSA）的短文本分類方法^[8]，該方法首先通過LSA對文本進行預處理，然後對處理結果再進行獨立分量分析。LSA利用奇異值分解（Singular Value Decomposition，SVD）降秩方法實現信息抽取和噪聲去除，將文檔的高維表示投影在低維的潛在語義空間中，從而呈現出潛在的語義結構。然而對原始詞——文檔矩陣進行SVD，選取最大的一些奇異值對應的特徵作為潛在語義空間，目前沒有理論證明奇異值最大的那些特徵具有最好的分類能力，所以在該潛在語義空間上進行文本分類，分類效果並沒有得到改善。

滕少華等提出基於條件隨機場（Conditional Random Fields，CRFs）的短文本分類方法^[9]，該方法認為短文本通常集中於一個主題，從而文本中的特徵也具有很強的相關性。根據這種性質，該方法利用中文分詞中的字標註方法，將短文本分類問題轉化成序列標註問題，從而可以使用CRFs來解決短文本分類問題。然而CRFs依賴於高置信度特徵，高置信度特徵也可以引入干擾，這樣就很容易導致分詞錯誤，這種困難很難依靠CRFs自身來解決。雖然可以通過對基於CRFs的分詞結果進行後處理來解決該問題，但是這種方法有它的侷限性，只能使用基於CRFs的中文分詞。

綜上所述，目前的短文本分類方法不能有效地選擇那些分類能力好的特徵，分類準確度低，分類速度慢；或者依賴於中文分詞系統，擴展性差。本文提出的基於搜索的Na?觙veBayes文本分類方法在這些方面進行了改進。

2 基於搜索的樸素貝葉斯分類算法

基於搜索的樸素貝葉斯文本分類是將搜索技術應用到文本分類中，並對樸素貝葉斯分類算法進行改進，從而實現的一種適合短文本分類的分類方法。分類算法如下：

令C={c₁，c₂，…，c_m}是預定義的類別集，D={d₁，d₂，…，d_n}是待分類的文檔集，d={w₁，w₂，…，w_n}是一個文檔的特徵向量，文檔d_i

式(2)、式(4)中，|c|為文本的類別數，分子上的1是為了防止出現概率為零的情況進行的加權處理。

為了計算簡便，不妨在選取訓練數據時規定各類別中的文本數一樣多。這樣，對於每一個文本類別來說，先驗概率是相等的，計算P(c_j)的過程也可以忽略不計。計算貝葉斯概率也就簡化成了計算文檔d_i屬於類別c_j的後驗概率：

在式(5)中，對於每一類別來說，分母部分N(c_j)+|c|是相等的，即不影響屬於每一類別的概率大小比較，這樣就直接計算：

而為了防止出現負無窮和零的情況，只需要知道每一個屬性(詞)在指定類別中出現的文檔個數，即N(w_i|c_j)。

結合上面的公式推導，可以將基於搜索的NaiveBayes文本分類算法描述如下：

(1)假定有m個類別C₁

(2)給定一個沒有類標號的數據樣本X，對其進行中文分詞(分詞系統要和步驟(1)用到的分詞系統保持一致)，每個詞對應一個屬性，分別為W₁，W₂，…，W_n；

(3)求將數據樣本X分配給類別C_j的概率，即：

換言之，X被分配到使P(w|c_i)最大的類別C_i。

注意：步驟(1)也可以看作是建立分類模型，此步不影響分類的速度，因為建立分類模型是在進行文本分類之前做的。基於搜索的NaiveBayes分類器模型是對已知類標號的訓練數據集建立的索引，並且各個類別的訓練數據文本數是相等的。這也是基於搜索的NaiveBayes分類器和其他分類器的不同之處。為了提高速度，本文使用了Lucene.Net搜索技術。Lucene.Net中自帶的StandardAnalyzer分詞器是以字為單位索引的，對於中文文本分類來說，按單字分詞會影響分類的精度，所以本文使用了KTDictSeg分詞系統，KTDictSeg是由KaiToo搜索開發的一款基於字典的開源的中英文分詞系統。KTDictSeg可以識別中文人名，還有對Lucene.net 的支持，提供KTDictSegAnalyzer 分析器給Lucene.net。

分類器效率的評估結果可以有多種，比如分類的準確率、速度、可規模性等。而評估的方法也有多種，最簡單的是保持(Holdout)方法，即使用類標號已知的數據來測試分類器。在認為分類器的準確率可以接受時，就可以利用此分類器對類標號未知的數據進行分類預測。

3 實驗及結果分析

對於中文文本分類而言，目前還沒有標準的語料庫可供使用。因此，本文使用搜狗實驗室整理的語料庫(SogouC.reduced.20061127)，此語料庫包含了九個類別，分別是財經、IT、健康、體育、旅遊、教育、招聘、文化、軍事，每一類包含1 990篇文章。對此語料庫做一下簡單整理，從每一類中隨機選出160篇文章作為測試數據，用剩餘的1 830篇文章作為訓練數據建立分類模型。用準備好的測試數據對基於搜索的NaiveBayes文本分類器和weka的NaiveBayes文本分類器進行測試，測試結果如表1所示。

從表1可以看出，基於搜索的NaiveBayes分類器和weka的NaiveBayes分類器不相上下。但是，為了體現基於搜索的NaiveBayes分類器對於短文本分類的優越性，對這1 440篇測試數據做一下簡單處理後再次進行測試，即每一類中包含50字以內的文本50篇、50～200字的文本50篇、200～1 000字的文本50篇和1 000字以上的文本50篇。這樣測試數據就按照文本字數的多少分為了不同的等級，並且測試數據文本數也增加到了1 800篇。然後用整理後的測試數據對兩種分類器進行測試，測試結果如表2所示。

根據表2的數據繪製出分類準確率的曲線圖，如圖1所示。

通過圖1可以清楚地看到，對於100字以內的短文本的分類，基於搜索的NaiveBayes分類器在分類精度方面表現出了優越的性能。通過表2和表1的比較也不難發現，對於1 440篇長文本的分類，基於搜索的NaiveBayes分類器耗時12.587 5 s；而對於加入了短文本的1 800篇文本的分類，基於搜索的NaiveBayes分類器耗時13.006 2 s。從數字上可以看出，對於短文本的分類，基於搜索的NaiveBayes分類器在分類速度上也明顯提高。

這說明基於搜索的NaiveBayes分類方法對短文本的處理得到了很好的分類效果，並且並沒有因為選取全部的文本特徵而降低分類速度，相反，由於搜索技術的引入，從某種程度上還提高了文本分類的速度。

4 結論

本文針對傳統的文本分類方法對短文本分類的不足，提出了基於搜索的NaiveBayes文本分類方法。該方法與傳統的文本分類方法的不同之處在於，它將搜索引擎技術應用到了文本分類中，並對樸素貝葉斯分類算法進行了改進。實驗結果表明，對於短本文的分類，基於搜索的NaiveBayes分類方法不僅大大提高了分類的準確度，同時降低了時間複雜度。另外，在文本特徵提取和中文文本停詞的處理方面，針對不同的應用背景還需要做進一步的研究。實驗用的語料庫不是標準的語料庫，僅僅有17 910篇文章，因此，實驗的規模有待進一步擴大。在應用前景方面，隨著通信技術和互聯網的發展，電子郵件、短信、微博信息等各種短文本信息迅速增加，基於搜索的NaiveBayes文本分類器必將會得到廣泛的應用。

參考文獻

[1] Wu Xindong，KUMAR V，QUINLAN J R，et al.Top 10 algorithms in data mining[J].Knowl.Inf.Syst.，2008(14)：24-27.

[2] 陸玉昌，魯明羽，李凡，等.向量空間法中單詞權重函數的分析和構造[J].計算機研究與發展，2002，39(10)：1205-1210.

[3] RUMELHART D E，MCCLELLAND J L.Parallel distributed processing：explorations in microstructure of cognition，Vol.1：Foundations[M].Cambridge：MIT Press，1986：318-364.

[4] 李曉峰.動態全參數自調整BP神經網絡預測模型的建立[J].預測，2001，20(3)：69-71.

[5] 王建會，王洪偉，申展，等.一種實用高效的文本分類算法[J].計算機研究與發展，2005，42(1)：85-93.

[6] 石志偉，劉濤，吳功宜.一種快速高效的文本分類方法[J].計算機工程與應用，2005，41(29)：180-183.

[7] SCHONHOFEN P.Identifying document topics using the Wikipedia category network[C].Proc.the IEEE/WIC/ACM International Conference on Web Intelligence，2006：456-462.

[8] Pu Qiang，Yang Guowei.Short-text classification based on ICA and LSA[C].Berlin：Springer-Verlag Berlin/Heidelberg，2006：265-270.

[9] 滕少華.基於CRFs的中文分詞和短文本分類技術[D].北京：清華大學，2009.

作者信息:

康 衛1，邱紅哲2，焦鼕鼕1，房志奇1，於寅虎1

(1.華北計算機系統工程研究所，北京100083；2.北京航天飛行控制中心，北京100094）

閱讀更多 電子技術應用 的文章

關鍵字: 短文 分類 電子郵件