米據(jù)生,陳錦坤

(1.河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 河北 石家莊 050024;2.河北省計算數(shù)學(xué)與應(yīng)用重點實驗室,河北 石家莊 050024;3.閩南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,福建 漳州 363000)

自1982年P(guān)awlak[1]提出粗糙集理論以來,該理論已成為一種有效處理不確定和含糊信息的重要數(shù)學(xué)工具。在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)和知識發(fā)現(xiàn)等領(lǐng)域有重要的應(yīng)用[2-5]。

由于在現(xiàn)實數(shù)據(jù)集中,往往存在大量冗余和不確定性的信息,嚴(yán)重影響到后續(xù)數(shù)據(jù)挖掘和處理的效率。因此,如何高效地去掉冗余信息,已成為當(dāng)前數(shù)據(jù)分析處理的一個熱點問題。作為粗糙集理論的一個重要應(yīng)用,屬性約簡已經(jīng)被證明是一種有效的數(shù)據(jù)約簡方法。它通過刪除冗余屬性,能獲得數(shù)據(jù)集合的本質(zhì)信息和保持原始數(shù)據(jù)分類信息的完整性,從而提高數(shù)據(jù)的分類質(zhì)量。

基于區(qū)分矩陣和布爾推理方法計算所有的屬性約簡或最小約簡已經(jīng)被證明是一個NP-hard問題[6]。因此,各種高效的啟發(fā)式約簡算法被提出[7]。這些啟發(fā)式的約簡算法主要是尋找一個約簡或近似約簡。常用的啟發(fā)式約簡算法主要包括:基于區(qū)分矩陣的約簡算法[8-10];基于正域的約簡算法[11-13]和基于信息熵的約簡算法[14-17]。關(guān)于粗糙集的屬性約簡方法的系統(tǒng)闡述可參閱綜述文章[7,18]。

目前粗糙集屬性約簡方法的研究已經(jīng)取得了很多成果。然而,這些算法在處理大規(guī)模數(shù)據(jù)集,尤其是面對高維數(shù)據(jù)時,效率仍然不夠理想。針對以上問題,本文提出一種新的屬性約簡框架。主要是受到文[19-20]的啟發(fā),從圖論的角度出發(fā),對決策信息表的區(qū)分矩陣給出直觀和等價的刻畫,最后利用極小頂點覆蓋方法獲取決策表的屬性約簡。數(shù)值實驗結(jié)果表明,所提出的基于圖論的屬性約簡方法在面對較大規(guī)模數(shù)據(jù)集時具有有效性和高效性。

1 基本知識

1.1 屬性約簡

定義1[21]稱S=(U,A)是一個信息系統(tǒng),其中U和A分別是非空有限論域和屬性集;對于任意的屬性a,稱a:U→Va是信息函數(shù),滿足:?x∈U,a(x)∈Va,其中Va稱為屬性a的值域。

對任意的B?A,記

IND(B)={(x,y)∈U×U|a(x)=a(y),?a∈B},

顯然IND(B)是U上的一個等價關(guān)系,也稱為不可分辨關(guān)系,它能導(dǎo)出U上的一個劃分:

U/B={[x]B|x∈U},

其中,[x]B={y|(x,y)∈IND(B)}稱為x關(guān)于IND(B)的等價類。

給定一個信息系統(tǒng)S=(U,A)和X?U,X關(guān)于IND(B)的下、上近似分別定義為:

定義2[21]決策表是一個特殊的信息系統(tǒng)S=(U,C∪ccyqc82),其中C為條件屬性集,d?C為決策屬性。記IND(d)是由決策屬性d所導(dǎo)出的等價關(guān)系,而U/d是由IND(d)生成的劃分。

設(shè)S=(U,C∪0c0keis)是一個決策表,定義如下不可分辨關(guān)系:

IND(B|d)={(x,y)∈U×U|(?a∈B,a(x)=a(y))∨(d(x)=d(y))}。

稱B是S的一個約簡,若滿足:

所有約簡的交稱為S的核心屬性集。

定義3[22]設(shè)S=(U,C∪qssco0o)是決策表,?x,y∈U,稱

M(x,y)=

為x與y的區(qū)分集。所有的區(qū)分集可形成一個對稱矩陣M,稱為決策表S的區(qū)分矩陣。

利用區(qū)分矩陣,便可以定義相應(yīng)的區(qū)分函數(shù),從而獲得所有的約簡集。

定義4[23]設(shè)M為決策表S=(U,C∪ewskkiy)的區(qū)分矩陣,則稱

