决策蕴含简化算法研究

Simplification of Implication on Decision-Making

摘要: 随着形式背景中数据的增多，概念数量会急剧增加，会使决策的过程变得复杂。大多数参考文献的研究主要集中于给定决策背景的条件下，决策规则的提取，本文首次以决策蕴含简化方法为研究重点，利用计算机模拟人的思维过程，通过计算对象的覆盖，进而计算出决策背景，并在此基础上生成非冗余限制决策蕴含，与非冗余决策规则相比，其形式更简化，更有利于决策者进行决策；其次，为使决策过程简单，提出了决策背景的生成定理及非冗余限制决策蕴含的处理定理并予以证明；随后提出了算法并讨论了算法的时间复杂度。通过实例分析，对比了其它决策规则提取算法的运行效率和分类能力，证明本文提出的算法具有可行性和正确性。最后进行了总结并讨论了开放性问题。

Abstract: As the size of data table grows, the concepts generated become larger in number, which make de-cision-making more complex. The majority of references focused on acquisition of decision rules based on decision formal context which was given. This paper focuses on simplification of implication on decision-making for the first time, makes use of computer simulating the procedures of human thought, via computing the covers of object set, computes decision formal context, which forms the basis of this paper, non-redundant limitary decision implication with more simplified form is deduced compared to decision rules meanwhile, which is beneficial to decision makers; secondly, puts forward judging theorems of handling redundant limitary decision implications and generating decision formal context with demonstration in order to make decision-making simplified; subsequently, proposes an algorithm and discusses the time complexity. Comparing with other algorithms on runtime and ability of classification, experimental results show that the proposed method approves feasibility and accuracy. In the end, it draws a conclusion and discusses open issues.

1. 引言

形式概念分析 [1] 最早由德国教授Wille R.提出，以形式背景和形式背景下生成的概念为基础，开创了概念格理论与应用研究的先河。随后作为数据分析和处理的重要工具，形式概念分析已被广泛应用于计算机推理、知识发现及机器学习等领域。国外学者的研究主要包括：形式背景的分解、概念格的图形表示 [2] 及属性选取方法等。

形式背景中数据量的增多，相应的概念数量会急剧增长，每一个概念都代表一种分类，对象的分类众多，会给决策者制定决策时带来巨大的挑战。属性约简可以将研究问题进行简化，Skowron教授 [3] 提出了基于区分矩阵的求核算法，利用合取、析取运算对区分矩阵进行求解，奠定了属性约简的研究基础； Sabita Mahapatra [4] 等针对粗糙集理论，利用不可辨识矩阵进行属性提取并生成了决策规则，与统计方法进行对比说明了算法的有效性；李进金等人 [5]，引入交式可约元的概念，扩展了属性约简的研究方法；张文修等人 [6] 提出了概念格约简的判定定理，将可辨识属性矩阵作为属性约简的方法；王霞等人 [7] 针对不可约元的属性约简问题构造了属性约简集，丰富了属性约简方法；Wenbin Qian [8] 等人针对不完全序的模糊决策信息系统，提出基于优势的粗糙集与α-割集相结合的属性约简方法，在一致和不一致的信息系统中利用了布尔推理的方法，设计了向前和向后属性约简算法求解近似最优属性约简；Hua Mao [9] 提出利用有向图进行属性约简和概念格构造，借助图论的上下文中的概念，定义属性集上的相关图，进一步，定义一个预先加权的相关图，进而，提出在有向图中删除顶点的方法，扩展了概念格的研究方法；Jiaqing Zhou [10] 等人讨论了覆盖相关族及其简化的概念，并给出覆盖相关族的计算方法，然后从简化覆盖计算所有属性约简，最后提出了一种启发式的属性约简方法；Nguyen Ngoc Thuy [11] 等人提出了基于商集的属性重要性度量方法，设计了计算核和约简的有效算法，还给出与有效计算属性重要性和在计算过程中显著减少数据大小直接相关的属性。

为使决策问题得以简化，管理效率得到大幅度地提高，本文以决策背景的生成，即实现决策一体化为研究重点，并在此基础上深入研究属性约简相关问题。

针对决策背景下的属性约简理论和决策规则提前问题，李金海 [12] 等人对不同的约简方法进行比较，通过大量的实验给决策者提供参考依据；魏玲 [13] 等对于强协调决策形式背景和弱协调决策形式背景，分别给出了协调集和蕴含映射的判定定理及属性约简方法；李金海 [14] 等人提出了最小闭包概念格和限制决策蕴含的概念，并给出最简形式的决策规则；郭松涛 [15] 等人没有求解核心属性，而是给出了不必要属性的判定定理，通过设计启发式算法证明了算法的有效性。

