一種有效的屬性約簡(jiǎn)算法

陸 光，李 想，王 彪

(東北林業(yè)大學(xué)信息與計(jì)算機(jī)工程學(xué)院，黑龍江 哈爾濱 150040)

0 引言

一般將機(jī)器學(xué)習(xí)和特征規(guī)則學(xué)習(xí)定義為從給定的特征數(shù)據(jù)中提取重要的、潛在的、有用的結(jié)構(gòu)模式［9］。眾所周知，傳統(tǒng)的機(jī)器學(xué)習(xí)方法，如決策樹方法(ID3，C4.5)等主要研究的是數(shù)據(jù)約簡(jiǎn)的主要過(guò)程，也就是說(shuō)，在保留原始數(shù)據(jù)分類一致性不變的前提下通過(guò)屬性約簡(jiǎn)可以得到原始數(shù)據(jù)的一個(gè)更短的屬性值描述。如在約簡(jiǎn)前，如果對(duì)象x確定屬于類y，那么在約簡(jiǎn)后x仍然屬于類y。粗糙集理論的觀點(diǎn)可以表示為“知識(shí)就是一種對(duì)對(duì)象進(jìn)行分類的能力”［1］，其目的是對(duì)原始數(shù)據(jù)的最大約簡(jiǎn)，也就是說(shuō)尋找一種盡可能小的模式以適應(yīng)訓(xùn)練樣本。相對(duì)約簡(jiǎn)(后面用約簡(jiǎn)代替)是一個(gè)最小的屬性子集，保留了原始數(shù)據(jù)的分類一致性，從而能夠得到整個(gè)屬性集的分類［2］。在粗糙集理論［3，10-11］中，屬性約簡(jiǎn)是一個(gè)基本的、古典的數(shù)學(xué)問(wèn)題，這樣可以找到一個(gè)更好的或近似的約簡(jiǎn)，用其去更好地分類未知的對(duì)象。本文提出一種算法，可以有效地找到約簡(jiǎn)，其不只是探索好的約簡(jiǎn)方法，而且更專注Pawlak提出的數(shù)學(xué)問(wèn)題中的核問(wèn)題，這意味著本文把問(wèn)題看做是一個(gè)總結(jié)原數(shù)據(jù)的問(wèn)題，而不是一個(gè)泛化的問(wèn)題。因此，本文專注對(duì)算法的完整性和計(jì)算復(fù)雜度進(jìn)行分析，并完成其他相關(guān)工作。

表格知識(shí)體系被廣泛研究并常用于數(shù)據(jù)挖掘領(lǐng)域，決策表DT(Decision Table)是表格知識(shí)體系中的一種，因此決策表是一類特殊而重要的知識(shí)表達(dá)系統(tǒng)。一個(gè)數(shù)據(jù)集表示為一個(gè)表，表中每一行代表一個(gè)對(duì)象或者一個(gè)事件;每一列代表一個(gè)可以描述每個(gè)對(duì)象或事件的屬性。在決策表中，有一個(gè)獨(dú)特的屬性，它的值決定了一個(gè)對(duì)象屬于哪個(gè)類，稱這個(gè)屬性為決策屬性，定義為“d”;稱其他的屬性為條件屬性，條件屬性的集合被定義為“C”。假設(shè)tc∈C，把表中的第i列表示成 Ci(Ci∈C，1≤i≤tc)并且用(tc+1)列表示決策屬性d。在決策表中，如果i＜j，則說(shuō)明表中Ci在Cj的左側(cè)。形式上，一個(gè)決策表可以被看做DT=(U，C∪D，V，f)，其中 U 是非空有限的對(duì)象集，稱作全集，即論域;C是非空有限條件屬性集;D為決策屬性集;C∩D=Φ，C≠Φ，D≠Φ。對(duì)于任意一個(gè)a∈C∪D，a:U→Va，這里Va叫做a的一個(gè)值集［2］;最右邊的列定義成“d”，決策表根據(jù)d的值被分為rD組，稱這些組為“D域“，rD為由決策屬性d導(dǎo)出的等價(jià)類的數(shù)目。

