朱曉敏， 祁建軍

(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院 陜西 西安 710071)

DOI: 10.13705/j.issn.1671-6841.2017083

基于三支概念格線圖的混合蘊(yùn)含獲取

朱曉敏， 祁建軍

(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院 陜西 西安 710071)

考慮到三支概念分析中三支算子可以表達(dá)對象集和屬性集之間“共同具有”和“共同不具有”這兩種語義，基于該理論對混合蘊(yùn)含規(guī)則進(jìn)行研究.首先定義三支概念分析下的混合蘊(yùn)含規(guī)則，并利用三支算子的性質(zhì)給出混合蘊(yùn)含規(guī)則成立的充分必要條件；然后根據(jù)三支概念的構(gòu)建算法以及三支概念之間的偏序關(guān)系給出三支概念格線圖的構(gòu)建方法；最后，基于三支概念格線圖提出混合蘊(yùn)含規(guī)則的獲取方法.

三支概念分析； 三支算子； 混合蘊(yùn)含； 三支概念格； 線圖

DOI: 10.13705/j.issn.1671-6841.2017083

0 引言

三支概念分析(three-way concept analysis，3WCA)[1]理論是結(jié)合形式概念分析[2]和三支決策理論[3]提出的，它是一種新的知識(shí)表示與知識(shí)發(fā)現(xiàn)的理論方法.目前已有一些基于三支概念分析理論的研究成果.文獻(xiàn)[4]研究了TWCA以及三支概念格和經(jīng)典概念格之間的聯(lián)系；文獻(xiàn)[5]研究了基于三支概念分析的屬性約簡問題；文獻(xiàn)[6-7]針對決策形式背景的規(guī)則提取方法進(jìn)行了研究；文獻(xiàn) [8-9]分別提出了三支概念的構(gòu)建算法CbO3C和PCbO3C，其中CbO3C借鑒CbO算法[10]的思想，PCbO3C是利用多線程技術(shù)并行計(jì)算核心三支概念.

蘊(yùn)含規(guī)則的挖掘算法不斷得到優(yōu)化[11]，在形式概念分析中獲取蘊(yùn)含規(guī)則是一項(xiàng)重要的研究內(nèi)容.文獻(xiàn)[12]提出構(gòu)建概念格線圖的增量式算法CLearner，并在此基礎(chǔ)上獲取關(guān)聯(lián)規(guī)則，文獻(xiàn)[13]基于屬性約簡和近似屬性約簡的概念提出屬性蘊(yùn)含和關(guān)聯(lián)規(guī)則的獲取方法.以上主要研究屬性子集之間的“具有”關(guān)系，即正屬性蘊(yùn)含.忽視形式背景中負(fù)屬性蘊(yùn)含的信息可能會(huì)得到不完整的結(jié)論，比如僅考慮正屬性無法表示蘊(yùn)含規(guī)則：“鴕鳥是鳥，但不會(huì)飛”.在形式概念分析理論的基礎(chǔ)上屬性子集之間的“不具有”關(guān)系也已經(jīng)被研究.文獻(xiàn)[14]結(jié)合NextClosure算法提出混合屬性蘊(yùn)含的獲取方法，文獻(xiàn)[15-16]基于原形式背景與其補(bǔ)形式背景的并置提出混合屬性蘊(yùn)含的獲取方法.三支概念分析中三支算子可以同時(shí)表示數(shù)據(jù)集中“共同具有”和“共同不具有”這兩種語義，當(dāng)針對屬性集進(jìn)行考慮時(shí)，“共同具有”和“共同不具有”的屬性子集分別對應(yīng)正屬性蘊(yùn)含和負(fù)屬性蘊(yùn)含的前件或后件，利用三支算子可直接基于原形式背景獲取混合屬性蘊(yùn)含，在一定程度上減少了計(jì)算量和存儲(chǔ)空間.因此，本文基于三支概念分析理論研究混合蘊(yùn)含規(guī)則，結(jié)合三支概念的構(gòu)建算法給出三支概念格線圖的構(gòu)建方法，最后，基于三支概念格線圖給出混合蘊(yùn)含規(guī)則成立的條件.

