基于決策表分解的屬性約簡(jiǎn)算法

劉旭東，秦亮曦

（廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧530004）

0 引 言

屬性約簡(jiǎn)的方法很多，但所追求的目標(biāo)相同，就是能夠高效獲得最小約簡(jiǎn)集。然而，找到最小約簡(jiǎn)是一個(gè)NP－h(huán)ard問(wèn)題，通常采用基于屬性重要度等啟發(fā)式搜索算法找到最優(yōu)或次優(yōu)約簡(jiǎn)集，所以如何高效的獲得約簡(jiǎn)結(jié)果是屬性約簡(jiǎn)算法的研究重點(diǎn)。當(dāng)數(shù)據(jù)集較大時(shí)，現(xiàn)有一些基于屬性重要度的約簡(jiǎn)算法效率往往比較低。針對(duì)這一問(wèn)題，本文提出了一種基于決策表分解的屬性約簡(jiǎn)算法，不僅能得到較優(yōu)的約簡(jiǎn)集，更能降低時(shí)間復(fù)雜度，較快地得到約簡(jiǎn)結(jié)果。

1 粗糙集理論的基本概念［1，2］

定義1 決策表信息系統(tǒng)用S＝（U，C∪D，V，f）來(lái)表示，其中，U表示一個(gè)有限非空對(duì)象集 （論域），U ＝ ｛0，1，2，…，n｝；C為條件屬性集，D為決策屬性集，通常決策屬性只有一個(gè)，且C∩D＝；V＝∪Va，Va為屬性a的值域；f為信息函數(shù)f：U×（C∪D）→V，a∈（C∪D），x∈U，有f（x，a）∈Va。

定義2 令P C∪D ，ind（P）＝ ｛（x，y）｜f（x，a）＝f（y，a）， a∈P｝稱為S的不可區(qū)分關(guān)系。顯然，不可區(qū)分關(guān)系是一個(gè)等價(jià)類。屬性集P將論域U劃分為多個(gè)等價(jià)類，記為U／P。

定義3 對(duì)于決策表信息系統(tǒng)S，令U／C＝ ｛X1，X2，…，Xn｝，U／D ＝ ｛Y1，Y2，…，Ym｝。條件屬性C 關(guān)于決策屬性D 的正域POSC（D）＝∪ ｛Xi｜XiYj，Xi∈U／C，Yj∈U／D｝。正域基數(shù)是衡量屬性重要度的一個(gè)重要準(zhǔn)則。

定義4 對(duì)于決策表信息系統(tǒng)S，若POSP（D）＝POSC（D）， 且 對(duì) 于 a ∈ P， 有 POSP（D） ≠POS｛P－a｝（D），則稱P是S的一個(gè)屬性約簡(jiǎn)。

定義5 若存在2個(gè)對(duì)象x，y，若 a∈C，f（x，a）＝f（y，a），且f（x，D）≠f（y，D），則稱S是不相容決策表，即當(dāng)2個(gè)對(duì)象條件屬性相同，但分類不一樣時(shí)，此信息系統(tǒng)是不相容決策表，否則就是相容決策表。本文只考慮相容決策表。

定義6 互信息I（X，Y）是一個(gè)用來(lái)測(cè)量2個(gè)隨機(jī)變量X，Y之間相關(guān)程度的量，I（X，Y）其中，p（x，y）表示隨機(jī)變量X、Y的聯(lián)合分分別是變量X、Y的邊緣分布。

定義7 在決策表信息系統(tǒng)S＝ （U，C∪D，V，f）中，有屬性集P C，添加一個(gè)屬性p∈C到P中，獲得的互信息增加量 （信息增益）為gain＝I（P∪p，D）－I（P，D）。計(jì)算每個(gè)條件屬性對(duì)決策屬性的gain，gain越大，條件屬性就越重要。

2 基于決策表分解的屬性約簡(jiǎn)算法及其復(fù)雜度分析

2.1 算法思路