一個(gè)決策表描述了條件屬性知識(shí)范疇與決策屬性知識(shí)范疇之間存在的蘊(yùn)含關(guān)系［1］。如果在一個(gè)決策表中，兩個(gè)對(duì)象根據(jù)條件屬性或者是決策屬性被視為是不同的，那么就說(shuō)這兩對(duì)象之間有一個(gè)分界;如果根據(jù)條件屬性和決策屬性這兩者是不同的，那么說(shuō)它們之間有一個(gè)相對(duì)的劃分。更進(jìn)一步說(shuō)，如果兩個(gè)對(duì)象之一同所有其他對(duì)象是一致的，那么就說(shuō)相對(duì)劃分是有效的。證明約簡(jiǎn)，包括屬性約簡(jiǎn)和值約簡(jiǎn)，是保留原有決策表的相對(duì)界限的一個(gè)過(guò)程。

對(duì)于保持一致性來(lái)說(shuō)，所有有效相對(duì)界限集是充分也是必要的，其證明很簡(jiǎn)單。本文的任務(wù)就是找到一個(gè)約簡(jiǎn)，保留原系統(tǒng)的所有有效的相對(duì)界限，形成決策表的一個(gè)約簡(jiǎn)組合，再由Pawlak提出的屬性重要度計(jì)算出其中的核值，逐次求出除核值以外的屬性的重要度，把重要度大于預(yù)先設(shè)定的最小重要度值的屬性加入其中，最終得到一個(gè)約簡(jiǎn)，就像按壓海綿，擠壓出其兩邊的水，得到最終的約簡(jiǎn)。

1 屬性約簡(jiǎn)

1.1SEGMENT-SIG算法基本思想

假設(shè)，條件屬性是許多工作在一個(gè)生產(chǎn)線上的特殊的機(jī)器人，他們的任務(wù)是劃定一些對(duì)象，屬性約簡(jiǎn)方案是盡可能少地分配這些機(jī)器人，以完成預(yù)定的任務(wù)。對(duì)于許多工作在生產(chǎn)線上的機(jī)器人，它的任務(wù)是整合劃分決定下一個(gè)機(jī)器的任務(wù)。不能直接對(duì)一個(gè)機(jī)器人劃分，因?yàn)榭臻g復(fù)雜度將成為大型應(yīng)用程序的一個(gè)問(wèn)題。幸運(yùn)的是，有一個(gè)簡(jiǎn)單的方法，節(jié)省了空間和時(shí)間復(fù)雜度。

假設(shè)有一個(gè)屬性列表s_reduct，要使s_reduct作為最佳約簡(jiǎn)，它可以包含至少一個(gè)約簡(jiǎn)。算法通過(guò)連接一項(xiàng)任務(wù)到它的子任務(wù)，再由Pawlak提出的屬性重要度算法求得的約簡(jiǎn)屬性，產(chǎn)生了一個(gè)決策樹，一旦找到約簡(jiǎn)，IF-THEN規(guī)則通過(guò)最終決策表和讀值很容易被構(gòu)造出來(lái)。一個(gè)對(duì)象的條件屬性值會(huì)在規(guī)則先行詞(IF)處形成連接詞，決策屬性形成規(guī)則集(THEN)［2］。

