形式概念分析(FCA)^[1]于1982年由Wille教授提出，它是在形式背景中进行数据分析与规则提取的一个重要工具，通过分析形式背景中概念的结构提出了概念格，从本质上对对象和属性的内在联系进行了描述。Ganter^[2]在其专著中进一步总结了概念格相关知识。目前该理论已在信息检索^[3]、数据挖掘^[4-5]，软件工程^[6]等多个领域取得了广泛应用。

属性约简与规则提取是粗糙集理论中关键的研究方向，同样也是FCA中的重要问题。一个决策形式背景生成的全部形式概念，包括概念之间的关系都会储存在概念格中，这使得概念格的分析过程变得极为困难。因此，决策形式背景研究的重要课题之一就是保持决策不变进行属性约简，从而使形式背景中的隐藏知识更容易被发掘，即更易获取决策规则。越来越多的学者开始深入研究决策形式背景的属性约简与规则提取问题。

2009年，Wu^[6]研究了保持概念格的粒结构不变的属性约简与规则提取，并给出具体算法。Li等^[7-9]提出了一种新的决策形式背景知识约简框架，给出约简算法，且在决策形式背景研究了保持决策规则不变的属性约简。Li等^[10]研究了基于同余关系的不协调决策形式背景的属性约简。Li等^[11]提出了基于最大规则的决策形式背景中的新型属性约简。Chen^[12-13]提出了一种大数据模型下的快速属性约简模型，并结合实例分析其算法复杂度。Yang^[14]基于蕴涵映射对实数集决策形式背景中的属性约简和规则提取问题进行研究。Qi^[15]从多角度讨论了两类三支概念格与传统概念格之间的联系, 并给出了在经典概念格基础上构造三支概念格的算法。Zhang等^[16]利用概念格提出了一种基于案例的层次化分类器。Zhang等^[17]研究了模糊决策格值信息系统上的近似约简与规则提取。张^[18-19]叙述了信息系统上的知识发现与知识约简, 提出了协调近似表示空间上的规则融合方法。

目前在概念格领域已取得诸多成果，但仍存在众多问题有待解决。比如基于等价关系的粒协调决策形式背景的属性约简问题，利用确定性规则获取全部规则的具体途径，本文将进一步讨论这些问题。

1 预备知识

定义1^[6] 　设三元组 ${{F}} = ({{U}},{{A}},{{I}})$ 是形式背景， ${{U}} = \{ {x_1},{x_2}, \cdots ,{x_n}\} $ ， ${{A}} = \{ {a_1},{a_2}, \cdots ,{a_m}\} $ ， ${{I}} \subseteq {{U}} \times {{A}}$ 。如果 $(x,a) \in {{I}}$ ，则称 $x$ 具有属性 $a$ 。用 ${{P}}({{U}})$ 表示 ${{U}}$ 的幂集， ${{P}}({{A}})$ 表示 ${{A}}$ 的幂集。 $\forall {{X}} \in {{P}}({{U}})$ ， $ {{B}} \in {{P}}({{A}})$ ，定义：

$ {{{X}}^*} = \{ a \in {{A}}: \forall x \in {{X}}, (x,a) \in {{I}}\} $

(1)

$ {{{B}}^ \triangleleft } = \{ x \in {{U}}: \forall a \in {{B}}, (x,a) \in {{I}}\} $

(2)

定义2^[6] 　对于形式背景 ${{F}} = ({{U}},{{A}},{{I}})$ ，若二元组 $({{X}},{{B}}) \in {{P}}({{U}}) \times {{P}}({{A}})$ 满足 ${{X}}^* = {{B}}$ 且 ${{{B}}^ \triangleleft } = {{X}}$ ，则 $({{X}},{{B}})$ 称为形式概念或概念。其中 ${{X}}$ 是概念 $({{X}},{{B}})$ 的外延， ${{B}}$ 是概念 $({{X}},{{B}})$ 的内涵。

定义3^[6] 　对于形式背景 ${{F}} = ({{U}},{{A}},{{I}})$ ， ${{C}} \subseteq $ $ {{A}}$ ，可以得到形式背景 ${{{F}}_{{C}}} = ({{U}},{{C}},{{{I}}_{{C}}})$ ，F_C称为 ${{F}}$ 的子背景，其中 ${{{I}}_{{C}}}{\rm{ = }}{{I}} \cap ({{U}} \times {{C}})$ 。

则对 ${{X}} \subseteq {{U}}$ ，定义映射 $^{*{{C}}}:{{P}}({{U}}) \to {{P}}({{C}}):{{{X}}^{*{{C}}}} = $ $ \{ a \in {{C}}: \forall x \in {{X}}, (x,a) \in {{I}}\} $ 。特别地，当 ${{X}} = \{ x\} $ ， $ {{C}} = \{ a{\rm{\} }}$ 时有

