不協(xié)調(diào)區(qū)間值決策系統(tǒng)的最大分布約簡

尹繼亮，張楠，童向榮，陳曼如

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

屬性約簡[1-7]是粗糙集理論[1-3]的核心研究內(nèi)容之一，在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、決策分析、智能信息處理等領(lǐng)域取得了諸多研究成果。屬性約簡的目的是刪除冗余屬性，只保留使決策表某種分類特征不變的最小屬性子集。差別矩陣方法是一種用于求取所有屬性約簡的有效方法，該方法由Skowron[8]于1982年提出，并將差別矩陣應(yīng)用于正域約簡中。諸多學(xué)者在此基礎(chǔ)上做了大量的研究工作。Kryszkie-wicz[9]于1999年在不完備信息系統(tǒng)下引入廣義決策保持約簡的概念，并提出基于差別矩陣的廣義決策保持約簡方法；2007年，鄧大勇等[10]首先分析了不相容信息系統(tǒng)下幾種約簡目標(biāo)之間的關(guān)系；2009年，Miao等[11]進(jìn)一步分析了3種約簡目標(biāo)之間的關(guān)系，提出不可分辨關(guān)系保持約簡以及相應(yīng)的差別矩陣構(gòu)造方法；Zhou等[12]在2011年對現(xiàn)有的13種屬性約簡目標(biāo)進(jìn)行總結(jié)，并將所有約簡目標(biāo)分為4類，完善了現(xiàn)有約簡目標(biāo)之間的關(guān)系。

分布約簡保持了信息系統(tǒng)約簡前后每條規(guī)則置信度不變。2003年，張文修等[13]提出了分配約簡、分布約簡以及最大分布約簡的概念，并分別給出了基于差別矩陣的分配約簡、分布約簡以及最大分布約簡方法；2007年，徐偉華等[14]在優(yōu)勢關(guān)系下提出了兩種約簡概念，即分布約簡和最大分布約簡，同時(shí)建立了基于差別矩陣的分布和最大分布約簡的具體方法。如某一段時(shí)間內(nèi)的溫度、濕度等區(qū)間值數(shù)據(jù)在現(xiàn)實(shí)環(huán)境中大量存在，它較好地表示了許多不確定類型數(shù)據(jù)，區(qū)間值決策系統(tǒng)是經(jīng)典Pawlak決策系統(tǒng)的推廣，充分地考慮了數(shù)據(jù)的不確定性，在近幾年得到了廣泛關(guān)注。2009年，張楠等[15]定義了 α-極大相容類的概念，提出了區(qū)間值決策系統(tǒng)的廣義決策保持約簡；2016年，張楠等[16]在不協(xié)調(diào)區(qū)間值決策系統(tǒng)中提出確定性規(guī)則保持約簡；2016年，張楠等[17]討論了不協(xié)調(diào)區(qū)間值決策系統(tǒng)中的知識約簡并提出了分布約簡的概念。

基于上述研究，文獻(xiàn)[13]和[14]分別對等價(jià)關(guān)系和優(yōu)勢關(guān)系下的最大分布約簡進(jìn)行了研究，但未有區(qū)間值決策系統(tǒng)的最大分布約簡討論。置信度表示了信息系統(tǒng)中規(guī)則的可信程度，置信度越大，規(guī)則的可信程度越高；置信度越小，規(guī)則的可信程度越低，在實(shí)際應(yīng)用中，人們往往關(guān)注置信度最大的規(guī)則。為此，本文提出了區(qū)間值決策系統(tǒng)的最大分布約簡概念，為區(qū)間值決策系統(tǒng)提供了一種求取所有屬性約簡的新方法。

1 基本知識

1.1 區(qū)間值決策系統(tǒng)的粗糙近似

基于相容關(guān)系的區(qū)間值粗糙集模型是經(jīng)典Pawlak粗糙集模型的推廣，首先給出相關(guān)概念和性質(zhì)。

