喬麗娟，徐章艷，謝小軍，朱金虎，陳曉飛，李娟

(1.廣西師范大學(xué) 廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004； 2.廣西師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院,廣西 桂林 541004)

基于知識(shí)粒度的不完備決策表的屬性約簡(jiǎn)算法

喬麗娟1, 2，徐章艷1, 2，謝小軍1, 2，朱金虎1, 2，陳曉飛2，李娟2

(1.廣西師范大學(xué) 廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004； 2.廣西師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院,廣西 桂林 541004)

摘要：知識(shí)粒度是屬性約簡(jiǎn)的有效方法，但對(duì)于大型的決策表，計(jì)算知識(shí)粒度過(guò)于費(fèi)時(shí)，算法效率不高。在引入粒度差別矩陣后，設(shè)計(jì)了一個(gè)計(jì)算粒度差別矩陣中條件屬性出現(xiàn)頻率的函數(shù)，有效地降低粒度差別矩陣的存儲(chǔ)空間，根據(jù)此函數(shù)設(shè)計(jì)了一個(gè)高效屬性約簡(jiǎn)算法。新算法使得時(shí)間復(fù)雜度與空間復(fù)雜度都降為O(K|C||U|)(其中K=max{|Tc(xi)|, xi∈U}和O(|U|)。最后通過(guò)實(shí)例仿真說(shuō)明了此算法的高效性和可行性。

關(guān)鍵詞：屬性約簡(jiǎn)；知識(shí)粒度；不完全決策表；條件屬性頻率；差別矩陣；啟發(fā)信息

中文引用格式：?jiǎn)帖惥辏煺缕G，謝小軍，等.基于知識(shí)粒度的不完備決策表的屬性約簡(jiǎn)算法[J]. 智能系統(tǒng)學(xué)報(bào)， 2016, 11(1): 129-135.

英文引用格式：QIAO Lijuan, XU Zhangyan, XIE Xiaojun，et al. Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation[J]. CAAI Transactions on Intelligent Systems, 2016, 11(1): 129-135.

波蘭的數(shù)學(xué)家Pawlak在20世紀(jì)80年代提出的粗糙集是一種新型的用來(lái)處理不完全、不精確與不相容的數(shù)學(xué)工具和理論[1-2]。經(jīng)過(guò)了30多年的研究和發(fā)展，粗糙集理論已在知識(shí)發(fā)現(xiàn)、數(shù)據(jù)挖掘、模式識(shí)別等領(lǐng)域得到了大量應(yīng)用[3-4]。屬性約簡(jiǎn)作為粗糙集理論的重要研究?jī)?nèi)容，已被廣大學(xué)者所研究，提出了圍繞完備決策表的屬性約簡(jiǎn)算法，但是現(xiàn)實(shí)生活中的數(shù)據(jù)往往存在誤差，缺失及多源等特征。如何對(duì)不完備決策表進(jìn)行直接處理，已成為粗糙集理論的一個(gè)研究熱點(diǎn)[4]。近年來(lái)針對(duì)不完備決策表的研究也取得了顯著的進(jìn)步，已有學(xué)者提出很多有效的不完備決策表屬性約簡(jiǎn)算法[5-11]。知識(shí)粒度[12-13]作為粗糙集理論中度量屬性約簡(jiǎn)的重要方法之一，被廣泛運(yùn)用于不完備屬性約簡(jiǎn)算法。文獻(xiàn)[5]以屬性重要性為啟發(fā)信息,設(shè)計(jì)了一個(gè)基于知識(shí)粒度的屬性約簡(jiǎn)算法[5];文獻(xiàn)[6]通過(guò)不斷向核屬性集中添加屬性的方法，設(shè)計(jì)出一種基于相對(duì)知識(shí)粒度的不完備決策表屬性約簡(jiǎn)算法[6]；文獻(xiàn)[7]定義了一個(gè)粒度差別矩陣，進(jìn)而設(shè)計(jì)了基于知識(shí)粒度的不完備決策表的屬性約簡(jiǎn)算法[7],其時(shí)間復(fù)雜度為max{O(|C|2|U||Upos|)，O(|K||C|U|)}，其中K=max{|TC(xi)|,xi∈U},其空間復(fù)雜度為max{O(|C||U||Upos|),O(|U|)};文獻(xiàn)[8]給出了一個(gè)計(jì)算條件屬性頻率的公式，設(shè)計(jì)一個(gè)基于知識(shí)粒度的屬性約簡(jiǎn)算法[8]；文獻(xiàn)[9] 設(shè)計(jì)了一種基于對(duì)象矩陣的屬性約簡(jiǎn)算法[9]；文獻(xiàn)[11]提出簡(jiǎn)化差別矩陣定義，設(shè)計(jì)了一種快速的屬性約簡(jiǎn)算法[11]；文獻(xiàn)[12]中根據(jù)區(qū)分對(duì)象對(duì)集的思想，設(shè)計(jì)了基于正區(qū)域的屬性約簡(jiǎn)算法[12]；文獻(xiàn)[13]根據(jù)粒計(jì)算的思想構(gòu)建了粒矩陣，在此基礎(chǔ)上，設(shè)計(jì)了屬性約簡(jiǎn)算法。文獻(xiàn)[14]在粒計(jì)算屬性約簡(jiǎn)算法的基礎(chǔ)上進(jìn)行了改進(jìn)，得到一個(gè)新的算法。上述算法大多因?yàn)橐啻斡?jì)算知識(shí)粒度，導(dǎo)致計(jì)算效率都不太理想，為此設(shè)計(jì)出基于知識(shí)粒度的高效屬性約簡(jiǎn)算法具有非常重要的現(xiàn)實(shí)意義[5]。