fM=∧{∨M(x,y)|?x,y∈U,M(x,y)≠?}

為M的區(qū)分函數(shù)。

1.2 圖的極小頂點覆蓋

一般地,一個無向圖可表示為一個二元組G=(V(G),E(G)),其中V(G)是圖G的頂點集,E(G)是圖G所有邊的集合[25]。為簡單起見,一般可把圖簡寫為G=(V,E)。圖G中邊的端點若重合為一個頂點,則稱為環(huán)。若兩條邊有相同的端點,則稱這兩條邊是平行邊或重邊。稱圖H是圖G的子圖,記為H?G,若滿足V(H)?V(G)且E(H)?E(G)。設(shè)G1和G2是圖G的兩個子圖,稱G1∪G2為圖G的并圖,其頂點集和邊集分別為V(G1)∪V(G2)和E(G1)∪E(G2)。給定圖G的頂點v,dG(v)表示G中與頂點v相連接的邊的數(shù)目,稱為頂點v的度。

定義5[25]設(shè)G=(V,E)是給定的圖,K?V。若K能覆蓋圖G的所有邊(即E的每條邊都與K中的某個頂點相連接),則稱頂點子集K是圖G的一個頂點覆蓋。進(jìn)一步地,對于任意的v∈K,若K-{v}不是圖G的頂點覆蓋,則稱K是圖G的極小頂點覆蓋。

類似于求決策表的所有約簡,圖的所有極小頂點覆蓋也可以通過構(gòu)造相應(yīng)的布爾函數(shù)獲得[20,25]。

fG=∧{∨N(e)|?e∈E},

N(e)是與邊e∈E相連接的頂點集。

2 基于圖的屬性約簡框架

2.1 決策表的誘導(dǎo)圖

定義6[19-20]設(shè)S=(U,C∪kcqymcu)是決策表,M是S的區(qū)分矩陣,為了方便,用e∈M表示e是矩陣M中的元素。記

V=C,E={e∈M|e≠?},

則稱GS=(V,E)是決策表S的誘導(dǎo)圖。

從定義6可以看出,決策表S的誘導(dǎo)圖實際上是以決策表的條件屬性作為頂點集,而以區(qū)分矩陣M的非空元素作為邊集。它是對決策表的區(qū)分矩陣的一種直觀刻畫。通過這種刻畫,以及利用引理1和引理2,易知決策表S的所有屬性約簡集與該誘導(dǎo)圖的所有極小頂點覆蓋集是相同的[19-20]。從而,求決策表的屬性約簡問題可轉(zhuǎn)化為求相應(yīng)的圖的極小頂點覆蓋問題。這為粗糙集的屬性約簡方法提供了新的視角和方法。

例1表1是一個決策表S=(U,C∪iqeokoi),其中U={x1,x2,x3,x4},C={a1,a2,a3}。由定義3,可獲得其區(qū)分矩陣M(見表2)。在表2中,a2a3表示集合{a2,a3}。從而,由引理1,易知S有兩個約簡集,分別為{a1,a3}和{a2,a3}。

表1 例1的決策表Tab.1 A decision table of Example 1

利用定義6,其誘導(dǎo)圖GS見圖1。在圖1中,GS共有4條邊,對應(yīng)了區(qū)分矩陣M的4個非空且不重復(fù)的元素。

表2 表1的區(qū)分矩陣Tab.2 Discernibility matrix of Tab. 1

圖1 表1的誘導(dǎo)圖Fig.1 Induced graph of Tab.1

由于區(qū)分矩陣M是對稱矩陣,并且M中往往有很多重復(fù)的元素。定義6蘊(yùn)含了去掉這些重復(fù)的元素。因此,定義6所導(dǎo)出的圖是不包含平行邊的。實際上,如文獻(xiàn)[20]所述,利用吸收律,上面的誘導(dǎo)圖可以進(jìn)一步的簡化。

由于平行邊對獲取圖的頂點覆蓋沒有影響,因此,為計算的方便,可以得到下面更一般的誘導(dǎo)圖(見定義7和圖2)。

定義7設(shè)S=(U,C∪ywuoye0)是決策表,M是S的區(qū)分矩陣。記

V′=C,E′=M-{?}

定義6和定義7中所定義的兩種誘導(dǎo)圖的區(qū)別僅僅是去掉一些重復(fù)的邊(或平行邊)。實際上,圖1可看成是圖2的簡化(或子圖)。而且,這兩個圖的極小頂點覆蓋集是相同的(見性質(zhì)1)。記C(G)表示圖G的所有極小頂點覆蓋集。