假設(shè)有一個(gè)小的決策表DT，它包含N個(gè)對(duì)象，每個(gè)對(duì)象有一個(gè)序列號(hào)，有k個(gè)條件屬性和一個(gè)決策屬性 d。讓{［a，b］i，［c，d］i，［e，f］k}CR作為集合{(x，y)|x∈［a，b］or［c，d］，y∈［e，f］}的表示方法。在［a，b］i中小角標(biāo) i代表［a，b］分為 D 區(qū)域 i，即對(duì)任何 x∈［a，b］，d(x)=i。因?yàn)樗粫?huì)引起混亂，所以省略上標(biāo)“CR”。在本文中，［a，b］、［c，d］、［e，f］被稱為段。首先，按決策屬性d進(jìn)行排序，由決策屬性d可以導(dǎo)出界限集，稱 TD 區(qū)域，如{［a，b］0，［c，d］1}，其中0和1代表由d劃分的一類中的值。很明顯，所有的相對(duì)劃分就是TD的一個(gè)子集，TD的任何一個(gè)子集稱為一項(xiàng)任務(wù)。值得注意是，一項(xiàng)任務(wù)可以表示成段的一個(gè)集合。首先考慮最右邊的條件屬性，看它能誘導(dǎo)出哪一個(gè)相對(duì)劃分，如果這個(gè)屬性能夠明顯地誘導(dǎo)出一些相對(duì)劃分，劃分出來(lái)的部分稱為CTk，那么將屬性放在s_reduct中。當(dāng)CTk不為空時(shí)，分裂CTk形成 CTk-1，即下一個(gè)任務(wù)形成;當(dāng) CTk-1=CTk時(shí)，則去除當(dāng)前屬性，否則把當(dāng)前任務(wù)中的屬性加入到s_reduct中，直至所有任務(wù)結(jié)束。任務(wù)結(jié)束后，s_reduct中包含了一些屬性，然后運(yùn)用Pawlak的屬性重要度方法對(duì)s_reduct中的屬性進(jìn)一步約簡(jiǎn)，避免冗余的屬性出現(xiàn)。首先找到屬性集中的核值，把每一個(gè)屬性的重要度求出來(lái)，留下重要度最大的屬性，其中屬性重要度的度量值可以由專家給出，也可以直接去除重要度為0的屬性。

1.2SEGMENT-SIG算法基本步驟

在圖1中，CTi中的子任務(wù)被連接成一個(gè)列表，在子任務(wù)1中出現(xiàn)的“k”是子任務(wù)片段的編號(hào)。這個(gè)編號(hào)大于1。對(duì)于任何屬于這些片段的一個(gè)對(duì)象，“a”是Ci中的它的測(cè)量值。級(jí)聯(lián)任務(wù)CTi如圖1所示。

圖1 級(jí)聯(lián)任務(wù)的數(shù)據(jù)結(jié)構(gòu)

在算法的最開始，對(duì)象會(huì)被決策屬性d分類，假設(shè)結(jié)果是:{Seg1，Seg2，…，SegrD}，這樣 TD 就形成了，這些rD片段對(duì)應(yīng)rDD-區(qū)域，rD的值大于1。這些片段將會(huì)根據(jù)最右邊的條件屬性分類。換句話說(shuō)，它們會(huì)分裂形成一些子片段。有相同值的所有子片段會(huì)被放在一起形成一個(gè)新的任務(wù)。級(jí)聯(lián)任務(wù)分裂一些屬性會(huì)產(chǎn)生新的任務(wù)，就是它的子任務(wù)。這些子任務(wù)形成一個(gè)新的級(jí)聯(lián)任務(wù)。

下面對(duì)本文提出的屬性約簡(jiǎn)的一個(gè)有效算法進(jìn)行介紹。

一個(gè)正式的ADL描述SEGMENT-SIG算法步驟為:

SEGMENT這個(gè)子程序找到一個(gè)基本約簡(jiǎn)s_reduct。

(1)k←tc， /*假設(shè)|C|=tc*/;

(2)CTk←TD，s_reduct←{}/*決策屬性分裂形成的段TD，設(shè)初始約簡(jiǎn)為空*/;

(3)WHILE CTk≠Ф DO

(IF k=1 THEN標(biāo)記不一致對(duì)象并RETURN返回

分裂 CTk，形成 CTk－1

IF CTk－1≠CTkTHEN s_reduct←s_reduct∪{k －1}

k←k－1.);

(4)return s_reduct /*形成一個(gè)由原屬性中的部分屬性組成的新的決策表s_reduct。*/。

然后運(yùn)用Pawlak的屬性重要度方法［1］:

(1)B=Φ /*設(shè)s_reduct的核為B*/;

(2)計(jì)算條件屬性C相對(duì)于決策屬性D的核，令B←COREC(D);

(3)如果 PosB(D)=PosC(D)，那么 B=COREC(D)∈REDC(D)，否則轉(zhuǎn)到第(4)步;

(4)計(jì)算對(duì)任意的ci∈CB，計(jì)算屬性重要度sig(ci，B)=|posB∪{ci}(D)|-|posB(D)|，求得 cm=arg maxsig(ci，B)(若同時(shí)出現(xiàn)多個(gè)屬性滿足最大值，則從中選取一個(gè)與B的屬性值組合數(shù)最少的屬性作為cm)，令B=B∪{cm};

