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

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

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

1 基本概念

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

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

?a∈A}

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

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

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

?X}

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

定義4[15]設(shè)IOIS=(U,AT,V,f)是一個(gè)不完備序信息系統(tǒng)，對(duì)于A?AT，?x,y∈U，對(duì)象在屬性集A下的限制優(yōu)勢(shì)關(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)勢(shì)關(guān)系的粗糙集模型

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

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

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

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

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

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

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

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

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

?X}=

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

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

定義10表明了基于α優(yōu)勢(shì)關(guān)系的不完備序信息系統(tǒng)的屬性約簡(jiǎn)保持的是對(duì)象的α優(yōu)勢(shì)類(lèi)不變的最小屬性組成的集合?；诖耍旅娼o出其優(yōu)勢(shì)區(qū)分矩陣構(gòu)造的方法：

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

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

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

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

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

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

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

4 實(shí)例分析

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

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

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

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

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

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

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

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

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

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

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

由于各個(gè)對(duì)象在決策屬性下的優(yōu)勢(shì)類(lèi)如下：

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

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

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

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

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

參考文獻(xiàn):

[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]李金海,呂躍進(jìn).決策系統(tǒng)的快速屬性約簡(jiǎn)算法[J].電子科技大學(xué)學(xué)報(bào), 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é),李金海.基于信息量的完備覆蓋約簡(jiǎn)算法[J]. 計(jì)算機(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]王國(guó)胤. Rough集理論在不完備信息系統(tǒng)中的擴(kuò)充[J]. 計(jì)算機(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)中的集對(duì)分析方法[J]. 計(jì)算機(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]胡明禮, 劉思峰. 基于廣義擴(kuò)展優(yōu)勢(shì)關(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.