給定區(qū)間值信息系統(tǒng)[15-18]I S=(U,AT,V,f)，其中， U 是有限對象集合， U ={x1,x2,···,x|U|}； A T是有限屬性集合， A T={a1,a2,···,a|AT|}； V 是全體屬性的值域，即是屬性 ak∈ AT的 值域；f:U×AT →V是一個(gè)信息函數(shù)，它指定論域 U 中每一個(gè)對象 xi在屬性ak上的區(qū)間屬性值，即對任意的 xi∈U ， ak∈AT，有 f (xi,ak)=ak(xi)=[lki,uki]。

如果屬性集 A T由條件屬性集C和決策屬性集D 組 成，C ={a1,a2,···a|C|}， D =j5i0abt0b， 即C ∪ D=AT；V =VC∪VD， 其中， VC為 條件屬性值集合， VD為決策屬性值集合； f :U×C→VC為 區(qū)間值映射，f:U×D→VD為單值映射，則稱區(qū)間值信息系統(tǒng)為區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)。

定義1 設(shè) η1=[lki,uki]和 η2=[lkj,ukj]為任意兩個(gè)區(qū)間值，則區(qū)間值的交運(yùn)算與并運(yùn)算如下。

1)區(qū)間值交運(yùn)算為

目前，度量區(qū)間值相似度比較合理的主要方法有Jaccard相似率、悲觀相似率和樂觀相似率，本文統(tǒng)一采用Jaccard相似率來度量兩個(gè)區(qū)間值的相似度。

定義2 D S=(U,C∪D,V,f)為區(qū)間值決策系統(tǒng)，對 任 意 的 xi,xj∈U ， ak∈C ， 區(qū) 間 值 ak(xi)=和

Jaccard相似率為兩個(gè)區(qū)間數(shù)的交集與并集長度的比值，它適合度量長度相似的兩個(gè)區(qū)間數(shù)。

例1 區(qū)間值決策系統(tǒng) D S=(U,C∪D,V,f)，如表1所示，其中， U ={x1,x2,···,x6}為對象的集合，C ={a1,a2,a3,a4}為 條件屬性的集合， D =j5i0abt0b為決策屬性。

定義3[15]對于區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)， ak∈C， α ∈[0,1]， 則關(guān)于條件屬性 ak的 α-相容關(guān)系定義為

關(guān)于條件屬性子集 A ?U 的 α-相容關(guān)系定義為

性質(zhì)1[15]對于區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)， A ?C， ak∈A， α ∈[0,1]，是屬性 ak的 α-相容關(guān)系，則關(guān)于集合 A的相容關(guān)系為

性質(zhì)2[18]設(shè)區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)，A ?C ， 則具有：

1)自反性：任意 xi∈U，則 (xi,xj)∈。

2)對稱性：任意 xi，xj∈U，若 (xi,xj)∈，則(xj,xi)∈。

3)非傳遞性：任意 xi,xj,xk∈ U ， 若滿足(xi,xk)∈

定義4[18]設(shè)區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)， A ? C， α ∈ [0,1]，是屬性集A的 α-相容關(guān)系，則關(guān)于對象xi在屬性集A下的 α-相容類定義為

對任意 xi∈U ， 區(qū)間值決策系統(tǒng) D S 在 閾值 α下的相容類集合定義為其中 n是論域的個(gè)數(shù)。

經(jīng)典粗糙集中對象間的二元關(guān)系為等價(jià)關(guān)系，具有自反性、傳遞性、對稱性，導(dǎo)出的等價(jià)類集合是對論域的劃分，而定義4中的相容類是對論域的覆蓋。

定義5 給定區(qū)間值決策系統(tǒng)D S=(U,C∪D,V,f)，是 在相容關(guān)系下包含 xi的相容類，則對象集合X 關(guān) 于α -相容關(guān)系的上、下近似[19]分別定義為

集合 X 關(guān) 于 α-相容關(guān)系的正域?yàn)?/p>

下近似是由肯定屬于 X 的對象組成的集合，上近似是由可能屬于 X 的對象組成的集合，根據(jù)上下近似的概念，決策規(guī)則可以分為確定性規(guī)則和可能性規(guī)則。

