韓 玉，李美聰，郭新辰

(1.東北電力大學 理學院，吉林 吉林 132012；2.海南熱帶海洋學院 數學系，三亞 572022)

?

基于粗糙集理論的文本分類屬性約簡算法

韓 玉1，李美聰1，郭新辰2

(1.東北電力大學 理學院，吉林 吉林 132012；2.海南熱帶海洋學院 數學系，三亞 572022)

針對文本分類的特征空間高維問題，本文提出了一種基于粗糙集的屬性約簡算法及其改進的約簡算法。利用該算法有效降低了文本特征向量的維數。通過利用20 Newsgroups數據集進行試驗測試，在召回率、準確率和F-1度的指標上均具有較明顯的優(yōu)勢。

粗糙集；屬性約簡；文本分類

文本分類[1-2]是指根據帶有類別的文本集合的特點，根據每一個類別的文本子集合的共有特點，找出一個分類函數或分類模型分類器，根據該模型可以把其他文本映射到已有類別中的一個，從而實現自動對文本分類。粗糙集理論[3]是建立在分類機制的基礎上的，它將分類理解為在特定空間上的等價關系，而等價關系構成了對該空間的劃分，它將知識理解為對數據的劃分，每一被劃分的集合稱為概念，其主要思想是利用己知的知識庫，將不精確或不確定的知識用己知的知識庫中的知識來近似刻畫。該理論與其他處理不確定不精確問題理論的區(qū)別是：它無需提供問題所需處理的數據集合之外的任何先驗信息，因此和其它理論有很強的互補性。

在文本分類和粗糙集理論的基礎上，提出了基于粗糙集的文本分類系統(tǒng)[4]；研究了粗糙集理論中的屬性約簡算法，并找出合適的用于啟發(fā)式屬性約簡的屬性重要性衡量方法；對于粗糙集理論中的啟發(fā)式屬性約簡算法進行改進，根據此約簡算法提出一個基于改進啟發(fā)式屬性約簡的粗糙集文本分類系統(tǒng)，實驗結果表明：將改進后的屬性約簡算法運用在文本分類模型中，能夠得到較好的分類效果。

1 基于粗糙集理論的屬性約簡

1.1 粗糙集理論

1.2 基于粗糙集的屬性約簡

1.2.1 屬性約簡

1.2.2 模型的建立(特征選擇[10])

表1 文本分類決策表

在文本分類中，此決策表有如下特點：條件屬性集規(guī)模龐大，即n值很大，原因是文本向量空間的高維性。因此本文后續(xù)工作就是對文本進行降維。

1.3 屬性約簡算法及其改進算法

1.3.1 屬性約簡算法的描述

為了利用粗糙集理論中屬性重要性的相關結論，首先介紹幾個重要的定義。

擴張分辨能力的大小可以反映屬性對所屬集合的繼續(xù)分類所產生的影響能力，當IaADD=0時，說明屬性a對子集B的分類能力不產生影響，不應該繼續(xù)添加該屬性。

縮減分辨能力的大小也可以反映屬性對所屬集合的繼續(xù)分類所產生的影響能力，當IaSUB=0時，說明屬性a對子集B的分類能力不產生影響，可以刪減該屬性。

通過對屬性子集的擴張分辨能力和屬性子集的縮減分辨能力的定義，本文定義以下屬性約簡算法：

第一步：求解S的屬性集中條件屬性集C的核R=CORE(C)；

第二步：根據屬性子集的縮減分辨能力IaSUB對所有屬性進行排序；

第三步：按照IaSUB從大到小的順序依次將屬性ai加入到約簡集中，并判斷R=R∪{ai}是否是S的一個約簡集，如果是，則輸出R=R∪{ai}，如果不是，則C=C-{ai}，并繼續(xù)執(zhí)行第三步。

2.3.2 改進的屬性約簡算法

本文將粗糙集理論應用于文本分類。對于屬性的重要性評價主要有兩種：其一是基于特征選擇的屬性評價標準[11]；其二是基于粗糙集理論本身的屬性評價標準[12]。