(5)輸出B∈REDc(D)，即得到reduct最終的約簡(jiǎn)，算法結(jié)束。

在決策表中找到約簡(jiǎn)的主要步驟為:

(1)給條件屬性一個(gè)order/*最重要的或者是花費(fèi)代價(jià)少的屬性應(yīng)該設(shè)置在表的右側(cè)，通過(guò)測(cè)量的重要性，order次序可以是任意的*/;

(2)由決策屬性d分類的對(duì)象，形成一個(gè)D-區(qū)域。假設(shè)結(jié)果是:{Seg1，Seg2，…，SegrD}，TD 形成;

(3)s_reduct←SEGMENT;

(4)reduct←SEGMENT-SIG。

根據(jù)選擇所要處理屬性的次序找到一個(gè)約簡(jiǎn)，一個(gè)好的次序意味著好的約簡(jiǎn)［4］。一般來(lái)說(shuō)，好的先驗(yàn)算法可以形成高質(zhì)量的近似約簡(jiǎn)。算法SEGMENT-SIG可以確保近似約簡(jiǎn)是一個(gè)真正的約簡(jiǎn)。此外，算法可以用一些額外的時(shí)間找到更多的約簡(jiǎn)。

2 算法實(shí)例分析及實(shí)驗(yàn)結(jié)果報(bào)告

2.1 實(shí)例分析——決策表中的一個(gè)例子

舉個(gè)小例子，一個(gè)小的決策表DT=(U，C∪D，V，f)，其中 C={C1，C2，C3，C4，C5}。全集中有 11 個(gè)對(duì)象，首先按決策屬性d進(jìn)行排序，表格及排序結(jié)果如表1所示。由決策屬性d誘導(dǎo)出的界限集可以表示成{［1，5］0，［6，11］1}，稱之為 TD。

表1 決策表TD排序后的表格

首先觀察C5，它可以誘導(dǎo)出哪一個(gè)相對(duì)分段。屬性 C5的值在 TD 中(即［1，5］和［6，11］)分組或者分割段，結(jié)果可以在表1中看到。很顯然，對(duì)象x和y可以被屬性C5和d劃定，對(duì)任意x∈［1，2］和y∈［9，11］，也就是說(shuō)，{［1，2］0，［9，11］1}是相對(duì)劃分的一個(gè)集，所以{［3，5］0，［6，8］1}也是。

假設(shè)有一個(gè)屬性列表s_reduct，想要使s_reduct作為最佳約簡(jiǎn)，初始值為空，它可以包含至少一個(gè)約簡(jiǎn)。首先，把C5放在s_reduct中，因?yàn)镃5可以誘導(dǎo)出一些相對(duì)劃分。但是屬于［1，2］的對(duì)象卻不能被屬于［6，8］的對(duì)象劃分，同樣適用于［3，5］，［9，11］，這些對(duì)象需要被其他的屬性劃分。因此，一項(xiàng)新的任務(wù)形式是:第一項(xiàng)子任務(wù)是{［1，2］0，［6，8］1}，第二項(xiàng)子任務(wù)是{［3，5］0，［9，11］1}。用 CT5來(lái)表示這個(gè)新的任務(wù)，是兩個(gè)子任務(wù)的合集。本文稱CTi為一個(gè)級(jí)聯(lián)任務(wù)，因?yàn)樗B通屬性 Ci－1決定了 CTi－1。CTi即是之前的比喻，“機(jī)器”Ci－1面臨的任務(wù)。

當(dāng)CT5≠Φ時(shí)，必須考慮屬性C4。C5中的段根據(jù)C4的值被劃分，這意味著C4≠C5。換句話說(shuō)，C4可以誘導(dǎo)一些相對(duì)分割，而不能被C5誘導(dǎo)，因此把C4放在 s_reduct中。顯然，{［1，2］0，［6，6］1}和{［3，3］0，［9，11］1}形成一個(gè)新的級(jí)聯(lián)任務(wù)，可以表示成CT4。值得注意是，CT3=CT4。這樣，C3對(duì)于{C4，C5}是可有可無(wú)的，并且可以跳過(guò)。一旦CT2={［1，2］0，［6，6］1}≠CT3，則把 C2放在屬性列表 s_reduct中。

