基于矩阵的模糊-经典概念格属性约简

引用本文

林艺东, 李进金, 张呈玲. 基于矩阵的模糊-经典概念格属性约简. 模式识别与人工智能, 2020,33(1): 21-31
LIN Yidong, LI Jinjin, ZHANG Chengling. Attribute Reductions of Fuzzy-Crisp Concept Lattices Based on Matrix. PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2020,33(1): 21-31. 复制到剪切板

Doi: 10.16451/j.cnki.issn1003-6059.202001003
Permissions

《模式识别与人工智能》编辑部

基于矩阵的模糊-经典概念格属性约简

林艺东^1,², 李进金¹, 张呈玲¹

1.闽南师范大学数学与统计学院漳州 363000

2.厦门大学数学科学学院厦门 361005

通讯作者：

李进金,博士,教授,主要研究方向为拓扑学、粗糙集、概念格等.E-mail:jinjinli@mnnu.edu.cn.
作者简介：

林艺东,博士研究生,主要研究方向为粗糙集、概念格等.E-mail:yidong_lin@yeah.net.

张呈玲,硕士研究生,主要研究方向为概念格.E-mail:cl-zhang@163.com.

收稿日期: 2019-05-23 接受日期: 2019-12-03

资助项目: 国家自然科学基金项目(No.11871259,11701258,61379021,61603173), 福建省自然科学基金项目(No.2019J01748)资助

摘要

基于模糊形式背景,文中研究模糊-经典概念的矩阵表示及属性约简的矩阵方法.首先,从矩阵视角提出模糊-经典概念的外延和内涵的矩阵表示,进一步给出属性粒矩阵的概念.为了得到模糊-经典概念格的最小生成组,研究交不可约元的矩阵判定定理.再在保持交不可约元外延不变的约简框架下,通过矩阵刻画属性子集之间的相似性,给出属性内外重要性的度量,提出模糊-经典概念格属性约简的矩阵方法.最后,通过数值实验验证文中方法的有效性.

关键词: 属性约简; 模糊-经典概念; 矩阵表示; 交不可约元

中图分类号:O29;TP18

Attribute Reductions of Fuzzy-Crisp Concept Lattices Based on Matrix

LIN Yidong^1,², LI Jinjin¹, ZHANG Chengling¹

1. School of Mathematics and Statistics, Minnan Normal University, Zhangzhou 363000

2. School of Mathematical Sciences, Xiamen University, Xiamen 361005

Corresponding author:
LI Jinjin, Ph.D., professor. His research interests include topology, rough set and concept lattices.
AboutAuthor:

LIN Yidong, Ph.D. candidate. His research interests include rough set and concept lattices.

ZHANG Chengling, master student. Her research interests include concept lattices.

Fund:Supported by National Natural Science Foundation of China(No.11871259,11701258,61379021,61603173), Natural Science Foundation of Fujian Province(No.2019J01748)

Abstract

A matrix representation of fuzzy-crisp formal concepts based on fuzzy formal contexts and a matrix approach of attribute reduction are studied. Firstly, the matrix representations of the extension and intension of fuzzy-crisp concept are developed from the matrix perspective, respectively. The definition and the computing method of attribute granular matrix are formulated subsequently. To find the minimal generation group of fuzzy-crisp concept lattice, matrix judgment theorem of meet-irreducible elements is discussed, and it is utilized to construct the attribute reduction framework preserving the extents of meet-irreducible elements. The significance measure of attribute is proposed by introducing the similarity degree between attribute subsets with aforementioned matrices. And then a heuristic matrix-method of attribute reduction is developed. Finally, numerical experiments verify the effectiveness of the proposed approach.

Key words: Key Words Attribute Reduction; Fuzzy-Crisp Concept; Matrix Representation; Meet-Irreducible Element

本文责任编委张燕平

Recommended by Associate Editor ZHANG Yanping

Wille^[1]提出形式概念分析理论(Formal Concept Analysis, FCA), 以形式背景为基础, 通过对象和属性特征之间的Galois连接形成概念, 进而由全体概念生成概念格.概念格刻画概念之间的泛化和特化关系, 具有典型的层次结构.此外, 概念的外延和内涵匹配的完美化在本质上体现数据集上对象和属性的关系.因此, FCA成为有效的数据挖掘和知识表示的工具, 已成功应用于数字图书馆、信息检索、软件工程、机器学习、数据挖掘与知识发现等领域^{[2, 3, 4, 5]}.

在经典概念格理论中, 概念格基于精确的形式背景, 通常是0-1二值表, 1表示对象与属性具有关系, 0表示无关系.然而, 在实际应用中, 对象与属性之间的二元关系往往是模糊、不确定的.概念的外延和内涵也不仅限于经典集合.为了克服经典概念格理论的局限性, 学者们将Zedeh的模糊集理论与FCA结合, 研究模糊概念格理论^{[6, 7, 8, 9, 10, 11, 12]}.在模糊形式背景中, Kraj $\overset{ˇ}{c}$ i^[13]和Yahia等^[14]分别独立定义建立在经典集与模糊集之间的模糊概念格, 称为单边模糊概念格.

属性约简是概念格理论研究的核心问题.Ganter等^[15]提出对象约简和属性约简的概念, 揭示概念格外延和内涵之间的内在关系.Zhang等^[16]构造辨识矩阵, 给出属性协调集的概念及判定定理.此后, 国内的研究主要基于文献[16]的约简理论框架.在单边模糊概念格属性约简的研究中, Shao等^[7]研究变精度概念格属性约简和对象约简问题.随后, Shao等^[8]从粒计算角度研究经典-模糊概念格的属性约简问题, 构造辨识矩阵.针对模糊-经典概念格, Li等^[9]提出保持交不可约元外延不变的属性约简概念, 给出不同属性特征的判定定理.Mao等^[10]结合定向图理论, 提出模糊-经典概念格属性约简方法.Shi等^[17]基于模糊-经典概念格, 提出对象粒约简方法.Li^[18]在区间值模糊形式背景中研究多水平属性约简方法.

