陸 光，李 想，王 彪

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

0 引言

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

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

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

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

1 屬性約簡

1.1SEGMENT-SIG算法基本思想

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

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

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

1.2SEGMENT-SIG算法基本步驟

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

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

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

下面對本文提出的屬性約簡的一個有效算法進行介紹。

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

SEGMENT這個子程序找到一個基本約簡s_reduct。

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

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

(3)WHILE CTk≠Ф DO

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

分裂 CTk，形成 CTk－1

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

k←k－1.);

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

然后運用Pawlak的屬性重要度方法［1］:

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

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

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

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

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

在決策表中找到約簡的主要步驟為:

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

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

(3)s_reduct←SEGMENT;

(4)reduct←SEGMENT-SIG。

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

2 算法實例分析及實驗結(jié)果報告

2.1 實例分析——決策表中的一個例子

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

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

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

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

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

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

s_reduct中有 3 個屬性:C2、C4、C5(可以簡單表示成{2，4，5})。由屬性 C2、C4和 C5組成了新的決策表，如表2所示。表2中的屬性相比原始表的屬性已經(jīng)約簡了不少，然而這并不一定是最終的最簡約簡(盡管最簡不一定意味著最好)，所以有必要進行進一步驗證。根據(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}，約簡屬性中除了核值外剩余屬性為C4，求得其屬性重要度sig(4，C;D)=(8－8)/11=0，故C4對于屬性C2和C5而言是可有可無的，故刪除C4，所以最終約簡為{2，5}。

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

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

圖2 決策樹

2.2 實驗結(jié)果

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

用本文算法和ID3算法做對比，得到如圖3所示的兩個決策樹:圖3(b)是在這個例子當(dāng)中形成的決策樹，圖3(a)為ID3算法求得的決策樹。顯然，本文例子中創(chuàng)造的決策樹比ID3算法的決策樹要短。這并不奇怪，因為該算法使用屬性重要度方法進行第二次掃描，刪除所有非必要的屬性，根據(jù)奧坎氏簡化論，這是很有用的，盡管“短”并不總是意味著好。

圖3 兩個決策樹

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

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

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

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

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

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

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

3 結(jié)束語

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

算法的輸出是兩種類型的分類器:一個是IFTHEN規(guī)則，另一個是決策樹。這是SEGMENT-SIG算法的一個優(yōu)點，其他算法是做不到的。該算法的其他優(yōu)點就是通過讀取部分數(shù)據(jù)集到內(nèi)存可以解除內(nèi)存使用限制，因為它每次只是處理表的一列。

［1］苗奪謙，李道國.粗糙集理論、算法與應(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］王國胤.Rough集理論與知識獲?。跰］.西安:西安交通大學(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］王國胤，于洪，楊大春.基于條件信息熵的決策表約簡［J］.計算機學(xué)報，2002，25(7):759-766.

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