因?yàn)?CT1=CT2，對(duì)于{C2，C4，C5}而言，C1是可有可無(wú)的。同時(shí)發(fā)現(xiàn){［1，2］0，［6，6］1}是界限，不能被條件屬性誘導(dǎo)，但是可以被決策屬性誘導(dǎo)。這就意味著，對(duì)象1、2、6不能被確定地指定到同一個(gè)類里，則用一個(gè)特殊的符號(hào)“?”來(lái)簡(jiǎn)單地標(biāo)記它們。對(duì)于一個(gè)段［x，y］來(lái)說(shuō)，如果任何一個(gè)對(duì)象 z∈［x，y］被標(biāo)記成“?”，則稱其為段標(biāo)記。

s_reduct中有 3 個(gè)屬性:C2、C4、C5(可以簡(jiǎn)單表示成{2，4，5})。由屬性 C2、C4和 C5組成了新的決策表，如表2所示。表2中的屬性相比原始表的屬性已經(jīng)約簡(jiǎn)了不少，然而這并不一定是最終的最簡(jiǎn)約簡(jiǎn)(盡管最簡(jiǎn)不一定意味著最好)，所以有必要進(jìn)行進(jìn)一步驗(yàn)證。根據(jù)屬性重要度的方法可以求出新決策表的核值:由于 IND(C)={{1，2}，{3}，{4}，{5，6}，{7}，{8}，{10}，{11}}，IND(D)={{1，2，3，10，11}，{4，5，6，7，8，9，}}，POSc(D)={3，4，5，6，7，8，10，11}，求得 POS(C －C2)(D)={4，7，8，10，11}≠POSc(D)，POS(C － C4)(D)={3，4，5，6，7，8，10，11}=POSc(D)，POS(C － C5)={3，4，5，6，7，10}≠POSc(D)，故決策表的核值為{2，5}，約簡(jiǎn)屬性中除了核值外剩余屬性為C4，求得其屬性重要度sig(4，C;D)=(8－8)/11=0，故C4對(duì)于屬性C2和C5而言是可有可無(wú)的，故刪除C4，所以最終約簡(jiǎn)為{2，5}。

該算法中，可以采取一個(gè)輔助數(shù)組“Ad”，如表2所示。

最后，用這種方式得到一個(gè)約簡(jiǎn){C2，C5}。注意，算法通過(guò)連接一項(xiàng)任務(wù)到它的子任務(wù)，再由Pawlak提出的屬性重要度算法求得約簡(jiǎn)屬性，產(chǎn)生一個(gè)決策樹，如圖2所示。

圖2 決策樹

2.2 實(shí)驗(yàn)結(jié)果

由上述例子找到約簡(jiǎn)，IF-THEN規(guī)則通過(guò)最終決策表和讀值很容易被構(gòu)造出來(lái)。一個(gè)對(duì)象的條件屬性值會(huì)在規(guī)則先行詞(IF)處形成連接詞，決策屬性值對(duì)形成規(guī)則集(THEN)［2］。如從表2可以寫出規(guī)則“IF C2=1 and C5=0 THEN d=0”。這里，d的值由多數(shù)判決決定。

用本文算法和ID3算法做對(duì)比，得到如圖3所示的兩個(gè)決策樹:圖3(b)是在這個(gè)例子當(dāng)中形成的決策樹，圖3(a)為ID3算法求得的決策樹。顯然，本文例子中創(chuàng)造的決策樹比ID3算法的決策樹要短。這并不奇怪，因?yàn)樵撍惴ㄊ褂脤傩灾匾确椒ㄟM(jìn)行第二次掃描，刪除所有非必要的屬性，根據(jù)奧坎氏簡(jiǎn)化論，這是很有用的，盡管“短”并不總是意味著好。

圖3 兩個(gè)決策樹

從圖3(a)中所示的樹可知，任何一個(gè)樹的深度都能得出結(jié)論，因?yàn)樵诿恳还?jié)點(diǎn)處有條件值和決策值元素。對(duì)于不一致規(guī)則，可以得到像“IF C2=1 and C5=0，THEN d=0(2)or d=1(1)”的規(guī)則，而不是簡(jiǎn)單地把最普通的值分配給它們的決策屬性值，其中括號(hào)中的數(shù)字是匹配規(guī)則對(duì)象的編號(hào)。分離的概念形式在現(xiàn)實(shí)生活中是非常有用的。如果有一個(gè)相應(yīng)高級(jí)的層次概念［5］，則可以通過(guò)屬性定向誘導(dǎo)得到更多的一般規(guī)則［6］。

