高學(xué)義，張楠，童向榮，姜麗麗

(1. 煙臺(tái)大學(xué) 數(shù)據(jù)科學(xué)與智能技術(shù)山東省高校重點(diǎn)實(shí)驗(yàn)室，山東 煙臺(tái) 264005； 2. 煙臺(tái)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山東 煙臺(tái) 264005)

廣義分布保持屬性約簡(jiǎn)研究

高學(xué)義1,2，張楠1,2，童向榮1,2，姜麗麗1,2

(1. 煙臺(tái)大學(xué) 數(shù)據(jù)科學(xué)與智能技術(shù)山東省高校重點(diǎn)實(shí)驗(yàn)室，山東 煙臺(tái) 264005； 2. 煙臺(tái)大學(xué) 計(jì)算機(jī)與控制工程學(xué)院，山東 煙臺(tái) 264005)

屬性約簡(jiǎn)是粗糙集理論的重要研究?jī)?nèi)容之一。分布約簡(jiǎn)保證約簡(jiǎn)前后每個(gè)對(duì)象的概率分布保持不變，即保證每條規(guī)則的置信度在約簡(jiǎn)前后不發(fā)生改變。實(shí)際應(yīng)用中，人們往往更加關(guān)注可信度較高或較低的規(guī)則。因此，在本文中引入了廣義分布保持屬性約簡(jiǎn)，該屬性約簡(jiǎn)可以保證規(guī)則的置信度P(P∈[0,α]或[β,1])在約簡(jiǎn)前后不變。同時(shí)，給出了廣義分布保持屬性約簡(jiǎn)的判定方法與基于差別矩陣的廣義分布保持屬性約簡(jiǎn)算法，深入討論了幾種特殊情形下的廣義分布保持約簡(jiǎn)。最后，在4個(gè)UCI數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)分析表明，幾種特殊情形下的廣義分布保持屬性約簡(jiǎn)可退化為已有的一些屬性約簡(jiǎn)，且在不同置信區(qū)間下求得的廣義分布保持屬性約簡(jiǎn)存在包含關(guān)系，驗(yàn)證了相關(guān)結(jié)論的正確性。

分布保持；屬性約簡(jiǎn)；粗糙集；概率分布；差別矩陣

