APP下载

Characterization of Formal Concept Analysis for Complete Lattice in the Clarified Attribute Dual Context

2022-03-08WANRenxiaLIMeiMIAODuoqian

WAN Renxia,LI Mei*,MIAO Duoqian

(1.School of Mathematics and Information Science,North Minzu University,Yinchuan 750021,China;2.Department of Computer Science and Technology,Tongji University,Shanghai 201804,China)

Abstract:Formal concept analysis is an effective tool for data analysis and knowledge acquisition,and the three-way concept lattice is an extension of the concept lattice.In formal concept analysis,complete lattice has isomorphic relation with concept lattice,but not every complete lattice is isomorphic to three-way concept lattice.We study the properties of atoms,irreducible elements,com-plements and ∨-simplification law of concept lattice in the clarified attribute dual context,and discuss the isomorphism among com-plete lattice,negative concept lattice and three-way concept lattice.Within conditional constraints,we have produced a characteriza-tion transformation of complete lattice to concept lattice,negative concept lattice and three-way concept lattice.

Key words:formal concept analysis;complete lattice;concept lattice;three-way concept lattice;negative concept lattice

1 Introduction

In 1982,Wille proposed the formal concept analysis theory based on the concept description and hierarchical structure in philosophy[1].The concept lattice has become an effective tool for data analysis and processing as well as an effective method for mining associations.In recent years,formal concept analysis has been widely used in virtual machine scheduling[2],knowledge discovery[3-5],software engi-neering[6-7],data mining[8]and other fields.And,in different research fields,such as construction of con-cept lattices[9-11],reduction of concept lattices[12-16],and rule acquisition[17-20],scholars have extended the framework of formal concept analysis and proposed various types of formal concepts.Some researchers have also studied formal concept analysis from the perspective of granular computing.

Three-way decision theory has attracted exten-sive attention from scholars due to its good perfor-mance in information processing[21-30].Qi et al.[31]combined formal concept analysis with three-way decision and proposed three-way concept analysis.Li et al.[32-34]introduced a framework of three-way cognitive concept learning.Rodriguez-Jimenez et al.[35]showed that the lattice satisfying certain prop-erties could be obtained from some mixed formal contexts.Yu et al.[36]studied those complete lattices which can be represented by three-way concept lat-tices.Qian et al.[37]declared that concept lattice and three-way concept lattice were isomorphic in the dual context.Wei et al.[38]reviewed the re-search progress and related work about three-way concept analysis.

Wille[1]explored the basic theorem that every complete lattice was isomorphic to a concept lattice,but,Yu et al.[36]concluded that the complete lattice was not necessarily isomorphic to three-way con-cept lattice.In this paper,we investigate the rela-tionship between concept lattice and complete lat-tice in the clarified attribute dual context,and give the conditions that complete lattices are isomorphic to three concept lattices and negative concept lattic-es.Finally,we store the complete lattice successful-ly using Zhi's method[39].

2 Preliminaries

Definition 1[40]An order set V:(V,≤)is called a lattice,if for any two elements x and y in V,the supremum x∨y and the infimum x∧y always exist.Vis called a complete lattice,if the supremum∨V and the infimum ∧V exist for any subset X of V.

Every complete lattice V has a largest element,∨V called the unit element of the lattice,denoted by 1V.Dually,the smallest element0Vis called the ze-ro element.

