一種用于文本分類的特征選擇方法

摘要：文本分類是文本信息處理領域一個非常重要的研究方向，為了節省文本分類處理中所需的存儲空間和運算時間，在分類之前用高效的算法減少所需分析的數據是非常必要的。該文介紹了一種文本分類中特征降維的方法。和傳統的方法不同，該文所涉及的特征是從句子中提取的不同長度的詞組，然后用比數比來對其進行特征選擇。實驗結果表明，該文提出的方法與傳統方法相比，提高了文本分類的準確率。

關鍵詞：文本分類；特征提取；特征選擇；比數比

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)34-1762-03

A Feature Selection Method for Text Categorization

ZHOU Han1，2， ZHAO Wei-dong1，2， JI Jun3

(1.The Engineering Research Center for Enterprise Digital Technology， Ministry of Education， Tongji University， Shanghai 200092， China; 2. Research Center of CAD， Tongji University， Shanghai 201804， China; 3. China Petroleum Chemical Corporation Maoming Branch Chemical， Maoming 525011， China)

Abstract: Text categorization is a very important direction in text information process field. In order to save storage space and computing time in text categorization， it is necessary to reduce data which need to be analyzed by effective algorithm before classification. This paper introduces a method of dimensional reduction of features for text categorization. Unlike the traditional way， the feature refer in this article is the phrase of different length extracted from sentence， then use odds ratio to process feature selection. Experimental results show that， the proposed method in this paper has higher accuracy than conventional ones.

Key words: text categorization; feature extraction; feature selection; odds ratio

1 引言

隨著互聯網絡的發展，文本信息充斥著我們的生活，并且還在以迅猛的速度膨脹。在當前GB，TB級的文本集上，人工分類已經不能滿足要求，因此如何有效的將這些文本信息自動加以分類便于管理和利用成為我們今天的一個重大課題，以此為目的的自動文本分類技術也應運而生。文本的表示主要采用向量空間模型（Vector Space Model，VSM），其基本思想是把文本看作向量空間中的一個n維向量(W(t1)，W(t2)，…W(tn))，其中t1， t2，…tn為表示文本的n個特征，W(tk)， k=1，2，…n是第k個特征在該文本中對應的權重。在文本處理上，一般先進行分詞，形成文本特征向量，也就是特征提取，然后進行特征選擇，實現特征降維，最后根據一定的算法，比較文本特征向量與預定義類別的相似度，把文本歸類到最相似的那個預定義類別。常用的分類算法[1]包括簡單的向量距離，樸素貝葉斯，支持向量機，神經網絡和K最近鄰居算法等。

文本分類的一個難點是特征空間的高維性和文檔表示向量的稀疏性，中文的詞條有二十多萬條，為了降低特征空間的維數，提高分類的效率和精度，尋找有效的特征提取和選擇算法成為文本分類中一項非常重要的任務。

傳統的特征處理方式[2]使用向量空間中的“詞袋法”(BAG-OF-WORDS)來表示文本。這種方法有一個關鍵的假設，就是文章中出現的詞條的次序是無關緊要的，不考慮詞條的位置信息以及文本結構，把文本看成是一系列無序詞的組合。主要方法是首先對文本進行分詞，把單個的詞作為特征，然后采用一定的算法對其進行特征選擇，只把詞而非詞組作為特征向量。雖然大大降低了特征向量空間的維數，但往往忽略了上下文的聯系，每個向量都是孤立的毫無聯系的詞語，從而限制了整個文本分類系統的準確性。本文所用的特征向量是經過選擇后的詞組向量，實驗表明，這樣做，雖然使特征向量空間相對于詞向量空間有所增大，但是卻遠遠低于完全把詞組作為特征的向量空間，最重要的是這樣做可以有效提高文本分類的準確率。

2 特征提取與特征選擇

2.1 特征提取

文本分類是按照它的內容把自然語言構成的文本劃分到預先定義的類別中，把一篇文章分成很多的特征向量，并用這些向量來表示文本信息是最常用的方式。，每篇文章都是一個附帶權值的特征向量的集合，將這些向量從完整的文本信息中提取分離出來的過程就叫做特征提取。在大多數的文本分類系統[2]中，都是將詞作為特征向量進行提取，這種方式的缺點在于把每個詞都當成孤立的個體，忽略了詞與詞之間的語義聯系，所以很多學者嘗試把多個詞組成的詞組作為特征向量。但是大量的研究[3]表明，基于詞組的向量表示方法并沒有提高文本分類的效率，因為：

1) 詞組向量非常龐大，將會造成更大的特征空間。

2) 這些詞組向量的權值分配往往非常的不平均。

3) 會形成很多冗余的特征向量。

4) 含有很多噪音。

所以一般認為選取詞作為特征項要優于詞組。本文提出的詞組特征提取方法，不同于傳統的方式，把所有的詞組作為特征向量。這里詞組特征是從句子中提取出的不同長度的詞組，具體方法將在后面詳述。

2.2 特征選擇

特征選擇即根據一定的策略，去除那些表現力不強的詞匯，從而實現特征降維。這需要首先進行預處理，比如可以將對分類無幫助的詞性對應的詞去掉，在大多數的文本分類系統中，副詞和形容詞等往往對于分類起不到太大作用，這些詞的出現將會使得向量空間變得非常冗余，所以應該去掉。普遍認為在多數分類系統中，只有名詞和動詞特征向量對后面的分類具有積極意義。而在動詞和名詞中，又可以通過人工確定停用詞并手動將其刪除，對于同義詞，可以進行歸并，例如電腦和計算機，可認為是同一個向量，從而減少冗余信息，對于剩下的特征向量我們仍然需要用高效的算法進一步的篩選。常用的特征選擇算法包括：信息增益[4]，互信息[4]，X2統計量[4]，文檔頻率[4]，頻率差法[4]，低損降維[4]和比數比[4]。這些方法的基本思想都是對每一特征計算某種統計度量值，然后設定一個閥值，過濾掉度量值小于閥值的特征，把剩下的作為有效特征。