中文引用格式：高學(xué)義，張楠，童向榮，等.廣義分布保持屬性約簡(jiǎn)研究[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(3): 377-385.

英文引用格式：GAO Xueyi，ZHANG Nan，TONG Xiangrong，et at. Research on attribute reduction using generalized distribution preservation[J]. CAAI transactions on intelligent systems, 2017, 12(3): 377-385.

粗糙集理論是由波蘭學(xué)者Pawlak教授于1982年提出的一種用于處理和分析不確定、不精確數(shù)據(jù)的數(shù)學(xué)方法與工具[1-4]。目前，粗糙集理論在機(jī)器學(xué)習(xí)、決策分析、模式識(shí)別、數(shù)據(jù)挖掘和智能信息處理等領(lǐng)域得到了廣泛應(yīng)用。

屬性約簡(jiǎn)或知識(shí)約簡(jiǎn)是粗糙集理論的重要研究?jī)?nèi)容之一，其本質(zhì)是獲取保持知識(shí)庫(kù)某種分類(lèi)能力在約簡(jiǎn)前后不發(fā)生改變的最小屬性子集描述，國(guó)內(nèi)外學(xué)者做了大量的相關(guān)研究工作。1992年，Skowron[5]提出了差別矩陣的概念，為獲取信息系統(tǒng)或決策表的所有約簡(jiǎn)或最小約簡(jiǎn)提供了理論基礎(chǔ)；1998年，Kryszkiewicz[6]討論了基于差別矩陣的不完備信息系統(tǒng)廣義決策保持屬性約簡(jiǎn)問(wèn)題；2003年，張文修等[7]給出了分布約簡(jiǎn)和分配約簡(jiǎn)的差別矩陣約簡(jiǎn)方法，并提出了最大分布約簡(jiǎn)；2007年，徐偉華等[8]給出了優(yōu)勢(shì)關(guān)系下基于差別矩陣的分布約簡(jiǎn)和最大分布約簡(jiǎn)；2009年，苗奪謙等[9]提出了不可分辨關(guān)系保持屬性約簡(jiǎn)和相應(yīng)的差別矩陣構(gòu)造方法；2010年，張楠等[10]討論了區(qū)間值信息系統(tǒng)下的屬性約簡(jiǎn)問(wèn)題。為了提高屬性約簡(jiǎn)的算法效率，多種啟發(fā)式屬性約簡(jiǎn)算法相繼被提出。1999年，苗奪謙等[11]從信息論的角度給出了屬性重要度的度量方法，在此基礎(chǔ)上提出了基于互信息的啟發(fā)式約簡(jiǎn)算法；2002年，王國(guó)胤等[12]提出了基于條件信息熵的啟發(fā)式屬性約簡(jiǎn)算法；2010年，錢(qián)宇華等[13]提出了正向近似的基本概念并將其應(yīng)用于啟發(fā)式屬性約簡(jiǎn)的構(gòu)造過(guò)程，提高了屬性約簡(jiǎn)的計(jì)算效率；2011年，錢(qián)宇華等[14-15]進(jìn)一步將正向近似應(yīng)用于不完備決策表的啟發(fā)式屬性約簡(jiǎn)，改善了不完備決策表下啟發(fā)式屬性約簡(jiǎn)的求取效率；陳紅梅等[16-17]在動(dòng)態(tài)屬性約簡(jiǎn)方面做了大量的研究工作；文獻(xiàn)[18-19]對(duì)現(xiàn)有的屬性約簡(jiǎn)之間的關(guān)系進(jìn)行了深入討論與研究。

分布約簡(jiǎn)保證每個(gè)對(duì)象在約簡(jiǎn)前后的概率分布保持不變，即保證每條規(guī)則的置信度在約簡(jiǎn)前后不發(fā)生改變。在實(shí)際應(yīng)用中，人們往往更關(guān)注可信度較高或較低的規(guī)則[20]，分布約簡(jiǎn)的標(biāo)準(zhǔn)過(guò)于嚴(yán)格，很多對(duì)實(shí)際決策無(wú)用的規(guī)則的置信度在約簡(jiǎn)前后也要保持不變，很可能使得最終約簡(jiǎn)過(guò)于冗長(zhǎng)，對(duì)實(shí)際決策造成一定的干擾。本文在分布約簡(jiǎn)的基礎(chǔ)上，通過(guò)弱化分布約簡(jiǎn)的約簡(jiǎn)標(biāo)準(zhǔn)，提出了一種新的屬性約簡(jiǎn)，即廣義分布保持屬性約簡(jiǎn)，該屬性約簡(jiǎn)可以保證規(guī)則的置信度(P∈[0,α]或[β,1])在約簡(jiǎn)前后不變，并對(duì)廣義分布保持屬性約簡(jiǎn)的方法和相關(guān)性質(zhì)進(jìn)行了研究和討論。

1 廣義分布保持屬性約簡(jiǎn)

定義2 設(shè)決策表DT=(U,AT∪D,V,f)，U={u1,u2,…,un}，U/D={D1,D2,…,D|U/D|}，記dj為Dj對(duì)應(yīng)的決策值，則?ui∈U，A?AT,ui在A下關(guān)于決策屬性D的[α,β]決策-置信度序偶集定義為

定義3 給定決策表DT=(U,AT∪D,V,f)，U={u1,u2,…,un}，?A?AT，若A是一個(gè)廣義分布保持約簡(jiǎn)，當(dāng)且僅當(dāng)以下兩個(gè)條件成立：

