基于OE-概念格的形式背景属性约简

张呈玲，李进金，林艺东，2

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

2.厦门大学 数学科学学院，福建 厦门 361000

形式概念分析（Formal concept analysis）是由德国数学家Wille[1]于1982 年提出的一种建构概念格的有力工具。它以形式背景为基础展开讨论，通过对象集和属性集之间的关系建立一种概念层次关系。这充分体现了概念之间的泛化与特化的关系[2]，同时也体现了概念内涵和外延的完美匹配。近年来，形式概念分析已被应用到诸多领域，如机器学习、决策分析等[3-5]。形式背景的属性约简理论一直是学术界的研究热点。因为这可以获得更加简洁的知识。目前为止，已取得丰硕成果。张文修等[3]通过构造辨识矩阵提出了概念格属性约简方法，及讨论了不同类型属性的特征。王霞等[6]借助不可约元研究了形式背景的对象和属性约简。接着，吴伟志等[7]从粒计算的角度提出了形式背景的粒结构，并给出了粒约简的方法。相较于文献[3]，此方法无需构造概念格可直接通过区分属性获得约简。同时，形式背景是一个二元关系表，可以被认为是布尔矩阵。基于此，通过矩阵理论解决形式背景的有关问题已经取得了重要的成果[8-13]。李同军等[8]将布尔矩阵理论应用于形式概念分析中，给出了布尔形式背景的概念及探讨了布尔形式概念的计算。张清新等[9]针对对象子集的内涵和属性子集的外延提出了矩阵特征表示方法，并进一步地，利用协调集判断矩阵可探讨一个集合是否是协调集。接着，林艺东等[10]在文献[9]的粒矩阵的基础之上，借助属性重要度的刻画，给出了启发式的约简算法。

上述大家熟悉的模型均是二支模型，然而，在实际应用中并非如此。姚一豫等[14]于2009年提出了以“三分而治”思想为主的三支决策理论，即依据对象特征将论域划分为正域、负域、边界域，并对这三个区域的对象采取适当的策略。针对该理论，祁建军等[15]引入形式概念分析，给出了三支概念的定义，即对象导出三支概念和属性导出三支概念。任睿思等[16]从格结构、不可约元、粒计算角度讨论了三支概念格的属性约简问题。接着，文献[17]和[18]从粒计算角度，分别讨论了对象导出三支概念格的形式背景和决策形式背景的三支粒约简，且提出了其与二支概念格粒约简的联系。但针对三支概念格，目前较少利用矩阵理论研究三支概念格的属性约简。

因此，本文受文献[10]的启发，在文献[17-18]的约简框架下，针对对象导出三支概念格的形式背景，借助矩阵理论研究其属性约简问题。首先，提出OE-对象粒矩阵。其次，基于此矩阵，刻画属性之间的相似度，进而给出属性的重要度，进一步设计启发式属性约简的矩阵方法。接着，通过对象导出三支概念格的决策形式背景的引入，从规则提取的角度说明约简集对应的三支规则集更加简洁。

1 预备知识

1.1 三支概念分析

1.2 布尔矩阵理论

2 基于矩阵的OE-概念格的形式背景属性约简

本章基于文献[16]提出的OE-概念格的属性约简理论，并进一步地，探讨该理论的矩阵约简方法。

表1 形式背景K=(U,A,I)Table 1 Formal context K=(U,A,I)

3 基于矩阵的OE-概念格的决策形式背景属性约简

4 基于矩阵的对象导出三支概念格的决策形式背景的规则提取

本章在OE-概念格的三支协调决策形式背景下，讨论其三支规则集。下面先给出规则获取的概念。

定义12[19]设S=(U,A,I,D,J)是对象三支协调的，对于任意(X,(A,B))∈OEL(U,A,I)，若存在(Y,(C,D))∈OEL(U,D,J)(Y≠φ,U)，满足X⊆Y，称A→C是对象导出的三支正决策规则；同时，notB→ notD是对象导出的三支负决策规则。并记所有三支正规则的集合为PR(S)，所以三支负规则集合记为NR(S)。其全体三支规则集合用OE(S)。

