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

韓 玉，李美聰，郭新辰

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

?

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

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

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

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

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

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

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

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

1.1 粗糙集理論

1.2 基于粗糙集的屬性約簡

1.2.1 屬性約簡

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

表1 文本分類決策表

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

1.3 屬性約簡算法及其改進(jìn)算法

1.3.1 屬性約簡算法的描述

為了利用粗糙集理論中屬性重要性的相關(guān)結(jié)論，首先介紹幾個(gè)重要的定義。

擴(kuò)張分辨能力的大小可以反映屬性對(duì)所屬集合的繼續(xù)分類所產(chǎn)生的影響能力，當(dāng)IaADD=0時(shí)，說明屬性a對(duì)子集B的分類能力不產(chǎn)生影響，不應(yīng)該繼續(xù)添加該屬性。

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

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

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

第二步：根據(jù)屬性子集的縮減分辨能力IaSUB對(duì)所有屬性進(jìn)行排序；

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

2.3.2 改進(jìn)的屬性約簡算法

本文將粗糙集理論應(yīng)用于文本分類。對(duì)于屬性的重要性評(píng)價(jià)主要有兩種：其一是基于特征選擇的屬性評(píng)價(jià)標(biāo)準(zhǔn)[11]；其二是基于粗糙集理論本身的屬性評(píng)價(jià)標(biāo)準(zhǔn)[12]。

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

定義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.(認(rèn)知)

進(jìn)行特征選擇時(shí)，選擇CHI值大的特征。

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

(1)當(dāng)特征項(xiàng)i只在一種文本類別中出現(xiàn)時(shí)，Ii=CHI×Ri；

(2)當(dāng)特征項(xiàng)i在兩種以上文本類別中出現(xiàn)時(shí)，Ii=CHImax×Ri。

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

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

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

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

2.4 實(shí)驗(yàn)結(jié)果及分析

2.4.1 分類結(jié)果的評(píng)價(jià)指標(biāo)

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

(1)查準(zhǔn)率：應(yīng)該分類的文本數(shù)量與最終分到該類別的文本數(shù)量之間的比值，查準(zhǔn)率越高，說明算法越有效，計(jì)算方法為：

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

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

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

以上兩種指標(biāo)的綜合可以用F-Measure方法表示：

其中，參數(shù)β表示pr與re之間的重要程度。當(dāng)β=0時(shí)，F(xiàn)β=pr即為查準(zhǔn)率；當(dāng)β→時(shí)，F(xiàn)β為查全率；當(dāng)β=1時(shí)，表示考察查準(zhǔn)率和查全率同樣重要，此時(shí)

被稱為F1-Measure。

2.4.2 實(shí)驗(yàn)設(shè)置

本次實(shí)驗(yàn)數(shù)據(jù)是從新聞?wù)Z料語料庫中抽取了一部分進(jìn)行實(shí)驗(yàn)，共分為8個(gè)類別，其中類別包括alt.atheism，comp.graphics，rec.autos，misc.forsale，sci.crypt，sci.med，Sci.space，talk.politics.guns，共7605篇文本，其中訓(xùn)練文本4571篇，測試文本3034篇。

表2 語料庫中訓(xùn)練文本和測試文本的分布情況

2.4.3 實(shí)驗(yàn)結(jié)果及分析

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

表3 文本分類系統(tǒng)的評(píng)價(jià)結(jié)果1

表4 文本分類系統(tǒng)的評(píng)價(jià)結(jié)果2

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

3 結(jié) 論

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

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

筆者認(rèn)為在以后的工作中還有一些問題可以考慮進(jìn)一步深入研究：

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

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

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

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

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

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

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

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

[7] 徐凌雁.基于粗糙集的BP神經(jīng)網(wǎng)絡(luò)空氣品質(zhì)預(yù)測模型[J].東北電力大學(xué)學(xué)報(bào)，2015，33(5)：81-87.

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

[9] 吳守領(lǐng)，楊穎，楊磊，劉磊.基于粗糙集的決策表屬性約簡方法的研究[J].計(jì)算技術(shù)與發(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].計(jì)算機(jī)應(yīng)用研究，2012，29(7)：2541-2543.

[12] 李遠(yuǎn)遠(yuǎn)，云俊.基于粗糙集的綜合評(píng)價(jià)方法研究[J].武漢理工大學(xué)學(xué)報(bào)：信息與管理工程版，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

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

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

1005-2992(2016)05-0092-05

O144.4

A