α優(yōu)勢關(guān)系下粗糙集模型的屬性約簡

韋碧鵬，呂躍進，李金海

(1.柳州職業(yè)技術(shù)學(xué)院 公共基礎(chǔ)部，廣西 柳州 545006； 2. 廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，廣西 南寧 530004； 3.昆明理工大學(xué) 理學(xué)院，云南 昆明 650500)

波蘭數(shù)學(xué)家Pawlak于1982年提出了粗糙集理論[1]，它是一種處理模糊、不精確性以及不確定性的數(shù)學(xué)工具。近年來，由于它具有諸多優(yōu)勢，已經(jīng)被成功地運用于數(shù)據(jù)挖掘、模式識別、數(shù)據(jù)處理、決策分析等領(lǐng)域[2-4]。然而，在現(xiàn)實生活中，由于噪聲、測量數(shù)據(jù)的不完整性等因素，不完備信息系統(tǒng)依然廣泛存在。而Pawlak提出的經(jīng)典粗糙集并不適用不完備信息系統(tǒng)。這就有必要對它進行擴充以適用于處理不完備數(shù)據(jù)。目前，針對不完備信息系統(tǒng)缺失值的不同理解，對經(jīng)典粗糙集的擴充研究有如下模型：Kryszkiewicz[5]提出了基于容差關(guān)系的粗糙集模型，把不完備信息系統(tǒng)中的缺失值看作是遺漏型的，即可以和任意的對象進行比較；Stefanowski等[6]提出了基于非對稱相似關(guān)系和量化容差關(guān)系的粗糙集模型，把不完備信息系統(tǒng)中的缺失值看作是缺席型的；為了克服擴展模型的不足，王國胤[7]又給出了基于限制容差關(guān)系的粗糙集模型。這方面的更多研究，可以查看文獻[8-10]。

在現(xiàn)實世界中，很多的信息系統(tǒng)其屬性值域可能具有偏序性。此時，經(jīng)典粗糙集方法顯得無能為力。為了能夠處理具有偏序關(guān)系的信息系統(tǒng)，Greco等[11]提出了基于優(yōu)勢關(guān)系的粗糙集模型，即運用優(yōu)勢關(guān)系代替等價關(guān)系。為了讓優(yōu)勢關(guān)系下的粗糙集模型能夠同時處理缺失值，Shao等[12]把不完備序信息系統(tǒng)中的缺失值看作是遺漏型的，提出了基于優(yōu)勢關(guān)系的不完備序信息系統(tǒng)，并討論了屬性約簡和規(guī)則提取。針對文獻[12]提出的優(yōu)勢關(guān)系過于寬松，容易將實際不滿足條件的對象誤判為同一個優(yōu)勢類，胡明禮等[13]通過引入一個閾值得到了廣義擴展優(yōu)勢關(guān)系的概念，并對規(guī)則提取進行了重新考慮。此外，針對優(yōu)勢系統(tǒng)中缺失值是缺席型的情況，楊習(xí)貝等[14]提出了相似優(yōu)勢關(guān)系的粗糙集模型，并對屬性約簡做了研究。然而這并沒有彌補文獻[12]提出的優(yōu)勢關(guān)系過于寬松的缺陷，并且改進后的模型還容易將一些本屬于同一決策類的對象誤判為不同決策類。這在一定程度上會影響文獻[12]提出的模型決策分析的效果。因此，Luo 等[15]進一步又給出了限制優(yōu)勢粗糙集模型，既可以避免文獻[12]提出的優(yōu)勢關(guān)系過于寬松的現(xiàn)象，又不容易將一些本屬于同一決策類的對象誤判為不同的決策類。但文獻[15]提出的限制優(yōu)勢關(guān)系在某些情況下又顯得過于嚴(yán)格，例如：當(dāng)2個對象在各屬性下的取值為x=(4,3,2,1),y=(*,*,2,1)時，且各屬性值域的最大值均為4，那么根據(jù)文獻[15]提出的限制優(yōu)勢關(guān)系，對象x是不優(yōu)于對象y的；可現(xiàn)實生活中，對象x優(yōu)于對象y的可能性是非常大的，這有可能導(dǎo)致數(shù)據(jù)集中的決策規(guī)則沒有充分提取。

基于此，本文在分析不完備序信息系統(tǒng)中現(xiàn)有的幾種擴展粗糙集模型的基礎(chǔ)上，提出了基于α優(yōu)勢關(guān)系的粗糙集模型，它既吸收了其他擴展模型的優(yōu)點，又能有效克服它們的局限性，更有利于處理現(xiàn)實中的數(shù)據(jù)集。此外，基于α優(yōu)勢關(guān)系的粗糙集模型，給出了不完備序信息系統(tǒng)和序決策系統(tǒng)的區(qū)分矩陣屬性約簡算法，并表明了其區(qū)分矩陣只能運用屬性集的冪集進行構(gòu)造，而不能簡單地運用單屬性集進行構(gòu)造。

