决策形式背景基于OE-协调性的属性约简

常丽娜 魏玲 彭超林

摘要 属性约简作为形式概念分析中非常重要的一个研究分支，在三支概念分析中也同样重要。基于对象导出三支概念格，提出了保持决策形式背景OE-协调性的属性约简理论，丰富了三支概念分析的约简理论。首先，定义了决策形式背景的OE-协调集和OE-约简，并将属性按其特征分为3类。其次，指出OE-约简的本质就是极小OE-协调集，给出了OE-协调集的几个判定定理，通过研究OE-协调集的充要条件，获取OE-约简的判定定理。最后，给出OE-差别矩阵和OE-差别函数的定义，并给出了利用OE-差别矩阵和OE-差别函数计算OE-约简的方法。

关键词 三支概念分析;属性约简;OE-协调性;决策形式背景;对象导出三支概念格

Attribute reduction in formal decision contextsbased on OE-consistency

Abstract Attribute reduction， as a very important branch of formal concept analysis， is equally important in the three-way concept analysis. Based on object-induced concept lattices， attribute reduction theory which preserve OE-consistency of formal decision contexts is proposed， which enriches the reduction theory of three-way concept analysis. Firstly， OE-consistent set and OE-reduct of formal decision contexts are defined， and the attributes are classified into three categories according to their characteristics. Then， it is pointed out the essence of OE-reduct is minimal OE-consistent set， and several judgement theorems of OE-consistent set are given. By studying the necessary and sufficient conditions of OE-consistent set， judgement theorem of OE-reduct is obtained. Finally， the definition of OE-discernibility matrix and OE-discernibility function are given， and the method of calculating OE-reduct by using OE-discernibility matrix and OE-discernibility function is given.

Keywords three-way concept analysis; attribute reduction; OE-consistency; formal decision contexts; object-induced three-way concept lattices

形式概念分析［1-2］（formal concept analysis， FCA）作為数据分析与知识发现的有力工具， 是由德国数学家Wille于1982年提出的， 并被广泛应用于机器学习、冲突分析等很多领域［3］。

在经典形式概念分析的基础上， Qi等结合三支决策理论［4］（three-way decision， 3WD）于2014年提出了三支概念分析［5-6］（three-way concept analysis， 3WCA）， 既体现了三支决策的思想和应用价值， 也是经典形式概念分析的一种扩展， 能同时反映“共同具有”和“共同不具有”两种信息。目前， 三支概念分析已经得到了很多学者的关注和认可， 研究成果也越来越丰富。Ren等研究了两类三支概念格的4种属性约简问题， 并讨论了它们之间的关系［7］。Yu等通过考虑三支概念格（三支粗概念格）的原子、不可约元和补的性质， 研究了三支概念格（三支粗概念格）的性质，在具有这些特殊性质的完备格与三支概念格（三支粗概念格）之间建立了一个同构映射［8］。Zhi等提出了三支对偶概念格， 探讨了三支对偶概念格与经典对偶概念格的关系， 研究了三支概念格、三支对偶概念格、三支面向对象概念格和三支面向属性概念格4种类型的三支概念分析模型之间的关系［9］。Yang等引入一对组合算子， 提出了一种构造属性诱导三支概念格和对象诱导三支概念格的新方法［10］。Zhao等对三支算子的性质重新表述，研究了不同类型的三支概念格之间的关系［11］。

决策形式背景［12］这一概念是由魏玲提出的， 随之决策形式背景的知识发现成为FCA的研究热点。决策形式背景只有在满足一定的协调意义下， 对其的知识发现才更具合理性。Wei等定义了决策形式背景的强、弱协调性， 并在此基础上研究了两种协调意义下的属性约简［13］。Li等对决策形式背景的属性约简与规则获取进行了较为系统深入的研究［14-15］。Chen等研究了大规模决策形式背景的属性约简问题，提出了一种计算决策形式背景差别矩阵简单有效的方法［16］。作为形式概念分析的扩展， 决策形式背景的知识发现在三支概念分析中同样重要。陈雪等基于AE-概念格， 研究了决策形式背景的保持非冗余规则信息不变的属性约简问题［17］。林洪等研究了三支粒协调决策形式背景的粒约简问题［18］。刘琳等基于AE-概念格研究了决策背景的规则提取问题［19-20］。Wei等基于两类三支概念格定义了决策形式背景的OE-协调性和AE-协调性， 研究了三支规则提取问题［21］。Long等基于三支概念格研究了不完备决策背景的规则获取问题［22］。