Definition 2[40]If L is a lattice with least ele-ment 0.Then a∈L is called an atom if 0 is covered by a(i.e.0

Definition 3[40]Let L be a lattice.An ele-ment x∈L is join-irreducible,if(i) x≠0(in case L has a zero)(ii)x=a∨b implies x=a or x=b for all a,b∈L.

Dually,a meet-irreducible element is defined as following.

Let L be a lattice.An element x∈ L is meet-ir-reducible,if(i) x≠0(in case L has a zero)(ii)x=a∧b implies x=a and x=b for all a,b∈L.

We denote the set of join-irreducible elements of L by J(L)and the set of meet-irreducible ele-ments by M(L).

Let P be an ordered set and Q⊆P,then Q is called join-dense in P if for every element a∈P,there is a subset A of Q such that a=∨PA.Corre-spondingly,Q is called meet-dense in P if for every element a∈P,there is a subset A of Q such that a=∧PA.

Definition 4[9]A formal context(G,M,I)con-sists of two sets G and M and a relation I between G and M.The elements of Gare called the objects and the elements of M are called the attributes of the context.

In order to express that an object g is in a rela-tion I with an attribute m,we write g Im or(g,m)∈I and read it as "the object g has the attri-bute m".

For an object g∈G,we write g∗instead of{g}∗for the object intent{m∈M|gIm}of the objectg.Correspondingly,m∗:={g∈G|gIm}is the attribute extent of the attribute m.

We write OC(L)for the object concept(g∗∗,g∗)and AC(L)for the attribute concept(m∗,m∗∗).

For X⊆G and A⊆M,a pair of operators,∗:P(G)→P(M)and∗:P(M)→P(G),are defined by

If X,X1,X2⊆G are sets of objects and A,A1,A2⊆Mare sets of attributes,the following con-clusions hold[9]:

Given a formal context(G,M,I),a formal con-cept is defined to be a pair(X,A)of an object sub-set X⊆G and an attribute subset A⊆M,where X*=A and A*=X.Xis called the extension and A is called the intension of the concept(X,A).We write the set of the extensions and the set of intensions of all the concepts as LG(G,M,I)and LM(G,M,I),re-spectively.

It is easy to know that both(X**,X*)and(A*,A**)are formal concepts.

where Ic=(G×M)-I.

If X,X1,X2⊆G are sets of objects and A,A1,A2⊆Mare sets of attributes,the following con-clusions hold[41]:

Given a formal context(G,M,I),a concept in-duced by its negative operators is called a N-con-cept.

Definition 6[31]Let(G,M,I)be a binary infor-mation table.A pair[X,(A,B)]of an object subset X⊆G and two attribute subsets A,B⊆Mis called an object-induced three-way concept,for short,an OE-concept,of(G,M,I),if and only if X∗=(A,B)and(A,B)∗=X.All OE-concept form a complete lattice,which is called the object-induced three-way con-cept lattice of(G,M,I)and written as OEL(G,M,I).

Definition 7[9]A context(G,M,I)is called clarified,if for any objectsg,h∈G,g∗=h*it always follows that g=hand,correspondingly,m∗=n*im-plies m=n for all m,n∈M.

Definition 8[37]Let(G,M,I)be a formal con-text.If a*∩b∗=φ and a*∪b∗=G with a∈M,b∈M,then a is called as the dual attribute to b and denot-ed by b̂.

Proposition 1[9]If(G,M,I)is a formal con-text,∀(X,A)∈L,

Meet-irreducible elements are attribute con-cepts,whereas attribute concepts are not necessarily meet-irreducible elements,dually,join-irreducible el-ements are object concepts,whereas object concepts are not necessarily join-irreducible elements[9].

Lemma 1[9]If T is an index set and,for ev-ery t∈T,Xt⊆G is a set of objects,then

Proposition 2[9]The concept lattice L(G,M,I)is a complete lattice in which infimum and supre-mum are given by:

Theorem 1[37]If(G,M,I)is a clarified attri-bute dual context,|M|must be even.Where|M|represents the cardinality of the set.

Definition 9[35]Let L be a lattice.L satisfies the ∨-simplification law if,for all a1,a2,a3∈L.a1∨a2=a1∨a3implies a2=a3.

Definition 10[9]A context(G,M,I)is regular,if∀x∈G,x*≠φ,x∗≠M,and ∀a∈M,a*≠φ,a∗≠G.

Lemma 2[42]Let(G,M,I)be a formal con-text.∀a∈M,∀g∈G,then

Definition 11[40]If L is a finite lattice.For each l∈L,we define its opposite element as:

Lemma 3[35]If L is an arbitrary finite lattice.For all l∈L,

Definition 12[40]A lattice L with 0 is said to be pseudocomplemented if,for each a∈L,there ex-ists an element a′∈L such that,for all b∈L,a∧b=0⇔b≤a′,that is,

Definition 13 A lattice L with 0 is said to be∧-pseudocomplemented if,for each l∈M(L),there exists an element,such that,for all a∈L,

Definition 14 A lattice L with 0 is said to be dual ∧-pseudocomplemented if,for each l∈M(L),there exists an element lop∈M(L),such that,for all l̂∈ M(L),

We can specify lopas

Definition 15 A lattice L with 0,M(L)is closed with respect to pseudocomplement,if the set has a dual∧-pseudocomplemented of M(L).

Definition 16[40]Let L be a lattice with 0 and 1.For a∈L,we say b∈L is a complement of a,if a∧b=0 and a∨b=1.

“I think it is gone,” he said. But it was not gone; it was one of those bits of the looking-glass—that magic mirror, of which we have spoken—the ugly glass which made everything great and good appear small and ugly, while all that was wicked and bad became more visible, and every little fault could be plainly seen. Poor little Kay had also received a small grain in his heart, which very quickly turned to a lump of ice. He felt no more pain, but the glass was there still. “Why do you cry?” said he at last; “it makes you look ugly. There is nothing the matter with me now. Oh, see!” he cried suddenly, “that rose is worm-eaten, and this one is quite crooked15. After all they are ugly roses, just like the box in which they stand,” and then he kicked the boxes with his foot, and pulled off the two roses.

Definition 17[35]A lattice L is said to be∧-complemented if for all l∈M(L),we have that lopis a complement of l,i.e.lop∧l=0 and lop∨l=1.

Definition 18[40]If L is an ordered set,given one element l∈L,the up-set and down-set of l are[l)={x∈L|l≤x}and(l]={x∈L|x≤l},respectively.

In this paper,lAdenotes(l]∩A(L)and lMd e-notes[l)∩M(L).

Theorem 2[37]If(G,M,I)is a clarified attri-bute dual context,then

where Ic=(G×M)-I.

Theorem 3[37]Let(G,M,I)be a clarified attri-bute dual context,then

Definition 19[40]Let P and Q be ordered sets.A map φ:P→Q is said to be

(1)order-preserving if x≤ y in P implies

(2)an order-embedding if x≤ y in P if and only if φ(x)≤φ(y)in Q;

(3)An order-isomorphism if it is an order-em-bedding which maps P onto Q;

3 Characterizing of Concept Lattices

Proposition 4 Let(G,M,I)be a clarified attri-bute dual context,we have the following properties:

Proof

(4)From(1),∀g∈G,(g**,g*)=(g,g*)obvious-ly holds.

Proposition 5 If(G,M,I)is a clarified attri-bute dual context,J(L)=OC(L).

Proof Since join-irreducible elements are ob-ject concepts,whereas object concepts are not neces-sarily join-irreducible elements[8],then

Now,let's prove that OC(L)⊆J(L).

And,according to Proposition 4,we then have{h∈G|g*⊂h*}=φ.Then,according to Lemma 2,

holds.Therefore,

From Proposition 4,we can see that J(L)={(g,g*)|g∈G}.

Proposition 6 If(G,M,I)is a clarified attribute dual context,we have A(L)={(g,g*)|g∈G}.

Proof Fixed,g0∈G,if(X,A)is a concept such that(φ,M)<(X,A)≤ (g0,g0∗)which implies

According to the Definition 2,atoms are join-irreducible elements.By Proposition 5 and Proposi-tion 6,we can easily come to the following Lemma:

Lemma 4 If(G,M,I)is a clarified attribute dual context,then J(L)=A(L).

Lemma 4 and Proposition 5 show that all atoms and join-irreducible elements of concept lattice are object concepts.

Proposition 7 If(G,M,I)is a clarified attri-bute dual context,then(L,≤)satisfies ∨-simplifica-tion law.

Proof Assume there are three concepts a1=(X1,A),a2=(X2,B),a3=(X3,C),and a1∨a2=a1∨a3,whereas a2≠a3.

From formula(2),we can know

From equation a1∨a2=a1∨a3,we have

From Lemma 4,we know

Therefore,the theorem holds.

Then dually,whether the attribute concepts(m*,m**)are meet-irreducible?To clarify the ques-tion,we illustrate it through Example 1.

Example 1[36]If(G,M,I)is a formal context,G={1,2,3,4},M={a,b,c,d},details of L are shown in Table 1 and Fig.1..

Table 1 Formal context(G,M,I)

Table 2 Formal context(G,M,I)

Fig.1 L(G,M,I)in Example 3.1

We can get the following meet-irreducible ele-ments of the concept lattice:

However,(1,acde)=(d*,d**)is not always meet-irreducible element.

Example 2 If(G,M,I)is a clarified attribute dual context,details of L are shown in Table 2 and Fig.2.

Fig.2 L(G,M,I)in Example 3.2

We can easily have

Example 2 shows that there are special cases in which the statement“the attribute concepts are meet-irreducible in clarified attribute dual context”is valid,then,under what circumstance this state-ment is always true?

Proposition 8 If K=(G,M,I)is a clarified attri-bute dual context,M(L)={(m*,m**)|m∈M}.

Proof Since meet-irreducible elements are at-tribute concepts,whereas attribute concepts are not necessarily meet-irreducible elements[8],then

i)if{X ∈LG(K)|m*⊂X}={G},∀m∈M.

