决策蕴涵上的推理规则和推理过程研究*

贾 楠，张少霞，翟岩慧，2+，李德玉，2

1.山西大学 计算机与信息技术学院，太原 030006

2.山西大学 计算智能与中文信息处理教育部重点实验室，太原 030006

1 引言

形式概念分析是由德国Wille教授于1982年提出的一种从形式背景进行数据分析、知识表示和规则提取的强有力工具[1]。形式背景和形式概念是形式概念分析的两个基本概念，概念格是从形式背景上提取的形式概念的集合，本质上是描述对象和属性之间的关系，并通过Hasse图来可视化概念之间的泛化和例化关系。目前，形式概念分析已经被广泛应用于信息检索[2]、软件工程[3]、机器学习[4]、社会网络[5]、基于认知的概念学习[6-10]和知识约简[11-17]。

形式概念分析中对知识获取的研究就是对蕴涵的研究[18-21]。蕴涵表示为形如A→B的公式，其含义是任意具有属性集A的对象集同时也具有属性集B。但是，从形式背景中得到的蕴涵的数量往往很庞大[19]。

引入决策蕴涵是减少蕴涵数量的一种方法，决策蕴涵是在决策情形下的蕴涵，也是决策背景下的知识表示形式，反映了条件属性和决策属性之间的决策关系[21-22]。从逻辑角度对决策蕴涵的研究分为语义和语构两方面[22]，其中语义部分的研究包括以下几方面[22-25]：

决策蕴涵的合理性：怎样判断决策蕴涵是否合理？或者说，决策蕴涵在什么情况下是成立的？

决策蕴涵集的封闭性：决策蕴涵集是否包含所有合理的决策蕴涵？

决策蕴涵集的完备性：如何在不损失信息的前提下生成一个决策蕴涵集？

决策蕴涵集的冗余性：一个决策蕴涵集是否是紧致的?即，是否存在某些决策蕴涵可以从决策蕴涵集中的其他决策蕴涵推导出来？

在语构方面，首先给定一个决策蕴涵集和一些推理规则，然后研究如何应用这些推理规则从给定的决策蕴涵集中推导出新的决策蕴涵。这个方面的研究需要回答下列问题[21-22]：

推理规则的合理性：是否推理规则推导出的任何决策蕴涵都是合理的？

推理规则集的完备性：是否可以由给定的推理规则集推导出所有合理的决策蕴涵？

推理规则集的无冗余性：推理规则之间是否是紧致的？即，是否某些推理规则可以由其他推理规则导出？

近年来，针对语构上的推理规则已经开展了一些研究工作。Qu等[21]考虑了一种特殊的推理规则——α-推理规则。该规则通过扩大决策蕴涵的前件和减少决策蕴涵的后件来得到新的决策蕴涵，但是该推理规则并不是完备的。Li等[26-30]研究了决策背景、不完备决策背景和实决策背景中的推理规则。Zhai等[22]提出了两种推理规则——扩增推理规则和合并推理规则，并证明了它们的完备性，即给定一个完备集，可以通过扩增推理规则和合并推理规则从完备集中推导出对应的封闭集。虽然文献[22]从理论上证明了扩增推理规则和合并推理规则的合理性和完备性，但并没有具体研究如何使用推理规则推导出封闭集。本文提出了一种更简单的推理规则——后件合并推理规则。后件合并推理规则是特殊的合并推理规则，它只对前件相同的决策蕴涵进行合并，证明了后件合并推理规则是合理的，并且该推理规则与扩增推理规则组成的推理规则集是完备的、无冗余的；进一步，研究了扩增推理规则和后件合并推理规则的性质，最后给出了使用这两条推理规则从完备集推导其对应封闭集的有效方法。

2 基本概念和性质

本章给出形式概念分析中的基本概念和性质。

定义1[19]形式背景是一个三元组K=(G,M,I)，其中G是对象集，M是属性集，I⊆G×M是对象和属性之间的二元关系。对于g∈G m∈M(g,m)∈I表示“对象g具有属性m”。

定义2[19]设K=(G,M,I)为形式背景，对于集合A⊆G，记：

相应地，对于集合B⊆M，记：