圖2 表1的一般誘導(dǎo)圖Fig.2 General induced graph of Tab.1

證明由定義6、定義7和引理2即可證得。

性質(zhì)2GS=(V,E)是決策表S的一般誘導(dǎo)圖,若a∈C是S的核心屬性,則a在圖GS中是帶環(huán)的頂點。

證明由相關(guān)的定義即可證得。

2.2 一般誘導(dǎo)圖的分解和約簡方法

定義7所給出的一般誘導(dǎo)圖本質(zhì)上是對決策表的區(qū)分矩陣的刻畫。但是一個決策表的區(qū)分矩陣往往需要O(|U|2|C|)的存儲空間,這也意味著生成整個誘導(dǎo)圖也需要O(|U|2|C|)的存儲空間。這對于具有較大樣本集的決策表而言,易因存儲空間的不足而導(dǎo)致其算法極其低效。因此,本文避免生成整個誘導(dǎo)圖,而是通過局部的思想,對其子圖進(jìn)行分步處理。

定義8設(shè)GS=(V,E)是決策表S=(U,C∪ekuwke0)的一般誘導(dǎo)圖。對于任意的x∈U,記

Vx=V,Ex={M(x,y)|y∈U},

則Gx=(Vx,Ex)是GS的一個子圖。

證明由定義3、定義7和定義8即可證得。

定理1表明決策表的一般誘導(dǎo)圖可分解為一些子圖的并。

例2在例1中,對于x1∈U,其子圖Gx1見圖3(a)。顯然,Gx1是GS(圖2)的一個子圖。由圖2,易知GS恰好分解為4個子圖。

圖3 GS的子圖Fig.3 Subgraphs of GS

證明由定義8和定理1即可證得。

3 基于圖的屬性約簡算法

由上一節(jié)的理論結(jié)果,本節(jié)將設(shè)計相應(yīng)的啟發(fā)式算法來獲得決策表的主要屬性。通過改進(jìn)經(jīng)典的圖頂點覆蓋算法[26],我們有下面基于圖的粗糙集特征選擇算法。

算法1基于圖的粗糙集特征選擇算法1(GRF1)

輸入:決策表S=(U,C∪ouqyioy)

輸出:一個屬性約簡Red

1) Red=?

2) 生成誘導(dǎo)圖GS=(V,E);∥根據(jù)定義6

whileE≠?

v0=arg max{dG(v)|v∈V};

Red←[Red,v0];

去掉E中被Red所覆蓋的邊,并仍記為E.end while

3) for每個v∈Red

if Red-{v}能覆蓋簡化圖G的所有邊

Red←Red-{v};

end if

end for

算法1(GRF1)的空間復(fù)雜度是O(|U|2|C|),與其他基于區(qū)分矩陣的約簡算法的存儲空間基本是一致的。其次,GRF1的時間復(fù)雜度是O(|U||C|)。與其他大部分的約簡算法相比,GRF1顯然更加快速。但是面對大規(guī)模數(shù)據(jù)集,尤其是含有較大樣本的數(shù)據(jù)集時,GRF1容易因為內(nèi)存不足而導(dǎo)致無法運(yùn)行。

算法2基于圖的粗糙集特征選擇算法2(GRF2)

輸入:決策表S=(U,C∪akuse08)

輸出:一個近似屬性約簡Red

1) Red=?

2) for 對每個x∈U

生成子圖Gx=(Vx,Ex);//定義8

Red←[Red,v0];

end while

end for

算法2(GRF2)的時間和空間復(fù)雜度都是O(|U||C|),與其他基于區(qū)分矩陣的約簡算法和GRF1相比,其存儲空間降低了很多。這將會極大地提高GRF2的運(yùn)行效率。但是與GRF1相比,GRF2不一定獲得一個真正的約簡,它所獲得的特征數(shù)目往往比GRF1多。

4 實驗結(jié)果與分析

實驗選用了8個公開的數(shù)據(jù)集進(jìn)行驗證。具體的數(shù)據(jù)集描述見表3。在實驗中,我們選取了3種具有代表性的約簡算法進(jìn)行對比,它們分別是基于區(qū)分矩陣的約簡算法SPS[10]、基于正域的約簡算法FPR[13]和基于信息熵的約簡算法FCCE[13]。本文所有的實驗結(jié)果均在Windows 10 (i7-6700,CPU 3.40 GHz,內(nèi)存24GB)的普通個人PC上獲得,使用的操作平臺是Matlab2016b和Weka3.8。