定義6[16]給定區(qū)間值決策系統(tǒng)D S=(U,C∪D,V,f)，X?U， A ?C ， 則條件屬性集 A的近似分類精度定義為

近似分類精度表示確定性規(guī)則占可能性規(guī)則的比例，近似分類精度越大，區(qū)間值信息系統(tǒng)中確定性規(guī)則越多；反之，確定性規(guī)則越少。

定義7[16]對于區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)， A ?C ， 決策屬性D對 U 的劃分為U/D ={D1,D2,···,D|U/D|}， 決策屬性D關(guān)于 α-相容關(guān)系的上、下近似分別定義為

決策屬性D關(guān)于 α-相容關(guān)系的正域定義為

定義8[16]設(shè)區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)， A ?C ， 決策屬性D對 U 的 劃分為U/D={D1,D2,···,D|U/D|}，則在決策屬性D下，關(guān)于條件屬性集A的近似分類精度定為

定義5和定義6是關(guān)于集合 X的上、下近似和近似分類精度，而定義7和定義8是關(guān)于決策屬性D的上、下近似和近似分類精度。

定義9[13]對于區(qū)間值決策系統(tǒng)D S=(U,C∪D,V,f)，對任意 xi,xj∈U ， 且 i ≠ j， 若xi和 xj具 有 α-相容關(guān)系，且滿足 d (xi)=d(xj)， 則稱 xi∈U 是 關(guān)于屬性集 A ?C的α-協(xié)調(diào)對象；否則稱為α -不協(xié)調(diào)對象。

若存在一個(gè)對象 xi∈U 是 關(guān)于 A ?C 的 α-不協(xié)調(diào)對象，那么稱 D S為不協(xié)調(diào)區(qū)間值決策表，否則稱為協(xié)調(diào)區(qū)間值決策表。

例2 如表1所示的區(qū)間值決策系統(tǒng)，令 α =0.6，則相容關(guān)系為

根據(jù)相似率布爾矩陣，計(jì)算閾值 α =0.6下的相容類集合為

U/D={{x1,x5,x6},{x2,x3,x4}}為決策屬性D對U的劃分，計(jì)算決策屬性D關(guān)于相容關(guān)系 T0.6的上、

C下近似：

計(jì)算條件屬性集C的近似分類精度：

1.2 區(qū)間值決策系統(tǒng)的分布約簡

文獻(xiàn)[16]提出不協(xié)調(diào)區(qū)間決策系統(tǒng)的分布約簡。

定義10 設(shè)區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)， A ? U， U /D={D1,D2,···,D|U/D|}，則xi∈U對應(yīng)的概率分布定義為

定義11 設(shè)區(qū)間值決策系統(tǒng)DS=(U,C∪D,V,f)，U={x1,x2,···,x|U|}， 則對任意1 ≤ i,j≤ |U|：

定義12 設(shè)區(qū)間值決策系統(tǒng) D S=(U,C∪D,V,f)，C={a1,a2,···,a|C|}，i,j)表 示 可 辨識矩陣中第i行j列的元素，基于 α-相容類的分布可辨識函數(shù)定義為與 a1,a2,···,a|C|相對應(yīng)的 |C |個(gè)布爾變量aˉ1,aˉ2,···,aˉ|C|的布爾函數(shù)為此函數(shù)簡稱分布可辨識函數(shù)。這里的 ∨表示滿足 a ∈的全體布爾變量a ˉ的析取式。

定理1 設(shè)區(qū)間值決策系統(tǒng) D S=(U,C∪D,V,f)，是分布可辨識函數(shù)的形式轉(zhuǎn)化，若A?C是分布約簡，當(dāng)且僅當(dāng)A是的一個(gè)蘊(yùn)含項(xiàng)。

基于可辨識矩陣的分布約簡算法(distribution reduction algorithm based on discernibility matrix，DRADM)描述如下。

算法1 DRADM

輸入 區(qū)間值決策系統(tǒng) D S，閾值α。

輸出 區(qū)間值決策系統(tǒng)的所有分布保持約簡結(jié)果。

1)計(jì)算區(qū)間值決策系統(tǒng) D S 的 在閾值 α下的相容類集合 SCα(U)；

