決策蘊涵與可變決策蘊涵上的推理規則研究

薛東前，翟巖慧,2+，張少霞，李德玉,2，徐偉華

1.山西大學 計算機與信息技術學院，太原030006

2.山西大學 計算智能與中文信息處理教育部重點實驗室，太原030006

3.西南大學 人工智能學院，重慶400715

形式概念分析（formal concept analysis）是德國Wille 教授1982 年提出的從形式背景建立概念格來進行數據分析的有效數學工具，其核心概念為形式背景、形式概念與概念格。形式概念分析通過概念格所展現出的概念之間的特化與泛化關系，揭示了數據表的內在結構，發現了對象與屬性之間的依賴關系。目前，形式概念分析已被廣泛地研究，并應用到關聯分析、推薦系統、屬性約簡以及基于概念的認知學習等相關領域中。

形式概念分析對知識獲取的研究就是對蘊涵的研究。由于形式背景中得到的蘊涵數量往往很龐大，Qu等提出了決策蘊涵。決策蘊涵是在決策情形下的蘊涵，反映了條件屬性和決策屬性間的決策關系。Zhai等從語義方面給出了決策蘊涵的閉包、一致閉包等相關概念，并對-推理規則的完備性進行了討論；提出了合并推理規則，證明了擴增推理規則與合并推理規則相對于決策蘊涵語義層面的完備性，即給定一個完備集，可以通過擴增推理規則和合并推理規則從完備集中推導出對應的封閉集。在此基礎上，賈楠等提出了新的推理規則：合并推理規則。相比于合并推理規則，合并推理規則形式上更加簡潔，并證明了合并推理規則是合理的，并且該推理規則與擴增推理規則組成的推理規則集是完備且無冗余的。

上文研究僅僅考慮了確定條件下屬性蘊涵，針對不確定條件的情況，Zaki等研究了關聯規則的語義，Balcázar提出了標準冗余、普通冗余和基于閉包冗余等概念，并且在此基礎上提出了基于普通冗余的推理規則以及基于閉包冗余的推理規則。基于這些研究，Zhai等在不精確條件下對決策蘊涵進行了拓展，提出了可變決策蘊涵，從邏輯層面研究了可變決策蘊涵的語義和語構特征。在語構方面，文獻[22]提出了四條推理規則，并且證明了其中三條推理規則“有效度收縮推理規則”“有效度提升推理規則”和“置空推理規則”相對于可變決策蘊涵的語義是合理的和完備的。另外，Zhang等考慮了其他知識表示形式，如概念規則和粒規則，討論了這些知識表示形式與決策蘊涵之間的關系。Zhai等進一步研究了模糊決策蘊涵，從邏輯角度研究了模糊決策蘊涵的語義特征和語構特征。

雖然不同框架提出了不同類型的決策蘊涵，但是并沒有對不同類型的決策蘊涵進行比較性的研究。本文基于可變決策蘊涵，提出了受限可變決策蘊涵，并從語構層面研究了受限可變決策蘊涵和決策蘊涵在推理規則上的關系，并從語義層面為語構上的區別提供了解釋，同時對受限可變決策蘊涵和決策蘊涵在知識推理能力強弱等方面進行了探討。

1 基本概念及性質

1.1 決策蘊涵邏輯

決策蘊涵主要分為數據層面與邏輯層面上的研究。本節主要介紹了決策蘊涵邏輯層面上的研究，分為語義研究和語構研究。

決策蘊涵的語構方面主要研究推理規則的合理性、完備性和無冗余性。文獻[17]提出兩條推理規則。

擴增推理規則：

合并推理規則：

文獻[17]進一步證明了擴增推理規則和合并推理規則的合理性、完備性以及無冗余性。

1.2 可變決策蘊涵邏輯

設為完備格，可變決策蘊涵的形式為(→,)，其中(→)為決策蘊涵，∈稱為決策蘊涵的有效度。

設為完備格，?(?)。定義可變決策蘊涵函數為α:2×2→，滿足對于任意,∈2，若?，則α(,)≥α(,)。

幾種可變決策蘊涵函數定義如下。

