劉旭東，秦亮曦

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

0 引 言

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

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

定義1 決策表信息系統(tǒng)用S＝（U，C∪D，V，f）來表示，其中，U表示一個有限非空對象集 （論域），U ＝ ｛0，1，2，…，n｝；C為條件屬性集，D為決策屬性集，通常決策屬性只有一個，且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)系是一個等價類。屬性集P將論域U劃分為多個等價類，記為U／P。

定義3 對于決策表信息系統(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ù)是衡量屬性重要度的一個重要準(zhǔn)則。

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

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

定義6 互信息I（X，Y）是一個用來測量2個隨機(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，添加一個屬性p∈C到P中，獲得的互信息增加量 （信息增益）為gain＝I（P∪p，D）－I（P，D）。計算每個條件屬性對決策屬性的gain，gain越大，條件屬性就越重要。

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

2.1 算法思路

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

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

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

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

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

1.for每個條件屬性p∈C，do

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

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

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

3.分解決策表for（U／p中每個等價類），do

3.1.if（等價類不在正域中）｛

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

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

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

2.3 實(shí)例分析

在表1中，有7個對象，4個條件屬性a，b，c，d，一個決策屬性e。先劃分等價類，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｝｝。通過等價類計算正域，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個新決策表，見表2、表3。

表1 決策表S

表2 決策表S1

表3 決策表S2

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

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

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

表4 決策表S11

表5 決策表S21

3 實(shí)驗分析

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

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

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

表7 約簡結(jié)果對比圖 （屬性個數(shù)）

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

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

4 結(jié)束語

本文針對大多數(shù)屬性約簡算法運(yùn)行效率不高的問題，提出了一種基于決策表分解的屬性約簡算法。此算法通過不斷對決策表進(jìn)行分解，避免了許多重復(fù)計算，降低了計算時間。結(jié)合正域基數(shù)和互信息增益能更客觀地衡量屬性的重要性。對算法進(jìn)行了時間復(fù)雜度分析，并通過實(shí)驗對算法的效率進(jìn)行了測試。實(shí)驗結(jié)果表明，該算法運(yùn)行效率要優(yōu)于文獻(xiàn) ［5］中的算法。當(dāng)數(shù)據(jù)集越大且含有較多冗余屬性時，提高的幅度越明顯。今后的工作集中在以下幾個方面：對連續(xù)型數(shù)據(jù)屬性約簡的研究，對不相容決策表的約簡研究，以及將約簡結(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）.［苗奪謙，李道國.粗糙集理論﹑算法與應(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ū)分矩陣的屬性約簡算法改進(jìn)策略 ［J］.武漢科技大學(xué)學(xué)報，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）.［王熙照，王婷婷，翟俊海.基于樣例選取的屬性約簡算法 ［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ā)式粗糙集決策表屬性約簡算法 ［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)的快速屬性約簡算法 ［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)的最小屬性約簡算法 ［J］.武漢理工大學(xué)學(xué)報 （交通科學(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的快速屬性約簡算法 ［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.