由于屬性約簡算法中存在很多需要屬性核約簡的工作量，因此對屬性約簡算法的改進可以增加屬性的重要性權重，因此綜合粗糙集理論和文本特征選擇的屬性重要性評價，根據重要性進行約簡，以下定義評價公式。

定義3：文本特征選擇屬性重要性采用CHI，其特征選擇性能在文本分類中效果優(yōu)于其它方法，具體公式如下：

例1：I do believe this is a critical need for Americans. I do believe that we can have in this country a health care system for everyone.(認知)

進行特征選擇時，選擇CHI值大的特征。

定義4：如果考慮到兩種屬性重要性衡量權重的重要性同等重要

(1)當特征項i只在一種文本類別中出現時，Ii=CHI×Ri；

(2)當特征項i在兩種以上文本類別中出現時，Ii=CHImax×Ri。

第一步：求解S的屬性集中條件屬性集C關于決策屬性D的絕對核R=CORED(C)；

第二步：根據屬性子集的縮減分辨能力IaSUB對所有屬性進行排序，然后在根據每個屬性ai的重要性Ii的值進行大小排序；

一般的啟發(fā)式屬性約簡算法在對于屬性約簡過程中都只是利用一種啟發(fā)式信息，進行一次選擇，改進后的啟發(fā)式屬性約簡算法，利用了兩種啟發(fā)式約簡信息，減少了冗余信息，應該得到更精簡的屬性約簡集。

下面我們將改進后的啟發(fā)式屬性約簡算法運用到文本分類系統(tǒng)中來驗證其可行性。

2.4 實驗結果及分析

2.4.1 分類結果的評價指標

為了檢驗分類算法的性能，需要從算法的復雜度、有效性以及算法描述的易理解程度三個方面進行分析，本文僅從算法有效性進行分析，包括以下幾個方面：

(1)查準率：應該分類的文本數量與最終分到該類別的文本數量之間的比值，查準率越高，說明算法越有效，計算方法為：

其中：TP表示應該分類到該類型的文本數量(被正確地分到該類的文本數)；FP表示被錯誤分類到該類型的文本數量(被錯誤地分到該類的文本數)。

(2)查全率：被正確分類到該類型中的文本數量與實際該類型中文本的數量之間的比值，該數值越大，說明分類越全面，計算方法為：

其中：TP表示應該分類到該類型的文本數量；FN表示應該被分到該類型卻被遺漏的文本數量(本應屬于該類，但沒分到該類的文本數)。

以上兩種指標的綜合可以用F-Measure方法表示：

其中，參數β表示pr與re之間的重要程度。當β=0時，Fβ=pr即為查準率；當β→時，Fβ為查全率；當β=1時，表示考察查準率和查全率同樣重要，此時

被稱為F1-Measure。

2.4.2 實驗設置

本次實驗數據是從新聞語料語料庫中抽取了一部分進行實驗，共分為8個類別，其中類別包括alt.atheism，comp.graphics，rec.autos，misc.forsale，sci.crypt，sci.med，Sci.space，talk.politics.guns，共7605篇文本，其中訓練文本4571篇，測試文本3034篇。

表2 語料庫中訓練文本和測試文本的分布情況

2.4.3 實驗結果及分析

實驗過程中，在訓練階段，首先用粗糙集理論提取出文本的分類規(guī)則，然后將預處理后的測試文本通過規(guī)則的匹配確定其類別。我們設計文本分類系統(tǒng)功能包括：訓練，分類(即測試)和評價。評價結果如下：

表3 文本分類系統(tǒng)的評價結果1

表4 文本分類系統(tǒng)的評價結果2

由表3和表4的分類評價結果，我們可以看出：對于測試集的7605篇測試文本，運用改進屬性約簡算法的粗糙集文本分類系統(tǒng)進行文本分類后，再利用提到的文本分類評價指標的計算方法計算得到每一個類別的召回率、準確率和F-l值，在經過平均計算出整個系統(tǒng)的召回86.0%，準確率85.5%，F-1值85.6%，改進之前召回率79.4%，準確率79.4%，F-1值79.4%，即該改進的系統(tǒng)能夠得到較高的召回率、準確率和F-l值，具有較好的分類效果。

