不完備序決策系統的約簡一致性研究

陳一舟，王加陽，鄭 娜

(中南大學 信息科學與工程學院，長沙 410083)

1 引 言

粒計算是當前智能信息處理中，通過模擬人的思維模式從而進行信息處理的一個新興研究方向.波蘭科學家Pawlak在20世紀80年代提出了粗糙集理論[1]，利用屬性的等價關系形成的等價類作為基本的知識粒度，使其成為是一種能夠處理不精確信息系統的數學工具.粗糙集中其他對象子集可以通過粗糙集的上、下近似算子來描述.經過三十多年的發(fā)展，粗糙集理論已經成為了粒計算的一個重要工具，在眾多人工智能領域，如專家系統、機器學習、模式識別和決策分析等研究中得到了廣泛的應用[2-4].經典粗糙集理論要求數據集中的每一個對象相對于每一個屬性都有唯一確定的離散值，因此，經典粗糙集理論僅可以處理完備信息系統.

但是在實際情況中，由于測量誤差、數據丟失等各種原因，我們所面臨的信息系統往往是不完備的，并且許多屬性帶有偏好信息，比如商品價格、學生成績等.因此，進一步豐富粗糙集理論，使其可以處理不完備序信息系統成為了粗糙集理論發(fā)展的一個重要方向.Greco[5-7]等人針對序信息系統中屬性值之間遞增或遞減的序關系，提出了基于優(yōu)勢關系的粗糙集模型，給處理不完備信息系統提供了一種新的決策思路.

證據理論是進行不確定性推理的重要工具，基于人們對客觀世界認識，根據人們已有知識對不確定性事件做出判斷.證據理論是在概率論的基礎上發(fā)展起來的，與傳統的概率論相比，它能更好的把握所研究對象的模糊性和不確定性.D-S證據理論引入證據函數，將認知的“不確定性”和“未知不明”等概念區(qū)分開來，由信任函數與似然函數構建信任區(qū)間，用信任區(qū)間代替單個概率值來度量知識的不確定性.它在決策分析、模式識別、自動檢測、社會計算、圖像融合、安全分析、粒計算等領域得到了廣泛的應用[8-15].

粗糙集理論和證據理論之間有著密不可分的聯系[16]，粗糙集的上、下近似質量函數與似然函數和信任函數分別對應，證據理論中的信任函數可以由粗糙集的近似空間來描述，同時，粗糙集中的屬性約簡問題也可以通過信任函數來解決.粗糙集的優(yōu)勢在于它不需要先驗知識，可以從已知的知識庫中獲取；而證據理論的優(yōu)勢在于可以進行不確定性推理，兩者結合可以為研究提供了更多的解決方向.

目前，關于不完備決策系統的研究大多集中在優(yōu)勢關系的改進以及約簡算法的設計上，關于其證據特征的研究較少.本文研究了在不完備序決策系統中，序上、下近似算子和證據理論中的信任函數和似然函數的關系，給出了如何根據序上、下近似算子來計算信任函數和似然函數的方法.另外，本文還提出了不完備序決策系統中在證據理論下，近似分布約簡、相對信然約簡以及相對分布約簡的定義和相關性質，并研究了其一致性.

2 不完備序決策系統

2.1 不完備決策系統

決策系統為一個三元組S=(U，A∪g0gggggg，f)，其中U是對象的非空有限屬性集合，稱為論域，A是非空有限屬性集，g0gggggg為決策屬性集合，當條件屬性集合和決策屬性集合的交集為空集且決策屬性值不存在缺失的情況時，該信息系統是一個決策系統.當決策系統中存在某些缺省或未知屬性值時，用符號“*”或者“null”表示這個缺省值或者未知值.即當A∩g0gggggg=?且d(x)≠*∩d(x)≠null時，三元組S=(U，A∪g0gggggg，f)表示一個不完備決策系統.

定義1. 在不完備決策系統S=(U，A∪g0gggggg，f)中，對于任意B?A，定義相似關系如下：

RB={(x，y)∈U×U|?a∈B，f(x，a)=

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

Rd={(x，y)|f(x，d)=f(y，d)}

其中對于任意x∈U：

RB(x)={y∈U|(x，y)∈RB}

Rd(x)={y∈U|(x，y)∈Rd}

由定義1可知，相似關系RB是自反，對稱但非傳遞的，但相似關系Rd是一個等價關系.進而給出不完備決策系統中，基于相似關系RB的下近似和上近似：

基于等價關系Rd的下近似和上近似為：

2.2 序決策系統

稱二元組(L，≤)是一個全序(標記)集，非空集合L稱為標記集，≤是L上的二元關系，需滿足如下條件：

1)自反性：對于任意的x∈L，x≤x；

2)傳遞性：對于任意的x，y，z∈L，x≤y，y≤z蘊含x≤z；

3) ≤線性序：對于任意的x，y∈L，或者x≤y，或者y≤x.

定義2. 給定一個決策系統S=(U，A∪g0gggggg，f)，如果條件屬性集A中的每一個屬性都是一個準則且決策屬性d的屬性值域是全序集，則稱該決策系統是一個序決策系統，記作S≥=(U，A∪g0gggggg，f).

假設屬性a∈A是一個標準，優(yōu)勢關系≥a：x≥ay表示x至少與y一樣優(yōu)，x≥ay?f(y，a)≤f(x，a)(根據升序)或者≥a：x≥ay?f(x，a)≤f(y，a)(根據降序)，其中x，y∈U.對于任意屬性子集B?A，定義x≥By??a∈A，x≥ay，它表示關于屬性集A中所有屬性，x至少與y一樣優(yōu).式f(x，d)≥f(y，dB)?x≥dy表示就決策屬性值而言，x至少與y一樣優(yōu).一般而言，標準的值域可能是不連續(xù)的，但是其優(yōu)先順序是已經確定的或者是已知的.

