決策蘊涵與可變決策蘊涵上的推理規(guī)則研究

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

1.山西大學(xué) 計算機與信息技術(shù)學(xué)院，太原030006

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

3.西南大學(xué) 人工智能學(xué)院，重慶400715

形式概念分析（formal concept analysis）是德國Wille 教授1982 年提出的從形式背景建立概念格來進行數(shù)據(jù)分析的有效數(shù)學(xué)工具，其核心概念為形式背景、形式概念與概念格。形式概念分析通過概念格所展現(xiàn)出的概念之間的特化與泛化關(guān)系，揭示了數(shù)據(jù)表的內(nèi)在結(jié)構(gòu)，發(fā)現(xiàn)了對象與屬性之間的依賴關(guān)系。目前，形式概念分析已被廣泛地研究，并應(yīng)用到關(guān)聯(lián)分析、推薦系統(tǒng)、屬性約簡以及基于概念的認(rèn)知學(xué)習(xí)等相關(guān)領(lǐng)域中。

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

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

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

1 基本概念及性質(zhì)

1.1 決策蘊涵邏輯

決策蘊涵主要分為數(shù)據(jù)層面與邏輯層面上的研究。本節(jié)主要介紹了決策蘊涵邏輯層面上的研究，分為語義研究和語構(gòu)研究。

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

擴增推理規(guī)則：

合并推理規(guī)則：

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

1.2 可變決策蘊涵邏輯

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

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

幾種可變決策蘊涵函數(shù)定義如下。

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

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

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

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

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

設(shè)L為可變決策蘊涵集，定義：

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

有效度收縮推理規(guī)則：

有效度提升推理規(guī)則：

置空推理規(guī)則：

后件收縮推理規(guī)則：

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

2 受限可變決策蘊涵

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

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

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

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

根據(jù)定義5，受限可變決策蘊涵函數(shù)定義為：

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

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

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

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

2.2 受限可變決策蘊涵的語構(gòu)

本節(jié)將可變決策蘊涵上的推理規(guī)則應(yīng)用于受限可變決策蘊涵。

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

有效度提升推理規(guī)則1：

有效度提升推理規(guī)則2：

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

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

最后，應(yīng)用后件收縮推理規(guī)則可得-后件收縮推理規(guī)則：

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

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

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

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

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

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

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

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

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

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

3 受限可變決策蘊涵和決策蘊涵關(guān)系研究

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

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

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

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

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

假設(shè)受限可變決策蘊涵集及其相應(yīng)的決策蘊涵集為：

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

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

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

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

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

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

假設(shè)受限可變決策蘊涵集：

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

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

4 結(jié)束語

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

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

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