一種改進(jìn)的最小屬性約簡算法＊

薛勝軍 郭 強

（武漢理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院1） 武漢 430063）

（南京信息工程大學(xué)計算機與軟件學(xué)院2） 南京 210044）

粗糙集理論是一種新型的處理模糊性和不確定性問題的數(shù)學(xué)工具，經(jīng)過將近30 a的發(fā)展，該理論已廣泛應(yīng)用于故障檢測、數(shù)據(jù)挖掘、模式識別、知識發(fā)現(xiàn)等領(lǐng)域．屬性約簡是粗糙集理論中的一個核心內(nèi)容，目前有很多研究都是針對屬性約簡方面的．求解屬性約簡的算法可以劃分為如下幾類：（1）基于正區(qū)域的求解算法，有時在求解的過程中會結(jié)合屬性的重要性、互信息等；（2）基于差別矩陣的求解算法；（3）基于智能計算的求解方法，如基于遺傳算法和神經(jīng)網(wǎng)絡(luò)．隨著問題規(guī)模的增大，基于差別矩陣求解算法的缺陷會愈加凸顯．有時在利用正區(qū)域或差別矩陣求解時，常結(jié)合屬性的重要性［1］、互信息［2］、屬性出現(xiàn)的頻率［3］等，使得算法更加高效．本文通過實例指出文獻(xiàn)［4］中的不足并加以改進(jìn)，結(jié)合了基于等價類壓縮的思想和基于核增量求解的思想提出了一種新的求解最小約簡的方法，最后通過實例驗證算法的有效性．

1 粗糙集的相關(guān)概念

設(shè)S＝（U，R，V，F(xiàn)）為一信息系統(tǒng)．式中：U＝（X1，X2，…，Xn）為論域（universe）；R 為屬性集合；V為屬性值集合；F為U×R→V 的映射，它為U中各對象的屬性指定惟一值．若R＝C∪D，C∩D＝?，C稱為條件屬性集；D稱為決策屬性集，則該信息系統(tǒng)稱為決策表．

定義1 設(shè)S＝（U，R，V，F(xiàn)），對于每個屬性子集P?R，定義屬性P的不可區(qū)分關(guān)系IND（P）＝｛（x，y）∈U2｜?r∈P，f（x，r）＝f（y，r）｝，如果（x，y）∈IND（P），則稱x與y 是P 不可區(qū)分的．不可區(qū)分關(guān)系也可稱為等價關(guān)系．IND（P）是U 的一個劃分，記為U／P，U／P中的任意元素［x］P＝｛y｜?a∈P，f（x，a）＝f（y，a）｝稱為等價類．

定義2 設(shè)S＝（U，R，V，F(xiàn)），對于每個子集X?U和一個等價關(guān)系P?R，定義兩個子集：＝｛Y∈U／R｜Y?X｝，X＝｛Y∈U／R｜Y∩X≠?｝．分別稱它們?yōu)閄的P下近似集和P上近似集．

定義4 設(shè)S＝（U，R，V，F(xiàn)），R＝C∪D，如果POSP（D）＝POSC（D）且對于?r∈P，都有POSP（D）≠POSC－｛r｝（D），則稱P 是S 的一個屬性約簡．S的所有屬性約簡的并集記為red（S）．red（S）中屬性數(shù)目最少的約簡稱為S的最小屬性約簡．

定義5 決策表S的所有屬性約簡的交集為屬性核，即core（S）＝∩red（S）．

定義6 如果有相同條件屬性的數(shù)據(jù)同時其決策屬性的值也相等，則稱該決策表為相容決策表，如果它們的分類不相同，則稱為不相容決策表．

定義7［5］決策表S＝（U，R，V，F(xiàn)）的差別矩陣M（S）是一個n×n的矩陣，n＝｜U｜，其第i行第j列的元素為Cij＝｛a∈C｜f（ui，a）＝f（uj，a），（ui，uj）?IND（D）且ui，uj中至少有一個屬于POSC（D）｝；否則Cij＝?．

推論1 在基于定義7的條件下，core（S）＝｛a∈c｜Cij＝｛a｝｝．

2 基于U／｛a｝的最小屬性約簡算法

該方法的思想在于先用單個條件屬性a對論域U進(jìn)行劃分，獲得若干子決策表，然后對各子決策表求解，整合各子決策表中的基數(shù)最小的約簡，將這些約簡合并到集合Gm中，若p∈Gm，POSp（D）＝POSC（D），則p為所求，否則p∪｛a｝為所求．該方法具有如下性質(zhì)．