差別矩陣作為粗糙集理論的重要技術(shù)之一，被廣泛應(yīng)用，但是求解差別矩陣費(fèi)時(shí)，本文引入了基于粒度的差別矩陣，利用條件屬性在區(qū)分對(duì)象時(shí)出現(xiàn)頻率的屬性約簡(jiǎn)思想，設(shè)計(jì)一個(gè)基于粒度差別矩陣計(jì)算屬性頻率的啟發(fā)函數(shù)。

1粗糙集基本概念

在五元組中，如果至少有一個(gè)屬性a∈C，使得Va包含空值(用*表示)，即至少有一個(gè)屬性a∈U，存在一個(gè)a∈U，使得f(x,a)=*，稱之為不完備決策表。

定義2[3]在不完備決策表s=(U,C,D,V,f)中，令B?C，定義U上的容差關(guān)系T(B)為T(B)={(x,y)∈U×U|?b∈B}，f(x,b)=f(y,b)∨f(x,b)=*∨f(y,b)=*}。用TB(x)表示在B中與x具有容差關(guān)系的全體對(duì)象集{y∈U|(x,y)∈T(B)}。

性質(zhì)1[16]設(shè)S=(U，C，D，V，f)是一個(gè)不完備信息系統(tǒng)，知識(shí)B?C的知識(shí)粒度定義為GD(B)，則1/|U|≤GD(B)≤1。

性質(zhì)2[16]設(shè)S=(U,C,D,V,f)是一個(gè)不完備信息系統(tǒng)，其中P,Q?C，如果?i∈{1,2,…,|U|}有TP(xi)?TQ(xi)，則GD(P)≤GD(Q)。

知識(shí)粒度可以描述知識(shí)的區(qū)分能力,知識(shí)粒度越小,其區(qū)分能力越強(qiáng)，反之區(qū)分能力越弱[5]。

定義4[5]在不完備決策表S=(U,C,D,V,f)中 , 知識(shí)B(B?C) 是C關(guān)于D的一個(gè)知識(shí)粒度的屬性約簡(jiǎn),當(dāng)且僅當(dāng)B滿足條件:

1)GD(B)=GD(C);

2)?b∈B?GD((B-))≠GD(C)。

2粒度差別矩陣相關(guān)概念

定義6[11]設(shè)在一個(gè)不完備決策表S=(U,C,D,V,f)中，U=Upos∪Uneg,定義粒度差別矩陣M=(m(i,j)),其元素定義如下：

式中：k=1,2,…,r。

定義7[7]設(shè)M=(m(i,j))為不完備決策表S=(U,C,D,V,f)的粒度差別矩陣,?B?C,若B滿足：

