形式模糊背景中单边模糊概念格的属性约简

doi:10.13232/j.cnki.jnju.2022.01.005

形式模糊背景中单边模糊概念格的属性约简

李同军^,¹^,², 张晓雨¹, 吴伟志¹^,², 谭安辉¹^,²

1.浙江海洋大学信息工程学院, 舟山, 316022

2.浙江省海洋大数据挖掘与应用重点实验室, 浙江海洋大学信息工程学院, 舟山, 316022

Attribute reduction of single⁃sided fuzzy concept lattice in formal fuzzy contexts

Li Tongjun^,¹^,², Zhang Xiaoyu¹, Wu Weizhi¹^,², Tan Anhui¹^,²

1.School of Information Engineering，Zhejiang Ocean University，Zhoushan，316022，China

2.Key Laboratory of Oceanographic Big Data Mining & Application of Zhejiang Province，School of Information Engineering，Zhejiang Ocean University，Zhoushan，316022，China

通讯作者: E⁃mail：litj@zjou.edu.cn

收稿日期: 2021-06-26

基金资助:

国家自然科学基金. 61773349. 61573321. 61976194

Received: 2021-06-26

摘要

形式概念分析是一种有效的知识表示和知识发现的方法，形式背景和形式概念是形式概念分析中的两个基本概念.形式背景描述了对象集和属性集间的一个二元经典关系，隐含其中的知识通过概念格的形式表示出来.形式模糊背景是形式背景在模糊集理论下的自然推广，建立在其上的模糊概念格在实际应用中面临许多困难，为此，多种形式的模糊概念格的改进形式应运而生.单边模糊概念格就是一种具有较好应用前景的改进模糊概念格.主要研究基于经典⁃模糊概念格的形式模糊背景的属性约简问题，这里属性约简的概念具有保持相应的概念格整体结构不变的含义.关于属性约简，给出了多种形式的属性约简判定定理，针对属性约简，将所有属性分为三类，探究了不同类型属性的特征刻画.最后，通过引入模糊概念间的辨识属性集的概念，得到了基于辨识属性矩阵的属性约简方法，并通过示例验证了属性约简方法的可行性.

关键词： 概念格 ; 经典⁃模糊概念 ; 属性约简 ; 形式模糊背景

Abstract

Formal concept analysis is an effective method of knowledge representation and knowledge discovery，in which formal context and formal concept are two basic concepts. A formal context is just a binary classical relation between an object set and an attribute set，and the knowledge hidden in which is represented by a concept lattice. Formal fuzzy context is a natural extension of formal context in fuzzy set theory，the fuzzy concept lattice based on formal fuzzy context meets many difficulties in practical application，so that some modified fuzzy concept lattice are proposed. One⁃sided fuzzy concept lattice is just a kind of modified fuzzy concept lattices with better application prospect. This paper mainly focus on the study of attribute reduction of formal fuzzy contexts based on the classic⁃fuzzy concept lattices，where，notion of attribute reduction means keeping the whole structure of the corresponding concept lattices unchanged. With respect to the attribute reducts，a variety of judgement theorems for the attribute reducts are given. Based on the attribute reducts，all attributes are divided into three classes，and different types of attributes are characterized by different features. Finally，by introducing a notion of discernible attribute set between concepts，a method of attribute reduction is established，and the feasibility of the attribute reduction method is verified by an example.

Keywords： concept lattice ; crisp⁃fuzzy concept ; attribute reduction ; formal fuzzy context