$ {x^{{\rm{*\{ a\} }}}} = \left\{ {\begin{array}{*{20}{c}} {\{ a\} ,\quad (x,a) \in {{I}} }\\ { \text{Ø} , \quad (x,a) \notin {{I}} } \end{array}} \right. $

(3)

定义4^[19] 　设 ${{{V}}_l}{\rm{(}}l \leqslant {{m) }}$ 是非空有限集，记

$ \begin{array}{l} {{P}}{\rm{ = \{ }}{{E}}{\rm{ = (}}{{{E}}_{\rm{1}}}{\rm{,}}{{{E}}_{\rm{2}}}{\rm{,}} \cdots {\rm{ ,}}{{{E}}_m}{\rm{) }}:{{{E}}_l} \leqslant {{{V}}_l}{\rm{(}}l \leqslant m{\rm{)\} }}\subseteq \\ \;\;\;{{P}}({{{E}}_{\rm{1}}}{\rm{)}} \times {{P}}({{{E}}_{\rm{2}}}{\rm{)}} \times \cdots \times ({{{E}}_m}{\rm{)}} \end{array} $

称 ${{P}}$ 为集合向量空间。对于 ${{P}}$ 中的两个集合向量 ${{E}}{\rm{ = (}}{{{E}}_1}{\rm{,}} \cdots {\rm{ ,}}{{{E}}_m}{\rm{) }}$ ， ${{S}}{\rm{ = (}}{{{S}}_{\rm{1}}}{\rm{,}} \cdots {\rm{ ,}}{{{S}}_m}{\rm{) }}$ ，如果 $\forall l \leqslant m$ ，均有 ${{{E}}_l} \leqslant {{{S}}_l}$ ，则记 ${{E}} \leqslant {{S}}$ ，且 ${\rm{(}}{{P}}{\rm{,}} \leqslant {\rm{)}}$ 为偏序集。

定义5^[19] 　设 ${\rm{(}}{{P}}{\rm{,}} \leqslant {\rm{)}}$ 为偏序集，称 ${{D}}:{{{P}}^2} \to $ [0,1]为集值向量包含度，满足下列条件：

1) $ {\rm{0}} \leqslant {{D(S/E)}} \leqslant 1$ ；

2) ${{E}} \leqslant {{S}}$ 时， ${{D}}({{S}}/{{E}}) = 1$ ；

3) ${{E}} \leqslant {{S}} \leqslant {{G}}$ 时， ${{D}}({{E}}/{{G}}) \leqslant {{D}}({{E}}/{{S}})$ 。

2 基于等价关系的粒协调决策形式背景的属性约简

以往对决策形式背景进行讨论时通常会分别构造条件概念格与决策概念格，利用两者的序关系来定义形式背景的协调性。本节利用等价关系对对象集进行划分，从而得到对应的决策类，可以在保持对象的决策不变的前提下删除冗余属性。

设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 为一个决策形式背景， ${{A}}$ 为条件属性集， ${{D}}$ 为决策属性集，并且 ${{A}} \cap {{D}} = \text{Ø}$ ， $ {{I}} \subseteq {{U}} \times {{A}}$ 。定义 ${{{R}}_{{D}}} = \{ (x,y) \in {{U}} \times {{U}}: {d_l}(x) = {d_l}(y) (\forall {d_l} \in$ $ {{D}})\} $ ，则由上述等价关系可产生 ${{U}}$ 上的一个划分：

${{U}}/{{{R}}_{{D}}} = \{ {[x]_{{D}}}: x \in {{U}}\} {\rm{ = \{ }}{{{D}}_1}{\rm{,}}{{{D}}_2}, \cdots ,{{{D}}_r}{\rm{\} }}$

其中

${[x]_D}{\rm{ = \{ }}y \in {{U}}: (x,y) \in {{{R}}_D}\} $

如果 $\forall x \in {{U}}$ ，均满足 ${x^{*A \triangleleft }} \subseteq {[x]_D}$ ，则称决策形式背景 ${{F}}$ 是粒协调的。

定义6　设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 为粒协调决策形式背景，对 ${{B}} \subseteq {{A}}$ ，如果 $\forall x \in {{U}}$ ，都有 ${x^{*{{B}} \triangleleft }} \subseteq {[x]_{{D}}}$ ，则称 ${{B}}$ 是 ${{F}}$ 的一个粒协调集。进一步，如果不存在 ${{C}} \subset {{B}}$ ，使得 $\forall x \in {{U}}$ 都有 ${x^{*{{C}} \triangleleft }} \subseteq {[x]_{{D}}}$ ，则 ${{B}}$ 是 ${{F}}$ 的粒约简。

注：1)对粒协调决策形式背景 ${{F}}$ 来说，必存在粒约简。如用 ${\rm{\{ }}{{{B}}_i}:i \leqslant l{\rm{\} }}$ 表示 ${{F}}$ 所有的粒约简，则 ${{B}} = \bigcap\limits_{i = 1}^l {{{{B}}_i}} $ 为 ${{F}}$ 的核心， ${{B}}$ 中的元素称为核心元素或绝对必要属性。

2)对于 $x$ ， $y \in {{{D}}_j}$ ， $\forall {d_l} \in {{D}}$ 有 ${d_l}(x) = {d_l}(y)$ ，显然决策类中所有对象决策值相同，记为 ${d_l}({{{D}}_j})$ 。称 ${{{T}}_j} = $ $ \{ {d_1}({{{D}}_j}), {d_2}({{{D}}_j}),\cdots ,{d_{|{{D}}|}}({{{D}}_j})\} $ 为决策类 ${{{D}}_j}$ 的决策值。

设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 是一个粒协调决策形式背景， ${{B}} \subseteq {{A}}$ ，记

$ {{{R}}_{{B}}} = \{ ({x_i},{x_j}) \in {{U}} \times {{U}}:x_i^{*\{ a\} } \subseteq x_j^{*\{ a\} },\forall a \in {{B}}\} $

(4)

则容易证明：

1) $ x_i^{*B \triangleleft } = \{ {x_j} \in {{U}}:({x_i},{x_j}) \in {{{R}}_B}\}$ ；

2) $x_i^{*B \triangleleft } \subseteq {[{x_i}]_D} \Leftrightarrow {{{R}}_B} \subseteq {{{R}}_D}$ ，即 ${{B}}$ 是粒协调集等价于 ${{{R}}_B} \subseteq {{{R}}_D}$ 。

定义7　设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 是一个粒协调决策形式背景， $x,y \in {{U}}$ ， $x$ 与 $y$ 的辨识属性集定义如下：

