Formal Concept Analysis (FCA) is a new and rich emerging discipline, and it provides ecient techniques and methods for ecient data analysis under the idea of attributes. The main tool used in this area is the Concept Lattice also named Galois Lattice or Maximal Rectangle Lattice. A naive way to generate the Concept Lattice is by enumeration of each cluster of attributes. Unfortunately the numbers of clusters under the inclusion attribute relation has an exponential upper bound. In this work, we present a novel algorithm, PIRA (PIRA is a Recursive Acronym), for computing Concept Lattices in an elegant way. This task is achieved through the relation between maximal height and width rectangles, and maximal anti-chains. Then, using a dendritical neural network is possible to identify the maximal anti-chains in the lattice structure by means of maximal height or width rectangles.
Formal Concept Analysis (FCA) refers to a mathematized and formal
humancentered way to analyze data. It can be described as an ontology-based Lattice
Theory. This theory describes ways of visualizing patterns, generate implications,
and representing generalizations and dependencies [
The Concept Lattice is mainly used to represent and describe hierarchies
between data clusters (formal concepts or classes), which are inherent in the
perceived information. A formal concept can be regarded also as a data cluster,
in which certain attributes are all shared by a set of objects. The Concept Lattice
is the main subject of the theory of FCA, and it was rst introduced in the early
eighties by Rudolf Wille [
In this work, we present a Morphological Neural Network based method to generate the Concept Lattice. This batch method is capable of generating the Hasse diagram, and it is a bottom-up generation algorithm. With that in mind, this work is organized as follows. Section 2 is an elementary description of FCA Theory. Next, section 3 is a short introduction on how the Single Lattice Layer Perceptron (SLLP) works. In section 4, a description on how to compute the Maximal Rectangles is given. In this section, we also dene a link between SLLP and the design of a classier for maximal anti-chains search. Section 5 shows a comparison between PIRA and other known algorithms. 2 2.1
First, it is necessary to dene the concept of a formal context [
In order to dene formal concepts of the formal context (G,M,I), it is necessary to dene two derivation operators, named Galois connectors.
Denition 2.
A0 := {m ∈ M | (g, m) ∈ I, ∀g ∈ A}
B0 := {g ∈ G | (g, m) ∈ I, ∀m ∈ B} These two derivation operators satisfy the following three conditions over arbitrary subsets A1, A2 ⊆ G and B1, B2 ⊆ M : 1. A1 ⊆ A2 then A02 ⊆ A01 dually B1 ⊆ B2 then B20 ⊆ B10 2. A1 ⊆ A010 and A01 = A0100 dually B1 ⊆ B100 and B10 = B1000 3. A1 ⊆ B10 ⇐⇒ B1 ⊆ A01 Next, the denition of a formal concept idea, which represents the building unit of FCA.
Denition 3. Let K be a formal context, K := (G, M, I). A formal concept C of K is dened as a pair C = (A, B), A ⊆ G and B ⊆ M , where the following conditions are satised, A = B0 and A0 = B, where A is named the extent and B is named the intent of the formal concept (A, B).
Next, we will show some useful notions from Lattice Theory [
Formal Concepts can be partially ordered by inclusion. And for any pair Ci, Cj have a unique greatest lower bound and a unique least upper bound. Then, the set of all formal concept in K, ordered by inclusion, is known as a Concept Lattice. Next denition links some denitions with the Formal Concept notion. Denition 5. (Rectangles in K). Let A ∈ G and B ∈ M , a rectangle in K is a pair (A, B) such that A × B ⊆ I .
Given the set of Rectangles in K, a special kind of rectangles are dened as follows: Denition 6. (Maximal Rectangles). A rectangle (A1, B1) is maximal if and only if there does not exist another valid rectangle (A2, B2) in K such that A1 ⊆ A2 or B1 ⊆ B2 .
From here, we have the formal concept as a maximal rectangle.
Theorem 1. (A, B) is a formal concept of K if and only if (A, B) is a maximal rectangle in K.
Now, the following denitions are going to be useful for the proposed bottom-up approach of FCA generation.
Denition 7. Let K := (G, M, I) and A ⊆ G. A is said to be an object derivative anti-chain set if and only if A01 * A02 and A02 * A01 for any two distinct A1, A2 ∈ A. Dually, for B ⊂ M nd B10 * B20 for any two distinct B10, B20 in B.
We will denote as D a derivative anti-chain and as A(K) the set of all antichains in K. All sets in which the super/subconcept order is not satised for any distinct elements of the set is called anti-chain set.
Denition 8. D+ is a maximal derivative anti-chain i there does not exist other D ∈ A(K) such that D ⊃ D+. There exists a maximal derivative antichain for objects and one for attributes.
Finally, we use a simple upward closed set denition.
Denition 9. Upward closed set. Let (L, ≤) be a poset P . A set S ⊆ L is said to be upward closed if ∀x, y ∈ S with y ≥ x implies that y ∈ S.
Using these denitions of anti-chains, maximal rectangles and upward closed set, it is possible to device a bottom-up approach by means of dendritic neuronal networks.
Articial Neural Networks (ANN ) are models of learning and automatic
processing inspired by the nervous system. The features of ANN make them quite
suitable for applications where there is no prior pattern that can be identied,
and there is only a basic set of input examples (previously classied or not).
They are also highly robust to noise, failure of elements in the ANN, and,
nally, they are parallelizable. As we said early, our work is related with LBNN,
which is also considered an Articial Neural Network, and are inspired in recent
advances in the neurobiology and biophysics of neural computation (author?)
[
The theory of LBNN is actively used in classication [
In SLLP, a set of n input neurons N1, . . . , Nn accepts input x = (x1, ..., xn) ∈
Rn. An input neuron provides information through axonal terminals to the
dendritic trees of output neurons. A set of O output neurons is represented by
O1, ..., Om. The weight of an axonal terminal of neuron Ni connected to the kth
dendrite of the Oj output neuron is denoted by wi`jk, in which, the superscript
` ∈ {0, 1} represents an excitatory ` = 1 or a inhibitory ` = 0 input to the
dendrite. The kth dendrite of Oj will respond to the total value received from
the N input neurons set, and it will accept or reject the given input. Dendrite
computation is the most important operation in LBNN. The following equation
τkj (x), from SLLP, corresponds to the computation of the kth dendrite of the jst
output neuron[
τkj (x) = pjk ^
^ (−1)1−`(xi + wi`jk) i∈I(k) `∈L
Where x is the input value of neurons N1, ..., Nn and xi is the the value of
the input neuron Ni. I(k) ⊆ 1, ..., n represents the set of all input neurons with
synaptic connection on the kth dendrite of Oj . The number of terminal axonal
bers on Ni that synapse on a dendrite of Oj is at most two, since `(i) ⊆ {0, 1}
. Finally, the last involved element is pjk ∈ {−1, 1} and it denotes the excitatory
(pjk = 1) or inhibitory (pjk = =1) response of the kth dendrite of Oj to the
received input. All the values τkj (x) are passed to the neuron cell body. The
value computation of Oj is a function that computes all its dendrites values.
The total value received by Oj is given by[
Kj _ τkj (x) k=1
In this SLLP model, Kj is the set of all dendrites of Oj , pj = ±1 represents the response of the cell body to the received input vector. At this point, we know that pj = 1 means that the input is accepted and pj = =1 means that the cell body rejects the received input vector. The last statement related with Oj correspond to an activation function f , namely yj = f [τ j (x)].
f [τ j (x)] = (1 ⇐⇒ τ (x) ≥ 0
0 ⇐⇒ τ (x) < 0
As, we mention early, dendrites congurations is computed using a training
set. For this, they use merge and elimination methods [
In PIRA-LBNN model for nding upward-closed set elements, a set of binary patterns are represented by G0. Thus, the binary representation of a formal context is itself a set of patterns, in which the derivative of each object is an element x ∈ G0. Then, we can dene each element x = (x1, ..., xn) ∈ G0 as a binary vector. This allows us to dene a simple class classication rule to nd maximal rectangles, and in an equivalent way the maximal anti-chains.
In PIRA algorithm we search all the rectangles with maximum width or height from each formal concept founded. There are two ways to achieve our goal. It means that ` = 1 or ` = 0 depending on whether it is calculating, a supremum or an inmum, by using excitatory or inhibitory dendrites. Thus, pjk is also a constant, pjk = 1 or pjk = −1 and it denotes the excitatory or inhibitory response of the kth dendrite of Mj to the received input, and another remarkable statement is the fact that we only need to connect zeros as axonal branches. The simplest way to compute the value of the kth dendrite derived from the SLLP equations, is: τkj (x) =
_ (xi) i∈I(k)
This equation, where τkj (x) is the value of the computation of the kth dendrite of the jth output neuron given a input x, I(k) ⊆ {1, ..., n} is the set of input neurons with terminal bers that synapse the kth dendrite of our output neuron. We realize that all weights wi`jk are equal to zero, this is, for our upward closed set classier, we only need to store zero values from the input patterns in the training step. Our goal is that the output of our classication neuron be x ∈ C1 (1) (2)
INPUT : NeuralNetwork P , P a t t e r n x OUTPUT: Updated P
D e n d r i t e k = addNewDendrite (P) FOR EACH element i n x
IF g e t V a l u e ( element ) = 0 i = g e t P o s i t i o n ( element ) addAxonalBranch ( k , i )
END
END END if the input x ∈ D+. The training step is to nd the set D+. This is achieved by processing elements from higher to lower cardinality,
Specically, each dendrite k corresponds with one maximal antichain intent to be tested, I(k) is the incidence set of positions where the value of the maximal rectangle is zero for the pattern represented by the k dendrite. We get the state value of Mj computing the minimum value of all it’s dendrites. Again, as the SLLP, each τkj(x) is computed, and it is passed to the cell body of Mj. Then we can get the total value received by our output neuron as follows: τ j(x) = ^ τkj(x) (3) We realize that the activation function is not required since f [τ j(x)] = τ j(x) where τ j(x) = 1 if x y for all y ∈ C1 and τ j(x) = 0 if x ≤ y for some y ∈ C1. As we mentioned above x is a maximal rectangles if and only if x y and y x for all y ∈ C1. Using the previous statement we can ensure that half of the work is done, and the second test, y x, will be performed by processing data in a particular order. In our case, we use cardinality order ensuring that each new computed row is not a superset of the previously computed rows.
As we said before, the idea is to use our LBNN structure to classify maximal rectangles. When we start computing a formal concept, our structure is empty, this means there are not dendrites or axonal connections. So, the rst step is to add each element with the maximal cardinality as a pattern to learn. Algorithm 1 shows how an element is added to our LBNN for maximal rectangles learning. First, algorithm 1 receives as parameter the LBNN which is being trained and a binary vector. As we will see below, this binary vector has been proven as an antichain element. Algorithm 1, rst grows a new dendrite kth in our output neuron Oj. Every column in x is checked, if that property is not contained by the object x, then an axonal branch grows from the i position of the input neuron set to the new dendrite. This operation is represented by addAxonalBranch calling. We can assure that we will not misclassify formal concepts in the processed context. The algorithm 2 shows how to compute the Concept Lattice by computing Maximal Antichain Sets recursively.
ELSE add a Link from p r e v i o u s l y c r e a t e d Rectangle i n
Global_Maximal_Rectangles to K−Infimum
INPUT : B i n a r y C o n t e x t (G,M, I ) OUTPUT: L a t t i c e L Step 1 : Get Maximum and Infimum e l e m e n t s .
FormalConcept max = getMax (G,M, I ) FormalConcept min = getMin (G,M, I ) addConcept ( L , max ) , addConcept ( L , min ) STEP 2 : Get maximal R e c t a n g l e s From min
MaxRectangles = Compute Maximal R e c t a n g l e s with :
G/min . e x t e n t , min . i n t e n t , I −Proj , max , min ,
L
In algorithm 2, the rst step creates a new dendritic neural network. It is initialized with one output neuron, n = |intent| and k = 0, where the number of input neurons is n, and each input neuron represents one attribute element in M . The second step is used to get the G0 set ordered by attribute cardinality. Next, in a third step, if the maximal cardinality of the elements in G’ is equal to the Supremum intent cardinality, it adds a link between Supremum and Inmum, and stops. Otherwise, it adds all the elements in G’ with the maximal cardinality, to the dendritical neural network structure. Those elements are maximal rectangles in the given binary context. The fourth step is used to check the remaining elements. If an element derivative does not exist already, as an intent, and the evaluation 3 says that it is a maximal rectangle, then, it adds the object and its derivative as a new maximal rectangle. Otherwise, if the element derivative already exists, it is added to the previously formal concept as its extent. In the last step, it processes each maximal rectangle that has been found. If that element is already contained in the lattice, it adds a link between Inmum and the previous element created in the lattice. Otherwise, it adds that link and processes that formal concept recursively. Then, it adds this new element to the lattice structure.
At this point, it computes all the concepts given by the binary context, but
B(K) cardinality is bounded by an exponential complexity. A simple way to
avoid this issue is to use a Binary Tree to store and recover all elements in B(K).
Basically, this binary tree works as a hash function using the concept of intent
in their binary representation. Then, it searches, nds and adds any intent in
|M | steps. In addition, the processing order enables us to generate the edges of
the Hasse diagram without additional computing steps. Therefore, the process
of generating the concept lattice and Hasse diagram presented in this paper has
an expected polynomial delay time [
As shown in [
Figure 1 shows the execution time behavior for a formal context with 10% density and 100 attributes. Here, the V-axis represent the running time of each algorithm in ms, and the H-axis the total number of objects under constant number of attributes. The test was performed by increasing the number of objects from one thousand to twenty thousand, with a random distribution and 10% of density.
We can verify that Bordat algorithm and our algorithm have the best performance when the number of objects increase with respect to the attributes.
Execution time when the number of objects grows from 1000 to 20000, with 100 attributes and 10% of density.
Execution time when the number of attributes from 10 to 100 with 1000 objects and 10% density case.
Figure 2 shows the increase in execution time when the number of attributes increases. All datasets for this test has a 10% density and 1000 objects, and the number of attributes is increasing from ten to one hundred, and, the number of formal concepts is growing too. Here we can notice that Bordat and Dendritical algorithms, are faster than Godin, Nourrine and Valtchev algorithms. We can also notice that Dendritical execution time behavior is faster when the number of objects grows.
Figure 3 shows the increase in execution time when the density percentage becomes higher. All datasets has 1000 objects and 100 attributes and when the density grows the number of formal concepts grows too. As we mention, density is mainly the percentage of attributes for all the objects in the formal context.
Here, we notice that when the density grows Dendritical is closer and even faster than the other algorithms. Figure 4 shows running time for zero diagonal contexts where |G| = |M| and yields the complete lattice, which means 2|M| formal concepts. In this kind of formal contexts, we can see a clear running time superiority of the dendritical algorithm. Finally, table 1 shows some examples of time complexity at each algorithm step. No. Obj No. Att Density Concepts Query Time Ordering Dendritical Total 1000 36 17 8377 722ms 20ms 49ms 791ms 1000 49 14 14190 924ms 67ms 101ms 1092ms 1000 81 11 26065 1853ms 124ms 201ms 2178ms Algorithms time when density becomes higher and the number of attributes become lower. Those tests shows the increase in execution when attributes and I ⊆ G × M are modied. 6
In this paper, we presented an algorithm based on the main idea of maximal rectangles, using the cardinality notion and the dendritical classier. We have also compared it with some known algorithms for the construction of Concept Lattices.
From the tests presented in this paper, we can see that as the number of objects grows, our algorithm time execution is higher than Bordat or other methods, but it could be a better choice when the density or the number of attributes is high. Also, the results shows a good performance for the M × M contexts in the worst case scenario, which demonstrates the feasibility of our algorithm on some kinds of datsets.