对象导出三支概念格的矩阵粗糙熵约简

Matrix Rough Entropy-based Reductions of Object-induced Three-way Concept Lattices

摘要

属性约简是形式概念分析的重要研究问题，寻求高效的属性约简方法也是关注热点。本文在形式背景中引入矩阵粗糙熵，探讨对象导出三支概念格（Object-induced Three-way Concept Lattice，简称OE-概念格）上基于矩阵粗糙熵的属性约简方法。首先将OE-对象粒矩阵与粗糙熵相结合，定义OE-概念格的OE-矩阵粗糙熵，基于OE-对象粒矩阵的相似性提出OE-矩阵相似熵，研究它们的性质；其次在形式背景上定义OE-概念格的矩阵粗糙熵协调集和矩阵粗糙熵约简集，给出基于矩阵粗糙熵的协调集判定定理；利用OE-矩阵相似熵引入属性的重要性度量，进一步给出获取矩阵粗糙熵属性约简的方法和算法；最后在UCI(University of California, Irvine)数据集上进行属性约简实验，对于属性量小于10的数据集和属性量大于10的数据集，约简时间分别平均缩短了69.1%和97.5%，进而验证了该算法更适用于大样本数据。

Abstract

Attribute reduction is an important research issue in formal concept analysis, and seeking efficient attribute reduction methods is also a hot topic of concern. This paper studies attribute reductions of the object-induced three-way concept lattices by introducing matrix rough entropy into the formal context. Firstly, the OE-matrix (object-induced three-way matrix) rough entropy of the OE-concept lattice is defined by combining the OE-object granular matrix with rough entropy, and OE-matrix similarity entropy based on the similarity of OE-object granular matrix is proposed and the related properties of them are discussed. Secondly, the matrix rough entropy consistent set and matrix rough entropy reduction set of the OE-concept lattices are defined. Then the judgment theorems for the matrix rough entropy consistent set are given. The importance measure of attributes applying OE-matrix similarity entropy is proposed, by which the method and corresponding algorithm for obtaining matrix rough entropy attribute reduction are furtherly investigated. Finally, experiments of attribute reduction were conducted on the UCI (University of California, Irvine) dataset. The experimental results showed that for datasets with the count of attribute less than 10 and datasets with the count of attribute greater than 10, the reduction time was reduced by an average of 69.1% and 97.5%, respectively, confirming that the algorithm is more suitable for the large sample data.

Graphical abstract

关键词

形式背景 / 对象粒矩阵 / 矩阵粗糙熵协调集 / 矩阵相似熵 / 属性约简

Key words

formal context / object granular matrix / matrix rough entropy consistent set / matrix similarity entropy / attribute reduction

0 引言

由德国数学家Wille提出的概念格理论^［1］（也称为形式概念分析理论），是一种数据处理工具。该理论以序理论和完备格为理论基础，以形式背景和形式概念为研究对象来表达和处理概念与概念间的层次关系^［2］。概念格作为数据分析的一种数学工具，已经被广泛应用于信息检索、知识发现、数据挖掘^［3-6］等领域。

属性约简是简化数据结构，去除数据分析中冗余信息的重要工具，也是形式概念分析的重要研究内容之一。张文修等^［7］首次将辨识属性矩阵引入形式概念分析中，提出了保持概念格整体结构不变的属性约简方法。Qi^［8］将文献［7］的方法进行改进，提出了只需比较上下邻关系的形式概念来构造辨识矩阵的方法。随着发展，概念格属性约简理论框架不断丰富，主要包括基于格结构^［9-10］、基于不可约元^［11-12］以及基于粒计算^［13-15］的属性约简方法。形式概念由外延及内涵构成，外延为对象子集，内涵为属性子集。由于一个形式概念寻找对象共同具有的属性，而未考虑共同不具有的属性，故Qi等^［16］将三分类即三支决策思想^［17］与形式概念分析相结合，提出对象/属性导出概念格（Object-induced/Attribute-induced Three-way Concept Attice，简称OE/AE-概念格）理论。三支概念结合正算子和负算子同时表达共同具有和共同不具有两种语义，蕴含信息更加丰富，更符合实际。三支概念格提出以来，三支概念格的形式背景属性约简也是热点关注问题。Ren等^［18］分别从粒计算、不可约元及格结构等角度研究了OE-概念格和AE-概念格的属性约简问题，分别给出了四种约简方法，并探究了各方法之间的关系。常欣欣等^［19］改进了OE-概念格粒约简中的可辨识函数，改进后的方法可不用构造OE-概念格即可求出粒约简。由于形式背景为二元关系表，可视为布尔矩阵，故张呈玲等^［20］借助布尔矩阵理论，研究了保持OE-概念格对象粒矩阵不变的属性约简问题。

信息熵^［21］作为一种处理不确定性的度量工具，且已被广泛应用于解决形式背景中的属性约简问题。Li等^［22］用信息熵计算属性权重来获得形式背景的属性约简。Singh等^［23］将信息熵加权方法应用于模糊概念格中进行属性约简。粗糙熵^［24］是用以衡量不完备信息系统中知识的不确定性方法。黄兵等^［25］将引入了一般二元关系下的粗糙熵来刻画知识的粗糙性和粗集粗糙性。李美争等^［26］将粗糙熵引入形式背景中，将所有概念的外延看作每个元素的邻域来定义粗糙熵进行概念格的属性约简。接着，陈东晓等^［27］从信息粒的角度出发，提出了基于信息熵研究形式背景属性约简的方法。贺青青等^［28］将布尔矩阵与信息熵相联系，提出了基于矩阵熵的形式背景属性约简方法。将信息熵应用于三支概念格的属性约简研究较少。吴荣等^［29］结合OE-对象粒和信息熵定义了OE-概念格的熵协调集和熵约简。

在当今大数据时代，数据爆炸式增长，对海量数据进行有效处理成为大势所趋，对大数据下属性约简效率的要求也更高。而矩阵能对海量数据进行快速运算，是一种高效的数据处理工具。为解决数据量庞大导致的约简时间长、效率不够高等问题，本文将OE-对象粒矩阵与粗糙熵结合，提出基于矩阵粗糙熵的OE-概念格属性约简新方法，该方法首先将OE-对象粒矩阵引入粗糙熵，提出OE-矩阵粗糙熵，应用OE-矩阵粗糙熵引入形式背景上OE-概念格的矩阵粗糙熵约简，进而给出判定矩阵粗糙熵协调集的方法，最后借助OE-对象粒矩阵的相似性，引入OE-矩阵相似熵，给出属性的重要性度量，由此构造获取OE-概念格矩阵粗糙熵约简的算法。

1 预备知识

