基于三支概念格线图的混合蕴含获取

朱晓敏， 祁建军

(西安电子科技大学 计算机学院 陕西 西安 710071)

DOI: 10.13705/j.issn.1671-6841.2017083

基于三支概念格线图的混合蕴含获取

朱晓敏， 祁建军

(西安电子科技大学 计算机学院 陕西 西安 710071)

考虑到三支概念分析中三支算子可以表达对象集和属性集之间“共同具有”和“共同不具有”这两种语义，基于该理论对混合蕴含规则进行研究.首先定义三支概念分析下的混合蕴含规则，并利用三支算子的性质给出混合蕴含规则成立的充分必要条件；然后根据三支概念的构建算法以及三支概念之间的偏序关系给出三支概念格线图的构建方法；最后，基于三支概念格线图提出混合蕴含规则的获取方法.

三支概念分析； 三支算子； 混合蕴含； 三支概念格； 线图

DOI: 10.13705/j.issn.1671-6841.2017083

0 引言

三支概念分析(three-way concept analysis，3WCA)[1]理论是结合形式概念分析[2]和三支决策理论[3]提出的，它是一种新的知识表示与知识发现的理论方法.目前已有一些基于三支概念分析理论的研究成果.文献[4]研究了TWCA以及三支概念格和经典概念格之间的联系；文献[5]研究了基于三支概念分析的属性约简问题；文献[6-7]针对决策形式背景的规则提取方法进行了研究；文献 [8-9]分别提出了三支概念的构建算法CbO3C和PCbO3C，其中CbO3C借鉴CbO算法[10]的思想，PCbO3C是利用多线程技术并行计算核心三支概念.

蕴含规则的挖掘算法不断得到优化[11]，在形式概念分析中获取蕴含规则是一项重要的研究内容.文献[12]提出构建概念格线图的增量式算法CLearner，并在此基础上获取关联规则，文献[13]基于属性约简和近似属性约简的概念提出属性蕴含和关联规则的获取方法.以上主要研究属性子集之间的“具有”关系，即正属性蕴含.忽视形式背景中负属性蕴含的信息可能会得到不完整的结论，比如仅考虑正属性无法表示蕴含规则：“鸵鸟是鸟，但不会飞”.在形式概念分析理论的基础上属性子集之间的“不具有”关系也已经被研究.文献[14]结合NextClosure算法提出混合属性蕴含的获取方法，文献[15-16]基于原形式背景与其补形式背景的并置提出混合属性蕴含的获取方法.三支概念分析中三支算子可以同时表示数据集中“共同具有”和“共同不具有”这两种语义，当针对属性集进行考虑时，“共同具有”和“共同不具有”的属性子集分别对应正属性蕴含和负属性蕴含的前件或后件，利用三支算子可直接基于原形式背景获取混合属性蕴含，在一定程度上减少了计算量和存储空间.因此，本文基于三支概念分析理论研究混合蕴含规则，结合三支概念的构建算法给出三支概念格线图的构建方法，最后，基于三支概念格线图给出混合蕴含规则成立的条件.

1 基础知识

本节给出所需要用到的三支概念分析理论的相关定义.

定义1[17]形式背景(U,V,R)包括两个集合U和V，以及二者之间的关系R.U中的每个元素称为对象，V中的每个元素称为属性.对象u与属性v有关系R，记为uRv，读作“对象u具有属性v”.

如果X*=A与A*=X同时成立，则称(X,A)为(U,V,R)的一个形式概念(简称概念)，X称为概念(X,A)的外延，A称为内涵.特别地，对于对象u∈U，相应的对象概念[18]为：γu=({u}**,{u}*).对于属性v∈V，相应的属性概念[18]为：μv=({v}*,{v}**).

形式背景(U,V,R)中所有的形式概念组成了一个完备格，称为(U,V,R)的概念格，并记为CL(U,V,R).

例1表1是形式背景(U,V,R)，其中U={1,2,3,4}，V={a,b,c,d}.图1为(U,V,R)对应的概念格CL(U,V,R).并且(U,V,R)中所有的对象概念为

γ(1)=({1},{b,d}),γ(2)=({1,2},{b}),

γ(3)=({3,4},{c}),γ(4)=({4},{a,c}).

所有的属性概念为

μ(a)=({4},{a,c}),μ(b)=({1,2},{b}),

μ(c)=({3,4},{c}),μ(d)=({1},{b,d}).

