Building a Representation Context Based on Attribute Exploration Algorithms

Abstract

In this paper we discuss the problem of constructing the representation context of a pattern structure. First, we present a naive algorithm that computes the representation context of a pattern structure using an algorithm which is a variation of attribute exploration. Then, we study a different sampling technique for reducing the size of the representation context. Finally we show how to build such a reduced context and we discuss the possible ways of doing it.

Introduction

Formal Concept Analysis (FCA) has dealt with non binary data mainly in two different ways: one is by scaling [ 9 ] the original dataset into a formal context. This method has some drawbacks as it generates a formal context with larger dimensions than the original dataset and, depending on the method used to scale, some information may also be lost. Another way to deal with non binary data is by generalizing FCA into “pattern structures” [ 10,15 ], which allows handling complex data directly. Thus, instead of a analysing a binary relation between some objects and their attributes, it analyses a relation between objects and their representations, the values of which form a meet-semilattice. Pattern structures have proved useful for different unrelated tasks, such as, for instance to analyze gene expressions [ 14,13 ], compute database dependencies [ 1,2 ] or compute biclusters [ 6 ], or other structures data, like trees, intervals, graphs, sequences, fuzzy and heterogeneous data, among others [ 12 ].

Any pattern structure can be represented by an equivalent formal context, which is consequently called a “representation context” [ 10,4 ]. By equivalent we mean that there is a bijection between the intents in the representation context and the pattern-intents in the pattern structure. In fact, this means that both contain the same set of extents.

Pattern structures are difficult to calculate precisely because of the complex nature of the object representations they model. Often, pattern concept lattices are very large and their associated sets of pattern concepts are difficult to handle. In this article we tackle this problem by mining a reduced “representation context” of pattern structures by means of irreducible patterns (IPs) [ 7,11 ]. IPs act as a basis –in the linear-algebraic sense– of the space of patterns, i.e. each pattern can be represented as a linear combination of the join of a subset of IPs. In the standard FCA notation, IPs correspond to the intents of V-irreducible concepts. More specifically, we propose an algorithm that calculates the extents of a pattern structure while simultaneously calculating a small representation context. The later allows for a cheap calculation of most pattern extents and it is incrementally completed with samples obtained from the actual pattern structure. The algorithm is based on attribute exploration [ 8 ] (object exploration in this case) that instead of a domain-expert, uses an oracle to validate the question “is set X an extent in the pattern structure?”. In the negative case, the oracle should be able to sample a new attribute to add in the representation context which is heuristically selected to be an IP (or close to it).

We first present a naive algorithm based on NextClosure [ 8 ] and attribute exploration techniques. Then, we present an alternative way to “call the oracle” with a sampling strategy which strongly depends on the nature of the object descriptions. We show that the sampling strategy is able to obtain very small representation contexts, and as well, it sometimes generates with the highest probability the representation contexts with irreducible attributes only.

This work mainly relies on studies about the formalization of representation contexts such as [ 10 ] and [ 4 ], and on the book [ 8 ]. Moreover, a short version of this paper was published in the proceedings of the ICFCA 2019 Conference [ 5 ]. 2

Notation and Background

In the following we introduce some definitions needed for the development of this article. The notations used are based on [ 9 ]. A formal context (G, M, I) is a triple where G is a set of objects, M is a set of attributes and I ⊆ G × M is an incidence relation where (g, m) ∈ I denotes that “object g has the attribute m”. The derivation operators are denoted as 0 : ℘(G) → ℘(M) and 0 : ℘(M) → ℘(G).

A many-valued context M = (G, N, W, J) is a data table where, in addition to G and M, we define a set of values Wm for each attribute m ∈ M (where W = S Wm for all m ∈ M) such that m(g) = w denotes that “the value of the attribute m for the object g is w” (with w ∈ Wm). Additionally, in this document we will consider each Wm as an ordered set where Wim denotes the i-th element in the set. An example of a many-valued context can be found in Table 1 where a(r1) = 1, Wb = {1, 2} and Wb2 = 2.