Since K=(G,M,I)is a clarified attribute dual context and by Definition 10,we have(G,M,I)is regular,thus

ii)if

which means that{a∈M|m*⊂X}≠φ.By formula(1)and formula(3),we know

we have∃a∈M,m*=a*.

If(a*,a**)is not a meet-irreducible element,by Definition 7,we have m*=a*⇒m=a.∀X,Y∈LG(K),m*=X∩Y,thus

By the formula(1)and formula(3),then

By the formular(8)and(9),hence

It contradicts with m*=X∩Y.Then,

According to Lemma 2,we have

By the formular(7)and(10),therefore M(L)=AC(L)holds.

Now,we investigate the relationship between m and m̂.

Lemma 5 Let(G,M,I)be a clarified attribute dual context,then ∀m∈M,(m*,m**)and(m̂*,m̂**)are both complemented.

Proof Since m*∩m̂*=φ and m∗∪m̂∗=G,we then have

Proposition 9 Let K=(G,M,I)be a clarified attribute dual context.If the pseudocomplement of l∈M(L)exists,then

(1)lop={l̂∈ M(L)|l̂∧ l=0},

(2)M(L)is closed with respect to pseudocom-plement.

Proof (1)By Proposition 8,AC(L)=M(L),we consider

By Proposition 5 and Lemma 3,the equality lop=∨{x∈A(L)|x∉lA}holds.