定义1^［30］ 三元组\left(U,A,I\right)称为形式背景，其中U=\left\{x_{\mathrm{1}},x_{\mathrm{2}},\cdots ,x_n\right\}为非空有限对象集，A=\left\{a_{\mathrm{1}},a_{\mathrm{2}},\cdots ,a_m\right\}为非空有限属性集，二元关系I\subseteq U\times A，对任意x\in U，a\in A，\left(x,a\right)\in I表示对象x具有属性a，\left(x,a\right)\notin I表示对象x不具有属性a。Ganter和Wille^［30］给出了形式背景上的一对算子：对任意X\subseteq U，B\subseteq A，

\begin{array}{l}{X}^{\mathrm{*}}=\left\{a\in A\left|\forall x\in X,\left(x,a\right)\in I\right.\right\},\\ B^{\mathrm{*}}=\left\{x\in U\left|\forall a\in B,\left(x,a\right)\in I\right.\right\},\end{array}（1）

X^{\mathrm{*}}表示X中对象共同具有的属性集合，B^{\mathrm{*}}表示共同具有B中所有属性的对象集合。若X^{\mathrm{*}}=B且B^{\mathrm{*}}=X，称\left(X,B\right)为\left(U,A,I\right)上的形式概念，X和B分别称为\left(X,B\right)的外延和内涵。所有形式概念构成的集合记为L\left(U,A,I\right)。

基于公式（1），Qi等定义了\left(U,A,I\right)上的一对补算子^［16］：对任意X\subseteq U，B\subseteq A，

\begin{array}{l}{X}^{\overline{\mathrm{*}}}=\left\{a\in A\left|\forall x\in X,\left(x,a\right)\notin I\right.\right\},\\ B^{\overline{\mathrm{*}}}=\left\{x\in U\left|\forall a\in B,\left(x,a\right)\notin I\right.\right\},\end{array}（2）

称其为负算子，称公式（1）中算子为正算子。

设S是非空集合，P\left(S\right)为集合S的幂集，DP\left(S\right)=P\left(S\right)\times P\left(S\right)。在DP\left(S\right)上定义集合间的运算^［16］：对任意\left(A,B\right)，\left(C,D\right)\in DP\left(S\right)，

（1） \left(A,B\right)\bigcap \left(C,D\right)=\left(A\bigcap C,B\bigcap D\right),\left(A,B\right)\bigcup (C,D)=(A\bigcup C,B\bigcup D);

（2） {\left(A,B\right)}^c=\left(A^c,B^c\right)；

（3） \left(A,B\right)\subseteq \left(C,D\right)\iff A\subseteq C且B\subseteq D。

定义2^［16］ 设\left(U,A,I\right)是形式背景。对任意X\subseteq U，B,C\subseteq A，定义算子

，

{\left(B,C\right)}^{\cdot >}=\left\{x\in U\left|x\in B^{\mathrm{*}}\right.\wedge x\in C^{\overline{\mathrm{*}}}\right\}=B^{\mathrm{*}}\bigcap C^{\overline{\mathrm{*}}}，

称算子对为形式背景\left(U,A,I\right)上的对象导出三支算子，简称OE-算子。

若\left(X,\left(B,C\right)\right)满足，{\left(B,C\right)}^{\cdot >}=X，称\left(X,\left(B,C\right)\right)为OE-概念，X和\left(B,C\right)分别称为\left(X,\left(B,C\right)\right)的外延和内涵。所有OE-概念构成的集合记为L_{\mathrm{O}\mathrm{E}}\left(U,A,I\right)。\forall \left(X,\left(B,C\right)\right),\left(Y,\left(D,E\right)\right)\in L_{\mathrm{O}\mathrm{E}}\left(U,A,I\right)，L_{\mathrm{O}\mathrm{E}}\left(U,A,I\right)上的序关系“\le”定义为：\left(X,\left(B,C\right)\right)\le \left(Y,\left(D,E\right)\right)\iff X\subseteq Y\iff \left(B,C\right)\supseteq\left(D,E\right)。其上确界与下确界定义为：

，

，

则\left(L_{\mathrm{O}\mathrm{E}}\left(U,A,I\right),\le \right)为完备格，称为\left(U,A,I\right)的对象导出三支概念格，简称OE-概念格^［16］。

对任意x\in U，有L_{\mathrm{O}\mathrm{E}}\left(U,A,I\right)， 称为OE-对象粒概念。对任意B\subseteq A，称\left(U,B,I_B\right)为\left(U,A,I\right)的子形式背景，其中I_B=I\cap (U\times B)。子形式背景\left(U,B,I_B\right)上的OE-算子记为和\cdot {>}_B，则\forall X\subseteq U，C,D\subseteq A有，，{(C,D)}^{\cdot {>}_B}={(C,D)}^{\cdot >A}={\left(C,D\right)}^{\cdot >}。

取值为0或1的矩阵称为布尔矩阵，其运算性质如下：

性质1^［31］ 设\mathit{M}={\left(a_{ij}\right)}_{n\times m}，\mathit{N}={\left(b_{ij}\right)}_{n\times m}，\mathit{P}={\left(c_{ij}\right)}_{m\times p}是布尔矩阵， 则以下性质成立：

（1） \mathit{M}\le \mathit{N}\iff a_{ij}\le b_{ij}，i\le n，j\le m；

（2） \mathit{M}\vee \mathit{N}={\left(a_{ij}\vee b_{ij}\right)}_{n\times m}，\mathit{M}\wedge \mathit{N}={\left(a_{ij}\wedge b_{ij}\right)}_{n\times m}；

（3） \mathit{M}\cdot \mathit{P}={\left(d_{ij}\right)}_{n\times p}，其中d_{ij}=\underset{\mathrm{1}\le k\le m}{\vee }\left(a_{ik}\wedge c_{kj}\right)；

（4） \mathit{M}-\mathit{N}={\left(a_{ij}\wedge \left(\mathrm{1}-b_{ij}\right)\right)}_{n\times m}；

（5） \sim \mathit{M}={\left(\mathrm{1}-a_{ij}\right)}_{n\times m}。

记\mathit{M}\left(i,:\right)和\mathit{M}\left(:,j\right)分别为矩阵\mathit{M}的第i行和第j列，\mathit{M}\left(i,j\right)为矩阵\mathit{M}第i行第j列所对应的元素。对任意X\subseteq U，X的特征向量为\mathit{\lambda }\left(X\right)=\left(X\left(x_{\mathrm{1}}\right),X\left(x_{\mathrm{2}}\right),\cdots ,X\left(x_n\right)\right)，其中X\left(x_i\right)=\mathrm{1}\iffx_i\in X。

