不完備序決策系統(tǒng)的約簡(jiǎn)一致性研究

陳一舟，王加陽(yáng)，鄭 娜

(中南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410083)

1 引 言

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

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

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

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

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

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

2.1 不完備決策系統(tǒng)

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

定義1. 在不完備決策系統(tǒng)S=(U，A∪j5i0abt0b，f)中，對(duì)于任意B?A，定義相似關(guān)系如下：

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)}

其中對(duì)于任意x∈U：

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

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

由定義1可知，相似關(guān)系RB是自反，對(duì)稱但非傳遞的，但相似關(guān)系Rd是一個(gè)等價(jià)關(guān)系.進(jìn)而給出不完備決策系統(tǒng)中，基于相似關(guān)系RB的下近似和上近似：

基于等價(jià)關(guān)系Rd的下近似和上近似為：

2.2 序決策系統(tǒng)

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

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

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

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

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

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

定義3. 給定有序決策系統(tǒng)S≥=(U，A∪j5i0abt0b，f)，對(duì)于任意B?A，關(guān)于B和d的優(yōu)勢(shì)關(guān)系定義如下：

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

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

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

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

上述性質(zhì)證明過(guò)程簡(jiǎn)單，均可由序決策系統(tǒng)的相關(guān)定義推理而得，故此處不再贅述.

3 不完備序決策系統(tǒng)的信任結(jié)構(gòu)

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

定義9. 給定不完備序決策系統(tǒng)S≥=(U，A∪j5i0abt0b，f)，其信任結(jié)構(gòu)是(M，m)，定義U上的信任函數(shù)Bel：2U→[0，1]如下：

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

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

則其相應(yīng)的基本概率分配函數(shù)如下：

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

定理3. 表明，優(yōu)勢(shì)關(guān)系的上、下近似質(zhì)量函數(shù)均滿足半可加性，可作為證據(jù)理論中似然函數(shù)與信任函數(shù).同理可得劣勢(shì)關(guān)系的似然函數(shù)與信任函數(shù).由此便可以通過(guò)序上下近似算子來(lái)得出序決策系統(tǒng)的信任結(jié)構(gòu).

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

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

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

首先給出在不完備序決策系統(tǒng)中，近似分布約簡(jiǎn)的相關(guān)概念，然后給出在不完備序決策系統(tǒng)中，近似分布約簡(jiǎn)與信任約簡(jiǎn)和似然約簡(jiǎn)的等價(jià)性證明.

定義10. 設(shè)S≥={U，A∪j5i0abt0b，f}是一個(gè)不完備序決策系統(tǒng)，其中A是條件屬性集，d是決策屬性，B?A，令

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

下面給出不完備序決策系統(tǒng)的相對(duì)信任約簡(jiǎn)和相對(duì)似然約簡(jiǎn)的相關(guān)概念.

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

定理5. 設(shè)S≥={U，A∪j5i0abt0b，f}是一個(gè)不完備序決策系統(tǒng)，B?A，則(1)B是相對(duì)*≥信任協(xié)調(diào)集，當(dāng)且僅當(dāng)B是*≥一下近似分布協(xié)調(diào)集;(2)B是相對(duì)*≥信任約簡(jiǎn)，當(dāng)且僅當(dāng)B是*≥一下近似分布約簡(jiǎn).

證明：

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

證畢

推論2. 設(shè)S≥={U，A∪j5i0abt0b，f}是一個(gè)不完備序決策系統(tǒng)，B?A，則

1)B是相對(duì)*≤信任協(xié)調(diào)集，當(dāng)且僅當(dāng)B是*≤一下近似分布協(xié)調(diào)集;

2)B是相對(duì)*≤信任約簡(jiǎn)，當(dāng)且僅當(dāng)B是*≤一下近似分布約簡(jiǎn).

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

定理6. 設(shè)S≥={U，A∪j5i0abt0b，f}是一個(gè)不完備序決策系統(tǒng)，B?A，則

1)B是相對(duì)*≥信任協(xié)調(diào)集當(dāng)且僅當(dāng)B是相對(duì)*≤似然協(xié)調(diào)集；

2)B是相對(duì)*≥信任協(xié)調(diào)集當(dāng)且僅當(dāng)B是相對(duì)*≤似然協(xié)調(diào)集.

證明：

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

證畢

定理7. 設(shè)S≥={U，A∪j5i0abt0b，f}是一個(gè)不完備序決策系統(tǒng)，B?A，則

1)B是相對(duì)*≤信任協(xié)調(diào)集當(dāng)且僅當(dāng)B是相對(duì)*≥似然協(xié)調(diào)集；

2)B是相對(duì)*≤信任協(xié)調(diào)集當(dāng)且僅當(dāng)B是相對(duì)*≤似然協(xié)調(diào)集.

證畢

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

5 結(jié) 語(yǔ)

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