由定義3可知，對(duì)于置信度在[α,β]內(nèi)的規(guī)則，它們的置信度在廣義分布保持約簡(jiǎn)前后保持不變。

2 廣義分布保持屬性約簡(jiǎn)的判定與方法

首先，給出廣義分布協(xié)調(diào)集的等價(jià)證明。

證明 不妨記ρ([ui]A)={[uj]AT:[uj]AT?[ui]A}，其中i,j∈{1,2,…,n}。由于A?AT，故ρ([ui]A)構(gòu)成[ui]A的一個(gè)劃分。

定理1給出了判斷屬性子集是廣義分布協(xié)調(diào)集的方法，由此可進(jìn)一步得到廣義分布保持約簡(jiǎn)的方法，在此可給出廣義分布差別矩陣的概念。

定義

定義5 設(shè)DT=(U,AT∪D,V,f)，M[α,β]為廣義分布保持約簡(jiǎn)的差別矩陣，其對(duì)應(yīng)的差別函數(shù)為

通過(guò)化DF(M[α,β])的主合取范式轉(zhuǎn)化為主析取范式即可得到所有廣義分布保持屬性約簡(jiǎn)。

定理3 設(shè)DT=(U,AT∪D,V,f)，M[α,β]為DT的廣義分布保持約簡(jiǎn)的差別矩陣，且α和β滿(mǎn)足(α=0∧β∈[0,1])或(α∈[0,1]∧β=1)。DF(M[α,β])是由M[α,β]導(dǎo)出的差別函數(shù)，DF(M[α,β])的極小析取范式為

3 廣義分布保持屬性約簡(jiǎn)算法

本節(jié)給出廣義分布保持約簡(jiǎn)算法(generalized distribution preservation reduction algorithm，GDPRA)，算法描述如下。

輸入 決策表DT=(U,AT∪D,V,f)，α和β。

輸出 DT的所有廣義分布保持屬性約簡(jiǎn)。

1) 計(jì)算每個(gè)對(duì)象在條件屬性集下關(guān)于決策屬性的置信度分布μAT。

2) 根據(jù)每個(gè)對(duì)象的置信度分布μAT獲取每個(gè)對(duì)象的[α,β]決策-置信度序偶集。

3) 根據(jù)對(duì)象之間的決策-置信度序偶集構(gòu)造相應(yīng)的廣義分布差別矩陣。

4) 根據(jù)廣義分布差別矩陣構(gòu)造廣義分布差別函數(shù)，并通過(guò)吸收率進(jìn)行簡(jiǎn)化。

5) 在DF(M[α,β])基礎(chǔ)上通過(guò)結(jié)合律獲取所有的廣義分布保持約簡(jiǎn)。

其中，α和β滿(mǎn)足(α=0∧β∈[0,1])或(α∈[0,1]∧β=1)。

例1 如表1所示，論域?yàn)閁={u1,u2,u3,u4}，AT={a1,a2,a3,a4}為條件屬性集，D=ggsm2cw為決策屬性，分別求[α,β]=[0,0.3]以及[α,β]=[0.8,1]時(shí)的所有廣義分布保持約簡(jiǎn)。

表1 決策表

1)獲取每個(gè)對(duì)象的置信度分布

U/AT={E1,E2,E3}

U/D={D1,D2,D3}

E1={u1}

E2={u2}

E3={u3,u4}

D1={u1}

D2={u2,u4}

D3={u3}

μAT(u1)=(1,0,0)

μAT(u2)=(0,1,0)

μAT(u3)=(0,0.5,0.5)

μAT(u4)=(0,0.5,0.5)

2)獲取每個(gè)對(duì)象的[α,β]決策-置信度序偶集

當(dāng)α=0，β=0.3時(shí)

當(dāng)α=0.8，β=1時(shí)

3)構(gòu)造廣義分布差別矩陣