2)根據(jù)每個(gè)對象對應(yīng)的相容類，計(jì)算每個(gè)對象相對于每一個(gè)決策類的概率分布

例3 如表1所示的區(qū)間值決策系統(tǒng)，令α =0.6，

根據(jù)例2可知相似布爾矩陣以及相容類集合。

計(jì)算每個(gè)對象對應(yīng)的概率分布：

計(jì)算分布保持約簡可辨識矩陣：

計(jì)算分布約簡可辨識函數(shù)：

轉(zhuǎn)化后的分布約簡可辨識函數(shù)為

因此分布保持約簡為 {a1,a3}和 {a2,a3}。

2 區(qū)間值決策系統(tǒng)的最大分布約簡

本節(jié)在區(qū)間值決策系統(tǒng)中引入最大規(guī)則置信度的概念，提出了不協(xié)調(diào)區(qū)間值決策系統(tǒng)的最大分布約簡算法。

定義13 設(shè)區(qū)間值決策系統(tǒng)D S=(U,C∪D,V,f)，A ? C，U/D={D1,D2,···,D|U/D|}， 則 xi∈ U對應(yīng)的最大概率分布定義為

若對任意的 xi∈U，有 γαA(xi)=γCα(xi)，稱 A是DS中基于 α-相容關(guān)系的最大分布協(xié)調(diào)集，簡稱最大分布協(xié)調(diào)集。若A是最大分布協(xié)調(diào)集，且A的任意真子集都不是最大分布協(xié)調(diào)集，那么稱A是DS中基于 α-相容關(guān)系的最大分布相對約簡，簡稱最大分布約簡。

定義14 設(shè)區(qū)間值決策系統(tǒng)D S=(U,C∪D,V,f)，A?C， xi∈U，若屬性子集A滿足：

那么稱屬性子集A為區(qū)間值決策系統(tǒng)基于相容關(guān)系的最大分布約簡。DS的所有約簡集合記為 α-Reduct， 所有約簡的交集稱為DS的核，記為 α-C ore。

定理2 設(shè)區(qū)間值決策系統(tǒng) D S=(U,C∪D,V,f)，A?C ， 則A是最大分布協(xié)調(diào)集當(dāng)且僅當(dāng)任意 xi,xj∈U，

定義15 設(shè)區(qū)間值決策系統(tǒng) D S=(U,C∪D,V,f)，U={x1,x2,···,x|U|}， 則對任意 i≥ 1,j≤ |U|：

基于α-相容類的最大分布可辨識矩陣是一個(gè)相對于主對角線對稱的矩陣，在進(jìn)行運(yùn)算時(shí)只需考慮其上三角或下三角部分即可。

定理3 設(shè)區(qū)間值決策系統(tǒng) D S=(U,C∪D,V,f)，A?C ， 則A是最大分布協(xié)調(diào)集當(dāng)且僅當(dāng)任意 xi,xj∈U，

“? ”：假設(shè)存在 xi，xj∈U，滿1得 A不是最大分布協(xié)調(diào)集。定理得證。

定義16 設(shè)區(qū)間值決策系統(tǒng)D S=(U,C∪D,V,f)，陣中第i行 j列的元素，基于α-相容類的最大分布可辨識函數(shù)為與 a1,a2,···,am相對應(yīng) |C |個(gè)布爾變量aˉ|C|(i,j)≠ ?}， 為基于 α-相容類的最大分布約簡可辨識函數(shù)，簡稱最大分布可辨識函數(shù)。(i,j)表示滿足(i,j)的全體布爾變量 aˉ的析取式。

基于差別矩陣的分布約簡算法(maximum distribution reduction algorithm based on discernibility matrix，MDRADM)描述如算法 2。

算法2 MDRADM

輸入 區(qū)間值決策系統(tǒng)DS，閾值 α。

輸出 區(qū)間值決策系統(tǒng)的所有最大分布保持約簡結(jié)果。

2)根據(jù)每個(gè)對象對應(yīng)的相容類，計(jì)算每個(gè)對象相對于每一個(gè)決策類的概率分布