1)??≠m(i,j)∈M,有B∩m(i,j)≠?;

2)?a∈B,B′=B-{a}均不滿足(1)。

則稱B是C關(guān)于D的一個(gè)屬性約簡(jiǎn)，此約簡(jiǎn)記為基于粒度差別矩陣的屬性約簡(jiǎn)。

證明由定義1知：命題顯然成立。

定理2[7]基于知識(shí)粒度的屬性約簡(jiǎn)定義與基于粒度差別矩陣的屬性約簡(jiǎn)定義是等價(jià)的。

定理2說(shuō)明基于知識(shí)粒度的屬性約簡(jiǎn)可以轉(zhuǎn)化到粒度差別矩陣上進(jìn)行。

針對(duì)不完備決策表，文獻(xiàn)[7]中給出了一個(gè)基于粒度差別矩陣的屬性約簡(jiǎn)算法，其時(shí)間復(fù)雜度為max{O(|C|2|Upos||U|),O(K|U||C|)}。算法對(duì)粒度差別矩陣進(jìn)行遍歷，若只包含一個(gè)條件屬性就將其放入屬性約簡(jiǎn)中，并去掉差別矩陣中任何含有該條件屬性的差別元素,直至差別矩陣為空。該算法雖然有效降低了時(shí)間復(fù)雜度，但是構(gòu)造粒度差別矩陣仍然需要占用大量的空間，對(duì)于處理大型數(shù)據(jù)集仍然具有一定的難度。

經(jīng)分析，算法中在粒度差別矩陣中出現(xiàn)的條件屬性才是能區(qū)分對(duì)象的條件屬性，由于構(gòu)造粒度差別矩陣耗費(fèi)空間，參考文獻(xiàn)[16]的方法，設(shè)計(jì)一種計(jì)算粒度差別矩陣中含有的條件屬性頻率的函數(shù)，然后給出計(jì)算該函數(shù)的快速算法，無(wú)須構(gòu)造粒度差別矩陣就可以將其中能有效區(qū)分對(duì)象的條件屬性找出，以降低算法的時(shí)間和空間復(fù)雜度。

3計(jì)算屬性頻率的啟發(fā)函數(shù)

根據(jù)定義6，粒度差別矩陣中包含的條件屬性可由兩部分產(chǎn)生，設(shè)對(duì)象都在Upos里產(chǎn)生的條件屬性的個(gè)數(shù)為N1，則

(1)

兩個(gè)對(duì)象一個(gè)在Upos中，另一個(gè)在Uneg中，產(chǎn)生的條件屬性頻率為N2，則

(2)

計(jì)算條件屬性的頻率函數(shù)|FB(U,a)|如下：

(3)

證明由粒度差別矩陣的定義知，計(jì)算Ai/{a}={Ai1,Ai2,…,Aik}產(chǎn)生的條件屬性頻率，可分兩部分計(jì)算，一種是對(duì)象都在Upos中;另一種是一個(gè)在Upos中，而另一個(gè)在Uneg中的。

2)若一個(gè)對(duì)象在Upos中，另一個(gè)對(duì)象在Uneg中，由劃分的定義知，同屬一個(gè)集合里的兩個(gè)對(duì)象值相等，即只有不同劃分集合里才有可能產(chǎn)生條件屬性頻率，且Upos和Uneg之間要求決策值不同，故需要對(duì)每個(gè)劃分集合里屬于Upos的集合對(duì)D劃分，同時(shí)屬于Uneg的集合也對(duì)D劃分。所以，Negj/D劃分集合里每個(gè)集合與posi/D劃分集合里對(duì)于決策屬性在不同劃分集合里就能產(chǎn)生條件屬性頻率。

為了方便敘述，假設(shè)將Ai所有集合中屬于正域的所有集合對(duì)D劃分posi/D存放在一個(gè)矩陣中，矩陣的行表示每一個(gè)非空集合對(duì)D的劃分，矩陣的列表示決策值相同的集合，生成的矩陣為

(4)

同理，將Ai所有集合中屬于負(fù)域的所有集合對(duì)D劃分Negj/D存放在另一個(gè)矩陣中，生成的矩陣為