PDF (485KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

李同军, 张晓雨, 吴伟志, 谭安辉. 形式模糊背景中单边模糊概念格的属性约简. 南京大学学报（自然科学）[J], 2022, 58(1): 38-48 doi:10.13232/j.cnki.jnju.2022.01.005

Li Tongjun, Zhang Xiaoyu, Wu Weizhi, Tan Anhui. Attribute reduction of single⁃sided fuzzy concept lattice in formal fuzzy contexts. Journal of nanjing University[J], 2022, 58(1): 38-48 doi:10.13232/j.cnki.jnju.2022.01.005

形式概念分析（Formal Concept Analysis，FCA）是德国数学家Wille提出的一种用于数据分析和知识处理的方法^［1-2］，已被广泛应用于数据挖掘、知识工程、机器学习、信息检索等领域^［3-5］.

形式背景是FCA的基本数据结构，是对象集和属性集之间的一个二元关系.形式背景上的每个形式概念包括外延和内涵两个部分，外延是一个对象子集，内涵是一个属性子集，所有的形式概念形成一个完备格，即概念格.

基于概念格的知识约简是FCA的一个重要的研究方向.概念格知识约简主要分为概念约简、属性约简和对象约简，其中属性约简是寻找最小的属性子集，使得概念格的某种性质保持不变^［6-7］.张文修等^［8］在格同构意义下研究了概念格属性约简问题，给出基于辨识属性矩阵的属性约简方法.Wu et al^［9］在粒计算思想下研究了概念格的粒约简问题.Kumar et al^［10］运用矩阵分解方法研究了概念格知识约简问题.Liu et al^［11］用粗糙集方法研究了概念格约简.决策形式背景是形式背景的一种推广，Li et al^［12-13］研究了不同形式决策背景中规则提取、属性约简等问题.

对象集和属性集间的二元模糊关系称为形式模糊背景，建立其上的模糊概念分析是经典形式概念分析的一种扩展.Burusco and Fuentes⁃Gonzales^［14］首次将模糊集引入形式概念分析.一些研究者将模糊集或模糊逻辑引入模糊概念格的研究中，得到了一些模糊概念格的推广模型^［15-17］.单边模糊概念格是一种形式的模糊概念格，单边是指概念的外延和内涵一个是经典集，另一个是模糊集.Krajči^［18］和Yahia et al^［19］首先独立地提出“单边模糊概念”的概念.Zhang et al^［20］给出变精度概念格的定义，其中涉及了三种单边模糊概念.

关于模糊概念格的属性约简，Shao et al^［21-22］和Li et al^［23］研究经典⁃模糊变精度概念格^［20］的减少属性和减少对象的知识约简方法、粒约简以及模糊⁃经典概念格的保持格中交不可约元的属性约简问题.Singh et al^［24］用信息熵给出计算形式模糊背景的权重的方法.Mao and Miao^［25］运用有向图理论给出了模糊⁃经典概念格的保持交不可约元的属性方法.Shi and Yang^［26］研究了模糊⁃经典概念格的保持属性粒不变的对象约简问题.Lin et al^［27-28］提出布尔矩阵和粒度矩阵的概念，据此给出形式模糊背景粒度约简方法.

与经典形式背景相比，形式模糊背景上的知识约简问题的研究甚少.对应张文修等^［8］提出的经典形式背景中保持完整格结构的属性约简，本文提出经典⁃模糊概念格的一种属性约简概念，探索属性约简的判定定理，给出不同类型属性的特征刻画.通过引入辨识属性集的概念，给出了属性约简的一种方法，在用示例说明结论正确性的同时，也验证了约简方法的可行性.

1 经典⁃模糊概念格的基本知识

本节回顾形式模糊背景下经典⁃模糊概念的基本知识^{［18-19，22］}.

1.1　经典⁃模糊概念

设 $U$ 是一个非空、有限的集合，称为论域. $P (U)$ 和 $F (U)$ 分别表示 $U$ 中全部经典子集的集合和 $U$ 上全部模糊集的集合.在这里， $U$ 上模糊集 $\tilde{X}$ 为 $U$ 到 $[0,1]$ 的映射.

形式模糊背景是一个三元组 $(U, A, \tilde{I})$ ，其中 $U$ 和 $A$ 都是非空有限集合，分别称为对象集和属性集， $U$ 和 $A$ 中的元素分别称为对象和属性， $\tilde{I}$ 是 $U \times A$ 上的一个模糊集，即 $U$ 到 $A$ 的一个模糊关系.对于 $x \in U$ ， $a \in A$ ， $x \tilde{I}$ 和 $\tilde{I} a$ 分别表示 $A$ 和 $U$ 上的模糊集，即 $(x \tilde{I}) (b) = \tilde{I} (x, b)$ ， $b \in A$ ； $(\tilde{I} a) (y) = \tilde{I} (y, a)$ ， $y \in U$ .

下文总假设形式模糊背景 $(U, A, \tilde{I})$ 满足： $\forall x, y \in U$ ， $x \tilde{I} \neq y \tilde{I}$ ； $\forall a, b \in A$ ， $\tilde{I} a \neq \tilde{I} b$ .

设 $(U, A, \tilde{I})$ 是一个形式模糊背景，算子 $f : P (U) \to F (A)$ 和 $g : F (A) \to P (U)$ 定义如下：

\begin{array}{l} f (X) = \cap_{x \in X} x \tilde{I}, X \in P (U) \\ g (\tilde{B}) = \{x \in U : \tilde{B} \subseteq x \tilde{I}\}, \tilde{B} \in F (A) \end{array}

算子 $f$ 和 $g$ 满足下列性质：

\forall X, X_{1}, X_{2} \in P (U)

，

\forall \tilde{B}, {\tilde{B}}_{1}, {\tilde{B}}_{2} \in F (A)

，

（1） $\begin{array}{l} X_{1} \subseteq X_{2} \Rightarrow f (X_{1}) \supseteq f (X_{2}) \\ {\tilde{B}}_{1} \subseteq {\tilde{B}}_{2} \Rightarrow g ({\tilde{B}}_{1}) \supseteq g ({\tilde{B}}_{2}) \end{array}$

（2） $\begin{array}{l} f (X_{1} ⋃ X_{2}) = f (X_{2}) ⋂ f (X_{2}) \\ g ({\tilde{B}}_{1} ⋃ {\tilde{B}}_{2}) = g ({\tilde{B}}_{1}) ⋂ g ({\tilde{B}}_{2}) \end{array}$

（3） $X \subseteq (g f) (X)$ ， $\tilde{B} \subseteq (f g) (\tilde{B})$

（4） $f (X) = (f g f) (X)$ ， $g (\tilde{B}) = (g f g) (\tilde{B})$

这里，符号 $(g f)$ 表示内层算子 $f$ 与外层算子 $g$ 的复合运算 $g \circ f$ .

对于 $X \in P (U)$ ， $\tilde{B} \in F (A)$ ，若 $f (X) = \tilde{B}$ ， $g (\tilde{B}) = X$ ，则称 $(X, \tilde{B})$ 为 $(U, A, \tilde{I})$ 的一个经典⁃模糊概念，简称概念，并分别称 $X$ 和 $\tilde{B}$ 为概念的外延和内涵.记 $(U, A, \tilde{I})$ 的全部概念组成的集合为 $L (U, A, \tilde{I})$ ，简记为 $L (\tilde{I})$ .

对于任意 $X \in P (U)$ ， $((g f) (X), f (X)) \in L (\tilde{I})$ ；对于任何 $\tilde{B} \in F (A)$ ， $(g (\tilde{B}), (f g) (\tilde{B})) \in L (\tilde{I})$ .

在 $L (\tilde{I})$ 中定义如下偏序关系：

(X_{1}, {\tilde{B}}_{1}), (X_{2}, {\tilde{B}}_{2}) \in L (\tilde{I})

(X_{1}, {\tilde{B}}_{1}) \leq (X_{2}, {\tilde{B}}_{2}) \Leftrightarrow X_{1} \subseteq X_{2}

等价地， ${\tilde{B}}_{1} \supseteq {\tilde{B}}_{2}$ .

则 $(L (\tilde{I}), \leq)$ 是一个完备格，称为概念格，其中的下确界（ $\land$ ）和上确界（ $\lor$ ）运算分别为：

(X_{1}, {\tilde{B}}_{1}) \land (X_{2}, {\tilde{B}}_{2}) = (X_{1} ⋂ X_{2}, f (X_{1} ⋂ X_{2}))

(X_{1}, {\tilde{B}}_{1}) \lor (X_{2}, {\tilde{B}}_{2}) = (g ({\tilde{B}}_{1} ⋂ {\tilde{B}}_{2}), {\tilde{B}}_{1} ⋂ {\tilde{B}}_{2})

不难验证，当模糊关系 $\tilde{I}$ 退化为经典关系时，经典⁃模糊概念变为经典形式概念^［1］，算子 $f$ 和 $g$ 也变成相应的经典算子.因此，经典⁃模糊概念格是经典形式概念格的一种推广.

记 $L_{U} (\tilde{I})$ 为 $L (\tilde{I})$ 中所有概念的外延构成的集合.

例1表1给出一个形式模糊背景 $(U, A, \tilde{I})$ ，其中，对象集为 $U = \{x_{1}, x_{2}, x_{3}, x_{4}\}$ ，属性集为 $A = \{a, b, c, d, e\}$ . $U$ 到 $A$ 上的模糊关系 $\tilde{I}$ 如表1所示，其具体含义为：比如 $\tilde{I} (x_{2}, d) = 0.82$ ，表示对象属性对 $(x_{2}, d)$ 关于模糊集 $\tilde{I}$ 的隶属度为0.82，也表示对象 $x_{2}$ 具有属性 $d$ 的程度为0.82. $(U, A, \tilde{I})$ 上的所有经典⁃模糊概念如表2所示，图1为概念格 $L (\tilde{I})$ 的Hasse图.

表1 一个形式模糊背景

Table 1 A formal fuzzy context

$\tilde{I}$	a	b	c	d	e
$x_{1}$	0.41	0.90	0.21	0.79	1.00
$x_{2}$	0.23	0.44	0.65	0.82	0.00
$x_{3}$	0.87	0.66	0.55	0.42	1.00
$x_{4}$	0.53	0.50	0.73	0.40	0.00

新窗口打开| 下载CSV

表2 由表1导出的全部经典⁃模糊概念

Table 2 All crisp⁃fuzzy concepts derived from Table 1

(外延，内涵)
FC₁	$(\{x_{1}, x_{2}, x_{3}, x_{4}\}, \{a^{0.23}, b^{0.44}, c^{0.21}, d^{0.40}, e^{0.00}\})$
FC₂	$(\{x_{1}, x_{2}, x_{3}\}, \{a^{0.23}, b^{0.44}, c^{0.21}, d^{0.42}, e^{0.00}\})$
FC₃	$(\{x_{2}, x_{3}, x_{4}\}, \{a^{0.23}, b^{0.44}, c^{0.55}, d^{0.40}, e^{0.00}\})$
FC₄	$(\{x_{1}, x_{3}, x_{4}\}, \{a^{0.41}, b^{0.50}, c^{0.21}, d^{0.40}, e^{0.00}\})$
FC₅	$(\{x_{1}, x_{2}\}, \{a^{0.23}, b^{0.44}, c^{0.21}, d^{0.79}, e^{0.00}\})$
FC₆	$(\{x_{1}, x_{3}\}, \{a^{0.41}, b^{0.66}, c^{0.21}, d^{0.42}, e^{1.00}\})$
FC₇	$(\{x_{2}, x_{3}\}, \{a^{0.23}, b^{0.44}, c^{0.55}, d^{0.42}, e^{0.00}\})$
FC₈	$(\{x_{2}, x_{4}\}, \{a^{0.23}, b^{0.44}, c^{0.65}, d^{0.40}, e^{0.00}\})$
FC₉	$(\{x_{3}, x_{4}\}, \{a^{0.53}, b^{0.50}, c^{0.55}, d^{0.40}, e^{0.00}\})$
FC₁₀	$(\{x_{1}\}, \{a^{0.41}, b^{0.90}, c^{0.21}, d^{0.79}, e^{1.00}\})$
FC₁₁	$(\{x_{2}\}, \{a^{0.23}, b^{0.44}, c^{0.65}, d^{0.82}, e^{0.00}\})$
FC₁₂	$(\{x_{3}\}, \{a^{0.87}, b^{0.66}, c^{0.55}, d^{0.42}, e^{1.00}\})$
FC₁₃	$(\{x_{4}\}, \{a^{0.53}, b^{0.50}, c^{0.73}, d^{0.40}, e^{0.00}\})$
FC₁₄	$(\emptyset, \{a^{1.00}, b^{1.00}, c^{1.00}, d^{1.00}, e^{1.00}\})$

新窗口打开| 下载CSV

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 概念格 $L (\tilde{I})$ 的Hasse图

Fig.1 The Hasse diagram of the concept lattice $L (\tilde{I})$

命题1

设 $(U, A, \tilde{I})$ 是一个形式模糊背景，则

L_{U} (\tilde{I}) = \{(g f) (X) : X \in P (U)\}

证明

对于任意 $X \in P (U)$ ，由 $((g f) (X),$

$f (X)) \in L (\tilde{I})$ 得 $(g f) (X) \in L_{U} (\tilde{I})$ ，故：

\{(g f) (X) : X \in P (U)\} \subseteq L_{U} (\tilde{I})

对于 $(X, \tilde{B}) \in L (\tilde{I})$ ，由

X = g (\tilde{B}) = (g f g) (\tilde{B}) = (g f) (X)

得：

X \in \{(g f) (X) : X \in P (U)\}

故

L_{U} (\tilde{I}) \subseteq \{(g f) (X) : X \in P (U)\}

因此，

L_{U} (\tilde{I}) = \{(g f) (X) : X \in P (U)\}

命题得证.

设 $U$ 是一个论域， $R$ 是 $U$ 上的一个二元关系，即 $R \subseteq U \times U$ ，在粗糙集理论中，称 $(U, R)$ 为一个广义近似空间.对于 $X \in P (U)$ ， $X$ 在 $(U, R)$ 中的上近似和下近似分别定义为：

\bar{R} (X) = \{x \in U : R (x) ⋂ X \neq \emptyset\}

\underset{̲}{R} (X) = \{x \in U : R (x) \subseteq X\}

其中， $R (x)$ 为 $x$ 关于 $R$ 的后继邻域，即：

R (x) = \{y \in U : (x, y) \in R\}

对于形式模糊背景 $(U, A, \tilde{I})$ 和 $a \in A$ ，令：

R_{a} = \{(x, y) \in U \times U : \tilde{I} (x, a) \geq \tilde{I} (y, a)\}

则 $R_{a}$ 是 $U$ 上的一个优势关系，即 $R_{a}$ 满足自反性和传递性，也就是 $\forall x \in U$ ， $(x, x) \in R_{a}$ ； $\forall x, y, z \in$

U

，若

(x, y) \in R_{a}

，

(y, z) \in R_{a}

，则

(x, z) \in R_{a}

命题2

设 $(U, A, \tilde{I})$ 是一个形式模糊背景，则：

\forall X \in P (U)

，

(g f) (X) = \cap_{a \in A} \bar{R_{a}} (X)

证明

$\forall X \in P (U)$ ，

\begin{array}{l} (g f) (X) = \{x \in U : f (X) \subseteq x \tilde{I}\} = \\ \{x \in U : \cap_{y \in X} y \tilde{I} \subseteq x \tilde{I}\} = \\ \{x \in U : \forall a \in A (\land_{y \in X} \tilde{I} (y, a) \leq \tilde{I} (x, a))\} = \\ \{x \in U : \forall a \in A [\exists y \in U (y \in X, \tilde{I} (y, a) \leq \tilde{I} (x, a))]\} = \\ \{x \in U : \forall a \in A (\exists y \in U (y \in X, y \in R_{a} (x)))\} = \\ \{x \in U : \forall a \in A (R_{a} (x) ⋂ X \neq \emptyset)\} = \\ \{x \in U : \forall a \in A, x \in \bar{R_{a}} (X)\} = \\ \cap_{a \in A} \bar{R_{a}} (X) \end{array}

命题得证.

1.2　形式模糊背景的子背景

设 $U$ 是一个论域， $V \subseteq U$ ， $\tilde{X} \in F (U)$ ， $\tilde{X}$ 在 $V$ 上的限制 ${\tilde{X}|}_{V}$ 为 $V$ 上的模糊集，满足对于任意 $x \in V$ ，有 ${\tilde{X}|}_{V} (x) = \tilde{X} (x)$ .

定义1

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $C \subseteq A$ ，称形式模糊背景 $(U, C, {\tilde{I}}_{C})$ 为 $(U, A, \tilde{I})$ 的子背景，其中， ${\tilde{I}}_{C} = {\tilde{I}|}_{U \times C}$ .

在子背景 $(U, C, {\tilde{I}}_{C})$ 下，算子 $f_{C} : P (U) \to F (C)$ 和 $g_{C} : F (C) \to P (U)$ 定义如下：

f_{C} (X) = \underset{x \in X}{\cap} x {\tilde{I}}_{C}, X \in P (U)

g_{C} (\tilde{B}) = \{x \in U : \tilde{B} \subseteq x {\tilde{I}}_{C}\}, \tilde{B} \in F (C)

算子 $f_{C}$ 和 $g_{C}$ 与算子 $f$ 和 $g$ 具有相同的性质.

容易证明，对于任何 $X \in P (U)$ ， $f_{C} (X) = {f (X)|}_{C}$ .记 $g_{C} f_{C}$ 为 ${(g f)}_{C}$ .由于 $f_{A} = f$ ， $g_{A} = g$ ， ${(g f)}_{A} = g f$ ，所以仍将 $f_{A}$ ， $g_{A}$ 和 ${(g f)}_{A}$ 分别记为 $f$ ， $g$ 和 $g f$ .特别地，对于 $a \in A$ ，简记 ${(g f)}_{\{a\}}$ 为 ${(g f)}_{a}$ .

命题3

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $C_{1}, C_{2} \subseteq A$ ，且 $C_{1} ⋂ C_{2} = \emptyset$ ，则：

{(g f)}_{C_{1} ⋃ C_{2}} = {(g f)}_{C_{1}} ⋂ {(g f)}_{C_{2}}

证明

由命题2直接可得.

命题3说明，若 $C_{1} \subseteq C_{2} \subseteq A$ ，则 ${(g f)}_{C_{2}} \leq {(g f)}_{C_{1}}$ ，即 ${(g f)}_{C_{2}} (X) \subseteq {(g f)}_{C_{1}} (X)$ ， $X \in P (U)$ .

命题4

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $C \subseteq A$ ，则对于任意 $X \in P (U)$ ， ${(g f)}_{C} (X) \in L_{U} (\tilde{I})$ .

证明

只需证明：

(g f) ({(g f)}_{C} (X)) = {(g f)}_{C} (X)

，

X \in P (U)

对于任何 $x \in (g f) ({(g f)}_{C} (X))$ ，由定义得 $f ({(g f)}_{C} (X)) \subseteq x \tilde{I}$ ，两边取在 $C$ 上的限制得：

f {({(g f)}_{C} (X))|}_{C} \subseteq x {\tilde{I}}_{C}

由于：

f {({(g f)}_{C} (X))|}_{C} = f_{C} ({(g f)}_{C} (X))

及

f_{C} ({(g f)}_{C} (X)) = f_{C} (X)

所以 $f_{C} (X) \subseteq x {\tilde{I}}_{C}$ ，故 $x \in {(g f)}_{C} (X)$ .因此，

(g f) ({(g f)}_{C} (X)) \subseteq {(g f)}_{C} (X)

再结合

{(g f)}_{C} (X) \subseteq (g f) ({(g f)}_{C} (X))

可得：

(g f) ({(g f)}_{C} (X)) = {(g f)}_{C} (X)

命题得证.

命题4说明，对于任意 $C \subseteq A$ ，都有 $L_{U} ({\tilde{I}}_{C}) \subseteq L_{U} (\tilde{I})$ ，所以 $L ({\tilde{I}}_{C})$ 中每个概念与 $L (\tilde{I})$ 中某个概念外延相等.因此 $L ({\tilde{I}}_{C})$ 的基数不大于 $L (\tilde{I})$ 的基数，即 $|L ({\tilde{I}}_{C})| \leq |L (\tilde{I})|$ .

例2 设 $(U, A, \tilde{I})$ 是例1中的形式模糊背景，取 $C = \{b, c, e\}$ ，则子背景 $(U, C, {\tilde{I}}_{C})$ 如表3所示，它的所有经典⁃模糊概念如表4所示，图2为概念格 $L ({\tilde{I}}_{C})$ 的Hasse图.从表4可以看出， $L_{U} ({\tilde{I}}_{C}) \subseteq L (\tilde{I})$ .

表3 一个子背景 $(U, C, {\tilde{I}}_{C})$

Table 3 A sub⁃context $(U, C, {\tilde{I}}_{C})$

$\tilde{I}$	b	c	e
$x_{1}$	0.90	0.21	1.00
$x_{2}$	0.44	0.65	0.00
$x_{3}$	0.66	0.55	1.00
$x_{4}$	0.50	0.73	0.00

新窗口打开| 下载CSV

表4 $(U, C, {\tilde{I}}_{C})$ 的所有经典⁃模糊概念

Table 4 All crisp⁃fuzy concepts of $(U, C, {\tilde{I}}_{C})$

	(外延，内涵)
$F C_{1}^{C}$	$(\{x_{1}, x_{2}, x_{3}, x_{4}\}, \{b^{0.44}, c^{0.21}, e^{0.00}\})$
$F C_{2}^{C}$	$(\{x_{1}, x_{3}, x_{4}\}, \{b^{0.50}, c^{0.21}, e^{0.00}\})$
$F C_{3}^{C}$	$(\{x_{2}, x_{3}, x_{4}\}, \{b^{0.44}, c^{0.55}, e^{0.00}\})$
$F C_{4}^{C}$	$(\{x_{1}, x_{3}\}, \{b^{0.66}, c^{0.21}, e^{1.00}\})$
$F C_{5}^{C}$	$(\{x_{3}, x_{4}\}, \{b^{0.50}, c^{0.55}, e^{0.00}\})$
$F C_{6}^{C}$	$(\{x_{2}, x_{4}\}, \{b^{0.44}, c^{0.65}, e^{0.00}\})$
$F C_{7}^{C}$	$(\{x_{1}\}, \{b^{0.90}, c^{0.21}, e^{1.00}\})$
$F C_{8}^{C}$	$(\{x_{2}\}, \{b^{0.44}, c^{0.65}, e^{0.00}\})$
$F C_{9}^{C}$	$(\{x_{3}\}, \{b^{0.66}, c^{0.55}, e^{1.00}\})$
$F C_{10}^{C}$	$(\{x_{4}\}, \{b^{0.50}, c^{0.73}, e^{0.00}\})$
$F C_{11}^{C}$	$(\emptyset, \{, b^{1.00}, c^{1.00}, e^{1.00}\})$

新窗口打开| 下载CSV

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 概念格 $L ({\tilde{I}}_{C})$ 的Hasse图

Fig.2 The Hasse diagram of the concept lattice $L ({\tilde{I}}_{C})$

2 格约简的定义与判定定理

定义2

设 $L (U, A_{1}, {\tilde{I}}_{1})$ 和 $L (U, A_{2}, {\tilde{I}}_{2})$ 是两个概念格，若对于任何 $(X, \tilde{B}) \in L ({\tilde{I}}_{2})$ ，都存在 $(X^{'}, {\tilde{B}}^{'}) \in L ({\tilde{I}}_{1})$ 使得 $X = X^{'}$ ，则称 $L ({\tilde{I}}_{1})$ 细于 $L ({\tilde{I}}_{2})$ ，记为 $L ({\tilde{I}}_{1}) \leq L ({\tilde{I}}_{2})$ .

如果 $L ({\tilde{I}}_{1}) \leq L ({\tilde{I}}_{2})$ ，且 $L ({\tilde{I}}_{2}) \leq L ({\tilde{I}}_{1})$ ，则称 $L ({\tilde{I}}_{1})$ 与 $L ({\tilde{I}}_{2})$ 同构，记为 $L ({\tilde{I}}_{1}) ≅ L ({\tilde{I}}_{2})$ .

由定义2可知：

\begin{array}{l} L ({\tilde{I}}_{1}) \leq L ({\tilde{I}}_{2}) \Leftrightarrow L_{U} ({\tilde{I}}_{2}) \subseteq L_{U} ({\tilde{I}}_{1}) \Rightarrow \\ |L_{U} ({\tilde{I}}_{2})| \leq |L_{U} ({\tilde{I}}_{1})| \end{array}

因而，

\begin{array}{l} L ({\tilde{I}}_{1}) ≅ L ({\tilde{I}}_{2}) \Leftrightarrow L_{U} ({\tilde{I}}_{1}) = L_{U} ({\tilde{I}}_{2}) \Rightarrow \\ |L_{U} ({\tilde{I}}_{1})| = |L_{U} ({\tilde{I}}_{2})| \end{array}

根据命题4直接可得下面结论.

命题5

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $C \subseteq A$ ，则 $L (\tilde{I}) \leq L ({\tilde{I}}_{C})$ .

定义3

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D \subseteq A$ .若 $L ({\tilde{I}}_{D}) ≅ L (\tilde{I})$ ，则称 $D$ 是 $(U, A, \tilde{I})$ 的协调集.若进一步地 $\forall d \in D$ ， $D - \{d\}$ 不是协调集，则称 $D$ 是 $(U, A, \tilde{I})$ 的约简.

从定义3可以看出，约简是保证对应子背景的概念与原背景的概念具有相同的层次结构，而且对应概念的外延保持不变的最小的属性集.

为了求出约简，需要给出协调集的充要条件，即协调集判定定理.下面定理的结论是显然的.

定理1

协调集判定定理1 设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D \subseteq A$ ，则：

D 是 协 调 集 \Leftrightarrow L_{U} ({\tilde{I}}_{D}) = L_{U} (\tilde{I})

定理1说明，判断 $D$ 是否为协调集，只需看它对应的概念格中概念的数量是否较原概念格中的概念的数量有所减少，如果没有减少，则 $D$ 就是协调集.

定理2

协调集判定定理2 设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D \subseteq A$ ，则：

D 是 协 调 集 \Leftrightarrow {(g f)}_{D} \leq g f

证明

“ $\Rightarrow$ ” 设 $D$ 是协调集，由定理1得 $L_{U} ({\tilde{I}}_{D}) = L_{U} (\tilde{I})$ .由于对于任意 $X \subseteq U$ ，都有

$(g f) (X) \in L_{U} (\tilde{I})$ ，故 $(g f) (X) \in L_{U} ({\tilde{I}}_{D})$ ，从而 ${(g f)}_{D} ((g f) (X)) = (g f) (X)$ .由 $X \subseteq (g f) (X)$ 得

{(g f)}_{D} (X) \subseteq {(g f)}_{D} ((g f) (X))

，所以

{(g f)}_{D} (X) \subseteq

(g f) (X)

，因此

{(g f)}_{D} \leq g f

“ $\Leftarrow$ ” 设 ${(g f)}_{D} \leq g f$ ，由于 $g f \leq {(g f)}_{D}$ ，所以 ${(g f)}_{D} = g f$ .根据命题1可得 $L_{U} ({\tilde{I}}_{D}) = L_{U} (\tilde{I})$ ，故 $D$ 是协调集.定理得证.

从定理2的证明可以看出， ${(g f)}_{D} \leq g f \Leftrightarrow$

{(g f)}_{D} = g f

定理3

协调集判定定理3 设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D \subseteq A$ ，则D是协调集 $\Leftrightarrow$ $\forall d \in A - D$ ， $\exists E \subseteq D$ ，使得 ${(g f)}_{E} \leq {(g f)}_{d}$ .

证明

“ $\Rightarrow$ ” 设 $D$ 是协调集，由定理2得 ${(g f)}_{D} \leq g f$ ，再由 $g f = {(g f)}_{D} ⋂ {(g f)}_{A - D}$ ，得 ${(g f)}_{D} \leq {(g f)}_{A - D}$ . $\forall d \in A - D$ ，总有 ${(g f)}_{A - D} \leq {(g f)}_{d}$ ，故 ${(g f)}_{D} \leq {(g f)}_{d}$ .

“ $\Leftarrow$ ” 设 $\forall d \in A - D$ ， $\exists E \subseteq D$ ，使得 ${(g f)}_{E} \leq {(g f)}_{d}$ ，由命题3得知 ${(g f)}_{D} \leq {(g f)}_{E}$ 成立，故 ${(g f)}_{D} \leq {(g f)}_{d}$ ，进而得出 ${(g f)}_{D} \leq {(g f)}_{A - D}$ ，再推出 ${(g f)}_{D} \leq g f$ .因此由定理2可知， $D$ 是协调集.定理得证.

由定理3及其证明可得下面的推论.

推论1

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D \subseteq A$ ，则 $D$ 是协调集 $\Leftrightarrow$ $\forall d \in A - D$ ，都有 ${(g f)}_{D} \leq {(g f)}_{d}$ .

定理4

协调集判定定理4 设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D \subseteq A$ ，则 $D$ 是协调集 $\Leftrightarrow$

\forall F \subseteq A - D

，

\exists E \subseteq D

，使得

{(g f)}_{E} \leq {(g f)}_{F}

证明

“ $\Rightarrow$ ” 若 $D$ 是协调集，则由推论1和命题3得 ${(g f)}_{D} \leq {(g f)}_{A - D}$ . $\forall F \subseteq A - D$ ，有 ${(g f)}_{A - D} \leq$

{(g f)}_{F}

，故

{(g f)}_{D} \leq {(g f)}_{F}

“ $\Leftarrow$ ” 设 $\forall F \subseteq A - D$ ， $\exists E \subseteq D$ ，使得 ${(g f)}_{E} \leq {(g f)}_{F}$ ，则 $\forall d \in A - D$ ， $\exists E_{d} \subseteq D$ ，使得 ${(g f)}_{E_{d}} \leq$ ${(g f)}_{d}$ .因此，由定理3知道 $D$ 是协调集.定理证毕.

由定理4易推出下面的推论.

推论2

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D \subseteq A$ ，则 $D$ 是协调集 $\Leftrightarrow {(g f)}_{D} \leq {(g f)}_{A - D}$ .

3 概念格的属性特征

设 $(U, A, \tilde{I})$ 是一个形式模糊背景，根据定义3可知， $(U, A, \tilde{I})$ 的约简一定存在，但约简可能不止一个.相对于形式模糊背景的所有约简，属性的重要性是不同的.

定义4

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $\{D_{i}, i = 1,2, \dots, l\}$ 是 $(U, A, \tilde{I})$ 的全部约简.将 $A$ 中属性分成三部分：（1）绝对必要属性（核心属性） $c : c \in \cap_{i \leq l} D_{i}$ ；（2）相对必要属性 $b : b \in \cup_{i \leq l} D_{i} - \cap_{i \leq l} D_{i}$ ；（3）绝对不必要属性 $d : d \in A - \cup_{i \leq l} D_{i}$ .

因此，核心属性是所有约简中不可缺少的属性，绝对不必要属性是不属于任何约简的属性，而相对必要属性必属于某个约简，但是不属于每个约简.

不同类型的属性在概念格约简中有不同特征.

定理5

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $a \in A$ ，则 $a$ 是核心属性 $\Leftrightarrow A - \{a\}$ 不是协调集.

证明

“ $\Rightarrow$ ” 设 $a$ 为核心属性，则对于任何约简 $D_{i}$ （ $i \leq l$ ），都有 $a \in D_{i}$ .若 $A - \{a\}$ 是协调集，易知存在约简 $D \subseteq A - \{a\}$ ，故 $a \notin D$ ，它与 $a$ 为核心属性矛盾.因此， $A - \{a\}$ 不是协调集.

“ $\Leftarrow$ ” 若 $A - \{a\}$ 不是协调集，由推论1得， ${(g f)}_{A - \{a\}} \leq {(g f)}_{a}$ 不成立. $\forall E \subseteq A - \{a\}$ ，由于 ${(g f)}_{A - \{a\}} \leq {(g f)}_{E}$ ，所以 ${(g f)}_{E} \leq {(g f)}_{a}$ 不成立，由此可以断定 $E$ 不是协调集，因为若 $E$ 是协调集，则由定理2得 ${(g f)}_{E} \leq g f$ ，进而 ${(g f)}_{A - \{a\}} \leq g f$ ，故 $A - \{a\}$ 为协调集，矛盾！对于任何约简 $D_{i}$ （ $i \leq l$ ），由于 $D_{i}$ 是协调集，所以 $D_{i} ⊄ A - \{a\}$ ，故 $a \in D_{i}$ .因此，从 $D_{i}$ 的任意性知道 $a$ 为核心属性.定理得证.

定理6

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $a \in A$ ，则 $a$ 是绝对不必要属性 $\Leftrightarrow (g f) (a) \leq {(g f)}_{a}$ ，其中， $(g f) (a) = ⋃ \{{(g f)}_{B - \{a\}} : B \subseteq A, {(g f)}_{B} \leq g f\}$ .

证明

“ $\Rightarrow$ ” 设 $a$ 是绝对不必要属性，即对于任何约简 $D_{i}$ （ $i \leq l$ ），都有 $a \notin D_{i}$ . $\forall B \subseteq A$ ，若 ${(g f)}_{B} \leq g f$ ，即 $B$ 是协调集，则存在约简 $D$ ，满足 $D \subseteq B$ ，由 $a \notin D$ 得 $D \subseteq B - \{a\}$ ，故 ${(g f)}_{B - \{a\}} \leq$ ${(g f)}_{D}$ ，再由 $D$ 是协调集得 ${(g f)}_{D} \leq {(g f)}_{a}$ ，进而 ${(g f)}_{B - \{a\}} \leq {(g f)}_{a}$ .因此， $(g f) (a) \leq {(g f)}_{a}$ .

“ $\Leftarrow$ ” 设 $(g f) (a) \leq {(g f)}_{a}$ ，则对于任何约简 $D$ ，由于 $D$ 是协调集，所以 ${(g f)}_{D} \leq g f$ ，故 ${(g f)}_{D - \{a\}} \leq (g f) (a) \leq {(g f)}_{a}$ .

由于 ${(g f)}_{D} = {(g f)}_{D - \{a\}} ⋂ {(g f)}_{a}$ ，所以 ${(g f)}_{D - \{a\}} =$

${(g f)}_{D} \leq g f$ .因此 $D - \{a\}$ 是协调集，由约简定义得 $a \notin D$ .由 $D$ 的任意性可知， $a$ 是绝对不必要属性.定理得证.

综合定理5和定理6，得到下面的属性特征刻画定理.

定理7

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $a \in A$ ，则：

（1） $a$ 是核心属性 $\Leftrightarrow A - \{a\}$ 不是协调集.

（2） $a$ 是相对必要属性 $\Leftrightarrow A - \{a\}$ 是协调集， $(g f) (a) \leq {(g f)}_{a}$ 不成立.

（3） $a$ 是绝对不必要属性 $\Leftrightarrow (g f) (a) \leq {(g f)}_{a}$ .

4 概念格约简的方法

下面引入形式模糊背景的辨识属性矩阵的概念，据此定义辨识函数，由辨识函数可以得到所有约简.

定义5

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $(X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j}) \in L (\tilde{I})$ ，令：

\begin{array}{l} D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) = \\ \{\begin{array}{l} \{a \in A : {\tilde{B}}_{i} (a) \neq {\tilde{B}}_{i} (a)\}, X_{i} \subset X_{j} 或 X_{j} \subset X_{i} \\ \emptyset, 否 则 \end{array} \end{array}

则称 $D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j}))$ 为 $(X_{1}, {\tilde{B}}_{1})$ 与 $(X_{2}, {\tilde{B}}_{2})$ 的辨识属性集.称：