通過研究[5]表明：用比數比（odds ratio）作為特征選擇算法的分類系統效果最好，因此本文采用比數比作為特征選擇的算法。在醫學當中，比數比通常出現在調查研究或病例對照研究中，用于表示某種因素的影響強度。其定義就是存在某因素時發病概率與不發病概率的比值與不存在某因素時發病概率與不發病概率的比值的比。而在文本分類的應用當中，比數比指的是一個特征向量屬于某個類別的概率與它不屬于這個類別的概率之比：

■

其中：Cpos表示正樣本的情況，Cneg表示負樣本的情況，P（t|Cpos）表示向量t屬于類別c的概率，P（t|Cneg）表示向量t不屬于類別c的概率，比數比考察本類別和其他所有類別的差異，將其它類別全部看作負樣本，這是它的獨到之處。

3 算法實現

前文提到在應用特征選擇算法之前，需要進行預處理，分為兩部分，文本預處理和詞庫預處理，將處理后的文本進行分詞也就是特征提取，得到初步的向量空間，然后用OR對其進行特征選擇得到最終的向量空間，流程如圖1。

首先對待分類文本進行預處理，把html標簽、標點符號等等非文字信息過濾掉。然后對處理后的文本進行分詞，即特征提取， 由于分詞都是基于詞庫的，所以可以在進行特征選擇之前，對詞庫進行預處理將不必要的特征從詞庫中剔除，在特征提取之時就力求精簡，使很多冗余向量在應用特征選擇算法之前就被屏蔽掉，從而提高系統效率，此時獲得的初步向量空間由詞和所有詞組構成，將這些特征向量用比數比算法進行處理，所有詞向量繼續保留，而詞組向量則按所包含詞的數量進行分類。每個子類中比數比最高的詞組將保留，其余將被丟棄，所以經過處理后的向量既不是單純的詞向量，也不是所有的詞組向量。例如當原句為“高效特征選擇算法”時，用比數比處理特征向量的方法如表1。

在這個例子中，原句經過分詞形成了最多由4個詞組成的詞組，那么先將其按詞的個數分類，然后在各個子類中選擇其中比數比最高的那個詞組。例如在由2個詞組成的詞組中，“特征選擇”的比數比（OR）最高，則保留之，其余丟棄，所以最后經過特征選擇后保留的特征向量集包括：{“高效”，“特征”，“選擇”，“算法”，“特征選擇”，“特征選擇算法”，“高效特征選擇算法”}，這些向量將會被用于后面的分類工作。

4 實驗結果與分析

該文對此特征選擇方法的效率進行了實驗，其數據為來自某市政府網站的電子信件數據庫。信件總共有5132封，分為教育，交通，環保，房地產，政府工作，能源等6個大類。將其中5000封作為訓練集，其余132封作為測試集，首先將經過比數比過濾后的特征向量個數與將所有詞組作為特征向量的個數進行比較。訓練集中6大類的信件數量如表2。

經過比數比過濾后，特征向量的數量比把所有詞組作為特征的向量數量大幅減少，具體如表3。

實驗結果表明用比數比進行特征選擇后，特征向量比把所有詞組作為特征向量大為縮減，從而比后者提高了效率，雖然比單純用詞作為向量的方法增加了向量空間，但是會增加整個系統文本分類的準確率，本文將5000封信件數據作為訓練集，然后分別選取詞，詞組和經過比數比特征選擇后的詞組作為特征向量，對132封測試信件進行分類，并比較三種方法的準確率，具體數據如表4所示。

5 總結

試驗結果表明把經過比數比特征選擇后的詞組作為特征向量具有較高的分類準確率，針對向量空間的選擇對文本分類準確率的影響，還需要更多的理論研究和實驗。

參考文獻：

[1] 劉麗珍，宋瀚濤.文本分類中的特征選擇[J].計算機工程，2004(2).

[2] 程澤凱，陸小藝.文本分類中的特征選擇[J].安徽工業大學學報，2004(7).

[3] Ko Y J，Park J，Seo J.Imporving text categorization using the importance of sentences[J].Information Processing and Management，2004(4).

[4] 周茜，趙明生，扈旻.中文文本分類中的特征選擇研究[J].中文信息學報，2005，10(1).

[5] 胡佳妮，徐蔚然，郭軍，等.文本分類中的特征選擇算法研究[J].光通信研究，2005(3).

[6] Cohen W W，Singer Y.Context-sensitive learning methods for text categorization[C].Proc of the 19th Int'l ACM SIGIR Conf on Research and Development in Information Retrieval，Zurich，1996:307-315.

[7] Baker L D，McCallum A K.Distributional clustering of words for text classification[C].Proceedings of SIGIR，1998.

[8] Weiss S M，White B F，Apt C.Lightweight document matching for help-desk

applications[J].IEEE Intelligent Systems，2000，15(2).[9] Flach P A.On the Logic of Hypothesis Generation[J].Applied LogicSeries，2000，18(6):89-106，

[10] Sebastiani F.Machine Learning in Automated Text Categorization[J].ACM Computing Surveys，2002，34(1):1-47.