[α,β]=[0,0.3]時(shí)對(duì)應(yīng)的廣義分布差別矩陣如表2所示，[α,β]=[0.8,1]時(shí)對(duì)應(yīng)的廣義分布差別矩陣如表3所示。

表2 廣義分布差別矩陣1

表3 廣義分布差別矩陣2

4)獲取差別函數(shù)并進(jìn)行簡(jiǎn)化

DF(M[0,0.3])=(a2)∧(a3)

DF(M[0.8,1])=(a2)∧(a3)

5)通過(guò)結(jié)合律獲取所有的廣義分布保持約簡(jiǎn)

由計(jì)算得，[α,β]=[0,0.3]時(shí)和[α,β]=[0.8,1]時(shí)的所有廣義分布保持約簡(jiǎn)均為{a2,a3}。

4 一些特殊情形下的討論

1)α=β=0時(shí)

當(dāng)α和β取值均為0時(shí)，廣義分布保持約簡(jiǎn)實(shí)質(zhì)是保證對(duì)于置信度為0的規(guī)則在約簡(jiǎn)前后的置信度均為0，而對(duì)于置信度不為0的規(guī)則在約簡(jiǎn)前后的置信度均不為0，由此可得如下結(jié)論。

定理4 設(shè)決策表DT=(U,AT∪D,V,f)，對(duì)于?R?AT且R≠?，α=β=0，若R是決策表DT的一個(gè)廣義分布保持約簡(jiǎn)，則R必定同時(shí)是決策表DT的一個(gè)廣義決策保持約簡(jiǎn)。

2)α=β=1時(shí)

顯然，當(dāng)α=β=1時(shí)，廣義分布保持約簡(jiǎn)實(shí)質(zhì)是保證了置信度為1的規(guī)則在約簡(jiǎn)前后的置信度保持不變，由此可得如下結(jié)論。

定理5 決策表DT=(U,AT∪D,V,f)，對(duì)于?R?AT且R≠?，令α=β=1，若R是決策表DT的一個(gè)廣義分布保持約簡(jiǎn)，則R必定同時(shí)是決策表DT的一個(gè)正域保持約簡(jiǎn)。

綜上，由于?ui,uj∈U，故在α=β=1的條件下，MPOS=M[1,1]成立，故R是決策表DT的廣義分布保持約簡(jiǎn)，則R必定同時(shí)是決策表DT的一個(gè)正域保持約簡(jiǎn)，證畢。

3)α=0，β=1時(shí)

當(dāng)α=0，β=1時(shí)，廣義分布保持約簡(jiǎn)實(shí)質(zhì)是保證了置信度在[0,1]內(nèi)的所有規(guī)則在約簡(jiǎn)前后的置信度不變，同時(shí)易得，此時(shí)對(duì)象的[α,β]決策-置信度序偶集等價(jià)于在決策等價(jià)類(lèi)劃分上的置信度分布，由此可得如下結(jié)論。

定理6 決策表DT=(U,AT∪D,V,f)，對(duì)于?R?AT且R≠?，α=0且β=1，若R是決策表DT的一個(gè)廣義分布保持約簡(jiǎn)，則R必定同時(shí)是決策表DT的一個(gè)分布保持約簡(jiǎn)。

綜上，圖1給出了廣義分布保持約簡(jiǎn)與上述幾種約簡(jiǎn)之間的關(guān)系。

圖1 幾種不同約簡(jiǎn)之間的關(guān)系Fig.1 Relationships among different reductions

例2 表1所示決策表，論域U={u1,u2,u3,u4}，AT={a1,a2,a3,a4}為條件屬性集，D=ieoy0mc為決策屬性。由

U/AT={E1,E2,E3}

E1={u1}

E2={u2}

E2={u3,u4}

U/D={D1,D2,D3}

D1={u1}

D2={u2,u4}

D3={u3}

POSAT(D)={u1,u2}

δAT(u1)={0}

δAT(u2)={1}

δAT(u3)={1,2}

δAT(u4)={1,2}