定義8［6］決策表Si＝（Ui，r－｛a｝，V，F(xiàn)），P?A，U／P＝｛X1，X2，…，Xn｝，知識P 的 劃分粒度E（P）定義為E（P）＝ ｜Xi｜

性質(zhì)1 決策表S＝（U，R，V，F(xiàn)），P?A，U／P＝｛X1，X2，…，Xn｝，則1≤｜U｜／n≤E（P）≤｜U｜．即劃分粒度越小，分類能力越強．當(dāng)n＝｜U｜時劃分粒度最強．

定義9 決策表S＝（U，R，V，F(xiàn)），R＝C∪D，a∈C，n＝｜Va｜，U／a＝｛U1，U2，…，Un｝，則第i個等價類構(gòu)成原決策表S的第i個子決策表（1≤i≤n），記為Si＝（Ui，R－｛a｝，V，F(xiàn)）．差別矩陣為M（Si），差別集為 AS（i），約簡集為red（Si），G＝｛Ra｜Ra＝∪Ri，Ri∈red（Si）｝，H＝｛Ra∪｛a｝｜Ra∈G｝．設(shè)G中元素最小基數(shù)為m，Gm＝｛R｜R∈G，｜R｜＝m｝．

定理1 若G＝?，則POS｛a｝（D）＝POSC（D）．

性質(zhì)2 Ui∈IND（D）當(dāng)且僅當(dāng)red（Si）＝?．

定理2［7］H∪G中必存在原系統(tǒng)的最小約簡．

定理3 任取RS∈red（S），則在每一個子系統(tǒng)Si中都存在P∈red（Si）滿足P?RS．

引理 ∪core（Si）?core（S），其中1≤i≤n．

證明 由定理3即可得到．

文獻(xiàn)［4］中的方法沒有考慮如果Gm中的元素全為核屬性時的情況．因為核屬性必屬于最小約簡，但是根據(jù)文獻(xiàn)［10］的思想，只能隨機的選取其中一個核屬性，必會漏選其他的核屬性，所得的結(jié)果就不是正確的了．另外，文獻(xiàn)［4］中的方法是對整個論域元素依次進(jìn)行計算，這就會出現(xiàn)重復(fù)計算的現(xiàn)象，增加了算法的復(fù)雜度，降低了效率．

3 基于等價類的決策表壓縮方法

定義10［8］在 決策表 S ＝（U，C，D，V，F(xiàn)）中，記U／C＝｛［u′1］C，［］C…［u′m］C｝，U′＝｛u′1，u′2，…，u′m｝，POSC（D）＝］C∪ ［u′i2］C∪ … ∪］C，其中?∈U′且｜［］C／D｜＝1（s＝1，2，…，t）；記U′pos＝…｝，U′neg＝ U′－U′pos，稱S′＝（U′，C，D，V，f）為簡化的決策表．

定理3 在決策表S＝（U，C，D，V，F(xiàn)）中，S′＝（U′，C，D，V，f）為其簡化的決策表．若?B?C有（D）＝且?b∈B 均有（D）≠P（D），則B 是C 相對于D 的屬性約簡．

推論2 在不涉及決策屬性計算的情況下，簡化后的決策表的分類能力不變．

證明 在壓縮后的決策表中，各等價類之間的計算仍然不變，只是減少了差別矩陣中非空元素的重復(fù)計算，即各等價類之間只計算一次．此時，用于計算結(jié)果的分辨信息并未減少．又由定理3可知，壓縮后的決策表的約簡滿足原決策表，從而推論得證．

文獻(xiàn)［8］提供了一種快速的求解等價類的方法，該方法在目前是最快的，算法的具體內(nèi)容可參考文獻(xiàn)［8］．通過該方法的計算，可以得到Upos和Uneg，將它們壓縮后便可得到新的論域＝∪．以文獻(xiàn)［4］中的例子為為例，經(jīng)計算，可得等價類｛1，5｝，｛2，8｝，｛3｝，｛4｝，｛6｝，｛7｝．具體步驟如下．

第一趟收集

front［0］→1→2→5→8→4→3→6→7→end［0］

第二趟分配

front［0］→1→2→4→5→7→8→end［0］

