2.845

2023影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于种群个体数自适应的多尺度量子谐振子优化算法

焦育威 王鹏

张家录, 吴霞. 形式背景上近似推理生成决策蕴涵研究. 自动化学报, 2024, 50(11): 2286−2300 doi: 10.16383/j.aas.c220705
引用本文: 焦育威, 王鹏. 基于种群个体数自适应的多尺度量子谐振子优化算法. 自动化学报, 2023, 49(7): 1587−1600 doi: 10.16383/j.aas.c200247
Zhang Jia-Lu, Wu Xia. Study on the approximate reasoning models of decision implication in formal decision context. Acta Automatica Sinica, 2024, 50(11): 2286−2300 doi: 10.16383/j.aas.c220705
Citation: Jiao Yu-Wei, Wang Peng. Multi-scale quantum harmonic oscillator algorithm based on subpopulation number adaptive. Acta Automatica Sinica, 2023, 49(7): 1587−1600 doi: 10.16383/j.aas.c200247

基于种群个体数自适应的多尺度量子谐振子优化算法

doi: 10.16383/j.aas.c200247
基金项目: 国家自然科学基金(60702075), 西南民族大学研究生创新型科研项目(CX2020SZ03) 资助
详细信息
    作者简介:

    焦育威:西南民族大学计算机科学与技术学院硕士研究生. 主要研究方向为量子启发式算法, 高性能计算. E-mail: jiaoyuwei@stu.swun.edu.cn

    王鹏:西南民族大学计算机科学与技术学院教授. 2004年获中国科学院成都计算机应用研究所计算机软件与理论专业博士学位. 主要研究方向为量子理论, 量子启发式算法, 计算智能与高性能计算. 本文通信作者. E-mail: wp002005@163.com

Multi-scale Quantum Harmonic Oscillator Algorithm Based on Subpopulation Number Adaptive