3 結 論

本文對于粗糙集理論中的啟發(fā)式屬性約簡算法進行改進，利用兩種約簡信息，將傳統(tǒng)的一次約簡變?yōu)槎渭s簡，由于冗余信息會干擾啟發(fā)式屬性約簡算法的分類結果，因此利用改進后的屬性約簡算法可以減少冗余信息的干擾，得到更精簡的屬性約簡集。該方法在保持規(guī)則的分類能力基本不變的情況下分類準確率較高，極大地壓縮了文本特征子集的向量維數，避免基于向量比較文本分類方法計算量較大的問題。

實驗結果表明：無論是召回率、準確率還是F-1值，改進后的屬性約簡算法相對于啟發(fā)式屬性約簡算法都有很大較高，得到了很好的分類效果，證明了改進屬性約簡算法的有效性。但存在的缺點是對于大型數據庫，其訓練時間較長。

筆者認為在以后的工作中還有一些問題可以考慮進一步深入研究：

(1)語料庫往往是一個文本分類系統(tǒng)進行分類效果好壞的關鍵因素，可以研究怎樣建立一個科學合理的語料庫及建設語料庫應遵循的規(guī)則。

(2)本文所設計的模型是基于小規(guī)模的考慮，并且實驗所選用的語料庫也是小規(guī)模的，將它應用于大規(guī)模的真實環(huán)境是未來的工作。

[1] 潘雪增，廖一星.文本分類及其特征降維研究[D].杭州：浙江大學，2012.

[2] 林亞平，楊昂.文本分類算法研究[D].長沙：湖南大學，2002.

[3] 王國胤，姚一豫，于 洪.粗糙集理論與應用研究綜述[J].計算機學報，2009，32(7)：1229-1246.

[4] 張桂蕓，王麗紅.基于粗糙集理論的文本分類技術研究[D].天津：天津師范大學，2009.

[5] Pawlak Z.Rough Sets[J].International Journal of Computer and Information Sciences，1982，11(5):341-356.

[6] 武尚，程紅福，明曉樂.基于優(yōu)勢關系的粗糙集擴展研究[J].計算機與數字工程，2014，8(6)：943-947.

[7] 徐凌雁.基于粗糙集的BP神經網絡空氣品質預測模型[J].東北電力大學學報，2015，33(5)：81-87.

[8] 張志飛，苗奪謙.基于粗糙集的文本分類特征選擇算法[J].智能系統(tǒng)學報，2009，4(5)：453-457.

[9] 吳守領，楊穎，楊磊，劉磊.基于粗糙集的決策表屬性約簡方法的研究[J].計算技術與發(fā)展，2012，22(1)：32-35.

[10] Wenhao Shu，Hong Shen.Incremental feature selection based on rough set in dynamic incomplete data[J]. Pattern Recognition，2014，47(12):3890-3906.

[11] 張玉芳，萬斌候.文本分類中的特征降維方法研究[J].計算機應用研究，2012，29(7)：2541-2543.

[12] 李遠遠，云俊.基于粗糙集的綜合評價方法研究[J].武漢理工大學學報：信息與管理工程版，2009，31(6)：981-985.

The Text Classification Attribute Reduction Algorithm Based on the Rough Set Theory

HAN Yu1，LI Mei-cong1，GUO Xin-chen2

(1.College Of Science，Northeast Dianli University，Jilin 132012，China；2.Department of Mathematics，Hainan Tropical Ocean College，572022，China)

In view of high dimension problems of text feature space in text classification，This paper proposes a kind of attribute reduction algorithm based on rough set theory and its improved algorithm，Greatly reduce the dimension of text feature vector.By using 20 newsgroups data sets to test，the precision rate and recall rate and F-1 degree index all has a clear advantage.

Rough set；Attribute reduction；Text classification

2016-04-12

吉林省教育廳科研項目(2015-248)

韓 玉(1978-)，男，吉林省洮南市人，東北電力大學理學院副教授，博士，主要研究方向：數理統(tǒng)計、數據挖掘.

1005-2992(2016)05-0092-05

O144.4

A