\begin{array}{l} D I S (\tilde{I}) = \\ (D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) : (X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j}) \in L (\tilde{I})) \end{array}

为 $(U, A, \tilde{I})$ 的辨识属性矩阵.

辨识属性矩阵是对称矩阵，即：

D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) = D I S ((X_{j}, {\tilde{B}}_{j}), (X_{i}, {\tilde{B}}_{i}))

在辨识属性矩阵中，为空集的辨识属性集对概念格的属性约简没有意义，因此在辨识属性矩阵中仅列出主对角线一侧的非空辨识属性集.

例3表5给出例1中形式模糊背景的辨识属性矩阵.

表5 例1中形式模糊背景的辨识属性矩阵

Table 5 The discernibility matrix of the content in Example 1

	FC₂	FC₃	FC₄	FC₅	FC₆	FC₇	FC₈	FC₉	FC₁₀	FC₁₁	FC₁₂	FC₁₃	FC₁₄
FC₁	$\{d\}$	$\{c\}$	$\{a b\}$	$\{d\}$	$\{a b d e\}$	$\{c d\}$	$\{c\}$	$\{a b c\}$	$\{a b d e\}$	$\{c d\}$	A	$\{a b c e\}$	A
FC₂				$\{d\}$	$\{a b e\}$	$\{c\}$			$\{a b d e\}$	$\{c d\}$	$\{a b c e\}$		A
FC₃						$\{d\}$	$\{c\}$	$\{a b\}$		$\{c d\}$	$\{a b d e\}$	$\{a b c\}$	A
FC₄					$\{b d e\}$			$\{a c\}$	$\{b d e\}$		A	$\{a c\}$	A
FC₅									$\{a b e\}$	$\{c d\}$			A
FC₆									$\{b d\}$		$\{a c\}$		$\{a b c d\}$
FC₇										$\{c d\}$	$\{a b e\}$		A
FC₈										$\{d\}$		$\{a b c\}$	A
FC₉											$\{a b d e\}$	$\{c\}$	A
FC₁₀													$\{a b c d\}$
FC₁₁													A
FC₁₂													$\{a b c d\}$
FC₁₃													A

