Morphisms Between Pattern Structures and Their Impact on Concept Lattices

Abstract

We provide a general framework for pattern structures by investigating adjunctions between posets and their morphisms. Our special interest is the impact of pattern morphisms on the induced concept lattices. In particular we are interested in conditions which are sufficient for the induced residuated maps to be injective, surjective or bijective. One application is that every representation context of a pattern structure has a formal concept lattice that is induced by a certain pattern morphism.

Introduction

Pattern structures within the framework of formal concept analysis have been introduced in [3]. Since then they have turned out to be a useful tool for analysing various real-world applications (cf. [3–7]). Our paper extends the concept of representation contexts and interprets them via morphisms, closely related to o-projections as recently introduced and investigated in [2]. In [8], we disussed the meaning of projections of pattern structures, realizing the importance of residual projections. As a matter of fact, our generalization of representation contexts of pattern structures gives rise to residual projections.

Preliminaries

The fundamental order theoretic concepts of our paper are nicely presented in the book on Residuation Theory by T.S. Blythe and M.F. Janowitz (cf. [1]).

Definition 1 (Adjunction). Let P p P; ⁄q and L p L; ⁄q be posets; furthermore let f : P L and g : L P be maps. ( 1 ) The pair p f ; gq is an adjunction w.r.t. pP; Lq if f x ⁄ y is equivalent to x ⁄ gy for all x P P and y P L. In this case, we will refer to pP; L; f ; gq as a poset adjunction. ( 2 ) f is residuated from P to L if the preimage of a principal ideal in L under f is always a principal ideal in P, that is, for every y P L there exists x P P s.t.

f 1tt P L | t ⁄ yu t s P P | s ⁄ xu: ( 3 ) g is residual from L to P if the preimage of a principal filter in P under g is always a principal filter in L, that is, for every x P P there exists y P L s.t.

g 1ts P P | x ⁄ su t t P L | y ⁄ tu: ( 4 ) The dual of L is given by Lop p L; ¥q with ¥: tp x; tq P L L | t ⁄ xu. The pair p f ; gq is a Galois connection w.r.t. pP; Lq if p f ; gq is an adjunction w.r.t. pP; Lopq.

The following well-known facts are straightforward (cf. [1]).

Proposition 1. Let P p P; ⁄q and L p L; ⁄q be posets. ( 1 ) A map f : P L is residuated from P to L iff there exists a map g : L P s.t. p f ; gq is an adjunction w.r.t. pP; Lq. ( 2 ) A map g : L P is residual from L to P iff there exists a map f : P L s.t. p f ; gq is an adjunction w.r.t. pP; Lq. ( 3 ) If p f ; gq and ph; kq are adjunctions w.r.t. pP; Lq with f h or g k then f h and g k. ( 4 ) If f is a residuated map from P to L, then there exists a unique residual map f from L to P s.t. p f ; f q is an adjunction w.r.t. pP, Lq. In this case, f is called the residual map of f . ( 5 ) If g is a residual map from L to P, then there exists a unique residuated map g from P to L s.t. pg ; gq is an adjunction w.r.t. pP, Lq. In this case, g is called the residuated map of g. ( 6 ) A residuated map f from P to L is surjective iff f f idL iff f is injective. ( 7 ) A residuated map f from P to L is injective iff f f idL iff f is surjective.

Definition 2. Let P p P; ⁄q be a poset and T

P. Then

( 1 ) The restriction of P onto T is given by P|T : p T; ⁄ XpT T qq, which clearly is a poset too. ( 2 ) The canonical embedding of P|T into P is given by the map T P; t t. ( 3 ) T is a kernel system in P if the canonical embedding t of P|T into P is residuated.

In this case, the residual map j of t will also be called the residual map of T in P. The composition k : t j is referred to as the kernel operator associated with T in P. ( 4 ) Dually, T is a closure system in P if the cannonical embedding t of P|T into P is residual. In this case, the residuated map y of t will also be called the residuated map of T in P. The composition g : t y is referred to as the closure operator associated with T in P. ( 5 ) A map k : P P is a kernel operator on P if s ⁄ x is equivalent to s ⁄ kx for all s P kP and x P P.

Remark: In this case, kP forms a kernel system in P, the kernel operator of which is k. ( 6 ) Dually, a map g : P P is a closure operator on P if x ⁄ t is equivalent to gx ⁄ t for all x P P and t P gP.

Remark: In this case, jP forms a closure system in P, the closure operator of which is g.

The following known facts will be needed for the sequel (cf. [1]) .

Proposition 2. Let P p P; ⁄q and L p L; ⁄q be posets.

( 1 ) If f is a residuated map from P to L then f preserves all existing suprema in P, that is, if s P P is the supremum (least upper bound) of X P in P then f s is the supremum of f X in L.

In case P and L are complete lattices, the reverse holds too: If a map f from P to

L preserves all suprema, that is,

f psupP X q supL f X f or all X