定义3[19]设K=(G,M,I)为形式背景，对于集合A⊆G和B⊆M，若AI=B且BI=A则称二元组(A,B)为形式概念，简称概念。其中A为该概念的外延，B为该概念的内涵。

性质1[19]设K=(G,M,I)为形式背景，对于集合A,A1,A2⊆G和B,B1,B2⊆M有：

定义4[19]设K=(G,M,I)为形式背景，C1=(A1,B1)和C2=(A2,B2)是概念，定义偏序：

所有概念在该偏序下构成格，称为概念格。

3 决策蕴涵

决策蕴涵有两种研究方式：一种是决策蕴涵的逻辑研究；另一种是决策蕴涵的数据研究。决策蕴涵的逻辑研究包括语义和语构研究；决策蕴涵的数据研究主要指决策背景上的决策蕴涵研究。首先介绍决策蕴涵的逻辑研究。

3.1 决策蕴涵逻辑

3.1.1 决策蕴涵逻辑的语义

首先给出决策蕴涵逻辑中决策蕴涵的定义。

定义5[22]设C是条件属性集，D是决策属性集，其中C⋂D=∅。若A⊆C且B⊆D，则称A→B是一个决策蕴涵。此时，A为该决策蕴涵的前提，B为该决策蕴涵的结论。

定义6[22]设C是条件属性集，D是决策属性集，L和L1是决策蕴涵集。定义：

（1）对于属性集T⊆C⋃D和决策蕴涵A→B，若A⊈T⋂C或B⊆T⋂D，则称T满足A→B（或称T是A→B的一个模型），记为T╞A→B。若T满足L中的任意一个决策蕴涵，则T是L的一个模型，记为T╞L。

（2）若对于任意的T⊆C⋃D T╞L蕴含T╞A→B，则称A→B可以从L语义导出，记为L├A→B。若任意的A1→B1∈L1都可以从L语义导出，则称L1可以从L中语义导出，记为L├L1。

（3）若任意的A→B∈L都不能从L中其他的决策蕴涵语义导出，即L{A→B}⊢/{A→B}，则称L是无冗余的。

（4）若任意可以从L中语义导出的决策蕴涵都包含在L中，则称L是封闭的。

（5）对于封闭的决策蕴涵集L，若L1⊆L且L├1L，则称L1相对于L是完备的。

定义7[22]设C是条件属性集，L是决策蕴涵集，A⊆C在L上的闭包为：

可以证明[22]，AL是A相对于L得到的最大结论。

定理1[22]设L为决策蕴涵集，A→B是一个决策蕴涵，则L├A→B当且仅当B⊆AL。

3.1.2 决策蕴涵逻辑的语构

决策蕴涵逻辑的语构研究包括推理规则的合理性、完备性和无冗余性。文献[22]提出两条推理规则：

扩增推理规则：

合并推理规则：

定理2[22]（合理性）扩增推理规则和合并推理规则是合理的，即：

（1）A→B是一个决策蕴涵，且有A1⊇A和B1⊆B，则A→B⊢A1→B1；

（2）A→B和A1→B1是决策蕴涵，则{A→B,A1→B1}⊢A⋃A1→B⋃B1。

定理3[22]（完备性）扩增推理规则和合并推理规则是完备的，即对任意封闭的决策蕴涵集L及其完备集L1⊆L，A→B∈L当且仅当A→B可以使用扩增推理规则和合并推理规则从L1推出。

定义8令L为决策蕴涵集：

（1）使用推理规则φ在L上得到的所有决策蕴涵的集合记为Lφ；

（2）使用推理规则集Φ在L上得到的所有决策蕴涵的集合记为LΦ。

推理规则集的无冗余性意味着推理规则之间不能互相导出，这说明每个推理规则在进行推理时都是不可替代的。

定义9[22]令Φ为推理规则集，φ为某一推理规则且φ∉Φ。称推理规则φ相对于Φ是无冗余的，若存在决策蕴涵集L，使得Lφ⊈LΦ。称推理规则集Φ是无冗余的，若对任意的φ∈Φ，φ相对于Φφ是无冗余的。

定理4[22]（无冗余性）扩增推理规则和合并推理规则是无冗余的。

下面的例子说明了定理4的正确性。