新窗口打开| 下载CSV

定理8

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $a \in A$ ，则：

$a$ 是核心属性 $\Leftrightarrow \exists (X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j}) \in L (\tilde{I})$ ， $D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) = \{a\}$ .

证明

“ $\Leftarrow$ ” 设 $D I S ((X_{1}, {\tilde{B}}_{1}), (X_{2}, {\tilde{B}}_{2})) = \{a\}$ ，不妨设 $X_{1} \subset X_{2}$ .由于 $X_{i} = (g f) (X_{i})$ ， $i = 1,2$ ，所以 $(g f) (X_{1}) \neq (g f) (X_{2})$ .由辨识属性集定义可知， $\forall b \in A - \{a\}$ ， ${\tilde{B}}_{1} (b) = {\tilde{B}}_{2} (b)$ ，故 ${{\tilde{B}}_{1}|}_{A - \{a\}} = {{\tilde{B}}_{2}|}_{A - \{a\}}$ .由 $f (X_{i}) = {\tilde{B}}_{i}$ （ $i = 1,2$ ）得 $f_{A - \{a\}} (X_{1}) = f_{A - \{a\}} (X_{2})$ ，故 ${(g f)}_{A - \{a\}} (X_{1}) = {(g f)}_{A - \{a\}} (X_{2})$ .因此 ${(g f)}_{A - \{a\}} \neq g f$ ，等价地， ${(g f)}_{A - \{a\}} \leq g f$ 不成立.根据定理2得 $A - \{a\}$ 不是协调集，再由定理5知道 $a$ 是核心属性.