上述文献针对形式背景下的属性约简提供了丰富的理论支撑，但基于决策规则的属性约简的相关文献相对较少，因此本文以决策背景的生成为切入点，这也是本文的创新所在。

本文分为五部分：第一部分介绍了概念格的理论基础；第二部分引入了非冗余限制决策蕴含相关理论并予以证明；第三部分提出了决策蕴含简化方法及属性约简算法并进行了理论分析；第四部分通过实验分析论证算法的有效性；最后，进行总结并讨论了开放性问题。

2. 概念格理论基础

形式背景表示为一个三元组 $\left(X,Y,I\right)$，其中X表示对象集，Y表示属性集， $I\subseteq X\times Y$ 表示一个二元关系， $I\left(x,y\right)\in \left\{0,1\right\}$。

定义 1形式概念

令 $A\subset X$， $B\subset Y$，则：

$A^{\ast }=\left\{y|\forall x\in A,I\left(x,y\right)=1\right\}$

$B^{\ast }=\left\{x|\forall y\in B,I\left(x,y\right)=1\right\}$

$\langle A,B\rangle$ 是一个概念当且仅当 $A=B^{*}$ 且 $B=A^{*}$。其中A为概念的外延，B为概念的内涵。

性质1 $A^{\ast }={\displaystyle \underset{x\in A}{\cap }{x}^{\ast }}$， $B^{\ast }={\displaystyle \underset{y\in B}{\cap }{y}^{\ast }}$。

性质2 $Y_1\subseteq Y_2\subseteq Y\Rightarrow Y_2{}^{\text{*}}\subseteq Y_1{}^{\text{*}}$。

性质3 $Y_1\subseteq Y_1{}^{\text{**}}$。

证明：由概念的外延和内涵的定义可证。

偏序关系( $\le$ )可以描述概念间的等级结构。设 $\langle A_1,B_1\rangle$ 和 $\langle A_2,B_2\rangle$ 为形式背景下的两个概念，当且仅当 $A_1\subset A_2$ 或 $B_1\supset B_2$，记为 $\langle A_1,B_1\rangle \le \langle A_2,B_2\rangle$。

若 $B\subseteq B_1$ 并且没有 $\langle A_2,B_2\rangle$ 满足 $B\subseteq B_2\subseteq B_1$，则 $\langle A_1,B_1\rangle$ 是 $\langle A,B\rangle$ 的后继。

概念格 [16] [17] [18] 是偏序集，每个元素拥有最小上界和最大下界。概念格表示为： $L\left(I\right)=\left(\left(X,Y,I\right),\le \right)$。

定理1 基于属性的概念

$\forall a\in Y$， $\langle a^{\ast },a^{\ast \ast }\rangle$ 为基于属性的概念。

证明：根据形式概念的定义，令 $A=a^{\ast }$， $B=a^{\ast \ast }$，则 $B=A^{\ast }$ ； $B^{\ast }=a^{\ast \ast \ast }=a^{\ast }=A$，证毕。

推论1 形式概念

$Y_1\subseteq Y$， $\langle Y_1^{\ast },Y_1^{\ast \ast }\rangle$ 为形式概念。

推论2 形式概念续

$X_1\subseteq X$， $\langle X_1^{\ast \ast },X_1^{\ast }\rangle$ 为形式概念。

证明：由外延内涵和定理1易证。

3. 非冗余限制决策蕴含相关理论

定义2 [19] 决策背景

五元组 $\left(X,Y,I,T,J\right)$ 为一个决策背景，其中T为决策属性， $J\subseteq X\times T$ 是一个二元关系， $J\left(x,t\right)\in \left\{0,1\right\}$。

定义3 [19] 强规则、弱规则与冗余规则

$L\left(I\right)=\left(\left(X,Y,I\right),\le \right)$ 为基于条件属性的概念格， $L\left(I_1\right)=\left(\left(X,T,J\right),\le \right)$ 为基于决策属性的概念格，若 $\forall \langle A,B\rangle \in L\left(I\right)$， $\langle C,D\rangle \in L\left(I_1\right)$，满足 $A\subseteq C$，且 $C\ne X,C\ne \varnothing$，则称 $B\to D$ 是一个规则，B为规则的前置条件，D为规则的结论。若 $A=C$，则称 $B\to D$ 为强规则；若 $A\subset C$，则称为弱规则。若存在，有，则规则为冗余规则。

定理2 冗余规则判定定理1

若，，满足，且，则有强规则，弱规则，且弱规则为冗余规则。