例1令L={{a1}→{d1},{a1a2}→{d2}}。使用扩增推理规则从L可得{a1a2}→{d1}，显然该决策蕴涵不能由合并推理规则得到。同样地，对{a1}→{d1}和{a1a2}→{d2}使用合并推理规则得到{a1a2}→{d1d2}，显然该决策蕴涵也不能只通过扩增推理规则得到。

这里，用{a1a2}表示{a1,a2}，后文类似。

3.2 决策背景中的决策蕴涵

下面给出决策蕴涵的数据研究，即决策背景上的决策蕴涵，并将决策蕴涵逻辑的研究运用到决策背景中的决策蕴涵上。

首先引入决策背景的概念。

定义10[21]决策背景为三元组K=(G,C⋃D,IC⋃ID)，其中G为对象集，C为条件属性集，D为决策属性集，且C⋂D≠∅，IC⊆G×C为条件关联关系，ID⊆G×D为决策关联关系。对于g∈G m∈C⋃D(g,m)∈IC或(g,m)∈ID表示“对象g具有属性m”。

决策背景K=(G,C⋃D,IC⋃ID)通常用一个二维表表示，在表中行列的交点处为1表示这个对象含有这个属性。

例2表1给出决策背景K=(G,C⋃D,IC⋃ID)，其中，G={g1,g2,g3,g4,g5,g6,g7,g8}C={a1,a2,a3,a4,a5,a6}D={d1,d2}。

Table 1 Decision context表1 决策背景

定义11[21]设K=(G,C⋃D,IC⋃ID)为决策背景，对于集合A1⊆C A2⊆D和B⊆G记：

对于g∈G和A⊆C，将{g}C、{g}D和(AC)D简记为gC、gD和ACD。

显然，性质1也适用于定义11的算子。例如，对于A1⊆A2⊆C，若。

定义12[21]设K=(G,C⋃D,IC⋃ID)为决策背景，A⊆C且B⊆D。若AC⊆BD，则称A→B是一个决策蕴涵。其中A是该决策蕴涵的前提，B是该决策蕴涵的结论。

例3以表1所示的决策背景为例，令A={a2a3}，则AC={g5g7} 令B={d2} 则BD={g2g5g7} 显然，AC⊆BD，则A→B是一个决策蕴涵。

4 决策蕴涵上的推理规则和推理过程

4.1 决策蕴涵上的推理规则

3.1.2 小节引入了扩增推理规则和合并推理规则。在此基础上，提出一条新的推理规则——后件合并推理规则：

显然，后件合并推理规则是一种特殊的合并推理规则，它只对前件相同的决策蕴涵的后件进行合并。因此，后件合并推理规则在形式上更简洁。

因为合并推理规则是合理的，因此后件合并推理规则也是合理的。

定理5（合理性定理）后件合并推理规则是合理的，即：若A→B1和A→B2是决策蕴涵，则{A→B1,A→B2}├A→B1⋃B2。

证明显然。 □

下面证明扩增推理规则和后件合并推理规则是无冗余的。

首先，根据定义8，定义：

定义13令L为决策蕴涵集：

（1）使用扩增推理规则在L上得到的所有决策蕴涵的集合记为LA；

（2）使用后件合并推理规则在L上得到的所有决策蕴涵的集合记为；

（3）使用合并推理规则在L上得到的所有决策蕴涵的集合记为LC；

（4）先使用扩增推理规则得到LA，再使用后件合并推理规则得到，简记为。

定理6（无冗余性定理）后件合并推理规则和扩增推理规则是无冗余的。

证明根据定义9，只需证明：

（1）存在决策蕴涵集L有；

（2）存在决策蕴涵集L有LCα⊈LA。

下面证明（1）。令L1={A1→B1}，其中B1≠∅，令A2⊇A1，B2⊂B1，则由扩增推理规则可以得到决策蕴涵A2→B2。显然，决策蕴涵A2→B2不能由后件合并推理规则推出。

下面证明（2）。令L2={A→B1,A→B2}，其中B1⊈B2且B2⊈B1，由后件合并推理规则可从L得到决策蕴涵A→B1⋃B2。显然，决策蕴涵A→B1⋃B2不能由扩增推理规则推出。

综上所述，后件合并推理规则和扩增推理规则是无冗余的。 □