(5)

根據(jù)定義6可知，只有屬性值不同且不為缺省值的才能包含條件屬性，所以在本文的所有算法中，對(duì)象U對(duì)屬性a的劃分，將含有缺省值的放在劃分的最后一個(gè)集合里，不予處理。

4屬性約簡(jiǎn)算法

首先，對(duì)不完備決策系統(tǒng)中的對(duì)象進(jìn)行劃分。

算法1論域U對(duì)屬性a的劃分

輸入不完備決策表S=(U,C,D,V,f)，C={a1,a2,…,am}，U={x1,x2,…,x|U|}

輸出U/a={A1,A2,…,At}

1)t=1；At={xi}；

2)for(j=2;j<|U|+1;j++)。

若任一條件屬性ai∈C(i=1,2,…,|C|)均有f(xi,ai)=f(xj,ai)≠*，則At=At∪{xj}；否則t=t+1;At={xj}；(其中在此求劃分時(shí)*單獨(dú)放到一塊)。

3)輸出U/a={A1,A2,…,At}。

算法1中，1)、3)時(shí)間復(fù)雜度忽略不計(jì)，2)的時(shí)間復(fù)雜度為O(|U|)，則算法2的時(shí)間復(fù)雜度是O(|U|)，空間復(fù)雜度為O(|U|)。

算法2求條件屬性頻率的函數(shù)

輸入U(xiǎn)/A={A1,A2,…,At}，條件屬性的最大值和最小值分別標(biāo)記為Mb,mb；

輸出U/(A∪)，條件屬性頻率函數(shù)|Fa(U,b)|；

1)|FA(U,b)|=0，U/(A∪)=?；

2)對(duì)?Ai={x1,x2,…,xj}∈U/A,以靜態(tài)鏈表為存儲(chǔ)空間，依次放入對(duì)象x1,x2,…,xj;令表頭指針指向xi;

①建立Mb-mb+2空隊(duì)列，令front[k]和end[k](k=0,1,2,…,Mb-mb+1)分別為第k個(gè)隊(duì)列的頭指針和尾指針，將鏈表中的對(duì)象x∈Ai按鏈表中的次序分配到第f(x,b)-mb個(gè)隊(duì)列中去，將鏈表中的對(duì)象值為*的對(duì)象分配到*隊(duì)列中。

②對(duì)除*隊(duì)列的每個(gè)非空隊(duì)列作如下處理：

3)輸出U/(A∪)，條件屬性總頻率數(shù)|FA(U,b)|。

算法時(shí)間空間復(fù)雜度分析：算法2中1)的時(shí)間復(fù)雜度忽略不計(jì)，2)①的時(shí)間復(fù)雜度為O(|Ai|)，設(shè)posi/={Ai1,Ai2,…,Aik}，則2)②a時(shí)間復(fù)雜度為O(Aij)(j=1,2,…,k)，2)②b時(shí)間復(fù)雜度為O(Aij)，即2)②時(shí)間復(fù)雜度為O(|Ai|)，2)時(shí)間復(fù)雜度O(|Ai|)+O(|A2|)+…+O(|Ai|)≤O(|U|)。故算法2的最壞時(shí)間復(fù)雜度為O(|U|)，同理可得最壞空間復(fù)雜度為O(|U|)。

算法3以條件屬性的頻率為啟發(fā)信息的屬性約簡(jiǎn)算法

輸入不完備決策表S=(U,C,D,V,f),C=(c1,c2,…,cm),U={x1,x2,…,xn}；

輸出屬性約簡(jiǎn)Red(C)。

2)將Ki按從小到大運(yùn)用快速排序方法得到

|Ki1|≤|Ki2|≤…≤|Kim|，它們對(duì)應(yīng)的屬性為ci1，ci2,…,cim令Red(C)={ci1}；

3)for(k=2,k

由算法3計(jì)算；|Fred(U,ci(k-1))|

4)輸出屬性約簡(jiǎn)Red(C)。

