基于優(yōu)化容許關系的集值粗糙集模型及屬性約簡

摘要：粗糙集理論是一種用于處理不確定性和模糊知識的數(shù)學工具，其基本思想是在保持系統(tǒng)分類能力不變的前提下，通過知識約簡，導出問題的分類規(guī)則。集值信息系統(tǒng)使得粗糙集理論得到更廣泛的應用。提出了具有協(xié)調(diào)性的優(yōu)化容許關系，并討論了基于該關系的粗糙集模型，證明了相關性質(zhì)。討論了不確定性度量問題，提出了優(yōu)化容許關系下集值信息系統(tǒng)基于粗糙熵的屬性約簡，并給出了屬性約簡算法。

關鍵詞：粗糙集；集值信息系統(tǒng)；優(yōu)化容許關系；粗糙熵；屬性約簡

一、前言

波蘭數(shù)學家Z Pawlak在1982年提出了一種新的數(shù)據(jù)分析理論——粗糙集理論（Rough Set），由此打開了一扇粗糙集研究的大門。此后，很多數(shù)學家、邏輯學家和計算機專家對此進行了深入的研究。作為一種新的處理模糊性（Vagueness）和不確定性（Uncertainty）問題的數(shù)學工具，粗糙集理論的基本思想是在維持系統(tǒng)分類能力不變的基礎上，借助于知識約簡，給出問題的分類規(guī)則。模糊集理論、證據(jù)理論和概率統(tǒng)計等也是處理不確定性問題的較為常用的數(shù)學工具。兩相比對，粗糙集理論與它們聯(lián)系較為緊密，但也同時具有它獨有的優(yōu)越性：在處理不確定性問題時，模糊集理論離不開隸屬函數(shù)，證據(jù)理論離不開基本概率賦值，統(tǒng)計學離不開概率分布，而粗糙集理論則不需要任何關于數(shù)據(jù)和相應問題間的先驗知識或附加信息，而僅僅通過數(shù)據(jù)自身的不可區(qū)分關系，在保持信息系統(tǒng)分類能力不變的前提下，對屬性和屬性值進行約簡，從而得到保持知識能力不變的決策規(guī)則。

經(jīng)典粗糙集以完備信息系統(tǒng)為研究對象，以等價關系（滿足自反性，對稱性，傳遞性）為基礎。而在現(xiàn)實生活中，由于數(shù)據(jù)測量的誤差、對數(shù)據(jù)理解或獲取的限制等原因，使得在數(shù)據(jù)獲取時往往面臨的是不完備信息系統(tǒng)，這就限制了Z Pawlak（經(jīng)典）粗糙集理論的應用范圍。定義適合不完備信息系統(tǒng)的粗糙集模型是粗糙集理論能廣泛應用的基本問題之一，集值粗糙集模型是對未知屬性值賦予了它所有可能的取值，即給它賦予了該屬性值域的一個子集，進而將不完備信息系統(tǒng)向集值信息系統(tǒng)進行轉(zhuǎn)化。這樣，集值信息系統(tǒng)就提供了一種卓有成效的方法用來處理不完備信息系統(tǒng)。本文基于改進容許關系的集值粗糙集模型，繼續(xù)研究，提出新的具有協(xié)調(diào)性的優(yōu)化容許關系，建立新的模型。優(yōu)化容許關系除了具備改進容許關系RB（α，β）[1]所具備的性質(zhì)和優(yōu)點外，還有其自身的優(yōu)點，它的分類精度不低于改進容許關系的分類精度，并且它是一個協(xié)調(diào)的二元關系，因此它在集值信息系統(tǒng)中能夠得到更為廣泛應用。

二、基本概念

定義1[2]稱（U，A，F(xiàn)）是集值信息系統(tǒng)，若U={x1，…，xn}是對象集，每一個xi（i≤n）叫做一個對象；A={a1，…，am}是屬性集，每一個al （l≤m）叫做一個屬性；F={fl：l≤m}是對象屬性值映射，其中fl：U→P0 （Vl）（l≤m）， Vl是屬性al的值域，P0（Vl）表示Vl的非空子集全體。