The pattern structure framework is a generalization of FCA [ 10 ] where objects may have complex descriptions. A pattern structure is a triple (G, (D, u), δ) where G is a set of objects, (D, u) is a semi-lattice of complex object descriptions, and δ is a function that assigns to each object in G a description in D. The derivation operators for a pattern structure are denoted as (·) : G → D and (·) : D → G.

A ⊆ G ; A = l δ(g)

g∈A d ∈ D ; d = {g ∈ G | d v δ(g)}

Pattern structures come in different flavors depending on the nature of the representation for which they are intended. Regardless of the nature of data, any pattern structure can be represented with a formal context, as the next definition shows: Definition 1 ([ 10 ]). Let (G, (D, u), δ) be a pattern structure, and let (G, M, I) be a context such that M ⊆ D and (g, m) ∈ I ⇐⇒ m v δ(g).

If every intent of (G, (D, u), δ) is of the form

G X = l{d ∈ D | (∀x ∈ X)x v d} for some X ⊆ M (i.e. M is F-dense in (D, u)), then (G, M, I) is a “representation context” of (G, (D, u), δ)

The condition that M is F-dense in (D, u) means that any element in D can be represented (uniquely) as the meet of the filters of a set of descriptions X ⊆ M in (D, u).

Representation contexts yield concept lattices that are isomorphic to the pattern concept lattices of their corresponding pattern structures. Moreover, there is a bijection between the intents in the representation context and the pattern-intents in the pattern structure. For any pattern-intent d ∈ D in the pattern structure we have an intent X ⊆ M in the representation context such that d = F X and X =↓ d ∩ M where ↓ d is the ideal of d in (D, u). 3

Computing a Representation Context: a First and

Naive Approach

3.1

The NaiveRepContext Algorithm

We first present a simple and naive method for building a representation context from a given pattern structure. Algorithm 1 shows this method in the form of a procedure called NaiveRepContext. This procedure is based on the standard NextClosure algorithm [ 8 ], to which some changes –marked with an asterisk– have been performed. These changes represent the interaction of the algorithm with the oracle.

The algorithm receives as inputs a copy of a many-valued context M = (G, N, W, J) and implementations for the derivation operators (·) and (·) corresponding to the pattern structure (G, (D, u), δ) defined over M. To distinguish the attributes in the many-valued context from those in the representation context created by Algorithm 1, we will refer to N as a set of columns in the many-valued context.

The algorithm starts by building the representation context K. The set of objects is the same set of objects in the pattern structure, while the set of attributes and the incidence relation are initially empty. Line 12 checks whether a set of objects (B00) in the representation context is an extent in the pattern structure (B ). If this is the case, the algorithm continues executing NextClosure. Otherwise, the algorithm adds to the representation context a new attribute corresponding to the pattern associated to the mismatching closure. It also adds to the incidence relation the pairs object-attribute, i.e. (h, B ) as defined in line 14. Line 24 outputs the calculated representation context.

Algorithm 1 A Naive Calculation of the Representation Context.

Proposition 1.

Algorithm 1 computes a representation context (G, M, I) of (G, (D, u), δ). Proof. We show that (G, M, I) meets the conditions in Definition 1. Similarly to NextClosure, Algorithm 1 enumerates all closures –given an arbitrary closure operator– in lectic order. However, Algorithm 1 uses two different closure operators, namely the standard closure operator of FCA defined over the representation context under construction (·)00, and the one defined by the two derivation operators in the pattern structure, i.e. (·) and (·) . Both closure operators are made to coincide by the new instructions in the algorithm. When this is not the case (i.e. B00 6= B for a given B ⊆ G), a new attribute is added to the representation context in the shape of B . Additionally, the pair (h, B ) is added to the incidence relation of the representation context for all objects h ∈ B. This in turn ensures that B00 = B holds in the modified representation context.