表1 形式背景(U,V,R)

图1 CL(U,V,R)Fig.1 CL(U,V,R)

在三支概念分析中文献[1]将定义2给出的算子称为正算子，并给出相应负算子的定义.

∀v∈A((uRv))}.

文献[1]把正算子和负算子结合起来形成两对三支算子，分别称为OE算子和AE算子.

如果Xlt;·=(A,B)与(A,B)·gt;=X同时成立，则称(X,(A,B))为(U,V,R)的一个对象导出三支概念，简称OE概念.X称为(X,(A,B))的外延，(A,B)称为(X,(A,B))的内涵，由所有OE概念组成的集合记作OEL(U,V,R)，叫作对象导出三支概念格，简称OE概念格.

如果(X，Y)·gt;=A与Alt;·=(X，Y)同时成立，则称((X,Y),A)为(U,V,R)的一个属性导出三支概念，简称AE概念.(X,Y)称为((X,Y),A)的外延，A称为((X,Y),A)的内涵.由所有AE概念组成的集合记作AEL(U,V,R)，叫作属性导出三支概念格，简称AE概念格.

对于对象子集X⊆U，属性子集A⊆V，有

对于OE概念(X,(A,B))和(Y,(C,D))，若满足偏序关系：(X,(A,B))≤(Y,(C,D))⟺X⊆Y⟺(C,D)⊆(A,B)，则称(Y,(C,D))为(X,(A,B))的父概念，(X,(A,B))为(Y,(C,D))的子概念. 对于AE概念((X,Y),A)和((Z,W),B)，若满足偏序关系:((X,Y),A)≤((Z,W),B)⟺(X,Y)⊆(Z,W)⟺B⊆A，则称((Z,W),B)为((X,Y),A)的父概念，((X,Y),A)为((Z,W),B)的子概念.设(X,(A,B)),(Y,(C,D))∈OEL(U,V,R)，则(X,(A,B))∧(Y,(C,D))=(X∩Y,((A,B)∪(C,D))·gt;lt;·).设((X,Y),A),((Z,W),B)∈AEL(U,V,R)，则((X,Y),A)∨((Z,W),B)=(((X,Y)∪(Z,W))·gt;lt;·,A∩B).

例2形式背景(U,V,R)(表1)对应的OEL(U,V,R)和AEL(U,V,R)分别如图2和图3所示.

图2 OEL(U,V,R)Fig.2 OEL(U,V,R)

图3 AEL(U,V,R)Fig.3 AEL(U,V,R)

下面给出属性蕴含定义以及相关性质.

定义5[18]设(U,V,R)为形式背景，A,B⊆V，若满足“具有A中所有属性的对象也具有B中所有属性”，则称属性蕴含A→B在(U,V,R)中成立.属性蕴含A→B在(U,V,R)中成立，当且仅当A*⊆B*.

形式背景(U,V,R)中对象之间的蕴含规则也可被类似地讨论.

设(U,V,R)为形式背景，X,Y⊆U，如果满足“对象集X共同具有的属性，对象集Y也共同具有”，则称对象蕴含X→Y在(U,V,R)中成立.对象蕴含X→Y在(U,V,R)中成立，当且仅当X*⊆Y*.

2 三支概念格线图

概念格线图以一种简洁的形式表示对象集和属性集之间的“具有”关系，为了能以同样的形式表示对象集和属性集之间“具有”和“不具有”的关系，本节针对三支概念格线图进行研究.

2.1 对象导出三支概念格线图

对象导出三支概念格线图可基于对象导出三支概念格获得，具体步骤如下：

(1) 根据三支概念的构建算法[8-9]构建OEL(U,V,R)，并用小圆圈代表每一个OE概念；

2.2 属性导出三支概念格线图

构建属性导出三支概念格线图的具体步骤如下：

(1) 根据三支概念的构建算法[8-9]构建AEL(U,V,R)，并用小圆圈代表每一个AE概念；

例3对于形式背景(U,V,R)(表1)，对象导出三支概念格线图和属性导出三支概念格线图分别如图4和图5所示.此处仅以对象导出三支概念格线图为例，给出如下具体构建过程：

(1) 构建OEL(U,V,R).不同于图2，这里仅用小圆圈代表每一个OE概念；

(3) 标记对象OE概念.比如，用“1”标记对象1的对象OE概念({1},({b,d},{a,c}))；