在粗糙集理論中，一種關系是否為協(xié)調(diào)關系，對分類結(jié)果也會產(chǎn)生重要影響。協(xié)調(diào)二元關系的定義如下：

定義2信息系統(tǒng)S=（U，A，V，f），R是其上的二元關系，?x∈U，若滿足?P，Q?A，P?Q，都有RQ（x）?RP（x），或者滿足?P，Q?A，P?Q，都有RQ（x）?RP（x），則稱二元關系R是協(xié)調(diào)的，否則，稱之為不協(xié)調(diào)的。

雖然改進容許關系RB（α，β）有很多的優(yōu)越性，但是它是一個非協(xié)調(diào)的二元關系，我們舉例說明：在表1中，取B={a1，a2，a3，a4}，B?A，取α=1/3，β=3/5，

得每一對象的相容類分別為：

[x1]RA（α，β）={x1，x2，x4}，[x2]RA（α，β）={x1，x2，x4}，

[x3]RA（α，β）={x3，x6，x9，x10}，[x4]RA（α，β）={x1，x2，x4}，

[x5]RA（α，β）={x5，x6，x10}，[x6]RA（α，β）={x3，x5，x6，x9，x10}，

[x7]RA（α，β）={x7}，[x8]RA（α，β）={x8}，[x9]RA（α，β）={x3，x6，x9}，

[x10]RA（α，β）={x3，x5，x6，x10}。

[x1]RB（α，β）={x1，x2，x4}，[x2]RB（α，β）={x1，x2，x4}，

[x3]RB（α，β）={x3，x6，x9，x10}，[x4]RB（α，β）={x1，x2，x4}，

[x5]RB（α，β）={x3，x5，x6，x9，x10}，[x6]RB（α，β）={x3，x5，x6，x9，x10}，

[x7]RB（α，β）={x7}，[x8]RB（α，β）={x8}，[x9]RB（α，β）={x5，x6，x9}，

[x10]RB（α，β）={x3，x5，x6，x10}。

顯然，[x3]RA（α，β）?[x3]RB（α，β），并且[x3]RB（α，β）?[x3]RA（α，β），所以RA（α，β）是集值信息系統(tǒng)（U，A，F(xiàn)）上的不協(xié)調(diào)的二元關系。

?C?B?A，由于RB（α，β）的非協(xié)調(diào)性，使得我們不能夠斷定RA（α，β）與RB（α，β）的關系，也不能斷定RB（α，β）與RC（α，β）的關系，即RA（α，β）?RB（α，β）與RB（α，β）?RA（α，β）可能都不成立，RC（α，β）?RB（α，β）與RB（α，β）?RC（α，β）也可能都不成立。以上結(jié)果會造成我們在求基于改進容許關系下的集值信息系統(tǒng)屬性約簡時的計算難度，從而限制了改進容許關系在集值信息系統(tǒng)中的廣泛應用。

為了彌補改進容許關系的以上不足，下面我們在改進容許關系的基礎上進行適當修改，把其擴充為新的二元關系，以便新模型能在保持原有模型良好性能基礎上會有更廣泛的應用。

三、集值信息系統(tǒng)中基于優(yōu)化容許關系的粗糙集模型

在集值信息系統(tǒng)（U，A，F(xiàn)）中，B?A，xi，xj∈U。記

，SB（xi，xj）={al∈B|fl（xi）=fl（xj），|fl （xi）|=1}。

我們將改進容許關系RB（α，β）進行修正，得到具有協(xié)調(diào)性的優(yōu)化容許關系。

定義3優(yōu)化容許關系RB（α，β）：

。

并記[xi]R'B（α，β）={xj∈U|（xi，xj ）∈R'B（α，β）}為xi的相容類。顯而易見，優(yōu)化容許關系R'B（α，β）具備等價關系中的對稱性和自反性，卻未必具備傳遞性。

優(yōu)化容許關系R'B（α，β），通過合理設置參數(shù)α，β的值，同樣能填充R*B[3]限制性太強、RB∩ [4]和RBα [5]限制性太寬的不足，這里不再舉例說明。

定義4設（U，A，F(xiàn)）是一個集值信息系統(tǒng)，X?U，B?A。則對X的R'B（α，β）有以下概念：