P; then f is residuated. ( 2 ) If g is a residual map from L to P, then g preserves all existing infima in L, that is, if t P L is the infimum (greatest lower bound) of Y L in L then gt is the infimum of gY in P.

In case P and L are complete lattices, the reverse holds too: If a map g from L to P preserves all infima, that is, f pinfP Y q infL gY f or all Y

L; then g is residual. ( 3 ) For an adjunction p f ; gq w.r.t. pP; Lq the following hold: (a1) f is an isotone map from P to L. (a2) f g f f (a3) f P is a kernel system in L with f g as associated kernel operator on L. In particular, L P; y f gy is a residual map from L to L| f P. (b1) g is an isotone map from L to P. (b2) g f g g (b3) gL is a closure system in P with g f as associated closure operator on P. In particular, P gL; x g f x is a residuated map from P to P|gL.

Adjunctions and Their Concept Posets Definition 3. Let P : p P; S; s ; s q and Q : p Q; T; t; t q be poset adjunctions. Then a pair pa; b q forms a morphism from P to Q if pP; Q; a; a q and pS; T; b ; b q are poset adjunctions satisfying t a b s

Remark: This implies a tative:

t s b , that is, the following diagrams are commu

Next we illustrate the involved poset adjunctions:

a a b b s

P S a b t

t

Q

t T s

P S a b

Q T

t s

s Definition 4 (Concept Poset). For a poset adjunction P p P; S; s ; s q let BP : tp p; sq P P

S | s p s ^ s s pu denote the set of pformalq concepts in P . Then the concept poset of P is given by BP : p P

Sq | BP ; that is, pp0; s0q ⁄ p p1; s1q holds iff p0 ⁄ p1 iff s0 ⁄ s1, for all pp0; s0q; pp1; s1q P BP . If pp; sq is a formal concept in P then p is referred to as extent in P and s as intent in P . From [9] we point out Theorem 1: Theorem 1. Let pa; b q be a morphism from a poset adjunction P p P; S; s ; s q to a poset adjunction Q p Q; T; t; t q. Then

pBP ; BQ ; F ; F q is a poset adjunction for and

F : BP

BQ ; pp; sq p t b s; b sq F : BQ

BP ; pq; tq p

a q; s a qq: s

BP

BQ Theorem 2. Under the conditions of the previous theorem the following hold: ( 1 ) If a is surjective then F is surjective too. ( 2 ) If b is injective then F is injective too. ( 3 ) If a is surjective and b is injective then F is an isomorphism from BP to BQ .. Proof. ( 1 ) Assume that a is surjective, that is, a a idQ. Then for all pp; sq P BP , the second component of pF F qpp; sq is b s a q taa q tq s. This yields F F idBQ , that is, F is surjective. ( 2 ) The first component of pF F qpp; sq is a t b s t b b s t s p. Therefore, F F idBP , which yields F being injective. ( 3 ) If a is surjective and b is injective, than F and F are naturally inverse by ( 1 ) and ( 2 ), that is, F is an isomorphism from BP to BQ . 4

The Impact of Pattern Morphism on Concept Lattices Definition 5. A triple G p G; D; d q is a pattern setup if G is a set, D p D; q is a poset, and d : G D is a map. In case every subset of d G : t d g | g P Gu has an infimum in D, we will refer to G as pattern structure. Then the set

CG : t infD d X | X

Gu forms a closure system in D and furthermore CG :

D|CG forms a complete lattice.

If G p G; D; d q and H p H; E; eq each is a pattern setup, then a pair p f ; jq forms a pattern morphism from G to H if f : G H is a map and j is a residual map from D to E satisfying j d e f , that is, the following diagram is commutative: d In the sequel we show how our previous considerations apply to pattern structures. Theorem 3. Let p f ; jq be a pattern morphism from a pattern structure G p G; D; d q to a pattern structure H p H; E; eq.

To apply the previous theorem we give the following construction: f gives rise to an adjunction pa; a q between the power set lattices 2G : p 2G; q and 2H : p 2H ; q via and a : 2G 2H ; X

f X a : 2H 2G;Y f 1Y: Further let j denote the residuated map of j w.r.t. pE; Dq, that is, pE; D; j ; jq is a poset adjunction. Then, obviously, pDop; Eop; j; j q is a poset adjunction too.

For pattern structures the following operators are essential:

: 2G : D : 2H : E

D; X E; Z infD d X infE eZ 2G; d t g P G | d 2H ; e t h P H | e d gu ehu P p 2G; Dop; ; q Q p 2H ; Eop; ; q:

It now follows that pa; jq forms a morphism from the poset adjunction

to the poset adjunction

In particular, p f X q jpX q holds for all X

We receive the following diagram of adjunctions:

2G Dop 2G

Dop For the following we recall that the concept lattice of G is given by BG : BP and the concept lattice of H is BH : BQ .

Then Theorem 1 yields that the quadruple pBG ; BH ; F ; F q is an adjunction for a j a F j l 2H Eop 2H Eop and

F : BG

BH ; pX ; dq pp