定义3^［20］ 设\left(U,A,I\right)是形式背景。记r_{ij}=\mathrm{1}\iff\left(x_i,a_j\right)\in I。称{\mathit{M}}_I={\left(r_{ij}\right)}_{n\times m}是I的关系矩阵。称{\mathit{M}}^{+}=\sim \left({\mathit{M}}_I\cdot \left(\sim {{\mathit{M}}_I}^{\mathrm{T}}\right)\right)为正对象粒矩阵，称{\mathit{M}}^{-}=\sim \left(\left(\sim {\mathit{M}}_I\right)\cdot {{\mathit{M}}_I}^{\mathrm{T}}\right)为负对象粒矩阵，其中{\mathit{M}}^{+}\left(i,:\right)=\lambda \left(x_i^{\mathrm{*}\mathrm{*}}\right)，{\mathit{M}}^{-}\left(i,:\right)=\lambda \left(x_i^{\overline{\mathrm{*}}\overline{\mathrm{*}}}\right)，{{\mathit{M}}_I}^{\mathrm{T}}为{\mathit{M}}_I的转置。

对任意x\in U，有，由正对象粒矩阵和负对象粒矩阵可引入OE-对象粒矩阵。

定义4^［20］ 设\left(U,A,I\right)是形式背景。{\mathit{M}}_I是I的关系矩阵。令\mathit{M}={\mathit{M}}^{+}\wedge {\mathit{M}}^{-}，其中\mathit{M}\left(i,:\right)=，称\mathit{M}为OE-对象粒矩阵。对任意B\subseteq A，{\mathit{M}}_B={\mathit{M}}_B^{+}\wedge{\mathit{M}}_B^{-}为子形式背景\left(U,B,I_B\right)的OE-对象粒矩阵，其中

{\mathit{M}}_B^{+}=\sim \left(\left({\mathit{M}}_I\wedge {\mathit{R}}_B\right)\cdot \left(\sim {\left({\mathit{M}}_I\wedge {\mathit{R}}_B\right)}^{\mathrm{T}}\right)\right)，{\mathit{M}}_B^{-}=\sim \left(\sim \left({\mathit{M}}_I\wedge {\mathit{R}}_B\right)\right)\cdot {\left({\mathit{M}}_I\wedge {\mathit{R}}_B\right)}^{\mathrm{T}}，

{\mathit{R}}_B是任意一行均为\lambda \left(B\right)的\left|U\right|\times \left|A\right|阶矩阵。显然。

运用定义4可快速求出形式背景及其子背景的所有OE-对象粒概念的外延。

性质2 设\left(U,A,I\right)是形式背景。对任意B,C\subseteq A，x\in U，

（1）若C=A-B，， {\mathit{M}}_A={\mathit{M}}_B\wedge {\mathit{M}}_C；

（2）若C\subseteq B\subseteq A，， {\mathit{M}}_A\le{\mathit{M}}_B\le {\mathit{M}}_C。

证明 （1）对任意x\in U，B\subseteq A，由定义2可得，。由公式（1）、（2）可得x^{{\mathrm{*}}_A{\mathrm{*}}_A}=x^{{\mathrm{*}}_B{\mathrm{*}}_B}\bigcap x^{{\mathrm{*}}_C{\mathrm{*}}_C}，x^{{\overline{\mathrm{*}}}_A{\overline{\mathrm{*}}}_A}=x^{{\overline{\mathrm{*}}}_B{\overline{\mathrm{*}}}_B}\bigcap x^{{\overline{\mathrm{*}}}_C{\overline{\mathrm{*}}}_C}，故有。对任意x_i\in U，由定义4知 {\mathit{M}}_A\left(i,:\right)=，由x_i的任意性得{\mathit{M}}_A={\mathit{M}}_B\wedge {\mathit{M}}_C。

（2）由定义2知，对任意B\subseteq A，有x^{{\mathrm{*}}_B{\mathrm{*}}_B}\bigcap x^{{\overline{\mathrm{*}}}_B{\overline{\mathrm{*}}}_B}。当C\subseteq B\subseteq A时，由公式（1）得x^{{\mathrm{*}}_A{\mathrm{*}}_A}\subseteq x^{{\mathrm{*}}_B{\mathrm{*}}_B}\subseteq x^{{\mathrm{*}}_C{\mathrm{*}}_C}，x^{{\overline{\mathrm{*}}}_A{\overline{\mathrm{*}}}_A}\subseteq x^{{\overline{\mathrm{*}}}_B{\overline{\mathrm{*}}}_B}\subseteq x^{{\overline{\mathrm{*}}}_C{\overline{\mathrm{*}}}_C}。由此可得。故对任意x_i\in U，

{\mathit{M}}_A\left(i,:\right)\le {\mathit{M}}_B\left(i,:\right)\le{\mathit{M}}_C\left(i,:\right)。即{\mathit{M}}_A\le{\mathit{M}}_B\le {\mathit{M}}_C。

应用正、负算子提出的OE-概念格相较于经典概念格表达的信息更加丰富。针对数据爆炸式增长带来的庞大形式背景，利用矩阵能高效快速处理海量数据，和粗糙熵能用以衡量知识的不确定性的特点，结合OE-对象粒矩阵和粗糙熵提出OE-矩阵粗糙熵，研究基于OE-矩阵粗糙熵的OE-概念格的属性约简理论。通过定义OE-矩阵相似熵引入属性的重要性度量，研究OE-概念格的矩阵粗糙熵属性约简方法。

2 OE⁃概念格的OE⁃矩阵粗糙熵

文献［25］定义了一般二元关系下的粗糙熵。下面由OE-对象粒矩阵引入OE-概念格上的OE-矩阵粗糙熵。

定义5 设\left(U,A,I\right)是形式背景。对任意B\subseteq A，定义B的OE-矩阵粗糙熵为

E_{\mathrm{M}\mathrm{R}}\left(B\right)=-\frac{\mathrm{1}}{\left|\lambda \left(U\right)\right|}{\displaystyle \sum _{i=\mathrm{1}}^{\left|U\right|}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{1}}{\left|{\mathit{M}}_B\left(i,:\right)\right|}，

其中\left|{\mathit{M}}_B\left(i,:\right)\right|表示行向量{\mathit{M}}_B\left(i,:\right)中非零元的个数。

定理1 设\left(U,A,I\right)是形式背景。对任意B,C\subseteq A，

（1）C\subseteq B\Rightarrow E_{\mathrm{M}\mathrm{R}}\left(B\right)\le E_{\mathrm{M}\mathrm{R}}\left(C\right)；

（2）对任意x_i\in U，。

证明 （1）由C\subseteq B及性质2（2）可知，{\mathit{M}}_B\le {\mathit{M}}_C，故\forall x_i\in U，{\mathit{M}}_B\left(i,:\right)\le{\mathit{M}}_C\left(i,:\right)，由定义5得E_{\mathrm{M}\mathrm{R}}\left(B\right)\leE_{\mathrm{M}\mathrm{R}}\left(C\right)。

（2）若对任意x_i\in U，，则有{\mathit{M}}_B\left(i,:\right)={\mathit{M}}_C\left(i,:\right)\Rightarrow \left|{\mathit{M}}_B\left(i,:\right)\right|=\left|{\mathit{M}}_C\left(i,:\right)\right|。故由定义5得E_{\mathrm{M}\mathrm{R}}\left(B\right)=E_{\mathrm{M}\mathrm{R}}\left(C\right)。