算法正確性分析：若|FRed(U,ci(k-1))|=0，即當(dāng)前屬性不能將兩個(gè)對(duì)象區(qū)分開(kāi)，則RRed∪{cik}=RRed，則由算法3知，當(dāng)輸出約簡(jiǎn)Red(C)時(shí)，有RC=RRed。由定理2知，算法3求出的屬性約簡(jiǎn)就是基于知識(shí)粒度的屬性約簡(jiǎn)。

算法時(shí)間復(fù)雜度分析：算法3的1)由文獻(xiàn)[11]知時(shí)間復(fù)雜度為O(K|C||U|)(其中K=max{|Tc(xi)|,xi∈U}),空間復(fù)雜度為O(|U|)。2)的時(shí)間復(fù)雜度為O(|C|)+O(|U|),空間復(fù)雜度為O(|U|)(由算法1的復(fù)雜度分析可得)。3)的時(shí)間復(fù)雜度為O(|C||U|),空間復(fù)雜度為O(|U|)。故算法3的時(shí)間復(fù)雜度為O(K|C||U|)(其中K=max{|TC(xi)|,xi∈U},空間復(fù)雜度為O(|U|)。

5實(shí)例分析

為了證明算法的可行性，以文獻(xiàn)[16]中的不完備決策表1為例子進(jìn)行相應(yīng)說(shuō)明。

表1　不完備決策表

為方便計(jì)算，將屬性值從左至右簡(jiǎn)記為P、M、S、X，則該表的條件屬性為C={P,M,S,X}。

由算法3 1)求得各屬性的知識(shí)粒度分別是：

|K1|=GD(P)=(4+4+6+4+6+4)/36=28/36;

|K2|=GD(M)=(6+6+6+6+6+6)/36=36/36;

|K3|=GD(S)=(5+5+5+5+5+1)/36=26/36;

|K3|=GD(X)=(3+3+4+4+4+6)/36=24/36;

Upos={x1,x2,x3},Uneg={x4,x5,x6}

由2)排序|K4|≤|K3|≤|K1|≤|K2|，他們對(duì)應(yīng)的屬性為X、S、P、M，則有Red(C)={X}，RC=?。

由3)計(jì)算|F?(U,X)|=6，計(jì)算的|FX(U,S)|=6，計(jì)算的|F{X,S}(U，P)|=1，計(jì)算的|F{X，S，P}{U,M}|=0，算法結(jié)束，輸出約簡(jiǎn)Red(C)={X,S,P}。

由算法2求|FRed(X)|。

輸入U(xiǎn)/?={x1,x2,x3,x4,x5,x6}

由算法2，2)的2)①對(duì)A1={x1,x2,x3,x4,x5,x6}求得：

front[1]→x1→x2→end[1]；

front[2]→x3→x4→x5→end[2]；

front[*]→x6→end[*]；

對(duì)第1個(gè)非空隊(duì)列有pos1={x1,x2},Neg1=?；

由算法2，2)的②計(jì)算每個(gè)非空隊(duì)列中的posi/D。

每個(gè)非空隊(duì)列中的Negi/D：

對(duì)A*={x6},因A*不能區(qū)分對(duì)象，故無(wú)需計(jì)算。

故|F?(U，X)|=2N1+N2=2*2+2=6,

求|FX(U,S)|。

輸入U(xiǎn)/(X)={{x1,x2},{x3,x4,x5}}

由算法2 2)的①對(duì)A1={x1,x2}求得front[1]→x1→x2→end[1];

對(duì)其劃分有pos1={x1,x2},Neg1=?;

易知，|FX(U,S)|1=0,

對(duì)A2={x3,x4,x5}求得

front[1]→x3→end[1]；

front[2]→x4→x5→end[2]；

對(duì)第1個(gè)非空隊(duì)列有pos1={x3},Neg1=?;

易知N2=0+0+0+1*3+0+1*3=6

|FX(U,S)|2=2N1+N2=0+6=6

|FX(U,S)|=|FX(U,S)|1+|FX(U,S)|2=6