决策形式背景在满足一定的协调意义下，其知识发现才更具合理性和可解释性，因此，研究决策形式背景不同的协调性，可以挖掘出一个决策背景更多的信息与细节。本文根据文献［20］提出的决策形式背景的OE-协调性的定义， 基于对象导出三支概念格，研究决策形式背景保持OE-协调性的属性约简理论， 并通过实例表明协调集判定定理及约简计算方法的有效性。

1 预备知识

1.1 形式概念分析

将形式背景（G，M，I）的概念的全体记为L（G，M，I），对于任意的（X1，A1），（X2，A2）∈L（G，M，I）， 它们的偏序关系为

进一步， 定义任意两个概念的下确界和上确界为

则L（G，M，I）形成一个完备格，称为概念格。

1.2 三支概念分析

下面给出三支算子的概念。

记形式背景（G，M，I）的所有OE-概念构成的集合为OEL（G，M，I），所有OE-概念外延构成的集合为OELE（G，M，I）。对于任意的（X1，（A1，B1）），（X2，（A2，B2））∈OEL（G，M，I）， 定义它们的偏序关系为

如果（X1，（A1，B1））≤（X2，（A2，B2））且（X1，（A1，B1））≠（X2，（A2，B2））， 则记为（X1，（A1，B1））<（X2，（A2，B2））。如果（X1，（A1，B1））<（X2，（A2，B2））， 且不存在OE-概念（X，（A，B））使得（X1，（A1，B1））<（X，（A，B））<（X2，（A2，B2））成立， 则称（X1，（A1，B1））是（X2，（A2，B2））的子概念， （X2，（A2，B2））是（X1，（A1，B1））的父概念， 記作（X1，（A1，B1））（X2，（A2，B2））。其中，任意两个OE-概念的下确界和上确界为

则OEL（G，M，I）是一个完备格，称为对象导出三支概念格，简记为OE-概念格。

2 决策形式背景的属性约简

2.1 OE-协调性与属性约简的相关定义

本节首先介绍决策形式背景OE-协调性的定义， 然后给出保持决策形式背景OE-协调性的协调集和约简的定义。

定义4［20］  如果（G，M，I）和（G，N，J）是形式背景， M∩N=， 则称五元组（G，M，I，N，J）为一个决策形式背景， 其中M称为条件属性集， N称为决策属性集。背景（G，M，I）的对象导出三支概念格记为OEL（G，M，I）， 背景（G，N，J）的对象导出三支概念格记为OEL（G，N，J）。如果对于任意（Y，（E，F））∈OEL（G，N，J）， 总存在（X，（A，B））∈OEL（G，M，I）， 使得X=Y，则称OEL（G，M，I）细于OEL（G，N，J）， 记作OEL（G，M，I）≤OEL（G，N，J）， 且称决策形式背景（G，M，I，N，J）是对象导出三支协调的， 简称为OE-协调的。

定义6 设OE-协调的决策形式背景（G，M，I，N，J）的所有OE-约简为｛Di|Di是约简，i∈τ｝（τ为一个指标集）， 则条件属性集M中的属性可分为以下3类：

定理1 设决策形式背景（G，M，I，N，J）是OE-协调的， 则其OE-约简一定存在。