Funds: Supported by National Natural Science Foundation of China (60702075) and Innovative Research Project for Postgraduates of Southwest Minzu University (CX2020SZ03)
More Information
    Author Bio:

    JIAO Yu-Wei Master student at the School of Computer Science and Technology, Southwest Minzu University. His research interest covers quantum inspired algorithm and high performance computing

    WANG Peng Professor at the School of Computer Science and Technology, Southwest Minzu University. He received his Ph.D. degree in computer software and theory from Chengdu Institute of Computer Applications, Chinese Academy of Sciences in 2004. His research interest covers quantum mechanics, quantum inspired algorithm, computational intelligence, and high performance computing. Corresponding author of this paper

  • 摘要: 优化算法中多种群采样方式可转化为蒙特卡洛对当前函数积分的评估, 针对不同子种群对整体评估的差异性, 提出子种群规模 (个体数) 自适应的改进策略, 并用于多尺度量子谐振子优化算法(Multi-scale quantum harmonic oscillator algorithm, MQHOA) 的改进, 同时阐述多种群策略所具有的量子特性以及量子隧道效应与寻优性能的相关性. 已有的优化算法忽视了动态调节子种群规模对寻优能力的影响, 该策略通过动态调节子种群规模, 提高适应度差的子种群发生量子隧道效应的概率, 增强了算法的寻优能力. 将改进后的算法MQHOA-d (Multi-scale quantum harmonic oscillator algorithm based on dynamic subpopulation) 与 MQHOA 及其他优化算法在 CEC2013 测试集上进行测试, 结果表明原算法 MQHOA“早熟”问题在 MQHOA-d 中得到解决, 且 MQHOA-d 对多峰函数和复合函数优化具有显著优势, 求解误差和计算时间均小于几种经典优化算法.
  • 基于信息系统的知识获取是机器学习、人工智能研究的重要方面, 而规则提取又是知识获取的主要内容之一[1]. 形式背景$ (G,M,I) $是一个由对象集$ G $, 属性集$ M $及$ G $与$ M $间的二元关系$ I $组成的三元组. 在基于形式背景进行规则提取时, 规则是通过内涵属性集合之间的关系描述且通过对应的外延对象集合之间的包含(或近似包含)关系来反映, 其形式是一个如$ A \to B $的表达式, 其中$ A $和$ B $是属性集合, 其含义是形式背景中具有属性$ A $的对象也具有属性$ B $[2-3].

    为了从逻辑角度刻画蕴涵规则, 通常在更广泛意义下讨论蕴涵规则$ A \to B $, $ A $和$ B $分别是条件属性集和决策属性集, 此时的蕴涵规则被称为决策蕴涵规则, 简称决策蕴涵[3-4]. Zhai等[5-6]在抽象的条件属性和决策属性集上引进决策蕴涵, 从逻辑语义和逻辑语构2个方面对决策蕴涵进行了探讨[6], 他们还在Pavelka模糊逻辑意义下提出并讨论了模糊决策蕴涵. 贾楠等[7]分析了这种一般决策蕴涵的推理规则, 并讨论了推理规则集的完备性和无冗余性. 为适应智能决策的需要, 王琪等[8]研究了含参模糊决策蕴涵. 张少霞等[9]讨论了基于逻辑公式的逻辑型决策蕴涵, 使得决策知识的表示更加丰富. 抽象集合上的决策蕴涵讨论固然可以丰富决策蕴涵的理论, 但实际数据分析中在讨论决策蕴涵时更加关注信息系统上、特别是形式背景中的决策蕴涵$ A \to B $, 此时$ A $和$ B $分别是决策形式背景的条件属性集和决策属性集. 形式背景上的决策蕴涵还包括概念规则和粒规则2个特殊类型. Zhang等[10]对决策形式背景中的决策蕴涵、概念规则、粒规则的特征和彼此间的关系进行了研究, 借助决策蕴涵逻辑分析了概念规则和粒规则中的信息损失及其信息丢失背后的原因. 为有效进行多粒度意义下的数据分析, 李金海等[11-12]讨论了多粒度意义下的决策蕴涵性质, 实现了跨粒度重组数据的决策蕴涵生成.

    传统上, 人们习惯于应用二值逻辑及其推理以探究事物之间的确定因果关系和获取确定性新知识[13]. 但是, 正如亚马逊的推荐系统[14]和谷歌的流感预测[15]等现实案例所展示, 对于大数据环境下的数据分析和应用, 人们更加关注事物之间的相关关系分析, 寻找数据之间的近似因果关系一样受到人们的关注和重视[16]. 也正是因为这个原因, 人们不断尝试创新各种方法以探索事物之间的近似因果关系, 并依托这种近似因果关系从现有知识获取新知识[17]. 推理是寻找事物之间因果关系, 从已有知识获取新知识的重要方法, 是数理逻辑的主要研究内容. 人们一般认为模糊逻辑及其推理应用是探究事物之间近似因果关系及获取不确定性知识的手段和方法[18-19]. 然而, 正如文献[18]所指出, 借助于全蕴涵三I推理思想[19], 经典二值逻辑系统中存在着与模糊推理相同的求解机制, 从而基于经典二值逻辑也可以进行近似推理的探讨.

    决策蕴涵、概念规则都是信息系统上知识的表现形式, 决策蕴涵、概念规则推理是知识推理的一个重要方面. 因此, 将经典二值逻辑框架下的近似推理模式应用于决策蕴涵、概念规则, 讨论决策蕴涵、概念规则的推理模式及性质, 依据形式背景上的现有决策蕴涵、概念规则, 通过近似推理方法寻找新的决策蕴涵、概念规则是有意义的. 从知识发现的角度看, 基于现有数据集上的决策蕴涵、概念规则等知识, 采用近似推理的方法获取更大数据集上的决策蕴涵、概念规则等新的知识是非常有价值的.

    本文应用经典二值逻辑中的分离规则(Modus ponens, MP)、逆分离规则(Modus tonens, MT)近似推理来探讨形式背景上的决策蕴涵和概念规则的近似推理的特征, 并提出实现方法. 首先, 讨论决策蕴涵的属性逻辑语义的性质. 其次, 在经典二值逻辑框架下分析基于全蕴涵三I推理思想的决策蕴涵和概念规则的MP、MT近似推理模式的特征, 证明决策蕴涵的MP、MT近似推理结论是决策蕴涵, 概念规则的MP、MT近似推理的结论是概念规则. 引进属性逻辑公式间的伪距离, 并在逻辑伪距离空间中分析对象参数变化对决策蕴涵的MP、MT近似推理结论的影响. 最后, 提出2个利用MP、MT近似推理来生成拟决策蕴涵的算法, 对2个算法的复杂性进行分析, 并通过数值实验对本文提出方法的有效性进行验证.

    本节概述下文要用到的形式概念分析和属性逻辑的知识.

    定义1[3]. 一个形式背景是一个三元组$ K = (G,M,I) $, 其中$ G $为对象集合, $ M $为属性集合, $ I $是$ G $到$ M $的二元关系, $ gIm $表示对象$ g $具有属性$ m $.

    通常称不包含空行、空列、满行和满列的形式背景为正则形式背景[20]. 本文只讨论正则形式背景.

    定义2[3]. 在形式背景$ K = (G,M,I) $中, 对$ A \subseteq G $, 记$ \alpha^I(A) = \{m \in M | \forall g \in A, gIm\} $ ($ A $中对象共同具有属性的集合); 对$ B \subseteq M $, 记$\beta^I(B) = \{g \in G | \forall m \in B, gIm\}$ (具有$ B $中所有属性的对象集合); $ \alpha^I $, $ \beta^I $分别称为$ K $的属性映射和对象映射.

    定义3[3]. 在形式背景$ K = (G,M,I) $中, 对$A \subseteq G$, $ B \subseteq M $, 如果$ \alpha^I(A) = B $, $ \beta^I(B) = A $, 则称$C = (A, B)$是一个概念, 并称$ A $是概念$ C $的外延, $ B $是概念$ C $的内涵. 形式背景$ K $的全体概念记为$ C(K) $.

    命题1[3]. 对$ A, A_1, A_2 \subseteq G $, $ B, B_1, B_2 \subseteq M $.

    1) $\alpha^I(A_1) \subseteq \alpha^I(A_2) \Rightarrow \alpha^I(A_2) \subseteq \alpha^I(A_1)$, $\beta^I(B_1) \subseteq \beta^I(B_2) \Rightarrow \beta^I(B_2) \subseteq \beta^I(B_1)$;

    2) $ A \subseteq \beta^I(\alpha^I(A)) $, $B \subseteq \alpha^I(\beta^I (B))$;

    3) $ A \subseteq \beta^I(B) $当且仅当$ B \subseteq \alpha^I(A) $;

    4) $ \alpha^I(A_1 \cup A_2) = \alpha^I(A_1) \cap \alpha^I(A_2) $, $\beta^I(A_1 \cup A_2) = \beta^I(A_1) \cap \alpha^I(A_2)$;

    5) $ \alpha^I(A_1 \cap A_2) \supseteq \alpha^I(A_1) \cup \alpha^I(A_2) $, $\beta^I(A_1 \cap A_2) \supseteq \beta^I(A_1) \cup \alpha^I(A_2)$;

    6) $(\beta^I(\alpha^I(A))、 \alpha^I(A))、 (\beta^I (B) $ 和 $\alpha^I(\beta^I (B))) $都是概念.

    定义4[21]. 设$ K = (G,M,I) $是一个形式背景, $\neg、 \wedge\;和\; \to$是逻辑联结词. 称$ a \in M $为一个原子属性公式, 全部原子属性公式生成的$ (\neg, \wedge, \to) $自由代数记为$ \Gamma(K) $, 称$ \Gamma(K) $中的元素为基于形式背景$ K $的属性逻辑公式 (简称属性公式).

    $ \Gamma(K) $中的元素可以通过以下方式[21]得到:

    1)$ M \subseteq \Gamma(K) $;

    2)若$ \varphi \in \Gamma(K) $, 则$ \neg \in \Gamma(K) $;

    3)若$ \varphi, \psi \in \Gamma(K) $, 则$ \varphi \wedge \psi, \varphi \to \psi \in \Gamma(K) $;

    4)$ \gamma \in \Gamma(K) $当且仅当$ \gamma $可经过以上3步有限次所产生.

    本文讨论的决策蕴涵的前件和后件都是属性合取公式, 对于$ B \subseteq M $, 由$ B $中的属性合取公式为$ \varphi = \wedge_{b \in B} $. 在不会引起混淆时, 时常不区分属性集$ B $及$ B $中属性组成的合取公式. 同时, 为了表述简便, 也经常使用逻辑联结词$\varphi \vee \psi = \neg (\neg \varphi \;\wedge \neg \psi)$.

    对逻辑公式进行赋值是研究二值逻辑、模糊逻辑等逻辑系统语义的基本手段[18], 但现有文献对决策逻辑[1]及决策蕴涵的逻辑研究较少有从赋值出发来进行[6]. 本文作者在基于软集的决策分析[22]和基于形式背景的属性逻辑[21, 23]的研究中, 已经尝试从属性公式赋值的角度来对相关内容进行讨论.

    设$ K = (G,M,I) $是形式背景. 对每个$uu \in G$, $ u $自然地决定了一个映射 $ v^{(0)}_{u}: M \to \{0,1\} $, $ v^{(0)}_{u}(a) = I(u, a) $. 由于$ \Gamma(K) $是由原子属性公式集$ M $生成的$(\neg、 \wedge、 \to)$型自由代数, 故$ v^{(0)}_{u} $可唯一延拓成$ \Gamma(K) $上的一个映射$ v_{u} $, $ v_{u} $在$ M $上的限制正是$ v^{(0)}_{u} $, 称映射$ v_{u} $为属性公式集的一个K-赋值, 全体K-赋值之集记为$ \Omega_K = \{v_{u}: u \in G\} $. 显然, $ G $到$\Omega_K$之间有一一对应$\pi: G \to \Omega_K$, $ \pi(u) = v_{u} $. 对每个$ a \in M $, $ a $决定了一个定义在 $ G $上的函数 $ \overline{a} $, $\overline{a}: G \to \{0,1\}$, $ \overline{a} (u) \;=\; I(a, u) $. 同样, 一个由 $ t $个原子属性公式$a_{i_{1}},\cdots,a_{i_{t}}$组成的属性公式$\varphi = \varphi (a_{i_{1}}, \cdots, a_{i_{t}})$也决定了 $ G $ 上的函数 $\overline{\varphi}(u)\; =\; \overline{\varphi} (\overline{a}_{i_{1}}(u),\cdots, \overline{a}_{i_{t}}(u))$, $ \overline{\varphi} $作用于$\overline{a}_{i_{1}},\cdots,\overline{a}_{i_{t}}$的方式如同$ \varphi $作用于$a_{i_{1}},\cdots,a_{i_{t}}$的方式一样. 例如, $ \varphi = \neg a_1 \vee a_2 \to a_3 $, 则$ \overline{\varphi}(u) = (1- \overline{a}_1(u)) \vee \overline{a}_2(u) \to \overline{a}_3(u) $.

    另一方面, 按照经典二值逻辑系统的赋值方法, 由映射$ v^{M}_{u}: M \to \{0,1\} $所决定的公式集$ \Gamma(K) $上的映射$ v: \Gamma(K) \to \{0,1\} $为$ \Gamma(K) $的赋值, 对$ \varphi \in \Gamma(K) $, $ v(\varphi) $称为逻辑公式$ \varphi $的值. $ \Gamma(K) $的全部赋值之集记为$\Omega$. 一般地, $\Omega_K$为$\Omega$的子集.

    例1. 一个形式背景$ K = (G,M,I) $见表1, 其中对象集$ G = \{u_1, u_2, u_3, u_4, u_5, u_6, u_7\} $, 属性集$ M = \{a_1, a_2, a_3, a_4, a_5, a_6\} $.

    表 1  形式背景$K=(G,M,I)$
    Table 1  A formal context $K=(G,M,I)$
    $G$$a_1$$a_2$$a_3$$a_4$$a_5$
    $u_1$11001
    $u_2$00110
    $u_3$10100
    $u_4$01010
    $u_5$01011
    $u_6$10101
    下载: 导出CSV 
    | 显示表格

    根据K-赋值的产生方法, $\Omega_K$有7个赋值. 而按照二值逻辑赋值方法, $\Omega$有$ 2^{5} = 32 $个赋值. 一般地, $ \Omega_K $为 $\Omega$的真子集, 比如赋值 $ v_{0}: v_{0}(a_1) = 0 $, $ v_{0}(a_2) = 0 $, $ v_{0}(a_3) = 0 $, $ v_{0}(a_4) = 0 $, $ v_{0}(a_5) = 0 $; $v_{1}: v_{1}(a_1) \,=\, 1$, $v_{1}(a_2) \,= \,1$, $v_{1}(a_3)\, =\, 1$, $v_{1}(a_4) \,= \,0$, $v_{1}(a_5) = 0$; $v_0、 v_1$在 $\Omega$中, 而不在 $\Omega_K$中.

    由于全体K-赋值集$\Omega_K$为全体赋值集$\Omega$的真子集, 因此, 本文的K-赋值也可作为文献[24]所讨论的数理逻辑部分赋值理论的具体实例.

    在形式背景中, $ I(u,a) = 1 $表明一个对象$ u $具有属性$ a $, 此时有$ \overline{a}(u) = 1 $. 一般地, 如果$ \overline{\varphi}(u) = 1 $, 则表明对象$ u $具有属性公式$ \varphi $中的全部属性, 此时也称对象$ u $满足公式$ \varphi $. 对于$ \varphi \in \Gamma(K) $, 称满足$ \varphi $的对象之集$ \{u \in G | \overline{\varphi}(u) = 1\} $为$ \varphi $的K-语义, 本文记$ \varphi $的K-语义为$ ||\varphi||_{K} $, 在不会引起混乱时, 也可将下标$ K $省略. 属性公式的K-语义有以下命题2.

    命题2[21]. 设$ K = (G,M,I) $是一个形式背景, 则对任何$ \varphi, \psi \in \Gamma(K) $, 下式成立:

    1) $ ||\neg \varphi|| = G - ||\varphi|| $;

    2) $ ||\varphi \vee \psi|| = ||\varphi|| \cup ||\psi|| $;

    3) $ ||\varphi \wedge \psi|| = ||\varphi|| \cap ||\psi|| $;

    4) $ ||\varphi \to \psi|| = (G-||\varphi||) \cup ||\psi|| $.

    命题3[21]. 设$\Sigma = \{v_{u_{1}}, \cdots, v_{u_{l}}\} \subset \Omega_K$, $\{r_{1}, \cdots, r_{l}\}$是一个0 ~ 1序列, 则存在属性公式$ \varphi \in \Gamma(K) $满足$v_{u_{i}}(\varphi) = r_i, i = 1, \cdots, l$.

    在经典二值逻辑的确定性推理中, 有2个基本的推理规则: MP和MT, 这2个规则同样适应属性逻辑的推理. 但在人工智能的研究中同样也关注近似推理, 即对知识的近似获取同样感兴趣. 因此, 人们也经常需要如下适应于近似推理的广义MP[17-18]:

    $$ \left\{ \begin{array}{ll} \text{已 知} \qquad\quad \varphi \to \psi \quad \\ \underline{\text{且给定} \qquad \varphi^{\ast}\quad\quad } \qquad \qquad \qquad \\ \text{求} \qquad\qquad\qquad \psi^{\ast} \end{array} \right. $$ (1)

    式中, $ \varphi,\psi,\varphi^{\ast},\psi^{\ast} \in \Gamma(K) $.

    在确定推理中, 上述广义MP式(1)是无解的. 在实际应用中, 虽然不能找到其精确解, 但可以寻求上述广义MP式(1)的近似解. 根据全蕴涵三I推理思想, 所求的近似解$ \psi^{\ast} $要得到小前提$ \varphi^{\ast} $的最大支持, 还要得到大前提$ \varphi \to \psi $的最大支持, 即$ \psi^{\ast} $应该使得对于所讨论范围内的对象, 蕴涵公式$(\varphi \to \psi) \to (\varphi^{\ast} \to \psi^{\ast})$能取得最大值1. 因此, 给出如下广义MP解的定义.

    定义5[17]. 设$ \varphi,\psi,\varphi^{\ast} \in \Gamma(K) $, $\Sigma、 \Delta$为$ G $的2个子集. 基于形式背景的近似推理的广义MP式(1)的$( \Sigma, \Delta)$解是满足以下条件的属性公式$ \psi^{\ast} $:

    1) $\forall x \in \Delta, \forall y \in \Sigma$,

    $(\overline{\varphi}(y) \to \overline{\psi}(x)) \to (\overline{\varphi^{\ast}} (y) \to \overline{\psi^{\ast}}(x)) = 1.$

    2)如果有$\gamma \in \Gamma(K)$满足$\forall x \in \Delta, \forall y \in \Sigma$,

    $ (\overline{\varphi}(y) \to \overline{\psi}(x)) \to (\overline{\varphi^{\ast}}(y) \to \overline{\gamma}(x)) = 1 $, 则$\forall x \in \Delta$, $ \overline{\psi^{\ast}}(x) \leq \overline{\gamma}(x) $.

    定理1[17]. 设$\varphi,\psi,\varphi^{\ast} \in \Gamma(K)$, $\Sigma$和$ \Delta $是$ G $的2个子集. 基于形式背景的广义MP式(1)的解$ \psi^{\ast} $满足:

    $$ \overline{\psi^{\ast}}(x) = [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}(y) \to \overline{\psi}(x))], x \in \Delta $$ (2)

    式中, $ \wedge$表示函数取小运算.

    注1. 由于$ \overline{\varphi}(y) \to \overline{\psi}(x) = (1 - \overline{\varphi}(y)) \wedge \overline{\psi}(x) $, 因此式(2)可改写为:

    $$ \overline{\psi^{\ast}}(x) = \mathop\vee\limits_{y \in \Sigma} [\overline{\varphi^{\ast}}(y) \wedge (1-\overline{\varphi}(y))] \vee [\overline{\psi}(x) \wedge\mathop \vee\limits_{y \in \Sigma} \overline{\varphi^{\ast}}(y)] $$

    式中, $\vee$表示函数取大运算.

    从而有以下4种特殊情形:

    1)如果有$y_0 \in \Sigma$, 使得$\overline{\varphi^{\ast}}(y_0) \wedge (1-\overline{\varphi}(y_0)) = 1$, 则$\forall x \in \Delta$, $ \overline{\psi^{\ast}}(x) = 1 $.

    2)如果对任何$y \in \Sigma$, 有$ \overline{\varphi^{\ast}}(y) = 0 $, 则$\forall x \in \Delta$, $ \overline{\psi^{\ast}}(x) = 0 $.

    3)如果有$y_0 \in \Sigma$, 使得$ \overline{\varphi^{\ast}}(y) = 1 $, 且$||\varphi^{\ast}|| \subseteq ||\varphi||$, 则$\forall x \in \Delta$, $ \overline{\psi^{\ast}}(x) = \overline{\psi}(x) $.

    4)如果$ \varphi = \varphi^{\ast} $, 则由式(2)有$ \psi = \varphi^{\ast} $, 从而广义MP的确是经典MP的推广.

    对于如下多规则MP近似推理问题[17]:

    $$ \left\{ \begin{array}{ll} \text{已 知} \qquad \quad \varphi_1 \to \psi_1 \quad \\ \qquad \qquad \qquad \cdots \\ \qquad \qquad \quad \varphi_n \to \psi_n \quad \qquad \qquad \\ \underline{\text{且给定} \qquad \varphi^{\ast}\quad\quad } \\ \text{求} \qquad\qquad\qquad \psi^{\ast} \end{array} \right. $$ (3)

    如果采用先推理后聚合的推理过程, 聚合算子取合取算子, 则其推理结论的属性公式函数为[17]:

    $$ \overline{\psi^{\ast}}(x) = \mathop\wedge^{n}\limits_{i = 1} \mathop\vee\limits_{y \in \Sigma} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], x \in \Delta $$ (4)

    类似于二值逻辑推理的MT, 考虑如下基于形式背景的近似推理的广义MT[17]:

    $$ \left\{ \begin{array}{ll} \text{已 知} \qquad\quad \varphi \to \psi \quad \\ \underline{\text{且给定} \qquad \qquad \psi^{\ast} } \qquad \qquad \\ \text{求} \qquad\qquad \varphi^{\ast} \end{array} \right. $$ (5)

    式中, $\varphi,\psi,\varphi^{\ast},\psi^{\ast} \in \Gamma(K)$.

    定义6[17]. 设$\varphi,\psi,\psi^{\ast} \in \Gamma(K)$, $\Sigma、\Delta$是$ G $的2个子集. 基于形式背景的近似推理的广义MT式(3)的$( \Sigma, \Delta)$解是满足以下条件的属性公式$ \varphi^{\ast} $:

    1)$\forall x \in \Delta,\;\forall y \in \Sigma$,

    $(\overline{\varphi}(y) \to \overline{\psi}(x)) \to (\overline{\varphi^{\ast}} (y) \to \overline{\psi^{\ast}}(x)) = 1 .$

    2)如果有$\chi \in \Gamma(K)$满足$\forall x \in \Delta, \forall y \in \Sigma$,

    $(\overline{\varphi}(y) \to \overline{\psi}(x)) \to (\overline{\varphi^{\ast}}(y) \to \overline{\gamma}(x)) = 1$则$\forall y \in \Sigma$, $ \overline{\psi^{\ast}}(y) \geq \overline{\chi}(y) $.

    定理2[17]. 设$\varphi,\psi,\psi^{\ast} \in \Gamma(K)$, $\Sigma、 \Delta$是$ G $的2个子集. 基于形式背景的广义MT式(3)的解$ \varphi^{\ast} $满足:

    $$ \overline{\varphi^{\ast}}(y) = \mathop\wedge\limits_{x \in \Delta} [(\overline{\varphi}(y) \to \overline{\psi}(x)) \to \overline{\psi^{\ast}}(x)], y \in \Sigma $$ (6)

    注2. 由于$ \overline{\varphi}(y) \to \overline{\psi}(x) = (1 - \overline{\varphi}(y)) \wedge \overline{\psi}(x) $, 因此式(6)可改写为:

    $$ \overline{\varphi^{\ast}}(y) = \mathop\wedge\limits_{x \in \Delta} [\overline{\psi^{\ast}}(x) \vee (1-\overline{\psi}(x))] \wedge [\overline{\varphi}(x) \vee \mathop\wedge\limits_{x \in \Delta} \overline{\psi^{\ast}}(x)] $$

    从而有以下3种特殊的情形:

    1)如果有$x_0 \in \Delta$, 使得$ \overline{\psi^{\ast}}(x) \vee (1-\overline{\psi}(x)) = 0 $, 则$\forall y \in \Sigma$, $ \overline{\varphi^{\ast}}(x) = 0 $.

    2)如果对任何$x \in \Delta$, 有$ \overline{\psi^{\ast}}(y) = 1 $, 则$\forall y \in \Sigma$, $ \overline{\varphi^{\ast}}(x) = 1 $.

    3)如果有$x_0 \in \Delta$, 使得$ \overline{\psi^{\ast}}(y) = 0 $, 且$||\psi|| \subseteq ||\psi^{\ast}||$, 则$\forall y \in \Sigma$, $ \overline{\varphi^{\ast}}(y) = \overline{\varphi}(y) $.

    对于如下多规则MT近似推理问题[17]:

    $$ \left\{ \begin{array}{ll} \text{已 知} \qquad\quad \varphi_1 \to \psi_1 \quad \\ \qquad \qquad \qquad \cdots \\ \qquad \qquad \quad \varphi_n \to \psi_n \quad \qquad \qquad \\ \underline{\text{且给定} \qquad \qquad \psi^{\ast} } \\ \text{求} \qquad\qquad \psi^{\ast} \end{array} \right. $$ (7)

    如果采用先推理后聚合的推理过程, 聚合算子取合取算子, 则其推理结论的属性公式函数为[17]:

    $$ \overline{\psi^{\ast}}(y) = \mathop\wedge^{n}\limits_{i = 1} \mathop\wedge\limits_{x \in \Delta} [(\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x)) \to \overline{\psi^{\ast}}(x)], y \in \Sigma $$ (8)

    为了方便展开决策蕴涵的逻辑推理, 本节利用属性逻辑的K-赋值, 对决策蕴涵进行属性逻辑的语义分析.

    定义 7[5]. 称形式背景$ K_1 = (G,C,I) $和$K_2 = (G,D,J)$的并置$ K = (G,C,D,I,J) $为决策形式背景, 并分别称$ C $和$ D $为条件属性集和决策属性集. 若$ A \subseteq C, B \subseteq D $, 且有$ ||\wedge_{a \in A} a|| \subseteq ||\wedge_{b \in B} b|| $, 称属性公式$ \wedge_{a \in A} a \to \wedge_{b \in B} b $为决策蕴涵, 称$ \wedge_{a \in A} a $为决策蕴涵前件(或前提), $ \wedge_{b \in B} b $为决策蕴涵后件(或结论). 如果$A, B$还分别是条件概念和决策概念的内涵属性集, 称决策蕴涵$ \wedge_{a \in A} a \to \wedge_{b \in B} b $为概念规则. 记决策形式背景$ K $的全体决策蕴涵之集为$ K_D $, 全体概念规则之集为$ K_C $.

    为了不引起混淆, 也经常简记$ ||\wedge_{a \in A} a|| $为$ ||A|| $, $ \wedge_{a \in A} a \to \wedge_{b \in B} b $为$ A \to B $.

    从形式上看, 文献[5-6]讨论的抽象集合上的决策蕴涵$ A \to B $是一个由逻辑联结词$ \to $将2个属性合取公式联结起来的属性公式. 但是, 由于数据分析讨论决策蕴涵时常常是在信息系统或决策形式背景上进行的, 而且还要将概念规则和粒规则纳入决策蕴涵的范畴来统一讨论, 因此基于决策形式背景上的决策蕴涵$ A \to B $比一般抽象属性集上的决策蕴涵多了一个限制条件$ ||\wedge_{a \in A} a|| \subseteq ||\wedge_{b \in B} b|| $[4, 10-11].

    定义8[5]. 设$ (G,C,D,I,J) $是决策形式背景.

    1)对于属性集$ T \subseteq C \cup D $和决策蕴涵$ A \to B $, 若$ A \varsubsetneq T \cap C $或$ B \subseteq T \cap D $, 称$ T $满足$ A \to B $ (或称$ T $是$ A \to B $的模型), 记为$ T \models A \to B $. 设$ L \subseteq K_D $, 若$ T $满足$ L $中的任意一个决策蕴涵, 称$ T $是$ L $的一个模型, 记为$ T \models L $.

    2)若对任意$ T \subseteq C \cup D $, $ T \models L $蕴涵$T \models A \to B$, 称$ A \to B $为$ L $的语义结论, 记为$L \models A \to B$.

    从逻辑观点看, 一个决策蕴涵是通过蕴涵联结词将条件属性合取公式和决策属性合取公式连接起来的属性逻辑公式, 定义8和语义结论等术语是命题逻辑中的相应术语在决策蕴涵中的本质特征刻画. 因此, 在引进属性逻辑语言后, 可以借用命题逻辑中的赋值方法对决策蕴涵、概念规则等进行讨论.

    利用前面引入的K-赋值, 以下给出决策蕴涵的K-语义结论定义.

    定义9. 设$ K = (G,C,D,I,J) $是决策形式背景, $ A \to B \in K_D $, $ L \subseteq K_D $, $ v $是K-赋值. 记$ v(L) = \wedge_{A_1 \to B_1 \in L} v(A_1 \to B_1) $, 如果对任何K-赋值$v \in \Omega_K$, 都有$ v(L) = 1 $蕴涵$ v(A \to B) = 1 $, 称$ A \to B $为 $ L $的K-语义结论, 记为$ L \models_K A \to B $.

    从逻辑语义角度看, 决策蕴涵集的语义结论是从全部模型$ L $的角度来讨论, 而K-语义结论只从形式背景对象集所决定的K-赋值来考虑. 之间的关系正是计量逻辑学中基于全部赋值和部分赋值推理的关系在决策蕴涵的具体体现[13, 24].

    命题4. 设$ K = (G,C,D,I,J) $是决策形式背景, $ A \to B \in K_D $.

    1)$ T \subseteq C \cup D $是$ A \to B $的模型当且仅当对赋值$v_T \in \Omega$, 有$ v_T (A \to B) = 1 $, $ v_T $是由$ T $决定的赋值.

    2)如果$v \in \Omega_K$, 使得$ v(A \to B) = 1 $, 则$ T_0 = \{m | m \in C \cup D, v(m) = 1\} $是$ A \to B $的模型.

    证明. 1)设$ T \subseteq C \cup D $是$ A \to B $的模型, $ v_T $是由$ T $所决定的赋值, 即$ T $中的原子属性公式赋值为1, $ C \cup D -T $中的原子属性公式赋值为0. 则当$ A \varsubsetneq T \cap C $时, 有$ a \in A $使$ v_T (a) = 0 $, 于是$v_T (A \to B) = v_T (A) \to v_T (B) = 1$. 而当$ B \subseteq T \cap D $时, 对任何$ b \in B $有$ v_T (b) = 1 $, 此时同样有$v_T (A \to B) = v_T (A) \to v_T (B) = 1$. 因此总有$ v_T (A \to B) = 1 $.

    反之, 假设$ T $不是$ A \to B $的模型. 若令 $T = \{m | m \in C \cup D, v(m) = 1\}$, 则可断定 $ T $是$ A \to B $的模型, 即$ A \varsubsetneq T \cap C $或$ B \subseteq T \cap D $. 否则, 如果$A \subseteq T \cap C$且$ B \varsubsetneq T \cap D $, 则有$ v_T (A) = 1 $且$ v_T (B) = 0 $, 从而$ v_T (A \to B) = 0 $. 与已知矛盾.

    2)如果$ T_0 $不是$ A \to B $的模型, 则$ A \subseteq T_0 \cap C $且$ B \varsubsetneq T \cap D $. 从而$ \forall a \in A, a \in T_0 \cap C $, 且$\exists b \in B, b \notin T_0 \cap D$, 于是$ v(A) = 1, v(B) = 0 $. 因此$v(A \to B) = 0$, 与已知$ v(A \to B) = 1 $矛盾. 所以$ T_0 $是$ A \to B $的模型.

    由命题4的1)可知, $ T $是$ L \subseteq K_D $的模型当且仅当对任何的$ A_1 \to B_1 \in K_D $, 有$ v_T (A_1 \to B_1) = 1 $. $L \models A \to B$当且仅当如果对任何的$ A_1 \to B_1 $和$ v \in \Omega $, 有$ v(A_1 \to B_1) = 1 $, 则一定也有$v(A \to B) = 1$. 由于K-赋值$ \Omega_K $只是全部模型$ T \subseteq C \cup D $所决定赋值集$ \Omega $的真子集, 因此如果$ L \models A \to B $, 则$ L \models_K A \to B $. 反之, 即使对任何K-赋值$ v \in \Omega_K $, 当对任何$ A_1 \to B_1 \in L $, $ v(A_1 \to B_1) = 1 $时, 都有$ v(A \in B) = 1 $, 也不一定能断定$ L \models A \to B $. 因此, 命题4的2)只能用来判定$ A \to B $不是$ L $的语义结论. 即如果有$ K $-赋值$ v_0 \in \Omega_K $, 使得$ \forall A_1 \to B_1 \in L $, $v_0(A_1 \to B_1) = 1$, 但$ v_0(A \to B) = 0 $, 这时就可以断言$ A \to B $不是$ L $的语义结论. 本文例2也说明了这一点.

    例2. 一个决策形式背景$ K = (G,C,D,I,J) $见表2, 对象集$ G = \{u_1, u_2, u_3, u_4\} $, 条件属性集$ C = \{a_1, a_2, a_3, a_4\} $, 决策属性集$ D = \{d_1, d_2, d_3\} $.

    表 2  决策形式背景$K=(G,C,D,I,J)$
    Table 2  A formal decision context $K=(G,C,D,I,J)$
    $G$$a_1$$a_2$$a_3$$a_4$$d_1$$d_2$$d_3$
    $u_1$1111101
    $u_2$0010010
    $u_3$1000011
    $u_4$0110100
    下载: 导出CSV 
    | 显示表格

    $ L = \{a_1 \wedge a_2 \wedge a_3 \to d_1 \wedge d_3\} $, 显然对任何K-赋值$ v \in \Omega_K $, 当$ v(a_1 \wedge a_2 \wedge a_3 \to d_1 \wedge d_3) = 1 $时, 有$ v(a_1 \wedge a_2 \to d_1 \wedge d_3) = 1 $, 即$L \models_{K} a_1 \wedge a_2 \to d_1 \wedge d_3$. 若取$ T = \{a_1, a_2, a_4, d_1, d_2\} $, 显然有$v_{T} (a_1 \wedge a_2 \;\wedge a_3 \to d_1 \wedge d_3) = 1$的模型, 但$ T $却不是$a_1 \wedge a_2 \to d_1\; \wedge d_3$的模型, 于是$ a_1 \wedge a_2 \to d_1 \wedge d_3 $不是$ L $的语义结论.

    命题5. 设$ K = (G,C,D,I,J) $是决策形式背景. 对$ A \subseteq C, B \subseteq D $, 有:

    1) $ A \to \alpha^{J} (\beta^{I}(A)) $是决策蕴涵;

    2) $ A \to B $是决策蕴涵当且仅当$B \subseteq \alpha^{J} (\beta^{I}(A))$.

    证明. 1)显然有$ \alpha^{J} (\beta^{I}(A)) \subseteq D $, 且$||A|| = \beta^{I}(A) \subseteq \beta^{I} (\alpha^{J} (\beta^{I}(A))) = ||\alpha^{J} (\beta^{I}(A))||.$ 所以 $ A \to \alpha^{J} (\beta^{I}(A)) $是决策蕴涵.

    2)若$ A \to B $是决策蕴涵, 则 $||A|| = \beta^{I}(A) \subseteq ||B|| = \beta^{J}(B)$. 因此$ B \subseteq \alpha^{J} (\beta^{J}(B)) \subseteq \alpha^{J} (\beta^{I}(A)) $.

    反之, 如果$ B \subseteq \alpha^{J} (\beta^{I}(A)) $, 则$||A|| = \beta^{I}(A) \subseteq \beta^{J} (\alpha^{J} (\beta^{I}(A))) \subseteq \beta^{J}(B) = ||B||.$ 所以 $ A \to B $是决策蕴涵.

    命题6. 设$ K = (G,C,D,I,J) $是决策形式背景, $ A \to B \in K_D $, $ L \subseteq K_D $. 则$ A \to B $不是$ L $的K-语义结论当且仅当存在$ d \in B $使得$ A \to d $不是$ L $的K-语义结论.

    证明. 如果$ A \to B $不是$ L $的K-语义结论, 则存在K-赋值$ v_0 \in \Omega_K $, 虽然$ \forall A_1 \to B_1 \in L $, $ v_0(A_1 \to B_1) = 1 $, 但$ v_0(A \to B) = 0 $, 即$ v_0(A) > v_0(B) $. 于是存在$ d \in B $, 使得$ v_0(A) = 1 $, 而$ v_0(d) = 0 $. 所以$ A \to d $不是$ L $的K-语义结论.

    反之, 若存在$ d \in B $使得$ A \to d $不是$ L $的K-语义结论, 则有K-赋值$ v_0 \in \Omega_K $, 使得$ \forall A_1 \to B_1 \in L $, $ v_0(A_1 \to B_1) = 1 $, 但$ v_0(A \to d) = 0 $意味着$ v_0(A) = 1 $, $ v_0(d) = 0 $. 于是$ v_0(A) = 1 > 0 = v_0(d) \geq v_0(B) $, 即$ v_0(A \to d) = 0 $. 所以$ A \to B $不是$ L $的K-语义结论.

    第1节给出的形式背景上的广义MP、广义MT的前提和结论所涉及的公式是一般的属性公式, 且通常是在给定的对象范围内$( \Sigma, \Delta)$探讨推理规则的解. 由于本文是在决策形式背景上来讨论决策蕴涵推理, 而决策蕴涵中的前件和后件分别是条件原子属性公式和决策原子属性合取公式, 且通常是通过全部的对象集合之间的包含关系来反映. 因此, 本节在分析决策蕴涵的MP近似推理、MT近似推理的特征时, 推理的对象范围参数$( \Sigma, \Delta)$是全部对象集$ G $.

    本节讨论决策形式背景上基于广义MP的决策蕴涵的近似推理 (以下简称决策蕴涵的MP近似推理)的特征.

    定理3. 设$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$是决策形式背景$ K = (G,C,D,I,J) $的决策蕴涵集, $ \varphi^{\ast} $是条件属性合取公式, $ f $是由$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$和$ \varphi^{\ast} $的MP近似推理得到的解函数:

    $$ f(x) =\mathop \wedge^{n}\limits_{i = 1} \mathop\vee\limits_{y \in G} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], x \in G $$

    如果记$ W = \{x \in G | f(x) = 1\} $, $\alpha^{J}(W) = \{d \in D | \forall x \in W, xJd\}$. 当$ \alpha^{J}(W) $非空时, 令$ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $, 则$ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵.

    证明. 如果$ ||\varphi^{\ast}|| $是空集, $ \varphi^{\ast} \to \psi^{\ast} $当然是决策蕴涵. 因此, 不妨设$ ||\varphi^{\ast}|| $非空, 并设$ x_0 \in ||\varphi^{\ast}|| $, 有$ \overline{\varphi^{\ast}} (x_0) = 1 $. 设:

    $$ f_i (x) = \mathop\vee\limits_{y \in G} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], i = 1, \cdots, n $$

    根据注1, 在$ \overline{\varphi^{\ast}} (x_0) = 1 $的条件下, 只有当$ ||\varphi^{\ast}|| \subseteq ||\varphi_{i}|| $时, 才有$ f_i (x) = \overline{\psi}_{i} (x) $; 否则, $ f_i (x) $恒等于1. 不妨设在决策蕴涵集$ L $的前件属性公式集$\{\varphi_{1}, \cdots, \varphi_{n}\}$中有$ i_k $个属性公式$\varphi_{i_1}, \cdots, \varphi_{i_k}$满足条件$ ||\varphi^{\ast}|| \subseteq ||\varphi_{i_1}||, \cdots $, $ ||\varphi^{\ast}|| \subseteq ||\varphi_{i_k}|| $. 从而:

    $$ f(x) = \mathop\wedge^{n}\limits_{i = 1} f_{i} (x) = \overline{\psi}_{i_1}(x) \wedge \cdots \wedge \overline{\psi}_{i_k}(x), x \in G $$

    如果记$ W = \{x \in G | f(x) = 1\} $, $\alpha^{J}(W) = \{d \in D | \forall x \in W, xJd\}$, 当$ \alpha^{J}(W) $非空时, 令$ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $,则对$ x \in G $:

    $$ \overline{\psi^{\ast}} (x) = \mathop\wedge\limits_{d \in \alpha^{J}(W)} \overline{d}(x) \geq f(x) = \overline{\psi}_{i_1}(x) \wedge \cdots \wedge \overline{\psi}_{i_k}(x) $$

    上式说明, 当$ \overline{\varphi^{\ast}} (x_0) = 1 $时, 有$\overline{\varphi}_{i_1} (x_0) = 1, \cdots$, $\overline{\varphi}_{i_k} (x_0) = 1$. 又由于$ \varphi_{i_1} \to \psi_{i_1}, \cdots $, $ \varphi_{i_k} \to \psi_{i_k} $是决策蕴涵, 故有$ ||\varphi_{i_1}|| \subseteq ||\psi_{i_1}||, \cdots $, $ ||\varphi_{i_k}|| \subseteq ||\psi_{i_k}|| $. 从而$ \overline{\psi}_{i_1} (x_0) = 1, \cdots $, $ \overline{\psi}_{i_k} (x_0) = 1 $. 因此:

    $$ \overline{\psi^{\ast}} (x_0) \geq f(x_0) = \overline{\psi}_{i_1}(x_0) \wedge \cdots \wedge \overline{\psi}_{i_k}(x_0) = 1 $$

    即$ ||\varphi^{\ast}|| \subseteq ||\psi^{\ast}|| $. 所以$ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵.

    下面探讨基于现有决策蕴涵经过MP近似推理生成新的决策蕴涵的模式1.

      模式1. 决策蕴涵的MP近似推理生成模式

    前提. 决策蕴涵集$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$, 条件属性合取公式$\varphi^{\ast}$.

    结论. 决策蕴涵$ \varphi^{\ast} \to \psi^{\ast} $.

    1)计算属性公式函数$\overline{\varphi^{\ast}}, \overline{\varphi}_{i}, \overline{\psi}_{i}, i = 1, \cdots, n .$

    2)计算MP近似推理解函数:

    $$ f(x) = \mathop\wedge^{n}\limits_{i = 1}\mathop \vee\limits_{y \in G} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], x \in G $$

    3) 计算$ W = \{x \in G | f(x) = 1\} $, $\alpha^{J}(W) = \{d \in D | \forall x \in W, xJd\}.$

    4)生成决策蕴涵$ \varphi^{\ast} \to \wedge_{d \in \alpha^{J}(W)} d $.

    5)对任何$ B \subseteq \alpha^{J}(W) $, 生成决策蕴涵$ \varphi^{\ast} \to \wedge_{d \in B} d $.

    例3. 一个决策形式背景$ K = (G,C,D,I,J) $见表3, 对象集$G = \{u_1, u_2, u_3, u_4, u_5, u_6, u_7\}$, 条件属性集$ C = \{a_1, a_2, a_3, a_4, a_5, a_6\} $, 决策属性集$ D = \{d_1, d_2, d_3\} $.

    表 3  决策形式背景$K=(G,C,D,I,J)$
    Table 3  A formal decision context $K=(G,C,D,I,J)$
    $G$$a_1$$a_2$$a_3$$a_4$$a_5$$a_6$$d_1$$d_2$$d_3$
    $u_1$110011101
    $u_2$001111110
    $u_3$101001001
    $u_4$010101100
    $u_5$010111110
    $u_6$101011011
    $u_7$011100111
    下载: 导出CSV 
    | 显示表格

    给定2个决策蕴涵$ a_1 \wedge a_2 \to d_1 \wedge d_3 $, $a_1 \wedge a_6 \to d_3$和条件属性公式$ a_1 \wedge a_2 \wedge a_6 $, 根据决策蕴涵生成模式1, MP近似推理得到如下非平凡决策蕴涵$ a_1 \wedge a_2 \wedge a_6 \to d_1 \wedge d_3 $, $ a_1 \wedge a_2 \wedge a_6 \to d_1 $, $a_1 \wedge a_2\; \wedge a_6 \to d_3$.

    按照决策蕴涵的定义, 对于由原子属性公式构成的蕴涵公式, 当$ ||\varphi|| $是空集时, $ \varphi \to \psi $一定是决策蕴涵, 但这类决策蕴涵在实际知识获取中作用不是很大, 且极大地增大了决策蕴涵的个数. 因此, 决策蕴涵的MP近似推理生成模式1没有考虑生成这类平凡的决策蕴涵. 定理3和决策蕴涵生成模式1给出的决策蕴涵的MP近似推理是基于广义MP的, 是从逻辑角度来考虑的. 注意到, 广义MP的小前提是条件属性公式, 大前提是决策蕴涵, 而决策蕴涵的前件和后件分别是由条件属性和决策属性的合取构成的属性公式. 从知识发现的角度看, 属性合取公式本质上描述了知识的内涵, 因此决策蕴涵的MP近似推理的实质是一种从条件形式背景上的知识来获取决策形式背景上的知识的知识推理方法. 如果将条件属性理解为原因, 决策属性理解为结果, 则决策蕴涵的MP近似推理遵循的是一种“由因及果”的知识推理模式.

    当$ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵时, 对任何由$ \psi^{\ast} $中部分原子属性公式组成的合取公式$ \gamma $, $ \varphi^{\ast} \to \gamma $都是决策蕴涵. 显然$ \varphi^{\ast} \to \wedge_{d \in \alpha^{J}(||\varphi^{\ast}||))} d $是决策蕴涵且含有最多的决策属性. 由定理3的证明过程可知, $ f(x) $和$ \varphi^{\ast} (x) $不一定总相等, 从而$ \alpha^{J}(W) $和$ \alpha^{J}(||\varphi^{\ast}||) $不一定相同. 因此, 对给定的$ \varphi^{\ast} $, 通过MP近似推理得到的决策蕴涵$ \varphi^{\ast} \to \wedge_{d \in \alpha^{J}(W)} d $不一定就是决策蕴涵$\varphi^{\ast} \to \wedge_{d \in \alpha^{J}(||\varphi^{\ast}||)} d$. 这是因为由MP近似推理得到的决策蕴涵$\varphi^{\ast} \to \wedge_{d \in \alpha^{J}(W)} d$还受到了大前提 $ \varphi^{\ast} \to \gamma $的约束. 定理3的证明过程表明了$\varphi^{\ast} \;\to \wedge_{d \in \alpha^{J}(W)} d$是得到给定前提$ \varphi^{\ast} $和$\{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$最大支持的含有最多决策属性的决策蕴涵.

    定理4. 在定理3条件下, 有$\{\varphi_{1} \to \psi_{1}, \cdots, \varphi_{n} \to \psi_{n}\} \models_{K} \varphi^{\ast} \to \psi^{\ast}$.

    证明. 由定理3可知, $ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵. 由于$ G $ ~ $ \Omega_K $间存在一一对应$\pi: G \to \Omega_K$, $ \pi(x) = v_x $. 对$ x \in G $决定的$v_x \in \Omega_K$, 如果$v_x (\varphi_{1} \to \psi_{1}) = 1, \cdots, v_x (\varphi_{n} \to \psi_{n}) = 1$, 则$v_x (\varphi_{1}) \leq v_x (\psi_{1}), \cdots, v_x (\varphi_{n}) \leq v_x (\psi_{n})$. 即$\overline{\varphi}_{1}(x) \leq \overline{\psi}_{1}(x), \cdots, \overline{\varphi}_{n}(x) \leq \overline{\psi}_{n}(x)$. 因此:

    $$ \begin{split} f(x) =\;& \mathop\wedge^{n}\limits_{i = 1} \mathop\vee\limits_{y \in G} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))] \;\geq \\ & \mathop\wedge^{n}\limits_{i = 1} [\overline{\varphi^{\ast}}(x) \wedge (\overline{\varphi}_{i}(x) \to \overline{\psi}_{i}(x))] \end{split}$$

    $ \forall x \in G $, 如果记$ W = \{x \in G | f(x) = 1\} $, $\alpha^{J}(W) = \{d \in D | \forall x \in W, xJd\}$, $ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $. 则$ \overline{\psi^{\ast}}(x) = \wedge_{d \in \alpha^{J}(W)} \overline{d}(x) \geq f(x) \geq \overline{\varphi^{\ast}}(x) $. 从而对任何$v_x \in \Omega_K$, $ v_x (\varphi^{\ast}) \leq v_x (\psi^{\ast}) $, $ v_x(\varphi^{\ast} \to \psi^{\ast}) = 1 $. 所以$\{\varphi_{1} \;\to \psi_{1}, \cdots, \varphi_{n} \to \psi_{n}\} \models_{K} \varphi^{\ast} \to \psi^{\ast}$.

    定义10. 对于给定的属性公式$\varphi_{1}, \cdots, \varphi_{k}$, 称属性公式集$\varphi_{1}, \cdots, \varphi_{k}$不相容是指$ \forall x \in G $, $\overline{\varphi}_{1} (x) \;\wedge \cdots \wedge \overline{\varphi}_{k} (x) = 0$; 否则, 称为相容.

    命题7. 设$ \varphi \to \psi $是决策形式背景$K = (G, C, D,I,J)$的决策蕴涵, $ \varphi^{\ast} $是与$ \varphi $不相容的条件属性公式, 则由$ \varphi \to \psi $和$ \varphi^{\ast} $经过MP近似推理可以得到前件为$ \varphi^{\ast} $的全部决策蕴涵.

    证明. $ \varphi \to \psi $和$ \varphi^{\ast} $的MP近似推理的解函数为:

    $$ f(x) =\mathop \vee\limits_{y \in G} [\overline{\varphi^{\ast}}(y) \wedge (1-\overline{\varphi}(y))] \vee [\overline{\psi}(x) \wedge\mathop \vee\limits_{y \in G} \overline{\varphi^{\ast}}(y)] $$

    由于$ \varphi^{\ast} $与$ \varphi $不相容, 故$ \forall x \in G $, $\overline{\varphi^{\ast}} (x) \wedge \overline{\varphi} (x) = 0$. 于是$ \forall x \in G $, $ f(x) = 1 $. 由定理3的证明可知, 对任何$ W \subseteq G = \{x \in G | f(x) = 1\} $, $ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $, $ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵.

    命题7表明, 一个与决策蕴涵前提不相容的条件属性公式$ \varphi^{\ast} $, 与决策蕴涵一起可以MP近似推理得出前提为$ \varphi^{\ast} $的全部决策蕴涵.

    命题8. 在定理3的条件下, 有$\{\varphi_{1} \to \psi_{1}, \varphi_{2} \;\to \psi_{2}\} \models_K \varphi_{1} \wedge \varphi_{2} \to \psi_{1} \wedge \psi_{2}$.

    证明. 由定理3, $\{\varphi_{1} \to \psi_{1}, \varphi_{2} \to \psi_{2}\} \models_K \varphi_{1} \;\wedge \varphi_{2} \to \psi^{\ast}$, $ \psi^{\ast} $是由$ \{\varphi_{1} \to \psi_{1}, \varphi_{2} \to \psi_{2}\} $和 $\varphi_{1} \wedge \varphi_{2}$的MP近似推理的结论. 因此:

    $$ \begin{split} f(x) =\;& \mathop\wedge^{2}_{i = 1} \mathop\vee\limits_{y \in G} [\overline{\varphi_{1} \wedge \varphi_{2}} (y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))] \;= \\ & \overline{\psi}_{1} (x) \wedge \overline{\psi}_{2} (x) \end{split}$$

    $ W = \{x \in G | \overline{\psi}_{1} (x) \wedge \overline{\psi}_{2} (x) = 1\} $, 又由于$\alpha^{J}(W) \;= \{d \in D | \forall x \in W, xJd\}$, 故结论$ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $包含$ \psi_{1} \wedge \psi_{2} $的全部原子属性公式. 所以$ \{\varphi_{1} \to \psi_{1} $, $ \varphi_{2} \to \psi_{2}\} \models_K \varphi_{1} \wedge \varphi_{2} \to \psi_{1} \wedge \psi_{2} $.

    定理5. 设$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$是决策形式背景$ K = (G,C,D,I,J) $的概念规则集, $ \varphi^{\ast} $是条件概念的内涵属性公式, $ f $是由$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$和$ \varphi^{\ast} $的MP近似推理得到的解函数:

    $$ f(x) = \mathop\wedge^{n}\limits_{i = 1} \mathop\vee\limits_{y \in G} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], x \in G $$

    若记$ W = \{x \in G | f(x) = 1\} $, $\alpha^{J}(W) = \{d \in D | \forall x \in W, xJd\}$. 当$ \alpha^{J}(W) $非空时, 令$ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $, 则$ \varphi^{\ast} \to \psi^{\ast} $是概念规则.

    证明. 由定理3可知, $ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵. 显然有$ (||\psi^{\ast}||, \alpha^{J}(W)) $是决策概念, 即$ \psi^{\ast} $是决策概念的内涵属性公式. 与定理3的证明类似, 可以证明$ ||\varphi^{\ast}|| \subseteq ||\psi^{\ast}|| $, $ \varphi^{\ast} \to \psi^{\ast} $是概念规则.

    由定理5, 在基于MP近似推理的决策蕴涵生成模式中, 用概念规则代替决策蕴涵, 条件概念属性公式代替条件属性公式, 可以得到相应的基于MP近似推理的概念规则生成方法.

    例4 (续例3). $ a_2 \wedge a_4 \to d_1 $, $ a_3 \wedge a_4 \to d_2 $是两条概念规则, $a_2 \wedge a_3 \wedge a_4$是条件概念内涵属性公式, 利用决策蕴涵生成模式1, 得到概念规则: $a_2 \;\wedge a_3 \wedge a_4 \to d_1$, $a_2 \wedge a_3 \wedge a_4 \to d_2$, $ a_2 \wedge a_3 \wedge a_4 \to d_3 $, $ a_2 \wedge a_3 \wedge a_4 \to d_1 \wedge d_2 $, $a_2 \wedge a_3 \wedge a_4 \to d_2 \wedge d_3$, $a_2 \;\wedge a_3 \wedge a_4 \to d_1 \wedge d_3$, $ a_2 \wedge a_3 \wedge a_4 \to d_1 \wedge d_2 \wedge d_3 $.

    以上结论表明, 本文给出的MP近似推理方法是一种保持决策蕴涵和概念规则不变的推理模式, 即决策蕴涵和概念规则集在MP近似推理模式下是封闭的.

    本节讨论决策形式背景上基于广义MT的近似推理(以下简称MT近似推理)的特征.

    定理6. 设$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$是决策形式背景$ K = (G,C,D,I,J) $的决策蕴涵集, $ \psi^{\ast} $是决策属性合取公式, 由$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$和$ \psi^{\ast} $的MT近似推理得到的解函数为:

    $$ g(y) = \mathop\wedge^{n}\limits_{i = 1}\mathop \wedge\limits_{x \in G} [(\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x)) \to \overline{\varphi^{\ast}}(x)], y \in G $$

    若记$ V = \{y \in G | g(y) = 1\} $, $\alpha^{I}(V) = \{c \in C | \forall y \in V, yIc\}$. 当$ \alpha^{I}(V) $非空时, 令$ \varphi^{\ast} = \wedge_{c \in \alpha^{I}(V)} c $, 则$ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵.

    证明. 设$ y_0 \notin ||\psi^{\ast}|| $, 即$ \psi^{\ast} (y_0) = 0 $. 如果记:

    $$ \begin{split} g_i (y) = \;&\mathop\wedge\limits_{x \in G} [(\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x)) \to \wedge \overline{\varphi^{\ast}}(x)],\\ & i = 1, \cdots, n \end{split}$$

    由注2, 在$ \psi^{\ast} (y_0) = 0 $的条件下, 只有满足$||\psi_{i}|| \subseteq ||\psi^{\ast}||$时, 才会有$ g_i (y) = \overline{\varphi}_{i}(y) $; 否则, $ g_i (y) $在$ G $上恒为0. 不妨设决策蕴涵集$ L $的后件属性公式集$\{\psi_{1}, \cdots, \psi_{n}\}$中有$ i_l $个属性公式$\psi_{i_1}, \cdots, \psi_{i_l}$满足条件$||\psi_{1}|| \subseteq ||\psi^{\ast}||, \cdots,$ $ ||\psi_{l}|| \subseteq ||\psi^{\ast}|| $. 从而有:

    $$ g(y) = \mathop\wedge^{n}\limits_{i = 1} g_{i} (y) = \overline{\varphi}_{i_1}(y) \wedge \cdots \wedge \overline{\varphi}_{i_l}(y), y \in G $$

    记$ V = \{y \in G | g(y) = 1\} $, $\alpha^{I}(V) = \{c \in C | \forall y \in V, yIc\}$. 当$ \alpha^{I}(V) $非空时, 令$ \varphi^{\ast} = \wedge_{c \in \alpha^{I}(V)} c $, 注意到都是原子属性公式的合取, 于是有:

    $$ \overline{\psi^{\ast}} (y) =\mathop \wedge\limits_{c \in \alpha^{I}(V)} \overline{c}(y) = g(y) = \overline{\varphi}_{i_1}(y) \wedge \cdots \wedge \overline{\varphi}_{i_l}(y) $$

    $ \forall y \in G $. 由于$\varphi_{i_1} \to \psi_{i_1}, \cdots,$ $ \varphi_{i_l} \to \psi_{i_l} $是决策蕴涵, 故有$||\varphi_{i_1}|| \subseteq ||\psi_{i_1}||, \cdots ,$ $ ||\varphi_{i_l}|| \subseteq ||\psi_{i_l}|| $. 又由$ \overline{\psi^{\ast}} (y_0) = 0 $, 知$ \overline{\psi}_{1} (y_0) = 0, \cdots $, $ \overline{\psi}_{l} (y_0) = 0 $, 从而$\overline{\varphi}_{1} (y_0) = 0, \cdots ,$ $ \overline{\varphi}_{l} (y_0) = 0 $. 故$\overline{\psi^{\ast}} (y_0) = \overline{\varphi}_{i_1}(y_0) \wedge \cdots \wedge \;\overline{\varphi}_{i_l}(y_0) = 0$, 即$ y_0 \notin ||\varphi^{\ast}|| $. 因此$ ||\varphi^{\ast}|| \subseteq ||\psi^{\ast}|| $. 所以$ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵.

    定理6给出的决策蕴涵的MT近似推理是基于广义MT的. 从知识发现的思维过程看, 广义MT有着与MP相反的思维模式. 因此, 决策蕴涵的MT近似推理本质上应属于“由果溯因”的知识推理模式.

    命题9. 在定理6的条件下, 有$\{\varphi_{1} \to \psi_{1}, \cdots ,$ $ \varphi_{n} \to \psi_{n}\} \models_{K} \varphi^{\ast} \to \psi^{\ast} $.

    证明. 由定理6知$ \varphi^{\ast} \to \psi^{\ast} $是决策蕴涵. 由于$ G $和$\Omega_K$之间有一一对应$\pi: G \to \Omega_K$, $ \pi(y) = v_y $. 对$ y \in G $决定的$v_y \in \Omega_K$, 如果$v_y (\varphi_{1} \to \psi_{1}) = 1, \cdots, v_y (\varphi_{n} \to \psi_{n}) = 1$, 则$v_y (\varphi_{1}) \leq v_y(\psi_{1}), \cdots, v_y (\varphi_{n}) \leq v_y(\psi_{n})$. 即$\overline{\varphi}_{1}(y) \leq \overline{\psi}_{1}(y), \cdots, \overline{\varphi}_{n}(y) \leq \overline{\psi}_{n}(y)$. 因此:

    $$ \begin{split} g(y) = \;&\mathop\wedge^{n}\limits_{i = 1} \mathop\wedge\limits_{x \in G} [(\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x)) \to \overline{\varphi^{\ast}}(x)]\; \leq \\ &\mathop \wedge^{n}\limits_{i = 1} [(\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(y)) \to \overline{\varphi^{\ast}}(y)] = \overline{\psi^{\ast}}(y) \end{split}$$

    $ \forall y \in G $, $ V = \{y \in G | g(y) = 1\} $, $\alpha^{I}(V) = \{c \in C | \forall y \in V, yIc\}$, $ \varphi^{\ast} = \wedge_{c \in \alpha^{I}(V)} c $, 于是$\overline{\psi^{\ast}}(y) \geq g(y) = \wedge_{c \in \alpha^{I}(V)} \overline{c}(y) = \overline{\varphi^{\ast}}(y)$. 故$\forall v_y \in \Omega_K$, $ v_y (\varphi^{\ast}) \leq v_y (\psi^{\ast}) $, $ v_y (\varphi^{\ast} \to \psi^{\ast}) = 1 $. 所以$\{\varphi_{1} \to \psi_{1}, \cdots, \varphi_{n} \to\psi_{n}\} \models_{K}$ $ \varphi^{\ast} \to \psi^{\ast}$.

    定理7. 设$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$是决策形式背景$ K = (G,C,D,I,J) $的概念规则集, $ \psi^{\ast} $是决策概念内涵属性合取公式, $ g $是由$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$和$ \psi^{\ast} $的MT近似推理得到的解函数:

    $$ g(y) = \mathop\wedge^{n}\limits_{i = 1}\mathop \wedge\limits_{x \in G} [(\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x)) \to \overline{\varphi^{\ast}}(x)], y \in G $$

    若记$ V = \{y \in G | g(y) = 1\} $, $\alpha^{I}(V) = \{c \in C | \forall y \in V, yIc\}$. 当$ \alpha^{I}(V) $非空时, 令$ \varphi^{\ast} = \wedge_{c \in \alpha^{I}(V)} c $, 则$ \varphi^{\ast} \to \psi^{\ast} $是概念规则.

    证明. 显然有$ (||\varphi^{\ast}||, \alpha^{I}(V)) $是条件概念, 即$ \varphi^{\ast} $是条件概念的内涵属性公式. 与定理6的证明类似, 可证明$ ||\varphi^{\ast}|| \subseteq ||\psi^{\ast}|| $, $ \varphi^{\ast} \to \psi^{\ast} $是概念规则.

    由定理5和定理7可知, 决策蕴涵和概念规则集在MT近似推理模式下也是封闭的.

    应用定理6的结论, 可以得到下述基于MT近似推理的决策蕴涵和概念规则生成模式2.

      模式2. 决策蕴涵的MT近似推理生成模式

    前提. 决策蕴涵集$L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$, 决策属性合取公式$ \psi^{\ast} $.

    结论. 决策蕴涵$ \varphi^{\ast} \to \psi^{\ast} $.

    1)计算属性公式函数$\overline{\psi^{\ast}}, \overline{\varphi}_{i}, \overline{\psi}_{i}, i = 1, \cdots, n$;

    2)计算MT近似推理解函数:

    $$ g(y) = \mathop\wedge^{n}\limits_{i = 1}\mathop \wedge\limits_{x \in G} [(\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x)) \to \overline{\varphi^{\ast}}(x)], y \in G . $$

    3)计算$ V \;=\; \{y \in G | g(y) = 1\} $, $\alpha^{I}(V) = \{c \in C | \forall y \in V, yIc\}$;

    4)生成决策蕴涵$ \wedge_{c \in \alpha^{I}(V)} c \to \psi^{\ast} $;

    5)对任何$ A \supseteq \alpha^{I}(A) $, 生成决策蕴涵$\wedge_{c \in A} c \to \psi^{\ast}$.

    由定理7, 在基于MT近似推理的决策蕴涵生成模式中, 用概念规则代替决策蕴涵, 决策概念内涵属性公式代替决策属性公式, 可以得到相应的基于MT近似推理的概念规则生成方法.

    例5 (续例3). 对于给定的2条概念规则$(a_2 \;\wedge a_4 \wedge a_5 \wedge a_6 \to d_1 \wedge d_2$, $a_1 \wedge a_3 \wedge a_5 \wedge a_6 \to d_1 \wedge d_3)$和决策概念内涵属性公式$ d_2 $, 利用决策蕴涵生成模式2, 经过MT近似推理得到概念规则$a_1 \wedge a_2 \;\wedge a_3 \wedge a_4 \wedge a_5 \wedge a_6 \to d_2$.

    第3节分析了决策形式背景全体对象集上的决策蕴涵的MP、MT近似推理的特征, 给出了利用MP、MT近似推理生成决策蕴涵的方法. 在人工智能环境下, 在应用MP、MT近似推理进行知识获取时, 经常需要基于部分数据集上的现有决策蕴涵经过MP、MT近似推理动态地挖掘更大数据集上的决策蕴涵, 即遇到更多的是数据对象动态变化时的决策蕴涵挖掘. 另一方面, 利用少量的决策蕴涵借助MP、MT近似推理模式产生更多的决策蕴涵, 这正是知识推理的目的. 如何评价近似推理的好坏, 即如何评价近似推理结论的有效性, 目前还没有见到公认的标准. 本节引入属性逻辑伪距离, 对MP、MT近似推理结论的有效性进行刻画, 进而提出基础数据对象集动态变化时应用MP、MT近似推理来获取决策蕴涵的算法.

    例6 (续例3). 给定决策蕴涵$a_1 \wedge a_2 \to d_1 \wedge d_3$、 $ a_1 \wedge a_6 \to d_3 $和条件属性公式$ a_2 \wedge a_6 $.

    如果近似推理的基础数据对象集是整个对象集, MP近似推理得到的解函数为$ f(x) = 1, x \in G $, 这时MP近似推理的结论是空集. 如果推理范围限定为${ \Sigma} = \{u_1, u_2, u_3, u_6, u_7\}$, MP近似推理得到的解函数为$ f(x) = \overline{d_1 \wedge \ d_3}(x), x \in G $, 从而可得属性公式$ a_2 \wedge a_6 \to d_1 \wedge d_3 $. 注意到, 在整个对象集$ G $上, 它不是决策蕴涵, 但如果限定在对象集$ \Sigma $上, 则它是决策蕴涵. 本文称限定在部分对象集上是决策蕴涵的属性公式为拟决策蕴涵.

    定义11. 设$ K = (G,M,I) $是形式背景, 属性公式$ \varphi,\psi \in \Gamma (K) $, ${ \Sigma} \subseteq G$. 定义$ \varphi $在${ \Sigma}$上的真度为:

    $$ \tau_{ \Sigma} (\varphi) = \int_{ \Sigma} \overline{\varphi} (x) \text{d} P $$

    式中, $ P $是$ G $上的概率测度. 属性公式$ \varphi,\psi $的${ \Sigma}\text{-} 伪$距离定义为:

    $$ \rho_{ \Sigma} (\varphi, \gamma) = 1- \tau_{ \Sigma} ((\varphi \to \psi) \wedge (\psi \to \varphi)) $$

    当$ P $是$ G $上的均匀概率测度 (计数测度) 时, 定义11中定义的真度可表示为:

    $$ \tau_{ \Sigma} (\varphi) = \frac{1}{m} \sum^{m}\limits_{i = 1} \overline{\varphi} (x_i) $$

    式中, $ m $为对象集${ \Sigma}$的元素个数.

    由于$ \varphi $是一些属性的合取, 按照决策逻辑思想, $ \overline{\varphi} (x) = 1 $意味着支持“$ x $支持$ \varphi $”, 即对象$ x $具有$ \varphi $中的全部属性, 因此真度$\tau_{ \Sigma}$可以被理解为一种“投票模型”. 由于在实际数据处理中形式背景通常是用表格表示的, 这时对象$ x $的概率$ P(x) $其实就是与$ x $有相同属性值的对象数与全体对象个数的比值, 而公式$ \varphi $的真度$\tau_{ \Sigma} (\varphi)$其实就是${ \Sigma}$上具有$ \varphi $中全部属性的对象的概率和. 当$ P $是$ G $上的计数测度时, $\tau_{ \Sigma} (\varphi)$是$\Sigma $上具有$ \varphi $中全部属性的对象个数与$\Sigma $中全体对象个数的比值.

    命题10. 设$ \varphi,\psi \in \Gamma (K) $, ${ \Sigma} \subseteq G$. 则:

    $$ \begin{split} \rho_{ \Sigma} (\varphi) =\;& \int_{ \Sigma} |\overline{\varphi} (x) - \overline{\psi} (x)| \text{d}P \;= \\ & \frac{1}{m} \sum^{m}\limits_{i = 1} |\overline{\varphi} (x_i) - \overline{\psi} (x_i)| \end{split} $$

    证明.

    $$ \begin{split} &\rho_{ \Sigma} (\varphi, \psi) = 1- \tau_{ \Sigma} ((\varphi \to \psi) \wedge (\psi \to \varphi))\; = \\ &\quad 1- \int_{ \Sigma} (\overline{\varphi \to \psi} (x) \wedge \overline{\psi \to \varphi} (x)) \text{d}P \;= \\ &\quad 1- \int_{ \Sigma} (\overline{\varphi} (x) \to \overline{\psi} (x) \wedge \overline{\psi} (x) \to \overline{\varphi} (x)) \text{d}P \;= \\ &\quad 1- \int_{ \Sigma} (1- \overline{\varphi} (x) + \overline{\psi} (x)) \;\wedge\\ &\quad (1- \overline{\psi} (x) + \overline{\varphi} (x)) \text{d}P \;= \\ &\quad\int_{ \Sigma} [1- (1- \overline{\varphi} (x) + \overline{\psi} (x)) \;\wedge \\ &\quad(1- \overline{\psi} (x) + \overline{\varphi} (x))] \text{d}P \;= \\ &\quad\int_{ \Sigma} |\overline{\varphi} (x) - \overline{\psi} (x)| \text{d}P \end{split} $$

    设$ F \subseteq \Gamma (K) $, ${ \Sigma} \subseteq G$, 称$ \gamma \in \Gamma (K) $是$ F $的$\Sigma$-语义结论是指$\Sigma$对所决定的任何赋值$v_x \in v_{ \Sigma}$, 如果$ v_x (F) = \wedge \{v_x (\varphi) | \varphi \in F\} = 1 $, 则有$ v_x (\gamma) = 1 $. $ F $的全体$\Sigma$-语义结论之集记为$D_{ \Sigma}(F)$.

    定义12. 设$ K = (G,M,I) $是形式背景, $ F \subseteq \Gamma (K) $, $ \varphi \in \Gamma (K) $, $\Sigma \subseteq G$, $ \varepsilon >0 $. 如果${\rm{div}}(F) = \text{inf} \{\rho_{ \Sigma}(\varphi, \gamma) | \gamma \in D_{ \Sigma}(F)\}$, 则称$ \varphi $为$ F $的误差小于$ \varepsilon $的结论, 记为$ \varphi \in D_{\varepsilon}(F) $.

    定理8. 设$ K = (G,M,I) $是形式背景, $ F \subseteq \Gamma (K) $, $ \varphi \in \Gamma (K) $, $\Sigma \subseteq G$, $ \varepsilon >0 $. 则$ \varphi \in D_{\varepsilon}(F) $当且仅当$\text{sup}\{\tau_{ \Sigma} (\gamma \to \varphi) | \gamma \in D_{ \Sigma}(F)\} > 1-\varepsilon$.

    证明. 设$ \varphi \in D_{\varepsilon}(F) $, 则存在属性公式$\gamma_{0} \in D_{ \Sigma}(F)$使得$\rho_{ \Sigma} (\varphi, \gamma_0) < \varepsilon$. 则:

    $$ \begin{split} \rho_{ \Sigma} (\varphi, \gamma_0) =\;& 1- \tau_{ \Sigma} ((\varphi \to \gamma_0) \wedge (\gamma_0 \to \varphi))\; \geq \\ &1- \tau_{ \Sigma} (\gamma_0 \to \varphi) \end{split}$$

    因此

    $$ \begin{split}&1-\text{sup}\{\tau_{ \Sigma} (\gamma \to \varphi) | \gamma \in D_{ \Sigma}(F)\}\; \leq \\ &\qquad 1-\tau_{ \Sigma} (\gamma_0 \to \varphi) | \gamma \in D_{ \Sigma}(F)< \varepsilon \end{split}$$

    所以, $\text{sup}\{\tau_{ \Sigma} (\gamma \to \varphi) | \gamma \in D_{ \Sigma}(F)\} > 1-\varepsilon$.

    反之, 如果$\text{sup}\{\tau_{ \Sigma} (\gamma \to \varphi) | \gamma \in D_{ \Sigma}(F)\} > 1-\varepsilon$, 则$\text{inf}\{1-\tau_{ \Sigma} (\gamma \to \varphi) | \gamma \in D_{ \Sigma}(F)\} < \varepsilon .$易证:

    $$ (\varphi \to \varphi \vee \gamma) \wedge (\varphi \vee \gamma \to \varphi) \approx \gamma \to \varphi $$

    则:

    $$ \begin{split} \rho_{ \Sigma} (\varphi, \varphi \vee \gamma) = \;&1- \tau_{ \Sigma} ((\varphi \to \varphi \vee \gamma) \wedge (\varphi \vee \gamma \to \varphi))= \\ & 1- \tau_{ \Sigma} (\gamma \to \varphi) \qquad \end{split}$$

    故$\text{inf} \{\rho_{ \Sigma}(\varphi, \varphi \vee \gamma) | \gamma \in D_{ \Sigma}(F)\} < \varepsilon$. 于是存在$\gamma \in D_{ \Sigma}(F)$使得$\rho_{ \Sigma}(\varphi, \varphi \vee \gamma) < \varepsilon$. 又由$\gamma \in D_{ \Sigma}(F)$有$\varphi \vee \gamma \in D_{ \Sigma}(F)$. 因此:

    $$ \text{inf} \{\rho_{ \Sigma}(\varphi, \gamma) | \gamma \in D_{ \Sigma}(F)\} \leq \rho_{ \Sigma}(\varphi, \varphi \vee \gamma)<\varepsilon $$

    所以, $ \varphi \in D_{\varepsilon}(F) $.

    定理9. 设${ \Sigma} \subset { \Delta} \subseteq G$, $ \psi^{\ast} $是$ \{\varphi_{i} \to \psi_{i} | $ $i = 1, \cdots, n\}$和$ \varphi^{\ast} $的MP近似推理结论, 则$ \psi^{\ast} $是$ L $的后件属性公式集$F = \{\psi_1, \cdots,\psi_n\}$的误差小于$(| \Delta|-| \Sigma|)/{| \Delta|}$的结论, 其中$| \Delta|$表示$\Delta$的元素个数.

    证明. $\{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$和$ \varphi^{\ast} $的MP近似推理的$( \Sigma, \Delta)$解函数为:

    $$ f(x) =\mathop \wedge^{n}\limits_{i = 1} \mathop\vee\limits_{y \in \Sigma} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], x \in \Delta $$ (9)

    设$||\varphi^{\ast}||_{\Delta} \cap \Sigma \subseteq ||\varphi_{i_1}||_{\Delta} \cap \Sigma, \cdots,$ $||\varphi^{\ast}||_{\Delta} \cap \Sigma \;\subseteq ||\varphi_{i_k}||_{\Delta} \cap \Sigma$. 从而$f(x) = \overline{\psi}_{i_1}(x) \wedge \cdots \wedge \overline{\psi}_{i_k}(x), x \;\in \Delta .$令$ \gamma = \psi_{i_1} \wedge \cdots \wedge \psi_{i_k} $, 显然有$\gamma \in D_{ \Sigma}(F)$. 又记$W = \{x \in { \Delta} | f(x) = 1\}$, $ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $. 由式(9)和决策蕴涵生成模式1可知, $\forall x \in \Sigma$, $\overline{\varphi^{\ast}} (x) = \wedge_{d \in \alpha^{J}(W)} \overline{d}(x) \geq f(x) = \overline{\psi}_{i_1}(x) \wedge \cdots \wedge \overline{\psi}_{i_k}(x) , $ 即 $ \forall x \in \Sigma $, $ \overline{\gamma \to \psi^{\ast}} (x) = 1 $. 所以:

    $$ \tau_{ \Delta} (\gamma \to \psi^{\ast}) = \int_{\Delta} \overline{\gamma \to \psi^{\ast}} (x) \text{d}P \geq \qquad $$
    $$\qquad \qquad \frac{| \Sigma|}{| \Delta|} = 1-\frac{| \Delta|-| \Sigma|}{| \Delta|} $$

    命题11. 设${ \Sigma} \subset \Delta_1 \subset \Delta_2$, $ \{\varphi_{i} \to \psi_{i} | $ $i = 1, \cdots, n\}$和$ \varphi^{\ast} $的MP近似推理的$({ \Sigma}, \Delta_1)$, $({ \Sigma}, \Delta_2)$结论分别是$ \psi^{\ast}_{1} $和$ \psi^{\ast}_{2} $. 则$ \psi^{\ast}_{2} $比$ \psi^{\ast}_{1} $包含有更多的原子属性公式, 且$ \psi^{\ast}_{2} $和$F = \{\psi_1, \cdots, \psi_n\}$的距离小于$ \psi^{\ast}_{1} $和$F = \{\psi_1, \cdots, \psi_n\}$的距离.

    证明. $ \{\varphi_{i} \to \psi_{i} | $ $i = 1, \cdots, n\}$和$ \varphi^{\ast} $的MP近似推理的$({ \Sigma}, \Delta_1)$, $({ \Sigma}, \Delta_2)$解函数分别为$ f_1 (x) $和$ f_2 (x) $:

    $$ \begin{split}& f_1(x) =\mathop \wedge^{n}\limits_{i = 1} \mathop\vee\limits_{y \in \Sigma} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], x \in \Delta_1 \\ & f_2(x) =\mathop \wedge^{n}\limits_{i = 1} \mathop\vee\limits_{y \in \Sigma} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], x \in \Delta_2 \end{split} $$

    显然$ \forall x \in \Delta_1, f_1(x) = f_2(x) $. 不妨设在决策蕴涵集$ L $的前件属性公式集$\{\varphi_1, \cdots, \varphi_n\}$中有$ i_k $个前件属性公式$\varphi_{i_1}, \cdots, \varphi_{i_k}$满足条件$||\varphi^{\ast}||_{\Delta} \cap { \Sigma} \subseteq ||\varphi_{i_1}||_{\Delta}\; \cap { \Sigma}, \cdots$, $||\varphi^{\ast}||_{ \Delta} \cap { \Sigma} \subseteq ||\varphi_{i_k}||_{\Delta} \cap { \Sigma}$. 因此, 类似于定理3的证明, 不妨设:

    $$ \begin{split} &f_1(x) = \overline{\psi}_{i_1}(x) \wedge \cdots \wedge \overline{\psi}_{i_k}(x), x \in \Delta_1 \\ & f_2(x) = \overline{\psi}_{i_1}(x) \wedge \cdots \wedge \overline{\psi}_{i_k}(x), x \in \Delta_2 \end{split} $$

    记$ \gamma = \psi_{i_1} \wedge \cdots \wedge \psi_{i_k} $, $ W_1 = \{x \in \Delta_1 | f(x) = 1\} $, $ \psi^{\ast}_{1} = \wedge_{d \in \alpha^{J}(W_1)} d $, $ W_2 = \{x \in \Delta_2 | f(x) = 1\} $, $\psi^{\ast}_{2} \;= \wedge_{d \in \alpha^{J}(W_2)} d$. 显然$ W_1 \subseteq W_2 $, 从而$ \psi^{\ast}_{1} $比$ \psi^{\ast}_{2} $包含有更多的决策原子属性公式, 于是$\forall x \in \Delta_2, \overline{\psi^{\ast}_{1}} (x)\; \leq \overline{\psi^{\ast}_{2}} (x)$. 因此由伪距离的定义知, $ \psi^{\ast}_{2} $与$ \gamma $间的伪距离比$ \psi^{\ast}_{1} $与$ \gamma $间的伪距离要小.

    由命题11, 当${ \Sigma} \subset \Delta_1 \subset \Delta_2$时, $ \{\varphi_{i} \to \psi_{i} | $ $i = 1, \cdots, n\}$和$ \varphi^{\ast} $的MP近似推理的$({ \Sigma}, \Delta_1)$结论$ \psi^{\ast}_{1} $比$({ \Sigma}, \Delta_2)$结论$ \psi^{\ast}_{2} $有更小的精确度.

    定理10. 设$\Sigma \subset \Delta \subseteq G$, $ \varphi^{\ast} $是$ \{\varphi_{i} \to \psi_{i} | $ $i = 1, \cdots, n\}$和$ \psi^{\ast} $的MT近似推理结论. 则$ \varphi^{\ast} $是$ L $的前件属性公式集$F = \{\varphi_1, \cdots, \varphi_n\}$的误差小于$(| \Delta|\;- | \Sigma|)/{| \Delta|}$的结论.

    证明. $L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$和$ \psi^{\ast} $的多规则MT近似推理的$( \Sigma, \Delta)$解函数为:

    $$ g(y) = \mathop\wedge^{n}\limits_{i = 1} \mathop\wedge\limits_{x \in \Sigma} [(\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x)) \to \overline{\varphi^{\ast}}(x)], y \in \Delta $$ (10)

    设$||\varphi_{i_1}||_{\Delta} \cap \Sigma \subseteq ||\varphi^{\ast}||_{\Delta} \cap \Sigma, \cdots,$ $||\varphi_{i_l}||_{\Delta} \cap \Sigma \;\subseteq ||\varphi^{\ast}||_{\Delta} \cap \Sigma$. 从而$f(x) = \overline{\varphi}_{i_1}(x) \wedge \cdots \wedge \overline{\varphi}_{i_l}(x), x \in \Delta .$令$ \gamma = \varphi_{i_1} \wedge \cdots \wedge \varphi_{i_l} $, 显然有$\gamma \in D_{ \Sigma}(F)$. 又记$V = \{y \in { \Delta} | g(y) = 1\}$, $ \varphi^{\ast} = \wedge_{c \in \alpha^{I}(V)} c $. 由式(9)和决策蕴涵生成模式2可知:

    $$ \overline{\varphi^{\ast}} (y) = \wedge_{c \in \alpha^{I}(V)} \overline{c}(y) \geq g(y) = \overline{\varphi}_{i_1}(x) \wedge \cdots \wedge \overline{\varphi}_{i_l}(x) $$

    $\forall y \in \Sigma$, 则$\forall y \in \Sigma$, $ \overline{\gamma \to \varphi^{\ast}} (y) = 1 $. 所以:

    $$ \begin{split} \tau_{ \Delta} (\gamma \to \varphi^{\ast}) =\;& \int_{\Delta} \overline{\gamma \to \varphi^{\ast}} (y) \text{d}P \;\geq \\ &\frac{| \Sigma|}{| \Delta|} = 1-\frac{| \Delta|-| \Sigma|}{| \Delta|} \end{split} $$

    由定理10、命题11的证明, 可证明如下结论成立.

    命题12. 设${ \Sigma} \subset \Delta_1 \subset \Delta_2$, $ \{\varphi_{i} \to \psi_{i} | $ $i = 1, \cdots, n\}$和$ \psi^{\ast} $的MT近似推理的$({ \Sigma}, \Delta_1)$, $({ \Sigma}, \Delta_2)$结论分别是$ \varphi^{\ast}_{1} $和$ \varphi^{\ast}_{2} $, 则$ \varphi^{\ast}_{2} $比$ \varphi^{\ast}_{1} $包含更多的原子属性公式, 且$ \varphi^{\ast}_{2} $和$F = \{\varphi_1, \cdots, \varphi_n\}$的距离小于$ \varphi^{\ast}_{1} $和$F = \{\varphi_1, \cdots, \varphi_n\}$的距离.

    由例6可知, $ \{\varphi_{i} \to \psi_{i} | $ $i = 1, \cdots, n\}$和$ \varphi^{\ast} $在部分对象集$\Sigma \subset \Delta$的具有局部意义的MP近似推理结论$ \psi^{\ast} $不一定使得$ \psi^{\ast} \to \varphi^{\ast} $是整个对象集$ G $上的决策蕴涵. 由定理9、定理10、命题11和命题12可知, 利用MP、MT近似推理提取局部意义的决策蕴涵(以下称为拟决策蕴涵)生成算法1和算法2.

      算法1. MP近似推理生成拟决策蕴涵算法

      输入. $L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$, 条件属性合取公式$ \varphi^{\ast} $, 部分决策形式背景$K = ({ \Delta},C,D,I,J)$, 对象集${ \Sigma} \subseteq { \Delta}$.

    输出. 拟决策蕴涵$ \varphi^{\ast} \to \psi^{\ast} $.

    1) 计算$||\varphi^{\ast}||_{ \Sigma}$, $||\varphi_{i}||_{ \Sigma}$, $i = 1, \cdots, n$, 其中$||\varphi^{\ast}||_{ \Sigma} = \{u \in \Sigma | \forall a \in \varphi^{\ast}, I(u,c) = 1\}$;

    2) 找出满足条件$||\varphi^{\ast}||_{ \Sigma} \subseteq ||\varphi_{i}||_{ \Sigma}$的前件属性公式$\varphi_{i_1}, \cdots, \varphi_{i_k}$, 相应的后件属性公式为$\psi_{i_1}, \cdots, \psi_{i_k}$;

    3) 如果没有满足条件2), 推理问题无解; 否则, 令$ \gamma = \psi_{i_1} \wedge \cdots \wedge \psi_{i_k} $;

    4) 计算$W = \{u \in \Delta | \forall d \in { \Sigma},\ J(u,d) = 1\}$, $\alpha^{J}(W) = \{d \in D | \forall u \in W, uJd\}$.

    5)令$ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $, 计算属性公式$ \gamma $和$ \psi^{\ast} $的伪距离;

    6)获取拟决策蕴涵$ \varphi^{\ast} \to \psi^{\ast} $.

    算法1的时间复杂度分析如下:

    1)计算$||\varphi^{\ast}||_{ \Sigma}$, $||\varphi_{i}||_{ \Sigma}$, $i = 1, \cdots, n$的时间复杂度为$\mathrm{O}((n+1)|C|| \Sigma|)$, $ n $为$ L $中的决策蕴涵个数, $ |C| $是条件属性集$ C $的元素个数, $ | \Sigma| $是对象集$ \Sigma $的元素个数.

    2)找出满足条件$||\varphi^{\ast}||_{ \Sigma} \subseteq ||\varphi_{i}||_{ \Sigma}$的前件属性公式$\varphi_{i_1}, \cdots, \varphi_{i_k}$的时间复杂度为$ \mathrm{O}(n| \Sigma|) $.

    3)计算$ W $的时间复杂度为$\mathrm{O}(|D|| \Delta|)$; 计算$ \alpha^{J}(W) $的时间复杂度也是$\mathrm{O}(|D|| \Delta|)$, $ |D| $是决策属性集$ D $的元素个数, $| \Delta|$是对象集$\Delta$的元素个数.

    4)计算$ \psi^{\ast} = \wedge_{d \in \alpha^{J}(W)} d $的时间复杂度为$ \mathrm{O}(|D|) $, 计算$ \gamma $和$ \psi^{\ast} $的伪距离需要先计算属性公式函数$ \overline{\gamma} $和$ \overline{\psi^{\ast}} $, 其时间复杂度为$\mathrm{O}(2|D|| \Delta|)$, 计算$ \gamma $和$ \psi^{\ast} $的伪距离时间复杂度为$\mathrm{O}(| \Delta|)$, 所以算法1中步骤5)的时间复杂度为$\mathrm{O}(2|D|| \Delta|)$.

    由于$\Sigma \subseteq \Delta$且$| \Sigma|$与$| \Delta|$相差不是很大, 所以MP近似推理生成一个拟决策蕴涵算法的时间复杂度为$\mathrm{O}((n+1)|C \cup D|| \Delta|)$.

      算法2. MT近似推理生成拟决策蕴涵算法

    输入. $L = \{\varphi_{i} \to \psi_{i} | i = 1, \cdots, n\}$, 决策属性合取公式$ \psi^{\ast} $, 部分决策形式背景$K = ({ \Delta},C,D,I,J)$, 对象集${ \Sigma} \subseteq { \Delta}$.

    输出. 拟决策蕴涵$ \varphi^{\ast} \to \psi^{\ast} $.

    1) 计算$||\psi^{\ast}||_{ \Sigma}$, $||\psi_{i}||_{ \Sigma}$, $i = 1, \cdots, n$, 其中$||\psi^{\ast}||_{ \Sigma} = \{u \in \Sigma | \forall a \in \psi^{\ast}, J(u,d) = 1\}$;

    2) 找出满足条件$||\psi_{i}||_{ \Sigma} \subseteq ||\psi^{\ast}||_{ \Sigma}$的后件属性公式$\psi_{i_1}, \cdots, \psi_{i_l}$, 相应的前件属性公式为$\varphi_{i_1}, \cdots, \varphi_{i_l}$;

    3) 如果没有满足式(2)中条件的公式, 推理问题无解; 否则, 令$ \lambda = \varphi_{i_1} \wedge \cdots \wedge \varphi_{i_l} $;

    4) 计算$V = \{u \in { \Delta} | \forall c \in \lambda,\ I(u,c) = 1\}$, $\alpha^{I}(V) = \{c \in C | \forall u \in V, uIc\}$;

    5)令$ \varphi^{\ast} = \wedge_{c \in \alpha^{I}(V)} c $, 计算属性公式$ \lambda $和$ \varphi^{\ast} $的伪距离;

    6)获取拟决策蕴涵$ \varphi^{\ast} \to \psi^{\ast} $.

    类似于MP近似推理生成拟决策蕴涵算法的时间复杂度分析, MT近似推理生成拟决策蕴涵算法的时间复杂度也是$\mathrm{O}((n+1)|C \cup D|| \Delta|)$.

    本节参考文献[25], 通过3个数值实验验证本文算法的有效性. 由于MT近似推理生成拟决策蕴涵算法与MP近似推理生成拟决策蕴涵算法的推理机制、步骤和计算表达式类似, 因此只就MP近似推理生成拟决策蕴涵算法进行实验. 基于定理9和命题11的证明过程, 算法的有效性通过MP近似推理结论$ \psi^{\ast}_{\Delta} $与相应大前提的后件合取公式$\gamma = \psi_{i_1} \wedge \cdots \wedge \psi_{i_k}$的伪距离$\rho_{ \Delta}(\gamma, \psi^{\ast}_{\Delta})$、后件属性公式合取式对MP近似推理结论的平均支持度$\tau_{\Delta}(\gamma, \psi^{\ast}_{\Delta})$、MP近似推理获取拟决策蕴涵的时间成本来评价.

    实验环境为Win7 64位 Intel (R) 3.4 GHz, 4 GB内存. 实验1用来测试MP近似推理生成拟决策蕴涵个数及与相应后件公式的伪距离. 实验数据设置为条件属性个数20, 决策属性个数10, 对象个数2000, 分成4个数据组, 每组500个数据, 数据的属性值(包括条件属性和决策属性) 随机生成, 数据填充比强度${|I|} / ({|G| |M|} )$为20%. 每组前400个数据为基础数据集$\Sigma$, MP近似推理的大前提是由$\Sigma$产生的决策蕴涵集$ L = \{\varphi_{u} \to \psi_{u} | u \in \Sigma\} $, $\varphi_{u} (c) = I(c, u), c \in C$是对象$ u $决定的条件属性公式, 决策属性公式$\psi_{u} (d) = \wedge_{x \in \Sigma} [\beta^{I} (\varphi_{u}) (x) \to J(x,d)] , d \in D$, 后100个数据中的对象$ u $决定的条件属性公式$ \varphi^{\ast}_{u} $作为MP近似推理的小前提, 并用来测试算法1的效果.

    各组后100个数据经过MP近似推理生成的拟决策蕴涵个数见表4.

    表 4  生成的拟决策蕴涵个数
    Table 4  The number of generated quasi-decision implications
    数据组别生成的拟决策蕴涵个数
    数据组162
    数据组258
    数据组374
    数据组471
    下载: 导出CSV 
    | 显示表格

    各组数据经过MP近似推理产生的拟决策蕴涵的后件$\psi^{\ast}_{ \Delta}$与相应后件合取公式$\gamma = \psi_{i_1} \wedge \cdots \wedge \psi_{i_k}$的最大伪距离和最小伪距离见表5.

    表 5  生成的拟决策蕴涵后件与后件合取公式的伪距离
    Table 5  The pseudo-metric between the consequent of generated quasi-decision implications and the consequent conjunctive
    数据组别最大伪距离最小伪距离
    数据组10.1950.147
    数据组20.1890.160
    数据组30.1970.152
    数据组40.1940.161
    下载: 导出CSV 
    | 显示表格

    实验1基于400个实验基础数据, 通过近似推理获得新增加100个数据所确定的拟决策蕴涵. 实验结果显示经过MP近似推理产生的拟决策蕴涵的后件与相应后件合取公式的伪距离有点大. 但在实际知识推理中, 往往依据大量的数据通过近似推理发现少量新增数据所隐含的新知识. 由定理9可知, 当待获取新知识的新增数据个数与基础数据集的数据个数的比值${(| \Delta|-| \Sigma|)} / {| \Delta|}$较小时, MP近似推理产生的拟决策蕴涵的后件与相应后件合取公式的伪距离也比较小. 实验2和实验3也都有效地支持了这个理论分析.

    实验2用来测试对象集$\Sigma、 \Delta$的变化对MP近似推理生成拟决策蕴涵的个数及与相应后件合取公式的伪距离的影响. 实验数据设置为条件属性为20个, 决策属性为10个, 实验基础数据对象集$\Sigma$的元素个数$| \Sigma|$为1000, 近似推理新增对象以10个为1组的频率, 逐步增加到100个, 从而$\Delta$的元素个数$| \Delta|$动态地逐步增加到1010, 1020, $\cdots,$1100, 相应的数据组分别被命名为数据组1, 数据组$2,\cdots,$数据组10, 数据填充比强度与实验1相同, 为20%.

    基于基础数据对象集$\Sigma$产生的MP近似推理的决策蕴涵集$ L $和逐次新增加数据中的对象$ u $所决定的条件属性公式$ \varphi_{u} $进行MP近似推理. MP近似推理生成的拟决策蕴涵的个数以及生成的拟决策蕴涵的后件与相应后件合取公式$\gamma = \psi_{i_1} \wedge \cdots \wedge \psi_{i_k}$的最小伪距离见表6.

    表 6  测试数据变化生成的拟决策蕴涵表
    Table 6  A table of generated quasi-decision implication as test data changes
    数据组别拟决策蕴涵个数最小伪距离
    数据组130.0082
    数据组250.0157
    数据组380.0256
    数据组4120.0324
    数据组5160.0418
    数据组6210.0527
    数据组7250.0619
    数据组8290.0718
    数据组9340.0821
    数据组10390.0913
    下载: 导出CSV 
    | 显示表格

    表5表6可以看出, 在基础数据集确定前提下, 从新增加数据所生成的拟决策蕴涵个数以及生成的拟决策蕴涵的后件与相应的后件合取公式$ \gamma = \psi_{i_1} \wedge \cdots \wedge \psi_{i_k} $的最小伪距离都随着测试数据的增加而增加, 增加趋势基本是线性的. 这与定理9、命题11的理论分析结论相吻合.

    实验3用来测试在同一个数据集上、采用不同方式获取拟决策蕴涵时的时间成本比较. 实验3的实验数据取值方式和数据填充比强度同实验1. 基础数据对象集$\Sigma$的元素个数$| \Sigma|$为2000个, MP近似推理的新增数据对象以100个为1组的频率, 逐步增加到500个, 从而$\Delta$的元素个数$| \Delta|$动态地逐次增加到$2\,100, 2\,200,\cdots ,2\,500$, 相应的数据组分别被命名为数据组1, 数据组$2,\cdots,$数据组5.

    根据命题5中步骤1), 由包含2000个对象的基础数据集$\Sigma$中的每个对象$ u $产生决策蕴涵(对象$ u $决策蕴涵产生的过程同实验1), 以如此产生的全部决策蕴涵集$L = \{\varphi_{u} \to \psi_{u} | u \in \Sigma\}$作为MP近似推理的大前提. MP近似推理的小前提是各数据组中新增加对象$u \in \Delta - \Sigma$所决定的条件属性公式$ \varphi^{\ast}_{u} $. MP近似推理的对象范围参数$\Sigma$为2000个对象组成的基础数据集, 参数$\Delta$分别为在$\Sigma$上逐次加入新数据得到的数据组1, 数据组$2,\cdots,$数据组5. 运用算法1, 分别由$ L $和$ \varphi^{\ast}_{u} $进行MP近似推理生成以$ \varphi^{\ast}_{u} $为前件的拟决策蕴涵. 采用2种方式获取$\Delta\; - \Sigma$上的新增决策蕴涵: 方式1)是由各数据组的新增加对象$u \in \Delta - \Sigma$所决定的条件属性公式$ \varphi^{\ast}_{u} $和$ L $直接在$\Delta$上进行MP近似推理以获取$\Delta$上的拟决策蕴涵, 即通过:

    $$ \begin{split} &f_{\Delta u}(x) = \mathop\wedge\limits^{n}_{i = 1} \mathop\vee\limits_{y \in \Delta} [\overline{\varphi^{\ast}}(y) \wedge (\overline{\varphi}_{i}(y) \to \overline{\psi}_{i}(x))], x \in \Delta \\ &W_u = \{x \in \Delta | f_{\Delta u}(x) = 1\}, \psi^{\ast}_{\Delta u} = \wedge_{d \in \alpha^{J}(W_u)} d \end{split}$$

    获取$\Delta$上的决策蕴涵$\varphi^{\ast}_{u} \to \psi^{\ast}_{\Delta u}$.

    方式2)是先由基础数据集$\Sigma$产生决策蕴涵集$L = \{\varphi_{u} \to \psi_{u} | u \in \Sigma\}$, 再运用MP近似推理算法1获取$\Delta$上的拟决策蕴涵 (以下称这种获取方式为增量获取方式). 算法效率是通过$ L $中的决策蕴涵后件对MP近似推理结论的平均支持度$\tau_{ \Delta}(\psi_{1} \wedge\;\cdots \wedge \;\psi_{n} \to \psi^{\ast}_{\Delta})$以及获取$\Delta$上拟决策蕴涵所用时间成本来刻画. 采用2种不同方式获取拟决策蕴涵时, 拟决策蕴涵集$ L $的后件对MP近似推理结论的平均支持度$\tau_{\Delta}(\psi_{1} \wedge \cdots \wedge \psi_{n} \to \psi^{\ast}_{ \Delta})$和时间成本对比如表7所示.

    表 7  后件集对结论的支持度和获取拟决策蕴涵时间成本对比
    Table 7  Comparison of the support degree of consequent set to the conclusion and time consumption of obtaining quasi-decision implications
    数据组别$L$的后件集对结论支持度$\tau_{\Delta}$方式1)总时间成本(s)方式2)总时间成本 (s)增量获取所用时间成本(s)
    数据组10.9330.2040.2230.103
    数据组20.9230.2830.3040.147
    数据组30.9140.3610.3890.198
    数据组40.9030.4500.4840.258
    数据组50.8930.5390.2580.326
    下载: 导出CSV 
    | 显示表格

    表7可以看出, 对给定的基础数据集$ \Sigma $, 随着数据集$ \Delta $的数据个数的增加, 决策蕴涵集$ L $的后件公式集对MP近似推理结论的支持度会减少, 其变化幅度不是很显著, 当MP近似推理的参数数据集$ \Sigma $与$ \Delta $的数据个数比 ${| \Sigma|} / {| \Delta|}$较大时, 实际支持度$ \tau_{\Delta} $比 ${| \Sigma|} / {| \Delta|}$要小很多, 定理9中的比值 ${| \Sigma|} / {| \Delta|}$只是支持度$ \tau_{ \Delta} $的下界. 2种方式总时间成本随着实验数据的增加而增加, 增加的趋势基本上是线性的. 与方式1)相比, 方式2)获取决策蕴涵的总时间成本可能要多些. 但如果是在已有$ \Sigma $上的决策蕴涵的基础上来获取$ \Delta $上的新增决策蕴涵, 方式2)充分利用了$ \Sigma $上的已有决策蕴涵, 减少了获取决策蕴涵$ L = \{\varphi_{u} \to \psi_{u} | u \in \Sigma\} $的时间成本, 扣除获取$ \Sigma $上的决策蕴涵的时间成本后, 增量获取决策蕴涵所用时间成本就要少很多.

    方式2)是基于已有决策蕴涵借助近似推理模式产生新的更多决策蕴涵, 体现了人工智能时代通过学习来获取新知识的思想方法, 是知识推理的有效手段. 但如何评价近似推理好坏, 目前还没有公认的标准. 本文引入的“决策蕴涵后件对MP近似推理结论的平均支持度”和“决策蕴涵前件对MT近似推理结论的伪距离”都是通过公式的真度来定义的. 按照文献[18]的支持度理论, 一个由条件联结词连接的蕴涵公式的真度本质上刻画了前件公式对后件公式的支持度, 上述评价标准实际上刻画了推理大前提中的知识对近似推理得到的结论知识的支持程度, 因此, 它们应是一个比较有效的知识推理评价标准. 由实验1 ~ 实验3可知, 本文提出的应用MP和MT近似推理生成拟决策蕴涵的方法具有较好效果.

    本文提出的近似推理方法的一个应用是针对有缺失值的不完全决策形式背景的属性值补齐. 这时对象范围参数选择为包含缺失值的对象集, 对象范围选择不包含缺失值的对象集, 进而根据缺失值是条件属性值还是决策属性值, 选择应用MP或MT近似推理来补齐有缺失值的不完全决策形式背景, 进而实现不完全决策形式背景上的决策蕴涵和概念规则等知识的获取.

    本文从数据分析需求的角度讨论决策蕴涵, 利用属性逻辑的K-赋值对决策蕴涵进行属性逻辑语义刻画, 在此基础上研究决策蕴涵、概念规则的近似推理. 分析经典二值逻辑框架下基于全蕴涵三I推理思想的决策蕴涵和概念规则的MP、MT近似推理模式的特征, 证明决策蕴涵的MP、MT近似推理结论是决策蕴涵, 概念规则的MP、MT近似推理结论是概念规则, 引进属性逻辑伪距离, 分析人工智能环境下通过MP、MT近似推理生成拟决策蕴涵的模式和效果. 提出若干基于现有决策蕴涵、概念规则通过MP、MT近似推理产生新的决策蕴涵、概念规则、拟决策蕴涵的模式和方法, 并通过实际例子和数值实验来说明这些模式的应用和效果. 人工智能环境下的机器学习是一种基于现有知识通过一定的规则获取新知识的过程. 本文提出的基于现有决策蕴涵、概念规则通过近似推理来产生新的决策蕴涵及概念规则的方法正是依据这个思想来进行的. 本文提出的方法是一种获取决策蕴涵、概念规则的新方法, 为人工智能、大数据环境下的知识发现、知识推理提供了新的途径. 未来工作包括以下2个方面:

    1)决策蕴涵和概念规则的近似推理机制的逻辑语构方面也是值得探讨的.

    2)将本文提出的形式背景上的近似推理模式推广到模糊形式背景, 研究模糊形式背景中模糊决策蕴涵和模糊概念规则的近似推理机制及方法.

  • 图  1  不同采样中心概率密度曲线

    Fig.  1  Probability density curves of different sampling centers

    图  2  MQHOA-d所生成种群在Ellipsoidal函数二维空间分布示意图

    Fig.  2  Schematic diagram of spatial distribution of subpopulations generated by MQHOA-d in Ellipsoidal function of 2D

    图  3  一维双阱函数图与隧道效应示意图

    Fig.  3  One dimensional double well function diagram and tunnel effect diagram

    图  4  MQHOA-d与MQHOA发生隧道效应点数量与迭代次数关系图

    Fig.  4  The relationship between the number of tunneling points and the number of iterations between MQHOA-d and MQHOA

    图  5  CEC2013测试集上各算法误差等级图(维度为30, 重复51次)

    Fig.  5  Rank sum test results of all algorithms on CEC2013 test set (repeated 51 times in the 30-dimensional case)

    图  6  CEC2013测试函数在30维情况下重复51次实验箱体图

    Fig.  6  Boxplots of CEC2013 benchmark functions repeated 51 times in the 30-dimensional case

    图  7  CEC2013测试函数在30维情况下各算法重复51次实验平均时间消耗热力图

    Fig.  7  Rank of mean time consumption on CEC2013 repeated 51 times in the 30-dimensional case

    表  1  量子理论与优化算法的对应关系

    Table  1  The relationship between quantum theory and optimization algorithm

    量子理论 优化算法 说明
    势能评估/势能最低点 $f(x)/f(x)$ 的全局最小值 量子系统下将函数优化问题转化为寻找势能最低点问题
    波函数 解的概率分布 量子系统下波函数对优化问题的概率描述
    势阱等效 优化问题目标函数的近似方法 如QPSO中用Delta势阱逼近目标函数, MQHOA以谐振子逼近目标函数
    势垒宽度 子种群位置到最优解的相对距离 势垒宽度越大, 隧道效应概率越低
    量子隧道效应 跳出局部最优能力 波函数计算隧道效应概率, 增加迭代过程中发生隧道效应的采样点数量, 可提高算法性能
    下载: 导出CSV

    表  2  CEC2013测试函数维度为30情况下各算法51次重复实验的平均误差和标准差

    Table  2  Mean errors and standard deviation of each algorithm on CEC2013 repeated 51 times in the 30-dimensional

    $ f $ MQHOA MQHOA-d SPSO2011 QPSO EFWA AFWA
    MeanErr Std MeanErr Std MeanErr Std MeanErr Std MeanErr Std MeanErr Std
    1 $9.71\times 10^{-11}$ $1.44\times 10^{-11}$ $3.25\times10^{-13}$ $1.14\times 10^{-13}$ $2.36\times 10^{-13}$ $4.46\times 10^{-14}$ $2.59\times 10^{-13}$ $9.12\times 10^{-14}$ $7.82\times 10^{-2}$ $1.31\times 10^{-2}$ ${{{\boldsymbol{0.00}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{0}}} } }$ ${{{\boldsymbol{0.00}}{\boldsymbol{\times}}{\boldsymbol{10}}^{{\boldsymbol{0}}} } }$
    2 $1.15\times 10^{6}$ $2.65\times 10^{5}$ $1.76\times 10^{6}$ $3.97\times 10^{5}$ ${{{\boldsymbol{9.68}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{4}}} } }$ ${{{\boldsymbol{4.82}}\times {\boldsymbol{10}}^{{\boldsymbol{4}}} } }$ $1.62\times 10^{7}$ $7.01\times 10^{6}$ $5.43\times 10^{5}$ $2.04\times 10^{5}$ $8.92\times 10^{5}$ $3.92\times 10^{5}$
    3 $3.32\times 10^{7}$ $ 3.94\times 10^{7} $ ${{{\boldsymbol{3.60}}\times {\boldsymbol{10}}^{{\boldsymbol{6}}} } }$ ${{{\boldsymbol{4.19}}\times {\boldsymbol{10}}^{{\boldsymbol{6}}} } }$ $ 1.07\times 10^{8} $ $ 1.58\times 10^{8} $ $ 2.28\times 10^{8} $ $ 3.23\times 10^{8} $ $ 1.26\times 10^{8} $ $ 2.15\times 10^{8} $ $ 1.26\times 10^{8} $ $ 1.54\times 10^{8} $
    4 $ 3.83\times 10^{4} $ $ 5.80\times 10^{3} $ $ 4.24\times 10^{4} $ $ 4.43\times 10^{3} $ $ 1.55\times 10^{3} $ $ 5.87\times 10^{2} $ $ 1.03\times 10^{4} $ $ 2.49\times 10^{3} $ ${{{\boldsymbol{1.09}}{\boldsymbol{\times}} {\boldsymbol{10^{0}}}}} $ ${{{\boldsymbol{3.53}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{1}}} } }$ $ 1.14\times 10^{1} $ $ 6.83\times 10^{0} $
    5 $ 1.92\times 10^{-3} $ $ 2.46\times 10^{-4} $ $ 2.22\times 10^{-3} $ $ 4.23\times 10^{-4} $ $ 4.03\times 10^{-4} $ $ 2.92\times 10^{-5} $ ${{{\boldsymbol{3.40}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{7}}} } }$ ${{{\boldsymbol{3.94}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{7}}} } }$ $ 7.90\times 10^{-2} $ $ 1.01\times 10^{-2} $ $ 6.04\times 10^{-4} $ $ 9.24\times 10^{-5} $
    6 $ 3.16\times 10^{1} $ $ 2.65\times 10^{1} $ $ 2.41\times 10^{1} $ $ 1.60\times 10^{1} $ ${{{\boldsymbol{1.70}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{1}}} } }$ ${{{\boldsymbol{2.02}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}}}} $ $ 3.21\times 10^{1} $ $ 2.15\times 10^{1} $ $ 3.49\times 10^{1} $ $ 2.71\times 10^{1} $ $ 2.99\times 10^{1} $ $ 2.63\times 10^{1} $
    7 ${{{\boldsymbol{2.07}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ ${{{\boldsymbol{1.26}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ $ 2.23\times 10^{1} $ $ 8.22\times 10^{0} $ $ 5.65\times 10^{1} $ $ 2.03\times 10^{1} $ $ 4.71\times 10^{1} $ $ 1.66\times 10^{1} $ $ 1.33\times 10^{2} $ $ 4.34\times 10^{1} $ $ 9.19\times 10^{1} $ $ 2.63\times 10^{1} $
    8 $ 2.10\times 10^{1} $ $ 4.43\times 10^{-2} $ ${{{\boldsymbol{2.09}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{1}}} } }$ ${{{\boldsymbol{5.62}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{2}}} } }$ ${{{\boldsymbol{2.09}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{1}}} } }$ ${{{\boldsymbol{6.88}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{2}}} } }$ ${{{\boldsymbol{2.09}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{1}}} } }$ ${{{\boldsymbol{5.15}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{2}}} } }$ $ 2.10\times 10^{1} $ $ 4.82\times 10^{-2} $ ${{{\boldsymbol{2.09}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{1}}} } }$ ${{{\boldsymbol{7.85}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{2}}} } }$
    9 $ 3.91\times 10^{1} $ $ 1.37\times 10^{0} $ $ 2.29\times 10^{1} $ $ 6.38\times 10^{0} $ $ 2.41\times 10^{1} $ $ 4.10\times 10^{0} $ ${{{\boldsymbol{2.12}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ ${{{\boldsymbol{7.99}}{\boldsymbol{\times}} {\boldsymbol{10^{0}}} } }$ $ 3.19\times 10^{1} $ $ 3.48\times 10^{0} $ $ 2.48\times 10^{1} $ $ 4.89\times 10^{0} $
    10 $ 4.75\times 10^{-1} $ $ 2.53\times 10^{-1} $ $ 5.43\times 10^{-2} $ $ 2.97\times 10^{-2} $ $ 2.13\times 10^{-1} $ $ 9.54\times 10^{-2} $ $ 1.92\times 10^{0} $ $ 1.26\times 10^{0} $ $ 8.29\times 10^{-1} $ $ 8.42\times 10^{-2} $ ${{{\boldsymbol{4.73}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{2}}} } }$ ${{{\boldsymbol{3.44}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{2}}} } }$
    11 $ 1.67\times 10^{2} $ $ 4.78\times 10^{1} $ ${{{\boldsymbol{3.41}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ ${{{\boldsymbol{2.23}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ $ 8.61\times 10^{1} $ $ 3.02\times 10^{1} $ $ 1.59\times 10^{2} $ $ 2.01\times 10^{1} $ $ 4.22\times 10^{2} $ $ 9.26\times 10^{1} $ $ 1.05\times 10^{2} $ $ 3.43\times 10^{1} $
    12 $ 1.71\times 10^{2} $ $ 3.93\times 10^{1} $ ${{{\boldsymbol{2.64}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ ${{{\boldsymbol{6.96}}{\boldsymbol{\times}} {\boldsymbol{10^{0}}} } }$ $ 7.21\times 10^{1} $ $ 2.53\times 10^{1} $ $ 2.03\times 10^{2} $ $ 1.51\times 10^{1} $ $ 6.33\times 10^{2} $ $ 1.38\times 10^{2} $ $ 1.52\times 10^{2} $ $ 4.43\times 10^{1} $
    13 $ 1.87\times 10^{2} $ $ 1.58\times 10^{1} $ ${{{\boldsymbol{6.83}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ ${{{\boldsymbol{1.40}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ $ 1.39\times 10^{2} $ $ 3.02\times 10^{1} $ $ 2.06\times 10^{2} $ $ 1.51\times 10^{1} $ $ 4.51\times 10^{2} $ $ 7.45\times 10^{1} $ $ 2.36\times 10^{2} $ $ 6.06\times 10^{1} $
    14 $ 7.13\times 10^{3} $ $ 2.03\times 10^{2} $ $ 3.16\times 10^{3} $ $ 1.07\times 10^{3} $ $ 4.54\times 10^{3} $ $ 8.04\times 10^{2} $ $ 6.17\times 10^{3} $ $ 5.54\times 10^{2} $ $ 4.16\times 10^{3} $ $ 6.16\times 10^{2} $ ${{{\boldsymbol{2.97}}{\boldsymbol{\times}} {\boldsymbol{10^{3}}} } }$ ${{{\boldsymbol{5.70}}{\boldsymbol{\times}}{\boldsymbol{ 10^{2}}} } }$
    15 $ 7.32\times 10^{3} $ $ 2.59\times 10^{2} $ ${{{\boldsymbol{2.80}}{\boldsymbol{\times}} {\boldsymbol{10^{3}}} } }$ ${{{\boldsymbol{6.30}}{\boldsymbol{\times}} {\boldsymbol{10^{2}}} } }$ $ 4.45\times 10^{3} $ $ 6.60\times 10^{2} $ $ 7.25\times 10^{3} $ $ 3.79\times 10^{2} $ $ 4.13\times 10^{3} $ $ 5.61\times 10^{2} $ $ 3.81\times 10^{3} $ $ 5.03\times 10^{2} $
    16 $ 2.48\times 10^{0} $ $2.67\times 10^{-1}$ ${{{\boldsymbol{3.23}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{1}}} } }$ ${{{\boldsymbol{2.85}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{1}}} } }$ $ 1.88\times 10^{0} $ $ 3.94\times 10^{-1} $ $ 2.50\times 10^{0} $ $ 2.67\times 10^{-1} $ $ 5.92\times 10^{-1} $ $ 2.30\times 10^{-1} $ $ 4.97\times 10^{-1} $ $ 2.56\times 10^{-1} $
    17 $ 2.10\times 10^{2} $ $ 1.33\times 10^{1} $ ${{{\boldsymbol{5.94}}{\boldsymbol{\times}}{\boldsymbol{ 10^{1}}} } }$ ${{{\boldsymbol{1.33}}{\boldsymbol{\times}} {\boldsymbol{10^{1} }}} }$ $ 1.34\times 10^{2} $ $ 3.06\times 10^{1} $ $ 2.32\times 10^{2} $ $ 1.44\times 10^{1} $ $ 3.10\times 10^{2} $ $ 6.52\times 10^{1} $ $ 1.45\times 10^{2} $ $ 2.55\times 10^{1} $
    18 $ 2.09\times 10^{2} $ $ 1.21\times 10^{1} $ ${{{\boldsymbol{6.02}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ ${{{\boldsymbol{2.00}}{\boldsymbol{\times}}{\boldsymbol{ 10^{1}}} } }$ $ 1.38\times 10^{2} $ $ 2.48\times 10^{1} $ $ 2.38\times 10^{2} $ $ 1.64\times 10^{1} $ $ 1.75\times 10^{2} $ $ 3.81\times 10^{1} $ $ 1.75\times 10^{2} $ $ 4.92\times 10^{1} $
    19 $ 1.58\times 10^{1} $ $ 1.58\times 10^{0} $ ${{{\boldsymbol{3.01}}{\boldsymbol{\times}} {\boldsymbol{10^{0} }}} }$ ${{{\boldsymbol{1.46}}{\boldsymbol{\times}} {\boldsymbol{10^{0}}} } }$ $ 7.91\times 10^{0} $ $ 3.37\times 10^{0} $ $ 1.73\times 10^{1} $ $ 1.75\times 10^{0} $ $ 1.23\times 10^{1} $ $ 3.68\times 10^{0} $ $ 6.92\times 10^{0} $ $ 2.37\times 10^{0} $
    20 ${{{\boldsymbol{1.20}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ ${{{\boldsymbol{4.32}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{1}}} } }$ $ 1.46\times 10^{1} $ $2.32\times 10^{-1}$ $ 1.31\times 10^{1} $ $ 1.91\times 10^{0} $ $ 1.25\times 10^{1} $ $2.55\times 10^{-1}$ $ 1.46\times 10^{1} $ $1.73\times 10^{-1}$ $ 1.30\times 10^{1} $ $9.72\times 10^{-1}$
    21 $ 3.38\times 10^{2} $ $ 7.88\times 10^{1} $ ${{{\boldsymbol{2.86}}{\boldsymbol{\times}} {\boldsymbol{10^{2}}} } }$ ${{{\boldsymbol{7.01}}{\boldsymbol{\times}}{\boldsymbol{ 10^{1}}} } }$ $ 3.46\times 10^{2} $ $ 8.31\times 10^{1} $ $ 3.00\times 10^{2} $ $ 6.99\times 10^{1} $ $ 3.24\times 10^{2} $ $ 9.67\times 10^{1} $ $ 3.16\times 10^{2} $ $ 9.33\times 10^{1} $
    22 $ 7.64\times 10^{3} $ $ 3.03\times 10^{2} $ ${{{\boldsymbol{3.12}}{\boldsymbol{\times}} {\boldsymbol{10^{3} }}} }$ ${{{\boldsymbol{7.19}}{\boldsymbol{\times}} {\boldsymbol{10^{2}}} } }$ $ 4.16\times 10^{3} $ $ 7.19\times 10^{2} $ $ 6.16\times 10^{3} $ $ 5.17\times 10^{2} $ $ 5.75\times 10^{3} $ $ 1.08\times 10^{3} $ $ 3.45\times 10^{3} $ $ 7.44\times 10^{2} $
    23 $ 7.51\times 10^{3} $ $ 3.35\times 10^{2} $ ${{{\boldsymbol{3.50}}{\boldsymbol{\times}} {\boldsymbol{10^{3}}} } }$ ${{{\boldsymbol{5.83}}{\boldsymbol{\times}} {\boldsymbol{10^{2}}} } }$ $ 4.52\times 10^{3} $ $ 8.56\times 10^{2} $ $ 7.30\times 10^{3} $ $ 2.83\times 10^{2} $ $ 5.74\times 10^{3} $ $ 7.59\times 10^{2} $ $ 4.70\times 10^{3} $ $ 8.98\times 10^{2} $
    24 $ 2.40\times 10^{2} $ $ 7.21\times 10^{0} $ ${{{\boldsymbol{2.20}}{\boldsymbol{\times}} {\boldsymbol{10^{2}}} } }$ ${{{\boldsymbol{4.94}}{\boldsymbol{\times}} {\boldsymbol{10^{0}}} } }$ $ 2.53\times 10^{2} $ $ 9.33\times 10^{0} $ $ 2.46\times 10^{2} $ $ 7.35\times 10^{0} $ $ 3.37\times 10^{2} $ $ 7.33\times 10^{1} $ $ 2.70\times 10^{2} $ $ 1.31\times 10^{1} $
    25 $ 3.14\times 10^{2} $ $ 3.34\times 10^{0} $ $ 2.73\times 10^{2} $ $ 8.64\times 10^{0} $ $ 2.81\times 10^{2} $ $ 6.78\times 10^{0} $ ${{{\boldsymbol{2.60}}{\boldsymbol{\times}} {\boldsymbol{10^{2}}} } }$ ${{{\boldsymbol{6.08}}{\boldsymbol{\times}} {\boldsymbol{10^{0}}} } }$ $ 3.56\times 10^{2} $ $ 2.80\times 10^{1} $ $ 2.99\times 10^{2} $ $ 1.24\times 10^{1} $
    26 $ 2.22\times 10^{2} $ $ 4.67\times 10^{1} $ ${{{\boldsymbol{2.03}}{\boldsymbol{\times }}{\boldsymbol{10^{2}}} } }$ ${{{\boldsymbol{1.74}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ $ 2.67\times 10^{2} $ $ 7.25\times 10^{1} $ $ 2.91\times 10^{2} $ $ 6.83\times 10^{1} $ $ 3.21\times 10^{2} $ $ 9.04\times 10^{1} $ $ 2.73\times 10^{2} $ $ 8.51\times 10^{1} $
    27 $ 7.73\times 10^{2} $ $ 2.03\times 10^{2} $ ${{{\boldsymbol{5.42}}{\boldsymbol{\times}} {\boldsymbol{10^{2}}} } }$ ${{{\boldsymbol{3.92}}{\boldsymbol{\times}} {\boldsymbol{10^{1}}} } }$ $ 8.10\times 10^{2} $ $ 1.11\times 10^{2} $ $ 7.47\times 10^{2} $ $ 1.26\times 10^{2} $ $ 1.28\times 10^{3} $ $ 1.10\times 10^{2} $ $ 9.72\times 10^{2} $ $ 1.33\times 10^{2} $
    28 $ 3.39\times 10^{2} $ $ 2.76\times 10^{2} $ ${{{\boldsymbol{3.00}}{\boldsymbol{\times}} {\boldsymbol{10^{2}}} } }$ ${{{\boldsymbol{6.97}}{\boldsymbol{\times}} {\boldsymbol{10}}^{{\boldsymbol{-}}{\boldsymbol{11}}} } }$ $ 4.29\times 10^{2} $ $ 5.27\times 10^{2} $ $ 3.64\times 10^{2} $ $ 2.59\times 10^{2} $ $ 4.34\times 10^{3} $ $ 2.08\times 10^{3} $ $ 4.37\times 10^{2} $ $ 4.67\times 10^{2} $
    下载: 导出CSV
  • [1] Shi Y H, Eberhart R C. Parameter selection in particle swarm optimization. In: Proceedings of the 7th International Conference on Evolutionary Programming VII. San Diego, USA: Springer, 1998. 591−600
    [2] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58-73 doi: 10.1109/4235.985692
    [3] 王东风, 孟丽. 粒子群优化算法的性能分析和参数选择. 自动化学报, 2016, 42(10): 1552-1561 doi: 10.16383/j.aas.2016.c150774

    Wang Dong-Feng, Meng Li. Performance analysis and parameter selection of PSO algorithms. Acta Automatica Sinica, 2016, 42(10): 1552-1561 doi: 10.16383/j.aas.2016.c150774
    [4] 王丽芳, 曾建潮. 基于微粒群算法与模拟退火算法的协同进化方法. 自动化学报, 2006, 32(4): 630-635 doi: 10.16383/j.aas.2006.04.019

    Wang Li-Fang, Zeng Jian-Chao. A cooperative evolutionary algorithm based on particle swarm optimization and simulated annealing algorithm. Acta Automatica Sinica, 2006, 32(4): 630-635 doi: 10.16383/j.aas.2006.04.019
    [5] Chang D X, Zhang X D, Zheng C W, Zhang D M. A robust dynamic niching genetic algorithm with niche migration for automatic clustering problem. Pattern Recognition, 2010, 43(4): 1346-1360 doi: 10.1016/j.patcog.2009.10.020
    [6] Luo R H, Pan T S, Tsai P W, Pan J S. Parallelized artificial bee colony with ripple-communication strategy. In: Proceedings of the 4th International Conference on Genetic and Evolutionary Computing. Shenzhen, China: IEEE, 2010. 350−353
    [7] 王大志, 闫杨, 汪定伟, 王洪峰. 基于OpenMP求解无容量设施选址问题的并行PSO算法.北大学学报(自然科学版), 2008, 29(12): 1681-1684

    Wang Da-Zhi, Yan Yang, Wang Ding-Wei, Wang Hong-Feng. OpenMP-based multi-population PSO algorithm to solve the uncapacitated facility location problem. Journal of Northeastern University (Natural Science), 2008, 29(12): 1681-1684
    [8] Roshanzamir M, Balafar M A, Razavi S N. A new hierarchical multi group particle swarm optimization with different task allocations inspired by holonic multi agent systems. Expert Systems With Applications, 2020, 149: Article No. 113292 doi: 10.1016/j.eswa.2020.113292
    [9] Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of the ICNN'95 —— International Conference on Neural Networks. Perth, Australia: IEEE, 1995. 1942−1948
    [10] Črepinšek M, Liu S H, Mernik M. Exploration and exploitation in evolutionary algorithms: A survey. ACM Computing Surveys, 2013, 45(3): Article No. 35
    [11] Finnila A B, Gomez M A, Sebenik C, Stenson C, Doll J D. Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters, 1994, 219(5-6): 343-348 doi: 10.1016/0009-2614(94)00117-0
    [12] 方伟, 孙俊, 谢振平, 须文波. 量子粒子群优化算法的收敛性分析及控制参数研究. 物理学报, 2010, 59(6): 3686-3694 doi: 10.7498/aps.59.3686

    Fang Wei, Sun Jun, Xie Zhen-Ping, Xu Wen-Bo. Convergence analysis of quantum-behaved particle swarm optimization algorithm and study on its control parameter. Acta Physica Sinica, 2010, 59(6): 3686-3694 doi: 10.7498/aps.59.3686
    [13] Sun J, Fang W, Wu X J, Palade V, Xu W B. Quantum-behaved particle swarm optimization: Analysis of individual particle behavior and parameter selection. Evolutionary Computation, 2012, 20(3): 349-393 doi: 10.1162/EVCO_a_00049
    [14] 王鹏, 黄焱, 任超, 郭又铭. 多尺度量子谐振子高维函数全局优化算法. 电子学报, 2013, 41(12): 2468-2473 doi: 10.3969/j.issn.0372-2112.2013.12.023

    Wang Peng, Huang Yan, Ren Chao, Guo You-Ming. Multi-scale quantum harmonic oscillator for high-dimensional function global optimization algorithm. Acta Electronica Sinica, 2013, 41(12): 2468-2473 doi: 10.3969/j.issn.0372-2112.2013.12.023
    [15] 王鹏, 杨云亭. 基于量子自由粒子模型的优化算法框架. 电子学报, 2020, 48(7): 1348-1354 doi: 10.3969/j.issn.0372-2112.2020.07.013

    Wang Peng, Yang Yun-Ting. Optimization algorithm framework based on quantum free particle model. Acta Electronica Sinica, 2020, 48(7): 1348-1354 doi: 10.3969/j.issn.0372-2112.2020.07.013
    [16] Narayanan A, Moore M. Quantum-inspired genetic algorithms. In: Proceedings of the IEEE International Conference on Evolutionary Computation. Nagoya, Japan: IEEE, 1996. 61−66
    [17] Han K H, Kim J H. Genetic quantum algorithm and its application to combinatorial optimization problem. In: Proceedings of the Congress on Evolutionary Computation. CEC00. La Jolla, USA: IEEE, 2000. 1354−1360
    [18] Wang L, Niu Q, Fei M R. A novel quantum ant colony optimization algorithm. In: Proceedings of the International Conference on Life System Modeling and Simulation. Shanghai, China: Springer, 2007. 277−286
    [19] (李元诚, 李宗圃, 杨立群, 王蓓. 基于改进量子差分进化的含分布式电源的配电网无功优化. 自动化学报, 2017, 43(7): 1280-1288)

    Li Yuan-Cheng, Li Zong-Pu, Yang Li-Qun, Wang Bei. An improved quantum differential evolution algorithm for optimization and control in power systems including DGs. Acta Automatica Sinica 2017, 43(7): 1280-1288
    [20] Wang P, Ye X G, Li B, Cheng K. Multi-scale quantum harmonic oscillator algorithm for global numerical optimization. Applied Soft Computing, 2018, 69: 655-670 doi: 10.1016/j.asoc.2018.05.005
    [21] Rosenthal J S. Markov chain Monte Carlo algorithms: Theory and practice. In: Proceedings of the Monte Carlo and Quasi-Monte Carlo Methods 2008. Berlin, Germany: Springer, 2009. 157−169
    [22] 王鹏, 黄焱. 多尺度量子谐振子优化算法物理模型. 计算机科学与探索, 2015, 9(10): 1271-1280 doi: 10.3778/j.issn.1673-9418.1502003

    Wang Peng, Huang Yan. Physical model of multi-scale quantum harmonic oscillator optimization algorithm. Journal of Frontiers of Computer Science and Technology, 2015, 9(10): 1271-1280 doi: 10.3778/j.issn.1673-9418.1502003
    [23] Pharr M, Humphreys G. Physically Based Rendering: From Theory to Implementation. Amsterdam: Elsevier, 2004. 489−531
    [24] Tan Y, Zhu Y C. Fireworks algorithm for optimization. In: Proceedings of the 1st International Conference on Advances in Swarm Intelligence (ICSI). Beijing, China: Springer, 2010. 355−364
    [25] Tan Y, Yu C, Zheng S Q, Ding k. Introduction to fireworks algorithm. International Journal of Swarm Intelligence Research, 2013, 4(4): 39-70 doi: 10.4018/ijsir.2013100103
    [26] Zheng S Q, Janecek A, Tan Y. Enhanced fireworks algorithm. In: Proceedings of the IEEE Congress on Evolutionary Computation. Cancun, Mexico: IEEE, 2013. 2069−2077
    [27] Li J Z, Zheng S Q, Tan Y. Adaptive fireworks algorithm. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC). Beijing, China: IEEE, 2014. 3214−3221
    [28] Zambrano-Bigiarini M, Clerc M, Rojas R. Standard particle swarm optimisation 2011 at CEC-2013: A baseline for future PSO improvements. In: Proceedings of the IEEE Congress on Evolutionary Computation. Cancun, Mexico: IEEE, 2013. 2337−2344
    [29] Sun J, Xu W B, Feng B. A global search strategy of quantum-behaved particle swarm optimization. In: Proceedings of the IEEE Conference on Cybernetics and Intelligent Systems. Singapore: IEEE, 2004. 111−116
    [30] Fang L, Zhi G Z. An improved QPSO algorithm and its application in the high-dimensional complex problems. Chemometrics and Intelligent Laboratory Systems, 2014, 132: 82-90
    [31] Liang J J, Qu B Y, Suganthan P N, Hernández-Díaz A G. Problem Definitions and Evaluation Criteria for the CEC2013 Special Session on Real-parameter Optimization, Technical Report 201212, Computational Intelligence Laboratory, China, 2013
    [32] Li J Z, Tan Y. Loser-out tournament-based fireworks algorithm for multimodal function optimization. IEEE Transactions on Evolutionary Computation, 2018, 22(5): 679-691 doi: 10.1109/TEVC.2017.2787042
    [33] 王柳静, 张贵军, 周晓根. 基于状态估计反馈的策略自适应差分进化算法. 自动化学报, 2020, 46(4): 752-766 doi: 10.16383/j.aas.2018.c170338

    Wang Liu-Jing, Zhang Gui-Jun, Zhou Xiao-Gen. Strategy self-adaptive differential evolution algorithm based on state estimation feedback. Acta Automatica Sinica, 2020, 46(4): 752-766 doi: 10.16383/j.aas.2018.c170338
    [34] Andre J, Siarry P, Dognon T. An improvement of the standard genetic algorithm fighting premature convergence in continuous optimization. Advances in Engineering Software 2001, 32(1): 49-60 doi: 10.1016/S0965-9978(00)00070-3
    [35] Holland J H. Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press, 1975.
    [36] Bertoni A, Dorigo M. Implicit parallelism in genetic algorithms. Artificial Intelligence, 1993, 61(2): 307-314 doi: 10.1016/0004-3702(93)90071-I
    [37] Codling E A, Plank M J, Benhamou S. Random walk models in biology. Journal of the Royal Society Interface, 2008, 5(25): 813-834 doi: 10.1098/rsif.2008.0014
    [38] Shenvi N, Kempe J, Whaley K B. Quantum random-walk search algorithm. Physical Review A, 2003, 67(5): Article No. 052307
  • 加载中
图(7) / 表(2)
计量
  • 文章访问数:  1146
  • HTML全文浏览量:  347
  • PDF下载量:  137
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-04-24
  • 录用日期:  2020-09-22
  • 网络出版日期:  2023-05-29
  • 刊出日期:  2023-07-20

目录

/

返回文章
返回