证明：详见文献 [19]。

通过以上论述不难发现对于任意一个决策概念，若强弱规则同时存在，则弱规则必为冗余规则。

定义4 [14] 最小闭标记

令为形式背景，若存在属性集，，如果，使，则称R为A的闭标记，也称R为F的生成，如果对于R的任意一个子集，，均不是A的闭标记，则称R为A的最小闭标记。

定义5 [14] 限制决策蕴含与限制决策蕴含

令为决策背景，，且，，且，若R是A的最小闭标记，则为决策背景下的限制决策蕴含；特殊地，若，则为决策背景下的强限制决策蕴含。

由定义5可知，限制决策蕴含与决策规则相比，前置条件包含的属性更少，决策形式更简化，更有利于决策者进行决策。

定义6 [20] 协调集

令为形式背景，若存在属性集使得。则称E为形式背景的协调集。

定义7 条件概念和决策概念的外延集

在决策背景中，条件概念的外延集为：，决策概念的外延集为：。

定理3 冗余规则判定定理2

，且，规则为非冗余规则，则不存在，满足，也不存在，满足，否则为冗余规则。

证明：详见文献 [19]。

定理4 冗余限制决策蕴含判定定理

若同时存在限制决策蕴含，，，则为冗余限制决策蕴含。

证明：由已知条件易知，，，，即可以由已知条件蕴含得出，所以为冗余限制决策蕴含，得证。

定义8 决策

令表示决策属性，则。k越小，决策越简单；反之，决策越复杂。

定理5 决策简化定理1

，，满足，且不，满足，使，为使决策过程简单，则。

证明：

由已知可得，，则。假设，，满足，即，则，成立，则仍需要决策，则。因为，所以，。即决策变得复杂，与题设矛盾，故假设不成立，得证。

定理6 决策简化定理2

，满足，，，且，有，则，。

证明：由定理5易证，假设，由题设条件可知，，即对进行了两次决策，与简化决策的目的相悖，故假设不成立，即，。

定义9 覆盖

令，若，则为X的一个覆盖。

由定义9易知，对象集X的覆盖有多个。

定理7 决策简化定理3

令，满足，，，，则。

证明：由定理5、定理6可知，，由已知条件可知，，即，得证。

定理8 强规则与强限制决策蕴含判定定理

令为形式背景，，满足，则必存在强规则，若为的最小闭标记，则有强限制决策蕴含。

证明：由定理5可知，，易得。即，因为，且，由强规则的定义可得，为强规则；又因为为的最小闭标记，由强限制决策蕴含的定义可得，得证。

定义10 [21] 约简

，，满足，则为F的约简。

定理9 约简判定定理

令为形式背景，存在非冗余强限制决策蕴含，，，则下的约简。

证明：由定理1可知，，，，由已知条件可知：，，。由限制决策蕴含的定义得，为的最小闭标记，也是的生成。由

定义10可知，为的约简。令，，，，，，，由限制决策蕴含的定义可以推出：，，，与原背景中的决策蕴含相同，令，则在子背景中无法推出，所以，均不能约简，满足约简的定义。故约简为，得证。

4. 决策蕴含简化方法及属性约简算法

由以上论述可以归纳出生成非冗余限制决策蕴含的一般步骤：给定形式背景，首先生成概念及每个概念的最小闭标记，将概念按外延降序排序，计算对象的覆盖，由此生成决策背景，然后生成限制决策蕴含，最后对冗余限制决策蕴含进行处理并输出。下面以伪码形式给出非冗余限制决策蕴含的输出算法：

(1) 生成条件概念

输入：形式背景；

调用概念生成算法；

输出：概念结构体数组；/*为概念的个数，存储外延中元素的个数，存储内涵中元素的个数，存储外延，存储内涵，存外延的最小闭标记*/

(2) 求X的覆盖

;/*按eno降序对概念进行快速排序*/

;;

for (i=2;i 1;i++)

{;

if() {no=i;; break;}

}/*数组t存决策属性*/

(3) 生成决策背景

while()

{for(k=1;; k++)

; j++; k++/*二维数组DC存决策背景*/

}

(4) 生成决策概念

决策概念采用结构体数组，成员同上。

(5) 调用最小闭标生成算法

详见文献 [20]，最小闭标记存入。

(6) 生成限制决策蕴含

for each

for each

if()

{;

;/*结构体数组LDI存限制决策蕴含，其有三个成员，存前置条件，存结论，存前置条件中属性的个数*/

break;

}

(7) 冗余限制决策蕴含处理

for each

for each