A consequence of the equality B00 = B is that the set of extents in the representation context is the same as the set of extents in the pattern structure. This also means that there is a one-to-one correspondence between the intents in the representation context and the patterns in the pattern structure, i.e. for any extent B00 = B , the intent B000 = B0 corresponds to the pattern B = B (B000 = B0 and B = B are properties of the derivation operators [ 9 ]). Thus, we have that any element in D, which can be represented as B for an arbitrary B ⊆ G, is of the form F B0 or d{d ∈ D | (∀m ∈ B0)m v d}. Consequently, M is F-dense in (D, u) and (G, M, I) is an RC of the pattern structure (G, (D, u), δ). tu 3.2

An Example of Execution

Table 3 shows the execution trace of NaiveRepContext over an interval pattern structure defined over the many-valued formal context on Table 1. Columns in Table 3 are: row number, a candidate set B in Algorithm 1, its closure in the representation context, its closure in the pattern structure, the result of the test in line 12 of Algorithm 1, and the pattern-intent B . Notice that there are 26 entries in the last column of the table that correspond to the 26 different attributes in the resulting representation context in Table 4. The latter are enumerated in the order they appear in Table 3.

Examining the first row in Table 3, we observe that the algorithm initially calculates the closure of set {r7}. At this point the representation context is empty so the closure of {r7} corresponds exactly to G. However, using the pattern structure we find out that {r7} = {r7} (test B00 = B fails) and we need to add something to the representation context. Algorithms 1 adds to M the attribute corresponding to {r7} which is labelled as attribute d1 in the representation context of Table 4 (thus ensuring that {r7}00 = {r7})). The procedure is the same for the following sets in the lectic enumeration until we calculate the closure of {r3}.

Two important things occur at this point: Firstly, {r3} = {r3}. Secondly, there is enough information in the representation context so that {r3}00 = {r3} as well. Consequently, no new attribute is added to the representation context.

Let us discuss this example in more depth. The representation context at this point is conformed by the same elements in Table 4 truncated at column d10. At this point, we should observe that {r3} = F{r3}0 = F{d6, d8, d9, d10}.

Another important observation is that we do not really need to verify in the pattern structure that {r3} = {r3}00. Because closure is an extensive operation (B ⊆ B00 and B ⊆ B ) at any point in the execution of Algorithm 1 we have that B ⊆ B ⊆ B00. Thus, B = B00 =⇒ B = B . This is indeed quite important since, as shown in Table 3, usually B00 = B is true more often than not (in this example, 38 times out of 64). By avoiding the calculation of B within the pattern structure we can avoid the costly calculation of pattern similarities and subsumptions by means of the representation context.

Computing Smaller Representation Contexts

Extending the NaiveRepContext Algorithm with Sampling

Algorithm 1 is able to calculate the representation context of the interval pattern structure created for the many-valued context in Table 1 rather inefficiently since it creates a different attribute for almost every interval pattern in the pattern structure. As previously described, Algorithm 1 is able to avoid creating attributes for some interval patterns when there is enough information in the partial representation context. More formally, it does not include a new attribute d in the representation context if and only if there exists a set Y ⊆ M such that d = F Y or d = Tm∈Y m . Knowing this, we are interested in examining whether there is a way to calculate a smaller representation context given an interval pattern structure definition.

Table 6 shows the execution trace of Algorithm 1 over the interval pattern structure defined over Table 2. We can observe that the algorithm generates 14 different attributes in the representation context, one for each interval pattern concept except for the top and bottom concepts. Notice that this pattern structure contains 24 = 16 interval pattern concepts and since it has 4 objects, we can conclude that its associated concept lattice is Boolean.

This example is interesting because it is a worst-case scenario for Algorithm 1. In fact, it generated the largest possible representation context for the interval pattern structure derived from Table 2. Moreover, it verified each extent closure in the pattern structure. This example is even more interesting considering that for such an interval pattern structure there is a known smallest representation context which corresponds to a contranominal scale [ 8 ] that for this example would contain only 4 attributes as shown in Table 5.