令=(,,,)為決策背景T={g?g|∈}?(?)，?，?。

（1）設=[0,1]，則置信度是可變決策蘊涵函數：

（2）設=[0,1]，則支持度是可變決策蘊涵函數：

（3）設=[0,1]×[0,1]，則置信度和支持度是可變決策蘊涵函數：

設L為可變決策蘊涵集，定義可變決策蘊涵函數(,)=∨{y|(→B,y)∈L且?B}。

設L為可變決策蘊涵集，定義：

可變決策蘊涵的語構方面主要是研究推理規則的合理性、完備性和無冗余性。文獻[22]提出四條推理規則。

有效度收縮推理規則：

有效度提升推理規則：

置空推理規則：

后件收縮推理規則：

文獻[22]證明了有效度收縮推理規則、有效度提升推理規則和置空推理規則的合理性、完備性以及無冗余性。

2 受限可變決策蘊涵

2.1 受限可變決策蘊涵的語義

需要將可變決策蘊涵的不確定性剝離，才能對可變決策蘊涵和決策蘊涵進行比較，為此，本文首先將有效度限制到集合={0,1}。

令={0,1}，∈，稱可變決策蘊涵(→,)為受限可變決策蘊涵。

由定義9 可知，若有效度為1，可變決策蘊涵(→,1) 成立；若有效度為0，可變決策蘊涵(→,0)不成立。為了防止混淆，將受限可變決策蘊涵集記為L。

根據定義5，受限可變決策蘊涵函數定義為：

需要注意的是，命題3 僅僅在剝離不確定性情況下成立，對于一般的可變決策蘊涵不成立，如例2所示。

令L={(→,(1,0.5)),(→,(0.5,1))}，=[0,1]×[0,1]。應用有效度提升推理規則到L可得(→,(1,1))，即有L?(→,(1,1))。然而，L中并不存在{}?′滿足(→′,(1,1))?L。

由例2 可以看出，命題3 對于可變決策蘊涵不成立是源于真值結構的不可比性或非鏈性。換句話說，若為鏈，則命題3 對可變決策蘊涵成立。

令=[0,1]，L 為可變決策蘊涵，則L?(→,1)當且僅當存在?′滿足(→′,1)∈L。

2.2 受限可變決策蘊涵的語構

本節將可變決策蘊涵上的推理規則應用于受限可變決策蘊涵。

通過分析可知，應用有效度收縮推理規則到(→,1)只能推導出(→,1)，因此該推理規則對于受限可變決策蘊涵失效。應用有效度提升推理規則可得到以下推理規則。

有效度提升推理規則1：

有效度提升推理規則2：

對于(→,0)和(→,0)，應用有效度提升推理規則只能得到(→?,0)，因此，有效度提升推理規則在這種情況失效。當可變決策蘊涵的有效度為0 時，該可變決策蘊涵不成立，因此不是有效的決策知識。

可以看出，有效度提升推理規則1 的作用是縮減成立的可變決策蘊涵(→,1)或(→,1)的后件為?；有效度提升推理規則2 的作用是縮減(→,1)的后件。由有效度提升推理規則1 和有效度提升推理規則2 可知，無論(→,1)的有效度等于1 還是0 都可以得出(→?,1)，因此，可變決策蘊涵(→?,1)的成立與(→,1)的有效度沒有關系；換句話說，有效度提升推理規則1 和有效度提升推理規則2 可以合并為一條推理規則——-有效度提升推理規則：

最后，應用后件收縮推理規則可得-后件收縮推理規則：

命題5 說明-有效度提升推理規則和-后件收縮推理規則是等價的。

-有效度提升推理規則和-后件收縮推理規則等價。

首先證明-有效度提升推理規則能夠推出-后件收縮推理規則的推理結果。當(→,1)成立且?時，有?=，應用-有效度提升推理規則有(→?,1)=(→,1)。反過來，當(→,1)成立且?時，由??和-后件收縮推理規則有(→?,1)。