1 基本概念

若存在一個屬性a∈AT使得Va為空值(記作：f(x,a)=*)，則稱該信息系統(tǒng)是不完備的信息系統(tǒng)，記作：IIS；否則稱為完備的信息系統(tǒng)。

定義1[11]設(shè)IS=(U,AT,V,f)是一個完備信息系統(tǒng)，對于?A?AT，?x,y∈U，有：

?a∈A}

定義2[12]設(shè)IIS=(U,AT,V,f)是一個不完備信息系統(tǒng)，對于A?AT，?x,y∈U，有

?a∈A,f(x,a)≥

f(y,a)∨f(x,a)=*∨f(y,a)=*}

?X}

通過分析定義2，可以得出文獻[12]在不完備序信息系統(tǒng)中提出的優(yōu)勢關(guān)系是以空值可以等于任意值為假設(shè)前提的，即認(rèn)為空值可以優(yōu)于任意值，同時又認(rèn)為任意值可以優(yōu)于空值，這顯然不符合實際情況。例如：當(dāng)x=(1,1,*)，y=(1,1,4)，z=(*,*,4)時，其中“4”表示屬性值下最大的取值，“1”為屬性值下最小的取值。根據(jù)定義2進行分析可得：

定義4[15]設(shè)IOIS=(U,AT,V,f)是一個不完備序信息系統(tǒng)，對于A?AT，?x,y∈U，對象在屬性集A下的限制優(yōu)勢關(guān)系為

?a∈A,f(x,a)≥

f(y,a)∨(f(x,a)=maxVa∧f(y,a)=

*)∨(f(x,a)=*∧f(y,a)=minVa)}∪IU

?X}

2 α優(yōu)勢關(guān)系的粗糙集模型

定義6 設(shè)IOIS=(U,AT,V,f)是一個不完備序信息系統(tǒng)，對于?a?AT，?x,y∈U，對象在屬性a下的取值為Va={a1,a2,...,am}，并且a1

從定義6中得知，在單屬性下，2個對象優(yōu)于的程度在0和1之間。當(dāng)對象x在屬性a下取值完全小于對象y的取值時，用數(shù)值0來表示對象x劣于對象y的程度，即概率；當(dāng)對象x在屬性a下取值完全大于對象y的取值時，用數(shù)值1來表示對象x優(yōu)于對象y的程度。然而，當(dāng)對象x和對象y有一個缺失值時，且對象在屬性下取值的多樣性，使得很難確定2個對象的優(yōu)于程度；根據(jù)概率的含義，即在m個數(shù)中，有n個數(shù)優(yōu)于一個確定數(shù)值的概率為n/m，得出定義6,2個對象中有一個為缺失值時它們的優(yōu)于程度。當(dāng)2個對象都為缺失值時，沒有根據(jù)可以判別它們之間優(yōu)于程度，因此，運用1/m概率來表示，意味著優(yōu)于程度很小。

定義7 設(shè)IOIS=(U,AT,V,f)是一個不完備序信息系統(tǒng)，對于A?AT，?x,y∈U，則對象x在屬性集A下優(yōu)于y的概率為

通過定義7，可以得出不完備序信息系統(tǒng)各個對象的優(yōu)勢類如下：

定義8 設(shè)IOIS=(U,AT,V,f)是一個不完備序信息系統(tǒng)，對于A?AT，?x,y∈U，有

性質(zhì)1 設(shè)IOIS=(U,AT,V,f)是一個不完備序信息系統(tǒng)，則α優(yōu)勢關(guān)系滿足如下性質(zhì)：

3)當(dāng)B?A?AT時，?x∈U，

性質(zhì)2 設(shè)IOIS=(U,AT,V,f)是一個不完備序信息系統(tǒng)，對于A?

三者優(yōu)勢關(guān)系滿足如下性質(zhì)：

?X}=

3 基于α優(yōu)勢關(guān)系粗糙集模型的屬性約簡

3.1 不完備序信息系統(tǒng)的屬性約簡

定義10表明了基于α優(yōu)勢關(guān)系的不完備序信息系統(tǒng)的屬性約簡保持的是對象的α優(yōu)勢類不變的最小屬性組成的集合。基于此，下面給出其優(yōu)勢區(qū)分矩陣構(gòu)造的方法：

定義11 設(shè)IOIS=(U,AT,V,f)是一個不完備序信息系統(tǒng)，對于?x,y∈U，有