輸入U(xiǎn)/(X∪({S})={{x1,x2},{x3},{x4,x5}由算法2的2)①對(duì)A1={x1,x2}求得

front[1]→x1→end[1]；

front[2]→x2→end[2]；

對(duì)第1個(gè)非空隊(duì)列有pos1={x1}，Neg1=?;

對(duì)第2個(gè)非空隊(duì)列pos2={x2}，Neg2=?。

故|F{X,S}(U,P)|1=1。

對(duì)A2={x3}求

front[1]→x3→end[1];

易知，|F{X,S}(U,P)|2=0

對(duì)A3={x4,x5}求得

front[1]→x4→end[1];

front[*]→x5→end[*];

易知，|F{X,S}(U,P)|3=0，

輸入U(xiǎn)/({X,S}∪{P})={{x1},{x2},{x4}}

求得|F{X,S,P}(U,M)|=0。

實(shí)例說(shuō)明，該約簡(jiǎn)與文獻(xiàn)[5]相同。新算法不僅通俗易懂，且在粒度差別矩陣的基礎(chǔ)上大大減少存儲(chǔ)空間，且大大提高了算法收斂的時(shí)間速度，即新算法是一個(gè)高效可行的屬性約簡(jiǎn)算法。

6實(shí)驗(yàn)對(duì)比

為了更好地說(shuō)明新算法比其他同類算法更具有有效性和實(shí)用性，選用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的6個(gè)數(shù)據(jù)集：Credit、Car、Hepatitis、Soybean-large、Vote和Wine進(jìn)行實(shí)驗(yàn)。選取比較新的算法進(jìn)行對(duì)比，考察新算法的高效性，分別與文獻(xiàn)[17]、文獻(xiàn)[18]、文獻(xiàn)[11]進(jìn)行對(duì)比，文獻(xiàn)[17]是在差別矩陣的基礎(chǔ)上提出的屬性約簡(jiǎn)算法，文獻(xiàn)[17]算法運(yùn)行時(shí)間記為t1，文獻(xiàn)[18]是基于沖突域的屬性約簡(jiǎn)算法，算法運(yùn)行時(shí)間記為t2，文獻(xiàn)[11] 算法運(yùn)行時(shí)間記為t3，本文算法運(yùn)行時(shí)間記為tnew，對(duì)比結(jié)果見(jiàn)表2。為了增強(qiáng)實(shí)驗(yàn)結(jié)果的可靠性，本文所取的最終時(shí)間為 7次實(shí)驗(yàn)結(jié)果的平均值。實(shí)驗(yàn)運(yùn)行的環(huán)境為：CPU為AMD，2.00 GB內(nèi)存，在Visual Stdio2010平臺(tái)。

表2　UCI數(shù)據(jù)集信息

圖1　UCI數(shù)據(jù)集對(duì)比Fig.1　The comparison of UCI data sets

表2中的數(shù)據(jù)集,|C|代表?xiàng)l件屬性個(gè)數(shù),|U|代表對(duì)象個(gè)數(shù)。

從表2 中的實(shí)驗(yàn)數(shù)據(jù)可以看出，對(duì)于小的數(shù)據(jù)集({Hepatitis,15,199}，{Wine,14,178})上,對(duì)比的4種算法的運(yùn)行時(shí)間相差不大。但是對(duì)于較大的數(shù)據(jù)集，運(yùn)行時(shí)間就相差很大，而且隨著數(shù)據(jù)集的擴(kuò)大，新算法的運(yùn)行時(shí)間相對(duì)于其他3種算法的增長(zhǎng)幅度小得多，表明新算法具有較好的可擴(kuò)展性。

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

在決策表中，知識(shí)粒度是有效進(jìn)行屬性約簡(jiǎn)的方法，以往的屬性約簡(jiǎn)算法由于計(jì)算知識(shí)粒度浪費(fèi)了大量時(shí)間，算法效率不高。因此，本文設(shè)計(jì)一個(gè)基于知識(shí)粒度的計(jì)算條件屬性頻率的啟發(fā)函數(shù)，以知識(shí)粒度為啟發(fā)信息，提出新的屬性約簡(jiǎn)算法，大大降低了算法的時(shí)間復(fù)雜度。在以后的研究中，可以將計(jì)算屬性頻率的思想利用到其他屬性約簡(jiǎn)的方法中，如相容矩陣、差別矩陣等，也可進(jìn)一步應(yīng)用到規(guī)則獲取中。

參考文獻(xiàn):