因此，屬性約簡(jiǎn)之后得到兩個(gè)不同的分類器:一個(gè)是規(guī)則系統(tǒng)，另一個(gè)是決策樹。目前分類的有效性是本文關(guān)心的問(wèn)題，決策樹的形式是比較常見(jiàn)的，而規(guī)則對(duì)人們來(lái)說(shuō)更難理解。

該算法時(shí)間需求主要是排序。假設(shè)SEGMENT實(shí)際描述屬性的編號(hào)是r，表中對(duì)象的編號(hào)是N，排序需要O(rNlnN)步，這里1≤r≤tc。值得注意是，在SEGMENT中，可以用第二次排序來(lái)減輕排序的不規(guī)則。算法中另一部分時(shí)間是計(jì)算兩個(gè)級(jí)聯(lián)任務(wù)的交集，僅需要O(NlnN)步。因此，SEGMENT-SIG算法的最壞的時(shí)間復(fù)雜度是:O(rNlnN)。

在SEGMENT中，內(nèi)存中保存的所有級(jí)聯(lián)任務(wù)CTi(Ci∈s_reduct)常駐內(nèi)存，僅用一個(gè)級(jí)聯(lián)任務(wù)CTi，所有這些級(jí)聯(lián)任務(wù)占用O(rN)單元，這些是額外的或者是附加的空間。同時(shí)，僅需要總表的一小部分，表的一個(gè)或者幾個(gè)進(jìn)入到內(nèi)存，這樣僅僅需要O(N)個(gè)單元，因此總的空間是O(rN)。然而，也可以在內(nèi)存中不保存所有的級(jí)聯(lián)任務(wù)CTi，而是把這些任務(wù)寫入磁盤中，可以通過(guò)磁碟常駐視圖，寫入和讀出操作，這樣算法僅需要O(N)內(nèi)存空間。

讓length(CTi)作為CTi片段大小的編號(hào)，對(duì)于在SEGMENT中任意的 i∈［2，tc+1］，并假設(shè) length(CTi－1)/length(CTi)≤μ(0≤μ≤1)，算法最壞的時(shí)間復(fù)雜度是:O(Min(tc，logμ(2/N))×NlnN)，因?yàn)橛蠱in(tc，logμ(2/N))個(gè)屬性要被瀏覽到。之前最快的算法，稱它為 NERS(Nguyen Sinh Hoa and Nguyen Hung Son的算法粗糙集的效率)，它得到一個(gè)約簡(jiǎn)需要瀏 覽 表 Tc次［7］，最壞 的時(shí)間復(fù)雜 度 是 O(Tc2NlnN)。

一般來(lái)說(shuō)，SEGMENT-SIG算法在面臨大量的屬性時(shí)，可以顯示出它的優(yōu)點(diǎn)。但是，眾所周知，數(shù)據(jù)挖掘中更加嚴(yán)格的限制是內(nèi)存。也許，是由于在面對(duì)大量數(shù)據(jù)集［2］(當(dāng)矩陣中不同元素的數(shù)量適中時(shí)，它們?nèi)匀皇遣豢捎玫?時(shí)，基于算法的差別矩陣是不可行的，而且一些嵌入式RSES文庫(kù)中的算法并不適用于比預(yù)訂的規(guī)模大的決策表，一般只限于500個(gè)對(duì)象、20個(gè)屬性。影響NERS有效性的一個(gè)因素是排序中對(duì)象的移動(dòng)。給NERS增加一個(gè)輔助數(shù)組來(lái)避免此類運(yùn)動(dòng)，稱這種改進(jìn)為NERSA。NERS和NERSA需要把整個(gè)表放在內(nèi)存中，還規(guī)定了對(duì)內(nèi)存的需求。由于已經(jīng)做出解釋，SEGMENT-SIG算法通過(guò)把一列或者是幾個(gè)一步一步放入內(nèi)存可以避免這個(gè)問(wèn)題，使得它更適合數(shù)據(jù)挖掘的需求。

