=Paper=
{{Paper
|id=Vol-1252/cla2014_submission_33
|storemode=property
|title=A Generalized Framework to Consider Positive and Negative Attributes in Formal Concept Analysis
|pdfUrl=https://ceur-ws.org/Vol-1252/cla2014_submission_33.pdf
|volume=Vol-1252
|dblpUrl=https://dblp.org/rec/conf/cla/Rodriguez-JimenezCEM14
}}
==A Generalized Framework to Consider Positive and Negative Attributes in Formal Concept Analysis==
https://ceur-ws.org/Vol-1252/cla2014_submission_33.pdf
A generalized framework to consider positive
and negative attributes in formal concept
analysis.
J. M. Rodriguez-Jimenez, P. Cordero, M. Enciso and A. Mora
Universidad de Málaga, Andalucı́a Tech, Spain.
{pcordero,enciso}@uma.es
{amora,jmrodriguez}@ctima.uma.es
Abstract. In Formal Concept Analysis the classical formal context is
analized taking into account only the positive information, i.e. the pres-
ence of a property in an object. Nevertheless, the non presence of a prop-
erty in an object also provides a significant knowledge which can only
be partially considered with the classical approach. In this work we have
modified the derivation operators to allow the treatment of both, positive
and negative attributes which come from respectively, the presence and
absence of the properties. In this work we define the new operators and
we prove that they are a Galois connection. Finally, we have also studied
the correspondence between the formal context in the new framework
and the extended concept lattice, providing new interesting properties.
1 Introduction
Data analysis of information is a well established discipline with tools and tech-
niques well developed to challenge the identification of hide patterns in the data.
Data mining, and general Knowledge Discovering, helps in the decision mak-
ing process using pattern recognition, clustering, association and classification
methods. One of the popular approaches used to extract knowledge is mining
the patterns of the data expressed as implications (functional dependencies in
database community) or association rules.
Traditionally, implications and similar notions have been built using the posi-
tive information, i.e. information induced by the presence of attributes in objects.
In Manilla et al. [6] an extended framework for enriched rules was introduced,
considering negation, conjunction and disjunction. Rules with negated attributes
were also considered in [1]: “if we buy caviar, then we do not buy canned tuna”.
In the framework of formal concept analysis, some authors have proposed the
mining of implications with positive and negative attributes from the apposition
of the context and its negation (K|K) [2, 4]. Working with (K|K) conduits to
a huge exponential problem and also as R. Missaoui et.al. shown in [9] real
applications use to have sparse data in the context K whereas dense data in K
(or viceversa), and therefore “generate a huge set of candidate itemsets and a
tremendous set of uninteresting rules”.
2 Rodriguez-Jimenez et al.
R. Missaoui et al. [7, 8] propose the mining from a formal context K of
a subset of all mixed implications, i.e. implication with positive and negative
attributes, representing the presence and absence of properties. As far as we
know, the approach of these authors uses, for first time in this problem, a set of
inference rules to manage negative attributes.
In [11] we followed the line proposed by Missaoui and presented an algo-
rithm, based on the NextClosure algorithm, that allows to obtain mixed impli-
cations. The proposed algorithm returns a feasible and complete basis of mixed
implications by performing a reduced number of requests to the formal context.
Beyond the benefits provided by the inclusion of negative attributes in terms
of expressiveness, Revenko and Kuznetsov [10] use negative attributes to tackle
the problem of finding some types of errors in new object intents is introduced.
Their approach is based on finding implications from an implication basis of
the context that are not respected by a new object. Their work illustrates the
great benefit that a general framework for negative and positive attributes would
provide.
In this work we propose a deeper study of the algebraic framework for Formal
Concept Analysis taking into account positive and negative information. The
first step is to consider an extension of the classical derivation operators, proving
to be Galois connection. As in the classical framework, this fact will allows
to built the two usual dual concept lattices, but in this case, as we shall see,
the correspondence among concept lattices and formal contexts reveal several
characteristics which induce interesting properties. The main aim of this work
is to establish a formal full framework which allows to develop in the future new
methods and techniques dealing with positive and negative information.
In Section 2 we present the background of this work: the notions related with
formal concept analysis and negative attributes. Section 3 introduces the main
results which constitute the contribution of this paper.
2 Preliminaries
2.1 Formal Concept Analysis
In this section, the basic notions related with Formal Concept Analysis (FCA)
[12] and attribute implications are briefly presented. See [3] for a more detailed
explanation. A formal context is a triple K = hG, M, Ii where G and M are
finite non-empty sets and I ⊆ G × M is a binary relation. The elements in G
are named objects, the elements in M attributes and hg, mi ∈ I means that the
object g has the attribute m. From this triple, two mappings ↑: 2G → 2M and
↓: 2M → 2G , named derivation operators, are defined as follows: for any X ⊆ G
and Y ⊆ M ,
X ↑ = {m ∈ M | hg, mi ∈ I for all g ∈ X} (1)
Y ↓ = {g ∈ G | hg, mi ∈ I for all m ∈ Y } (2)
X ↑ is the subset of all attributes shared by all the objects in X and Y ↓ is the
subset of all objects that have the attributes in Y . The pair (↑, ↓) constitutes
A generalized framework for negative attributes in FCA 3
a Galois connection between 2G and 2M and, therefore, both compositions are
closure operators.
A pair of subsets hX, Y i with X ⊆ G and Y ⊆ M such X ↑ = Y and
↓
Y = X is named a formal concept. X is named the extent and Y the intent of
the concept. These extents and intents coincide with closed sets wrt the closure
operators because X ↑↓ = X and Y ↓↑ = Y . Thus, the set of all formal concepts
is a lattice, named concept lattice, with the relation
hX1 , Y1 i ≤ hX2 , Y2 i if and only if X1 ⊆ X2 (or equivalently, Y2 ⊆ Y1 ) (3)
This concept lattice will be denoted by B(G, M, I).
The concept lattice can be characterized in terms of attribute implications
being expressions A → B where A, B ⊆ M . An implication A → B holds in a
context K if A↓ ⊆ B ↓ . That is, any object that has all the attributes in A has also
all the attributes in B. It is well known that the sets of attribute implications
that are valid in a context satisfies the Armstrong’s Axioms:
[Ref] Reflexivity: If B ⊆ A then ` A → B.
[Augm] Augmentation: A → B ` A ∪ C → B ∪ C.
[Trans] Transitivity: A → B, B → C ` A → C.
A set of implications Σ is considered an implicational system for K if: an
implication holds in K if and only if it can be inferred, by using Armstrong’s
Axioms, from Σ.
Armstrong’s axioms allow us to define the closure of attribute sets wrt an
implicational system (the closure of a set A is usually denoted as A+ ) and it
is well-known that closed sets coincide with intents. On the other hand, several
kind of implicational systems has been defined in the literature being the most
used the so-called Duquenne-Guigues (or stem) basis [5]. This basis satisfies
that its cardinality is minimum among all the implicational systems and can be
obtained from a context by using the renowned NextClosure Algorithm [3].
2.2 Negatives attributes
As we have mentioned in the introduction, classical FCA only discover knowledge
limited to positive attributes in the context, but it does not consider information
relative to the absence of properties (attributes). Thus, the Duquenne-Guigues
basis obtained from Table 1 is {e → bc, d → c, bc → e, a → b}. Moreover, the
implications b → c and b → d do not hold in Table 1 and therefore they can
not be derived from the basis by using the inference system. Nevertheless, both
implications correspond with different situations. In the first case, some objects
have attributes b and c (e.g. objects o1 and o3 ) whereas another objects (e.g. o2 )
have the attribute b and do not have c. On the other side, in the second case,
any object that has the attribute b does not have the attribute d.
A more general framework is necessary to deal with this kind of information.
In [11], we have tackled this issue focusing on the problem of mining implication
with positive and negative attributes from formal contexts. As a conclusion of
4 Rodriguez-Jimenez et al.
I a b c d e
o1 × × ×
o2 × ×
o3 × × ×
o4 × ×
Table 1. A formal context
that work we emphasized the necessity of a full development of an algebraic
framework.
First, we begin with the introduction of an extended notation that allows
us to consider the negation of attributes. From now on, the set of attributes is
denoted by M , and its elements by the letter m, possibly with subindexes. That
is, the lowercase character m is reserved for positive attributes. We use m to
denote the negation of the attribute m and M to denote the set {m | m ∈ M }
whose elements will be named negative attributes.
Arbitrary elements in M ∪ M are going to be denoted by the first letters in
the alphabet: a, b, c, etc. and a denotes the opposite of a. That is, the symbol a
could represent a positive or a negative attribute and, if a = m ∈ M then a = m
and if a = m ∈ M then a = m.
Capital letters A, B, C,. . . denote subsets of M ∪ M . If A ⊆ M ∪ M , then A
denotes the set of the opposite of attributes {a | a ∈ A} and the following sets
are defined:
– Pos(A) = {m ∈ M | m ∈ A}
– Neg(A) = {m ∈ M | m ∈ A}
– Tot(A) = Pos(A) ∪ Neg(A)
Note that Pos(A), Neg(A), Tot(A) ⊆ M .
Once we have introduced the notation, we are going to summarize some
results concerning the mining of knowledge from contexts in terms of implications
with negative and positive attributes [11]. A trivial approach could be obtained
by adding new columns to the context with the opposite of the attributes [4].
That is, given a context K = hG, M, Ii, a new context (K|K) = hG, M ∪M , I ∪Ii
is considered, where I = {hg, mi | g ∈ G, m ∈ M, hg, mi 6∈ I}. For example, if
K is the context depicted in Table 1, the context (K|K) is those presented in
Table 2. Obviously, the classical framework and its corresponding machinery can
be used to manage the new context and, in this (direct) way, negative attributes
are considered. However, this rough approach induces a non trivial growth of
the formal context and, consequently, algorithms have a worse performance.
In our opinion, a deeper study was done by R. Missaoui et al. in [7] where an
evolved approach has been provided. For first time –as far as we know– inference
rules for the management of positive and negative attributes are introduced [8].
The authors also developed new methods to mine mixed attribute implications
by means of the key notion [9].
A generalized framework for negative attributes in FCA 5
I ∪I a b c d e a b c d e
o1 × × × × ×
o2 × × × × ×
o3 × × × × ×
o4 × × × × ×
Table 2. The formal context (K|K)
In [11], we have developed a method to mine mixed implications whose main
goal has been to avoid the management of the large (K|K) contexts, so that the
performance of the corresponding method has a controlled cost.
First, we extend the definitions of derivation operators, formal concept and
attribute implication.
Definition 1. Let K = hG, M, Ii be a formal context. We define the operators
⇑: 2G → 2M ∪M and ⇓: 2M ∪M → 2G as follows: for X ⊆ G and Y ⊆ M ∪ M ,
X ⇑ = {m ∈ M | hg, mi ∈ I for all g ∈ X}
∪ {m ∈ M | hg, mi 6∈ I for all g ∈ X} (4)
Y ⇓ = {g ∈ G | hg, mi ∈ I for all m ∈ Y }
∩ {g ∈ G | hg, mi 6∈ I for all m ∈ Y } (5)
Definition 2. Let K = hG, M, Ii be a formal context. A mixed formal concept
in K is a pair of subsets hX, Y i with X ⊆ G and Y ⊆ M ∪ M such X ⇑ = Y and
Y ⇓ = X.
Definition 3. Let K = hG, M, Ii be a formal context and let A, B ⊆ M ∪ M ,
the context K satisfies a mixed attribute implication A → B, denoted by K |=
A → B, if A⇓ ⊆ B ⇓ .
For example, in Table 1, as we previously mentioned, two different situations
were presented. Thus, in this new framework we have that K 6|= b → d and
K |= b → d whereas K 6|= b → c either K 6|= b → c.
Now, we are going to introduce the mining method for mixed attribute im-
plications. The method is strongly based on the set of inference rules built by
supplementing Armstrong’s axioms with the following ones, introduced in [8]:
let a, b ∈ M ∪ M and A ⊆ M ∪ M ,
[Cont] Contradiction: ` aa → M M .
[Rft] Reflection: Aa → b ` Ab → a.
The closure of an attribute set A wrt a set of mixed attribute implications Σ,
denoted as A++ , is defined as the biggest set such that A → A++ can be inferred
from Σ by using Armstrong’s Axioms plus [Cont] and [Rft]. Therefore, a mixed
implication A → B can be inferred from Σ if and only if B is a subset of the
closure of A, i.e. B ⊆ A++ .
6 Rodriguez-Jimenez et al.
The proposed mining method, depicted in Algorithm 1, uses the inference
rules in such a way that it is not centered around the notion of key, but it
extends, in a proper manner, the classical NextClosure algorithm [3].
Algorithm 1: Mixed Implications Mining
Data: K = hG, M, Ii
Result: Σ set of implications
1 begin
2 Σ := ∅;
3 Y := ∅;
4 while Y < M do
5 foreach X ⊆ Y do
6 A := (Y r X) ∪ X;
7 if Closed(A, Σ) then
8 C := A⇓⇑ ;
9 if A 6= C then Σ := Σ ∪ {A → C r A}
10 Y := Next(Y ) // i.e. successor of Y in the lectic order
11 return Σ
12 end
The algorithm to calculate the mixed implicational system doesn’t need to
exhaustive traverse all the subsets of mixed attributes, but only those ones that
are closed w.r.t. the set of implications previously computed. The Closed func-
tion is defined having linear cost and is used to discern when a set of attributes
is not closed and thus, the context is not visited in this case.
Function Closed(A,Σ): boolean
Data: A ⊆ M ∪ M with Pos(A)∩Neg(A) = ∅ and Σ being a set of mixed
implications.
Result: ‘true’ if A is closed wrt Σ or ‘false’ otherwise.
1 begin
2 foreach B → C ∈ Σ do
3 if B ⊆ A and C * A then exit and return false if B r A = {a},
A ∩ C 6= ∅, and a 6∈ A then exit and return false
4 return true
5 end
3 Mixed concept lattices
As we have mentioned, the goal of this paper is to develop a deep study of the
generalized algebraic framework. In this section we are going to introduce the
main results of this paper providing the properties of the generalized concept
lattice. The main pillar of our new framework are the two derivation operators
introduced in Equations 4 and 5. The following theorem ensures that the pair
of these operators is a Galois connection:
A generalized framework for negative attributes in FCA 7
Theorem 1. Let K = hG, M, Ii be a formal context. The pair of derivation
operators (⇑, ⇓) introduced in Definition 1 is a Galois Connection.
Proof. We need to prove that, for all subsets X ⊆ G and Y ⊆ M ∪ M ,
X ⊆ Y ⇓ if and only if Y ⊆ X ⇑
First, assume X ⊆ Y ⇓ . For all a ∈ Y , we distinguish two cases:
1. If a ∈ Pos(Y ), exists m ∈ M with a = m and, for all g ∈ X, since X ⊆ Y ⇓ ,
hg, mi ∈ I and therefore a = m ∈ X ⇑ .
2. If a ∈ Neg(Y ), exits m ∈ M with a = m and, for all g ∈ X, since X ⊆ Y ⇓ ,
hg, mi 6∈ I and therefore a = m ∈ X ⇑ .
Conversely, assume Y ⊆ X ⇑ and g ∈ X. To ensure that g ∈ Y ⇓ , we need to
prove that hg, ai ∈ I for all a ∈ Pos(Y ) and hg, ai ∈
/ I for all a ∈ Neg(Y ), which
is straightforward from Y ⊆ X ⇑ . t
u
Therefore, above theorem ensures that ⇑◦⇓ and ⇓◦⇑ are closure operators.
Furthermore, as in the classical case, both closure operators provide two dually
isomorphic lattices. We denote by B] (G, M, I) to the lattice of mixed concepts
with the relation
hX1 , Y1 i ≤ hX2 , Y2 i iff X1 ⊆ X2 (or equivalently, iff Y1 ⊇ Y2 )
Moreover, as in the classical FCA, mixed implications and mixed concept lattice
make up the two sides of the same coin, i.e. the information mined from the
mixed formal context may be dually represented by means of a set of mixed
attribute implications or a mixed concept lattice.
As we shall see later in this section, unlike the classical FCA, mixed concept
lattices are restricted to an specific lattice subclass. There exist specific prop-
erties that lattices may observe to be considered a valid lattice structure which
corresponds to a mixed formal context. In fact, this is one of the main goal of this
paper, the characterization of the lattices in the mixed formal concept analysis.
In Table 3 six different lattices are depicted. In the classical framework, all of
them may be associated with formal contexts, i.e. in the classical framework any
lattice corresponds with a collection of formal context. Nevertheless, in the mixed
attribute framework this property does not hold anymore. Thus, in Table 3, as
we shall prove later in this paper, lattices 3 and 5 cannot be associated with a
mixed formal context.
The following two definitions characterizes two kind of significant sets of
attributes that will be used later:
Definition 4. Let K = hG, M, Ii be a formal context. A set A ⊆ M ∪ M is
named consistent set if Pos(A) ∩ Neg(A) = ∅.
The set of consistent sets are going to be denoted by Ctts, i.e.
Ctts = {A ⊆ M ∪ M | Pos(A) ∩ Neg(A) = ∅}
If A ∈ Ctts then |A| ≤ |M | and, in the particular case where |A| = |M |, we have
Tot(A) = M . This situation induces the notion of full set:
8 Rodriguez-Jimenez et al.
◉
◉ ◉
◉ ◉ ◉
Lattice 1 Lattice 2 Lattice 3
◉ ◉ ◉
◉ ◉ ◉
◉
◉ ◉
◉ ◉ ◉ ◉
◉ ◉ ◉
Lattice 4 Lattice 5 Lattice 6
Table 3. Scheletons of some lattices
Definition 5. Let K = hG, M, Ii be a formal context. A set A ⊆ M ∪ M is said
to be full consistent set if A ∈ Ctts and Tot(A) = M .
The following lemma, which characterize the boundary cases, is straightforward
from Definition 1.
Lemma 1. Let K = hG, M, Ii be a formal context. Then ∅⇑ = M ∪ M , ∅⇓ = G
and (M ∪ M )⇓ = ∅.
In the classical framework, the concept lattice B(G, M, I) is bounded by hM ↓ , M i
and hG, G↑ i. However, in this generalized framework, as a direct consequence
from above lemma, the lower and upper bounds of B ] (G, M, I) are h∅, M ∪ M i
and hG, G⇑ i respectively.
Lemma 2. Let K = hG, M, Ii be a formal context. The following properties
hold:
1. For all g ∈ G, {g}⇑ is a full consistent set.
2. For all g1 , g2 ∈ G, if g1T∈ {g2 }⇑⇓ then {g1 }⇑ = {g2 }⇑ . 1
3. For all X ⊆ G, X ⇑ = g∈X {g}⇑ .
Proof. 1. It is obvious because, for all m ∈ M , hg, mi ∈ I or hg, mi ∈/ I and
{g}⇑ = {m ∈ M | hg, mi ∈ I} ∪ {m ∈ M | hg, mi ∈ / I} being a disjoint union.
Thus, Tot({g}⇑ ) = M and Pos({g}⇑ ) ∩ Neg({g}⇑ ) = ∅.
1
That is, g1 and g2 have exactly the same attributes.
A generalized framework for negative attributes in FCA 9
2. Since (⇑, ⇓) is a Galois connection, g1 ∈ {g2 }⇑⇓ (i.e. {g1 } ⊆ {g2 }⇑⇓ ) implies
{g2 }⇑ ⊆ {g1 }⇑ . Moreover, by item 1, both {g1 }⇑ and {g2 }⇑ are full consistent
and, therefore, {g1 }⇑ = {g2 }⇑ .
3. In the same way that occurs in the classical framework, since (⇑, ⇓) is a
Galois connection between (2G , ⊆) and (2M ∪M , ⊆), for any X ⊆ G, we have
⇑ T
that X ⇑ = = g∈X {g}⇑ .
S
g∈X {g} t
u
The above elementary lemmas lead to the following theorem emphasizing a sig-
nificant difference with respect to the classical construction and it focuses on how
the inclusion of new objects influences the structure of mixed concept lattice.
Theorem 2. Let K = hG, M, Ii be a formal context, g0 be a new object, i.e.
g0 ∈ / G, and Y ⊆ M be the set of attributes that g0 satisfies. Then, there exists
g ∈ G such that {g}⇑ = {g0 }⇑ if and only if there exists an isomorphism between
B ] (G, M, I) and B ] (G ∪ {g0 }, M, I ∪ {hg0 , mi | m ∈ Y }).
That is, if a new different object (an object that differs at least in one attribute
from each object in the context) is added to the formal context then the mixed
concept lattice changes.
Proof. Obviously, if there exists g ∈ G such that {g}⇑ = {g0 }⇑ , from Lemma 2 g
and g0 have exactly the same attributes, and moreover the lattices B ] (G, M, I)
and B ] (G ∪ {g0 }, M, I ∪ {hg0 , mi | m ∈ Y }) are isomorphic.
Conversely, if the mixed concept lattices are isomorphic, there exists X ⊆ G
such that the closed set X ⇑ in B ] (G, M, I) coincides with {g0 }⇑ . Thus, in the
mixed concept lattice B ] (G ∪ {g0 }, M, I ∪ {hg0 , mi | m ∈ X}), by Lemma 2, we
have that {g0 }⇑ = X ⇑ = ∩g∈X {g}⇑ . Moreover, since {g0 }⇑ is a full consistent
set, X 6= ∅ because of, by Lemma 1, ∅⇑ = M ∪ M . Therefore, for all g ∈ X
(there exists at least one g ∈ X), g0 ∈ {g}⇑ and, by Lemma 2, {g}⇑ = {g0 }⇑ . t u
Example 1. Let K1 = ({g1, g2}, {a, b, c}, I1 ) and K2 = ({g1, g2, g3}, {a, b, c}, I2 )
be formal contexts where I1 and I2 are the binary relations depicted in Table 4.
Note that K2 is built from K1 by adding the new object g3. In the classical frame-
I2 a b c
I1 a b c
g1 × ×
g1 × ×
g2 × ×
g2 × ×
g3 ×
Table 4. The formal contexts K1 and K2
work, the concept lattices B({g1, g2}, {a, b, c}, I1 ) and B({g1, g2, g3}, {a, b, c}, I2 )
are isomorphic. See Figure 1.
However, the lattices of mixed concepts cannot be isomorphic because the
new object g3 is not a repetition of one existing object. See Figure 2.
The following theorem characterizes the atoms of the new concept lattice B ] .
10 Rodriguez-Jimenez et al.
<⦰,abc> <⦰,abc>
B({g1, g2}, {a, b, c}, I1 ) B({g1, g2, g3}, {a, b, c}, I2 )
Fig. 1. Lattices obtained in the classical framework
<⦰,abcabc> <⦰,abcabc>
B] ({g1, g2}, {a, b, c}, I1 ) B] ({g1, g2, g3}, {a, b, c}, I2 )
Fig. 2. Lattices obtained in the extended framework
A generalized framework for negative attributes in FCA 11
Theorem 3. Let K = hG, M, Ii be a formal context. The set of atoms in the
lattice B ] (G, M, I) is {h{g}⇑⇓ , {g}⇑ i | g ∈ G}.
Proof. First, fixed g0 ∈ G, we are going to prove that the mixed concept
h{g0 }⇑⇓ , {g0 }⇑ i is an atom in B ] (G, M, I). If hX, Y i is a mixed concept such that
⇑⇓ ⇑ ⇑ ⇑
h∅, M ∪ M i < hX, Y i ≤ h{g T 0 } , {g 0 } i, then {g0 } ⊆ Y = X M ∪ M . By
⇑ ⇑ ⇑
Lemma 2, {g0 } ⊆ X = g∈X {g} . Moreover, for all g ∈ X 6= ∅, by Lemma 2,
both {g0 }⇑ and {g}⇑ are full consistent sets and, since {g0 }⇑ ⊆ {g}⇑ , we have
{g0 }⇑ = {g}⇑ . Therefore, {g0 }⇑ = X ⇑ = Y and hX, Y i = h{g0 }⇑⇓ , {g0 }⇑ i.
Conversely, if hX, Y i is an atom in B ] (G, M, I), then X 6= ∅ and there
exists g0 ∈ X. Since (⇑, ⇓) is a Galois connection, {g0 }⇑ ⊇ X ⇑ = Y and,
therefore, h{g0 }⇑⇓ , {g0 }⇑ i ≤ hX, Y i. Finally, since hX, Y i is an atom, we have
that hX, Y i = h{g0 }⇑⇓ , {g0 }⇑ i. t
u
The following theorem establishes the characterization of the mixed concept
lattice, proving that atoms and join irreducible elements are the same notions.
Theorem 4. Let K = hG, M, Ii be a formal context. Any element in B ] (G, M, I)
is ∨-irreducible if and only if it is an atom.
Proof. Obviously, any atom is ∨-irreducible. We are going to prove that any
∨-irreducible element belongs to {h{g}⇑⇓ , {g}⇑ i | g ∈ T G}. Let hX, Y i be a ∨-
irreducible element. Then, by Lemma 2, Y = X ⇑ = g∈X {g}⇑ . Let X 0 be the
smaller set such that X 0 ⊆ X and Y = g∈X 0 {g}⇑ . If X 0 is a singleton, then
T
hX, Y i ∈ {h{g}⇑⇓ , {g}⇑ i | g ∈ G}.
Finally, we prove that X 0 is necessarily a singleton. In other case, a bipartition
of X 0 in two disjoint sets Z1 and Z2 can T
be made satisfying Z1 ∪Z2 = X 0 , Z1 6= ∅,
Z2 6= ∅ and Z1 ∩ Z2 6= ∅. Then, Y = g∈Z1 {g} ∩ g∈Z2 {g}⇑ = Z1⇑ ∩ Z2⇑ and
⇑
T
so hX, Y i = hZ1⇑⇓ , Z1⇑ i ∨ hZ2⇑⇓ , Z2⇑ i and Z1⇑ 6= Y 6= Z2⇑ . However, it is not posible
because hX, Y i is ∨-irreducible. t
u
As a final end point of this study, we may conclude that unlike in the classical
framework, not every concept lattice may be linked with a formal context. Thus,
lattices number 3 and 5 from Table 3 cannot be associated with a mixed formal
context. Both of them have one element which is not an atom but, at the same
time, it is a join irreducible element in the lattice. More specifically, there does
not exists a mixed concept lattice with three elements.
4 Conclusions
In this work we have presented an algebraic study of a general framework to
deal with negative and positive information. After considering new derivation
operators we prove that they constitutes a Galois connection. The main results
of the work are devoted to establish the new relation among mixed concept
lattices and mixed formal concepts. Thus, the most outstanding conclusions are
that:
12 Rodriguez-Jimenez et al.
– the inclusion of a new (and different) object in a formal concept has a direct
effect in the structure of the lattice, producing a different lattice.
– no any kind of lattice may be associated with a mixed formal context, which
induces a restriction in the structure that mixed concept lattice may have.
Acknowledgements
Supported by grant TIN2011-28084 of the Science and Innovation Ministry of
Spain, co-funded by the European Regional Development Fund (ERDF).
References
1. R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules in Large
Databases. In Proceedings of the 20th International Conference on Very Large Data
Bases (VLDB), pages 487–499, Santiago de Chile, Chile, 1994. Morgan Kaufmann
Publishers Inc.
2. J.F. Boulicaut, A. Bykowski, and B. Jeudy. Towards the tractable discovery of
association rules with negations. In FQAS, pages 425–434, 2000.
3. B. Ganter. Two basic algorithms in concept analysis. Technische Hochschule,
Darmstadt, 1984.
4. G. Gasmi, S. Ben Yahia, E. Mephu Nguifo, and S. Bouker. Extraction of association
rules based on literalsets. In DaWaK, pages 293–302, 2007.
5. J.L. Guigues and V. Duquenne. Familles minimales d implications informatives
resultant d un tableau de donnees binaires. Mathematiques et Sciences Sociales,
95:5–18, 1986.
6. H. Mannila, H. Toivonen, and A. Inkeri Verkamo. Efficient algorithms for discov-
ering association rules. In KDD Workshop, pages 181–192, 1994.
7. R. Missaoui, L. Nourine, and Y. Renaud. Generating positive and negative exact
rules using formal concept analysis: Problems and solutions. In ICFCA, pages
169–181, 2008.
8. R. Missaoui, L. Nourine, and Y. Renaud. An inference system for exhaustive
generation of mixed and purely negative implications from purely positive ones. In
CLA, pages 271–282, 2010.
9. R. Missaoui, L. Nourine, and Y. Renaud. Computing implications with negation
from a formal context. Fundam. Inform., 115(4):357–375, 2012.
10. A. Revenko and S. Kuznetzov. Finding errors in new object intents. In CLA, pages
151–162, 2012.
11. J.M. Rodriguez-Jimenez, P. Cordero, M. Enciso, and A. Mora. Negative attributes
and implications in formal concept analysis. Procedia Computer Science, 31(0):758
– 765, 2014. 2nd International Conference on Information Technology and Quan-
titative Management, ITQM 2014.
12. R. Wille. Restructuring lattice theory: an approach based on hierarchies of con-
cepts. In Rival, I. (ed.): Ordered Sets, pages 445–470. Boston, 1982.