3)根據(jù)每個(gè)對象的概率分布，計(jì)算所對應(yīng)的最大分布 γCα(xi)。

算法2是通過可辨識矩陣求得區(qū)間值決策表的所有最大分布保持約簡，因此算法在最壞情況下的時(shí)間復(fù)雜度為 O (|C||U|2)， |C |為 條件屬性的個(gè)數(shù)， |U |為對象的個(gè)數(shù)。

例4 如表1所示的區(qū)間值決策系統(tǒng)，令α=0.6，根據(jù)例2可知相似布爾矩陣以及相容類。

計(jì)算決策屬性 D 對 U 劃分：

計(jì)算每個(gè)對象對應(yīng)的概率分布：

計(jì)算每個(gè)對象對應(yīng)的最大分布：

計(jì)算最大分布約簡可辨識矩陣：

計(jì)算最大分布約簡可辨識函數(shù)：

因此，最大分布保持約簡結(jié)果為{a3}。

例5 如表1所示的區(qū)間值決策系統(tǒng)，令 α分別為0.4,0.5,0.6,0.7，則分布保持約簡結(jié)果為

最大分布保持約簡結(jié)果為

性質(zhì)3 設(shè)區(qū)間值決策系統(tǒng) D S=(U,C∪D,V,f)，H=h1∨h2∨···∨hm和 K=k1∨k2∨···∨kn分別是分布約簡和最大分布約簡結(jié)果，則在閾值 α 下 ，對于 K 中任意一個(gè)蘊(yùn)含項(xiàng) kj， H 中 存在一個(gè)蘊(yùn)含項(xiàng) hi滿足

3 實(shí)驗(yàn)驗(yàn)證與分析

本節(jié)對提出的最大分布約簡算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)包括兩部分：1)比較最大分布約簡方法和其他約簡方法的約簡結(jié)果，驗(yàn)證了性質(zhì)3的正確性；2)比較了最大分布保持、分布保持和正域保持3種約簡算法的約簡效率。采用UCI標(biāo)準(zhǔn)測試集進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為PC機(jī)，操作系統(tǒng)為Windows 7旗艦版64 位；內(nèi)存為6.0 GB DDR3，CPU為Intel i5-3470。

實(shí)驗(yàn)選取8組標(biāo)準(zhǔn)UCI數(shù)據(jù)集，對缺失數(shù)據(jù)通過將對應(yīng)屬性下占多數(shù)屬性值進(jìn)行替換，對名詞性數(shù)據(jù)采用{0,1}替換，對連續(xù)型數(shù)據(jù)采用等頻分割[19]的方法，所有數(shù)據(jù)預(yù)處理均在WEKA3.6進(jìn)行，數(shù)據(jù)集信息如表2所示， |U |表示對象數(shù)，|AT|表示條件屬性數(shù)， |D |表示決策屬性將對象分類個(gè)數(shù)。

表2 UCI數(shù)據(jù)集信息Table 2 UCI data sets information

由于表格有限，表3～10中數(shù)據(jù)集名稱均為相應(yīng)數(shù)據(jù)集名稱的縮寫。

由于采用的UCI數(shù)據(jù)集都是單值數(shù)據(jù)，因此需將單值數(shù)據(jù)轉(zhuǎn)換為區(qū)間值數(shù)據(jù)，單值數(shù)據(jù)轉(zhuǎn)換為區(qū)間值數(shù)據(jù)的方法在文獻(xiàn)[19]中已經(jīng)描述，先將該方法改進(jìn)，引進(jìn)閾值 λ，該值可調(diào)節(jié)振幅，即區(qū)間值的長度。

表3 約簡結(jié)果對比(λ =2.4,α=0.4)Table 3 Comparison of reduction results (λ =2.4,α=0.4)

表4 約簡結(jié)果對比(λ =2.4,α=0.5)Table 4 Comparison of reduction results(λ =2.4,α=0.5)

表5 約簡結(jié)果對比(λ =2.4,α=0.6)Table 5 Comparison of reduction results (λ =2.4,α=0.6)