$ {{{D}}_d}(x,y){\rm{ = }}\left\{ {\begin{array}{*{20}{c}} {\{ a \in {{A}}:x_{}^{*\{ a\} }\not \subseteq y_{}^{*\{ a\} }\} ,}& {{d_l}(x) \ne {d_l}(y)}\\ {\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\text{Ø} ,}& {\text{其他}} \end{array}} \right. $

(5)

且 ${{ {{D}}}^*} = \{ {{{D}}_d}(x,y)\mid x,y \in {{U}}\} $ 为 ${{F}}$ 的辨识矩阵。

由定义7可知，以下性质显然成立：

1) $ {{{D}}_d}(x,x) = \text{Ø}$ ；

2) $ {{{D}}_d}(x,y) \bigcap {{{{D}}_d}} (y,x) = \text{Ø}$ 。

定理1　设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 是一个粒协调决策形式背景， ${{B}} \subseteq {{A}}$ 。则 ${{B}}$ 是 ${{F}}$ 的粒协调集，当且仅当 ${{{D}}_d}(x,y) \ne \text{Ø}$ 时有 ${{B}} \bigcap {{{{D}}_d}(x,y)} \ne \text{Ø}$ 。

证明　 $\left( { \Rightarrow } \right)$ 当 ${{{D}}_d}(x,y) \ne \text{Ø}$ 时，由定义7可知， $\forall {d_l} \in {{D}}$ 均满足 ${d_l}(x) \ne {d_l}(y) $ ，即 $(x,y)\not \in {{{R}}_{{D}}}$ 。而 ${{B}}$ 是 ${{F}}$ 的粒协调集，则有 ${{R}}_{{B}}^{} \subseteq {{{R}}_{{D}}}$ 。因此 $(x,y) \notin {{R}}_{{B}}^{}$ ，故必存在 $b \in {{B}}$ 使得 $x_{}^{*\{ b\} }\not \subseteq y_{}^{*\{ b\} }$ 。所以 $b \in {{{D}}_d}(x,y)$ 。因而 ${{B}}\bigcap {{{{D}}_d}(x,y)} \ne \text{Ø}$ 。

$\left( \Leftarrow \right)$ 若 ${{{D}}_d}(x,y) \ne \text{Ø}$ ，则 $\forall {d_l} \in {{D}}$ ， ${d_l}(x) \ne {d_l}(y)$ ，即 $(x,y)\not \in {{{R}}_{{D}}}$ 。故 ${{B}} \bigcap {{{{D}}_d}(x,y)} \ne \text{Ø}$ ，一定存在 $b \in {{B}},$ 使得 $b \in {{{D}}_d}(x,y)$ ，则有 $x_{}^{*\{ b\} }\not \subseteq y_{}^{*\{ b\} }$ ，从而 $(x,y) \notin {{R}}_B^{}$ 。当 $(x,y)\not \in {{{R}}_{{D}}}$ 时 $(x,y) \notin {{R}}_B^{}$ ，故 ${{{R}}_B} \subseteq {{{R}}_{{D}}}$ 。综上， ${{B}}$ 是 ${{F}}$ 的粒协调集。

定理2　设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 是一个粒协调决策形式背景， $a \in {{A}}$ ，则 $a$ 是 ${{F}}$ 的核心属性，等价于存在 $x$ ， $y \in {{U}}$ 使得 ${{{D}}_d}(x,y{\rm{) = \{ }}a{\rm{\} }}$ 。

证明　 $\left( \Rightarrow \right)$ 如果条件属性 $a \in {{A}}$ 是 ${{F}}$ 的核心属性，则 ${{A}} - {\rm{\{ }} a {\rm{\} }}$ 不可能是 ${{F}}$ 的粒约简，即 ${{R}}_{{{A}} - \{ a\} }^{} \nsubseteq $ ${{{R}}_{{D}}} $ 。故存在 $x$ ， $y \in {{U}}$ ，使得 $(x,y)\not \in {{{R}}_{{D}}}$ 时有 $(x,y) \in {{{R}}_{{{A}} - \{ a\} }}$ 。此时 ${d_l}(x) \ne {d_l}(y)$ 。又易证 $x_{}^{*\{ a\} }\not \subseteq y_{}^{*\{ a\} }$ ，由定义7可知 $a \in {{{D}}_d}(x,y)$ ，即 $\exists x,y \in {{U}}$ 使得 ${{{D}}_d}(x,y{\rm{) = \{ }}a{\rm{\} }}$ (事实上，如 $x_{}^{*\{ a\} } \subseteq y_{}^{*\{ a\} }$ ，则由 $(x,y) \in {{{R}}_{{{A}} - \{ a\} }}$ 可知 $(x,y) \in {{{R}}_{{A}}}$ 。又 ${{F}}$ 是一个粒协调决策形式背景，所以 ${{{R}}_{{A}}} \subseteq {{{R}}_{{D}}}$ ，即 $\forall {d_l} \in {{D}}$ 均满足 ${d_l}(x) = {d_l}(y) $ ，这与 ${d_l}(x) \ne {d_l}(y)$ 矛盾，所以 $x_{}^{*\{ a\} }\not \subseteq y_{}^{*\{ a\} }$ )。

$\left( \Leftarrow \right)$ 如果 ${D_d}(x,y{\rm{) = \{ }}a{\rm{\} }}$ ，定义7可知 ${d_l}(x) \ne {d_l}(y)$ $x_{}^{*\{ a\} }\not \subseteq y_{}^{*\{ a\} }$ 并且任取 $b \in {{A}} - a,$ 必有 $x_{}^{*\{ b\} } \subseteq y_{}^{*\{ b\} }$ 。因此 $(x,y)\not \in {{{R}}_D}$ 且 $(x,y) \in {{{R}}_{{{A}} - \{ a\} }}$ 。故可得 ${{{R}}_{{{A}} - \{ a\} }}\not \subseteq {{{R}}_D}$ ，即 ${{A}} - {\rm{\{ }} a {\rm{\} }}$ 不是 ${{F}}$ 的粒约简， $a$ 是 ${{F}}$ 的核心属性。