[1]PAWLAK Z, GRZYMALA-BUSSE J, SLOWINSKI R. Rough sets[J]. Communications of the ACM, 1995, 8(1): 89-95.

[2]PAWLAK Z. Rough set theory and its applications to data analysis[J]. Cybernetics and systems: an international, 1998, 29(7): 661-668.

[3]KRYSZKIEWICZ M. Rough set approach to incomplete information systems[J]. Information sciences, 1998, 112 (1-4): 39-49.

[4]錢文彬, 楊炳儒, 徐章艷, 等. 基于不完備決策表的容差類高效求解算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2013, 34(2): 345-350.

QIAN Wenbin, YANG Bingru, XU Zhangyan, et al. Efficient algorithm for computing tolerance classes of incomplete decision table[J]. Journal of Chinese computer systems, 2013, 34(2): 345-350.

[5]李秀紅, 史開(kāi)泉. 一種基于知識(shí)粒度的不完備信息系統(tǒng)的屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)科學(xué), 2006, 33(11): 169-170, 199.

LI Xiuhong, SHI Kaiquan. A knowledge granulation-based algorithm for attribute reduction under incomplete information systems[J]. Computer science, 2006, 33(11): 169-170, 199.

[6]史先紅, 史進(jìn)玲. 一種基于相對(duì)粒度的不完備決策表約簡(jiǎn)算法[J]. 河南師范大學(xué)學(xué)報(bào)：自然科學(xué)版, 2010, 38(4): 51-53, 84.

SHI Xianhong, SHI Jinling. A reduction algorithm based on relative granularity in incomplete decision tables[J]. Journal of Henan normal university:natural science, 2010, 38(4): 51-53, 84.

[7]張清國(guó), 鄭雪峰. 基于知識(shí)粒度的不完備決策表的屬性約簡(jiǎn)的矩陣算法[J]. 計(jì)算機(jī)科學(xué), 2012, 39(2): 209-211, 243.

ZHANG Qingguo, ZHENG Xuefeng. Discernibility matrix algorithm of attribute reduction based on knowledge granulaion in incomplete decision table[J]. Computer science, 2012, 39(2): 209-211, 243.

[8]張偉, 徐章艷, 王曉宇. 一種結(jié)合概率啟發(fā)信息和知識(shí)粒度的屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2013, 30(7): 43-45, 50.

ZHANG Wei, XU Zhangyan, WANG Xiaoyu. An attribute reduction algorithm combining probability heuristic information and knowledge granularity[J]. Computer applications and software, 2013, 30(7): 43-45, 50.

[9]PAWLAK Z. Rough sets and intelligent data analysis[J]. Information sciences, 2002, 147(1-4): 1-12.

[10]王煒, 徐章艷, 李曉瑜. 不完備決策表中基于對(duì)象矩陣屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)科學(xué), 2012, 39(4): 201-204.

WANG Wei, XU Zhangyan, LI Xiaoyu. Attribute reduction algorithm based on object matrix in incomplete decision table[J]. Computer science, 2012, 39(4): 201-204.

[11]舒文豪, 徐章艷, 錢文彬, 等. 一種快速的不完備決策表屬性約簡(jiǎn)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2011, 32(9): 1867-1871.

SHU Wenhao, XU Zhangyan, QIAN Wenbin, et al. Quick attribution reduction algorithm based on incomplete decision table[J]. Journal of Chinese computer systems, 2011, 32(9): 1867-1871.

[12]韓智東, 王志良, 高靜. 用差別矩陣思想設(shè)計(jì)的基于正區(qū)域的高效屬性約簡(jiǎn)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2011, 32(2): 299-304.

HAN Zhidong, WANG Zhiliang, GAO Jing. Efficient attribute reduction algorithm based on the idea of discernibility object pair set[J]. Journal of Chinese computer systems, 2011, 32(2): 299-304.

[13]鐘珞, 梅磊, 郭翠翠, 等. 粒矩陣屬性約簡(jiǎn)的啟發(fā)式算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2011, 32(3): 516-520.

ZHONG Luo, MEI Lei, GUO Cuicui, et al. Heuristic algorithm for attribute reduction on granular matrix[J]. Journal of Chinese computer systems, 2011, 32(3): 516-520.

