基于圖的粗糙集屬性約簡(jiǎn)方法

米據(jù)生,陳錦坤

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

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

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

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

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

1 基本知識(shí)

1.1 屬性約簡(jiǎn)

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

對(duì)任意的B?A,記

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

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

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

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

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

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

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

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

稱B是S的一個(gè)約簡(jiǎn),若滿足:

所有約簡(jiǎn)的交稱為S的核心屬性集。

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

M(x,y)=

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

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

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

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

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

1.2 圖的極小頂點(diǎn)覆蓋

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

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

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

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

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

2 基于圖的屬性約簡(jiǎn)框架

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖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)的頂點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

3 基于圖的屬性約簡(jiǎn)算法

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

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

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

輸出:一個(gè)屬性約簡(jiǎn)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每個(gè)v∈Red

if Red-{v}能覆蓋簡(jiǎn)化圖G的所有邊

Red←Red-{v};

end if

end for

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

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

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

輸出:一個(gè)近似屬性約簡(jiǎn)Red

1) Red=?

2) for 對(duì)每個(gè)x∈U

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

Red←[Red,v0];

end while

end for

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

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

秒/s

表5 約簡(jiǎn)結(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é) 語(yǔ)

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