例4令L={{a1}→{d1}{a1}→{d2}}。使用扩增推理规则从{a1}→{d1}可得{a1a2}→{d1}，显然该决策蕴涵不能由后件合并推理规则推出。同样地，对{a1}→{d1}和{a1}→{d2}使用后件合并推理规则得到{a1}→{d1d2}，显然该决策蕴涵也不能只通过扩增推理规则得出。

进一步，可以得到：

性质2合并推理规则相对于扩增推理规则和后件合并推理规则是冗余的。

证明根据定义9，只需证明对任意的决策蕴涵集L若A→B∈LC那么A→B也可以通过扩增推理规则和后件合并推理规则得到。

因为A→B∈LC所以A→B必然可以通过L中的若干条决策蕴涵使用合并推理规则得到，即必存在P⊆L使得：

接下来证明通过扩增推理规则和后件合并推理规则可以从P得到A→B。

因为⋃{A1|A1→B1∈P}=A，所以对任意的A1→B1∈P有A1⊆A，进而可以对P中所有的决策蕴涵使用扩增推理规则得到集合：

又因为⋃{B1|A1→B1∈P}=B，使用后件合并推理规则，将P1中决策蕴涵的前件和后件分别进行合并即可得到A→B。 □

例5令L={{a1}→{d1},{a2a3}→{d2}}。使用合并推理规则可以从{a1}→{d1}和{a2a3}→{d2}得到{a1a2a3}→{d1d2}。事实上，也可以分别对{a1}→{d1}和{a2a3}→{d2}使用扩增推理规则得到{a1a2a3}→{d1}和{a1a2a3}→{d2}，然后再对{a1a2a3}→{d1}和{a1a2a3}→{d2}使用后件合并推理规则得到{a1a2a3}→{d1d2}。

事实上，性质2和例5也说明，在推导过程中，后件合并推理规则可以替代合并推理规则，因此扩增推理规则和后件合并推理规则也是完备的。

定理7（完备性定理）扩增推理规则和后件合并推理规则是完备的，即对任意封闭的决策蕴涵集L及其完备集L1⊆L A→B∈L当且仅当A→B可以使用扩增推理规则和后件合并推理规则从L1推出。

证明（充分性）根据定理2和定理5，扩增推理规则和后件合并推理规则是合理的，因此L1├A→B；而又因为L是封闭的，因此A→B∈L。

（必要性）因为A→B∈L根据定理3知道A→B可以使用扩增推理规则和合并推理规则从L1推出，因此A→B也可以使用扩增推理规则、合并推理规则和后件合并推理规则从L1推出；又根据性质2，合并推理规则相对于扩增推理规则和后件合并推理规则是冗余的，因此A→B可以只使用扩增推理规则和后件合并推理规则从L1推出。 □

4.2 决策蕴涵的推理过程研究

通过决策蕴涵的语构研究，可以使用推理规则集从决策蕴涵集导出新的决策蕴涵。4.1节中已证明了扩增推理规则和后件合并推理规则相对于决策蕴涵的语义是完备的，即从任意的决策蕴涵集开始，重复应用这两条推理规则，可以得到给定决策蕴涵集的封闭集。在本节，将讨论推理规则的性质，并将其应用在推理过程中，以便更有效地从决策蕴涵集得到封闭集。

下面，首先定义推理过程中的一些算子。

定义14令L为一决策蕴涵集，记：

（1）LA为对L中所有的决策蕴涵均使用一次扩增推理规则得到的所有决策蕴涵的集合，即：

方便起见，规定：

（1）对L中的决策蕴涵先进行一次A运算，再进行一次Cα运算记为，其余类似；

（2）从L开始，连续进行n次A运算记为，其余类似。

例6以表1中的决策背景为例，L={{a2a4a5a6}→{d1}{a1a3a4a5}→{d1}{a1a3a4a5}→{d2}}是它的一个决策蕴涵集。决策蕴涵集LA和分别如下所示：

根据定理7，对于完备集L，可以交替进行A运算和Cα运算，直至不再产生新的决策蕴涵即可得到，但是这样的推导方式效率并不高。

下面，首先研究扩增推理规则和后件合并推理规则的性质以及如何通过A运算和Cα运算得到LA和（LA和分别是使用扩增推理规则和后件合并推理规则在L上得到的所有的决策蕴涵的集合，见定义13）。

性质3令L为一决策蕴涵集，则：