“ $\Rightarrow$ ” 设 $a$ 是核心属性，则由定理5知 $A - \{a\}$ 不是协调集，从而由定理2得 ${(g f)}_{A - \{a\}} \leq g f$ 不成立，即存在 $X \subseteq U$ ，使得 $(g f) (X) \subset {(g f)}_{A - \{a\}} (X)$ .记 $X_{1} = (g f) (X)$ ， $X_{2} = {(g f)}_{A - \{a\}} (X)$ ，则有 $(X_{1}, f (X_{1}))$ ， $(X_{2}, f (X_{2})) \in L (\tilde{I})$ .因为：

\begin{array}{l} {f (X_{2})|}_{A - \{a\}} = {(f (g f)) (X)|}_{A - \{a\}} = \\ (f_{A - \{a\}} {(g f)}_{A - \{a\}}) (X) = {(f g f)}_{A - \{a\}} (X) = \\ f_{A - \{a\}} (X) = {f (X)|}_{A - \{a\}} = \\ {(f g f) (X)|}_{A - \{a\}} = f {((g f) (X))|}_{A - \{a\}} = \\ f {(X_{1})|}_{A - \{a\}} \end{array}

且 $X_{1} \neq X_{2}$ 可推出 $f (X_{1}) \neq f (X_{2})$ ，所以 $f (X_{1}) (a) \neq f (X_{2}) (a)$ ，故由辨识属性集定义可得：