μAT(u1)=(1,0,0)

μAT(u2)=(0,1,0)

μAT(u3)=(0,0.5,0.5)

μAT(u4)=(0,0.5,0.5)

求得正域保持約簡(jiǎn)為{a2,a3},廣義決策保持約簡(jiǎn)為{a2,a3},分布保持約簡(jiǎn)為{a2,a3}。

據(jù)此構(gòu)造廣義分布差別矩陣，如表4所示。

表4 廣義分布差別矩陣

由廣義分布差別矩陣可得所有的廣義分布保持約簡(jiǎn)為{a2,a3}，與正域約簡(jiǎn)一致。同理，α=β=0時(shí)的廣義分布保持約簡(jiǎn)為{a2,a3}，與廣義決策約簡(jiǎn)一致;α=0,β=1時(shí)的廣義分布保持約簡(jiǎn)為{a2,a3}，與分布約簡(jiǎn)一致。

由定理4～6可得如下結(jié)論。

推論1 設(shè)DT=(U,AT∪D,V,f)，置信度區(qū)間為[α,β]，?A?AT，且A是置信度區(qū)間[α,β]下的一個(gè)廣義分布保持約簡(jiǎn)，進(jìn)一步，若給定置信度區(qū)間[α′,β′]，且滿(mǎn)足[α′,β′]?[α,β]，則?A′?A，使得A′是置信度區(qū)間[α′,β′]下的一個(gè)廣義分布保持約簡(jiǎn)，且滿(mǎn)足A′?A。其中，α和β滿(mǎn)足(α=0∧β∈[0,1])或(α∈[0,1]∧β=1)。

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

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

注：BTSC為數(shù)據(jù)集Blood Transfusion Service Center的縮寫(xiě)

實(shí)驗(yàn)分為兩部分。第1部分驗(yàn)證置信度區(qū)間分別為[1.0,1.0]、[0.0,0.0]以及[0.0,1.0]時(shí)，廣義分布保持約簡(jiǎn)可分別退化為正域保持約簡(jiǎn)、廣義決策保持約簡(jiǎn)以及分布約簡(jiǎn)，同時(shí)，也可驗(yàn)證廣義分布保持約簡(jiǎn)算法的正確性；第2部分驗(yàn)證在較小的置信度區(qū)間下求得的廣義分布保持約簡(jiǎn)是在較大的置信度區(qū)間下求得的廣義分布保持約簡(jiǎn)的子集。

5.1 廣義分布保持屬性約簡(jiǎn)的退化情形

本節(jié)中，分別令[α,β]取值為[1.0,1.0]、[0.0,0.0]和[0.0,1.0]，并求4個(gè)UCI數(shù)據(jù)集的廣義分布保持約簡(jiǎn)，然后，分別求它們?cè)谡虮３旨s簡(jiǎn)算法(positive region preservation reduction algorithm，PRPRA)，廣義決策保持約簡(jiǎn)算法(algorithm of generalized decision preservation reduction，AGDPR)以及分布保持約簡(jiǎn)算法(distribution preservation reduction algorithm，DPRA)下的約簡(jiǎn)，通過(guò)前后對(duì)比，驗(yàn)證廣義分布保持約簡(jiǎn)在3個(gè)特殊置信度區(qū)間下的退化情況，實(shí)驗(yàn)結(jié)果如表6～8所示。

表6 GDPRA和PRPRA的約簡(jiǎn)結(jié)果([α,β]=[1,1])

Table 6 Reduction results for GDPRA and PRPRA ([α,β]=[1,1])

數(shù)據(jù)集GDPRAPRPRAHaberman’sSurvival{2,3}{2,3}BTSC{1,4}{1,4}StoneFlakes{2,6,7}{2,6,7}AirfoilSelf-Noise{1,2,3,4}{1,2,3,4}

表7 GDPRA和GDECPRA的約簡(jiǎn)結(jié)果([α,β]=[0,0])