证明 因为（G，M，I，N，J）是OE-协调的， 故M是OE-协调集， 若m∈M， 都有（G，M-｛m｝，IM-m，N，J）不是OE-协调的， 则M就是OE-约简。若m∈M， 使得（G，M-｛m｝，IM-m，N，J）是OE-协调的， 令M1=M-｛m｝， 则M1是OE-协调集， 若m1∈M1， 都有（G，M1-｛m1｝，IM1-m1，N，J）不是OE-协调的， 则M1是OE-约简;否则， 再进一步研究M1-｛m1｝。重复上述过程， 由于M是有限集， 所以至少可以找到决策形式背景（G，M，I，N，J）的一个OE-约简， 故OE-约简必存在。

例1 表1给出了一个决策形式背景（G，M，I，N，J）。其中对象集G=｛1，2，3，4｝， 条件属性集为M=｛a，b，c，d，e，f｝， 决策属性集为N=｛g，h，i｝。

背景（G，M，I）共有13个对象导出三支概念， 分别标为TCi（i=1，2，…，13）， 其对象导出三支概念格OEL（G，M，I）如图1所示;背景（G，N，J）共有10个对象导出三支概念， 其对象导出三支概念格OEL（G，N，J）如图2所示。

容易判断，OEL（G，M，I）≤OEL（G，N，J）， 所以该决策形式背景是OE-协调的。它的OE-约简共有4个， 分别是D1=｛a，b，e｝， D2=｛a，c，e｝， D3=｛b，d，e｝， D4=｛c，d，e｝。其中OE-核心属性为e， OE-相对必要属性为a，b，c，d， 绝对不必要属性为f。

由例1可知OE-协调的决策形式背景的OE-约简未必是唯一的。

利用上述定义和定理，得到以下推论。

推论1 OE-核心是OE-约简OE-约简唯一。

证明 。（反证法）假设若OE-核心是OE-约简， 则OE-约简不唯一。不妨设Dj，Dk均为OE-约简， 且Dj≠Dk。那么OE-核心∩i∈τDiDj∩DkDj， 由于Dj是OE-约简， 而∩i∈τDiDj， 即∩i∈τDi是Dj的真子集， 所以OE-核心∩i∈τDi不可能是OE-约简， 与已知条件矛盾， 故假设不成立。因此， 如果OE-核心是OE-约简， 则OE-约简唯一。

显然成立。

推论2 m∈M是OE-不必要属性M-｛m｝是OE-协调集。

推论3 m∈M是OE-核心属性M-｛m｝不是OE-协调集。

2.2 OE-协调集判定定理

因为决策形式背景上的OE-约简D满足以下两个条件：首先， D是OE-协调集;其次， 对于任意的d∈D，D-｛d｝不是OE-协调集。即OE-约简的本质就是极小OE-协调集。因此， 只要对OE-协调集的充要条件研究透彻， 就能获得OE-约简的判定方法。下面给出OE-协调集的几个充要条件， 即OE-协调集判定定理。

证明 必要性。由定理2必要性的证明可得。

证明 必要性。由定理3可证。

定理5 （OE-协调集判定定理4）设（G，M，

证明 必要性。由定理2可证。

上面给出了4个关于决策形式背景（G，M，I，N，J）的OE-协调集等价命题（定理2～5）， 均可作为一个条件属性子集D是否为决策背景的OE-协调集的判定方法。但是对于具体决策形式背景而言， 定理2、3的理论意义更强， 定理4、5的可操作性更强。由于只考虑决策属性集N×N中的元素， 因此，实际判断时多选用定理5。

由定理5及OE-约简的定义易得OE-约简的判定方法。

例2 （续例1）针对表1所示的决策形式背景（G，M，I，N，J）， 下面根据定理5对任意选取的条件属性子集是否为OE-协调集进行判断，若条件属性子集为OE-协调集，进一步利用定理6判断其是否为OE-约简。

设D=｛a，b，e，f｝， 已知N=｛g，h，i｝， 由于

其中，D满足定理5， 所以D是OE-协调集。进一步， D1=D-｛f｝=｛a，b，e｝也是OE-协调集， 所以D不是OE-约简。而D1的所有真子集｛a， b｝， ｛a， e｝， ｛b， e｝均不是OE-协调集， 所以D1是OE-约简。同理， 可判定D2=｛a，c，e｝， D3=｛b，d，e｝， D4=｛c，d，e｝均为OE-约简， 与例1所得结果一致。