1 基礎(chǔ)知識(shí)

本節(jié)給出所需要用到的三支概念分析理論的相關(guān)定義.

定義1[17]形式背景(U,V,R)包括兩個(gè)集合U和V，以及二者之間的關(guān)系R.U中的每個(gè)元素稱為對象，V中的每個(gè)元素稱為屬性.對象u與屬性v有關(guān)系R，記為uRv，讀作“對象u具有屬性v”.

如果X*=A與A*=X同時(shí)成立，則稱(X,A)為(U,V,R)的一個(gè)形式概念(簡稱概念)，X稱為概念(X,A)的外延，A稱為內(nèi)涵.特別地，對于對象u∈U，相應(yīng)的對象概念[18]為：γu=({u}**,{u}*).對于屬性v∈V，相應(yīng)的屬性概念[18]為：μv=({v}*,{v}**).

形式背景(U,V,R)中所有的形式概念組成了一個(gè)完備格，稱為(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)對應(yīng)的概念格CL(U,V,R).并且(U,V,R)中所有的對象概念為

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

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

所有的屬性概念為

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

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

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

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

在三支概念分析中文獻(xiàn)[1]將定義2給出的算子稱為正算子，并給出相應(yīng)負(fù)算子的定義.

?v∈A((uRv))}.

文獻(xiàn)[1]把正算子和負(fù)算子結(jié)合起來形成兩對三支算子，分別稱為OE算子和AE算子.

如果Xlt;·=(A,B)與(A,B)·gt;=X同時(shí)成立，則稱(X,(A,B))為(U,V,R)的一個(gè)對象導(dǎo)出三支概念，簡稱OE概念.X稱為(X,(A,B))的外延，(A,B)稱為(X,(A,B))的內(nèi)涵，由所有OE概念組成的集合記作OEL(U,V,R)，叫作對象導(dǎo)出三支概念格，簡稱OE概念格.

如果(X，Y)·gt;=A與Alt;·=(X，Y)同時(shí)成立，則稱((X,Y),A)為(U,V,R)的一個(gè)屬性導(dǎo)出三支概念，簡稱AE概念.(X,Y)稱為((X,Y),A)的外延，A稱為((X,Y),A)的內(nèi)涵.由所有AE概念組成的集合記作AEL(U,V,R)，叫作屬性導(dǎo)出三支概念格，簡稱AE概念格.

對于對象子集X?U，屬性子集A?V，有

對于OE概念(X,(A,B))和(Y,(C,D))，若滿足偏序關(guān)系：(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)，若滿足偏序關(guān)系:((X,Y),A)≤((Z,W),B)?(X,Y)?(Z,W)?B?A，則稱((Z,W),B)為((X,Y),A)的父概念，((X,Y),A)為((Z,W),B)的子概念.設(shè)(X,(A,B)),(Y,(C,D))∈OEL(U,V,R)，則(X,(A,B))∧(Y,(C,D))=(X∩Y,((A,B)∪(C,D))·gt;lt;·).設(shè)((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)對應(yīng)的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)

下面給出屬性蘊(yùn)含定義以及相關(guān)性質(zhì).

定義5[18]設(shè)(U,V,R)為形式背景，A,B?V，若滿足“具有A中所有屬性的對象也具有B中所有屬性”，則稱屬性蘊(yùn)含A→B在(U,V,R)中成立.屬性蘊(yùn)含A→B在(U,V,R)中成立，當(dāng)且僅當(dāng)A*?B*.

形式背景(U,V,R)中對象之間的蘊(yùn)含規(guī)則也可被類似地討論.

設(shè)(U,V,R)為形式背景，X,Y?U，如果滿足“對象集X共同具有的屬性，對象集Y也共同具有”，則稱對象蘊(yùn)含X→Y在(U,V,R)中成立.對象蘊(yùn)含X→Y在(U,V,R)中成立，當(dāng)且僅當(dāng)X*?Y*.