一般采用啟發(fā)式算法進(jìn)行屬性約簡(jiǎn)，定義一個(gè)啟發(fā)函數(shù)，如差別函數(shù)（區(qū)分函數(shù)）［3，4］或?qū)傩灾匾群瘮?shù)［5－11］，通過(guò)此函數(shù)進(jìn)行屬性約簡(jiǎn)。在基于差別函數(shù)的屬性約簡(jiǎn)算法中，需要通過(guò)比較對(duì)象之間的差異來(lái)構(gòu)造決策表信息系統(tǒng)的區(qū)分矩陣，當(dāng)數(shù)據(jù)集比較大時(shí)，空間和時(shí)間復(fù)雜度都比較高，所以一般采用定義屬性重要度函數(shù)的啟發(fā)算法。在基于屬性重要度的屬性約簡(jiǎn)算法中，傳統(tǒng)的約簡(jiǎn)算法（如文獻(xiàn) ［5］）建立在整個(gè)決策表上，通過(guò)劃分等價(jià)類U／P，不斷計(jì)算POSP（D）是否等于POSC（D）。只有當(dāng)?shù)葍r(jià)類中的所有對(duì)象決策屬性值相同時(shí)，這些對(duì)象才屬于正域。也就是說(shuō)，只要存在2個(gè)對(duì)象，其決策屬性值不同，那么整個(gè)等價(jià)類都不屬于正域，此時(shí)，就不用考慮其它對(duì)象。經(jīng)過(guò)研究，在選取某個(gè)最重要的屬性后，在下一步的迭代過(guò)程中，可以在上一次所求的各個(gè)等價(jià)類中分別計(jì)算正域，而不必在整個(gè)決策表上計(jì)算，并且如果其中一些等價(jià)類已經(jīng)在正域中，就可以忽略這些等價(jià)類。由于每次計(jì)算是建立在已分解的決策表上，所以不需要計(jì)算對(duì)屬性集的正域基數(shù)，每次迭代只需計(jì)算對(duì)單個(gè)屬性的正域基數(shù)，而且每次迭代所處理的對(duì)象將大大減少。由此設(shè)計(jì)出一個(gè)基于決策表分解的屬性約簡(jiǎn)算法，該算法的主要思想是在每次迭代選取一個(gè)最重要的屬性后，將原有決策表按照所求的等價(jià)類分解成各個(gè)更小的決策表。

從包含很多條件屬性的決策表信息系統(tǒng)中得到約簡(jiǎn)結(jié)果，通用方法是在每次迭代過(guò)程中挑選最重要的屬性直到找到一個(gè)合適的約簡(jiǎn)集。衡量屬性重要性有很多準(zhǔn)則：正域基數(shù)，信息熵，互信息增益等。在傳統(tǒng)的屬性約簡(jiǎn)算法中，一般只采用單一的評(píng)價(jià)標(biāo)準(zhǔn)來(lái)衡量屬性的重要度，如基于信息熵的屬性約簡(jiǎn)算法［5］一般以信息熵為評(píng)價(jià)標(biāo)準(zhǔn)，每次迭代選取信息熵最小的屬性；基于正區(qū)域的屬性約簡(jiǎn)算法［6－10］通常以正域基數(shù)為評(píng)價(jià)標(biāo)準(zhǔn)，每次迭代選取正域基數(shù)最大的屬性。當(dāng)存在多個(gè)屬性其衡量標(biāo)準(zhǔn)相同時(shí)，采用單一的標(biāo)準(zhǔn)就無(wú)法判別，只能隨機(jī)的選取其中某個(gè)屬性，進(jìn)而影響最終約簡(jiǎn)結(jié)果。本文提出的基于決策表分解的屬性約簡(jiǎn)算法采用正域基數(shù)和互信息增益相結(jié)合的方法來(lái)衡量屬性的重要度。由定義3知，屬性p關(guān)于決策屬性D的正域POSp（D）中個(gè)數(shù)越多，表明正域中不可分辨的對(duì)象個(gè)數(shù)越多，D對(duì)p的依賴度越大，屬性就越重要。由定義7知，添加一個(gè)屬性后，獲得的信息增益越大，表明這個(gè)屬性給分類系統(tǒng)帶來(lái)的信息就越大，該屬性就越重要。本文提出的屬性約簡(jiǎn)算法在每次迭代過(guò)程中，選取正域基數(shù)最大的屬性，當(dāng)存在正域基數(shù)相同時(shí)，再選取互信息增益較大的，這樣能更客觀地衡量屬性的重要度，從而得到更小的約簡(jiǎn)結(jié)果。當(dāng)兩者都相同時(shí)，說(shuō)明屬性是同等重要的，則隨機(jī)選取一個(gè)。

2.2 算法描述及復(fù)雜度分析

輸入：S＝ （U，C ∪ D，V，f）

輸出：約簡(jiǎn)結(jié)果RES