定理1给出了OE-概念格上OE-矩阵粗糙熵的单调性，以及OE-矩阵粗糙熵与OE-对象粒之间的关系。\mathit{M}与{\mathit{M}}_B之间共有的零的基数可以反映属性集A与B所对应的OE-对象粒矩阵的相似性，由此给出两属性集合间OE-矩阵相似熵的定义。

定义6 设\left(U,A,I\right)是形式背景。对任意B\subseteq A，定义B关于A的OE-矩阵相似熵为

E_{\mathrm{M}\mathrm{S}}\left(B\left|A\right.\right)=-\frac{\mathrm{1}}{\left|\lambda \left(U\right)\right|}{\displaystyle \sum _{i=\mathrm{1}}^{\left|U\right|}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\left|\sim {\mathit{M}}_B\left(i,:\right)\wedge \sim {\mathit{M}}_A\left(i,:\right)\right|}{\left|\sim {\mathit{M}}_A\left(i,:\right)\right|}。

定理2 设\left(U,A,I\right)是形式背景。对任意C\subseteqB\subseteq A， 有

（1） E_{\mathrm{M}\mathrm{S}}\left(B\left|C\right.\right)=\mathrm{0};

（2） E_{\mathrm{M}\mathrm{S}}\left(B\left|A\right.\right)\le E_{\mathrm{M}\mathrm{S}}\left(C\left|A\right.\right)。

证明 （1）由C\subseteq B及性质2知{\mathit{M}}_B\le{\mathit{M}}_C，故对任意x_i\in U，{\mathit{M}}_B\left(i,:\right)\le {\mathit{M}}_C\left(i,:\right)，则\sim {\mathit{M}}_B\left(i,:\right)\ge \sim {\mathit{M}}_C\left(i,:\right)，\sim {\mathit{M}}_B\left(i,:\right)\wedge \sim {\mathit{M}}_C\left(i,:\right)=\sim {\mathit{M}}_C\left(i,:\right)。由定义6知

E_{\mathrm{M}\mathrm{S}}\left(B\left|C\right.\right)=-\frac{\mathrm{1}}{\left|\lambda \left(U\right)\right|}{\displaystyle \sum _{i=\mathrm{1}}^{\left|U\right|}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\left|\sim {\mathit{M}}_C\left(i,:\right)\right|}{\left|\sim {\mathit{M}}_C\left(i,:\right)\right|}=\mathrm{0}。

（2）由C\subseteq B及性质2知{\mathit{M}}_B\le{\mathit{M}}_C，故对任意x_i\in U，{\mathit{M}}_B\left(i,:\right)\le {\mathit{M}}_C\left(i,:\right)，则\sim {\mathit{M}}_B\left(i,:\right)\ge \sim {\mathit{M}}_C\left(i,:\right)， \sim {\mathit{M}}_B\left(i,:\right)\wedge \sim {\mathit{M}}_A\left(i,:\right)\ge \sim {\mathit{M}}_C\left(i,:\right)\wedge \sim {\mathit{M}}_A\left(i,:\right)， 由定义6得E_{\mathrm{M}\mathrm{S}}\left(B\left|A\right.\right)\le E_{\mathrm{M}\mathrm{S}}\left(C\left|A\right.\right)。

3 OE-概念格的矩阵粗糙熵约简

下面讨论形式背景上OE-概念格的矩阵粗糙熵约简方法。

定义7 设\left(U,A,I\right)是形式背景。对任意B\subseteq A，若E_{\mathrm{M}\mathrm{R}}\left(B\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)，称B为OE-概念格的矩阵粗糙熵协调集。若B为OE-概念格的矩阵粗糙熵协调集，且对任意a\in B，E_{\mathrm{M}\mathrm{R}}\left(B-\left\{a\right\}\right)\ne E_{\mathrm{M}\mathrm{R}}\left(A\right)，称B为OE-概念格的矩阵粗糙熵约简。

记\mathrm{R}\mathrm{e}\left(A\right)=｛B\subseteq A\left|\right.B为\left(U,A,I\right)中OE-概念格的矩阵粗糙熵约简｝。若a\in \bigcap \mathrm{R}\mathrm{e}\left(A\right)，称a为核心属性，记所有核心属性所构成的集合为Core\left(A\right)。

定理3 设\left(U,A,I\right)是形式背景。对任意a\in A，a\in Core\left(A\right)\iff E_{\mathrm{M}\mathrm{R}}\left(A-\left\{a\right\}\right)\ne E_{\mathrm{M}\mathrm{R}}\left(A\right)。

证明 设a\in Core\left(A\right)，则a\in \bigcap \mathrm{R}\mathrm{e}\left(A\right)。若E_{\mathrm{M}\mathrm{R}}\left(A-\left\{a\right\}\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)，则存在B\subseteq A-\left\{a\right\}，使E_{\mathrm{M}\mathrm{R}}\left(B\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)且对任意b\in B，E_{\mathrm{M}\mathrm{R}}\left(B-\left\{b\right\}\right)\ne E_{\mathrm{M}\mathrm{R}}\left(A\right)，这与a\in \bigcap \mathrm{R}\mathrm{e}\left(A\right)矛盾。故E_{\mathrm{M}\mathrm{R}}\left(A-\left\{a\right\}\right)\ne E_{\mathrm{M}\mathrm{R}}\left(A\right)。

设E_{\mathrm{M}\mathrm{R}}\left(A-\left\{a\right\}\right)\ne E_{\mathrm{M}\mathrm{R}}\left(A\right)。若存在B\in\mathrm{R}\mathrm{e}\left(A\right)且a\notin B，则E_{\mathrm{M}\mathrm{R}}\left(B\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)。 由B\subseteqA-\left\{a\right\}\subseteq A及定理1得E_{\mathrm{M}\mathrm{R}}\left(A-\left\{a\right\}\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)，矛盾。故a\inCore\left(A\right)。

推论1 设\left(U,A,I\right)是形式背景。对任意a\in A，a\notin Core\left(A\right)\iff E_{\mathrm{M}\mathrm{R}}\left(A-\left\{a\right\}\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)。

定理4 设\left(U,A,I\right)是形式背景。D\subseteq A，E=A-D，{\mathit{M}}_D和{\mathit{M}}_E分别为子形式背景\left(U,D,I_D\right)和\left(U,E,I_E\right)的OE-对象粒矩阵。若{\mathit{M}}_D\le {\mathit{M}}_E，则D为OE-概念格的矩阵粗糙熵协调集。

证明 由E\bigcup D=A及性质2（1）可知{\mathit{M}}_D\wedge {\mathit{M}}_E={\mathit{M}}_A，故由{\mathit{M}}_D\le {\mathit{M}}_E可得{\mathit{M}}_A={\mathit{M}}_D。于是E_{\mathrm{M}\mathrm{R}}\left(D\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)，即D为OE-概念格的矩阵粗糙熵协调集。