D I S ((X_{1}, f (X_{1})), (X_{2}, f (X_{2}))) = \{a\}

定理得证.

定理8给出一个寻找核心属性的方法，也就是判断属性 $a$ 是否为核心属性，只需观察单点集 $\{a\}$ 是否为辨识属性矩阵中的一个元素.

定理9

协调集判定定理5 设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D \subseteq A$ ，则 $D$ 是协调集 $\Leftrightarrow$ 对于任何 $D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) \neq \emptyset$ ，都有 $D ⋂ D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) \neq \emptyset$ .

证明

“ $\Rightarrow$ ” 设 $D$ 是协调集， $D I S ((X_{i}, {\tilde{B}}_{i}),$

$(X_{j}, {\tilde{B}}_{j})) \neq \emptyset$ .由定理2易知， $X_{i} = {(g f)}_{D} (X_{i})$ ， $i = 1,2$ ，故 ${(g f)}_{D} (X_{1}) \neq {(g f)}_{D} (X_{2})$ ，从而 $f_{D} (X_{1}) \neq$

$f_{D} (X_{2})$ ，也就是， $\exists a \in D$ ，使得 $f (X_{1}) (a) \neq$

f (X_{2}) (a)

，即

{\tilde{B}}_{1} (a) \neq {\tilde{B}}_{2} (a)