當(dāng)需要挖掘的原始數(shù)據(jù)數(shù)量比較大時(shí)，一些其他的算法并不適合，并且用單純的屬性重要度方法進(jìn)行屬性約簡(jiǎn)顯得太繁瑣，本算法通過(guò)子算法SEGMENT遍歷一次后便可以把多余屬性去掉，相比單純屬性重要度方法而言，它首先是遵循逐步向前選擇的原則，一步步選擇屬性加入到s_reduct中，之后用逐步向后刪除法將不重要的屬性刪除，該方法得到了至少包含核在內(nèi)的一個(gè)組合，而不需要如單純屬性約簡(jiǎn)算法那樣對(duì)屬性進(jìn)行組合，大大節(jié)省了計(jì)算時(shí)間。

3 結(jié)束語(yǔ)

本文提出一種簡(jiǎn)單有效的算法SEGMENT-SIG，可以找到一個(gè)約簡(jiǎn)。該算法約簡(jiǎn)有兩個(gè)原因:其一，在大的數(shù)據(jù)庫(kù)中找到所有的約簡(jiǎn)，在文獻(xiàn)［8］中已經(jīng)證明是一個(gè)NP-Hard問(wèn)題;其二，對(duì)于一個(gè)專家來(lái)說(shuō)，逐次約簡(jiǎn)幾乎是處理不了的。

算法的輸出是兩種類型的分類器:一個(gè)是IFTHEN規(guī)則，另一個(gè)是決策樹。這是SEGMENT-SIG算法的一個(gè)優(yōu)點(diǎn)，其他算法是做不到的。該算法的其他優(yōu)點(diǎn)就是通過(guò)讀取部分?jǐn)?shù)據(jù)集到內(nèi)存可以解除內(nèi)存使用限制，因?yàn)樗看沃皇翘幚肀淼囊涣小?/p>

［1］苗奪謙，李道國(guó).粗糙集理論、算法與應(yīng)用［M］.北京:清華大學(xué)出版社，2008:132-232.

［2］Komorowski J，Pawlak Z，Polkowski L，et al.Rough Sets:A Tutorial［M］.Springer，1998:3-98.

［3］Pawlak Z.Rough Sets:Theoretical Aspects of Reasoning about Data［M］.Kluwer Academic Publishers，1992.

［4］Hu Q，Pao W，Yu D.Improved reduction algorithm based on A-Priori［J］.Computer Science，2002，29:115-117.

［5］Best J B.Cognitive Psychology［M］.Heinle and Heinle Publishers，Boston，MA，1998.

［6］Han J，Kamber M.Data Mining:Concepts and Techniques［M］.Morgan Kaufmann，San Francisco，CA，2000.

［7］Hoa N S，Son N H.Some efficient algorithms for rough set methods［C］//Proceedings of the Conference of Information Processing and Management of Uncertainty in Knowledge-Based Systems.1996:1451-1456.

［8］Skowron A，Rauszer C.The discernibility matrices and functions in information system［M］//Intelligent Decision Support-Handbook of Applications and Adbvances of the Rough Set Theory.Kluwer Academic Publishers，1992:331-362.

［9］He Yuguo.An efficient attribute reduction algorithm［C］//Proceedings of the 7th International Conference on Intelligent Data Engineering and Automated Learning.2006:859-868.

［10］王國(guó)胤.Rough集理論與知識(shí)獲?。跰］.西安:西安交通大學(xué)出版社，2001:117-152.

［11］Ivo Düntsch，Günther Gediga.Rough set data analysis［C］//Encyclopedia of Computer Science and Technology.2000:281-301.

［12］Pawlak Z.Rough set approach to knowledge-based decision support［J］.European Journal of Operational Research，1995，99(1):48-57.

［13］王國(guó)胤，于洪，楊大春.基于條件信息熵的決策表約簡(jiǎn)［J］.計(jì)算機(jī)學(xué)報(bào)，2002，25(7):759-766.

［14］張騰飛，肖健梅，王錫淮.粗糙集理論中屬性相對(duì)約簡(jiǎn)算法［J］.電子學(xué)報(bào)，2005，33(11):2080-2083.