—R'B（α，β）（X）={xi∈U│[xi ]R'B（α，β）∩X≠?}=∪{[xi ]R'B（α，β） |xi∈X}為上近似集，—R'B（α，β）（X）={xi∈U│[xi ]R'B（α，β）?X}={xi∈X│[xi ]R'B（α，β）?X}為下近似集，

posR'B（α，β） （X）=—R'B（α，β） （X）為正域，

negR'B（α，β）（X）=U-—R'B（α，β） （X）為負域，

bnR'B（α，β）（X）=—R'B（α，β）-（X）-—R'B（α，β） （X）為邊界。

由關系R'B（α，β）定義 X的近似精度ρR'B（α，β）為：

四、基于優(yōu)化容許關系的粗糙集模型的相關性質(zhì)

優(yōu)化容許關系R'B（α，β）的相關性質(zhì)除了具備改進容許關系RB（α，β）所具備的性質(zhì)外（這里不再一一列舉），還具有下面的性質(zhì)：

性質(zhì)1 設（U，A，F(xiàn)）是一個集值信息系統(tǒng)，則?B'?B?A，有

R'B'（α，β）?R'B（α，β）?R'A（α，β）。

證明：?（xi，xj ）∈R'B'（α，β），有clij ≥α，且；

因為B'?B，所以|SB' （xi，xj）|≤|SB （xi，xj）|，

從而，

于是（xi，xj）∈R'B（α，β），R'B'（α，β）?R'B（α，β）。

同理可證R'B（α，β）?R'A（α，β）。從而R'B'（α，β）?R'B（α，β）?R'A（α，β），結(jié)論成立。

優(yōu)化容許關系R'B（α，β）的近似分類精度不小于改進容許關系RB（α，β）的近似分類精度，即：

定理1集值信息系統(tǒng)（U，A，F(xiàn)），?X?U，?B?A，RB（α，β）、R'B（α，β）分別是其上的改進容許關系和優(yōu)化容許關系，則ρR'B（α，β） （X）≥ρRB（α，β），其中

證明：?（xi，xj）∈R'B（α，β），即clij ≥α，且，因為B?A，所以? ?，因此（xi，xj）∈RB（α，β）。即，?xi∈U，R'B（α，β）（xi）?RB（α，β）（xi），

從而，—R'B（α，β） （X）?—RB（α，β） （X），—R'B（α，β） （X）?—RB（α，β） （X），故ρR'B（α，β） （X）≥ρRB（α，β）（X）。

即結(jié)論成立。

五、優(yōu)化容許關系下的集值信息系統(tǒng)中的不確定性度量

隨著粗糙集理論研究的深化，一種新的不確定性——粗糙性，即信息系統(tǒng)中存在的知識和概念的不確定性，逐漸被人們認識和接受。信息系統(tǒng)的不確定性主要由兩個原因引起：一個原因來自論域上的二元關系及其產(chǎn)生的模塊，模塊的平均大小度量信息系統(tǒng)的不確定性，定義為知識的粗糙性；這種不確定性的另一個原因來自給定近似空間的粗糙集的邊界，邊界越大知識就越粗糙，處理這種不確定性可以使用粗糙度（或近似精度）來完成，稱之為概念的粗糙性。

知識的粗糙性和概念的粗糙性是粗糙集理論中不確定性問題研究的兩個主要方面。在粗糙集理論中，知識被認為是信息系統(tǒng)中的一個屬性子集?；谥R是區(qū)分對象能力的思想，知識實質(zhì)上是由屬性子集決定的對象空間的劃分或覆蓋，因此知識的粗糙性可以被認為是近似空間中基本知識粒的粗糙性。在粗糙集理論中，一個概念通過對象集來描述，如果概念不能被屬性所決定的基本知識粒精確描述，則稱這個概念為粗糙的。對于一個概念，在一個近似空間中可能是粗糙的，但是在另一個近似空間卻可能是精確的。所以概念的粗糙性源于一個近似空間提供的基本信息粒度。所以概念的粗糙性最終受知識粗糙性的影響?？傊?，系統(tǒng)所有屬性所決定的基本知識粒的粗糙性決定了一個信息系統(tǒng)的粗糙性。

知識的信息熵和知識的信息粒度是知識的不確定性度量的兩個比較經(jīng)典的方法，目前已有各種各樣的知識信息熵和知識信息粒度的定義形式，它們在度量知識的不確定性方面也都有各自很好的表現(xiàn)。下面我們基于知識的粗糙熵來討論知識的不確定性度量。

先將完備信息系統(tǒng)中知識距離的定義推廣到優(yōu)化容許關系下的集值信息系統(tǒng)中。

（一）優(yōu)化容許關系下的集值信息系統(tǒng)中的知識距離

在上面討論的基礎上，我們給出優(yōu)化容許關系下的集值信息系統(tǒng)中的知識距離的定義：

定義5集值信息系統(tǒng)（U，A，F(xiàn)），R'A（α，β）是其上的優(yōu)化容許關系，?P，Q?A，知識P，Q之間的距離定義為：

定理2對于集值信息系統(tǒng)（U，A，F(xiàn)），R'A（α，β）是其上的優(yōu)化容許關系，K（U）是其中的所有知識組成的集合，則?P，Q?A，（K（U），d）也構(gòu)成距離空間，并且對于K（U）中的任意兩個知識P，Q，d（P，Q）有界，即：

（1）0≤d（P，Q）≤1；

當且僅當P≈Q時，d（P，Q）=0，當且僅當U/R'P（α，β）=ω，U/R'Q（α，β）=δ或者U/R'P（α，β）=δ，U/R'Q（α，β）=ω時，d（P，Q）=1（其中，ω是論域上的恒等關系，δ為論域上的全域關系）；

（2）d（P，Q）=d（Q，P）；

（3）d（P，R）≤d（P，Q）+d（Q，R）。

性質(zhì)2集值信息系統(tǒng)（U，A，F(xiàn)）中，若?B?A，P，Q?A且P≠Q(mào)，則在優(yōu)化容許關系R_B^（'（α，β））下，P，Q之間的最大距離為1，最小距離為—? |U|（1|U|-1）? ?。

證明：設U/R'P（α，β）={[u1]R'P（α，β），[u2]R'P（α，β），…，[u|U|]R'P（α，β）}，