與其他推理規則不同，雖然置空推理規則只能推導出不成立的可變決策蘊涵，然而，該推理規則對于受限可變決策蘊涵的完備性是必要的。其原因在于：首先，無論對于決策蘊涵還是可變決策蘊涵（或模糊決策蘊涵），推理過程都是一個動態的過程，是將某條決策蘊涵為真的程度提升的過程。對于決策蘊涵，推理過程是推導出成立的決策蘊涵的過程，也是將該決策蘊涵為真的程度由0 提升為1 的過程；對于可變決策蘊涵，推理過程是將可變決策蘊涵的有效度提升的過程。因此，對于受限可變決策蘊涵來說，類似于決策蘊涵，推理過程是該受限可變決策蘊涵的有效度由0 提升為1 的過程。其次，由受限可變決策蘊涵的語義可知，任意有效度為0 的可變決策蘊涵均可由任意受限可變決策蘊涵集語義推出，因此包含在該受限可變決策蘊涵集導出的封閉集中。因此，為了滿足該語義要求，需要使用置空推理規則導出這些受限可變決策蘊涵。換句話說，對于有效度為1 的受限可變決策蘊涵來說，置空推理規則提供了推理的起點；對于有效度為0 的受限可變決策蘊涵來說，置空推理規則提供了推理的終點。

因此，在剝離不確定性后，可變決策蘊涵上只有置空推理規則和-后件收縮推理規則兩條推理規則。

定理1 驗證了上述分析的正確性。

令={0,1}，L為封閉的受限可變決策蘊涵，則置空推理規則和-后件收縮推理規則相對于受限可變決策蘊涵的語義是完備的，即對L的完備集D?L，(→,)∈L當且僅當(→,)可以使用置空推理規則和-后件收縮推理規則從D推出。

充分性。由置空推理規則和-后件收縮推理規則的合理性可知結論成立。

必要性。若(→,0)∈L，則該受限可變決策蘊涵可由置空推理規則得到。若(→,1)∈L，由D是L的完備集可知，D?L，因此D?(→,1)。此時，由命題3 可知，存在′滿足?′，(→′,1)∈D，應用-后件收縮推理規則到(→′,1)即可得到(→,1)。

由定理1 可以看出，受限可變決策蘊涵上的推理規則僅僅是決策蘊涵上推理規則的特殊情形。具體來說，-后件收縮推理規則僅僅是擴增推理規則的一個特例；而從推理過程來看，置空推理規則也是決策蘊涵上的推理規則。事實上，如果只關注有效度為1 的可變決策蘊涵，-后件收縮推理規則也可以保證推出所有可以語義導出的有效度為1 的受限可變決策蘊涵。

3 受限可變決策蘊涵和決策蘊涵關系研究

可變決策蘊涵是處理有效度為[0,1] 的決策類型，決策蘊涵是處理經典情形{0,1}的決策類型。從處理類型看，似乎可以得出決策蘊涵是可變決策蘊涵的特例，但從語構角度看，受限可變決策蘊涵上的推理規則僅僅是決策蘊涵上擴增推理規則的一個特例。因此，決策蘊涵并不是可變決策蘊涵的特例，相反，受限可變決策蘊涵的推理規則僅僅是決策蘊涵推理規則的特殊情形。下面將從語義的角度論述該結論產生的原因。

下面的定理說明，如果受限可變決策蘊涵集L可以語義導出某些受限可變決策蘊涵，則該受限可變決策蘊涵對應的決策蘊涵也可以被相應的決策蘊涵集L語義導出。

令={0,1}，L為受限可變決策蘊涵集，L為L對應的決策蘊涵集。若L?(→,1)，則L?→。

由L?(→,1)和命題3可知，存在?′滿足(→′,1)∈L，因此有→′∈L；再由定義3可知L?→′。此時，假設╞L，則╞→′，因此當??時有′??；再由?′可知，當??時有?′??，因此╞→，從而L?→。

需要注意的是，定理2的逆并不成立，如例3所示。

假設受限可變決策蘊涵集及其相應的決策蘊涵集為：