To make matters worse, we can show that Algorithm 1 would behave the same for an interval pattern structure with an associated Boolean concept lattice of any size. Actually, this is a consequence of the lectic enumeration of object sets performed by Algorithm 1 which implies that whenever B0 ⊆ B1 (with B0, B1 closed sets in G) then, B0 is enumerated before B1. Since a pattern-intent B1 is not included in the representation context only when there exists a set Y ⊆ M such that Tm∈Y m = B1 we have that (∀m ∈ Y )B1 ⊆ m . Consequently, B1 would not be included in the representation context only when all m ∈ X had been already enumerated which cannot be the case because of lectic numeration.

B h[ 1, 1 ], [ 1, 1 ], [ 2, 2 ], [ 4, 4 ], [ 2, 2 ]i h[ 1, 1 ], [ 1, 1 ], [ 2, 2 ], [ 2, 2 ], [ 2, 2 ]i h[ 1, 1 ], [ 1, 1 ], [ 2, 2 ], [ 2, 4 ], [ 2, 2 ]i h[ 3, 3 ], [ 1, 1 ], [ 2, 2 ], [ 3, 3 ], [ 2, 2 ]i h[ 1, 3 ], [ 1, 1 ], [ 2, 2 ], [ 3, 4 ], [ 2, 2 ]i h[ 1, 3 ], [ 1, 1 ], [ 2, 2 ], [ 2, 3 ], [ 2, 2 ]i h[ 3, 3 ], [ 2, 2 ], [ 3, 3 ], [ 2, 2 ], [ 2, 2 ]i h[ 1, 3 ], [ 1, 2 ], [ 2, 3 ], [ 2, 4 ], [ 2, 2 ]i h[ 1, 3 ], [ 1, 2 ], [ 2, 3 ], [ 2, 2 ], [ 2, 2 ]i h[ 3, 3 ], [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 2, 2 ]i

h[ 1, 3 ], [ 1, 1 ], [ 2, 2 ], [ 2, 4 ], [ 2, 2 ]i h[ 1, 3 ], [ 1, 2 ], [ 2, 3 ], [ 2, 3 ], [ 2, 2 ]i

h[ 2, 2 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ]i h[ 1, 2 ], [ 1, 1 ], [ 1, 2 ], [ 1, 4 ], [ 1, 2 ]i h[ 1, 2 ], [ 1, 1 ], [ 1, 2 ], [ 1, 2 ], [ 1, 2 ]i h[ 2, 3 ], [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 2 ]i h[ 2, 3 ], [ 1, 2 ], [ 1, 3 ], [ 1, 2 ], [ 1, 2 ]i

h[ 1, 3 ], [ 1, 1 ], [ 1, 2 ], [ 1, 4 ], [ 1, 2 ]i h[ 1, 3 ], [ 1, 1 ], [ 1, 2 ], [ 1, 2 ], [ 1, 2 ]i h[ 1, 3 ], [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 2 ]i h[ 1, 3 ], [ 1, 2 ], [ 1, 3 ], [ 1, 2 ], [ 1, 2 ]i h[ 2, 3 ], [ 1, 2 ], [ 1, 3 ], [ 1, 3 ], [ 1, 2 ]i