通常, (模糊)形式背景是一个二元关系表, 可看成一个二元关系矩阵.同时, 概念之间的运算本质上是关于集合的运算, 而集合的运算通常可以转化为矩阵运算.于是, 张清新^[19]利用布尔矩阵提出概念格的属性约简方法.张呈玲等^[20]进一步在不协调形式背景下提出矩阵型属性约简方法.然而, 基于矩阵研究概念格的相关工作仍然较少见.特别地, 利用矩阵研究模糊形式背景属性约简的成果更少.目前仅有Lin等^{[21, 22]}在经典-模糊概念格的理论框架下进行一些相关工作.

本文受文献[19]启发, 在文献[9]的约简理论框架下, 研究模糊-经典概念格的矩阵表示及其属性约简的矩阵方法.首先提出概念外延与内涵的矩阵表示, 给出属性粒矩阵的概念.再基于矩阵框架给出交不可约元的矩阵判定定理.然后, 通过定义属性子集间的相似性刻画属性的重要度, 进而基于矩阵方法设计属性约简的启发式方法.最后, 通过数值实验评估本文方法效率.

1 相关知识

1.1 模糊-经典概念格

本节主要回顾模糊概念格的基本概念^{[7, 8]}和矩阵运算律.对任意非空集合U, P(U)表示U的幂集, F(U)表示U的模糊幂集.

设为模糊形式背景.其中:U={x₁, x₂, …, x_n}为对象集, A={a₁, a₂, …, a_m}为属性集, 为U与A之间的模糊关系.

与经典的形式背景不同, 对于任意x∈ U和a∈ A, $\tilde{I}$ (x, a)∈ [0, 1]表示对象x具有属性a的程度为 $\tilde{I}$ (x, a).定义映射

f∶ F(U)→ P(A), g∶ P(A)→ F(U),

对任意 ∈ F(U), B∈ P(A), 有

为了方便起见, 简记 , x∈ U, 简记g({a})为g(a), a∈ A.此外, 本文不考虑存在 ≠ 使的情况, 也不考虑存在a≠ b使g(a)=g(b)的情形.

根据映射f和g的定义, 可得如下性质:

若满足且 , 称为F的一个模糊-经典概念, 其中和B分别表示概念的外延和内涵.F的全体模糊-经典概念记为 , 称为F的模糊-经典概念格.对任意2个模糊-经典概念 , 有

并且

对于C⊆A, 记为模糊形式背景的子背景, 其中

对任意 , 有

其中

f_C∶ F(U)→ P(C), g_C∶ P(C)→ F(U).

此外, 若

则有

由此可知, 任何一个模糊-经典概念均可表示为由其内涵诱导的属性概念的交.

1.2 矩阵运算

首先引入特征向量.设论域U={x₁, x₂, …, x_n}, X⊆U的特征向量记为

λ _X=(λ _X(x₁), λ _X(x₂), …, λ _X(x_n)),

其中

λ _X(x_i)= $\{\begin{array}{l} 1, & x_{i} \in X \\ 0, & x_{i} \notin X \end{array}$

若 $\tilde{X}$ ∈ F(U), 则λ _X(x_i)∈ [0, 1]表示x_i属于X的隶属度.

其次, 设A= $(a_{ij})_{n \times m}$ 、B= $(b_{ij})_{n \times m}$ 、C= $(c_{ij})_{m \times p}$ 、D= $(d_{ij})_{p \times m}$ 均为模糊关系矩阵, 即a_ij、b_ij、c_ij、d_ij的取值均在0和1之间.规定矩阵运算如下:

1)A≤ B⇔ a_ij≤ b_ij, i=1, 2, …, n, j=1, 2, …, m;

2)A∨ B= $(a_{ij} \lor b_{ij})_{n \times m}$ ;

3)A∧ B= $(a_{ij} \land b_{ij})_{n \times m}$ ;

4)A· C= $(d_{ij})_{n \times p}$ , d_ij= $\underset{1 \leq k \leq m}{\lor}$ (a_ik∧ c_kj);

5)A-B= $(a_{ij} \land (1 - b_{ij} {))}_{n \times m}$ ;

6)~A= $(1 - a_{ij})_{n \times m}$ ;

7) $|A ⋂ D|$ 表示A与D相同行的个数.

其中:∨ 表示上确界(supremum), ∧ 表示下确界(infimum).

2 模糊-经典概念的矩阵表示

通常, 模糊形式背景是以数值表呈现, 行和列分别对应F中的对象和属性.换言之, 由于数值表体现对象与属性之间的模糊关系, 因此该数值表可作为模糊关系矩阵.记模糊形式背景F对应的模糊关系矩阵为 , 其中

$|U|$ =n, $|A|$ =m, c_ij= $\tilde{I}$ (x_i, a_j).

定理 1 设为模糊形式背景, 为模糊关系矩阵, 对任意B∈ P(A), 有

g(B)=~(λ _B· (~ ${M^{T}}_{I}$ )).

证明记λ _B=(t₁, t₂, …, t_m)且

$(a_{i})_{1 \times n}$ =~(λ _B· (~ ${M^{T}}_{I}$ )),

则

由定理1可知, 任何模糊-经典概念的外延均可通过特征向量与模糊关系矩阵之间的矩阵运算得到.然而, 概念的内涵无法通过类似的运算得到矩阵表示.为了解决这个问题, 定义如下矩阵运算律.

定义 1 设A= $(a_{ij})_{n \times m}$ 和B= $(b_{ij})_{m \times p}$ 为2个不同的模糊关系矩阵, 定义

AB= $(c_{ij})_{n \times p}$ , $|A|$ = $\overset{n}{\sum_{i = 1}} \overset{m}{\sum_{j = 1}} |a_{ij}|$ ,

其中