(4) 标记正属性OE概念和负属性OE概念.比如，用“a+”标记a的正属性OE概念({4},({a,c},{b,d}))，用“a-”标记a的负属性OE概念({1,2,3},(∅,{a})).

图4 三支概念格线图OEL(U,V,R)Fig.4 The line diagram of OEL(U,V,R)

图5 三支概念格线图AEL(U,V,R)Fig.5 The line diagram of AEL(U,V,R)

3 混合蕴含规则

首先基于三支概念分析理论提出混合属性蕴含的定义，然后讨论如何基于对象导出三支概念格线图获取混合属性蕴含，利用类似的方法对混合对象蕴含展开研究.混合属性蕴含的获取是基于对象导出三支概念格线图，而混合对象蕴含的获取是基于属性导出三支概念格线图.

3.1 混合属性蕴含

三支概念分析下混合属性蕴含的定义如下.

定义6设(U,V,R)是一个形式背景，A,B,C,D⊆V，如果满足“拥有A中所有属性并且不拥有B中任意属性的对象拥有C中所有属性且不拥有D中任意属性”，则称混合属性蕴含(A,B)→(C,D)在(U,V,R)中成立.其中二元组(A,B)称为(A,B)→(C,D)的前件，二元组(C,D)称为后件.

根据混合属性蕴含的定义和OE算子的性质，可得以下结论.

定理1设(U,V,R)是一个形式背景，A,B,C,D⊆V，混合属性蕴含(A,B)→(C,D)在(U,V,R)中成立的充分必要条件为：(A,B)·gt;⊆(C,D)·gt;.

例4混合属性蕴含({d},∅)→({b},{c})在(U,V,R)(表1)中成立，因为

然而，混合属性蕴含({c},∅)→({a},{b})在(U,V,R)中不成立，因为

根据混合属性蕴含的定义和对象导出三支概念格线图的性质，可得以下定理.

证明由OE概念之间偏序关系的性质以及OE概念之间下确界的定义可知，

又由定理1可知定理2成立.

由定理2可知，根据对象导出三支概念格线图可以判断任意给定的混合属性蕴含是否成立.

3.2 混合对象蕴含

当具有相同属性的对象被要求划分为同一类时，对象蕴含可以给出表示.然而，如果同时需要考虑不拥有某些属性的对象，混合对象蕴含将是更好的表达方式.接下来在三支概念分析理论的基础上针对混合对象蕴含进行研究，混合对象蕴含的定义如下.

定义7设(U,V,R)是一个形式背景，X,Y,Z,W⊆U，如果满足“被X中所有对象拥有并且不被Y中任意对象所拥有的属性，被Z中所有对象拥有且不被W中任意对象所拥有”，则称混合对象蕴含(X,Y)→(Z,W)在(U,V,R)中成立.其中二元组(X,Y)称为(X,Y)→(Z,W)的前件，二元组(Z,W)称为后件.

根据混合对象蕴含和AE算子的定义，可得以下定理.

定理3设(U,V,R)是一个形式背景，X,Y,Z,W⊆U，混合对象蕴含(X,Y)→(Z,W)在(U,V,R)中成立，当且仅当(X,Y)·gt;⊆(Z,W)·gt;.

根据混合对象蕴含的定义和属性导出三支概念格线图的性质，可得以下定理.

证明证明方法同定理2.

由定理4可知，根据属性导出三支概念格线图可以判断任意给定的混合对象蕴含是否成立.

4 结论

基于三支概念分析理论对混合蕴含规则进行研究，首先提出混合属性蕴含和混合对象蕴含的定义，结合三支算子的性质给出其成立的充分必要条件，然后提出三支概念格线图的构建方法并在此基础上获取混合蕴含规则.三支概念格线图为数据可视化提供了工具，其相对概念格提供了更多的信息，而混合属性蕴含可用于数据挖掘、机器学习等领域，比如利用正、负关联规则用于分类[19]以及文本聚类[20]等.混合蕴含规则的获取以及生成混合蕴含规则的基是至关重要的，未来将针对此问题进行深入的研究.

[1] QI J J, WEI L, YAO Y Y. Three-way formal concept analysis [C]//Proceedings of International Conference on Rough Sets and Knowledge Technology. Shanghai, 2014:732-741.

[2] WILLE R.Restructuring lattices theory: an approach based on hierarchies of concepts [C]//Proceedings of the 7th International Conference on Formal Concept Analysis. Darmstadt, 2009:314-339.