[14]唐孝, 舒蘭. 基于粒計(jì)算的屬性約簡(jiǎn)改進(jìn)算法[J]. 計(jì)算機(jī)科學(xué), 2014, 41(11A): 313-315, 346.

TANG Xiao, SHU Lan. Improved algorithm of attribute reduction based on granular computing[J]. Computer science, 2014, 41(11A): 313-315, 346.

[15]張清國(guó), 鄭雪峰. 相容矩陣的高效屬性約簡(jiǎn)算法[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2012, 33(9): 1944-1947.

ZHANG Qingguo, ZHENG Xuefeng. An efficiency attribute reduction algorithm of tolerance matrix[J]. Journal of Chiese computer systems, 2012, 33(9): 1944-1947.

[16]梁吉業(yè), 李德玉. 信息系統(tǒng)中的不確定性與知識(shí)獲取[M]. 北京: 科學(xué)出版社, 2005: 1-70.

[17]王煒, 徐章艷, 李曉瑜.不完備決策表中基于對(duì)象矩陣屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)科學(xué), 2012, 39(4): 201-204.

WANG Wei, XU Zhangyan, LI Xiaoyu. Attribute reduction algorithm based on object matrix in incomplete decision table[J]. Computer science, 2012, 39(4): 201-204.

[18]周建華, 徐章艷, 章晨光. 一種基于沖突域的不完備決策表屬性約簡(jiǎn)算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2014, 31(3): 239-241, 255.

ZHOU Jianhua, XU Zhangyan, ZHANG Chenguang. An incomplete decision table attribute reduction algorithm based on conflict region[J]. Computer applications and software, 2014, 31(3): 239-241, 255.

Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation

QIAO Lijuan1, 2, XU Zhangyan1, 2, XIE Xiaojun1, 2, ZHU Jinhu1, 2, CHEN Xiaofei2, LI Juan2

(1.Guangxi Key Laboratory of Multi-source Information Mining & Security, Guangxi Normal University, Guilin 541004, China; 2. College of Computer Science and Information Technology, Guangxi Normal University, Guilin 541004, China)

Abstract：The use of knowledge granularity is an effective attribute reduction approach. But for a large decision table, computing knowledge granularity is so time-consuming that the algorithm is not efficient for practical use.After the introduction of the discernibility matrix of granularity, a function was designed for calculating the occurrence frequency of condition attributes in the matrix. In this paper, we design an efficient attribute reduction algorithm based on the granularity discernibility matrix. The new algorithm reduces the time and space complexities to O(K|C||U|) (K=max{|Tc(xi)|, xi∈U}) and O(|U|), respectively. The results from our simulation example verify that the proposed algorithm is feasible and highly efficient.

Keywords：attribute reduction; knowledge granularity; incomplete decision table; condition attribute frequency; discernibility matrix; heuristic information

DOI:10.11992/tis.201506029

收稿日期：2015-06-16. 網(wǎng)絡(luò)出版日期：2015-12-29.

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61262004,61363034,60963008);廣西自然科學(xué)基金資助項(xiàng)目(2011GXNSFA018163);大學(xué)生創(chuàng)新資助項(xiàng)目(201410602099).

通信作者：?jiǎn)帖惥? E-mail：347671379@qq.com.

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-4785(2016)01-0129-07

作者簡(jiǎn)介：

喬麗娟，女，1988年生，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘及粗糙集理論。

徐章艷，男，1972年生，教授，博士，主要研究方向?yàn)閿?shù)據(jù)挖掘、模糊集、粗糙集理論。主持國(guó)家自然科學(xué)基金項(xiàng)目1項(xiàng)，參與國(guó)家自然科學(xué)基金項(xiàng)目2項(xiàng)，主持省部級(jí)科研項(xiàng)目1項(xiàng)；廳局級(jí)項(xiàng)目2項(xiàng)；主持校級(jí)項(xiàng)目2項(xiàng)。發(fā)表學(xué)術(shù)論文被SCI檢索3篇，被EI檢索5篇。

謝小軍，男，1990年生，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘及粗糙集理論。

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20151229.0837.020.html