2 三支概念格線圖

概念格線圖以一種簡潔的形式表示對象集和屬性集之間的“具有”關(guān)系，為了能以同樣的形式表示對象集和屬性集之間“具有”和“不具有”的關(guān)系，本節(jié)針對三支概念格線圖進(jìn)行研究.

2.1 對象導(dǎo)出三支概念格線圖

對象導(dǎo)出三支概念格線圖可基于對象導(dǎo)出三支概念格獲得，具體步驟如下：

(1) 根據(jù)三支概念的構(gòu)建算法[8-9]構(gòu)建OEL(U,V,R)，并用小圓圈代表每一個(gè)OE概念；

2.2 屬性導(dǎo)出三支概念格線圖

構(gòu)建屬性導(dǎo)出三支概念格線圖的具體步驟如下：

(1) 根據(jù)三支概念的構(gòu)建算法[8-9]構(gòu)建AEL(U,V,R)，并用小圓圈代表每一個(gè)AE概念；

例3對于形式背景(U,V,R)(表1)，對象導(dǎo)出三支概念格線圖和屬性導(dǎo)出三支概念格線圖分別如圖4和圖5所示.此處僅以對象導(dǎo)出三支概念格線圖為例，給出如下具體構(gòu)建過程：

(1) 構(gòu)建OEL(U,V,R).不同于圖2，這里僅用小圓圈代表每一個(gè)OE概念；

(3) 標(biāo)記對象OE概念.比如，用“1”標(biāo)記對象1的對象OE概念({1},({b,d},{a,c}))；

(4) 標(biāo)記正屬性O(shè)E概念和負(fù)屬性O(shè)E概念.比如，用“a+”標(biāo)記a的正屬性O(shè)E概念({4},({a,c},{b,d}))，用“a-”標(biāo)記a的負(fù)屬性O(shè)E概念({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 混合蘊(yùn)含規(guī)則

首先基于三支概念分析理論提出混合屬性蘊(yùn)含的定義，然后討論如何基于對象導(dǎo)出三支概念格線圖獲取混合屬性蘊(yùn)含，利用類似的方法對混合對象蘊(yùn)含展開研究.混合屬性蘊(yùn)含的獲取是基于對象導(dǎo)出三支概念格線圖，而混合對象蘊(yùn)含的獲取是基于屬性導(dǎo)出三支概念格線圖.

3.1 混合屬性蘊(yùn)含

三支概念分析下混合屬性蘊(yùn)含的定義如下.

定義6設(shè)(U,V,R)是一個(gè)形式背景，A,B,C,D?V，如果滿足“擁有A中所有屬性并且不擁有B中任意屬性的對象擁有C中所有屬性且不擁有D中任意屬性”，則稱混合屬性蘊(yùn)含(A,B)→(C,D)在(U,V,R)中成立.其中二元組(A,B)稱為(A,B)→(C,D)的前件，二元組(C,D)稱為后件.

根據(jù)混合屬性蘊(yùn)含的定義和OE算子的性質(zhì)，可得以下結(jié)論.

定理1設(shè)(U,V,R)是一個(gè)形式背景，A,B,C,D?V，混合屬性蘊(yùn)含(A,B)→(C,D)在(U,V,R)中成立的充分必要條件為：(A,B)·gt;?(C,D)·gt;.

例4混合屬性蘊(yùn)含(bxx55vz,?)→(,{c})在(U,V,R)(表1)中成立，因?yàn)?/p>

然而，混合屬性蘊(yùn)含({c},?)→({a},)在(U,V,R)中不成立，因?yàn)?/p>

根據(jù)混合屬性蘊(yùn)含的定義和對象導(dǎo)出三支概念格線圖的性質(zhì)，可得以下定理.

證明由OE概念之間偏序關(guān)系的性質(zhì)以及OE概念之間下確界的定義可知，

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