[3] YAO Y Y. An outline of a theory of three-way decisions [C]// Proceedings of the 8th International Conference on Rough Sets and Current Trends in Computing. Chengdu, 2012: 1-17.

[4] QI J J, QIAN T, WEI L. The connections between three-way and classical concept lattices [J]. Knowledge-based systems, 2016, 91: 143-151.

[5] REN R S, WEI L. The attribute reductions of three-way concept lattices[J]. Knowledge-based systems，2016, 99: 92-102.

[6] 刘琳，钱婷，魏玲. 基于属性导出三支概念格的决策背景规则提取[J]. 西北大学学报(自然科学版), 2016, 46(4): 481-487.

[7] 刘琳，魏玲，钱婷．决策形式背景中具有置信度的三支规则提取[J]．山东大学学报(理学版), 2017, 52(2):101-110.

[8] 汪文威，祁建军. 三支概念的构建算法[J]. 西安电子科技大学学报(自然科学版), 2017, 44(1): 77-82.

[9] 祁建军,汪文威.多线程并行构建三支概念[J]. 西安交通大学学报(自然科学版),2017, 51(3): 116-121.

[10] ANDREWS S. A ‘Best-of-Breed’approach for designing a fast algorithm for computing fixpoints of Galois connections[J]. Information sciences, 2015, 295: 633-649.

[11] 王青,谭良,杨显华. 基于Spark的Apriori并行算法优化实现[J]. 郑州大学学报(理学版), 2016, 48(4):60-64.

[12] GALLO A, MEO R. Using a reinforced concept lattice to incrementally mine association rules from closed itemsets[M]// Knowledge Discovery in Inductive Databases. Berlin： Springer, 2007:97-115.

[13] XIE Z, LIU Z. From intent reducts for attribute implications to approximate intent reducts for association rules[C]//Proceedings of the 5th International Conference on Computer and Information Technology. Gazirpur, 2005: 162-169.

[15] MISSAOUI R, NOURINE L, RENAUD Y. An inference system for exhaustive generation of mixed and purely negative implications from purely positive ones[C]//Proceedings of the 7th International Conference on Concept Lattices and Their Applications. Sevilla, 2010:271-282.

[16] MISSAOUI R, NOURINE L, RENAUD Y. Computing implications with negation from a formal context[J]. Fundamenta informaticae, 2012, 115(4):357-375.

[17] GANTER B, WILLE R. Formal concept analysis, mathematical foundations [M]. Berlin: Springer-Verla, 1999.

[18] GANTER B, OBIEDKOV S. Conceptual exploration [M]. Berlin: Springer-Verla, 2016.

[19] ANTONIE M L. An associative classifier based on positive and negative rules[C]//The 9th Workshop on Research Issues in Data Mining and Knowledge Discovery. Paris, 2004:64-69.

[20] 曲守宁, 王钦, 邹燕, 等. 基于关联规则的文本聚类算法的研究[J]. 计算机应用研究, 2008, 25(4): 986-988.

(责任编辑：孔 薇)

MiningMixedImplicationsBasedontheLineDiagramsofThree-wayConceptLattices

ZHU Xiaomin, QI Jianjun

(SchoolofComputerScienceandTechnology,XidianUniversity,Xi′an710071,China)

In the theory of three-way concept analysis, three-way operator expressed the semantics of "jointly possessed" and "jointly not possessed" between the objects and the attributes of a formal context. On the basis of such viewpoints, mixed implications were studied. Mixed implications in three-way concept analysis were defined firstly, and the necessary and sufficient conditions to make the mixed implications hold were given. Then the method of constructing the line diagrams of three-way concept lattices was given based on the algorithms for constructing three-way concepts and the partial order relations between three-way concepts. Finally, the approach to mining mixed implications from the line diagrams of three-way concept lattices was proposed.

three-way concept analysis; three-way operator; mixed implication; three-way concept lattice; line diagram

2017-04-19

国家自然科学基金项目(11371014)；陕西省自然科学基础研究计划项目(2014JM8306)．

朱晓敏(1993—)，女，河南商丘人，主要从事三支概念分析研究，E-mail:m15191852663@163.com；通信作者：祁建军(1970—)，男，陕西西安人，副教授，主要从事三支概念分析、概念格、三支决策以及粒计算研究，E-mail:qijj@mail.xidian.edu.cn．

TP18

A

1671-6841(2017)04-0016-06