定理5 设\left(U,A,I\right)是形式背景。D\subseteq A，D为OE-概念格的矩阵粗糙熵协调集当且仅当E_{\mathrm{M}\mathrm{S}}\left(D\left|A\right.\right)=\mathrm{0}。

证明 若D为OE-概念格的矩阵粗糙熵协调集，由定义7及定理1知，对任意x_i\in U，有{\mathit{M}}_D\left(i,:\right)={\mathit{M}}_A\left(i,:\right)\Rightarrow \sim {\mathit{M}}_D\left(i,:\right)=\sim {\mathit{M}}_A\left(i,:\right)，则(\sim {\mathit{M}}_D\left(i,:\right))\wedge (\sim {\mathit{M}}_A\left(i,:\right))=\sim {\mathit{M}}_A\left(i,:\right)，故E_{\mathrm{M}\mathrm{S}}\left(D\left|A\right.\right)=\mathrm{0}。

由E_{\mathrm{M}\mathrm{S}}\left(D\left|A\right.\right)=\mathrm{0}可得，对任意x_i\inU，有(\sim {\mathit{M}}_D\left(i,:\right))\wedge (\sim {\mathit{M}}_A\left(i,:\right))=\sim {\mathit{M}}_A\left(i,:\right)，则\sim {\mathit{M}}_D\left(i,:\right)\ge \sim {\mathit{M}}_A\left(i,:\right)，即{\mathit{M}}_D\le {\mathit{M}}_A，由D\subseteq A及性质2得{\mathit{M}}_D\ge {\mathit{M}}_A，故{\mathit{M}}_D={\mathit{M}}_A。由定理1和定义7得D为OE-概念格的矩阵粗糙熵协调集。

文献［29］给出了OE-概念格的熵协调集和熵约简。设\left(U,A,I\right)是形式背景，对任意B\subseteq A，OE-概念格上B的信息熵定义为H\left(B\right)=，\left|\cdot \right|表示集合的基数。若H\left(B\right)=H\left(A\right)，称B为OE-概念格的熵协调集。若H\left(B\right)=H\left(A\right)且对任意C\subseteq B有H\left(C\right)\ne H\left(A\right)，则称B为OE-概念格的熵约简集。

定理6 设\left(U,A,I\right)是形式背景。对任意B\subseteq A，

（1）B为OE-概念格的矩阵粗糙熵协调集当且仅当B为OE-概念格的熵协调集；

（2）B为OE-概念格的矩阵粗糙熵约简当且仅当B为OE-概念格的熵约简。

证明 （1）设B为OE-概念格的矩阵粗糙熵协调集，则E_{\mathrm{M}\mathrm{R}}\left(B\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)，故对任意x_i\in U，有，故B为OE-概念格的熵协调集。

（2）设B为OE-概念格的矩阵粗糙熵约简，则E_{\mathrm{M}\mathrm{R}}\left(B\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)且对任意b\in B，E_{\mathrm{M}\mathrm{R}}\left(A\right)\neE_{\mathrm{M}\mathrm{R}}\left(B-\left\{b\right\}\right)。由（1）知H\left(B\right)=H\left(A\right)。若存在b_{\mathrm{0}}\in B，使得H\left(B-\left\{b_{\mathrm{0}}\right\}\right)=H\left(A\right)，则E_{\mathrm{M}\mathrm{R}}\left(A\right)=E_{\mathrm{M}\mathrm{R}}\left(B-\left\{b_{\mathrm{0}}\right\}\right)，故B-\left\{b_{\mathrm{0}}\right\}为OE-概念格的矩阵粗糙熵协调集，与B为OE-概念格的矩阵粗糙熵约简矛盾。故B为OE-概念格的熵约简。

若B为OE-概念格的熵约简集，由（1）知B为OE-概念格的矩阵粗糙熵协调集。若存在b_{\mathrm{0}}\in B，使得E_{\mathrm{M}\mathrm{R}}\left(B-\left\{b_{\mathrm{0}}\right\}\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)，可得对任意x\in U，，则H\left(B-\left\{b_{\mathrm{0}}\right\}\right)=H\left(A\right)，与B为OE-概念格的熵约简集矛盾。故B为OE-概念格的矩阵粗糙熵约简集。

定理6说明OE-概念格的矩阵粗糙熵约简与熵约简等价。

定义7 设\left(U,A,I\right)是形式背景。对任意B\subseteq A，a\in B，a关于B的内重要度定义为：

S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,B\right)=E_{\mathrm{M}\mathrm{S}}\left(B-\left\{a\right\}\left|A\right.\right)-E_{\mathrm{M}\mathrm{S}}\left(B\left|A\right.\right)

对任意B\subseteq A，a\in A-B，a关于B的外重要度：

S^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{r}}\left(a,B\right)=E_{\mathrm{M}\mathrm{S}}\left(B\left|A\right.\right)-E_{\mathrm{M}\mathrm{S}}\left(B\bigcup \left\{a\right\}\left|A\right.\right)。

由定义7知，a关于B的内重要度是将a从B中删除时的一致性损失，a关于B的外重要度是将a添加至B中的一致性提高程度。由属性重要度可给出核心属性的判定定理。

定理7 设\left(U,A,I\right)是形式背景。对任意a\in A，a\in Core\left(A\right)\iff S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,A\right)>\mathrm{0}。

证明 S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,A\right)=E_{\mathrm{M}\mathrm{S}}\left(A-\left\{a\right\}\left|A\right.\right)-E_{\mathrm{M}\mathrm{S}}\left(A\left|A\right.\right)=E_{\mathrm{M}\mathrm{S}}\left(A-\left\{a\right\}\left|A\right.\right)，由于a\in Core\left(A\right)，则A-\left\{a\right\}不是矩阵粗糙熵协调集，由定理5知E_{\mathrm{M}\mathrm{S}}\left(A-\left\{a\right\}\left|A\right.\right)>\mathrm{0}，故S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,A\right)>\mathrm{0}。

设a\notin Core\left(A\right)，则至少存在一个矩阵粗糙熵协调集B\subseteq A-\left\{a\right\}。由定理2知E_{\mathrm{M}\mathrm{S}}\left(B\left|A\right.\right)\geE_{\mathrm{M}\mathrm{S}}\left(A-\left\{a\right\}\left|A\right.\right)，由于S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,A\right)=E_{\mathrm{M}\mathrm{S}}\left(A-\left\{a\right\}\left|A\right.\right)>\mathrm{0}，则E_{\mathrm{M}\mathrm{S}}\left(B\left|A\right.\right)>\mathrm{0}，与B为矩阵粗糙熵协调集矛盾，故a\in Core\left(A\right)。

定理7说明，核心属性关于A的内重要度均大于零，即Core\left(A\right)=\left\{a\in A\left|S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,A\right)>\mathrm{0}\right.\right\}。