應用擴增推理規則到→有→?→。顯然，此時并不存在{?′滿足(→′,1)∈L，由命題3可知(→,1)并不能由L語義導出。

例3 說明，可以由決策蘊涵集L推導出的決策蘊涵不一定可以由L推導出來；換句話說，在受限的情況下，可變決策蘊涵的推理能力弱于決策蘊涵。該結論事實上驗證了語構推理的正確性，即受限可變決策蘊涵的推理規則一方面僅能推導出后件縮小的可變決策蘊涵(如→)，推導不出前件擴大的可變決策蘊涵(如→)；另一方面，受限可變決策蘊涵的推理規則僅能應用于單個可變決策蘊涵，無法像合并推理規則一樣應用于兩個或兩個以上的可變決策蘊涵，因此難以推導出合并推理規則可以推導出的決策知識。例如，在例3中，應用合并推理規則到L可以推導出決策蘊涵→，但該決策蘊涵無法由置空推理規則和-后件收縮推理規則推出。

在語義方面，受限可變決策蘊涵較弱的推理能力會導致難以生成更為緊湊的決策知識集。

令={0,1}，L為受限可變決策蘊涵集，L 為對應的決策蘊涵集。若L是冗余的，則L 必是冗余的。

假設L是冗余的，則存在(→,1)滿足L?(→,1)?(→,1)。由命題3 可知，必存在?′滿足(→′,1)∈L?(→,1)。顯然有→′∈L?→。由定義3可知L?→?→′。假設╞L?→，則╞→′，因此當??時有′??，再由?′可知，當??時有?′??，因此╞→，從而L?→?→，L必是冗余的。

定理3 的逆命題并不成立，如例4 所示。

假設受限可變決策蘊涵集：

可驗證，對任意(→,1)∈L，都有L?(→,1)?(→,1)，因此L是無冗余的。對于L，→可由→應用擴增推理規則推出，→可由→和→應用合并推理規則推出。

定理3 和例4 說明，若L是冗余的，則L必是冗余的；換句話說，若L是無冗余的，則L必是無冗余的。因此，L比L更容易冗余，因而更需要簡化，也可以更加緊湊。同樣以例4 為例，因為決策蘊涵→和→在L中是冗余的，所以可以簡化，即L′={→,→} 可以保持L的所有決策知識，但比L更加精簡。相比較而言，在受限可變決策蘊涵框架下，L是無冗余的，因此不可以進一步精簡；在決策蘊涵框架下，其中的受限可變決策蘊涵(→,1)和(→,1)事實上是可以精簡的。

4 結束語

本文基于已有的決策蘊涵和可變決策蘊涵知識表示框架，分析了受限可變決策蘊涵的語義特征和語構特征，并將不確定性剝離后的可變決策蘊涵與決策蘊涵進行了比較研究。研究結果表明：（1）受限可變決策蘊涵上的推理規則只存在置空推理規則和-后件收縮推理規則兩條推理規則，其中置空推理規則并無實際價值，-后件收縮推理規則只是擴增推理規則的一個特例；（2）受限可變決策蘊涵的知識推理能力弱于決策蘊涵；（3）相對于受限可變決策蘊涵，決策蘊涵的知識表示形式更加精簡。

雖然受限可變決策蘊涵只是可變決策蘊涵的特例，但無論在語義上還是在語構上都有其獨特的特征。主要體現在：（1）語義上，受限可變決策蘊涵不僅允許取值為1，而且允許取值為格中的最大元（如(1,1)），因此受限可變決策蘊涵的語義更為寬泛；（2）語構上，受限可變決策蘊涵上的推理規則為決策蘊涵的特例，但這些推理規則值得進一步研究。一方面，這種研究可以進一步揭示推理規則間的聯系，對決策蘊涵來說，有助于發現最優的推理規則；另一方面，受限可變決策蘊涵上的推理規則為決策蘊涵的特例事實上說明這些推理規則更為簡潔，因此，基于受限可變決策蘊涵的推理會更為高效。

另外，當前的研究還缺少對決策蘊涵、模糊決策蘊涵和可變決策蘊涵的知識表示和推理能力的比較性研究。接下來將對以上決策類型進行比較性研究。