定义8　设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 是一个粒协调决策形式背景， $x,y \in {{U}}$ ， ${{{D}}_d}(x,y) \ne \text{Ø}$ 。记

$ {{M}}{\rm{ = }} \wedge ( \vee {{{D}}_d}(x,y)) = \wedge ( \vee \{ {a_l}:{a_l} \in {{{D}}_d}(x,y)\} ) $

(6)

基于文献[18]可知，如果 ${{B}}_k^q = \{ {a_{{i_t}}}:t \leqslant {q_k}\} $ 中没有重复元素，则

$ {{M}} = \vee _{k = 1}^p( \wedge _{t = 1}^{{q_k}}{a_{{i_t}}}) $

(7)

称为 ${{F}}$ 的极小析取范式。 ${{{B}}_k} (k \leqslant p)$ 是 ${{F}}$ 的所有粒约简的集合，具体算法如下：

算法 1 粒协调决策形式背景的属性约简算法

输入　粒协调决策形式背景F=(U，A，I，D，G)

输出　 B (粒约简集)

1) for 1≤i≤|U| and 1≤s≤|A|

2) if $ \left( {{x_i},{a_s}} \right) \in {{I}},{x_i}^{*\left\{ {{a_s}} \right\}} = {a_s}$

3) else $ {x_i}^{*\left\{ {{a_s}} \right\}} = \text{Ø}$

4) initialize $ {{{D}}_d}\left( {{x_i},{x_j}} \right) = \text{Ø}$

5) for 1≤s≤|A| and 1≤l≤|D| do

6)　if $ {x_i}^{*\left\{ {{a_s}} \right\}}\not \subseteq {x_j}^{*\left\{ {{a_s}} \right\}}\;\;\;{\rm{and}}\;\;{d_l}\left( {{x_i}} \right) \ne {d_l}\left( {{x_j}} \right)$ then

7) 　　 $ {{{D}}_d}\left( {{x_i},{x_j}} \right) \leftarrow {{{D}}_d}\left( {{x_i},{x_j}} \right) \vee {a_s}$

8) 　end if

9) end for

10) initialize $ {{B}}= \text{Ø}$

11) for 1≤i≤|U|, 1≤j≤|U| do

12) 　 $ {{B}} = {{B}} \wedge {{{D}}_d}\left( {{x_i},{x_j}} \right)$

13) end for

14) compute $ {{B}} = \vee _{m = 1}^p\left( { \wedge _{q = 1}^{{s_i}}{a_q}} \right)$

15) return B

例1　 表1给出了一个决策形式背景，其中对象集 ${{U}} = \{ {x_1},{x_2},{x_3},{x_4},{x_5},{x_6},{x_7}{\rm{\} }}$ ， ${{D}} = \{ d{\rm{\} }}$ 为决策属性集。 ${{A}} = \{ {a_1},{a_2},{a_3},{a_4},{a_5},{a_6},{a_7}{\rm{,}}{a_8}{\rm{\} }}$ 为条件属性集。

计算可知：

$ \qquad\begin{aligned} & x_1^{* \triangleleft } = \{ {x_1},{x_2},{x_3}\} = {[{x_1}]_D}, x_2^{* \triangleleft } = \{ {x_2},{x_3}\} \subseteq {[{x_2}]_D} = {[{x_1}]_D}\\ & x_3^{* \triangleleft } = \{ {x_3}\} \subseteq {[{x_3}]_D} = {[{x_1}]_D}, x_4^{* \triangleleft } = \{ {x_4}\} \subseteq \{ {x_4},{x_7}\} = {[{x_4}]_D}\\ & x_5^{* \triangleleft } = \{ {x_5},{x_6}\} \subseteq \{ {x_5},{x_6}\} = {[{x_5}]_D}\\ & x_6^{* \triangleleft } = \{ {x_6}\} \subseteq {[{x_6}]_D} = {[{x_5}]_D},x_7^{* \triangleleft } = \{ {x_7}\} \subseteq {[{x_7}]_D} = {[{x_4}]_D} \end{aligned} $

可知 ${{F}}$ 为粒协调的，其辨识矩阵如表2所示。由布尔方法可获取 ${{F}}$ 的所有粒约简，具体过程如下：

$ \begin{array}{l} {{M}} = \wedge ( \vee {D_d}(x,y)) \\ \;\;\;\;{\rm{ = }}{a_1} \wedge {a_4} \wedge {a_6} \wedge {a_8} \wedge ({a_3} \vee {a_5}) \\ \;\;\;\;{\rm{ = }}({a_1} \wedge {a_4} \wedge {a_6} \wedge {a_8} \wedge {a_3}) \vee ({a_1} \wedge {a_4} \wedge {a_6} \wedge {a_8} \wedge {a_5})\\ \end{array} $

故该形式背景存在两个粒约简，即B₁= {a₁, ${\rm{ \ }}{a_3},{a_4},$ ${a_6},{a_8}{\rm{\} }}$ 与 ${{{B}}_2} = \{ {a_1},{a_4},{a_5},{a_6},{a_8}{\rm{\} }}$ ， ${{F}}$ 的核心属性为 ${a_1},$ ${a_4},{a_6}$ 与 ${a_8}$ 。

3 基于等价关系的粒协调决策形式背景上的规则融合