定義3. 給定有序決策系統S≥=(U，A∪g0gggggg，f)，對于任意B?A，關于B和d的優(yōu)勢關系定義如下：

2.3 不完備序決策系統

定義4. 給定一個序決策系統S≥=(U，A∪g0gggggg，f)，如果?x∈U，a∈A，使得f(x，a)=*，則稱之為不完備序決策系統，否則稱之為完備序決策系統.

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

定義6. 給定一個不完備序決策系統S≥=(U，A∪g0gggggg，f)，決策屬性d的值域為Vd，為了方便，可假設Vd={1，2，3，…，L}，記為Clt={x∈U|f(x，d)=t}，則Cl={Clt|t∈Vd}是由決策屬性d對論域U形成的一個劃分.對t，s∈Vd，若t≥s，則任何屬于Clt的對象都至少和任何屬于Cls中的對象一樣優(yōu).Clt的上并集和下并集分別表示為：

上述性質證明過程簡單，均可由序決策系統的相關定義推理而得，故此處不再贅述.

3 不完備序決策系統的信任結構

證據理論用集合的形式表示命題，假設集合U包含了已知所有的證據，證據之間相互獨立.證據理論通過信任函數和似然函數構建信任區(qū)間，可量化表達“不確定”和“不知道”的能力.

定義9. 給定不完備序決策系統S≥=(U，A∪g0gggggg，f)，其信任結構是(M，m)，定義U上的信任函數Bel：2U→[0，1]如下：

似然函數Pls：2U→[0，1]如下：

定理2. 給定有不完備序決策系統S≥=(U，A∪g0gggggg，f)，對于任意X?U，B?A，似然函數與信任函數分別對應于基于優(yōu)勢關系的上、下近似質量函數，具體如下：

則其相應的基本概率分配函數如下：

證明：首先證明信任函數Bel≥滿足半可加性，對于任意X1，X2，…，Xn?U，我們有：

定理3. 表明，優(yōu)勢關系的上、下近似質量函數均滿足半可加性，可作為證據理論中似然函數與信任函數.同理可得劣勢關系的似然函數與信任函數.由此便可以通過序上下近似算子來得出序決策系統的信任結構.

證明過程與定理2類似，在此不再贅述.

推論1. 定不完備序決策系統S≥=(U，A∪g0gggggg，f)，B?A，對任意C?B，可得

4 不完備序決策系統的屬性約簡

首先給出在不完備序決策系統中，近似分布約簡的相關概念，然后給出在不完備序決策系統中，近似分布約簡與信任約簡和似然約簡的等價性證明.

定義10. 設S≥={U，A∪g0gggggg，f}是一個不完備序決策系統，其中A是條件屬性集，d是決策屬性，B?A，令

從定義10可看出，*≥上(下)近似分布約簡是保持不完備序決策系統的每個決策類的向上合并的上(下)近似不變的屬性子集，*≤上(下)近似分布約簡是保持不完備序決策系統的每個決策類的向下合并的上(下)近似不變的屬性子集.

下面給出不完備序決策系統的相對信任約簡和相對似然約簡的相關概念.

定義11. 設S≥={U，A∪g0gggggg，f}是一個不完備序決策系統，其中A是條件屬性集，d是決策屬性，B?A，T={Cl1，Cl2，…，ClL}，

定理5. 設S≥={U，A∪g0gggggg，f}是一個不完備序決策系統，B?A，則(1)B是相對*≥信任協調集，當且僅當B是*≥一下近似分布協調集;(2)B是相對*≥信任約簡，當且僅當B是*≥一下近似分布約簡.

證明：

2)根據(1)可知其成立.

證畢

推論2. 設S≥={U，A∪g0gggggg，f}是一個不完備序決策系統，B?A，則

1)B是相對*≤信任協調集，當且僅當B是*≤一下近似分布協調集;

2)B是相對*≤信任約簡，當且僅當B是*≤一下近似分布約簡.

證明過程與定理4類似，不再贅述.

定理6. 設S≥={U，A∪g0gggggg，f}是一個不完備序決策系統，B?A，則

1)B是相對*≥信任協調集當且僅當B是相對*≤似然協調集；

2)B是相對*≥信任協調集當且僅當B是相對*≤似然協調集.

證明：

2)根據(1)可知其成立.

證畢

定理7. 設S≥={U，A∪g0gggggg，f}是一個不完備序決策系統，B?A，則

1)B是相對*≤信任協調集當且僅當B是相對*≥似然協調集；

2)B是相對*≤信任協調集當且僅當B是相對*≤似然協調集.

證畢

定理5、定理6和推論2證明了*≥(*≤)下近似分布約簡是和相對*≥(*≤)信任約簡是等價的，并且相對*≥(*≤)信任約簡與相對*≤(*≥)似然約簡也是等價的.

5 結 語

粗糙集模型是粒計算研究中的重要方法，它對于粒計算研究的推動與發(fā)展起著巨大的作用.從完備決策系統到不完備決策系統，從無偏好決策系統到有偏好決策系統，每種不同的決策系統所具有的特征都被不斷的挖掘和發(fā)展，粗糙集理論也得到了越來越廣泛的應用.本文介紹了不完備序決策系統的特征，研究了基于優(yōu)勢關系的不完備序決策系統與證據理論之間的關系，并給出了上、下近似與似然函數、信任函數之間的轉換映射.接下來，提出了相對信任約簡與相對似然約簡的概念，并研究了它們之間的一致性關系，從而完善了不完備序決策系統的理論.以后我們將進一步討論不完備序決策系統的知識表示、規(guī)則獲取以及屬性約簡算法等.