推论2 设\left(U,A,I\right)是形式背景。对任意a\in A，a\notin Core\left(A\right)\iff S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,A\right)=\mathrm{0}。

定理8 设\left(U,A,I\right)是形式背景。B\subseteq A，B是OE-概念格的矩阵粗糙熵约简集当且仅当E_{\mathrm{M}\mathrm{S}}\left(B\left|A\right.\right)=\mathrm{0}且对任意a\in B，有S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,B\right)>\mathrm{0}。

证明 由定理5及定理7可得。

由定理7和定理8可给出OE-概念格的矩阵粗糙熵约简算法：先求出每个属性的内重要度，得到核心属性集，进而判断核心属性集是否为矩阵粗糙熵约简，若不是，则通过计算外重要度给核心属性集中添加外重要度最大的属性，直到得到OE-概念格的矩阵粗糙熵协调集，从粗糙熵协调集中删除冗余属性得到约简。由此给出OE-概念格的矩阵粗糙熵约简算法（Algorithm of Attribute Reduction Based on Matrix-rough Entropy，ARMRE算法）：

ARMRE算法 OE-概念格的矩阵粗糙熵约简算法

输入： 形式背景\left(U,A,I\right)

输出： 矩阵粗糙熵约简P

Let Core\left(A\right)=\mathrm{\varnothing }， P=\mathrm{\varnothing }

For a_i\left(i=\mathrm{1,2},\cdots ,m\right) in A

If S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a_i,A\right)>\mathrm{0}

Let Core\left(A\right)=Core\left(A\right)\bigcup \left\{a_i\right\}

Break

End If

End For

Do //如果P不是约简集，则循环

Let P=Core\left(A\right)，Q=A-P，Get E_{\mathrm{M}\mathrm{R}}\left(P\right)，Get E_{\mathrm{M}\mathrm{R}}\left(A\right)

For b in Q

If S^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{r}}\left(b,P\right)=\underset{c\in Q}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{S^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{r}}\left(c,P\right)\right\}

Let P=P\bigcup \left\{b\right\}

End If

End For

While E_{\mathrm{M}\mathrm{R}}\left(P\right)\ne E_{\mathrm{M}\mathrm{R}}\left(A\right)

For a_i in P //删除P中的冗余属性

If S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a_i,P\right)=\mathrm{0}

Let P=P-\left\{a_i\right\}

End If

End For

Print（P） //输出约简集P

在算法中，最多计算\left|A\right|次属性重要度，因此找出核心属性的时间复杂度为O\left({\left|U\right|}^{\mathrm{2}}{\left|A\right|}^{\mathrm{2}}\right)。计算OE-矩阵粗糙熵的时间复杂度为O\left({\left|U\right|}^{\mathrm{2}}\left|A\right|\right)。判断是否为OE-矩阵粗糙熵约简的时间复杂度为O\left({\mathrm{2}}^{\left|A\right|}\right)。删除冗余属性的时间复杂度为O\left({\left|U\right|}^{\mathrm{2}}{\left|A\right|}^{\mathrm{2}}\right)。因此该算法的综合时间复杂度为O\left({\left|U\right|}^{\mathrm{2}}{\left|A\right|}^{\mathrm{2}}+{\mathrm{2}}^{\left|A\right|}\right)。

例1表1给出形式背景\left(U,A,I\right)，其中U=\left\{x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},x_{\mathrm{4}},x_{\mathrm{5}}\right\}，A=\left\{a,b,c,d,e\right\}。

由表1及定义4可求得

{\mathit{M}}_I=\left[\begin{array}{ccccc}\mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{1}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}\end{array}\right]，{\mathit{M}}_A=\left[\begin{array}{ccccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right]，{\mathit{M}}_{A-\left\{a\right\}}=\left[\begin{array}{ccccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right]，

计算得S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,A\right)=E_{\mathrm{M}\mathrm{S}}\left(A-\left\{a\right\}\left|A\right.\right)=\mathrm{0}。同理S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(b,A\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{9}}{\mathrm{16}}，S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(c,A\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{81}}{\mathrm{256}}， S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(d,A\right)=\mathrm{0}，S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(e,A\right)=\mathrm{0}。由定理6可得，b,c为核心属性，a,d,e为非核心属性。

令B=\left\{b,c\right\}，验证B是否为OE-概念格的矩阵粗糙熵约简。由\lambda \left(B\right)=(\mathrm{0,1},\mathrm{1,0},\mathrm{0})，{\mathit{R}}_B=\left[\begin{array}{ccccc}\mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\end{array}\right]，{\mathit{M}}_B=\left[\begin{array}{ccccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right]，求得E_{\mathrm{M}\mathrm{R}}\left(B\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{1}}{\mathrm{4}}\ne E_{\mathrm{M}\mathrm{R}}\left(A\right)，故B不是OE-概念格的矩阵粗糙熵约简。计算a,d,e的外重要度：S^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{r}}\left(a,B\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{9}}{\mathrm{16}}，S^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{r}}\left(d,B\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{9}}{\mathrm{16}}，S^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{e}\mathrm{r}}\left(e,B\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{9}}{\mathrm{16}}。

由于属性a,d,e的外重要度相等，任取一属性添加至B中，如C=\left\{a,b,c\right\}，由\lambda \left(C\right)=(\mathrm{1,1},\mathrm{1,0},\mathrm{0})，{\mathit{R}}_C=\left[\begin{array}{ccccc}\mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{1}& \mathrm{1}& \mathrm{1}& \mathrm{0}& \mathrm{0}\end{array}\right]，{\mathit{M}}_C=\left[\begin{array}{ccccc}\mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{0}& \mathrm{1}\end{array}\right]，算得E_{\mathrm{M}\mathrm{R}}\left(C\right)=E_{\mathrm{M}\mathrm{R}}\left(A\right)，且S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(a,C\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{9}}{\mathrm{16}}，S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(b,C\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{9}}{\mathrm{16}}，S^{\mathrm{i}\mathrm{n}\mathrm{n}\mathrm{e}\mathrm{r}}\left(c,C\right)=-\frac{\mathrm{1}}{\mathrm{5}}\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\frac{\mathrm{9}}{\mathrm{16}}。故C=\left\{a,b,c\right\}为OE-概念格的矩阵粗糙熵约简。同理可求得\left\{b,c,d\right\}、\left\{b,c,e\right\}也是OE-概念格的矩阵粗糙熵约简。

4 实验分析

为验证形式背景上OE-概念格的矩阵粗糙熵约简的有效性，从UCI公开数据集中选取了10组数据构造形式背景。该10组数据的选取从对象数量增大及属性数量增大的角度进行了考虑，为了验证在大数据量下本文方法的约简效率，选取的数据集中分别包含了对象数量较大或属性数量较大的数据集。其中，离散型数据集为Lung Cancer、Car、Chord Finger和SCADI，连续型数据集为Chemical Composion、Cloud、Gait Classfication和Urban Land，其余为包含离散型数据和连续型数据的混合型数据集，如表2所示。