By Lemma 4,we have

Since m*∩m̂*=φ and m∗∪m̂∗=G,by Lemma 5 and Definition 13,we have

(2)By the definition of ∧-pseudocomplement and Definition 15,this conclusion is obvious.

Proposition 10 Let K=(G,M,I)be a clarified attribute dual context,if(X,A)∈M(L),then the pseudocomplement of(X,A)is a ∧-complement.

Proof Since it follows from Proposition 9,Definition 16,Lemma 5 and Definition 17 holds.

Theorem 4 Let L be a complete lattice,if L satisfies the following properties:

(1)A(L)=J(L).

(2)L fits ∨-simplification law.

(3)M(L)is closed with respect to pseudocom-plement.

Then the complete lattice L is isomorphic to concept lattice B(K)in clarified attribute dual con-text.

Proof In the clarified attribute dual context

there is a mapping:

We will prove:

1)the mapping h is well defined,i.e.h(l)is a concept in the lattice B(K);

2)his an order-embedding;

3)his bijection.

lM={m∈M(L)|g≤m,∀g∈lA}.Due to the Defi-nition of lMand lA,transitivity of≤,hence

is obvious.

If m∈M(L),then we have g≤m,∀g∈lAand A(L)=J(L),we then have

1b)We prove that lA=(lM)∗holds.

lA={g∈J(L)|g≤m,∀m∈lM},i.e.any atomg satisfies g≤l if and only if g≤m,∀m∈lM.

If g≤m,∀m∈lM,by transitivity,then g≤∧lM=l.

2) ∀l1,l2∈L,if l1≤l2,by Definition 18,then l1A≤l2A,we have h(l1)≤h(l2).∀l1,l2∈L,if h(l1)≤h(l2),this means l1A≤l2A,then

Thus,his an order-embedding.

3)To prove that h is a bijection.

Since the lattice L fits ∨-simplification law,if for all l1,l2,l3∈L,l1∨l2=l1∨l3implies l2=l3,by Definition 18,which yields

We then have

That is clarified.

where l,lop∈M(L).

Since A(L)=J(L),we then have

If h(l1)=h(l2),and since A(L)=J(L)and by the formular(11),then

Therefore,his injective.

Conversely,h(l)≤ (X,Y),if m∈Y=X∗,m∈M(L),then x≤m,∀x∈X,therefore,l≤m,i.e.m∈lM.

Referring to Theorem 2,Theorem 3 and Theo-rem 4,we can get the following theorem.

Theorem 5 Let L be a complete lattice,if L satisfies the following properties:

(1)A(L)=J(L).

(2)L fits ∨ -simplification law.

(3)M(L)is closed with respect to pseudocom-plement.

Then,the complete lattice L,the negative con-cept lattice of B(K)and three-way concept lattice of B(K)are isomorphic to each other in clarified attri-bute dual context.

4 Conclusion

We study atoms,join-irreducible elements,meet-irreducible elements and dual complement ele-ments in clarified attribute dual context,and con-clude that the complete lattice with some certain properties will be isomorphic to the negative con-cept lattice and three-way concept.

In addition,Zhi et al.[39]proposed a complete lattice storage method based on the formal concept analysis theory,however,this method is not effec-tive for storing three-way concept lattices.In this paper,we construct an isomorphic bridge between complete lattice and three-way concept lattice,which can provide the theoretical support for the Zhi's method to store three-way concept lattices.