本节给出粒协调决策形式背景中决策规则及最优决策规则的定义，进一步讨论粒协调决策形式背景上规则融合算法，并给出相关实例。

定义9　设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 是一个粒协调决策形式背景，称 $({{X}},{{Y}} \in {{L}}({{U}},{{A}}, {{I}})$ 为条件概念。决策类 ${{{D}}_j}$ 与其决策值 ${{{T}}_j}$ 构成的二元组 $({{{D}}_j},{{{T}}_j})$ 称为决策概念。如果 ${{X}} \ne \text{Ø} $ ， ${{Y}} \ne \text{Ø} $ ，并且有 ${{X}} \subseteq {{{D}}_j}$ ，则称 $\left( {{{X}},{{Y}}} \right) \Rightarrow ({{{D}}_j},{{{T}}_j})$ 为决策形式背景的粒决策规则。所有粒决策规则的集合记为 $\Im ({{F}})$ 。

对于粒协调决策形式背景来说，必有 ${x_i}^{*{{A}} \triangleleft } \subseteq $ ${[{x_i}]_{{D}}} $ 。于是可得到 ${\rm{|}}{{U}}{\rm{|}}$ 条确定性规则。显然还存在一些不确定性规则，下文给出用 ${\rm{|}}{{U}}{\rm{|}}$ 条确定性规则得到全部规则的两种规则融合方法。

设 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 是一个粒协调决策形式背景， $\forall x \in {{U}}$ ， ${a_l} \in {{A}}$ ，定义

${f_l}({x_i}) = \left\{ {\begin{array}{*{20}{c}} {1,\quad ({x_i},{a_l}) \in {{I}}} \\ { 0,\quad ({x_i},{a_l}) \notin {{I}}} \end{array}} \right.$

$\forall {{B}} \in {{A}}$ ， ${a_l} \in {{A}}$ ，定义 ${v_l}({{B}}) = \left\{ {\begin{array}{*{20}{c}} {1,\quad {a_l} \in {{B}}\;\;\;\; } \\ { 0,\quad {a_l}\not \in {{B}}{\text{。}}} \end{array}} \right.$

定义10　设 $({{P}}, \leqslant )$ 是偏序集，对于 ${{P}}$ 中的两个集合向量 ${{E}}$ 和 ${{S}}$ ，定义包含度为

$ {{D}}({{S}}/{{E}}) = \sum\limits_{i = 1}^m {\frac{{\left| {{{{S}}_l}} \right|}}{{\sum\limits_{i = 1}^m {\left| {{{{S}}_i}} \right|} }}} {\chi _{{{{F}}_l}}}({{{E}}_l}) $

(8)

其中 $ {\chi _{{{{F}}_l}}}({{{E}}_l}){\rm{ = }}\left\{ {\begin{array}{*{20}{c}} {1,\quad {{{E}}_l} \subseteq {{{S}}_l}\;\;\;\;} \\ {0,\quad {{{E}}_l}\not \subseteq {{{S}}_l}{\text{。}}} \end{array}} \right.$

3.1 乐观规则融合

1)由 ${{{R}}_D}$ 对 ${{U}}$ 进行划分，得到

${{U}}/{{{R}}_{{D}}} = \{ {{{D}}_1},{{{D}}_2}, \cdots ,{{{D}}_r}\} $

2)对于决策类 ${{{D}}_j}(j \leqslant r)$ ，记

${{{M}}_j} = \{ (\{ {f_1}({x_i})\} ,\{ {f_2}({x_i})\} , \cdots ,\{ {f_m}({x_i})\} )\left| {x_i^{* \triangleleft } \subseteq {{{D}}_j}} \right.\} (j \leqslant r)$

3)将 ${{{M}}_j}$ 中的向量取并运算，即每个分量取并运算，得到 ${{{S}}_j} = ({{S}}_1^j,{{S}}_2^j, \cdots ,{{S}}_m^j) (j \leqslant r)$ 。

4)对于概念 $({{X}},{{B}}) \in {{L}}({{U}},{{A}},{{I}})$ ，记

${{E}} = (\{ {v_1}\} ,\{ {v_2}\} , \cdots ,\{ {v_m}\} )$

计算 ${{D}}({{{S}}_j}/{{E}})$ ，若 ${{D}}({{{S}}_{{j_0}}}/{{E}}){\rm{ = }}\mathop {\max }\limits_{j \leqslant r} {{D}}({{{S}}_j}/{{E}})$ ，则有：

${\rm{If}}\;{{B}}, {\rm{then}} \;{{{T}}_{{j_o}}} \;\;\;({{D}}({{{S}}_{{j_o}}}/{{E}}))$

算法 2　粒协调决策形式背景中乐观规则融合算法

输入　 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$

输出　 R(决策规则)

1) for 1≤t≤|D| do

2) 　 $ {{U}}/{{{R}}_{{D}}} = \left\{ {{{{D}}_1},{{{D}}_2}, \cdots ,{{{D}}_r}} \right\} = \left\{ {{{\left[ x \right]}_{{D}}}:x \in {{U}}} \right\}$

3) end for

4) for $ {{{D}}_j}\left( {j \leqslant r} \right),\;\;{\rm{do}}$

5) $ {{{M}}_j} = \left\{ {\left( {\left\{ {{f_1}\left( {{x_i}} \right)} \right\},\left\{ {{f_2}\left( {{x_i}} \right)} \right\}, \cdots ,\left. {\left\{ {{f_{|{{A}}|}}\left( {{x_i}} \right)} \right\}} \right)|} \right.x_i^{* \triangleleft } \subseteq {{{D}}_j}} \right\}$