将选取的UCI数据集中的原始数据转化为形式背景：设\left(U,A,F\right)为信息系统，信息函数f:U\times A\to V，任意属性a\in A的均值和标准差记为\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}\left(a\right)和\mathrm{s}\mathrm{t}\mathrm{d}\left(a\right)。对任意x\in U，定义二元关系I\subseteq U\times A:，则信息系统\left(U,A,F\right)对应转化为形式背景\left(U,A,I\right)。

将表2中的UCI数据集转化为形式背景后进行属性约简实验，得到本文所提算法在各数据集下的约简时间，并与文献［29］中的算法进行约简时间的对比，最后通过绘制约简时间对比图，直观形象的总结出本文所提方法在约简时间上的优势。文献［29］受三支概念格粒约简的启发，基于OE-对象粒提出了基于信息熵的OE-概念格属性约简方法。本文结合OE-对象粒矩阵和粗糙熵提出了基于矩阵粗糙熵的OE-概念格属性约简方法，并用内重要度得到核心属性集，以外重要度对核心属性集增添属性来得到协调集，进而得到约简集的思想设计了算法。将文献［29］中的算法记为AROG（Algorithm of Attribute Reduction Based on Object-induced Granular）算法，用Matlab计算两种方法在以上十组数据集的约简时间，为了排除算法耗时随机性的影响，每个算法重复20次，然后计算其耗时平均值，对比两种算法的约简时间（表3）。

由表3实验结果可知，本文所提方法的约简时间更短，因此在处理样本量较大的数据集时，本文所提方法时间成本更低。图1为两算法在表2所示10个数据集上的约简时间对比图。

由图1可直观明显的看出本文所提方法的时间运行效率更高，在处理数据量越大的数据集时，特别是属性数量越大时，时间优势越明显。

5 结论

本文将粗糙熵引入OE-概念格中，结合OE-对象粒矩阵提出基于矩阵粗糙熵的OE-概念格的属性约简方法。首先提出OE-概念格的OE-矩阵粗糙熵的定义，利用OE-对象粒矩阵的相似性定义了OE-矩阵相似熵，讨论了它们的性质；引入了形式背景上OE-概念格的矩阵粗糙熵协调集和矩阵粗糙熵约简集，给出矩阵粗糙熵协调集的判定定理；基于OE-矩阵相似熵给出属性的重要性度量，进而给出获取OE-概念格矩阵粗糙熵约简的算法。并通过对比实验得出本文所提方法时间成本更短，更适用于大样本数据。本文所提方法只在形式背景上进行了讨论，未考虑属性权重对约简的影响，且对三支概念格中属性导出三支概念格的属性约简未作研究。下一步可研究加权矩阵粗糙熵的属性约简方法，同时在本文研究基础上探讨属性导出三支概念格的约简方法，和不完备形式背景或决策形式背景的三支概念格属性约简问题。

参考文献

[1] WILLE R. Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts[C]//RIVAL I. Ordered Sets. Dordrecht: Springer, 1982: 445-470. DOI: 10.1007/978-94-009-7798-3_15 .

[2] 胡小康. 基于模糊关系的形式概念分析方法研究[D]. 太原: 山西大学, 2017.

[3] HU X K. Research on Formal Concept Analysis Method Based on Fuzzy Relation[D]. Taiyuan: Shanxi University, 2017.

[4] ZOU C F, DENG H F, WAN J F, et al. Mining and Updating Association Rules Based on Fuzzy Concept Lattice[J]. Future Gener Comput Syst, 2018, 82: 698-706. DOI: 10.1016/j.future.2017.11.018 .

[5] HAO F, YANG Y X, MIN G Y, et al. Incremental Construction of Three-way Concept Lattice for Knowledge Discovery in Social Networks[J]. Inf Sci, 2021, 578: 257-280. DOI: 10.1016/j.ins.2021.07.031 .

[6] ZOU L, LIN H M, SONG X Y, et al. Rule Extraction Based on Linguistic-valued Intuitionistic Fuzzy Layered Concept Lattice[J]. Int J Approx Reason, 2021, 133: 1-16. DOI: 10.1016/j.ijar.2020.12.018 .

[7] QIN K Y, LIN H, JIANG Y T. Local Attribute Reductions of Formal Contexts[J]. Int J Mach Learn Cybern, 2020, 11(1): 81-93. DOI: 10.1007/s13042-019-00956-z .

[8] 张文修, 魏玲, 祁建军. 概念格的属性约简理论与方法[J]. 中国科学E辑: 信息科学, 2005, 35(6): 628-639. DOI: 10.1360/112004-104 .

[9] ZHANG W X, WEI L, QI J J. Theory and Method of Attribute Reduction of Concept Lattice[J]. Sci China Ser E, 2005, 35(6): 628-639. DOI: 10.1360/112004-104 .

[10] QI J J. Attribute Reduction in Formal Contexts Based Onanewdiscernibility Matrix[J]. J Appl Math Comput, 2009, 30(1): 305-314. DOI: 10.1007/s12190-008-0174-9 .

[11] 岳晓威, 彭莎, 秦克云. 基于面向对象(属性)概念格的形式背景属性约简方法[J]. 计算机科学, 2020, 47(1): 436-439. DOI: 10.11896/jsjkx.191100011 .

[12] YUE X W, PENG S, QIN K Y. Attribute Reduction Method of Formal Background Based on Object-oriented Concept Lattice[J]. Comput Sci, 2020, 47(1): 436-439. DOI: 10.11896/jsjkx.191100011 .

[13] 万青, 马盈仓, 李金海. 基于直观图的三支概念获取及属性特征分析[J]. 计算机科学与探索, 2022, 16(12): 2879-2889. DOI: 10.3778/j.issn.1673-9418.2104120 .

[14] WAN Q, MA Y C, LI J H. Three-way Concept Acquisition and Attribute Characteristic Analysis Based on Pictorial Diagrams[J]. J Front Comput Sci Technol, 2022, 16(12): 2879-2889. DOI: 10.3778/j.issn.1673-9418.2104120 .

[15] 万仁霞, 李梅, 苗夺谦. 净化属性对偶背景下完全格的形式概念分析[J]. 山西大学学报(自然科学版), 2022, 45(1): 77-86. DOI: 10.13451/j.sxu.ns.2021063 .

[16] WAN R X, LI M, MIAO D Q. Characterization of Formal Concept Analysis for Complete Lattice in the Clarified Attribute Dual Context[J]. J Shanxi Univ Nat Sci Ed, 2022, 45(1): 77-86. DOI: 10.13451/j.sxu.ns.2021063 .