Table 7 Reduction results for GDPRA and GDECPRA ([α,β]=[0,0])

數(shù)據(jù)集GDPRAGDECPRAHaberman’sSurvival{2,3}{2,3}BTSC{1,4}{1,4}StoneFlakes{2,3,4,5,6,7}{2,3,4,5,6,7}AirfoilSelf-Noise{1,2,3,4,5}{1,2,3,4,5}

表8 GDPRA和DPRA的約簡(jiǎn)結(jié)果([α,β]=[0,1])

Table 8 Reduction results for GDPRA and DPRA ([α,β]=[0,1])

數(shù)據(jù)集GDPRADPRAHaberman’sSurvival{1,2,3}{1,2,3}BTSC{1,2,4},{1,3,4}{1,2,4},{1,3,4}StoneFlakes{2,3,4,5,6,7}{2,3,4,5,6,7}AirfoilSelf-Noise{1,2,3,4,5}{1,2,3,4,5}

當(dāng)[α,β]分別為[1.0,1.0]、 [0.0,0.0]以及[0.0,1.0]時(shí)，GDPRA的約簡(jiǎn)結(jié)果分別同PRPRA、AGDPR以及DPRA的約簡(jiǎn)結(jié)果一致，驗(yàn)證了相關(guān)結(jié)論的正確性。

5.2 不同置信度區(qū)間下約簡(jiǎn)的包含關(guān)系

本部分實(shí)驗(yàn)設(shè)置如下：首先，固定α的值為0.0，令β取值范圍為0.0～1.0，取值間隔為0.2，記錄隨β取值的變化在不同置信度區(qū)間下求得的廣義分布保持約簡(jiǎn)。同樣的，固定β的值為1.0，令α取值范圍為0.0～1.0，取值間隔為0.2，記錄隨α取值的變化在不同置信度區(qū)間下求得的廣義分布保持約簡(jiǎn)，實(shí)驗(yàn)結(jié)果如表9～12所示。

表9 數(shù)據(jù)集1：Haberman’s survival

表10 數(shù)據(jù)集2：blood transfusion service center

表11 數(shù)據(jù)集3：stone flakes

表12 數(shù)據(jù)集4：airfoil self-noise

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

實(shí)際中，具有較高或較低置信度的規(guī)則往往更易受到人們的關(guān)注，若通過(guò)分布約簡(jiǎn)進(jìn)行規(guī)則提取，提取的規(guī)則可能過(guò)于冗長(zhǎng)，不便于實(shí)際決策。因此，本文對(duì)分布約簡(jiǎn)的約簡(jiǎn)標(biāo)準(zhǔn)進(jìn)行弱化，提出了廣義分布保持約簡(jiǎn)的概念。理論與實(shí)驗(yàn)分析表明，當(dāng)置信度區(qū)間取某些特殊值時(shí)，廣義分布保持屬性約簡(jiǎn)可退化為現(xiàn)有的一些屬性約簡(jiǎn)，表明了廣義分布保持屬性約簡(jiǎn)具有一定的泛化性能，同時(shí)為深入研究不同屬性約簡(jiǎn)之間的相互關(guān)系開(kāi)闊了研究思路。實(shí)驗(yàn)數(shù)據(jù)表明，廣義分布保持屬性約簡(jiǎn)較分布約簡(jiǎn)可以獲取更加簡(jiǎn)短的規(guī)則，且根據(jù)實(shí)際需要可以調(diào)整置信度區(qū)間以獲取所需規(guī)則，使得廣義分布保持屬性約簡(jiǎn)可以適應(yīng)不同的實(shí)際需求。但考慮到本文提出的算法主要是通過(guò)差別矩陣獲取所有的廣義分布保持屬性約簡(jiǎn)，其時(shí)間和空間復(fù)雜度較高，不便于在實(shí)際應(yīng)用中推廣，具有一定的局限性，故開(kāi)發(fā)更為高效的廣義分布保持屬性約簡(jiǎn)算法是未來(lái)主要的研究工作之一。

