基于知識粒度的不完備決策表的屬性約簡算法

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

(1.廣西師范大學 廣西多源信息挖掘與安全重點實驗室,廣西 桂林 541004； 2.廣西師范大學 計算機科學與信息工程學院,廣西 桂林 541004)

基于知識粒度的不完備決策表的屬性約簡算法

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

(1.廣西師范大學 廣西多源信息挖掘與安全重點實驗室,廣西 桂林 541004； 2.廣西師范大學 計算機科學與信息工程學院,廣西 桂林 541004)

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

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

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

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

1粗糙集基本概念

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

定義2[3]在不完備決策表s=(U,C,D,V,f)中，令B?C，定義U上的容差關系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具有容差關系的全體對象集{y∈U|(x,y)∈T(B)}。

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

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

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

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

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

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

2粒度差別矩陣相關概念

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

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

定義7[7]設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關于D的一個屬性約簡，此約簡記為基于粒度差別矩陣的屬性約簡。

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

定理2[7]基于知識粒度的屬性約簡定義與基于粒度差別矩陣的屬性約簡定義是等價的。

定理2說明基于知識粒度的屬性約簡可以轉化到粒度差別矩陣上進行。

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

(4)

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

(5)

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

4屬性約簡算法

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

算法1論域U對屬性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}；(其中在此求劃分時*單獨放到一塊)。

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

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

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

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

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

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

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

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

②對除*隊列的每個非空隊列作如下處理：

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

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

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

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

輸出屬性約簡Red(C)。

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

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

3)for(k=2,k

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

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

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

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

5實例分析

為了證明算法的可行性，以文獻[16]中的不完備決策表1為例子進行相應說明。

表1　不完備決策表

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

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

|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|，他們對應的屬性為X、S、P、M，則有Red(C)={X}，RC=?。

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

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

輸入U/?={x1,x2,x3,x4,x5,x6}

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

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

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

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

對第1個非空隊列有pos1={x1,x2},Neg1=?；

由算法2，2)的②計算每個非空隊列中的posi/D。

每個非空隊列中的Negi/D：

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

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

求|FX(U,S)|。

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

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

對其劃分有pos1={x1,x2},Neg1=?;

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

對A2={x3,x4,x5}求得

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

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

對第1個非空隊列有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/(X∪({S})={{x1,x2},{x3},{x4,x5}由算法2的2)①對A1={x1,x2}求得

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

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

對第1個非空隊列有pos1={x1}，Neg1=?;

對第2個非空隊列pos2={x2}，Neg2=?。

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

對A2={x3}求

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

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

對A3={x4,x5}求得

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

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

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

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

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

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

6實驗對比

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

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

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

表2中的數(shù)據(jù)集,|C|代表條件屬性個數(shù),|U|代表對象個數(shù)。

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

7結束語

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

參考文獻:

[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]. 小型微型計算機系統(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]李秀紅, 史開泉. 一種基于知識粒度的不完備信息系統(tǒng)的屬性約簡算法[J]. 計算機科學, 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]. 河南師范大學學報：自然科學版, 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]張清國, 鄭雪峰. 基于知識粒度的不完備決策表的屬性約簡的矩陣算法[J]. 計算機科學, 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]張偉, 徐章艷, 王曉宇. 一種結合概率啟發(fā)信息和知識粒度的屬性約簡算法[J]. 計算機應用與軟件, 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]王煒, 徐章艷, 李曉瑜. 不完備決策表中基于對象矩陣屬性約簡算法[J]. 計算機科學, 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]舒文豪, 徐章艷, 錢文彬, 等. 一種快速的不完備決策表屬性約簡算法[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]韓智東, 王志良, 高靜. 用差別矩陣思想設計的基于正區(qū)域的高效屬性約簡算法[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]鐘珞, 梅磊, 郭翠翠, 等. 粒矩陣屬性約簡的啟發(fā)式算法[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]. 計算機科學, 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]張清國, 鄭雪峰. 相容矩陣的高效屬性約簡算法[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)中的不確定性與知識獲取[M]. 北京: 科學出版社, 2005: 1-70.

[17]王煒, 徐章艷, 李曉瑜.不完備決策表中基于對象矩陣屬性約簡算法[J]. 計算機科學, 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]周建華, 徐章艷, 章晨光. 一種基于沖突域的不完備決策表屬性約簡算法[J]. 計算機應用與軟件, 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)絡出版日期：2015-12-29.

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

通信作者：喬麗娟. E-mail：347671379@qq.com.

中圖分類號：TP18

文獻標志碼：A

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

作者簡介：

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

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

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

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