設(shè)區(qū)間值決策系統(tǒng)( U ,C∪D,V,f)， 對任意的 xi∈U，at(xi)為 xi在 屬性t上的取值 U /D={D1,D2,···,D|U/D|}，Dk∈U/D，則單值性數(shù)據(jù)轉(zhuǎn)換為區(qū)間值數(shù)據(jù)的振幅為

式中

表6 約簡結(jié)果對比(λ =2.4,α=0.7)Table 6 Comparison of reduction results (λ =2.4,α=0.7)

表7 約簡結(jié)果對比(λ =3.5,α=0.4)Table 7 Comparison of reduction results (λ =3.5,α=0.4)

表8 約簡結(jié)果對比(λ =3.5,α=0.5)Table 8 Comparison of reduction results (λ =3.5,α=0.5)

區(qū)間值的左右區(qū)間分別為

式中 λ為調(diào)節(jié)區(qū)間值長度的值。

3.1 約簡結(jié)果對比

在本節(jié)中，討論了最大分布約簡與其他約簡方法之間的關(guān)系[20]，選取正域保持約簡算法(PRADM)[17]和分布保持約簡算法(DRADM)。 λ 分 別取 2 .4和3.5， α 分 別取 0 .4、0.5、0.6、0.7，共進(jìn)行了8組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3～10所示，其中：集合1=集合7=集合17=集合19=集合22=集合28={{1}, {2}, {3},{4}, {5}, {6}}；集合 2=集合 14=集合 16=集合18=集合21=集合23={{1}, {2}, {3}, {4}, {5}}；集合3=集合20=集合24={{1}, {2}, {3}, {4}, {5}, {6},{7}}；集合 4=集合 6={1, 3, 4, 5, 6, 7, 8, 9}；集合5=集合8=集合9=集合10=集合26=集合27={1, 2,3, 4, 5, 6, 7, 8, 9}；集合11=集合12=集合13={{1, 3,5},{2, 3, 5},{3, 4, 5},{1, 2, 3, 4, 6},{1, 5, 6},{2, 5,6},{3, 5, 6}{4, 5, 6}}；集合15={{1}, {2}, {3}, {4},{5}, {6}, {7}, {8}, {9}}；集合 25={1, 2, 3, 4, 5, 7, 8, 9}。

λ=3.5,α=0.6表9 約簡結(jié)果對比( )λ=3.5,α=0.6Table 9 Comparison of reduction results ( )

表3～6為 λ 取 2 .4， α 分別取0.4、0.5、0.6、0.7時(shí)，正域保持、分布保持和最大分布保持約簡算法的約簡結(jié)果。實(shí)驗(yàn)結(jié)果表明，MDRADM約簡結(jié)果為DRADM約簡結(jié)果的子集，即驗(yàn)證了性質(zhì)3的正確性，而PRADM約簡結(jié)果和MDRADM約簡結(jié)果沒有明顯關(guān)系。這是因?yàn)?，?dāng)正域?yàn)榭諘r(shí)，正域約簡結(jié)果為條件屬性中任意一個(gè)屬性，故PRADM的約簡結(jié)果和MDRADM的約簡結(jié)果不存在包含關(guān)系。當(dāng) λ =3.5,α=0.4時(shí)，對于大部分?jǐn)?shù)據(jù)集，DRADM的約簡結(jié)果最短，F(xiàn)ertility數(shù)據(jù)集則在λ=2.4， α =0.7時(shí)最短，但Liverdisorders數(shù)據(jù)集在任何閾值下均沒有冗余屬性。

λ=3.5,α=0.7表10 約簡結(jié)果對比( )λ=3.5,α=0.7Table 10 Comparison of reduction results ( )

3.2 約簡效率對比

本節(jié)選取Mammographic Mass數(shù)據(jù)集，對比兩個(gè)算法隨對象數(shù)量的增加耗時(shí)變化情況。圖1～5為 λ 取 2 .4， α分別取0.4、0.5、0.6、0.7、0.8時(shí)，3個(gè)算法的時(shí)間耗費(fèi)情況；橫坐標(biāo)表示Mammographic Mass數(shù)據(jù)集的對象數(shù)量，縱坐標(biāo)表示運(yùn)行時(shí)間，單位為s。