c_ij= $\underset{1 \leq k \leq m}{\land}$ (a_ikb_kj),
ai_kbk_j₌ $\{\begin{array}{l} 0, & a_{ik} > b_{kj} \\ 1, & a_{ik} \leq b_{kj} \end{array}$

定理 2 设为一个模糊形式背景, 为模糊关系矩阵, 对∀ X∈ F(U), 有

证明

推论 1 设为一个模糊形式背景, 为模糊关系矩阵, 对任意a_i∈ A, 都有

其中 (i, ∶ )为的第i行.

从粒计算角度上看, f°g(a_i)反映属性a_i的粒结构.另一方面, 模糊形式背景中所有属性的粒结构的特征向量可组成一个矩阵, 称为模糊形式背景的属性粒矩阵, 记为M.

定理 3 设为一个模糊形式背景, 为模糊关系矩阵, M为F的属性粒矩阵, 则

证明由推论1可得.

显然, M的第i行M(i, ∶ )=为属性a_i外延的内涵特征向量.

例1F为模糊形式背景, 如表1所示, 其中U={x₁, x₂, x₃, x₄, x₅}为对象集, A={a₁, a₂, a₃, a₄, a₅}为属性集.

表1 例1中模糊形式背景F Table 1 Fuzzy formal context F of example 1

由表1可知, F的模糊关系矩阵

若令

则根据定理1和定理2可得

由定理3可得F的属性粒矩阵:

3 基于属性粒矩阵的属性约简

下面基于Li等^[9]提出的属性约简框架探讨模糊形式背景属性约简的矩阵方法.∀ C⊆A, 设L_C表示的所有交不可约元组成的集合.交不可约元是指不能表示为除它本身之外的其它概念的交的概念.使用表示L_C中所有概念的外延集:

定义 2^[9] 设为模糊形式背景, B⊆A.若 , 称B为F的一个协调集.若B为一个协调集且其任意真子集C均不是协调集, 称B为F的一个约简.所有约简集的交称为F的核心, 记为core(F).

为了利用上述属性粒矩阵研究属性约简, 首先探讨交不可约元的矩阵判定定理.需要注意的是, 对于任意给定的模糊形式背景 , 对其进行预处理, 使任意两列均不相同, 仍记预处理后的模糊形式背景为F.此时任意a∈ A, b∈ A, 都有

g(a)≠ g(b).

定理 4 设为预处理后的模糊形式背景, 为模糊关系矩阵, M为F的属性粒矩阵.令

若

则(g(a_j), f°g(a_j))为一个交不可约元, 否则为交可约元.

证明由M(j, ∶ )为f°g(a_j)特征向量可知, P(j, ∶ )为g(a)的特征向量.若

表明

于是

因此, (g(a_j), f°g(a_j))为交不可约元.

例 2F为模糊形式背景, 如表2所示.

表2 例2中模糊形式背景F Table 2 Fuzzy formal context F of example 2

由表2可得F的属性粒矩阵:

根据定理4可得

P= $(\begin{array}{l} 1.0 & 1.0 & 1.0 & 1.0 \\ 0.7 & 1.0 & 1.0 & 0.9 \\ 1.0 & 1.0 & 1.0 & 1.0 \\ 0.5 & 0.6 & 0.9 & 0.9 \\ 0.5 & 0.6 & 0.9 & 0.9 \end{array})$ .

观察可得

而

因此F的交不可约元为

(g(a_i), f° g(a_i)), i=1, 2, 3, 4.

对任意C⊆A, 记 $L_{C}^{E}$ 对应的矩阵为 $M_{C}^{E}$ , 称为交不可约元外延矩阵. $M_{C}^{E}$ 可根据定理4获得, 在此不详细展开讨论.由上述研究可得如下推论.

推论 2 设为模糊形式背景, B⊆A.若 , 则B为F的协调集.若B为协调集, 且对任意C⊂B, 均有 , 则B为F的约简.

值得注意的是, 对于任意a∈ A, 属性概念(g(a), f°g(a))可能是交不可约元.反之, 任何交不可约元一定是属性概念.因此, ∀ B⊆A, 对∀ $M_{B}^{E}$ (i, ∶ ), 存在如下2种情形:

1)存在 $M_{A}^{E}$ (j, ∶ ), 使 $M_{B}^{E}$ (i, ∶ )= $M_{A}^{E}$ (j, ∶ );

2)对任意 $M_{A}^{E}$ (j, ∶ ), 均有 $M_{B}^{E}$ (i, ∶ )≠ $M_{A}^{E}$ (j, ∶ ).

另一方面, $M_{B}^{E}$ 的行数不大于 $M_{A}^{E}$ 的行数.由此可知, $M_{B}^{E}$ 与 $M_{A}^{E}$ 共同的行反映属性集B与A诱导的概念格结构的相似程度, 称为属性集B与A的相似程度.因此, 下面给出B与A的相似度量.

定义3 设为模糊形式背景, B⊆A. 分别为B和A对应的模糊-经典概念格的交不可约元矩阵, B和A的相似度定义为

E(B|A)= $\frac{|M_{A}^{E} ⋂ M_{B}^{E}|}{|M_{A}^{E} ⋂ M_{A}^{E}|}$ .

推论 3 设为模糊形式背景, B⊆A, B为F的协调集当且仅当E(B||A)=1.

推论 4 设为模糊形式背景, a∈ A, a∈ core(F)当且仅当E(A-{a}|A)< 1.

根据上述相似度定义, 给出属性重要度的2种度量.

定义 4 设为模糊形式背景, B⊆A.对任意a∈ B, 称

sig(B|a)=E(B|A)-E(B-{a}|A)

为属性a关于B的内重要度; 对任意a∈ A-B, 称

sig(a|B)=E(B∪ {a}|A)-E(B|A)

为属性a关于B的外重要度.

值得注意的是, sig(B|a)和sig(a|B)均通过相似度的变化刻画属性的重要性, 但前者反映当将属性a从B中去掉后相似度发生的变化, 而后者反映将a添加到B中所引起的相似度的变化.

定理 5 设为模糊形式背景, a∈ A, a为核心属性当且仅当sig(A|a)> 0, a为不必要属性当且仅当sig(A|a)=0.