front［1］→3→end［1］

front［2］→6→end［2］

第二趟收集

front［0］→1→2→4→5→7→8→3→6→end［0］

第三趟分配

front［0］→1→5→end［0］

front［1］→2→7→8→end［1］

front∪［2］→3→4→6→end［2］

第三趟收集

front［0］→1→5→2→7→8→3→4→6→end［0］

其中：｛1，5｝，｛2，8｝是不相容的，｛3｝，｛4｝，｛6｝，｛7｝是相容的，可以用｛1｝或者｛5｝來代替｛1，5｝，｛2｝或者｛8｝來代替｛2，8｝．則壓縮后可得U′pos＝｛3，4，6，7｝，U′neg＝｛1，2｝，U′＝U′pos∪U′neg．在構(gòu)成的新的差別矩陣時，減少了元素2，8分別和元素3，4，6，7之間的計算．在數(shù)據(jù)量較大的運算中，該方法的優(yōu)勢會更加明顯．

4 基于核的改進(jìn)算法

本算法對文獻(xiàn)［4］提出的基于U／｛a｝的最小屬性約簡算法進(jìn)行了改進(jìn)，具體步驟如下．

步驟1 按公式計算出最小劃分粒度｛a｝，若POS｛a｝（D）＝POSC（D），則｛a｝為最小約簡，退出，否則轉(zhuǎn)步驟2．

步驟2 對論域進(jìn)行壓縮，求出S′＝｛U′，R，V，F(xiàn)｝．

步驟3 用粒度最小的元素對論域進(jìn)行劃分，采用文獻(xiàn)［5］中的方法，對各個子系統(tǒng)進(jìn)行計算，求出約簡集red（Si）．

步驟4 將AS（i）中的單元素存入core中，保持core中各元素互不相同，并在red（Si）中刪除所有由單元素所組成的約簡．

步驟5 如果POScore（D）＝POSC（D），則core為最小約簡，退出，否則轉(zhuǎn)步驟6．

步驟6 如果POScore∪｛a｝（D）＝POSC（D），則core∪｛a｝為最小約簡退出，否則轉(zhuǎn)步驟7．

步驟 7 求 G＝ ｛Ra｜Ra＝ ∪Ri，Ri∈red（Si）｝，計算Gm＝｛R｜R∈G，｜R｜＝m｝．

步驟8 如果存在Gm中一元素p，使POSp∪core（D）＝POSC（D），則p∪core為最小約簡，退出，否則，任取p∈Gm，p∪core∪｛a｝為所求，退出．

該算法能在Gm中的元素為核屬性的情況下求的最小約簡．

證明 假設(shè)步驟1得到的不是最小約簡，則必存在元素數(shù)目小于1的約簡，此時只有空集，不符合要求，則｛a｝為最小約簡，步驟1得證．由推論2知步驟2不會影響結(jié)果的計算．依據(jù)定義5，若POScore（D）＝POSC（D），則core為最小約簡，步驟5得證．若POScore∪｛a｝（D）＝POSC（D），則core∪｛a｝是最小約簡．假設(shè)其不是，則必存在元素數(shù)目更小的約簡，因core（S）＝∩red（S），所以該約簡至少包含core且包含元素數(shù)目不小于｜core｜，又POScore（D）≠POSC（D），所 以 假 設(shè) 不 成 立，則core∪｛a｝為最小約簡，步驟6得證．因約簡必包含core，又p中包含的元素最少，則p∪core為最小約簡，否則，若 POSp∪core∪｛a｝（D）＝POSC（D），此時正好滿足文獻(xiàn)［4］中算法求解的條件，由文獻(xiàn)［4］中證明可得p∪core∪｛a｝為最小約簡，步驟8得證．

該算法考慮了各核屬性，解決了文獻(xiàn)［4］中基于U／｛a｝的最小屬性約簡算法的不足．步驟2的復(fù)雜度為O（｜C｜｜U｜），在實際問題中｜C｜｜U｜＜｜U｜2，又原算法的時間復(fù)雜度為O（K｜U1｜2＋K｜U2｜2＋…＋K｜Un｜2），K 為關(guān)于｜U｜與｜R｜的多項式或指數(shù)級式子，則改進(jìn)后的算法的時間復(fù)雜度為 max（｜C｜｜U｜，K｜U1｜2＋K｜U2｜2＋…＋K｜Un｜2），隨著數(shù)據(jù)量的增大，時間復(fù)雜度會趨向于O（K｜U1｜2＋ K｜U2｜2＋…＋ K｜Un｜2），由于對原決策表進(jìn)行壓縮，所以新的算法的空間復(fù)雜度會降低，這種優(yōu)勢在大數(shù)據(jù)量的計算中會很明顯．