h[ 1, 3 ], [ 1, 2 ], [ 1, 3 ], [ 1, 3 ], [ 1, 2 ]i h[ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ]i h[ 1, 1 ], [ 1, 1 ], [ 1, 2 ], [ 1, 4 ], [ 1, 2 ]i h[ 1, 2 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ], [ 1, 1 ]i sentation context. In this way we would maintain the F-dense in (D, u) property with a minimum number of attributes. Table 6 shows in gray those rows that represent the relevant attributes to add to the representation context. Adding only these four attributes would be enough to represent the set of interval pattern concepts. Nevertheless, algorithms that compute the irreducible attributes of a closure system have exponential complexity in the size of its formal context[ 3 ]. Instead, we resort to a sampling-based strategy to retrieve attributes with a large image in G. Our sampling method is based on picking large convex regions in the space. To achieve this, we use a many-valued context denoted as (G, N, W, J) to differentiate it from the sets in the representation context (G, M, I). Given a set B and its closure in the representation context B00 –which we know to be different from B – the goal of the sampling procedure is to find a set X such that B ⊆ (X ∩ B00). The sampling procedure starts by picking a random column in the manyvalued context n ∈ N. Then, we randomly pick a side to trim the ordered set Wn (left or right ) to generate a new set Wˆn. A candidate set X = {g ∈ G | n(g) ∈ Wˆn} is created and we check whether B ⊆ X. If so, we return X if and only if B00 6⊆ X. In a different case, we pick a random column from N and proceed with the same instructions. This is a basic description of the sampling algorithm described in Algorithm 3. Some details on the creation of Wˆn are left described only in the pseudocode.

Algorithm 3 is able to generate large convex regions by considering single dimensions of the space. It basically tries to answer the question: Which is the largest region in any dimension which contains set B? For example, let us try to sample an extent for the first row of Table 6 where B = {r4} and B00 = {r1, r2, r3, r4}. The many-valued context is showed in Table 2. Let us pick column b such that W b = {1, 2, 3, 4}. Next, we pick right to create Wˆb = {1, 2, 3}. The candidate set is then X1 = {r2, r3, r4} for which we have that B ⊆ X1 and B00 6⊆ X1 so we return X1 = {r2, r3, r4}.

We can observe that in the previous example {r2, r3, r4} corresponds to the image of an irreducible attribute in the representation context. Of course, this is a happy accident because we have made not-so-random decisions. True random decisions may lead to add reducible attributes into the representation context. However, since the random decisions are likely to pick large regions in the space, and thus attributes with a large image in G, they are likely to be irreducible attributes.

Algorithm 2 adapts a sampling method into the generation of the representation context. Line 14 calls the sampling procedure such as the one described in Algorithm 3. Line 13 has been changed for a while instruction instead of an if instruction. This is because in this case the closure B00 should converge to B by the addition of one or more attributes into the representation context. This convergence is ensured since in the worst case scenario Algorithm 3 returns B as an attribute for the representation context.

Let us finish the previous example by using Algorithm 2. We notice that with X1 = {r2, r3, r4} as the first object of the representation context we have that {r4}00 = {r2, r3, r4} which is again different from {r4} . Consequently, Algorithm 2 calls for a new sample which by the same procedure described could be X2 = {r1, r3, r4} (another happy accident). Notice that it cannot be again {r2, r3, r4} because of line 18 of Algorithm 3. Next, we have that {r4}00 = {r3, r4} calls for a new sample. This new sample could be X3 = {r1, r2, r4} which renders {r4}00 = {r4} . Algorithm 2 proceeds to calculate {r3}00 which in the current state of the representation context yields {r3, r4}. If the Sample procedure reAlgorithm 2 A General Algorithm for Computing a Representation Context. turns X4 = {r1, r2, r3} we have then that {r3}00 = {r3} . It should be noticed that at this point the representation context is complete w.r.t. the interval pattern structure. This is, any subsequent closure will be calculated in the representation context alone. Table 5 shows the contranominal scale corresponding to the representation context generated. 5

Conclusions

In this paper we have presented a sampling strategy in order to compute a smaller representation context for an interval pattern structure. We propose two algorithms to achieve such a computation, a first naive version based on object exploration, and a second improved version that uses a sampling oracle to quickly find irreducible patterns. These irreducible pattern can be considered the basis of a pattern structure. This paper is a first step towards the computation of minimal representation of a pattern structure by means of sampling techniques. Acknowledgments. This research work has been supported by the recognition of 2017SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya), and the grant TIN2017-89244-R from MINECO (Ministerio de Econom´ıa y Competitividad). Algorithm 3 An interval pattern extent sampler algorithm.