6) compute ${{{S}}_j} \!=\! \left\{ {\left( { \vee \left\{ {{f_1}\left( {{x_i}} \right)} \right\}, \!\cdots\! , \vee \left\{ {{f_{|{{A}}|}}\left( {{x_i}} \right)} \right\}} \right)} \right.$ $\left. {| x_i^{* \triangleleft } \subseteq {{{D}}_j}} \right\}$

7) for $ \left( {{{X}},{{B}}} \right) \in {{L}}\left( {{{U}},{{A}},{{I}}} \right)$ do

8) 　 $ {{E}} = \left( {\left\{ {{v_1}\left( {{B}} \right)} \right\},\left\{ {{v_2}\left( {{B}} \right)} \right\}, \cdots ,\left\{ {{v_{|{{A}}|}}\left( {{B}} \right)} \right\}} \right)$

9) end for

10) compute D(S_j/E)

11) if D(S_jo/E)=maxD(S_j/E) ，then

12) 　 $ {{{{R}}:}}\;{{B}} \Rightarrow {{{T}}_{{j_o}}}\left( {{{D}}\left( {{{{S}}_{{j_o}}}/{{E}}} \right)} \right)$

13) end if

14) return R

例2　接例1, ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$ 中的所有条件概念计算如下：

$\!\!\!\!\begin{array}{l} ({\rm{\{ }}{x_1},{x_2},{x_3}\},\!\{ {a_1},{a_6}{\rm{\} }});({\rm{\{ }}{x_2},\!{x_3}\} ,\!\{ {a_1},\!{a_6},{a_7}\} );(\{ {x_3}\} ,\{ {a_1},\!{a_2},\!{a_6},\!{a_7}\} )\\ ({\rm{\{ }}{x_4}{\rm{\} }},\{ {a_2},{a_6},{a_7},{a_8}\} );(\{ {x_5},{x_6}\} ,\{ {a_1},{a_3},{a_5}\} )\\ ({\rm{\{ }}{x_6}{\rm{\} }},{\rm{\{ }}{a_1}{\rm{,}}{a_2},{a_3},{a_5}{\rm{\} }});(\{ {x_7}\} ,\{ {a_2},{a_3},{a_4}\} )\\ (\{ {x_1},{x_2},{x_3},{x_4}\} ,\{ {a_6}\} );(\{ {x_1},{x_2},{x_3},{x_5},{x_6}\} ,\{ a { _1}\} )\\ \{ {x_2},{x_3},{x_4}\} ,\{ {a_6},{a_7}\} );(\{ {x_3},{x_4}\} ,{\rm{\{ }}{a_2},{a_6},{a_7}{\rm{\} }})\\ (\{ {x_3},{x_6}\} ,{\rm{\{ }}{a_1},{a_2}{\rm{\} }});(\{ {x_3},{x_4},{x_6},{x_7}\} ,{\rm{\{ }}{a_2}{\rm{\} }});({x_{567}},\{ {a_3}\} )\\ (\{ {x_6},{x_7}\} ,{\rm{\{ }}{a_2},{a_3}{\rm{\} }});(U,\text{Ø} );(\text{Ø} ,{{A}}) \end{array} $

为使讨论更具实际意义，在下列讨论中我们忽略 $({{U}},\text{Ø} )$ 、 $(\text{Ø} ,{{A}})$ 。

计算可知：

${{U}}/{{{R}}_{{D}}} = \{ \{ {x_1},{x_2},{x_3}\} ,\{ {x_4},{x_7}\} ,\{ {x_5},{x_6}\} \} $

则所有决策概念计算如下：

$ ({\rm{\{ }}{x_1},{x_2},{x_3}{\rm{\} }},{\rm{\{ }}1{\rm{\} }});({\rm{\{ }}{x_4},{x_7}{\rm{\} }},{\rm{\{ }}3{\rm{\} }});({\rm{\{ }}{x_5},{x_6}{\rm{\} }},{\rm{\{ }}2{\rm{\} }}) $

记

$ {{{D}}_1} = \{ {x_1},{x_2},{x_3}\} ,\;{{{D}}_2} = \{ {x_4},{x_7}\} ,\;{{{D}}_3} = \{ {x_5},{x_6}\} $

则有

$\begin{array}{l}{{{M}}_1} = \{ ({\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }}),\\[-1pt] \;\;\;\;\;\;\;\;\;({\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }}),\\[-1pt] \;\;\;\;\;\;\;\;\;({\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }}){\rm{\} }} \end{array}$

$\begin{array}{l} {{{M}}_2} = \{ ({\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }}),\\[-1pt] \;\;\;\;\;\;\;\;\;({\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }})\} \end{array}$

$\begin{array}{l} {{{M}}_3} = \{ ({\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }}),\\[-1pt] \;\;\;\;\;\;\;\;\;({\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}1{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }},{\rm{\{ }}0{\rm{\} }})\} \end{array}$

故

${{{S}}_1} = (\{ 1\} ,\{ 0,1\} ,\{ 0\} ,\{ 0\} ,\{ 0\} ,\{ 1\} ,\{ 0,1\} ,\{ 0\} )$

${{{S}}_2} = (\{ 0\} ,\{ 1\} ,\{ 0,1\} ,\{ 0,1\} ,\{ 0\} ,\{ 0 ,1\} ,\{ 0 ,1\} ,\{ 0 ,1\} )$

${{{S}}_3} = (\{ 1\} ,\{ 0,1\} ,\{ 1\} ,\{ 0\} ,\{ 1\} ,\{ 0\} ,\{ 0{\rm{\} }},\{ 0\} )$