（1）L⊆LA

（2）LA=LAA

（3）LA=LA

证明

（1）对于任意的A→B∈L，因为A⊆A且B⊆B，因而A→B∈LA，因此有L⊆LA。

（2）根据（1），显然有LA⊆LAA只需证明LAA⊆LA。令A→B∈LAALA，此时必存在A1→B1∈LA，并由此得到A→B，即有A⊇A1且B⊆B1。因为A1→B1∈LA，所以必存在A2→B2∈L，并由此得到A1→B1，即有A1⊇A2且B1⊆B2。因此得到A⊇A2且B⊆B2，结合A2→B2∈L可知A→B∈LA。

（3）因为LA是使用扩增推理规则在L上得到的所有的决策蕴涵的集合，所以必存在n使得LA=（一般都假设条件属性集和决策属性集为有限集，因此L也必为有限集，后文情况类似）。又因为LA=LAA，所以LA=LA。 □

例7以例6中的决策蕴涵集L为例，根据性质3可知，LA即为例6中的LA。

性质3和例7说明，在推导过程中，只需要对L中的所有决策蕴涵都进行一次A运算，即可得到通过扩增推理规则生成的所有决策蕴涵。

性质4令L为一决策蕴涵集，则：

证明

（1）对于任意的A→B∈L由因此。

共有两种情况：

①m≤n。此时，由（1）和题设可得：

②m＞n因为所以：

例8以例6中的决策蕴涵集L={{a2a4a5a6}→{d1}{a1a3a4a5}→{d1}{a1a3a4a5}→{d2}}为例，对L多次进行Cα运算可得到集合LCα：

性质5令为封闭的决策蕴涵集且，则

证明显然，因此只需证明。对任意的A→B∈，令P={A1→B1∈L|A1⊆A}，因为对于任意的A1→B1∈P，都有A1⊆A和B1⋂B⊆B1，所以可使用扩增推理规则得到A→B1⋂B，进而可推理得到集合P1={A→B1⋂B|A1→B1∈P} 此时，根据LA的定义有P1⊆LA。

接下来证明B=⋃{B1⋂B|A1→B1∈P}。

根据定义7可知AL=⋃{B1|A1→B1∈P} 因为且A→B∈根据定理1可知B⊆AL即B⊆⋃{B1|A1→B1∈P} 则B⋂{B1|A1→B1∈P}=B而根据集合的分配律有B⋂(⋃{B1|A1→B1∈P})=⋃{B⋂B1|A1→B1∈P} 因此有⋃{B⋂B1|A1→B1∈P}=B此时，使用后件合并推理规则可以将P1中所有的决策蕴涵合并为A→B因而有A→B∈又因为P1⊆LA所以A→B∈。

综上所述，对任意的A→B∈有A→B∈，因此。 □

性质5表明了生成封闭集不仅可以通过交替使用这两条推理规则，也可以先使用扩增推理规则得到LA再对LA使用后件合并推理规则得到封闭集。

定理8令为封闭的决策蕴涵集且，则。

证明根据性质3可知LA=LA，因此

定理8在性质5的基础上又进一步简化了生成封闭集的过程，在推导过程中，仅对决策蕴涵集中所有的决策蕴涵应用一次扩增推理规则即可。

5 结论与展望

本文基于已有的扩增推理规则和合并推理规则，提出了后件合并推理规则。该推理规则不仅简化了合并推理规则，而且具有合理性，与扩增推理规则组成的推理规则集也具有完备性和无冗余性;在此基础上，研究了扩增推理规则和后件合并推理规则的性质，并应用于推导过程，提出具体的推导方法。在实际问题中会遇到各种不同的需求，而不同的推导方法有可能满足不同的需求，因此也丰富了从决策蕴涵集得到封闭集的方法理论。

另外，这一研究也引出了一些新的问题，例如：不论使用扩增推理规则和合并推理规则，还是使用扩增推理规则和后件合并推理规则，都需要交替使用才能推导出所有的决策蕴涵，这样势必会增加推理的复杂度，因此是否存在更简单有效的推理规则，即只需一条推理规则便足以完成该推理过程?是否可以将本文的工作推广到可变决策蕴涵[31]和模糊决策蕴涵[20，32]上？这也是接下来需要进一步研究的问题。