[1]PAWLAK Z. Rough sets[J]. International journal of com-puter and information sciences, 1982, 11(5): 341-356.

[2]PAWLAK Z. Rough sets: theoretical aspects of reasoning about data[M]. Boston：Kluwer Academic Publishers, 1992.

[3]張文修. 粗糙集理論與方法[M]. 北京：科學(xué)出版社, 2001.

[4]王國(guó)胤, 姚一豫, 于洪. 粗糙集理論與應(yīng)用研究綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2009, 32(7): 1229-1246. WANG Guoyin, YAO Yiyu, YU Hong. A survey on rough set theory and applications[J]. Chinese journal of computers, 2009, 32(7): 1229-1246.

[5]SKOWRON A, RAUSZER C. The discernibility matrices and functions in information systems[J]. Theory and decision library, 1992, 11: 331-362.

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

[7]張文修, 米據(jù)生, 吳偉志. 不協(xié)調(diào)目標(biāo)信息系統(tǒng)的知識(shí)約簡(jiǎn)[J]. 計(jì)算機(jī)學(xué)報(bào), 2003, 26(1): 12-18. ZHANG Wenxiu, MI Jusheng, WU Weizhi. Knowledge reductions in inconsistent information systems[J]. Chinese journal of computers, 2003, 26(1): 12-18.

[8]徐偉華, 張文修. 基于優(yōu)勢(shì)關(guān)系下不協(xié)調(diào)目標(biāo)信息系統(tǒng)的分布約簡(jiǎn)[J]. 模糊系統(tǒng)與數(shù)學(xué), 2007, 21(4): 124-131. XU Weihua, ZHANG Wenxiu. Distribution reduction in inconsistent information systems based on dominance relations[J]. Fuzzy systems and mathematics, 2007, 21(4):124-131.

[9]MIAO Duoqian, ZHAO Yan, YAO Yiyu, et al. Relative reducts in consistent and inconsistent decision tables of the Pawlak rough set model[J]. Information sciences, 2009, 179(24): 4140-4150.