jdq ; jdq F : BH

BG ; pZ; eq p f 1Z; p f 1Zq q: BG

BH

By Theorem 2 the following hold:

( 1 ) If f is surjective then F is surjective too. ( 2 ) If j is injective then F is injective too. ( 3 ) If f is surjective and j is injective then F is an isomorphism from BG to BH . Theorem 4. Let G p G; D; d q and H p H; E; eq be pattern structure. And let G pG; CG ; d q be the pattern structure induced by G via d : G CG , g d g. It follows BG BG . Further let p f ; jq be a pattern morphism from G to H . Then with the notation introduced in the previous theorem, the map F from BG to BH is residuated. If f is surjective then so is F , if j is injective then so is F . If f is surjective and j is injective then F is an isomorphism from BG to BH .

X X 2G CG

X d

X M d 2G 2M

X

X 2G CG 2G 2M Definition 6. The representation context of a pattern structure G p G; D; d q w.r.t. a subset M of D is given by KpG ; Mq : p G; M; Iq with I : tp g; mq P G M | m d gu. Theorem 5. Let G p G; D; d q be a pattern structure and let M be a subset of D. The pattern structure associated with the representation context KpG ; Mq is given by H : p G; 2M; eq with e : G 2M; g M d g where M d : t m P M | m du for all d P D.

In particular, the concept lattice of KpG ; Mq is given by BKpG ; Mq BH .

Using the notation from the previous theorem, pidG; jq is a pattern morphism from G to H for j : CG 2M; x M x. Furthermore, the map F from BG to BH BKpG ; Mq is a residuated surjection. In case M is join-dense w.r.t. CG (that is, j is injective), F is an isomorphism from BG to BKpG ; Mq.

Remark: Based on the paradigm of concept morphisms, the previous theorem extends and sheds new light on theorem 1 of [3]. We generalize the definition of representation context introduced in [3] by allowing an abitrary subset M of patterns of the underlying pattern structure G as attribute set of the representation context KpG ; Mq. It then turns out that KpG ; Mq has a formal concept lattice which is induced by a morphism on G . More explicitly, there is a morphism on G to the pattern structure of KpG ; Mq which induces a residuated surjection from the concept lattice of G to the concept lattice of KpG ; Mq. In case M is join-dense w.r.t. G , the morphism between the concept lattices is an isomorphism (see also Theorem 1 of [3]). Our extension of the concept of representation context gives rise to various constructions of o-projections (as introduced in [2]) on G .

id j id F j BG

BKpG ; Mq

References

1. T.S. Blyth , M.F. Janowitz ( 1972 ), Residuation Theory, Pergamon Press, pp. 1 - 382 .

2. A. Buzmakov , S. O. Kuznetsov , A. Napoli ( 2015 ) , Revisiting Pattern Structure Projections . Formal Concept Analysis. Lecture Notes in Artificial Intelligence (Springer) , Vol. 9113 , pp 200 - 215 .

3. B. Ganter , S. O. Kuznetsov ( 2001 ), Pattern Structures and Their Projections . Proc. 9th Int. Conf. on Conceptual Structures , ICCS01, G. Stumme and H. Delugach (Eds.). Lecture Notes in Artificial Intelligence (Springer) , Vol. 2120 , pp. 129 - 142 .

4. T. B. Kaiser , S. E. Schmidt ( 2011 ), Some remarks on the relation between annotated ordered sets and pattern structures . Pattern Recognition and Machine Intelligence. Lecture Notes in Computer Science (Springer), Vol. 6744 , pp 43 - 48 .

5. M. Kaytoue , S. O. Kuznetsov , A. Napoli , S. Duplessis ( 2011 ), Mining gene expression data with pattern structures in formal concept analysis . Information Sciences (Elsevier) , Vol. 181 , pp. 1989 - 2001 .

6. S. O. Kuznetsov ( 2009 ), Pattern structures for analyzing complex data . In H. Sakai et al. (Eds.). Proceedings of the 12th international conference on rough sets , fuzzy sets, data mining and granular computing (RSFDGrC09) . Lecture Notes in Artificial Intelligence (Springer) , Vol. 5908 , pp. 33 - 44 .

7. S. O. Kuznetsov ( 2013 ), Scalable Knowledge Discovery in Complex Data with Pattern Structures . In: P. Maji , A. Ghosh , M.N. Murty , K. Ghosh , S.K. Pal , (Eds.). Proc. 5th International Conference Pattern Recognition and Machine Intelligence (PReMI2013). Lecture Notes in Computer Science (Springer), Vol. 8251 , pp. 30 - 41 .

8. L. Lumpe , S. E. Schmidt ( 2015 ), A Note on Pattern Structures and Their Projections. Formal Concept Analysis. Lecture Notes in Artificial Intelligence (Springer) , Vol. 9113 , pp 145 - 150 .

9. L. Lumpe , S. E. Schmidt ( 2015 ), Pattern Structures and Their Morphisms . CLA 2015 , pp 171 - 179 .