.因此

D ⋂ D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) \neq \emptyset

“ $\Leftarrow$ ” 设对于任何 $D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) \neq \emptyset$ 都有 $D ⋂ D I S ((X_{i}, {\tilde{B}}_{i}), (X_{j}, {\tilde{B}}_{j})) \neq \emptyset$ .要证 $D$ 是协调集，由定理2可知只需证明 ${(g f)}_{D} \leq g f$ .假设 $\exists X \subseteq U$ ，有 $(g f) (X) \subset {(g f)}_{D} (X)$ ，记 $X_{1} = (g f) (X)$ ， $X_{2} = {(g f)}_{D} (X)$ ，则 $(X_{1}, f (X_{1}))$ ， $(X_{2}, f (X_{2})) \in L (\tilde{I})$ ，且 $X_{1} \subset X_{2}$ .因为 $f (X) = (f g f) (X) = f ((g f) (X)) =$

$f (X_{1})$ ，所以 $f_{D} (X) = f_{D} (X_{1})$ ，再由 ${f (X_{2})|}_{D} = f_{D} (X_{2}) = f_{D} ({(g f)}_{D} (X)) = f_{D} (X)$ 得 $f_{D} (X_{2}) = f_{D} (X_{1})$ .于是由辨别属性集定义可知 $D ⋂ D I S ((X_{1}, f (X_{1})), (X_{2}, f (X_{2}))) = \emptyset$ ，矛盾！因此， $\forall X \subseteq U$ ， ${(g f)}_{D} (X) \subseteq (g f) (X)$ ，即 ${(g f)}_{D} \leq g f$ .定理得证.

定理9说明，寻找形式模糊背景的约简，只需寻找与辨识属性矩阵中非空元素的交集不是空集的最小属性集.

例4表5为例1中形式模糊背景 $(U, A, \tilde{I})$ 的辨识属性矩阵，据此可以确定 $(U, A, \tilde{I})$ 的全部约简.

首先，由辨识属性矩阵的单点集可知，c和d为核心属性.

接下来，考虑属性集 $D_{1} = \{a, c, d\}$ ， $D_{2} = \{b, c, d\}$ 和 $D_{3} = \{c, d, e\}$ .

由于 $\{b, e\} = A - D_{1}$ 和 $\{a, e\} = A - D_{2}$ 以及它们的非空子集都不是辨识属性集，所以 $D_{1}$ 和 $D_{2}$ 都是协调集.对于 $D_{1}$ 的三个子集 $\{a, c\} \{a, d\}$ 和 $\{c, d\}$ 以及 $D_{2}$ 的三个子集 $\{b, c\} \{b, d\}$ 和 $\{c, d\}$ ，由于 $\{d\} \{c\}$ 和 $\{a, b\}$ 是辨识属性集，而且 $\{a, c\} ⋂$

$\{d\} = \emptyset$ ， $\{a, d\} ⋂ \{c\} = \emptyset$ ， $\{b, c\} ⋂ \{d\} = \emptyset$ ， $\{b, d\} ⋂ \{c\} = \emptyset$ ， $\{c, d\} ⋂ \{a, b\} = \emptyset$ ，所以六个子集都不是协调集，因此 $D_{1}$ 和 $D_{2}$ 是约简.

对于 $D_{3}$ ，由于 $D_{3} ⋂ \{a, b\} = \emptyset$ ，所以 $D_{3}$ 不是协调集，故它不是约简.

最后得到： $(U, A, \tilde{I})$ 共有两个约简 $\{a, c, d\}$ 和 $\{b, c, d\}$ .因此，属性 $c$ 和 $d$ 是核心属性， $a$ 和 $b$ 是相对必要属性， $e$ 是绝对不必要属性.

定义6

设 $(U, A, \tilde{I})$ 是一个形式模糊背景， $D I S (\tilde{I})$ 为其辨识属性矩阵，令：

Δ (\tilde{I}) = \overset{}{⋀} (\lor H)

其中， $\lor H$ 表示一些布尔变量的析取，这些布尔变量恰好对应 $H$ 中全部属性，在不至于引起混淆的情况下，布尔变量仍用其对应的属性的标记符号来表示，称 $Δ (\tilde{I})$ 为 $(U, A, \tilde{I})$ 的辨识函数.

运用吸收律和分配律可以将辨识函数 $Δ (\tilde{I})$ 变换成极小析取范式，再依据下面的定理可以得到形式模糊背景 $(U, A, \tilde{I})$ 的全部约简.

定理10

设 $(U, A, \tilde{I})$ 是一个形式模糊背景，若等式 $Δ (\tilde{I}) = (\land D_{1}) \lor (\land D_{2}) \lor \dots \lor (\land D_{l})$ 的右端为极小析取范式，则 $D_{1}, D_{2}, \dots, D_{l}$ 是 $(U, A, \tilde{I})$ 的全部约简.

证明