定理7 （OE-协调集判定定理5）设（G，M，I，N，J）为OE-协调的决策形式背景， 则D是OE-协调集的充要条件是

所以有

故

2.3 约简方法

下面介绍差别矩阵和差别函数的定义，通过差别矩阵和差别函数的方法可以得到OE-协调决策形式背景的OE-约簡。

定义7 设（G，M，I，N，J）为OE-协调决策形式背景， （Xi，（Ai，Bi）），（Xj，（Aj，Bj））∈OEL（G，M，I）， 称

为（Xi，（Ai，Bi））与（Xj，（Aj，Bj））的OE-差别属性集。称

ΛOEL=（DISOE（（Xi，（Ai，Bi）），

（Xj，（Aj，Bj））），（Xi，（Ai，Bi）），

（Xj，（Aj，Bj））∈OEL（G，M，I）

为该OE-协调决策形式背景的OE-差别矩阵。

例3 （续例1）根据定义7， 表2给出了例1中决策形式背景（G，M，I，N，J）的OE-差别矩阵ΛOEL。其中， 矩阵第i行第j列代表的是OE-条件概念TCi与TCj的差别属性集DISOEL（TCi， TCj）。

为叙述方便，将OE-差别矩阵中的元素稍作变换， 若DISOEL（（X，（A，B）），（Y，（C，D）））=（E，F）， 则重新记DISOEL（（X，（A，B）），（Y，（C，D）））为H=E∪F， 依然用ΛOEL来表示决策背景（G，M，I，N，J）的OE-差别矩阵。

定理8表明， OE-协调的决策形式背景的协调集与差别矩阵的每个元素相交都非空， 而约简就是找满足这些条件的协调集中的极小集合。

定义8 设（G，M，I，N，J）为OE-协调决策形式背景， 则其OE-差别函数为

根据∧，∨的运算律， 差别函数f可以变换为最小析取范式， 这个最小范式的所有合取式就是OE-协调的决策形式背景（G，M，I，N，J）的全部OE-约简。

例4 （续例1）求例1中决策形式背景（G，M，I，N，J）的OE-差别函数。

决策形式背景（G，M，I，N，J）共有4个约简，分别是D1=｛a，b，e｝，D2=｛a，c，e｝，D3=｛b，d，e｝，D4=｛c，d，e｝， 与例1所得结果相同。

3 结语

本文基于对象导出三支概念格， 在OE-协调的决策形式背景下， 首先定义了OE-协调集和OE-约简； 其次，给出了OE-协调集的几个判定定理和OE-约简的判定定理； 最后，给出了利用差别矩阵和差别函数求OE-约简的计算方法。对于OE-协调的决策形式背景， OE-约简也是保持OE-非冗余规则信息不丢失的约简， 所以本文提出的OE-协调集的判定定理也是保持OE-非冗余规则信息不丢失的协调集判定定理， 丰富了三支概念分析的内容。

研究决策形式背景的属性约简理论是十分有意义的， 在约简后的决策背景上进行知识的更新与获取， 既能保证知识的完整性， 也更加精炼。本文是从对象导出三支概念格出发，研究了决策形式背景保持OE-协调性的属性约简问题，下一步还可从属性导出三支概念格出发来研究决策属性背景的保持AE-协调性的约简问题。

参考文献

［1］ WILLE R. Restructuring lattice theory： An approach based on hierarchies of concepts ［C］∥RIVAL I. Ordered Sets. Dordrecht-Boston： Reidel， 1982： 445-470.

［2］ GANTER B， WILLE R. Formal concept analysis： Mathematical foundations ［M］.Berlin： Springer-Verlag， 1999.

［3］ ZHI H L， QI J J， QIAN T， et al.Conflict analysis under one-vote veto based on approximate three-way concept lattice［J］. Information Sciences， 2020， 516： 316-330.

［4］ YAO Y Y. An outline of a theory of three-way decisions ［C］∥Rough Sets and Current Trends in Computing. Berlin： Springer， 2012： 1-17.