证明由定义2及推论4可得.

因此

core(F)={a∈ A∶ sig_D(A|a)> 0}.

定理 6 设为模糊形式背景, B⊆A, B为F的一个约简当且仅当E(B|A)=1, 并且对∀ a∈ B, 都有sig(B|a)> 0.

证明由推论3及定理5可得.

定理 7 设为模糊形式背景.若F的全体交可约元为(g(a_i), f°g(a_i)), i∈ T, T为指标集, 令

r(A)=A-{a_i∶ i∈ T},

则F的约简与模糊形式背景的约简相同.

证明不妨设

只需证明C={a_i∶ i∈ T}为F中所有不必要属性组成的集合.由C的定义易知, 任意a_i∈ C都是F中不必要属性.

因此, 根据上述分析, 可设计基于矩阵模糊形式背景属性约简的启发式算法(A Heuristic Algorithm for Attribute Reduction of Fuzzy Context Based on Attribute Granular Matrix, RFAG).

算法 1 RFAG

输入模糊形式背景

输出F的一个约简RED

step 1 预处理并计算属性粒矩阵M_A;

step 2 计算 $M_{A}^{E}$ 和r(A), 且RED← r(A);

step 3 输出约简集RED, 算法结束.

容易验证计算属性粒矩阵的时间复杂度为O(|U||A|), 计算 $M_{A}^{E}$ 的时间复杂度为O(|U|· |A|).因此, 算法1时间复杂度为O(|U||A|).文献[9]中算法时间复杂度为

例3F为模糊形式背景, 如表3所示.

表3 例3中模糊决策形式背景F Table 3 Fuzzy formal context F of example 3

由表3可知F的交不可约元外延矩阵:

$M_{A}^{E}$ = $(\begin{array}{l} 0.5 & 0.6 & 1.0 & 1.0 & 1.0 \\ 0.7 & 0.7 & 0.9 & 0.9 & 0.9 \\ 0.7 & 1.0 & 1.0 & 0.9 & 0.9 \\ 0.5 & 0.7 & 0.9 & 0.9 & 0.9 \end{array})$ .

由算法1可得sig(A|a₅)=0, {a₁, a₂, a₃, a₄}为F的约简.

4 基于属性粒矩阵的协调模糊决策形式背景属性约简

本节基于属性粒矩阵讨论协调模糊决策形式背景的属性约简问题.设为模糊决策形式背景, 其中, A为条件属性, D为决策属性, A∩ D=Ø .此外, .为了避免混淆, 记U与D之间的Galois连接为(f_D, g_D).基于模糊-经典概念格的框架, 首先定义协调的模糊决策形式背景.

定义 5 称为协调的, 若

即对 , 存在

使 ; 否则, 称S是不协调的.

由此给出协调集、约简集及核心定义.

定义 6 设为协调模糊决策形式背景, 若B⊆A, 满足

称B为S的协调集.进一步地, 若B的任意真子集C均不是S的协调集, 称B为S的一个约简.所有约简集的交称为S的核心, 记为core(S).

约简是保持S协调性不变的极小条件属性子集.值得注意的是, 对任意

都有

另一方面, 根据定义5, 可发现如下事实.

推论 5 若为协调模糊决策形式背景, 则

其中分别表示的外延集族.

推论 6 若为协调模糊决策形式背景, 对任意决策属性d∈ D, 存在B⊆A, B≠ Ø , 使

即对任意交不可约元的外延集g_D(d)∈ $L_{D}^{E}$ , 存在

g( $a_{t_{1}}$ )∈ $L_{A}^{E}$ , g( $a_{t_{2}}$ )∈ $L_{A}^{E}$ , …, g( $a_{t_{p}}$ )∈ $L_{A}^{E}$ ,

使

g_D(d)= $\overset{p}{⋂_{i = 1}}$ g( $a_{t_{i}}$ ).

进一步地, 若B⊆A为协调集, 则存在

g( $a_{t_{1}}$ )∈ $L_{B}^{E}$ , g( $a_{t_{2}}$ )∈ $L_{B}^{E}$ , …, g( $a_{t_{p}}$ )∈ $L_{B}^{E}$ ,

使

g_D(d)= $\overset{p}{⋂_{i = 1}}$ g_B( $a_{t_{i}}$ ).

由第3节可知, 对任意B⊆A, $M_{B}^{E}$ 的任一行均对应一个属性概念的外延.对比 $M_{B}^{E}$ 和 $M_{{\tilde{I}}_{B}}$ 可得对应的属性.记由 $M_{B}^{E}$ 对应的属性组成的集合为Int(B), 特征向量为 $λ_{B}^{I}$ .此外, 令N(λ _B)为 $|B|$ × $|A|$ 矩阵, 任意一行均为λ _B.

例4 由例2可知,

$λ_{A}^{I}$ =(1, 1, 1, 1, 0),
N( $λ_{B}^{I}$ )= $(\begin{array}{l} 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \end{array})$

定理 8 设为协调决策形式背景, B⊆A, (i, ∶ )对应的外延为g_D(d_i).若

则存在

g( $a_{t_{1}}$ )∈ $L_{B}^{E}$ , g( $a_{t_{2}}$ )∈ $L_{B}^{E}$ , …, g( $a_{t_{p}}$ )∈ $L_{B}^{E}$ ,

使

g_D(d_i)= $\overset{p}{⋂_{j = 1}}$ g_B( $a_{t_{j}}$ ).

证明由已知可得,

因此

而

表明 , 这说明

于是

因此存在

使

g_D(d_i)= $\overset{p}{⋂_{j = 1}}$ g_B( $a_{t_{j}}$ ).

推论 7 设为协调决策形式背景, B⊆A为S的协调集, 则

所以由上述定理和推论, 可得如下协调集的判定定理.

定理 9 设为协调模糊决策形式背景, B⊆A:

1)若 , 则B为协调集;

2) 当且仅当B为协调集.

证明只证明2).

