基于聯合提取特征的粗糙集文本分類技術研究

摘要：重點研究了文本的特征提取，通過對互信息和χ2統計的研究，根據其各自的缺陷，提出了一種新的特征提取算法——聯合特征提取算法（CEFA）。通過CEFA可以提取出更具代表性的特征項，利用粗糙集優越的約減性構造文本分類系統，提取決策規則，對文本進行分類。實驗表明該方法分類準確度較高。

關鍵詞：文本分類； 粗糙集； 互信息；χ2統計； 聯合提取特征

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2007)07－0097－02

Internet容納了海量的各種類型的源信息。隨著Internet的飛速發展，越來越多的人使用網絡來查找有用的信息。如何在海量的信息中獲得有價值的模式與知識是當前數據挖掘的主要目標[3]。搜索引擎是目前從網絡獲取有價值信息的重要途徑，然而目前的搜索引擎大部分都基于關鍵字進行查找，返回的信息大部分與目標信息無關。文本分類的目標是在分析文本內容的基礎上，為每個文本分配一個比較合適的類別，從而提高搜索引擎的查準率。

1粗糙集理論

粗糙集理論是波蘭華沙理工大學Pawlak教授于1982年提出的，它不需要任何先驗信息，能夠有效地分析和處理不完備、不一致、不精確的數據，已經在知識獲取、規則提取、機器學習、決策分析、模式識別、數據挖掘等領域獲得了廣泛的應用。利用粗糙集進行文本分類會涉及粗糙集的決策表、屬性約減等知識。

1．1不可分辨關系與決策表

條件屬性C和決策屬性D的等價關系IND(C)和IND(D)的等價類分別稱為條件類和決策類。在文本分類中，從文本提出的特征詞用做規則的前提條件；文本所屬的類別用做規則的決策。

1．2決策表的屬性約簡與規則的化簡

屬性約簡是粗糙集理論處理信息系統的重要手段。它在保持信息系統分類能力不變的前提下，導出問題的決策或分類規則。

（P），則稱Q是P的一個絕對約簡。

決策表約簡步驟如下：

（1）進行條件屬性的簡化，即從決策表中消去某些列；

（2）消去重復的行；

（3）消去屬性的冗余值。

決策表的簡化就是化簡決策表中的條件屬性?；喓蟮臎Q策表具有化簡前的功能，但具有更少的條件屬性，化簡的結果可以作為文本分類的規則。

2文本分類的關鍵技術

構成文本詞匯的數量是相當大的，因此，表示文本的向量空間的維數也相當大，可以達到幾萬維，如何用最少的詞匯即特征詞來表示文本是提高文本分類效率的關鍵。當前特征詞的提取方法有信息增益、互信息、 χ2統計等。

2．1互信息

互信息被普遍地應用于相關詞統計語言建模中[2]。其計算公式如下：

2．3聯合特征提取新算法

上述分析表明互信息與χ2統計在一定程度上存在互補性。在特征提取時互信息可能會濾掉那些有用的但P(W|Ci)相等時的高頻詞；而χ2可能會濾掉那些有用的低頻詞。因此，本文提出了一種聯合特征提取的方法——CEFA（Combined Extract Features Algorithm）。它具備了互信息與χ2統計的優點，用以提高文本表示質量。其算法描述如下：

（1）分別使用互信息和χ2統計計算各詞的權重。

（2）將各算法計算出來的權重按權重的大小排序。

（3）在各權重數組中取前N+n項（假定取N個特征詞），并求出這兩個數組中的交集，交集的個數為K。

（4）若K=N，轉（7）；若K＜N，轉（6）；若K＞N，轉（5）。

（5）n=n-1，轉（3）。

（6）n=n+1，轉（3）。

（7）結束。

3基于粗糙集的文本分類系統

3．1構建決策表

將特征項集合作為規則的條件屬性集，文本所屬的類別作為決策表的決策屬性集，進而可以構建如表1所示的決策表。

3．2基于粗糙集的文本分類規則提取過程

基于粗糙集理論并結合文本特征提取的新算法CEFA的文本分類系統處理過程如圖1所示。

（1）從語料庫中選取訓練文本，每個文本由人工標上唯一的類別標志；

（2）對訓練文本進行分次，用上述聯合方法進行特征提取，提取出關鍵詞；

（3）將特征項的權值進行離散化處理；

（4）構造決策表，以關鍵詞向量集為決策表的條件屬性集，文本所屬的類別集為決策表的決策屬性集；

（5）利用上面提到的決策表屬性約簡方法，對條件屬性進行約簡，并輸出規則。

3．3模式評價

模式評價采用分類正確率的評估方法，其內容是所有參與分類的文本中正確分出的文本數與人工分類的文本數的比率，用來評價分類效果的好壞。其公式如下：

正確率＝分類出的正確文本數/實際分類的文本數（4）

4試驗與分析

實驗采用的是中國科學院計算研究所的中文自然語言處理開放平臺（http://www.nlp.org.cn/）上提供的語料庫，共有經濟、政治、軍事、教育、計算機中五個類共1 499篇文章。選取其中的941篇文章作為訓練文本，剩余的558篇文章作為測試文本，分別采用互信息、χ2統計和本文提出的特征提取方法進行實驗。表2為分類的實驗結果。

從表2可以看出，使用CEFA和單獨使用任何一個所提取的特征項用于分類，其結果顯而易見。使用兩者聯合分類的正確率要高于單獨使用任何一種。因此，CEFA的分類準確度高，具有較高的執行效率。

參考文獻：

[1]王國胤.Rough集理論與知識獲取[M].西安:西安交通大學出版社，2001.

[2]YANG Yiming， PEDERSEN J O. A comparative study on feature selection in text categorization: proc.of the 14th Internation Conference on Machine Learning[C]//Nashvile Tennessee， USA: Morgan Kaufmann， 1997:412－420.

[3]龐劍鋒，卜東波，白碩.基于向量空間模型的文本自動分類系統的研究與實現[J].計算機應用研究，2001，18(9):23－26.

[4]McCALLUM A， NIGAMK. A comparison of event models for naive bayes text categorization[C]//AAAI’98 Workshop on Learning for Text Categorization， 1998.

[5]魯松，李曉黎，白碩，等.文檔中詞語權重計算方法的改進[J].中文信息學報，2000，14(6):8－13.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”