[17] CORNEJO M E, MEDINA J, RAMÍREZ-POUSSA E. On the Use of Irreducible Elements for Reducing Multi-adjoint Concept Lattices[J]. Knowl Based Syst, 2015, 89: 192-202. DOI: 10.1016/j.knosys.2015.07.003 .

[18] WANG Z, QI J J, SHI C J, et al. Multiview Granular Data Analytics Based on Three-way Concept Analysis[J]. Appl Intell, 2023, 53(11): 14645-14667. DOI: 10.1007/s10489-022-04145-4 .

[19] NIU J J, CHEN D G. Incremental Calculation Approaches for Granular Reduct in Formal Context with Attribute Updating[J]. Int J Mach Learn Cybern, 2022, 13(9): 2763-2784. DOI: 10.1007/s13042-022-01561-3 .

[20] WANG Z, SHI C J, WEI L, et al. Tri-granularity Attribute Reduction of Three-way Concept Lattices[J]. Knowl Based Syst, 2023, 276: 110762. DOI: 10.1016/j.knosys.2023.110762 .

[21] QI J J, WEI L, YAO Y Y. Three-way Formal Concept Analysis[C]//International Conference on Rough Sets and Knowledge Technology. Cham: Springer, 2014: DOI: 732-741.10.1007/978-3-319-11740-9_67 .

[22] YAO Y Y. An Outline of a Theory of Three-way Decisions[C]. Berlin Heidelberg: Springer, 2012: 1-17. DOI: 10.1007/978-3-642-32115-3_1 .

[23] REN R S, WEI L. The Attribute Reductions of Three-way Concept Lattices[J]. Knowl Based Syst, 2016, 99: 92-102. DOI: 10.1016/j.knosys.2016.01.045 .

[24] 常欣欣, 秦克云. 基于对象导出三支概念格的形式背景粒约简方法[J]. 计算机科学, 2018, 45(10): 225-228. DOI: 10.11896/j.issn.1002-137X.2018.10.041 .

[25] CHANG X X, QIN K Y.Approach for Granular Reduction in Formal Context Based on Objects-induced Three-way Concept Lattices[J]. Comput Sci, 2018, 45(10): 225-228. DOI: 10.11896/j.issn.1002-137X.2018.10.041 .

[26] 张呈玲, 李进金, 林艺东. 基于OE-概念格的形式背景属性约简[J]. 计算机工程与应用, 2021, 57(15): 82-89. DOI: 10.3778/j.issn.1002-8331.2006-0325 .

[27] ZHANG C L, LI J J, LIN Y D. Attribute Reduction in Formal Contexts Based on OE-concept Lattices[J]. Comput Eng Appl, 2021, 57(15): 82-89. DOI: 10.3778/j.issn.1002-8331.2006-0325 .

[28] SHANNON C E. A Mathematical Theory of Communication[J]. Bell Syst Tech J, 1948, 27(3): 379-423. DOI: 10.1002/j.1538-7305.1948.tb01338.x .

[29] LI J L, HE Z Y, ZHU Q L. An Entropy-based Weighted Concept Lattice for Merging Multi-source Geo-ontologies[J]. Entropy, 2013, 15(12): 2303-2318. DOI: 10.3390/e15062303 .

[30] SINGH P K, CHERUKURI A K, LI J H. Concepts Reduction in Formal Concept Analysis with Fuzzy Setting Using Shannon Entropy[J]. Int J Mach Learn Cybern, 2017, 8(1): 179-189. DOI: 10.1007/s13042-014-0313-6 .

[31] LIANG J Y, XU Z B. The Algorithm on Knowledge Reduction in Incomplete Information Systems[J]. Int J Unc Fuzz Knowl Based Syst, 2002, 10(1): 95-103. DOI: 10.1142/s021848850200134x .

[32] 黄兵, 周献中, 史迎春. 基于一般二元关系的知识粗糙熵与粗集粗糙熵[J]. 系统工程理论与实践, 2004, 24(1): 93-96. DOI: 10.3321/j.issn: 1000-6788.2004.01.016 .

[33] HUANG B, ZHOU X Z, SHI Y C. Entropy of Knowledge and Rough Set Based on General Binary Relation[J]. Syst Eng Theory Pract, 2004, 24(1): 93-96. DOI: 10.3321/j.issn: 1000-6788.2004.01.016 .

[34] 李美争, 李磊军, 米据生, 概念格中基于粗糙熵的属性约简方法[J]. 计算机科学, 2018, 45(1): 84-89. DOI: 10.11896/j.issn.1002-137X.2018.01.013 .

[35] LI M Z, LI L J, MI J S, et al. Rough Entropy Based Algorithm for Attribute Reduction in Concept Lattice[J]. Comput Sci, 2018, 45(1): 84-89. DOI: 10.11896/j.issn.1002-137X.2018.01.013 .

[36] 陈东晓, 李进金, 林荣德, 基于信息熵的形式背景属性约简[J]. 模式识别与人工智能, 2020, 33(9): 786-798. DOI: 10.16451/j.cnki.issn1003-6059.202009003 .

[37] CHEN D X, LI J J, LIN R D, et al. Attribute Reductions of Formal Context Based on Information Entropy[J]. Pattern Recognit Artif Intell, 2020, 33(9): 786-798. DOI: 10.16451/j.cnki.issn1003-6059.202009003 .

[38] 贺青青, 马建敏, 丁娜. 形式背景上基于矩阵信息熵的矩阵熵约简[J]. 南京大学学报(自然科学), 2023, 59(1): 98-106. DOI: 10.13232/j.cnki.jnju.2023.01.010 .

[39] HE Q Q, MA J M, DING N. Matrix Information Entropy Based Matrix Entropy Reduction in Formal Contexts[J]. J Nanjing Univ Nat Sci, 2023, 59(1): 98-106. DOI: 10.13232/j.cnki.jnju.2023.01.010 .

[40] 吴荣, 张文娟, 李进金. 对象导出三支概念格的熵属性约简[J]. 华侨大学学报(自然科学版), 2021, 42(5): 693-700. DOI: 10.11830/ISSN.1000-5013.202106031 .

[41] WU R, ZHANG W J, LI J J. Entropy Attribute Reduction of Object-induced Three-way Concept Lattice[J]. J Huaqiao Univ Nat Sci, 2021, 42(5): 693-700. DOI: 10.11830/ISSN.1000-5013.202106031 .

[42] GANTER B, WILLE R. Formal concept analysis: mathematical foundations[M]. Berlin Heidelberg: Springer, 1999.

[43] 张清新. 基于布尔矩阵的概念格属性约简方法[D]. 漳州:漳州师范学院, 2012.

[44] ZHANG Q X. Attribute Reduction Method for Concept Lattices Based on Boolean Matrices[D]. Zhangzhou: Zhangzhou Normal University, 2012.

基金资助

国家自然科学基金(61772019)

科技部国家重点研发计划项目(2022YFC3303100)

陕西省自然科学基金(2021JQ-2B)