对于条件概念 $({\rm{\{ }}{x_1},{x_2},{x_3},{x_4}{\rm{\} }},{\rm{\{ }}{a_6}{\rm{\} }})$ 来说，有 E = $ (\{ 0\} ,\{ 0\} ,\{ 0\} ,\{ 0\} ,\{ 0\} ,\{ 1\} ,\{ 0\} ,\{ 0\} )$ 。

计算可知：

$\begin{array}{l} \;\;{{D}}({{{S}}_1}/{{E}}) = 0.9\\ {{D}}({{{S}}_2}/{{E}}) \approx 0.92\\ \;{{D}}({{{S}}_3}/{{E}}) \approx 0.56 \end{array}$

综上可得规则“ ${\rm{\{ }}{a_6}{\rm{\} }} \Rightarrow d = 3 (0.92)$ ”，此处0.92为该方法中此条规则的可信度。由上述方式可获取规则：

$\{ {a_1},{a_6}{\rm{\} }} \Rightarrow d = 1 (1);$ $\{ {a_1},{a_6},{a_7}{\rm{\} }} \Rightarrow d = 1 (1)$

$\{ {a_1},{a_2},{a_6},{a_7}\} \Rightarrow d = 1 (1);$ $\{ {a_2},{a_6},{a_7},{a_8}\} \Rightarrow d = 2(1)$

$\{ {a_1},{a_3},{a_5}\} \Rightarrow d = 3 (1);$ ${\rm{\{ }}{a_1}{\rm{,}}{a_2},{a_3},{a_5}{\rm{\} }} \Rightarrow d = 3(1)$

$\{ {a_2},{a_3},{a_4}\} \Rightarrow d = 2 (1);$ $\{ {a_6}\} \Rightarrow d = 2 (0.92)$

$\{ {a_1}\} \Rightarrow d = 1 (0.9); $ $\{ {a_6},{a_7}\} \Rightarrow d = 2 (0.92)$

${\rm{\{ }}{a_2},{a_6},{a_7}{\rm{\} }} \Rightarrow d = 2 (1);$ ${\rm{\{ }}{a_1},{a_2}{\rm{\} }} \Rightarrow d = 2 \;(0.92)$

${\rm{\{ }}{a_2}{\rm{\} }} \Rightarrow d = 2 (1);$ ${\rm{\{ }}{a_3}{\rm{\} }} \Rightarrow d = 2 (0.92)$

$ {\rm{\{ }}{a_2},{a_3}{\rm{\} }} \Rightarrow d = 2 (1) $

由定义9可知，粒决策规则如下：

$\{ {a_1},{a_6}{\rm{\} }} \Rightarrow d = 1 (1);$ $\{ {a_1},{a_6},{a_7}{\rm{\} }} \Rightarrow d = 1 (1)$

$\{ {a_1},{a_2},{a_6},{a_7}\} \Rightarrow d = 1(1);$ $\{ {a_2},{a_6},{a_7},{a_8}\} \Rightarrow d = 2(1)$

$\{ {a_1},{a_3},{a_5}\} \Rightarrow d = 3 (1)$

显然粒决策规则在乐观规则融合方法中同样为确定性规则。

3.2 悲观规则融合

1)由 ${{{R}}_{{D}}}$ 对 ${{U}}$ 进行划分，得到

${{U}}/{{{R}}_{{D}}} = \{ {{{D}}_1},{{{D}}_2}, \cdots ,{{{D}}_r}\} $

2)对于决策类 ${{{D}}_j}(j \leqslant r)$ ，记

$ {{{M}}_j} = \{ (\{ {f_1}({x_i})\} ,\{ {f_2}({x_i})\} , \cdots ,\{ {f_m}({x_i})\} )\left| {x_i^{* \triangleleft } \subseteq {{{D}}_j}} \right.\} (j \leqslant r) $

3)将 ${{{M}}_j}$ 中的向量取最大值，即每个分量取最大值，得到 ${{{L}}_j} = ({{L}}_1^j,{{L}}_2^j, \cdots ,{{L}}_m^j) (j \leqslant r)$ 。

4)对于概念 $({{X}},{{B}}) \in {{L}}({{U}},{{A}},{{I}})$ ，记

${{E}} = (\{ {v_1}\} ,\{ {v_2}\} , \cdots ,\{ {v_m}\} )$

计算 ${{D}}({{{L}}_j}/{{E}})$ ，若 ${{D}}({{{L}}_{{j_0}}}/{{E}}){\rm{ = }}\mathop {\max }\limits_{j \leqslant r} {{D}}({{{L}}_j}/{{E}})$ ，则有：

${\rm{If}} \;{{B}}, {\rm{then}} \;{{{T}}_{{j_o}}} ({{D}}({{{L}}_{{j_o}}}/{{E}}))$

粒决策规则在该方法中可信度并不一定为1，且两种规则融合方式获取的规则并不一致。下面给出具体算法。

算法 3　粒协调决策形式背景中悲观规则融合算法

输入　 ${{F}} = ({{U}},{{A}}, {{I}},{{D}},{{G}} )$

输出　 R(决策规则)

1) for 1≤t≤|D|

2) $ {{U}}/{{{R}}_{{D}}} = \left\{ {{{{D}}_1},{{{D}}_2}, \cdots ,{{{D}}_r}} \right\} = \left\{ {{{\left[ x \right]}_{{D}}}:x \in {{U}}} \right\}$

3) for $ {{{D}}_j}\left( {j \leqslant r} \right),\;\;{\rm{do}}$

4) $ {{{M}}_j} = \left\{ {\left( {\left\{ {{f_1}\left( {{x_i}} \right)} \right\},\left\{ {{f_2}\left( {{x_i}} \right)} \right\}, \cdots ,\left. {\left\{ {{f_{|{{A}}|}}\left( {{x_i}} \right)} \right\}} \right)|} \right.x_i^{* \triangleleft } \subseteq {{{D}}_j}} \right\}$