具體的實驗結(jié)果如圖4、表4、表5、表6、表7和表8所示。圖4展示了GRF1和GRF2這兩種算法在生成相應(yīng)的圖時所需要的存儲空間。從圖4可看出,GRF2所需要的存儲空間比GRF1小很多,比如,對于數(shù)據(jù)集Chess,GRF2所占用的存儲空間僅僅是GRF1的0.13%。對于擁有大樣本的數(shù)據(jù)集而言,這種差異往往會更加明顯。以數(shù)據(jù)集Letter和Relathe為例,算法GRF1會因為“內(nèi)存溢出”而導(dǎo)致程序無法運(yùn)行。實際上其他基于區(qū)分矩陣的算法也往往具有這種現(xiàn)象。比如,算法SPS,雖然它已經(jīng)去掉了區(qū)分矩陣中一些不必要的元素,但是對于較大規(guī)模的數(shù)據(jù)集比如Letter而言,它仍然會因為內(nèi)存的不足而導(dǎo)致無法獲得實驗結(jié)果。因此,與其他基于區(qū)分矩陣的屬性約簡算法相比,GRF2更適合于處理大規(guī)模的數(shù)據(jù)集。實際上,GRF2和FPR,FCCE等算法的存儲空間復(fù)雜度都是一樣的。它們都適合于處理大樣本的數(shù)據(jù)集。

表4記錄了5種算法在這8個數(shù)據(jù)集上的運(yùn)行時間。在表中,“*”表示由于該算法“內(nèi)存溢出”而導(dǎo)致的程序無法運(yùn)行。從表4中可看出,GRF1和SPS適合于處理高維小樣本的數(shù)據(jù)集。FPR和FCCE適合于處理低維大樣本,而GRF2不管什么類型的數(shù)據(jù)集,其運(yùn)行速度均表現(xiàn)得極其高效。以Relathe數(shù)據(jù)集為例,GRF2的運(yùn)行時間分別是FPR,FCCE和SPS的0.46%,0.46%和0.30%。這些結(jié)果進(jìn)一步表明GRF2是一種高效的特征選擇方法。

表5列出了具體的約簡結(jié)果。從表中可知,與其他算法相比,GRF1和FCCE均能獲得極小的屬性子集。實際上它們均能獲得一個真正的約簡集。

而GRF2只能獲得一個協(xié)調(diào)集,平均而言,GRF2獲得的特征子集的屬性個數(shù)是最大的。然而,對于大部分的數(shù)據(jù)集而言,這種差異并不是很大。

表6,表7和表8分別記錄了這5種算法在約簡前后的分類精度。在這些表中,“Full”表示約簡前原始數(shù)據(jù)的分類精度。所有的分類精度均在Weka3.8上采用10折交叉驗證獲得,實驗中采用了3種分類器:CART,SVM和PAPT。實驗結(jié)果表明,與原始數(shù)據(jù)集的分類精度相比,這些約簡算法均能獲得較好的分類精度。這也表明這些算法能提取一些重要的特征。與FPR,FCCE和SPS相比,GRF1和GRF2獲得較好的平均分類精度。尤其是GRF2,在大部分的數(shù)據(jù)上,均能獲得最好的分類精度。

表3 實驗數(shù)據(jù)集Tab.3 Data sets for test

圖4 算法GRF1和GRF2的存儲空間Fig.4 Storage spaces of GRF1 and GRF2

秒/s

表5 約簡結(jié)果Tab.5 Results of reduct

表6 分類精度(CART)Tab.6 Classification accuracy (CART)

表7 分類精度(SVM)Tab.7 Classification accuracy (SVM)

表8 分類精度(PAPT)Tab.8 Classification accuracy (PAPT)

5 結(jié) 語

本文基于圖的頂點覆蓋方法提出了一種粗糙集屬性約簡模型。該模型對經(jīng)典粗糙集的區(qū)分矩陣進(jìn)行了直觀的刻畫,并把相應(yīng)的屬性約簡問題轉(zhuǎn)化為其誘導(dǎo)圖的極小頂點覆蓋問題。進(jìn)一步地,利用圖論中的理論方法,設(shè)計了兩種啟發(fā)式的屬性約簡算法。實驗結(jié)果表明,所提出的約簡算法不僅可以選擇少量的主要特征,而且能保持甚至提高約簡數(shù)據(jù)的分類精度。尤其是所提出的GRF2算法,能高效的處理大規(guī)模的數(shù)據(jù)集。但是,GRF2所提取的特征個數(shù)仍然較多,因此,如何進(jìn)一步去掉一些冗余的特征,這將是我們后續(xù)的主要工作之一。