根據(jù)對以往知識的了解，區(qū)分矩陣的構(gòu)造是可以僅僅在單元素下進行。但是，在α優(yōu)勢關(guān)系的粗糙集模型中，這樣的構(gòu)造是不成立的，如

假設(shè)基于α優(yōu)勢關(guān)系的優(yōu)勢區(qū)分矩陣可以如下構(gòu)造：

3.2 不完備序決策系統(tǒng)的屬性約簡

在α優(yōu)勢關(guān)系的不完備序信息系統(tǒng)中，若添加決策屬性d，則不完備序信息系統(tǒng)可以轉(zhuǎn)變?yōu)镮ODS=(U,AT∪j5i0abt0b,V,f)情形，其中屬性d也是一個準(zhǔn)則，稱之為決策屬性，d?AT且*?Vd，則稱IODS為不完備序決策系統(tǒng)。

從定義13中可以得出，基于α優(yōu)勢關(guān)系的不完備序決策系統(tǒng)的屬性約簡保持α優(yōu)勢關(guān)系的協(xié)調(diào)性不變的最小子集。下面給出其優(yōu)勢決策區(qū)分矩陣構(gòu)造的方法。

定義14 設(shè)IODS=(U,AT∪j5i0abt0b,V,f)是一個不完備序決策系統(tǒng)，對于?x,y∈U，有

4 實例分析

例1 下面給出一個不完備序決策系統(tǒng)，其中U={1,2,3,4,5}，AT={a,b,c}為條件屬性，d為決策屬性，且對象在單個條件屬性a、b、c下最大的取值分別為4、3、3，最小值都是1。運用表1給出的不完備序決策系統(tǒng)來分析文獻[12]提出的優(yōu)勢關(guān)系、文獻[15]提出的限制優(yōu)勢關(guān)系以及本文提出的α優(yōu)勢關(guān)系之間的性能；并計算α優(yōu)勢關(guān)系不完備序信息系統(tǒng)與決策系統(tǒng)的屬性約簡。

表1 不完備序決策系統(tǒng)

1)把表1中的決策屬性去掉，不完備序決策系統(tǒng)轉(zhuǎn)化為不完備序信息系統(tǒng)，分析三者優(yōu)勢關(guān)系之間的關(guān)系。

① 根據(jù)定義2，可得文獻[12]提出的優(yōu)勢關(guān)系下，各個對象的優(yōu)勢類為：

③ 令α=0.6，根據(jù)定義8，可得α優(yōu)勢關(guān)系下，各個對象的α優(yōu)勢類為：

根據(jù)定義得出三者優(yōu)勢關(guān)系下各個對象的優(yōu)勢類，在文獻[12]提出的優(yōu)勢關(guān)系下，對象4的優(yōu)勢類為對象2、4，然而在條件屬性c下，由于對象4取得最大值，因此，對象2優(yōu)于對象4的可能性是非常之??；另外，對象5的優(yōu)勢類為對象2、3、4、5，然而在條件屬性a下，對象4優(yōu)于對象5的可能性也是非常之小。因此，可以說文獻[12]提出的優(yōu)勢關(guān)系劃分的粒度過大了。在文獻[15]提出的限制優(yōu)勢關(guān)系下，對象3的優(yōu)勢類為對象3，然而對象2優(yōu)于對象3的可能性是非常之大。因此，說明了文獻[15]提出的限制優(yōu)勢關(guān)系劃分的粒度過細(xì)了。然而，在α優(yōu)勢關(guān)系下，設(shè)定確定的α取值，各個對象的優(yōu)勢類就不會出現(xiàn)上述的情況；可以看出，α優(yōu)勢關(guān)系吸取了上述兩者優(yōu)勢關(guān)系的優(yōu)點，丟棄了兩者的缺陷，更加符合實際情況，更有利于去處理現(xiàn)實生活中存在復(fù)雜的不完備序信息系統(tǒng)。

2)不完備序信息系統(tǒng)的屬性約簡

根據(jù)定義11，結(jié)合α優(yōu)勢類，可以得出不完備序信息系統(tǒng)的優(yōu)勢區(qū)分矩陣如表2。

表2 優(yōu)勢區(qū)分矩陣

故Δ*≥=(a∨b∨c)∧(a∨b)∧a∧c∧(a∨c)∧(a∧b)∧(b∨c)=abc，即該不完備序信息系統(tǒng)的屬性約簡為abc。

3)不完備序決策系統(tǒng)的屬性約簡。

由于各個對象在決策屬性下的優(yōu)勢類如下：

根據(jù)定義14，可以得出不完備序決策系統(tǒng)的優(yōu)勢決策區(qū)分矩陣如表3。

表3 優(yōu)勢決策區(qū)分矩陣

5 結(jié)束語