［5］ QI J J， WEI L， YAO Y Y. Three-way formal concept analysis ［C］∥Rough Sets and Knowledge Technology. Cham： Springer， 2014： 732-741.

［6］ QI J J， QIAN T， WEI L. The connections between three-way and classical concept lattices ［J］. Knowledge-Based Systems， 2016， 91： 143-151.

［7］ REN R S， WEI L. The attribute reductions of three-way concept lattices ［J］.Knowledge-Based Systems， 2016， 99： 92-102.

［8］ YU H Y， LI Q G， CAI M J. Characteristics of three-way concept lattices and three-way rough concept lattices［J］.Knowledge-Based Systems， 2018， 146： 181-189.

［9］ ZHI H L， QI J J， QIAN T， et al. Three-way dual concept analysis［J］.International Journal of Approximate Reasoning， 2019， 114： 151-165.

［10］YANG S C， LU Y N， JIA X Y， et al. Constructing three-way concept lattice based on the composite of classical lattices［J］.International Journal of Approximate Reasoning， 2020， 121： 174-186.

［11］ZHAO X R， MIAO D Q， HU B Q. On relationship between three-way concept lattices［J］.Information Sciences， 2020， 538： 396-414.

［12］魏玲. 粗糙集與概念格的约简理论与方法［D］.西安： 西安交通大学， 2005.

［13］WEI L， QI J J， ZHANG W X. Attribute reduction theory of concept lattice based on decision formal contexts ［J］.Science in China Series F： Information Sciences， 2008， 51（7）： 910-923.

［14］LI J H， MEI C L， LYU Y J. Knowledge reduction in decision formal contexts［J］.Knowledge-Based Systems， 2011， 24（5）： 709-715.

［15］LI J H， MEI C L， WANG J H， et al. Rule-preserved object compression in formal decision contexts using concept lattices ［J］.Knowledge-Based Systems， 2014， 71： 435-445.

［16］CHEN J K， MI J S， XIE B， et al. Attribute reduction in formal decision contexts and its application to finite topological spaces ［J］.International Journal of Machine Learning and Cybernetics， 2021， 12： 39-52.

［17］陈雪， 魏玲， 钱婷. 基于AE-概念格的决策形式背景属性约简［J］.山东大学学报（理学版）， 2017， 52（12）： 95-103.

CHEN X， WEI L， QIAN T. Attribute reduction in formal decision contexts based on AE-concept lattices ［J］.Journal of Shandong University （Natural Science）， 2017， 52（12）： 95-103.

［18］林洪， 秦克云. 决策形式背景三支粒约简［J］.计算机科学， 2018， 45（10）： 47-50.

LIN H， QIN K Y. Three-way granular reduction for decision formal context ［J］.Computer Science， 2018， 45（10）： 47-50.

［19］劉琳， 钱婷， 魏玲. 基于属性导出三支概念格的决策背景规则提取［J］.西北大学学报（自然科学版）， 2016， 46（4）： 481-487.

LIU L， QIAN T， WEI L.Rules extraction in formal decision contexts based on attribute-induced three-way concept lattices ［J］. Journal of Northwest University （Natural Science Edition）， 2016， 46（4）： 481-487.

［20］刘琳， 魏玲， 钱婷. 决策形式背景中具有置信度的三支规则提取［J］.山东大学学报（理学版）， 2017， 52（2）： 101-110.

LIU L， WEI L， QIAN T. Three-way rules extraction in formal decision contexts with confidence ［J］.Journal of Shandong University （Natural Science）， 2017， 52（2）：101-110.

［21］WEI L， LIU L， QI J J， et al. Rules acquisition of formal decision contexts based on three-way concept lattices ［J］.Information Sciences， 2020， 516： 529-544.

［22］LONG B H， XU W H， ZHANG X Y. Double threshold construction method for attribute-induced three-way concept lattice in incomplete fuzzy formal context ［J］.The Journal of Engineering， 2020（13）： 549-554.