U/R'Q（α，β） ={[u1]R'Q（α，β），[u2]R'Q（α，β），…，[u|U|]R'Q（α，β）。

當U/R'P（α，β） =ω，U/R'Q（α，β）=δ或者U/R'P（α，β）=δ，U/R'Q（α，β）=ω時，d（P，Q）取到最大值1，其中，ω是論域上的恒等關系，δ為論域上的全域關系，即? U/R'P（α，β）={{u1}，{u2}…，{u|U|}}，

U/R'Q（α，β）={{u1，u2，…，u|U|}，{u1，u2，…，u|U|}…，{u1，u2，…，u|U| }}；d（P，Q）取到最小值—? |U|（1|U|-1）? ，當且僅當存在唯一一個i0∈{1，2，…，|U|}，有

|[ui0]R'P（α，β）⊕[ui0]R'Q（α，β）=1，且?i≠i0，i∈{1，2，…，|U|}，[ui]R'P（α，β）=[ui]R'Q（α，β）。證畢。

（二）優(yōu)化容許關系下的集值信息系統(tǒng)中的知識粗糙性

下面我們用知識距離定義知識的粗糙熵，并用知識的粗糙熵來度量知識的粗糙性。

定義6集值信息系統(tǒng)（U，A，F(xiàn)）中，R'A（α，β）是其上的優(yōu)化容許關系，?P?A，知識P的粗糙熵定義為：

E（P）=d（P，ω）=—? |U|（1|U|-1）? ∑i=1i=|U||[ui]R'P（α，β）⊕{ui}|。

其中，U/R'P（α，β）={[u1]R'P（α，β），[u2]R'P（α，β），…，[u|U|]R'P（α，β）}，

U/R'ω（α，β），{u2}…，{u|U|}。規(guī)定，E（?）=0。

知識粗糙熵的性質(zhì)：

（1）有界性：0≤E（P）≤1。