1.for每個(gè)條件屬性p∈C，do

1.1.for（每個(gè)決策表 （第一次只有一個(gè)決策表）），do

求出等價(jià)類U／p，然后根據(jù)等價(jià)類計(jì)算正域POSP（D），對(duì)正域進(jìn)行累加。

2.選取正域基數(shù)最大的屬性p放入RES中。若正域基數(shù)最大的屬性存在多個(gè)，則先根據(jù)等價(jià)類求出互信息增益，再選取互信息增益最大的屬性p放入RES中。若互信息增益也相等，則選取序號(hào)靠前的屬性。

3.分解決策表for（U／p中每個(gè)等價(jià)類），do

3.1.if（等價(jià)類不在正域中）｛

構(gòu)造新決策表：對(duì)象集為等價(jià)類中的元素，條件屬性去除p，決策屬性不變；｝

4.如果決策表不為空，則轉(zhuǎn)到第1步 （決策表已經(jīng)被分解），否則，終止。

算法的時(shí)間復(fù)雜度分析：劃分等價(jià)類的時(shí)間復(fù)雜度為O （｜U｜）［6，8］，所以第1步計(jì)算正域的時(shí)間復(fù)雜度為O（｜C｜｜U｜）；求信息增益的時(shí)間復(fù)雜度為O （mn），其中，m是條件屬性p的種類，n是決策屬性的種類 （mn＜＜｜C｜｜U｜），所以第2步的時(shí)間復(fù)雜度最壞情況下為O （｜C｜）；第3步的時(shí)間復(fù)雜度為O （｜U｜），所以每層遞歸的時(shí)間復(fù)雜度為O （｜C｜｜U｜）。由于每層遞歸要處理的對(duì)象數(shù)目｜U｜不斷減小，條件屬性個(gè)數(shù)｜C｜也不斷減少。當(dāng)不存在冗余屬性時(shí)，需要遞歸｜C｜次，所以最壞情況下，時(shí)間復(fù)雜度為O （｜C｜2｜U｜）。

2.3 實(shí)例分析

在表1中，有7個(gè)對(duì)象，4個(gè)條件屬性a，b，c，d，一個(gè)決策屬性e。先劃分等價(jià)類，ind（｛a｝）＝ ｛｛0，2，3，4，5｝，｛1，6｝｝，ind（｛b｝）＝ ｛｛0，2，3｝，｛1，6｝，｛4，5｝｝，ind（｛c｝）＝｛｛0，6｝，｛1，2，3，4，5｝｝，ind（｛d｝）＝ ｛｛0，3，5｝，｛1，4，6｝，2｝，ind（｛e｝）＝ ｛｛0，5｝，｛1，3｝，｛2，4，6｝｝。通過(guò)等價(jià)類計(jì)算正域，POS｛a｝｛e｝＝，POS｛b｝｛e｝＝，POS｛c｝｛e｝＝，POS｛d｝｛e｝＝ ｛2｝。 所以選取屬性 d， 得 RES ＝ ｛d｝。U／｛d｝＝ ｛｛0，3，5｝，｛1，4，6｝，｛2｝｝，構(gòu)造2個(gè)新決策表，見(jiàn)表2、表3。

表1 決策表S

表2 決策表S1

表3 決策表S2

在決策表S1和S2中，先劃分等價(jià)類，對(duì)S1：ind（｛a｝）＝ ｛｛0，3，5｝｝，ind（｛b｝）＝ ｛｛0，3｝，｛5｝｝，ind（｛c｝）＝ ｛｛0｝， ｛3，5］｝，ind（｛e｝） ＝ ｛｛0，5｝， ｛3］｝； 對(duì) S2：ind（｛a｝）＝ ｛｛1，6｝，｛4｝｝，ind（｛b｝）＝ ｛｛1，6｝，｛4｝｝，ind（｛c｝）＝ ｛｛1，4｝，｛6｝｝，ind（｛e｝）＝ ｛｛1｝，｛4，6｝｝。

再計(jì)算正域：POS｛a｝｛e｝＝＋｛4｝＝ ｛4｝；POS｛b｝｛e｝＝｛5｝＋｛4｝＝ ｛5，4｝；POS｛c｝｛e｝＝ ｛0｝＋｛6｝＝ ｛0，6｝。b，c的正域基數(shù)相等，計(jì)算信息增益，gain（b）＝0.2516，gain（c）＝0.2516。于是，選取屬性b，RES ＝ ｛d，b｝。U／｛b｝＝｛｛0，3｝，｛5｝，｛1，6｝，｛4｝｝，再構(gòu)造新決策表，見(jiàn)表4、表5。