表明∀ g_D(d)∈ $L_{D}^{E}$ , d∈ D, 存在

$a_{t_{1}}$ ∈ Int(B), $a_{t_{2}}$ ∈ Int(B), …, $a_{t_{p}}$ ∈ Int(B),

使

g_D(d)= $\overset{p}{\underset{i = 1}{\land}}$ g_B( $a_{t_{i}}$ ).

显然, 定理9中2)等价于

例5S为一个模糊决策形式背景, 如表4所示.

表4 例5中模糊决策形式背景S Table 4 Fuzzy decision formal context S of example 5

可得在S中条件属性A和决策属性D下的所有概念如表5和表6所示.

表5 模糊决策形式背景S中条件属性A对应的概念 Table 5 Concepts with respect to A of fuzzy decision formal context S

	(对象, 属性)
C₁	({ $x_{1}^{1.0}$ , $x_{2}^{1.0}$ , $x_{3}^{1.0}$ , $x_{4}^{1.0}$ , $x_{5}^{1.0}$ }, Ø )
C₂	({ $x_{1}^{0.7}$ , $x_{2}^{1.0}$ , $x_{3}^{1.0}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, {a₃, a₅})
C₃	({ $x_{1}^{0.7}$ , $x_{2}^{0.7}$ , $x_{3}^{. 0.9}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, {a₂, a₃, a₅})
C₄	({ $x_{1}^{0.5}$ , $x_{2}^{0.7}$ , $x_{3}^{. 0.9}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, {a₂, a₃, a₄, a₅})
C₅	({ $x_{1}^{0.5}$ , $x_{2}^{0.6}$ , $x_{3}^{1.0}$ , $x_{4}^{1.0}$ , $x_{5}^{1.0}$ }, {a₁})
C₆	({ $x_{1}^{0.5}$ , $x_{2}^{0.6}$ , $x_{3}^{1.0}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, {a₁, a₃, a₅})
C₇	({ $x_{1}^{0.5}$ , $x_{2}^{0.6}$ , $x_{3}^{0.9}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, A)

表5 模糊决策形式背景S中条件属性A对应的概念 Table 5 Concepts with respect to A of fuzzy decision formal context S

表6 模糊决策形式背景S中决策属性D对应的概念 Table 6 Concepts with respect to D of fuzzy decision formal context S

	(对象, 属性)
C₁	({ $x_{1}^{1.0}$ , $x_{2}^{1.0}$ , $x_{3}^{1.0}$ , $x_{4}^{1.0}$ , $x_{5}^{1.0}$ }, Ø )
C₂	({ $x_{1}^{0.7}$ , $x_{2}^{1.0}$ , $x_{3}^{1.0}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, {d₁})
C₃	({ $x_{1}^{0.5}$ , $x_{2}^{0.7}$ , $x_{3}^{. 0.9}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, {d₁, d₂})
C₄	({ $x_{1}^{0.5}$ , $x_{2}^{0.6}$ , $x_{3}^{1.0}$ , $x_{4}^{1.0}$ , $x_{5}^{1.0}$ }, {d₃})
C₅	({ $x_{1}^{0.5}$ , $x_{2}^{0.6}$ , $x_{3}^{1.0}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, {d₁, d₃})
C₆	({ $x_{1}^{0.5}$ , $x_{2}^{0.6}$ , $x_{3}^{0.9}$ , $x_{4}^{0.9}$ , $x_{5}^{0.9}$ }, D)

表6 模糊决策形式背景S中决策属性D对应的概念 Table 6 Concepts with respect to D of fuzzy decision formal context S

显然,

所以模糊决策形式背景S是协调的.另外, 决策属性粒矩阵

M_D= $(\begin{array}{l} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 \end{array})$ .

根据定理4可得, 决策属性D对应的交不可约元矩阵

$M_{D}^{E}$ = $(\begin{array}{l} 0.7 & 1.0 & 1.0 & 0.9 & 0.9 \\ 0.5 & 0.7 & 0.9 & 0.9 & 0.9 \\ 0.5 & 0.6 & 1.0 & 1.0 & 1.0 \end{array})$ .

令B={a₁, a₃, a₄, a₅}, 由定理8可得

经检验

故B为协调集.

对任意B⊆A, 记为 $M_{D}^{B}$ .显然, $M_{D}^{B}$ 与 $M_{D}^{A}$ 共同的行反映由属性集B与A产生的 $L_{B}^{E}$ 与 $L_{A}^{E}$ 表示 $L_{D}^{E}$ 中元素能力的相似程度.因此, 给出B与A之间的相似度量.

定义 7 设为协调决策形式背景, B⊆A, B与A的相似度定义为

E(B|A, D)= $\frac{|M_{D}^{B} ⋂ M_{D}^{A}|}{|M_{D}^{A} ⋂ M_{D}^{A}|}$ .

推论 8 设为协调决策形式背景, B⊆A, B为S的协调集当且仅当

E(B|A, D)=1.

推论 9 设为协调决策形式背景, a∈ A, a∈ core(S)当且仅当

定义 8 设为协调决策形式背景, B⊆A, 对∀ a∈ B, 称

sig_D(B|a)=E(B|A, D)-E(B-{a}|A, D)

为属性a关于B的D内重要度.对∀ a∈ A-B, 称

sig_D(a|B)=E(B∪ {a}|A, D)-E(B|A, D)

为属性a关于B的D外重要度.

需要注意的是, sig_D(B|a)和sig_D(a|B)均通过相似度的变化刻画属性的重要性, 但前者刻画从B中除去属性a后相似度发生的变化, 而后者反映将a添加到B中引起的相似度的变化, 因此二者有本质区别.

定理 10 设为协调决策形式背景, a∈ A, a为核心属性当且仅当

sig_D(A|a)> 0,

a是不必要属性当且仅当

sig_D(A|a)=0.

证明由定义6及推论9可得.

因此

core(S)={a∈ A∶ sig_D(A|a)> 0}.

定理 11 设协调决策形式背景, B⊆A, 则B为S的一个约简当且仅当

E(B|A, D)=1,

且对于∀ a∈ B, 都有

sig_D(B|a)> 0.

证明由推论8及定理10可得.

因此, 根据上述分析, 可以基于矩阵设计协调模糊决策形式背景属性约简的启发式算法.

算法 2 基于属性粒矩阵的协调模糊决策形式背景

属性约简算法

输入协调模糊决策形式背景

输出S的一个约简RED

step 1 计算属性粒矩阵M_A、M_D, 令RED← Ø ;

step 2 对∀ a∈ A, 计算 $M_{D}^{A - {a}}$ 和 $M_{D}^{E}$ ;

step 3 对∀ a∈ A, 若 $M_{D}^{A - {a}}$ ≠ ~ $M_{D}^{E}$ , 则

RED← RED∪ {a};

step 4 若 $M_{D}^{RED}$ =~ $M_{D}^{E}$ , 执行step 7;

step 5 对∀ a∈ A-RED, 计算sig_D(a|RED);

step 6 选择属性a∈ A-RED, 满足

sig_D(a|RED)= $\max_{b \in A - RED}$ {sig_D(b|RED)},
RED← RED∪ {a};

step 7 对∀ a∈ RED, 若

sig_D(RED|a)> 0,

执行step 9;

step 8 若存在a∈ RED, 使

sig(RED|a)=0,

则

RED← RED-{a},

执行step 7;

step 9 输出约简集RED, 算法结束.

计算 $M_{D}^{E}$ 的时间复杂度为O(|U||D|), 计算 $M_{D}^{A - {a}}$ 的时间复杂度为O(|U||D|).此外, step 5和step 6的时间复杂度为O(|U||D||A|).因此算法2 的时间复杂度为O(|U||D||A|).

5 实验及结果分析

实验环境为Windows 10操作系统, Intel (R) Core (TM)i7-6700 CPU @3.41 GHz, 8 GB内存.软件为Matlab 9.3.实验所用数据为由表1、表3、表7、表8的模糊形式背景根据文献[23]方法组合生成以及从UCI获取的公开数据集.

表7 实验中第1个模糊形式背景F Table 7 Fuzzy formal context F used in experiment 1

表8 实验中第2个模糊形式背景F Table 8 Fuzzy formal context F used in experiment 2

设F₁、F₂为2个模糊形式背景.称[ $\begin{array}{l} F_{1} & F_{2} \end{array}$ ]为F₁、F₂的组合; 称 $[\begin{array}{l} F_{1} & 0 \\ 0 & F_{2} \end{array}]$ 为F₁、F₂的合并; 称 $[\begin{array}{l} F_{1} \\ F_{2} \end{array}]$ 为F₁、F₂的串联^[23].

如表9所示, F₁、F₂和F₃分别为表1、表3和表7的模糊形式背景.F₄为表7和表8转置的组合.F₅先由F₄、F₁和F₂合并, 再与F₃组合.F₁与2个F₂组合及合并, 再与F₃组合得到F₆.F₇为F₁、F₄的合并先与F₁组合, 再与F₂和F₃的串联.F₈为F₁~F₄的合并.F₉先由F₂与F₃组合, 再与F₄串联得到.F₄先与F₂、F₃的组合合并, 再和F₁串联得到F₁₀.另外, F₁₁为F₃的100倍合并.F₁₂为F₄的79倍合并.F₁₃为F₅的66倍合并.F₁₄为F₆的51倍合并.F₁₅为F₇的70倍合并.F₁₆为F₈的68倍合并.F₁₇为F₉的80倍合并.F₁₈为F₁₀的40倍合并.F₁₉为F₄的63倍合并.F₂₀是F₁₀的72倍合并.

表9 组合生成的实验数据 Table 9 Experimental datasets generated by combination

名称	$\|U\|$	$\|A\|$	名称	$\|U\|$	$\|A\|$
F₁	5	5	F₁₁	500	500
F₂	5	5	F₁₂	395	632
F₃	5	5	F₁₃	990	1518
F₄	5	8	F₁₄	510	1020
F₅	15	23	F₁₅	700	1260
F₆	10	20	F₁₆	1360	1564
F₇	10	18	F₁₇	800	800
F₈	20	23	F₁₈	600	720
F₉	10	10	F₁₉	315	504
F₁₀	15	18	F₂₀	1080	1296

表9 组合生成的实验数据 Table 9 Experimental datasets generated by combination

此外, 从UCI公开数据集中选取6个数据集, 检验本文方法在真实数据上的可行性和有效性, 数据见表10.每个数据集均归一化到[0, 1], 保留一位小数.

表10 UCI数据集上的实验数据 Table 10 Experimental datasets on UCI dataset

名称	$\|U\|$	$\|A\|$
Australian_credit	14	690
Crx	15	690
Diabe	34	366
Heart	13	270
Horse	22	368
Wison	9	699

表10 UCI数据集上的实验数据 Table 10 Experimental datasets on UCI dataset

对比方法为CAR(Computing All Attribute Redu-cts of L( $\tilde{U}$ , $\tilde{A}$ , $\tilde{I}$ ))^[9], CAR能求出模糊形式背景的所有约简, 而RFAG只能求出一个约简.为了便于实验对比, 在CAR的框架下找出模糊形式背景的一个约简.表11和表12分别给出2种算法在2个数据集上的实验结果.

表11 两种算法在组合数据集上的实验结果 Table 11 Experimental results of 2 algorithms on composite datasets

表12 两种算法在UCI数据集上的实验结果 Table 12 Experimental results of 2 algorithms on UCI datasets

由表11可见, RFAG得到的约简个数大部分小于CAR, 这是因为若形式背景存在相同的列时, 由CAR得到的约简存在冗余属性.从运行时间上看, 在每个数据集上, RFAG的运行时间均少于CAR.

由表12可见, 在每个UCI数据集上, 由RFAG得到的约简个数和运行时间均小于CAR.综上可知, RFAG优于CAR.

6 结束语

本文主要研究模糊-经典概念格的矩阵表示及属性约简的矩阵方法.提出概念外延和内涵的矩阵表示方法, 给出属性粒矩阵的定义.利用属性粒矩阵, 给出交不可约元的矩阵判定定理.在保持交不可约元的外延矩阵不变的基础上, 提出属性子集之间的相似性度量, 进而提出属性内外重要度的定义.随后设计属性约简的启发式算法.最后通过数值实验验证本文方法的效率.本项工作不仅丰富模糊-经典概念格的理论基础, 也为形式概念分析的研究提供一种途径.

参考文献

文献选项

[1]	WILLE R. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts // RIVAL I, ed. Ordered Sets. Berlin, Germany: Springer, 1982: 445-470. [本文引用:1]
[2]	CARPINETO C, ROMANO G. A Lattice Conceptual Clustering System and Its Application to Browsing Retrieval. Machine Learning, 1996, 24(2): 95-122. [本文引用:1]
[3]	HUANG C C, LI J H, MEI C L, et al. Three-Way Concept Lear-ning Based on Cognitive Operators: An Information Fusion Viewpoint. International Journal of Approximate Reasoning, 2017, 83: 218-242. [本文引用:1]
[4]	RAJAPAKSE R K, DENHAM M. Text Retrieval with More Realistic Concept Matching and Reinforcement Learning. Information Proce-ssing and Management, 2006, 42(5): 1260-1275. [本文引用:1]
[5]	VALTCHEV P, MISSAOUI R, GODIN R. Formal Concept Analysis for Knowledge Discovery and Data Mining: The New Challenges // Proc of the International Conference on Formal Concept Analysis. Berlin, Germany: Springer, 2004: 352-371. [本文引用:1]
[6]	XU W H, LI W T. Granular Computing Approach to Two-Way Lear-ning Based on Formal Concept Analysis in Fuzzy Datasets. IEEE Transactions on Cybernetics, 2016, 46(2): 366-379. [本文引用:1]
[7]	SHAO M W, YANG H Z, WU W Z. Knowledge Reduction in Formal Fuzzy Contexts. Knowledge-Based Systems, 2015, 73: 265-275. [本文引用:3]
[8]	SHAO M W, LEUNG Y, WANG X Z, et al. Granular Reducts of Formal Fuzzy Contexts. Knowledge-Based Systems, 2016, 114: 156-166. [本文引用:3]
[9]	LI K W, SHAO M W, WU W Z. A Data Reduction Method in Formal Fuzzy Contexts. International Journal of Machine Learning and Cybernetics, 2017, 8(4): 1145-1155. [本文引用:7]
[10]	MAO H, MIAO H R. Attribute Reduction Based on Directed Gra-ph in Formal Fuzzy Contexts. Journal of Intelligent and Fuzzy Systems, 2018, 34(6): 4139-4148. [本文引用:2]
[11]	WU X Y, WANG J Y, SHI L, et al. A Fuzzy Formal Concept Analysis-Based Approach to Uncovering Spatial Hierarchies among Vague Places Extracted from User-Generated Data. International Journal of Geographical Information Science, 2019, 33(5): 991-1016. [本文引用:1]
[12]	FORMICA A. Similarity Reasoning in Formal Concept Analysis: From One-to Many-Valued Contexts. Knowledge and Information Systems, 2019, 60(2): 715-739. [本文引用:1]
[13]	KRAJČS. Cluster Based Efficient Generation of Fuzzy Concepts. Neural Network World, 2003, 13(5): 521-530. [本文引用:1]
[14]	YAHIA S B B, AROUR K, SLIMANI A, et al. Discovery of Compact Rules in Relational Databases. Information Science Journal, 2000, 4(3): 497-511. [本文引用:1]
[15]	GANTER B, WILLE R. Formal Concept Analysis. Berlin, Germany: Springer, 1999. [本文引用:1]
[16]	ZHANG W X, WEI L, QI J J. Attribute Reduction in Concept La-ttice Based on Discernibility Matrix // Proc of the International Workshop on Rough Sets, Fuzzy Sets, Data Mining, and Granular-Soft Computing. Berlin, Germany: Springer, 2005: 157-165. [本文引用:2]
[17]	SHI L L, YANG H L. Object Granular Reduction of Fuzzy Formal Contexts. Journal of Intelligent and Fuzzy Systems, 2018, 34(1): 633-644. [本文引用:1]
[18]	LI L F. Multi-level Interval-Valued Fuzzy Concept Lattices and Their Attribute Reduction. International Journal of Machine Lear-ning and Cybernetics, 2017, 8(1): 45-56. [本文引用:1]
[19]	张清新. 基于布尔矩阵的概念格属性约简方法. 硕士学位论文. 漳州: 漳州师范学院, 2012. (ZHANG Q X. Attribute Reduction Method for Concept Lattices Based on Boolean Matrices. Zhangzhou, China: Zhangzhou Normal University, 2012. ) [本文引用:2]
[20]	张呈玲,李进金,林艺东. 不协调决策形式背景的矩阵型属性约简[J/OL]. [2019-04-15]. http: //kns. cnki. net/kcms/detail/11. 5602. TP. 20190612. 1553. 018. html. (ZHANG C L, LI J J, LIN Y D. Matrix-Type Attribute Reduction for Inconsistent Formal Decision Contexts[J/OL]. [2019-04-15]. http://kns.cnki.net/kcms/detail/11.5602.TP.20190612.1553.018.html [本文引用:1]
[21]	LIN Y D, LI J J. A Boolean Matrix Approach for Granular Reduction in Formal Fuzzy Contexts. Journal of Intelligent and Fuzzy Systems, 2019, 37(4): 5217-5228. [本文引用:1]
[22]	LIN Y D, LI J J, TAN A H, et al. Granular Matrix-Based Know-ledge Reductions of Formal Fuzzy Contexts[C/OL]. [2019-04-15]. https://xs.scihub.ltd/https:doi.org/10.1007/s13042-019-01022-4. [本文引用:1]
[23]	LI J H, MEI C L, LÜ Y J. A Heuristic Knowledge-Reduction Met-hod for Decision Formal Contexts. Computers and Mathematics with Applications, 2011, 61(4): 1096-1106. [本文引用:2]

1982

0.0

... Wille^[1]提出形式概念分析理论(Formal Concept Analysis, FCA),以形式背景为基础,通过对象和属性特征之间的Galois连接形成概念,进而由全体概念生成概念格 ...

1996

0.0

... 因此,FCA成为有效的数据挖掘和知识表示的工具,已成功应用于数字图书馆、信息检索、软件工程、机器学习、数据挖掘与知识发现等领域^[2,3,4,5] ...

2017

0.0

... 因此,FCA成为有效的数据挖掘和知识表示的工具,已成功应用于数字图书馆、信息检索、软件工程、机器学习、数据挖掘与知识发现等领域^[2,3,4,5] ...

2006

0.0

... 因此,FCA成为有效的数据挖掘和知识表示的工具,已成功应用于数字图书馆、信息检索、软件工程、机器学习、数据挖掘与知识发现等领域^[2,3,4,5] ...

2004

0.0

... 因此,FCA成为有效的数据挖掘和知识表示的工具,已成功应用于数字图书馆、信息检索、软件工程、机器学习、数据挖掘与知识发现等领域^[2,3,4,5] ...

2016

0.0

... 为了克服经典概念格理论的局限性,学者们将Zedeh的模糊集理论与FCA结合,研究模糊概念格理论^{[6,7,8,9,10,11,12]} ...

2015

0.0

... 为了克服经典概念格理论的局限性,学者们将Zedeh的模糊集理论与FCA结合,研究模糊概念格理论^{[6,7,8,9,10,11,12]} ...

... 在单边模糊概念格属性约简的研究中,Shao等^[7]研究变精度概念格属性约简和对象约简问题 ...

... 1 模糊-经典概念格本节主要回顾模糊概念格的基本概念^[7,8]和矩阵运算律 ...

2016

0.0

... 为了克服经典概念格理论的局限性,学者们将Zedeh的模糊集理论与FCA结合,研究模糊概念格理论^{[6,7,8,9,10,11,12]} ...

... 随后,Shao等^[8]从粒计算角度研究经典-模糊概念格的属性约简问题,构造辨识矩阵 ...

... 1 模糊-经典概念格本节主要回顾模糊概念格的基本概念^[7,8]和矩阵运算律 ...

2017

0.0

... 为了克服经典概念格理论的局限性,学者们将Zedeh的模糊集理论与FCA结合,研究模糊概念格理论^{[6,7,8,9,10,11,12]} ...

... 针对模糊-经典概念格,Li等^[9]提出保持交不可约元外延不变的属性约简概念,给出不同属性特征的判定定理 ...

... 本文受文献[19]启发,在文献[9]的约简理论框架下,研究模糊-经典概念格的矩阵表示及其属性约简的矩阵方法 ...

... 3 基于属性粒矩阵的属性约简下面基于Li等^[9]提出的属性约简框架探讨模糊形式背景属性约简的矩阵方法 ...

... 定义 2^[9] 设为模糊形式背景,B⊆A ...

... 文献[9]中算法时间复杂度为 ...

... 对比方法为CAR(Computing All Attribute Redu-cts of L( U~, A~, I~))^[9],CAR能求出模糊形式背景的所有约简,而RFAG只能求出一个约简 ...

2018

0.0

... 为了克服经典概念格理论的局限性,学者们将Zedeh的模糊集理论与FCA结合,研究模糊概念格理论^{[6,7,8,9,10,11,12]} ...

... Mao等^[10]结合定向图理论,提出模糊-经典概念格属性约简方法 ...

2019

0.0

... 为了克服经典概念格理论的局限性,学者们将Zedeh的模糊集理论与FCA结合,研究模糊概念格理论^{[6,7,8,9,10,11,12]} ...

2019

0.0

... 为了克服经典概念格理论的局限性,学者们将Zedeh的模糊集理论与FCA结合,研究模糊概念格理论^{[6,7,8,9,10,11,12]} ...

2003

0.0

... 在模糊形式背景中,Kraj cˇi^[13]和Yahia等^[14]分别独立定义建立在经典集与模糊集之间的模糊概念格,称为单边模糊概念格 ...

2000

0.0

... 在模糊形式背景中,Kraj cˇi^[13]和Yahia等^[14]分别独立定义建立在经典集与模糊集之间的模糊概念格,称为单边模糊概念格 ...

1999

0.0

... Ganter等^[15]提出对象约简和属性约简的概念,揭示概念格外延和内涵之间的内在关系 ...

2005

0.0

... Zhang等^[16]构造辨识矩阵,给出属性协调集的概念及判定定理 ...

... 此后,国内的研究主要基于文献[16]的约简理论框架 ...

2018

0.0

... Shi等^[17]基于模糊-经典概念格,提出对象粒约简方法 ...

2017

0.0

... Li^[18]在区间值模糊形式背景中研究多水平属性约简方法 ...

2012

0.0

... 于是,张清新^[19]利用布尔矩阵提出概念格的属性约简方法 ...

... 本文受文献[19]启发,在文献[9]的约简理论框架下,研究模糊-经典概念格的矩阵表示及其属性约简的矩阵方法 ...

2019

0.0

... 张呈玲等^[20]进一步在不协调形式背景下提出矩阵型属性约简方法 ...

2019

0.0

... 目前仅有Lin等^[21,22]在经典-模糊概念格的理论框架下进行一些相关工作 ...

0.0

... 目前仅有Lin等^[21,22]在经典-模糊概念格的理论框架下进行一些相关工作 ...

2011

0.0

... 实验所用数据为由表1、表3、表7、表8的模糊形式背景根据文献[23]方法组合生成以及从UCI获取的公开数据集 ...

... 称 F1F2为F₁、F₂的串联^[23] ...