[10]張楠, 苗奪謙, 岳曉冬. 區(qū)間值信息系統(tǒng)的知識(shí)約簡(jiǎn)[J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(8): 1362-1371. ZHANG Nan, MIAO Duoqian, YUE Xiaodong. Approaches to knowledge reduction in interval-valued information systems[J]. Journal of computer research and development, 2010, 47(8): 1362-1371.

[11]苗奪謙, 胡桂榮. 知識(shí)約簡(jiǎn)的一種啟發(fā)式算法[J]. 計(jì)算機(jī)研究與發(fā)展, 1999, 36(6): 681-684. MIAO Duoqian, HU Guirong. A heuristic algorithm for reduction of knowledge[J]. Journal of computer research and development, 1999, 36(6): 681-684.

[12]王國(guó)胤, 于洪, 楊大春. 基于條件信息熵的決策表約簡(jiǎn)[J]. 計(jì)算機(jī)學(xué)報(bào), 2002, 25(7): 759-766. WANG Guoyin, YU Hong, YANG Dachun. Decision table reduction based on conditional information entropy[J]. Chinese journal of computers, 2002, 25(7): 759-766.

[13]QIAN Yuhua, LIANG Jiye, PEDRYCZ W, et al. Positive approximation: an accelerator for attribute reduction in rough set theory[J]. Artificial intelligence, 2010, 174(9): 597-618.

[14]QIAN Yuhua, LIANG Jiye, PEDRYCZ W, et al. An efficient accelerator for attribute reduction from incom-plete data in rough set framework[J]. Pattern recognition, 2011, 44(8): 1658-1670.

[15]錢(qián)宇華, 梁吉業(yè), 王鋒. 面向非完備決策表的正向近似特征選擇加速算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(3): 435-442. QIAN Yuhua, LIANG Jiye, WANG Feng. A positive approximation based accelerated algorithm to feature selection from incomplete decision tables[J]. Chinese journal of computers, 2011, 34(3): 435-442.

[16]CHEN Hongmei, LI Tianrui, RUAN Da, et al. A rough-set based incremental approach for updating approximations under dynamic maintenance environments[J]. IEEE transactions on knowledge and data engineering, 2013, 25(2): 274-284.

[17]CHEN Hongmei, LI Tianrui, LUO Chuan, et al. A rough set-based method for updating decision rules on attribute values’ coarsening and refining[J]. IEEE transactions on knowledge and data engineering, 2014, 26(12): 2866-2899.

[18]JIA Xiuyi, SHANG Lin, ZHOU Bing, et al. Generalized attribute reduct in rough set theory[J]. Knowledge-based systems, 2015, 91: 204-218.

[19]ZHOU Jie, MIAO Duoqian, PEDRYCZ W, et al. Analysis of alternative objective functions for attribute reduction in complete decision tables[J]. Soft computing, 2011, 15(8): 1601-1616.

[20]ZHANG Xiao, MEI Changlin, CHEN Degang, et al. Multi-confidence rule acquisition and confidence-preserved attribute reduction in interval-valued decision systems[J]. International journal of approximate reasoning, 2014, 55(8): 1787-1804.

Research on attribute reduction using generalizeddistribution preservation

GAO Xueyi1,2， ZHANG Nan1,2， TONG Xiangrong1,2， JIANG Lili1,2

(1.Key Lab for Data Science and Intelligent Technology of Shandong Higher Education Institutes, Yantai University, Yantai 264005, China; 2. School of Computer and Control Engineering, Yantai University, Yantai 264005, China)

Attribute reduction is a pertinent issue in rough set theory. Distribution reduction ensures that the probability distribution of each target does not change before and after reduction; i.e., it ensures that the confidence of every rule remains unchanged before and after reduction. In actual applications, people are often interested in rules that have higher or lower confidences. Thus, attribute reduction based on generalized distribution preservation is proposed in this paper. Confidences in [0,α] or [β, 1] were unchanged using the proposed technique. We also propose judgment methods for generalized-distribution-preservation attribute reduction and investigate the generalized attribute-reduction algorithm based on a discernibility matrix. Some special cases with respect to generalized-distribution-preservation attribute reduction are discussed in depth. Finally, experiments on four data sets downloaded from UCI show that some special cases with respect to generalized distribution preservation reduction could degenerate into some existing attribute reductions and inclusion relations exist in generalized distribution preservation attribute reduction under different confidence intervals, verifying the correctness of the relevant conclusions.

distribution preservation; attribute reduction; rough sets; probability distribution; discernibility matrix

10.11992/tis. 21704025

http://kns.cnki.net/kcms/detail/23.1538.TP.20170703.1853.010.html

2017-04-19. 網(wǎng)絡(luò)出版日期：2017-07-03.

國(guó)家自然科學(xué)基金項(xiàng)目(61403329, 61572418, 61502410, 61572419)；山東省自然科學(xué)基金項(xiàng)目(ZR2013FQ020, ZR2015PF 010)；山東省高等學(xué)校科技計(jì)劃項(xiàng)目(J15LN09,116LN17).

張楠.E-mail：zhangnan0851@163.com.

TP181

A

1673-4785(2017)03-0377-09

高學(xué)義，男，1992年生，碩士研究生，主要研究方向?yàn)榇植诩?shù)據(jù)挖掘與機(jī)器學(xué)習(xí)。

張楠，男，1979年生，博士，主要研究方向?yàn)榇植诩?、認(rèn)知信息學(xué)與人工智能。

童向榮，男，1975年生，教授,博士，主要研究方向?yàn)槎郃gent系統(tǒng)、分布式人工智能與數(shù)據(jù)挖掘技術(shù)。