This paper establishes an ordering between partial formal contexts, which are trivalued contexts. We use three values to represent the presence or absence of a certain property or its unknown value. We establish a Galois connection between this ordered set and the Boolean algebra of attribute sets. Finally, we discuss the interpretation of this Galois connection. Formal Concept Analysis (FCA) [1] extracts knowledge from a binary relationship = (, , ) where is a set of objects, is a set of attributes, and is a relation between and (called incidence). See [2] for readers not habituated to FCA. The standard interpretation only considers the information in pairs (, ) ∈ where is an object and is an attribute, named positive information.
mixed concepts to extend FCA with positive and negative. The authors presented a new Galois connection that takes advantage of the relationship between the positive and negative attributes.
There are some occasions when we can not work out what those blank cells mean; that is, the
blanks are unknown information. There is quite a lot of recent work on processing unknown
information through FCA [
In [
Considering the following, given an attribute in the original formal context: the new object
will have the attribute if all the packed objects had the attribute; it will not have the attribute if
none of the compacted objects had the attribute; and finally, in other cases, the relation between
the new object and the attribute will be unkown. We want to merge the work [
2.1. Trivalued formal contexts We consider the ∧-semilattice 3 = (3, ≤) where 3 = {+, −, ∘}and ≤ is the smallest order such that ∘ ≤ + and ∘ ≤ − (see Fig. 2a). Then, a 3-set on a universal set is a mapping ∶ → 3 where, for each ∈ , () represents the knowledge about the membership of to : () = + means that it is known that belongs to (we call it positive information), () = − means that it is known that does not belong to (we call it negative information), and () = ∘ denotes the absence of information about the membership of (which is called unknown information). As usual, the algebraic structure of 3 is powered to 3 , the set of 3-sets on , by considering the pointwise ordering: ⊑ if () ≤ () for all ∈ .
This new structure is denoted by 3 = (3 , ⊑).
Given ∈ 3 , we call support of to the set of the elements of which we have information about, i.e. Spp() = { ∈ ∶ () ≠ ∘} . In addition, any 3-set establishes a partition of the universal set (the quotient set) in three parts:
Pos() = { ∈ ∶ () = +} = Neg() = { ∈ ∶ () = −} = −1(+) −1(−) 1 2 3 + ∘ − ∘ ∘ − − + ∘ Thus, two of these sets determine the third one and, therefore, we can consider that we are dealing with a pair of sets ( , )
with ∩ = ∅
formalisation provided by the so-called orthopairs [
When the support of a 3-set is finite, we express it as a sequence of elements (with no delimiters). It can be seen as an ordered re-writing of the concatenation of the elements of the orthopair, where the atoms in are capped. For instance, = 1 5̄ 7 means that . It corresponds to the equivalent ( 1 ) = ( notate = 7) = +, (
5) = −, and () = ∘ (i.e. the empty chain).
in other case. In particular, when Spp() = ∅ , we ′ = (, , ) (, ) = ∘
3 is a ∧-semilattice (see, for instance, Figure 3a) whose maximal elements are those holding Unk() = ∅ . They are called the full sets and coincide with those orthopairs ( , ) such that ∪ =
. The set of full sets is denoted by Full( ) .
Considering this three-valued structure, a partial formal context is defined as a triple ℙ = (, , ) being and sets and a 3-set on × . As usually, the elements of are named objects, the elements of attributes, and ∶ × → 3 incidence relation. For ∈ and ∈ the semantics of this incidence relation is the following: (, ) = + means that the object has the attribute ; (, ) = −
means that the object doesn’t have the attribute ; and (, ) = ∘
means that we do not know whether the object has the attribute or not. As in the classical case, these contexts are shown as tables and, given ∈ , we define the 3-set (, ) by currying the mapping , i.e. (, ) ∈ 3 is those 3-set such that (, )() = (, ) for each ∈
. For instance, for the partial formal context depicted in Figure 1, we have (1, ) = . A partial formal context ℙ = (, , ) such that ∈
Full( × )
is named total formal
context. On the other hand, following the classical interpretation, a (classical) formal context
is a partial formal context ℙ = (, ,
′
) where ′(, ) = +
if
, and
2.2. Inconsistencies: extending the underlying structure
In the formalism introduced by Ganter et.al. [
If we generalise this idea in the framework of partial contexts, we may find that, in a set of + ↖ ↗ − ∘ (a) ∧-semilattice 3 ↗ ↖ ∘ + ↖ ↗ − (b) lattice (4, ≤) objects, some have a certain attribute and others do not, i.e. we may find inconsistencies (due to conjunctive interpretation). This takes us from a trivalued model to a tetravalued model.
Hence, we introduce a fourth element representing inconsistent or contradictory information. This new element, which is denoted and called oxymoron, will be the maximum completion of 3 to be a lattice. This lattice (4, ≤) is shown in Fig. 2b and corresponds with the so-called “information ordering” in the Belnap’s lattice [12]. The posets 3 and 4 are respectively denoted by 1 ⊕ 2 and 1 ⊕ 2 ⊕ 1 in [13].
In the same way that we did for 3 , we consider its extension 4 , the set of mappings ∶ →
4 or 4-sets, and the pointwise order ⊑. Notice that (4 , ⊑) is a lattice whose infimum is and supremum is the 4-set that maps any ∈ to , which is named oxymoron and denoted by .̇ The 4-sets can be seen as paraconsistent orthopairs [14], where the condition ∩ = ∅ is omitted.
However, as in the classical propositional logic, we semantically consider that, when any contradiction appears, we can derive anything. Thus, we identify all inconsistent orthopairs and use ̇ as the representative element of this class. To formalise it, we define the following closure operator: ∶ 4 → 4 being () = { ̇ if ∈
3 , otherwise.
We denote by 3̇ its codomain ( 4 ) = 3 ∪ {}̇ , which is a closure system in (4 , ⊑). Therefore, (3̇ , ⊑) is, on the one hand, a complete lattice (see Fig.3) and, on the other hand, a ∧-subsemilattice of (4 , ⊑) (but not a sublattice). This lattice will be denoted by 3̇ . Notice that the super-atoms in 3̇ are the full sets. Since both infima coincide, they will be denoted by the same symbol: ∧. However, the supremum in (4 , ⊑) is denoted by the ∨, whereas in (3̇ , ⊑) is denoted by ⊔. Thus, for all { ∶ ∈ } ⊆ 3̇ , we have that and, in particular, ⨆ = ( ⋁ ) ∈
∈ ⨆ ≠ ̇ ∈ implies ⨆ = ⋁ . ∈ ∈ (1) 1↑ 2↖ 1 ← ↗ 1 2 ↖ 2 ↖ ↗ 1 2↖ ↗ 2 ↗ ̇ ↖ ↗ ↖ 1↑ 2↖ 1 ← ↗ 1 2 ↖ 2 ↖ ↗ 1 2↖ ↗ 2 1 2 ↗ ↑ → 1 (b) The lattice 3̇{ 1, 2} 3.
The lattice of partial formal contexts
As mentioned in the introduction, we have studied partial formal context in [
Unk( (, )} and ′((, ), ) = (, ) ⊔ for all (, ) ∈
′. Finally, this total formal context can be analyzed and managed with the tools introduced in [15]. The main problem of this approach is that the growth of the size of ∗(ℙ) with respect to the initial ℙ is exponential. Specifically, | ′| = ∑ 2|Unk( (, ))|
∈
An important feature of FCA is that, although the concept lattice has an exponential size with respect to the context, concepts can be computed lazily with algorithms whose cost is “polynomial delay”. In the following, we describe how to extend this idea to partial formal context by partially computing the concepts of ∗(ℙ) in a lazy way without having to have previously calculated ∗(ℙ). To do it, we introduce a lattice of partial contexts on which we will navigate in the search for concepts.
Given two partial formal contexts ℙ1 = ( 1, 1, 1) and ℙ2 = ( 2, 2, 2), we say that ℙ1 is a refinement of ℙ2 (denoted by ℙ1 ⪯ ℙ2) if 1 ⊆ 2, 1 = 2, and 2(, ) ⊑ 1(, ) for all ∈ 1 (2) In the Figure 5, a chain of partial formal contexts is shown. ∗ 1. 1. 2. 2. 2. 2. 3. 3. + + + − + − − − + − + + − − − − − − + + + + + − (a) = (, , ) (b) ∗(ℙ) = ( ′, , ′ ) ((ℙ 0), ⪯) is a complete lattice.
The infimum and the supremum in the complete lattice (ℙ0) are defined as follow: • The infimum of {ℙ = ( , , ) ∶ ∈ } ⊆ (ℙ 0) is k ℙ = (, , ) ℙ 1 2 3 ⪰ + ∘ − 1 2 ∈ }.
∘ ∘ − + + − + ∘ ∘ ∘ being = { ∈ ∶ ∈ In addition, the upper bound and the lower bound of (ℙ0) are ℙ0 and (∅, , ) respectively. 4. A Galois connection between partial formal contexts and 3-sets of attributes Now we present the Galois connection that will allow us to collect the formal concepts in a lazy way. Given a partial formal context ℙ0 = ( 0, , 0), we define two derivation operators as follows: = { ∈ ⋂ ∶ ⨆ (, ) ≠ ̇ } and, for all ∈ , (, ) = ∈
∈ • The supremum of {ℙ = ( , , ) ∶ ∈ } ⊆ (ℙ 0) is j ℙ = (, , ) = ⋃ and, for all ∈ , (, ) = ⨅ (, ) ∈ ∈ ∈ with ⨆ (, ) ∈ with • ⇑ ∶ (ℙ 0) → 3̇ that maps any = (, , ) ∈ (ℙ 0) to ⇑ = ⨅∈ (, ) . • ⇓ ∶ 3̇ → (ℙ 0) that maps any 3̇-set ∈ 3̇ to ⇓ = (, , ) where = { ∈ 0 ∶ 0(, ) ⊔ ≠ }̇
and (, ) = 0(, ) ⊔ , for each ∈ .
Example 1. Given the following partial formal context ℙ0 and 1, 2 ∈ (ℙ 0) ℙ0 1 2 + − ∘ + − ∘ 1 1 2 + − + + − ∘ + ∘ − we have 1⇑ = and ⇓ = 2.
Theorem 2. The pair (⇑, ⇓) is a Galois connection between (ℙ0) and 3̇ . and, therefore, ⇑ is an antitone mapping.
Let’s prove that ⇓ is also antitone. Assume that 1, 2 ∈ 3̇ satifiy 1 ⊑ 2, and let 1⇓ = ( 1, , 1) and 2⇓ = ( 2, , 2). On the one hand, since 1 ⊑ 2, we straightforwardly have that
2 = { ∈ ∶ 0(, ) ⊔ 2 ≠ }̇ ⊆ { ∈ ∶ 0(, ) ⊔ 1 ≠ }̇ = 1.
On the other hand, for all ∈ 2 ⊆ 1, we have that
1(, ) = 0(, ) ⊔ 1 ⊑ 0(, ) ⊔ 2 = 2(, ).
Now we prove that 1 ⪯ 1⇑⇓ for all 1 ∈ (ℙ 0). If 1 = ( 1, , 1) and 1⇑⇓ = 2 = Therefore, 2⇓ ⪯ 1⇓. ( 2, , 2), we have that Then, for all ∈ 1, we have 2 = { ∈ 0 ∶ 0(, ) ⊔ ⨅ 1( 1, ) ≠ }̇ .
1∈ 1 0(, ) ⊔ ⨅ 1( 1, ) ⊑ 0(, ) ⊔ 1(, ) = 1(, ) 1∈ 1 ∶ 0(, ) ⊔ ≠ }̇ ⇓⇑. and, therefore ∈
2 and 2(, ) ⊑ 1(, ) .
Finally, let’s prove that ⊑ ⇓⇑ for all ∈
3̇ . Since ⇑ = ( 1, , and 1(, ) = 0(, ) ⊔ for each ∈ 1, we have that ⊑ 1) where 1 = { ∈ ⨅∈ 1 1(, ) = 4 ̄
2 − + ∘ 2 8 ̄ ̇ ∅
1 + ∘ − 2 − + ∘
1 + + − 2 − + − 3 9 ̄
1 + ∘ − 2 − + − 6
̄ their fixed points provide dually isomorphic lattices.
Corollary 1. Given a partial formal context ℙ0 = ( 0, , 0), the set (ℙ 0) = {(, ) ∈ (ℙ
0) × 3̇ ∶ ⇑ = and ⇓ = } ( 1, 1) ⪯ ( 2, 2) if 1 ⪯ 2 (or equivalently, if 2 ⊑ 1) form a complete lattice denoted by (ℙ0).
The couples (, ) ∈ (ℙ
0) are named formal concept on ℙ0, and its components and are named extent and intent of the concept, respectively.
Example 2. In Figure 6 we present the lattice (ℙ0) obtained from the following partial formal ℙ0 1 2 + ∘ − − + ∘ Given a partial fomral context ℙ = (, , )
, the set of atoms of (ℙ) is {( ⇓, ) ∶ ∈ ℳ(ℙ)}
ℳ(ℙ) = { ∈ Full( ) ∶ (, ) ⊑
for some ∈ }
7
̄
5
11
∅
{1., 1. , ̄2., 2.}̄
̄
{1., 2.}̄
̇
∅
3
9
̄
{1., 1. , ̄2.}̄
̄
In addition, if the completion of ℙ is ∗(ℙ) = ( ′, , ′) then
ℳ(ℙ) = { ′((, ), ) ∶ (, ) ∈
′
}
and the lattice (ℙ) is isomorphic to the mixed concept lattice obtained from ∗(ℙ), which was
defined in [
Example 3. For the partial formal context ℙ0 defined in Example 2 provided in Section 4, the atoms of the lattice (ℙ0) are ℳ(ℙ) = {, ̄,
̄, ̄
of ℙ0,
}̄ ̄ (see Fig. 6) and, from the completion
∗(ℙ0)
1.
1. ̄
2.
2. ̄
+ + −
+ − −
− + +
− + −
we obtain the mixed concept lattice depicted in Figure 7.
5. Conclusions and future works
In this work, we have presented a Galois connection that allows us to combine the work
presented in [
In the future, we want to extend this work by presenting implications that are fulfilled in any possible universe, that is, in any of the completions of the partial formal context or, which is equivalent in granularity terms when we explore any grains obtaining the missing information. Acknowledgments Partially supported by the Spanish Ministry of Science, Innovation, and Universities (MCIU), State Agency of Research (AEI), Junta de Andalucía (JA), Universidad de Málaga (UMA) and European Regional Development Fund (FEDER) through the projects PGC2018-095869-B-I00 (MCIU/AEI/FEDER), TIN2017-89023-P (MCIU/AEI/FEDER), PRE2018-085199 and UMA2018FEDERJA-001 (JA/UMA/FEDER). [12] N. D. Belnap, A Useful Four-Valued Logic, Springer Netherlands, Dordrecht, 1977, pp. 5–37. [13] B. Davey, H. Priestley, Introduction to lattices and order, second ed., Cambridge University press, Cambridge, 2002. [14] D. Dubois, S. Konieczny, H. Prade, Quasi-possibilistic logic and measures of information and conflict, in: First International Workshop on Knowledge Representation and Approximate reasoning (KR & AR 2003), volume 57 of Fundamenta Informaticae, Olsztyn, Poland, 2003, pp. 101–125. [15] J. M. Rodríguez-Jiménez, P. Cordero, M. Enciso, A. Mora, Data mining algorithms to compute mixed concepts with negative attributes: an application to breast cancer data analysis, Mathematical Methods in the Applied Sciences 39 (2016) 4829–4845.