由定理2可知，根據(jù)對象導(dǎo)出三支概念格線圖可以判斷任意給定的混合屬性蘊(yùn)含是否成立.

3.2 混合對象蘊(yùn)含

當(dāng)具有相同屬性的對象被要求劃分為同一類時(shí)，對象蘊(yùn)含可以給出表示.然而，如果同時(shí)需要考慮不擁有某些屬性的對象，混合對象蘊(yùn)含將是更好的表達(dá)方式.接下來在三支概念分析理論的基礎(chǔ)上針對混合對象蘊(yùn)含進(jìn)行研究，混合對象蘊(yùn)含的定義如下.

定義7設(shè)(U,V,R)是一個(gè)形式背景，X,Y,Z,W?U，如果滿足“被X中所有對象擁有并且不被Y中任意對象所擁有的屬性，被Z中所有對象擁有且不被W中任意對象所擁有”，則稱混合對象蘊(yùn)含(X,Y)→(Z,W)在(U,V,R)中成立.其中二元組(X,Y)稱為(X,Y)→(Z,W)的前件，二元組(Z,W)稱為后件.

根據(jù)混合對象蘊(yùn)含和AE算子的定義，可得以下定理.

定理3設(shè)(U,V,R)是一個(gè)形式背景，X,Y,Z,W?U，混合對象蘊(yùn)含(X,Y)→(Z,W)在(U,V,R)中成立，當(dāng)且僅當(dāng)(X,Y)·gt;?(Z,W)·gt;.

根據(jù)混合對象蘊(yùn)含的定義和屬性導(dǎo)出三支概念格線圖的性質(zhì)，可得以下定理.

證明證明方法同定理2.

由定理4可知，根據(jù)屬性導(dǎo)出三支概念格線圖可以判斷任意給定的混合對象蘊(yùn)含是否成立.

4 結(jié)論

基于三支概念分析理論對混合蘊(yùn)含規(guī)則進(jìn)行研究，首先提出混合屬性蘊(yùn)含和混合對象蘊(yùn)含的定義，結(jié)合三支算子的性質(zhì)給出其成立的充分必要條件，然后提出三支概念格線圖的構(gòu)建方法并在此基礎(chǔ)上獲取混合蘊(yùn)含規(guī)則.三支概念格線圖為數(shù)據(jù)可視化提供了工具，其相對概念格提供了更多的信息，而混合屬性蘊(yùn)含可用于數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域，比如利用正、負(fù)關(guān)聯(lián)規(guī)則用于分類[19]以及文本聚類[20]等.混合蘊(yùn)含規(guī)則的獲取以及生成混合蘊(yùn)含規(guī)則的基是至關(guān)重要的，未來將針對此問題進(jìn)行深入的研究.

[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] 劉琳，錢婷，魏玲. 基于屬性導(dǎo)出三支概念格的決策背景規(guī)則提取[J]. 西北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 46(4): 481-487.

[7] 劉琳，魏玲，錢婷．決策形式背景中具有置信度的三支規(guī)則提取[J]．山東大學(xué)學(xué)報(bào)(理學(xué)版), 2017, 52(2):101-110.

[8] 汪文威，祁建軍. 三支概念的構(gòu)建算法[J]. 西安電子科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2017, 44(1): 77-82.

[9] 祁建軍,汪文威.多線程并行構(gòu)建三支概念[J]. 西安交通大學(xué)學(xué)報(bào)(自然科學(xué)版),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并行算法優(yōu)化實(shí)現(xiàn)[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 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] 曲守寧, 王欽, 鄒燕, 等. 基于關(guān)聯(lián)規(guī)則的文本聚類算法的研究[J]. 計(jì)算機(jī)應(yīng)用研究, 2008, 25(4): 986-988.

(責(zé)任編輯：孔 薇)

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

國家自然科學(xué)基金項(xiàng)目(11371014)；陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(2014JM8306)．

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

TP18

A

1671-6841(2017)04-0016-06