（2）單調(diào)性：若P?Q，則E（P）≤E（Q）。

但是，E（P）=E（Q）推不出P=Q，也就是說不同的知識可能有相同的粗糙熵。

定理3（知識的粗糙不變性[6]）信息系統(tǒng)中任意兩個知識P，Q?A，

U/R'P（α，β）={[u1]R'P（α，β），[u2]R'P（α，β），…，[u|U|]R'P（α，β）}，

UR'Q（α，β）={[u1]R'Q（α，β），[u2]R'Q（α，β），…，[u|U|]R'Q（α，β）}。

若存在一個一一映射f：U→U，，使|[ui]R'P（α，β）|=|[ui]R'Q（α，β）|，?i=1，2，…，|U|成立，則E（P）=E（Q）。

以上我們已經(jīng)詳細討論了優(yōu)化容許關系下的集值信息系統(tǒng)中知識的粗糙性問題，給出了集值信息系統(tǒng)在優(yōu)化容許關系下的知識距離的定義，討論了其相關性質(zhì)，并用知識間的距離定義了知識的粗糙熵；用知識粗糙熵來度量信息系統(tǒng)中知識的不確定性。

六、集值信息系統(tǒng)在優(yōu)化容許關系下基于知識粗糙熵的屬性約簡

作為粗糙集理論的其中一個焦點問題，約簡包括屬性約簡與屬性值約簡等。通常情況下，信息系統(tǒng)中的各種屬性的重要性一般不一樣，某些條件屬性甚至是冗余的。冗余屬性會造成兩方面的不利影響：首先，由于它需要處理時間和存儲空間，從而對資源造成了一定的浪費；其次，它會對研究人員做出正確、簡潔的決策造成一定的困擾。這樣說來，屬性約簡在粗糙集理論中重要性就不言而喻了。

所謂屬性約簡，是指在維持知識庫分類能力不變的基礎上，去掉里面不相關或者不重要的屬性[2]。一般而言，屬性約簡是由信息系統(tǒng)的屬性約簡和決策表的決策規(guī)則的約簡組成的?？梢跃S持原系統(tǒng)特定信息的屬性叫做系統(tǒng)的約簡。找出決策規(guī)則中對決策結(jié)論有影響的條件屬性叫做決策規(guī)則的約簡，或者叫做對象的約簡或值約簡。

前面討論了基于知識信息熵和知識信息粒度的知識粗糙性的度量，接下來我們利用知識粗糙熵來討論信息系統(tǒng)的屬性約簡。

定義7集值信息系統(tǒng)S=（U，A，F(xiàn)），?B?A，R'B（α，β）是其上的優(yōu)化容許關系，屬性a∈A在A中的重要性sigA （a）表達式是：sigA （a）=E（A）-E（A＼{a}），它反映了從A中除去a的前后知識粗糙熵變化情況。

特別當A={a}時，sig{a}（a）=E（{a}）-E（?）=E（{a}） 。

屬性重要性的性質(zhì)：

性質(zhì)1 sigA （a）≥0。

性質(zhì)2 屬性a∈A在A中是不可或缺的，當且僅當sigA （a）>0。

性質(zhì)3 CORE（A）={a∈A|sigA （a）>0}，稱為A的核屬性，它由A中所有的必要的屬性組成。

下面來定義集值信息系統(tǒng)在優(yōu)化容許關系下基于知識粗糙熵的屬性約簡中，屬性集外的屬性對屬性集的重要性，以方便在求出信息系統(tǒng)的核屬性后，能夠盡快的求出信息系統(tǒng)的屬性約簡。

定義8優(yōu)化容許關系下的集值信息系統(tǒng)S=（U，A，F(xiàn)），B?A，a∈A-B，a對B的重要性定義為：B中添加a后引起的知識粗糙熵變化的大小，即：

sigB （a）=E（B∪{a}）-E（B）。

a對B是必要的，當且僅當sigA （a）>0。

下面給出集值信息系統(tǒng)在優(yōu)化容許關系下基于知識粗糙熵的屬性約簡的定義：

定義9集值信息系統(tǒng)S=（U，A，F(xiàn)），B?A，R'B（α，β）是其上的優(yōu)化容許關系，稱B是S的一個約簡，如果E（B）=E（A），并且?b∈B，E（B＼＼）≠E（A）。

