高學義，張楠，童向榮，姜麗麗

(1. 煙臺大學 數(shù)據(jù)科學與智能技術山東省高校重點實驗室，山東 煙臺 264005； 2. 煙臺大學 計算機與控制工程學院，山東 煙臺 264005)

廣義分布保持屬性約簡研究

高學義1,2，張楠1,2，童向榮1,2，姜麗麗1,2

(1. 煙臺大學 數(shù)據(jù)科學與智能技術山東省高校重點實驗室，山東 煙臺 264005； 2. 煙臺大學 計算機與控制工程學院，山東 煙臺 264005)

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

分布保持；屬性約簡；粗糙集；概率分布；差別矩陣

中文引用格式：高學義，張楠，童向榮，等.廣義分布保持屬性約簡研究[J]. 智能系統(tǒng)學報， 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.

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

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

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

1 廣義分布保持屬性約簡

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

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

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

2 廣義分布保持屬性約簡的判定與方法

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

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

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

定義

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

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

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

3 廣義分布保持屬性約簡算法

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

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

輸出 DT的所有廣義分布保持屬性約簡。

1) 計算每個對象在條件屬性集下關于決策屬性的置信度分布μAT。

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

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

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

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

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

例1 如表1所示，論域為U={u1,u2,u3,u4}，AT={a1,a2,a3,a4}為條件屬性集，D=syggg00為決策屬性，分別求[α,β]=[0,0.3]以及[α,β]=[0.8,1]時的所有廣義分布保持約簡。

表1 決策表

1)獲取每個對象的置信度分布

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)獲取每個對象的[α,β]決策-置信度序偶集

當α=0，β=0.3時

當α=0.8，β=1時

3)構造廣義分布差別矩陣

[α,β]=[0,0.3]時對應的廣義分布差別矩陣如表2所示，[α,β]=[0.8,1]時對應的廣義分布差別矩陣如表3所示。

表2 廣義分布差別矩陣1

表3 廣義分布差別矩陣2

4)獲取差別函數(shù)并進行簡化

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

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

5)通過結合律獲取所有的廣義分布保持約簡

由計算得，[α,β]=[0,0.3]時和[α,β]=[0.8,1]時的所有廣義分布保持約簡均為{a2,a3}。

4 一些特殊情形下的討論

1)α=β=0時

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

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

2)α=β=1時

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

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

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

3)α=0，β=1時

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

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

綜上，圖1給出了廣義分布保持約簡與上述幾種約簡之間的關系。

圖1 幾種不同約簡之間的關系Fig.1 Relationships among different reductions

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

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)

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

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

表4 廣義分布差別矩陣

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

由定理4～6可得如下結論。

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

5 實驗分析

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

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

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

5.1 廣義分布保持屬性約簡的退化情形

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

表6 GDPRA和PRPRA的約簡結果([α,β]=[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的約簡結果([α,β]=[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的約簡結果([α,β]=[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}

當[α,β]分別為[1.0,1.0]、 [0.0,0.0]以及[0.0,1.0]時，GDPRA的約簡結果分別同PRPRA、AGDPR以及DPRA的約簡結果一致，驗證了相關結論的正確性。

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

本部分實驗設置如下：首先，固定α的值為0.0，令β取值范圍為0.0～1.0，取值間隔為0.2，記錄隨β取值的變化在不同置信度區(qū)間下求得的廣義分布保持約簡。同樣的，固定β的值為1.0，令α取值范圍為0.0～1.0，取值間隔為0.2，記錄隨α取值的變化在不同置信度區(qū)間下求得的廣義分布保持約簡，實驗結果如表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 結束語

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

[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]. 北京：科學出版社, 2001.

[4]王國胤, 姚一豫, 于洪. 粗糙集理論與應用研究綜述[J]. 計算機學報, 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é)調目標信息系統(tǒng)的知識約簡[J]. 計算機學報, 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)勢關系下不協(xié)調目標信息系統(tǒng)的分布約簡[J]. 模糊系統(tǒng)與數(shù)學, 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)的知識約簡[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]苗奪謙, 胡桂榮. 知識約簡的一種啟發(fā)式算法[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]王國胤, 于洪, 楊大春. 基于條件信息熵的決策表約簡[J]. 計算機學報, 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]錢宇華, 梁吉業(yè), 王鋒. 面向非完備決策表的正向近似特征選擇加速算法[J]. 計算機學報, 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)絡出版日期：2017-07-03.

國家自然科學基金項目(61403329, 61572418, 61502410, 61572419)；山東省自然科學基金項目(ZR2013FQ020, ZR2015PF 010)；山東省高等學校科技計劃項目(J15LN09,116LN17).

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

TP181

A

1673-4785(2017)03-0377-09

高學義，男，1992年生，碩士研究生，主要研究方向為粗糙集、數(shù)據(jù)挖掘與機器學習。

張楠，男，1979年生，博士，主要研究方向為粗糙集、認知信息學與人工智能。

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