{if(in && in)m++;

if()；

} /*前置条件和结论是其它限制决策蕴含的并集的限制决策蕴含为冗余限制决策蕴含*/

(8) 限制决策蕴含输出

for each

Output:;

算法的时间复杂度分析：

概念的生成算法最优可以是线性的时间复杂度 [20]，Ganter提出的算法，生成每个概念的时间复杂度为。

本文采用快速排序算法，时间复杂度为，下面将重点讨论属性约简算法的时间复杂度。

不难发现步骤(2) 求X的覆盖的算法时间复杂度；步骤(3) 生成决策背景的算法的时间复杂度；步骤(6) 生成限制决策蕴含的算法时间复杂度；步骤(7) 冗余限制决策蕴含处理算法的时间复杂度；步骤(8) 限制决策蕴含输出算法的时间复杂度。综上所述，本文算法可以在多项式时间内完成，时间复杂度为。

5. 实验分析

例1形式背景如表1所示，基于形式背景的概念如表2所示，生成的概念格如图1所示，排序后的概念及最小闭标记详见表3。因为，由定理5可得，，，生成的决策背景、决策概念如表4、表5所示，决策概念格见图2。其中决策概念为，，，，强限制决策蕴含为，，，，因为，所以为冗余限制决策蕴含，即，，为非冗余限制决策蕴含。

表6将本文算法与从规则定义出发提取出的规则进行了对比，表明本文得到的限制决策蕴含个数少且形式简单。

实验的配置环境为：CPU E6600、内存2GB 、Windows 10、Microsoft Visual C++ 6.0。随机生成3组形式背景，实验结果表明本文提出的算法执行效率不如文献 [22] 高，但高于文献 [15] (时间复杂度为)和文献 [23] (时间复杂度为)，具体如图3所示。

由约简后的规则，，可知，约简，约简后的背景如表7所示，约简后的概念见表8，而决策概念不变，应用本文的算法，仍然可以生成非冗余限制决策蕴含，，，原背景的所有蕴含均得以输出，约简前后没有信息损失，蕴含提取具有有效性。

约简后的形式背景中没有出现0行，即对象没有损失，易知决策概念不变。选取文献 [11] 的例子进行对比，结果表明本文提出的算法和 [11] 均能保证约简前后决策属性的分类能力不变，但本文算法提取出的蕴含更有效，形式更简单，详见表9。

Table 1. Formal context

表1. 形式背景

Table 2. Concepts based on formal context

表2. 基于形式背景的概念

Figure 1. The concept lattice based on conditional attributes

图1. 条件属性概念格

Table 3. Concepts after sorted and minimal closed label

表3. 排序后的概念及最小闭标记

Table 4. Decision formal context

表4. 决策背景

Table 5. Concepts based on decision-making attributes

表5. 基于决策属性的概念

Figure 2. The concept lattice based on decision-making attributes

图2. 基于决策属性的概念格

Table 6. Comparison with rules

表6. 规则对比实验

Figure 3. Running efficiency

图3. 运行效率

Table 7. Decision formal context after reduction

表7. 约简后的决策背景

Table 8. Conditional concepts after reduction

表8. 约简后的条件概念

Table 9. Comparison with ability of classification

表9. 分类能力比较

6. 总结

本文首次以决策蕴含简化方法为研究重点，通过计算对象的覆盖，进而生成决策背景，并在此基础上推导非冗余限制决策蕴含，与非冗余决策规则相比，其形式更简化，更有利于决策者进行决策；其次，提出简化的决策背景的生成定理、非冗余限制决策蕴含的处理定理及决策背景下属性约简的判定定理并予以证明，得出为使决策过程简单，需要决策的对象子集之间不能存在包含关系的结论；随后提出了算法并讨论了算法的时间复杂度，借助归并排序算法对形式背景生成的概念进行排序，能够使计算对象集的覆盖算法的效率得到提高，利用结构体数组存储概念，巧妙地设置循环控制条件(，break等)，本文算法的时间复杂度为。通过实例分析，算法具有可行性与正确性。

决策背景下的属性约简算法以决策规则的提取为根本出发点，需要在不损失决策规则的前提下进行约简，并没有从属性的语义或重要性出发考虑能否进行约简。因此关注属性的语义及重要性，设计更高效的规则提取算法是文章进一步的研究方向。

致谢

在此衷心感谢论文撰写过程中各位作者的通力支持，同时对参考文献中作者的工作表示诚挚地感谢。

基金项目

辽宁省自然科学基金项目(2019-ZD-0349，2019-ZD-0348)。

NOTES

^*通讯作者。