由以上討論我們給出基于知識粗糙熵的屬性約簡算法：

輸入：一個優(yōu)化容許關系下的集值信息系統(tǒng)S=（U，A，F(xiàn)）。

輸出：系統(tǒng)的約簡。

第1步：計算系統(tǒng)的知識粗糙熵E（A）；

第2步：計算CORE（A）={a∈A|sigA（a）>0}，C?CORE（A）；

第3步：計算E（C），如果E（C）=E（A），那么算法結(jié)束，否則（E（C）

第4步：（1）對每個屬性a∈A-C，計算sigC（a）；

（2）選擇屬性重要性最大的屬性，即選擇屬性a滿足：

a'∈A-Cmax{sigC（a'）并C?C∪{a}；

（3）計算E（C）；

（4）如果E（C）=E（A），那么算法結(jié)束，否則，轉(zhuǎn)（1）。

以上給出了集值信息系統(tǒng)在優(yōu)化容許關系下，基于知識粗糙熵的屬性約簡，并給出了約簡算法，可以看出屬性約簡在粗糙集理論中的重要地位。

七、結(jié)語

基于優(yōu)化容許關系，本文提出了一種新的集值粗糙集模型。這個模型填充了RBα未考慮取值明確且相等屬性對相容度影響、RB*限制性過高、RB∩寬松度過大的不足。由于改進容許關系RB（α，β）的非協(xié)調(diào)性，往往會造成我們在求基于改進容許關系下的集值信息系統(tǒng)屬性約簡時的計算難度，從而限制了改進容許關系在集值信息系統(tǒng)中的廣泛應用。闡述了不確定性度量問題的主要方法，提出了優(yōu)化容許關系下集值信息系統(tǒng)的基于知識粗糙熵的屬性約簡，并給出了約簡算法。

粗糙集理論從誕生到現(xiàn)在，已經(jīng)被廣泛應用到許多領域。譬如在人工神經(jīng)網(wǎng)絡、決策分析、智能控制、圖像處理、模式識別、知識發(fā)現(xiàn)、故障診斷和數(shù)據(jù)挖掘等很多領域都有著廣泛應用。近年來，不少研究者在粗糙集理論的應用上繼續(xù)探究，譬如文獻[ 7]將粗糙集理論應用在小區(qū)夜間用水量分析的漏損識別研究實際問題上。

下一步工作是在本文提出的優(yōu)化容許關系的基礎上，進一步研究不完備系統(tǒng)中屬性約簡和規(guī)則抽取算法，為實際應用系統(tǒng)開發(fā)奠定理論基礎。

參考文獻

[1]陶志，李桂秋.基于集值信息系統(tǒng)的改進粗集模型[J].中國民航大學學報，2010，28（6）：45-48.

[2]張文修，梁怡，吳偉志.信息系統(tǒng)與知識發(fā)現(xiàn)[M].北京：科學出版社，2003.

[3]宋笑雪，李鴻儒，張文修.集值信息系統(tǒng)的知識約簡與屬性特征[J].計算機工程，2006，32（22）：26-27+36.

[4]宋笑雪，解爭龍，張文修.集值決策信息系統(tǒng)的知識約簡與規(guī)則提取[J].計算機科學，2007，34（4）：182-184+191.

[5]陳子春，秦克云.集值信息系統(tǒng)基于變精度相容關系的知識約簡[J].計算機工程與應用，2008，44（9）：27-29，32.

[6]王寶麗，梁吉業(yè).信息系統(tǒng)中的知識距離與知識粗糙熵[J].計算機科學，2007，34（3）：151-154.

[7]儲文強，陳功，胡鴻昊.結(jié)合粗糙集屬性約簡和夜間用水量分析的漏損識別研究[J].科技通報，2021，37（9）：94-98+108.

基金項目：1.廣東省普通高校特色創(chuàng)新類項目（項目編號：2018KTSCX160）；2.廣州市科技計劃項目（項目編號：201804010088）

作者單位：廣東第二師范學院數(shù)學學院

責任編輯：尚丹