圖1 約簡效率對比 (α =0.4)Fig. 1 Comparison of reduction efficiency (α =0.4)

圖2 約簡效率對比 (α =0.5)Fig. 2 Comparison of reduction efficiency (α =0.5)

圖3 約簡效率對比 (α =0.6)Fig. 3 Comparison of reduction efficiency (α =0.6)

圖4 約簡效率對比 (α =0.7)Fig. 4 Comparison of reduction efficiency (α =0.7)

圖5 約簡效率對比 (α =0.8)Fig. 5 Comparison of reduction efficiency (α =0.8)

圖1 ～5中虛線表示PRADM隨著對象數(shù)量增加運(yùn)行時(shí)間變化曲線，空心圓點(diǎn)實(shí)線表示MDRADM隨著對象數(shù)量增加運(yùn)行時(shí)間變化曲線，交叉點(diǎn)實(shí)線表示DRADM隨著對象數(shù)量增加運(yùn)行時(shí)間變化曲線。實(shí)驗(yàn)結(jié)果表明，在對象數(shù)較少情況下，由于差別矩陣較簡單，PRADM、DRADM和MDRADM運(yùn)行時(shí)間幾乎沒有差別，但隨著對象數(shù)量的增加，3種算法的運(yùn)行時(shí)間差異越來越明顯；由于MDRADM差別元素是DRADM差別元素的一個(gè)子集，PRADM的差別矩陣為非對稱矩陣，故MDRADM的運(yùn)行時(shí)間小于PRADM和DRADM運(yùn)行時(shí)間。當(dāng) α分別取 0.5、0.6、0.7、0.8時(shí)，Mammographic Mass數(shù)據(jù)集隨著對象的增加，3個(gè)算法的耗時(shí)差距增大，這是由于隨著對象的增加差別矩陣愈加復(fù)雜，計(jì)算量越大造成的；當(dāng) α =0.4時(shí)，也呈現(xiàn)這樣的趨勢，但當(dāng)對象數(shù)達(dá)到900時(shí)，利用吸收率和結(jié)合律運(yùn)算的差別矩陣較簡單，造成時(shí)間增長率減小。當(dāng) λ 取 3. 5，α分別取 0.4、0.5、0.6、0.7、0.8時(shí)，3個(gè)算法的時(shí)間耗費(fèi)情況跟 λ 取 2. 4時(shí)的折線圖大致相同，所以本文不作詳細(xì)描述。

4 結(jié)束語

屬性約簡是粗糙集理論研究的熱點(diǎn)問題之一，在實(shí)際應(yīng)用中具有重要意義，主要作用有：1)提取更加泛化的規(guī)則；2)針對應(yīng)用中的海量數(shù)據(jù)，能夠壓縮數(shù)據(jù)集規(guī)模。分布保持約簡能夠保持信息系統(tǒng)在約簡前后置信度不變，而人們往往只關(guān)注置信度最大的規(guī)則，具有廣泛的應(yīng)用價(jià)值。

本文在相關(guān)研究成果的基礎(chǔ)上，在不協(xié)調(diào)區(qū)間值決策系統(tǒng)中提出最大分布約簡的概念，構(gòu)造了基于可辨識矩陣的最大分布約簡算法，該算法保持了在知識約簡前后各個(gè)規(guī)則的最大置信度不變。實(shí)驗(yàn)選取8組UCI數(shù)據(jù)集將本文算法與已有的兩種約簡算法的約簡結(jié)果和效率進(jìn)行對比。實(shí)驗(yàn)結(jié)果表明，分布約簡包含最大分布約簡，并且最大分布約簡算法比其他兩種算法具有更高的效率。由于本文提出的算法是在可辨識矩陣基礎(chǔ)上的，其時(shí)間和空間復(fù)雜度較高，不利于在實(shí)際應(yīng)用中推廣，故提出高效率的約簡算法是未來研究方向之一。