设S是对象三支协调的，若两个三支正决策规则A→B和A′→B′满足条件A⊆A′，B⊇B′，称A→B蕴含A′→B′；同样地，若两个负决策规则notC→not和notC′→notD′满足条件C⊆C′，D⊇D′，称notC→notD蕴含notC′→notD′。

例5针对表2 中的OE-概念格决策形式背景S=(U,A,I,D,J)，借助图1和图2及定义12，表3给出所有的三支规则集OE(S)。

表2 决策形式背景S=(U,A,I,D,J)Table 2 Formal decision context S=(U,A,I,D,J)

图1 对象导出三支概念格OEL(U,A,I)Fig.1 OE three-way concept lattice OEL(U,A,I)

图2 对象导出三支概念格OEL(U,D,J)Fig.2 OE three-way concept lattice OEL(U,D,J)

结合图2 和图3，约简集red={a3,a6}对应的决策形式背景Sred的三支规则集如表4所示。

图3 对象导出三支概念格OEL(U,red,Ired)Fig.3 OE three-way concept lattice OEL(U,red,Ired)

由表3 和表4 的分析可知，在OEG 粒约简集red={a3,a6} 对应的决策形式背景Sred=(U,Ared,Ired,D,J) 的三支规则集蕴含原决策形式背景S=(U,A,I,D,J)的三支规则集。并且，OEG 粒约简的决策形式背景中的三支规则更加简洁。

表3 例3的三支规则集OE(S)Table 3 Three-way decision rule of example 3 OE(S)

表4 例4的三支规则集OE(Sred)Table 4 Three-way decision rule of example 4 OE(Sred)

5 实验分析

本章将通过仿真实验验证所提出方法的有效性。实验环境是在Windows 10及Intel®Core™i5-6200UCPU@2.3 GHz，8.0 GB内存。仿真实验所用的软件Matlab 9.3。

5.1 收集数据

设K1、K2为两个形式背景，称[K1K2] 为K1、K2的组合，为K1、K2的串联，为K1、K2的合并[20]。

S1和S7分别是表5 和表6 的决策形式背景，如表7所示。S2是S1的90 倍串联；S3是S1的5 倍合并、9 倍串联；S4是S2的6 倍组合；S5是S1的7 倍组合，70 倍串联；S6是由S3的4 倍组合与S1的5 倍串联、20 倍组合串联形成。由上述方法，经S7相应的组合、串联、合并得到S8、S9、S10、S11。

表5 决策形式背景S1=(U,A,I,D,J)Table 5 Formal decision context S1=(U,A,I,D,J)

表6 决策形式背景S7=(U,A,I,D,J)Table 6 Formal decision context S7=(U,A,I,D,J)

表7 实验数据Table 7 Experimental data

5.2 实验比较

通过比较算法2（HOGR）与文献[18]约简理论（记为OER）之间的差异。值得注意的是，文献[18]借助辨识矩阵可以得出所有的约简集。为了便于比较，算法OER求决策形式背景下的一个极小约简。两者算法的约简个数及运行时间如表8所示。

表8 实验结果比较Table 8 Comparison of experimental results

根据表8可知，算法HOGR和OER在每个数据集上的约简个数相同，但是HOGR 在计算约简集的时间比OER 的运行时间短。因此，从运行时间角度，算法HOGR比OER输出约简集更具优越性。

6 结束语

本文研究了OE-概念格的形式背景的启发式属性约简方法。首先根据三支算子的定义，借助矩阵理论，给出了OE-对象粒矩阵。然后，在保持OE-对象粒矩阵不变的前提下，探讨属性之间的相似性及给出内外重要度的概念，接着设计启发式的约简算法。其次，将上述理论结果应用于OE-概念格的决策形式背景，给出核心属性的判定条件，且设计了基于矩阵的启发式算法。最后，从规则提取的角度得出了OEG 粒约简集所对应的三支规则集将更加简洁。未来可以在本文的基础上进一步地研究基于属性导出三支概念格属性约简的矩阵方法。