References

1. Jaume Baixeries , Mehdi Kaytoue, and Amedeo Napoli . Computing Similarity Dependencies with Pattern Structures . In Concept Lattices and their Applications , volume 1062 , pages 33 - 44 . CEUR Workshop Proceedings (ceur-ws. org) , 2013 .

2. Jaume Baixeries , Mehdi Kaytoue, and Amedeo Napoli . Characterizing Functional Dependencies in Formal Concept Analysis with Pattern Structures . Annals of Mathematics and Artificial Intelligence , 72 ( 1-2 ): 129 - 149 , 2014 .

3. Alexandre Bazin . Comparing algorithms for computing lower covers of implicationclosed sets . In Proceedings of the Thirteenth International Conference on Concept Lattices and Their Applications , Moscow, Russia, July 18-22 , 2016 ., pages 21 - 31 , 2016 .

4. Aleksey Buzmakov . Formal Concept Analysis and Pattern Structures for mining Structured Data . PhD thesis , University of Lorraine, Nancy, France, 2015 .

5. V´ıctor Codocedo, Jaume Baixeries, Mehdi Kaytoue, and Amedeo Napoli . Sampling Representation Contexts with Attribute Exploration . In Diana Cristea, Florence Le Ber, and Baris Sertkaya, editors, Proceedings of the 15th International Conference on Formal Concept Analysis (ICFCA), Lecture Notes in Computer Science 11511 , pages 307 - 314 . Springer, 2019 .

6. V´ ıctor Codocedo and Amedeo Napoli . Lattice-based biclustering using Partition Pattern Structures . In Proceedings of ECAI 2014 , volume 263 of Frontiers in Artificial Intelligence and Applications , pages 213 - 218 . IOS Press, 2014 .

7. Brian A. Davey and Hilary A. Priestley . Introduction to Lattices and Order. Cambridge University Press, Cambridge, UK, 1990 .

8. Benhard Ganter and Sergei Obiedkov . Conceptual Exploration . Springer, Berlin, 2016 .

9. Benhard Ganter and Rudolph Wille . Formal Concept Analysis . Springer, Berlin, 1999 .

10. Bernhard Ganter and Sergei O. Kuznetsov . Pattern Structures and Their Projections . In Proceedings of ICCS 2001, Lecture Notes in Computer Science 2120 , pages 129 - 142 . Springer, 2001 .

11. Michel Habib and Lhouari Nourine . Representation of lattices via set-colored posets . Discrete Applied Mathematics , 249 : 64 - 73 , 2018 .

12. Mehdi Kaytoue , V´ıctor Codocedo, Aleksey Buzmakov, Jaume Baixeries, Sergei O Kuznetsov, and Amedeo Napoli . Pattern Structures and Concept Lattices for Data Mining and Knowledge Processing . In Proceedings of ECML-PKDD 2015 (Part III) , volume 9286 of Lecture Notes in Computer Science, pages 227 - 231 . Springer, 2015 .

13. Mehdi Kaytoue , Sergei O. Kuznetsov , and Amedeo Napoli . Revisiting Numerical Pattern Mining with Formal Concept Analysis . In Toby Walsh, editor, Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011 ), pages 1342 - 1347 . IJCAI/AAAI, 2011 .

14. Mehdi Kaytoue , Sergei O. Kuznetsov , Amedeo Napoli, and S´ebastien Duplessis. Mining gene expression data with pattern structures in Formal Concept Analysis . Information Sciences , 181 ( 10 ): 1989 - 2001 , 2011 .

15. Sergei O. Kuznetsov . Pattern Structures for Analyzing Complex Data . In Hiroshi Sakai, Mihir K. Chakraborty , Aboul Ella Hassanien, Dominik Slezak, and William Zhu, editors, RSFDGrC , volume 5908 of Lecture Notes in Computer Science, pages 33 - 44 . Springer, 2009 .