5) $ {{{L}}_j} \!=\! \Big\{ {\left( {\max \left\{ {{f_1}\left( {{x_i}} \right)} \right\}{\rm{ }},\max \left\{ {{f_2}\left( {{x_i}} \right)} \right\} \cdots ,\max \left. {\left\{ {{f_{|{{A}}|}}\left( {{x_i}} \right)} \right\}} \right)|{\rm{ }}} \right.} \Big.$ $\Big. {x_i^{* \triangleleft } \subseteq {{{D}}_j}} \Big\}$

6) for $ \left( {{{X}},{{B}}} \right) \in {{L}}\left( {{{U}},{{A}},{{I}}} \right)$ do

7) 　 $ {{E}} = \left( {\left\{ {{v_1}\left( {{B}} \right)} \right\},\left\{ {{v_2}\left( {{B}} \right)} \right\}, \cdots ,\left\{ {{v_{|A|}}\left( {{B}} \right)} \right\}} \right)$

8) 　compute D(L_j/E)

9) 　if D(L_jo/E)=maxD(L_j/E)

10) 　then $ {{R}}:\;{{B}} \Rightarrow {{{T}}_{{j_o}}}\left( {{{D}}\left( {{{{L}}_{{j_o}}}/{{E}}} \right)} \right)$

11) 　return R

12) end for

例3　通过悲观融合方法同样可以获取 ${{F}}$ 中的全部规则。

首先计算可知：

${{{L}}_1} = (\{ 1\} ,\{ 1\} ,\{ 0\} ,\{ 0\} ,\{ 0\} ,\{ 1\} ,\{ 1\} ,\{ 0\} )$

${{{L}}_2} = (\{ 0\} ,\{ 1\} ,\{ 1\} ,\{ 1\} ,\{ 0\} ,\{ 1\} ,\{ 1\} ,\{ 1\} )$

${{{L}}_3} = (\{ 1\} ,\{ 1\} ,\{ 1\} ,\{ 0\} ,\{ 1\} ,\{ 0\} ,\{ 0{\rm{\} }},\{ 0\} )$

对条件概念 $({\rm{\{ }}{x_1},{x_2},{x_3},{x_4}{\rm{\} }},{\rm{\{ }}{a_6}{\rm{\} }})$ ，有

$\begin{array}{l} {{D}}({{{L}}_1}/{{E}}) = 0.625\\ {{D}}({{{L}}_2}/{{E}}){\rm{ = }}0.375\\ {{D}}({{{L}}_3}/{{E}}){\rm{ = }}0.375 \end{array}$

可得规则 “ ${\rm{\{ }}{a_6}{\rm{\} }} \Rightarrow d = 1 (0.625)$ ”，此处0.625为该方法中此条规则的可信度。由该方式可规则如下：

$\{ {a_1},{a_6}{\rm{\} }} \Rightarrow d = 1 (0.75);$ $\{ {a_1},{a_6},{a_7}{\rm{\} }} \Rightarrow d = 1 (0.875)$

$\{ {a_1},{a_2},{a_6},{a_7}\} \Rightarrow d \!=\! 1 (1);$ $\{ {a_2},{a_6},{a_7},{a_8}\} \Rightarrow d \!=\! 1(0.75)$

$\{ {a_2},{a_6},{a_7},{a_8}\} \Rightarrow d \!=\! 2 (0.75);$ $ \{ {a_1},{a_3},{a_5}\} \Rightarrow d \!=\! 3 (0.75)$

${\rm{\{ }}{a_1}{\rm{,}}{a_2},{a_3},{a_5}{\rm{\} }} \Rightarrow d = 3 (1);$ $\{ {a_2},{a_3},{a_4}\} \Rightarrow d = 2 (0.625)$

$\{ {a_2},{a_3},{a_4}\} \Rightarrow d = 3 (0.625);$ $ \{ {a_6}\} \Rightarrow d = 1 (0.625)$

$ \{ {a_1}\} \Rightarrow d = 1 (0.625);$ ${\rm{\{ }}{a_1}{\rm{\} }} \Rightarrow d = 3 (0.625)$

$\{ {a_6},{a_7}\} \Rightarrow d = 1 (0.75);$ ${\rm{\{ }}{a_2},{a_6},{a_7}{\rm{\} }} \Rightarrow d = 1 (0.875)$

${\rm{\{ }}{a_1},{a_2}{\rm{\} }} \Rightarrow d = 1 (0.75);$ ${\rm{\{ }}{a_1},{a_2}{\rm{\} }} \Rightarrow d = 3 (0.75)$

$ {\rm{\{ }}{a_2}{\rm{\} }} \Rightarrow d = 1 (0.75);$ ${\rm{\{ }}{a_2}{\rm{\} }} \Rightarrow d = 3 (0.625)$

$ {\rm{\{ }}{a_3}{\rm{\} }} \Rightarrow d = 3 (0.625);$ ${\rm{\{ }}{a_2},{a_3}{\rm{\} }} \Rightarrow d = 3 (0.75)$

4 结束语

形式概念分析中至关重要的两个研究问题就是属性约简问题与规则提取问题，而这两方面的研究都是为了更准确便捷地获取决策。本文用对象集与决策属性集之间的等价关系代替要求更为严格的伽罗瓦连接，使决策形式背景的模型更易获取决策。

本文利用集值向量包含度给出两种规则融合方法，获取了决策形式背景的全部规则，其中包括确定性规则与大量不确定性规则。在现实生活，这些不确定性规则可能具有重要意义，如何在部分不确定性规则不变的前提下进行属性约简，将是未来研究的重要方向。