5 實例分析

分別采用文獻(xiàn)［4］的算法和本文的算法對表1進(jìn)行計算，求該決策表的最小屬性約簡．

表1 決策表

E（｛a｝）＝62／12，E（｛b｝）＝50／12，E（｛c｝）＝72／12，E（｛d｝）＝102／12，故用屬性b對論域進(jìn)行劃分．對論域進(jìn)行壓縮，壓縮后得＝｛X1，X2，X3，X4，X5，X6，X7，X10｝，U′neg＝｛X9｝．劃分后得U1＝｛X1，X2，X3｝，U2＝｛X4，X7，X10｝，U3＝｛X5，X6，X9｝．AS（1）＝ ｛d，ad｝，AS（2）＝ ｛a，ac｝，AS（3）＝｛d，ad｝，red（S1）＝｛d｝，red（S2）＝｛a｝，red（S3）＝｛d｝，按照文獻(xiàn)［4］的思路，G＝｛｛a｝，｛d｝，｛d｝｝，POS｛b｝（D）≠POSC（D），又各子約簡的最小基數(shù)都為1，則從G中隨便取一個元素和屬性b構(gòu)成的集合便為最小約簡，但POS｛a，d｝（D）≠POSC（D），POScore∪｛a｝（D）≠POSC（D），所以，文獻(xiàn)［4］中的方法在此并不能求出最小約簡．

按新算法有core＝｛a，d｝，因POScore∪｛a｝（D）＝POSC（D），所以core∪｛b｝＝｛a，b，d｝為所求．對于文獻(xiàn)［4］中的例子，red（S1）＝?，AS（2）＝｛a｝，red（S2）＝?，AS（3）＝｛ab，ab｝，red（S3）＝ ｛｛a｝，｛b｝｝，故 core＝ ｛a｝，因 POScore∪｛c｝（D）＝POSC（D），故｛a，c｝為所求，結(jié)果與文獻(xiàn)［4］相符．

6 結(jié)束語

本文提出一種時間復(fù)雜度為max（｜C｜｜U｜，K｜U1｜2＋ K｜U2｜2＋…＋ K｜Un｜2）的算法，該算法通過基于等價類的思想對決策表進(jìn)行壓縮，降低了計算的復(fù)雜性和存儲空間，提高了算法的效率，在約簡的時候采用基于核的思想，逐步求解，可以保證獲得最小約簡．

［1］吳明芬，許 勇，劉志明．一種基于屬性重要性的啟發(fā)式約簡算法［J］．小型微型計算機系統(tǒng)［J］，2007，28（8）：1 452－1 455．

［2］顏 艷，楊慧中．一種基于互信息的粗糙集知識約簡算法［J］．清華大學(xué)學(xué)報：自然科學(xué)版，2007，47（52）：1 903－1 906．

［3］王加陽，高 燦．改進(jìn)的基于差別矩陣的屬性約簡算法［J］．計算機工程，2009，35（3）：65－67．

［4］葉明全，伍長榮．決策表分解及其最小屬性約簡研究［J］．計算機工程與應(yīng)用，2009，45（30）：126－128．

［5］劉文軍，谷云東，馮艷賓，等．基于可辨識矩陣和邏輯運算的屬性約簡算法的改進(jìn)［J］．模式識別和人工智能，2004，17（1）：119－123．

［6］馮琴榮，苗奪謙，程 昳．決策表屬性約簡的相對劃分粒度表示［J］．小型微型計算機系統(tǒng)，2008，29（12）：2302－2308．

［7］李訂芳，李貴斌，章 文．基于U／｛a｝劃分的最小約簡構(gòu)造［J］．武漢大學(xué)學(xué)報：理學(xué)版，2005，51（3）：269－272．

［8］徐章艷，劉作鵬，楊炳儒，等．一個復(fù)雜度為max（O（｜C｜｜U｜），O（｜C｜2｜U／C｜））的 快 速 屬 性 約簡算法［J］．計算機學(xué)報，2006，29（3）：391－399．