对于任何 $D_{i}$ （ $i \leq l$ ），由：

\overset{}{⋀} (\lor H) = (\land D_{1}) \lor (\land D_{2}) \lor \dots \lor (\land D_{l})

可知， $\land D_{i} \leq Δ (\tilde{I}) \leq \lor H$ ，这里 $H \in D I S (\tilde{I})$ ，且 $H \neq \emptyset$ .易证， $\land D_{i} \leq \lor H$ 等价于 $D_{i} ⋂ H \neq \emptyset$ ，故由定理9得 $D_{i}$ 是协调集.另外， $\forall a \in D_{i}$ ，记 $D_{i}^{'} = D_{i} - \{a\}$ ，则 $\land D_{i} < \land D_{i}^{'}$ .由析取范式的极小性知道， $\{D_{j}, j \leq l\}$ 中元素两两互不包含，因此 $D_{j}$ （ $j \neq i$ ）不是 $D_{i}^{'}$ 的子集，于是不难证出：

\begin{array}{l} Δ (\tilde{I}) = (\land D_{1}) \lor \dots \lor (\land D_{i - 1}) \lor (\land D_{i}) \lor \\ (\land D_{i + 1}) \lor \dots \lor (\land D_{l}) < (\land D_{1}) \lor \dots \lor \\ (\land D_{i - 1}) \lor (\land D_{i}^{'}) \lor (\land D_{i + 1}) \lor \dots \lor (\land D_{l}) \end{array}

(1)

假设 $D_{i}^{'}$ 是协调集，则 $\forall H \in D I S (\tilde{I})$ ，若 $H \neq \emptyset$ ，则有， $D_{i}^{'} ⋂ H \neq \emptyset$ ，从而， $\land D_{i}^{'} \leq \lor H$ ，进而可得 $\land D_{i}^{'} \leq Δ (\tilde{I})$ ，再由 $\land D_{j} \leq Δ (\tilde{I})$ （ $j \neq i$ ）得：

\begin{array}{l} (\land D_{1}) \lor \dots \lor (\land D_{i - 1}) \lor (\land D_{i}^{'}) \lor \\ (\land D_{i + 1}) \lor \dots \lor (\land D_{l}) \leq Δ \end{array}

与式（1）矛盾.因此， $D_{i}^{'}$ 不是协调集，故 $D_{i}$ 是约简.

设 $D$ 是一个约简，由于它是协调集，所以 $\forall H \in D I S (\tilde{I})$ ， $H \neq \emptyset$ ，有 $D ⋂ H \neq \emptyset$ ，故 $\land D \leq \lor H$ ，于是 $\land D \leq Δ (\tilde{I})$ .若 $D_{i} - D \neq \emptyset$ ， $i \leq l$ ，取 $a_{i} \in D_{i} - D$ ，记 $D^{'} = \{a_{i}, i \leq l\}$ ，则 $\land D_{i} \leq a_{i}$ ， $i \leq l$ ，进而 $\land D_{i} \leq \lor D^{'}$ ，于是 $Δ (\tilde{I}) = \underset{i \leq l}{\lor} (\land D_{i}) \leq \lor D^{'}$ ，故 $\land D \leq \lor D^{'}$ ，从而 $D ⋂ D^{'} \neq \emptyset$ ，即 $\exists a_{i}$ （ $i \leq l$ ），有 $a_{i} \in D$ ，这与 $a_{i} \in D_{i} - D$ 矛盾.因此， $\exists D_{i}$ （ $i \leq l$ ），使得 $D_{i} - D = \emptyset$ ，即 $D_{i} \subseteq D$ ，由于 $D_{i}$ 和 $D$ 都是约简，所以 $D_{i} = D$ .

综上得出， $D_{1}, D_{2}, \dots, D_{l}$ 是 $(U, A, \tilde{I})$ 的全部约简.定理得证.

例5 利用表5给出的例1中形式模糊背景 $(U, A, \tilde{I})$ 的辨识属性矩阵，可以写出辨识函数，将辨识函数转换成极小析取范式，即可得到背景的全部约简.

对辨识函数做范式转换时，由吸收律可知相同的辨识属性集在辨识函数的表达式可以只用一次.所有非空的不重复的辨识属性集为：

\{c\} \{d\} \{a, b\} \{a, c\} \{c, d\} \{b, d\} \{a, b, c\} \{a, b, e\} \{b, d, e\}

\{a, b, c, d\} \{a, b, c, e\} \{a, b, d, e\}, A

则：

\begin{array}{l} Δ (\tilde{I}) = c \land d \land (a \lor b) \land (a \lor c) \land (b \lor d) \land (c \lor d) \land \\ (a \lor b \lor c) \land (a \lor b \lor e) \land (b \lor d \lor e) \land \\ (a \lor b \lor c \lor d) \land (a \lor b \lor c \lor e) \land \\ (a \lor b \lor d \lor e) \land (\lor A) = \\ c \land d \land (a \lor b) = \\ (a \land c \land d) \lor (b \land c \land d) \end{array}

因此，依据定理8得 $\{a, c, d\}$ 和 $\{b, c, d\}$ 是背景的全部约简.这与例4中得到的结论一致.

从文献［29］可知，在某种意义下，经典概念格约简是唯一的.然而，从例4或例5可以看出，经典⁃模糊概念格的约简可能有多个.

利用辨识属性矩阵，构造辨识函数，求出经

典⁃模糊概念格的全部约简的计算复杂度比较高，但是在解决实际问题时可能只需求出一个约简，这时可以考虑采用如下较简单的约简计算方法：

（1）计算辨识矩阵，删除辨识矩阵中非极小的辨识属性集，初始化D为空集

（2）将辨识矩阵中所有单点集里的属性存入集合 $D$ 中，删除辨识矩阵中含有 $D$ 中属性的辨识属性集.若辨识矩阵中不存在为单点集的辨识属性集，则直接执行下一步.

（3）从辨识矩阵中任取一个非空的辨识属性集E，从此辨识属性集E中任取一个属性a，将该属性a存入集合 $D$ 中，删除辨识矩阵中所有含该属性a的辨识属性集，在辨识矩阵中，从每个非空辨识属性集中删除属于E的属性.

（4）重复步骤（3）.若辨识矩阵为空集，则停止计算，且 $D$ 为约简.

5 结论与展望

单边模糊概念格是经典概念格在形式模糊背景下的自然推广，单边模糊概念的特点是概念的外延和内涵一个是经典集合，一个是模糊集.尤其是经典⁃模糊概念，由于取外延是经典集合，所以运用经典⁃模糊概念提取决策规则更具优势.因此，研究基于经典⁃模糊概念的形式模糊背景的属性约简问题具有明显的实际应用意义.本文提出了经典⁃模糊概念格约简的概念，即寻找能够完全确定具有相同层次结构的经典⁃模糊概念格的最小属性集；给出了一些判断协调属性集的充分必要条件；相对于属性约简，对不同类型的属性进行了刻画；引入形式模糊背景的辨识属性矩阵的概念，并据此给出了属性约简的方法.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Ganter

，Wille

Formal concept analysis：Mathematical foundations

Springer Berlin Heidelberg，1999.

[本文引用: 2]

[2]

Wille

Restructuring lattice theory：An approach based on hierarchies of concepts

∥Rival I. Ordered sets. Springer Berlin Heidelberg，1982：445-470.