在決策表S11和S21中，對(duì)S11：ind（｛a｝）＝ ｛｛0，3｝｝，ind（｛c｝）＝ ｛｛0｝，｛3｝｝，ind（｛e｝）＝ ｛｛0，3｝｝；對(duì)S21：ind（｛a｝）＝ ｛｛1，6｝｝，ind（｛c｝）＝ ｛｛1｝，｛6｝｝，ind（｛e｝）＝｛｛1｝，｛6｝｝。再計(jì)算正域，POS｛a｝｛e｝＝ ｛0，3｝＋＝ ｛0，3｝；POS｛c｝｛e｝＝ ｛0，3｝＋｛1，6｝＝ ｛0，3，1，6｝。所以取屬性c，RES＝｛d，b，c｝。此時(shí)，沒(méi)有構(gòu)造決策表的對(duì)象，故算法終止。約簡(jiǎn)結(jié)果是 ｛d，b，c］。

表4 決策表S11

表5 決策表S21

3 實(shí)驗(yàn)分析

收集UCI數(shù)據(jù)庫(kù)中8個(gè)數(shù)據(jù)集對(duì)文獻(xiàn) ［5］中的算法（原算法）和本文提出的算法 （改進(jìn)算法）進(jìn)行對(duì)比測(cè)試。算法用C＋＋編寫(xiě)，實(shí)驗(yàn)環(huán)境為 Windows XP，Pentium4 3.0GHz，512M內(nèi)存，Code：Blocks10.05。數(shù)據(jù)集規(guī)模見(jiàn)表6。

表6 數(shù)據(jù)集

為了不影響測(cè)試結(jié)果，mushroom數(shù)據(jù)集中去掉了含有缺失值的對(duì)象。如果是連續(xù)型數(shù)據(jù)，則先進(jìn)行離散化處理。由于不同數(shù)據(jù)集運(yùn)行時(shí)間的跨度比較大，所以把實(shí)驗(yàn)結(jié)果放在2個(gè)圖中。實(shí)驗(yàn)結(jié)果如圖1，圖2，表7所示。由表7知，改進(jìn)算法與原算法得到的約簡(jiǎn)結(jié)果相同，說(shuō)明改進(jìn)算法是正確可行的。由圖1，圖2知，在運(yùn)行時(shí)間上，改進(jìn)算法比原算法都得到了不同程度的提高，其中mushroom提高的幅度最大，原算法需要25.469s，改進(jìn)算法只要0.578s。原算法隨著數(shù)據(jù)集的增加，運(yùn)行時(shí)間逐漸增加，但改進(jìn)算法的運(yùn)行時(shí)間不一定。比如，mushroom比chess大，但時(shí)間明顯要少于chess，主要原因有2點(diǎn)：①mushroom中含有大量冗余屬性，約簡(jiǎn)結(jié)果中只有3個(gè)屬性，算法只需迭代3次，而chess卻需要迭代31次；②mushroom的約簡(jiǎn)結(jié)果是 ｛a5，a20，a3｝ （a5表示第5個(gè)條件屬性），a5的正域基數(shù)為2868，所以在下一次迭代中只需考慮2776個(gè)對(duì)象，a20的正域基數(shù)為2664，所以在下一次迭代中只需考慮112個(gè)對(duì)象，這樣一來(lái)，計(jì)算時(shí)間大大降低了。所以改進(jìn)的算法在mushroom數(shù)據(jù)集上運(yùn)行效率最高。由此說(shuō)明，改進(jìn)算法要優(yōu)于原算法。

表7 約簡(jiǎn)結(jié)果對(duì)比圖 （屬性個(gè)數(shù)）

圖1 算法運(yùn)行時(shí)間對(duì)比1（單位：秒）

圖2 算法運(yùn)行時(shí)間對(duì)比2（單位：秒）

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