由于現(xiàn)實中處理的數(shù)據(jù)很多是不完備的，且存在偏序性，因此研究處理這種復(fù)雜數(shù)據(jù)情況的粗糙集方法是很有實際意義的。本文通過對現(xiàn)有優(yōu)勢關(guān)系的分析后提出了α優(yōu)勢關(guān)系及其相應(yīng)的粗糙集模型，以使得對不完備序信息系統(tǒng)的數(shù)據(jù)分析更加合理。此外，在基于α優(yōu)勢關(guān)系的粗糙集模型上，給出了不完備序信息系統(tǒng)的優(yōu)勢區(qū)分矩陣以及不完備序決策系統(tǒng)的優(yōu)勢決策區(qū)分矩陣，從而實現(xiàn)了屬性約簡，同時也表明了區(qū)分矩陣只能運用屬性集的冪集進行構(gòu)造，而不能運用單個屬性集進行構(gòu)造。

需要指出的是，在α優(yōu)勢關(guān)系的基礎(chǔ)上，還可以進一步研究不協(xié)調(diào)不完備序決策系統(tǒng)的屬性約簡算法，這是本文的下一步工作任務(wù)。

參考文獻:

[1]PAWLAK Z. Rough sets [J]. International Journal of Computer and Information Sciences, 1982, 11(5): 341-356.

[2]張文修,吳偉志,梁吉業(yè),等.粗糙集理論與方法[M].北京：科學(xué)出版社, 2001： 14-19.

[3]李金海,呂躍進.決策系統(tǒng)的快速屬性約簡算法[J].電子科技大學(xué)學(xué)報, 2007, 36(6): 1237-1240.

LI Jinhai, Lü Yuejin. Quick attribute reduction algorithm on decision system[J]. Journal of University of Electronic Science and Technology of China, 2007, 36(6): 1237-1240.

[4]覃麗珍,姚炳學(xué),李金海.基于信息量的完備覆蓋約簡算法[J]. 計算機科學(xué), 2012, 39(10): 235-239.

QIN Lizhen, YAO Bingxue, LI Jinhai. Complete algorithm for covering reduction based on information quantity[J]. Computer science, 2012, 39(10): 235-239.

[5]KRYSZKIEWICZ M. Rough set approach to incomplete information systems [J]. Information Sciences, 1998, 112: 39-49.

[6]STEFANOWSKI J, TSOUKIAS A. On the extension of rough sets under incomplete information[C]//Proceedings of New Directions in Rough Sets, Data Mining and Granular-Soft Computing. Berlin: Springer, 1999: 73-81.

[7]王國胤. Rough集理論在不完備信息系統(tǒng)中的擴充[J]. 計算機研究與發(fā)展, 2002, 39 (10): 1238-1243.

WANG Guoyin. Extension of rough set under incomplete information systems[J]. Journal of Computer Research and Development, 2002, 39 (10): 1238-1243.

[8]LIANG J Y, QU K S. Information measures of roughness of knowledge and rough sets in incomplete information systems[J]. Journal of System Science and System Engineering, 2001, 24(5): 544-547.

[9]GRZYMALA-BUSSE J W. Characteristic relations for incomplete data: a generalization of indiscernibility relation[C]//Proceedings of Rough Sets and Current Trends in Computing. Berlin: Springer, 2004: 244-253.

[10]楊習(xí)貝, 楊靜宇, 吳陳, 等. 不完備信息系統(tǒng)中的集對分析方法[J]. 計算機科學(xué), 2007, 34(4): 171-174.

YANG Xibei, YANG Jingyu, WU Chen, et al. Set pair analysis in incomplete information systems[J]. Information Science, 2007, 34(4): 171-174.

[11]GRECO S, MATARAZZO B, SLOWINGSKI R. Rough sets theory for multicriteria decision analysis[J]. European Journal of Operational Research, 2001, 129(1): 1-47.

[12]SHAO M W, ZHANG W X. Dominance relation and rules in an incomplete ordered information system [J]. International Journal of Intelligent Systems, 2005, 20: 13-27.

[13]胡明禮, 劉思峰. 基于廣義擴展優(yōu)勢關(guān)系的粗糙決策分析方法[J]. 控制與決策, 2007, 22(12): 1347-1351.

HU Mingli, LIU Sifeng. Rough analysis method of multi-attribute decision making based on generalized extended dominance relation[J]. Control and Decision, 2007, 22(12): 1347-1351.

[14]YANG X B, YANG J Y, WU C, et al. Dominance-based rough set approach and knowledge reductions in incomplete ordered information system[J]. Information Sciences, 2008, 178: 1219-1234.

[15]LUO G Z, YANG X B. Limited dominance-based rough set model and knowledge reductions in incomplete decision system[J]. Journal of Information Science and Engineering, 2010, 26: 2199-2211.