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

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

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

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

形式概念分析（formal concept analysis）是德國Wille 教授1982 年提出的從形式背景建立概念格來進(jìn)行數(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)域中。

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

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

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

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

1.1 決策蘊(yùn)涵邏輯

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

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

擴(kuò)增推理規(guī)則：

合并推理規(guī)則：

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

1.2 可變決策蘊(yùn)涵邏輯

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

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

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

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

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

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

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

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

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

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

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

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

置空推理規(guī)則：

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

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

2 受限可變決策蘊(yùn)涵

2.1 受限可變決策蘊(yùn)涵的語義

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

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

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

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

需要注意的是，命題3 僅僅在剝離不確定性情況下成立，對于一般的可變決策蘊(yùn)涵不成立，如例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 對于可變決策蘊(yùn)涵不成立是源于真值結(jié)構(gòu)的不可比性或非鏈性。換句話說，若為鏈，則命題3 對可變決策蘊(yùn)涵成立。

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

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

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

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

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

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

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

可以看出，有效度提升推理規(guī)則1 的作用是縮減成立的可變決策蘊(yùn)涵(→,1)或(→,1)的后件為?；有效度提升推理規(guī)則2 的作用是縮減(→,1)的后件。由有效度提升推理規(guī)則1 和有效度提升推理規(guī)則2 可知，無論(→,1)的有效度等于1 還是0 都可以得出(→?,1)，因此，可變決策蘊(yùn)涵(→?,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)出不成立的可變決策蘊(yùn)涵，然而，該推理規(guī)則對于受限可變決策蘊(yùn)涵的完備性是必要的。其原因在于：首先，無論對于決策蘊(yùn)涵還是可變決策蘊(yùn)涵（或模糊決策蘊(yùn)涵），推理過程都是一個動態(tài)的過程，是將某條決策蘊(yùn)涵為真的程度提升的過程。對于決策蘊(yùn)涵，推理過程是推導(dǎo)出成立的決策蘊(yùn)涵的過程，也是將該決策蘊(yùn)涵為真的程度由0 提升為1 的過程；對于可變決策蘊(yùn)涵，推理過程是將可變決策蘊(yùn)涵的有效度提升的過程。因此，對于受限可變決策蘊(yùn)涵來說，類似于決策蘊(yùn)涵，推理過程是該受限可變決策蘊(yùn)涵的有效度由0 提升為1 的過程。其次，由受限可變決策蘊(yùn)涵的語義可知，任意有效度為0 的可變決策蘊(yùn)涵均可由任意受限可變決策蘊(yùn)涵集語義推出，因此包含在該受限可變決策蘊(yùn)涵集導(dǎo)出的封閉集中。因此，為了滿足該語義要求，需要使用置空推理規(guī)則導(dǎo)出這些受限可變決策蘊(yùn)涵。換句話說，對于有效度為1 的受限可變決策蘊(yùn)涵來說，置空推理規(guī)則提供了推理的起點；對于有效度為0 的受限可變決策蘊(yùn)涵來說，置空推理規(guī)則提供了推理的終點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

令={0,1}，L為受限可變決策蘊(yùn)涵集，L 為對應(yīng)的決策蘊(yùn)涵集。若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è)受限可變決策蘊(yùn)涵集：

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

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

4 結(jié)束語

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

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

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