基于三支概念格線圖的混合蘊含獲取

朱曉敏， 祁建軍

(西安電子科技大學 計算機學院 陜西 西安 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混合屬性蘊含(g0gggggg,?)→({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