本文針對(duì)大多數(shù)屬性約簡(jiǎn)算法運(yùn)行效率不高的問(wèn)題，提出了一種基于決策表分解的屬性約簡(jiǎn)算法。此算法通過(guò)不斷對(duì)決策表進(jìn)行分解，避免了許多重復(fù)計(jì)算，降低了計(jì)算時(shí)間。結(jié)合正域基數(shù)和互信息增益能更客觀地衡量屬性的重要性。對(duì)算法進(jìn)行了時(shí)間復(fù)雜度分析，并通過(guò)實(shí)驗(yàn)對(duì)算法的效率進(jìn)行了測(cè)試。實(shí)驗(yàn)結(jié)果表明，該算法運(yùn)行效率要優(yōu)于文獻(xiàn) ［5］中的算法。當(dāng)數(shù)據(jù)集越大且含有較多冗余屬性時(shí)，提高的幅度越明顯。今后的工作集中在以下幾個(gè)方面：對(duì)連續(xù)型數(shù)據(jù)屬性約簡(jiǎn)的研究，對(duì)不相容決策表的約簡(jiǎn)研究，以及將約簡(jiǎn)結(jié)果用于分類中。

［1］Pawlak Z.Rough sets ［J］.International Journal of Computer and Information Sciences，1982，11 （5）：341－356

［2］MIAO Duoqian，LI Daoguo.Rough set theory，algorithm and application ［M］.Beijing：Tsinghua University Press，2008（in Chinese）.［苗奪謙，李道國(guó).粗糙集理論﹑算法與應(yīng)用［M］.北京：清華大學(xué)出版社，2008.］

［3］WANG Hui，WANG Jing，ZHANG Caiyun.Improvement of attribute reduction algorithm based on distinction matrix ［J］.Journal of Wuhan University of Science and Technology，2011，34 （2）：126－130 （in Chinese）.［王慧，王京，張彩云.基于區(qū)分矩陣的屬性約簡(jiǎn)算法改進(jìn)策略 ［J］.武漢科技大學(xué)學(xué)報(bào)，2011，34 （2）：126－130.］

［4］WANG Xizhao，WANG Tingting，ZHAI Junhai.An attribute reduction algorithm based on instance selection ［J］.Journal of Computer Research and Development，2012，49 （11）：2305－2310 （in Chinese）.［王熙照，王婷婷，翟俊海.基于樣例選取的屬性約簡(jiǎn)算法 ［J］.計(jì)算機(jī)研究與發(fā)展，2012，49 （11）：2305－2310.］

［5］SHEN Wei，ZHAO Jiabao.A new heuristic reduction algorithm of rough sets decision－making table ［J］.Computer Technology and Development，2010，20 （10）：16－20 （in Chinese）.［沈偉，趙佳寶.一種新的啟發(fā)式粗糙集決策表屬性約簡(jiǎn)算法 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20 （10）：16－20.］

［6］GE Hao，LI Longshu，YANG Chuanjian.Improvement to quick attribution reduction algorithm ［J］.Journal of Chinese Computer System，2009，30 （2）：308－314 （in Chinese）.［葛浩，李龍澍，楊傳健.改進(jìn)的快速屬性約簡(jiǎn)算法 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009，30 （2）：308－314.］

［7］XUE Shengjun，GUO Qiang.A minimal attribute reduction algorithm ［J］.Journal of Wuhan University of Technology（Transportation Science ＆ Engineering），2012，36 （3）：515－519（in Chinese）.［薛勝軍，郭強(qiáng).一種改進(jìn)的最小屬性約簡(jiǎn)算法 ［J］.武漢理工大學(xué)學(xué)報(bào) （交通科學(xué)與工程版），2012，36 （3）：515－519.］

［8］JIANG Yu，LIU Yintian，LI Chao.Fast algorithm for computing attribute reduction based on Bucket Sort ［J］.Control and Decision，2011，26 （2）：207－212 （in Chinese）.［蔣瑜，劉胤田，李超，基于Bucket Sort的快速屬性約簡(jiǎn)算法 ［J］.控制與決策，2011，26 （2）：207－212.］

［9］Qian Yuhua，Liang Jiye，Witold Pedrycz.Positive approximation：An accelerator for attribute reduction in rough set theory［J］.Artificial Intelligence，2010，174 （9－10）：597－618.

［10］Qian Yuhua，Witold Pedrycz，Liang JiYe.An efficient accelerator for attribute reduction from incomplete data in rough set frame－work ［J］.Pattern Recognition，2011，44 （8）：1658－1670.

［11］Meng Zuqiang，Shi Zhongzhi.A fast approach to attribute reduction in incomplete decision systems with tolerance relationbased rough sets ［J］.Information Sciences，2009，179（16）：2774－2793.