=Paper=
{{Paper
|id=None
|storemode=property
|title=Adapting Fuzzy Formal Concept Analysis for Fuzzy Description Logics
|pdfUrl=https://ceur-ws.org/Vol-972/paper14.pdf
|volume=Vol-972
|dblpUrl=https://dblp.org/rec/conf/cla/Distel12
}}
==Adapting Fuzzy Formal Concept Analysis for Fuzzy Description Logics==
https://ceur-ws.org/Vol-972/paper14.pdf
Adapting Fuzzy Formal Concept Analysis for
Fuzzy Description Logics
Felix Distel
Institute of Theoretical Computer Science, Technische Universität Dresden, Dresden,
Germany, felix@tcs.inf.tu-dresden.de
Abstract. Fuzzy Logics have been applied successfully within both For-
mal Concept Analysis and Description Logics. Especially in the latter
field, Fuzzy Logics have been gaining significant momentum during the
last two years. Unfortunately, the research on fuzzy logics within the two
communities has been conducted independently from each other, lead-
ing to different approaches being pursued. We show that if we look at a
restricted variant of fuzzy formal concept analysis, then the differences
between the two approaches can be reconciled. Moreover, an implica-
tional base can be computed even when the identity hedge is used.
1 Introduction
In many applications one is forced to deal with vague knowledge, knowledge that
does not fit into the binary world of classical logics. Among the countlessly many
examples are the questions whether a country is large, or whether two cities are
close to each other are difficult to answer with true or false. There are various
degrees of size and proximity. Fuzzy Logics has successfully proposed to use a
scale of truth degrees to describe vague knowledge. It has first been formalized
for propositional logic [1] and has since been applied to many other logics and
logic related formalisms. Among them are Formal Concept Analysis (FCA) [2]
and Description Logics (DL) [3].
Whenever one applies Fuzzy Logics to an existing formalism, one is faced with
several choices: Should the real unit interval be used for the set of truth degrees
or a more complex lattice of truth degrees? How should the semantics of the
conjunction be defined? Which parts of the existing theory should be replaced
by their fuzzy counterparts and which should remain unchanged? These decisions
have been made independently for fuzzy FCA and fuzzy DL.
In the crisp setting, a number of works have used FCA methods in DL. Some
use it as a tool for efficiently computing concept hierarchies [4]. Others use it
for ontology completion [5] and for exploring and learning from graph data [6,
7]. This work has been possible due to the close ties between FCA and DL.
In FCA objects can be described using sets of attributes, and in DL individuals
can be described using concept descriptions, in the easiest case conjunctions over
concept names. Sets of attributes in FCA and conjunctions over concept names in
DL share essentially the same semantics. While in the crisp case the similarities
c 2012 by the paper authors. CLA 2012, pp. 163–174. Copying permitted only for
private and academic purposes. Volume published and copyrighted by its editors.
Local Proceedings in ISBN 978–84–695–5252–0,
Universidad de Málaga (Dept. Matemática Aplicada), Spain.
164 Felix Distel
between fuzzy DL and fuzzy FCA are prominent, the situation is not so clear
in the fuzzy variants of the respective theories. In fuzzy FCA one is allowed to
use fuzzy sets of attributes. In fuzzy DL the same concept descriptions as in
crisp DL are used. They are not fuzzy, only their semantics are. In Section 3 we
identify such differences, that hinder the close cooperation that exists between
the crisp variants of the two fields. We propose simple adjustments to avoid
them. Generally speaking, one can say that the FCA community has been more
ambitious and applied Fuzzy Logics to a much larger extent than fuzzy DL.
Unfortunately, for this reason implication bases, which play an important role
in the cooperation between crisp DL and crisp FCA, can no longer effectively be
computed in the general case [8, 9].1 We shall see in Section 4 that if we restrict
expressivity of fuzzy FCA by considering only crisp sets of attributes, we can
effectively compute bases.2 Moreover, if the Gödel t-norm is used, this restricted
version of fuzzy FCA is exactly the segment of fuzzy FCA whose semantics
overlaps with fuzzy DL, presumably allowing synergies as in the crisp case.
The restriction to the Gödel t-norm is necessary, since fuzzy FCA uses weak
conjunction for the semantics of attribute sets, while DL uses strong conjunction
for its semantics. The two coincide only for the Gödel t-norm. From a current
DL viewpoint, this is not a severe restriction, since up to now the Gödel t-norm
is the only t-norm for which the standard DL reasoning tasks are known to be
decidable [10].
2 Preliminaries
2.1 T-Norms, Hedges and Fuzzy Sets
Fuzzy Logics represent vague data while maintaining a well-defined semantics.
Instead of using only the two values true and false a scale of truth degrees is used.
In this work we consider only the most typical choice where truth degrees are
values from the real unit interval [0, 1].
Fuzzy Logics provide several operators to define its semantics. A t-norm ⊗
is a binary operator ⊗ : [0, 1] × [0, 1] → [0, 1] that is associative, commutative,
monotone and has 1 as its unit. Every continuous t-norm gives rise to a binary
operator ⇒ : [0, 1] × [0, 1] → [0, 1] that is the unique operator satisfying
z ≤ x ⇒ y iff x ⊗ z ≤ y (1)
for all z ∈ [0, 1]. The intuition is that the t-norm and the residuum be used to
interpret conjunction and implication, respectively. Among the many continuous
t-norms perhaps the simplest one, and the one we shall be interested in, is the
Gödel t-norm. It is defined as x ⊗ y = min{x, y} and its residuum is
(
1 if x ≤ y
x⇒y=
y otherwise.
1
They can be computed if the globalization hedge is used. However, hedges do not
exist in fuzzy DL and would even be problematic, as we shall see later.
2
even if the globalization hedge is not used
Adapting Fuzzy FCA for Fuzzy Description Logics 165
A hedge ·∗ is a unary operator that is idempotent and satisfies 1∗ = 1, a∗ ≤ a,
and (a ⇒ b)∗ ≤ a∗ ⇒ b∗ for all a, b ∈ [0, 1]. It is used for truth-stressing, i.e. to
increase the contrast between 1 and the smaller truth values. A simple hedge is
the globalization, defined as 1∗ = 1 and a∗ = 0 for a 6= 0.
Fuzzy sets are a central idea of Fuzzy Logics. Given a set M a fuzzy (sub-)set
T of M is a function T : M → [0, 1], that maps each element of M to its mem-
bership degree in T . The cardinality of a fuzzy set T is defined as the cardinality
of its support {x ∈ M | T (x) > 0}. Two fuzzy sets T1 and T2 can be compared
pointwise by defining T1 ⊆ T2 iff T1 (x) ≤ T2 (x) for all x ∈ M . Alternatively, one
can associate a subsethood degree with T1 and T2 by defining
S(T1 , T2 ) = inf T1 (x) ⇒ T2 (x).
x∈M
For finite fuzzy sets we use notation such as {0.5/a, 1/b} to denote the set that
contains a with degree 0.5 and b with degree 1.
2.2 Formal Concept Analysis
The crisp setting We introduce crisp FCA in addition to fuzzy FCA, as we
shall need the crisp version of the Duquenne-Guigues Base in the later sections.
In crisp FCA [11], data is typically represented in the form of cross tables such
as the one in Table 1. More formally, a formal context is a triple K = (G, M, I)
where G is a set, called the set of objects, M is a set, called the set of attributes,
and I ⊆ G × M is a binary relation, called the incidence relation. For sets A ⊆ G
and B ⊆ M the derivation operators are defined as
A↑ = {m ∈ M | ∀g ∈ A : (g, m) ∈ I}, B ↓ = {g ∈ G | ∀m ∈ B : (g, m) ∈ I}. (2)
The two derivation operators ·↑ and ·↓ form an antitone Galois-connection. An
implication A → B, where A, B ⊆ M , is said to hold in the context K if A↓ ⊆ B ↓ .
A set of attributes U ⊆ M respects A → B iff A 6⊆ U or B ⊆ U . A → B follows
from a set of implications L iff every set U that respects all implications from L
also respects A → B.
One way to structure the data in a formal context K is the Duquenne-Guigues
base DG(K) [12]. DG(K) is a set of implication that is sound for K, i.e. every
implication from DG(K) holds in K, complete for K, i.e. every implication that
holds in K follows from DG(K), and has minimal cardinality among all sound and
complete sets of implications. A version that can handle background knowledge
has been introduced in [13]. Given a sound set of implications S (the background
knowledge) the S-Duquenne-Guigues base DG S (K) is a set of implications such
that DG S (K) is sound for K, S ∪ DG S (K) is complete for K and DG S (K) has
minimal cardinality [7]. The underlying mathematics of DG(K) and DG S (K)
are not relevant for this work. It is, however, important, that both bases can
effectively be computed for every finite context K.
166 Felix Distel
The Fuzzy Setting [2] In a fuzzy context K = (G, M, I) the incidence relation
I is a fuzzy relation, i.e. a fuzzy subset of G × M . The derivation operators are
defined for fuzzy subsets A of G and fuzzy subsets B of M as follows:
A↑ (m) = inf A(g)∗ ⇒ I(g, m) , B ↓ (g) = inf B(m) ⇒ I(g, m) .
(3)
g∈G m∈M
Notice, that the hedge ·∗ is used only for the derivation of fuzzy sets of objects.
The operators ·↑ and ·↓ form a Galois connection with hedges.
In fuzzy FCA the implications are also allowed to be fuzzy. A fuzzy implica-
tion is a pair written as A → B where A and B are fuzzy subsets of M . Let U
be a fuzzy subset of M . The degree to which A → B holds in U is defined as
kA → BkU = S(A, U )∗ ⇒ S(B, U ) (4)
The degree to which A → B holds in K is defined as kA → BkK = ming∈G kA →
BkIg , where Ig is the fuzzy set to which each m ∈ M belongs with degree I(g, m).
Let L be a fuzzy set of fuzzy implications. A set U ⊆ M is called a model of L if
kA → BkU ≥ L(A → B) holds for every fuzzy implication A → B. We say that
A → B follows from L to degree q if kA → BkU ≥ q for all models U of L. There
have been several works where the existence of bases for fuzzy implications has
been considered [8, 9]. We shall not go into details, however, we would like to
point out two things. First, it can be shown that it suffices to consider crisp sets
L that contain fuzzy GCIs [14]. Second, in this setting an effective algorithm for
computing a base is known only when globalization is used as the hedge [8].
2.3 Fuzzy Description Logics
For DL we only introduce the fuzzy version. The crisp version only occurs in
a high-level description in Section 3.1. For a formal introduction of crisp DL
we refer to [15]. DL is not just one formalism, but a family of many knowledge
representation formalisms. The observations in this work hold for any fuzzy DL
that provides for conjunction, i.e. virtually all of them. For brevity we only
introduce the lightweight DL called EL. In fuzzy EL (exactly like in crisp EL)
concept descriptions can be formed from a set of concept names NC and a set
of role names NR using the constructors ⊤, ⊓ and ∃. More formally, ⊤ and all
concept names are concept descriptions, and if C and D are concept description
and r is a role name then C ⊓ D and ∃r.C are also concept descriptions.
In fuzzy EL (in contrast to crisp EL) fuzzy sets are used to interpret both
concepts and roles. A fuzzy interpretation I = (∆I , ·I ) satisfies
AI : ∆I → [0, 1], rI : ∆I × ∆I → [0, 1].
for all A ∈ NC and all r ∈ NR . Fuzzy interpretations I are extended to complex
concept descriptions by defining ⊤I (x) = 1 and
(C ⊓ D)I (x) = C I (x) ⊗ DI (x), (∃s.C)I (x) = sup sI (x, z) ⊗ C I (z) (5)
z∈∆I
Adapting Fuzzy FCA for Fuzzy Description Logics 167
for all x ∈ ∆I . Fuzzy GCIs are typically written as hC ⊑ D, qi, where C, D
are concept descriptions and q ∈ [0, 1]. The fuzzy GCI hC ⊑ D, qi holds in the
fuzzy interpretation I if all x ∈ ∆I satisfy C I (x) ⇒ DI (x) ≥ q. The fuzzy
interpretation I is a model of the set of fuzzy GCIs T if all fuzzy GCIs from T
hold in I. hC ⊑ D, qi is entailed by T if it holds in all models of T .
3 Comparison of the Two Formalisms
3.1 The Crisp Setting
Most existing works at the intersection of FCA and DL have in common that
they associate FCA attributes and DL concept names. The objects are usually
chosen to be domain elements of an interpretation [6, 7]. Other choices, such
as selecting ABox individuals, usually require extending FCA theory, e.g. to
allow for partial knowledge [5]. These choices are motivated by the following
observation. Whether we compute the interpretation of the concept descrip-
tion Large ⊓ Populous ⊓ Asian or compute the derivation of the set of attributes
{Large, Populous, Asian}, the intuition in both cases is that we want to know
which countries are large and populous and Asian.
To formalize this connection, for every interpretation I = (∆I , ·I ) one can
define its induced context KI whose set of objects is ∆I , whose attributes
are the concept names and where x ∈ ∆I and A ∈ NC are incident iff x ∈
AI . For example, we can think of the context in Table 1 as being induced
by an interpretation I whose domain are the world’s 8 most populous coun-
tries, and where the concept names Populous, Large and Asian are interpreted
as PopulousI = {China, India}, LargeI = {China, Russia, US}, and AsianI =
{China, India, Indonesia, Pakistan, Russia}. d
In the induced context it holds for all sets U ⊆ NC that U ↓ = ( U )I , further
supporting the intuition that sets of attributes are treated like conjunctions
over
d attributes.
d Similarly, for two sets of concept names U, V ⊆ NC the GCI
U ⊑ V holds in the interpretation I iff the implication U → V holds in
the induced context of I. Hence, the notions of dependencies also coincide in
crisp FCA and crisp DL. One could even go so far to say that standard formal
contexts and the very simple DL that only allows for conjunction are syntactic
variants of each other.
3.2 The Fuzzy Setting
In this section, we analyze the differences between fuzzy FCA and fuzzy DL that
hinder a close cooperation like it exists in the crisp setting. First, the semantics
of fuzzy FCA do not treat sets of attributes like conjunctions over concept names.
Remember that in the crisp setting the exact same semantics are used to compute
the derivation of a set of attributes or the interpretation of a conjunction of
concept names. This is not true in the fuzzy setting because the infimum (or
minimum in the case of finite contexts) is used to interpret attribute sets (2) while
168 Felix Distel
Table 1. Induced Context Table 2. Induced Fuzzy Context
Large Populous Asian Large Populous Asian
Brazil Brazil 0.5 0.14 0.0
China × × × China 0.56 1.0 1.0
India × × India 0.19 0.9 1.0
Indonesia × Indonesia 0.11 0.18 0.76
Nigeria Nigeria 0.05 0.13 0.0
Pakistan × Pakistan 0.05 0.13 1.0
Russia × × Russia 1.0 0.11 0.75
US × US 0.58 0.23 0.0
the t-norm is used to interpret conjunctions (5).3 In the case of the Gödel t-norm
this is completely harmless, as the Gödel t-norm coincides with the minimum.
For the other t-norms the difference is relevant.
As an example, assume that Table 2 is obtained from a fuzzy interpretation
I by using the domain as objects, concept names as attributes and defining
I(x, A) = AI (x) (We could call it the induced fuzzy context of I). If we use the
Łukasiewicz t-norm, which is defined as x ⊗ y = max{0, x + y − 1}, then
(Populous ⊓ Large)I (US) = 0.23 ⊗ 0.58 = 0
However, in fuzzy FCA with the Łukasiewicz t-norm we obtain
{1/Populous, 1/Large}↓ (US) = min{1 ⇒ 0.23, 1 ⇒ 0.58} = 0.23.
Thus, unlike in the crisp case, the fuzzy semantics differ even for crisp sets of
attributes such as {1/Populous, 1/Large}.
Second, we can observe that in fuzzy DL concept descriptions on their own
are not fuzzy. The interpretations are fuzzy, the axioms are fuzzy, but the concept
descriptions themselves are not. By contrast, in fuzzy FCA it is possible to use
a fuzzy set of attributes to describe a class of objects.
To describe all countries that are (completely) huge and somewhat Asian,
one can use a fuzzy set of attributes {1/Large, 0.5/Asian}. Then in Table 2 the mem-
bership of Russia in the derivation {1/Large, 0.5/Asian}↓ is 1. By contrast, in DL it is
not possible to associate a truth degree with the concepts in a conjunction. The
best approximation of the above attribute set in DL is the simple conjunction
Large ⊓ Asian, which has, of course, a different semantics. In fact, Russia belongs
to (Large ⊓ Asian)I only with degree 0.75.4 In this respect fuzzy FCA is more
expressive than fuzzy DL.
Finally, fuzzy FCA typically uses hedges and fuzzy DL does not. In principle,
fuzzy FCA is more general here, since one could treat fuzzy DL as the special
3
Some authors use two types of conjunction: a strong conjunction interpreted by the
t-norm and a weak conjunction interpreted by the minimum. In this terminology,
we could write that fuzzy DL uses strong conjunction while fuzzy FCA uses weak
conjunction.
4
The Gödel t-norm is used to emphasize that this is independent of the first problem.
Adapting Fuzzy FCA for Fuzzy Description Logics 169
case where identity is used as the hedge. In practice, if identity is used as the
hedge, one cannot effectively compute a base in fuzzy FCA, at least not in the
settings that have previously been considered.
On the other hand, using globalization in combination with crisp sets of
attributes has practical limitations. Consider a fuzzy implication A → B. Using
the globalization as the hedge means, that all those counterexamples g ∈ G are
ignored that do not satisfy S(A, Ig ) = 1. This is particularly problematic, if we
only consider crisp left-hand sides A, since then
S(A, Ig ) = min (1 ⇒ I(g, m)) = min I(g, m). (6)
m∈A m∈A
If for just one m ∈ A the value I(g, m) is not 1 then S(A, Ig ) < 1 holds and the
object g is ignored. For example, in Table 2 if we consider A = {1/Large, 1/Populous}
then all objects are ignored, i.e. any implication with A as its left-hand side
holds. Presumably, in many applications values that differ from 1 are the rule
rather than the exception, meaning that almost all objects will be ignored.
4 Bridging the Gap
In the previous section we have identified the three aspects in which fuzzy DL
and fuzzy FCA disagree. We shall now consider a restricted subset of fuzzy FCA
for which the semantics agree. Unfortunately, it is not possible to use strong
conjunction instead of weak conjunction in fuzzy FCA, since the derivation op-
erators would no longer form a Galois-connection. Instead, we caution that the
following theory can only be applied directly in fuzzy DL with Gödel t-norm.
Since truly fuzzy implications have no equivalent in fuzzy DL, we only con-
sider implications A → B, where both sets A and B are crisp (from now on
called crisp implications). A similar idea has been proposed under the name of
“one-sided fuzzyness” in [16], with respect to concept lattices, not with respect
to bases. Instead of trying to compute a base that is complete for all fuzzy im-
plications we try to find a base that is complete only for crisp implications. In
standard fuzzy FCA there is a result, that allows one to consider only crisp sets
of fuzzy implications when searching for a base (Lemma 1 in [14]). Unfortunately,
this result cannot be applied in our restricted setting. Instead of computing a
crisp set containing fuzzy implications we compute a fuzzy set containing crisp
implications:
Problem 1. Given a fuzzy context K = (G, M, I) compute a fuzzy subset T of
{A → B | A, B ⊆ M } that is
– complete, i.e. for every implication A → B, A, B ⊆ M , kA → BkK = q
implies that A → B follows from T with degree q,
– sound, i.e. every implication A → B holds in K with degree at least T (A →
B), and
– irredundant, i.e. no fuzzy set U ( T is complete.
170 Felix Distel
Furthermore, we use identity as the hedge, thereby ensuring both compat-
ibility with DL and the use of all objects as potential counterexamples. These
three restrictions – Gödel t-norm, identity as the hedge, only crisp implications
– guarantee
d dthat A → B holds in the fuzzy induced context K of I to degree q
iff h A ⊑ B, qi holds in I. This is analogous to the crisp case.
4.1 Axiomatization
In [14] an axiomatic system is presented that can be used to infer all fuzzy
implications that follow from a crisp set of fuzzy implications. We present a
similar system of deduction rules, which can be used to infer for each crisp
implication the degree to which it follows from a fuzzy set of crisp implications.
Let L be a fuzzy subset of {A → B | A, B ⊆ M }. Our axiomatic system
consists of the following deduction rules, where q1 , q2 are positive truth values. In
each deduction step a new fuzzy subset Li+1 is obtained from the previous set Li ,
where L0 = L. For all implications E → F we define Li+1 (E → F ) = Li (E → F )
unless mentioned otherwise in the rules.
(Refl) From A ⊆ B and Li (A → B) < 1 infer Li+1 (A → B) = 1
(Union) From Li (A → B) = q1 , Li (A → C) = q2 and Li (A → B ∪ C) <
min{q1 , q2 } infer Li+1 (A → B ∪ C) = min{q1 , q2 }
(Trans) From Li (A → B) = q1 , Li (B → C) = q2 and Li (A → C) < q1 ⊗ q2
infer Li+1 (A → C) = q1 ⊗ q2 .
In each of the three rules the inferred implication obtains a membership
degree that is smaller or equal to the membership degrees of the rules in the pre-
condition. Since a rule can only be applied if the degree of the inferred implication
strictly increases, no implication can ever be used in its own deduction implicitly
or explicitly. There are only finitely many crisp implications and therefore the
deduction process must terminate. We now want to show that the deduction
system is sound, in the sense that if after a finite number k of deduction steps
we can deduce Lk (A → B) = q then A → B follows from L with at least degree
q, and complete in the sense that if A → B follows from L with degree q then
Lk (A → B) = q can be deduced.
Lemma 1. (Refl)–(Trans) is a sound and complete system of deduction rules.
Proof. To prove soundness, we prove that each rule application does not change
the models, i.e. that every model U of Li is a model of Li+1 . The converse that
every model of Li+1 is a model of Li is trivial, since Li ⊆ Li+1 . Soundness of
(Refl) is also trivial. Soundness of (Union): Assume that U is a model of Li . We
define α = minm∈A U (m), β = minm∈B U (m) and γ = minm∈C U (m). From (6)
and (4) we obtain
kA → BkU = α ⇒ β, kA → CkU = α ⇒ γ, kA → B ∪ CkU = α ⇒ min{β, γ}.
Monotonicity of the residuum yields kA → B ∪ CkU = min{α ⇒ β, α ⇒ γ} ≥
min{q1 , q2 }. This proves that U is also a model of Li+1 , which suffices to prove
Adapting Fuzzy FCA for Fuzzy Description Logics 171
soundness of (Union). Soundness of (Trans): Since U is a model of Li we obtain
from the preconditions α ⇒ β ≥ q1 and β ⇒ γ ≥ q2 . Using (1) we obtain α⊗q1 ≤
β and β ⊗ q2 ≤ γ. From monotonicity of the t-norm we obtain α ⊗ (q1 ⊗ q2 ) ≤ γ.
Using (1) again we get q1 ⊗ q2 ≤ α ⇒ γ = kA → CkU . Hence, U is a model of
Li+1 , which proves soundness of (Trans).
Completeness: Let X → Y be an implication that follows (semantically) from
L to degree q. Let Lk be the fuzzy set of implications obtained after exhaustively
applying the deduction rules. To prove completeness it suffices to show that that
Lk (X → Y ) ≥ q.
As a preliminary step, let us define the following fuzzy set X + (m) = Lk (X →
{m}) and show that it is a model of L. Assume that X + is not a model of L,
i.e. kA → BkX + < L(A → B) for some implication A → B. We use the notation
α = minm∈A X + (m) and β = minm∈B X + (m). Then kA → BkX + = α ⇒ β <
L(A → B), or equivalently by (1)
α ⊗ L(A → B) > β. (7)
On the other hand X + (a) = Lk (X → {a}) ≥ α holds for all a ∈ A. Because
the rules have been applied exhaustively to obtain Lk (Union) is not applicable
to Lk and therefore Lk (X → A) ≥ α. Using a similar argument for (Trans) we
obtain
Lk (X → B) ≥ Lk (X → A) ⊗ Lk (A → B) ≥ α ⊗ L(A → B),
where we have exploited the fact that truth values can only increase when a
rule is applied and therefore L(A → B) ≤ Lk (A → B). Finally, using (Refl)
and (Trans) it follows that Lk (X → {b}) ≥ α ⊗ L(A → B) for all b ∈ B. This
contradicts (7) and thus X + must be a model of L.
Since X → Y follows from L to degree q it must hold that
q ≤ kX → Y kX + = min X + (x) ⇒ min X + (y) = min X + (y).
x∈X y∈Y y∈Y
+
Therefore Lk (X → {y}) = X (y) ≥ q for all y ∈ Y . Since (Union) cannot be
applied to Lk we obtain Lk (X → Y ) ≥ q which proves completeness. ⊔
⊓
4.2 Stem Base
We now provide a practical approach for computing a finite base for the Gödel
t-norm, the only t-norm for which the semantics of fuzzy FCA and fuzzy DL
coincide. Assume that we are given a finite fuzzy context K = (G, M, I). Let QK
be the set containing 1 and all truth degrees that occur in K. Let q0 ∈ [0, 1] be a
fixed truth degree. We define a crisp context Kq0 = (Gq0 , M, Iq0 ) as follows. For
each g ∈ G and each q ∈ QK with q < q0 the set Gq0 contains an object gq with
{gq }′ = {m ∈ M | I(g, m) > q},
i.e. gq has exactly those attributes that g has with degree higher than q. As an
example, consider a context K of South American Countries (Table 3).5
5
The value for HighGDP is the fraction of the country’s GDP per capita and the GDP
per capita of Chile, the largest in South America. Similarly for the other values.
172 Felix Distel
Algorithm 1 Computing a Minimal Base with Gödel t-Norm
B=L=∅
for all q ∈ QK in decreasing order do
D = DG B (Kq )
B =B∪D
L = L ∪ {q/A→B | A → B ∈ D}
end for
return L
Lemma 2. A → B holds in K with at least degree q0 iff A → B holds in Kq0 .
Proof. Assume that A → B holds in K with degree less than q0 . According to
(4) and the definition of the Gödel-residuum this is equivalent to
min kA → BkIg < q0
g∈G
⇐⇒ ∃g ∈ G : min I(g, a) ⇒ min I(g, b) < q0
a∈A b∈B (8)
⇐⇒ ∃g ∈ G : min I(g, b) < q0 and min I(g, a) > min I(g, b)
b∈B a∈A b∈B
⇐⇒ ∃g ∈ G : ∃b ∈ B : I(g, b) < q0 and ∀a ∈ A : I(g, a) > I(g, b).
I(g, b) is a truth degree from QK and gI(g,b) satisfies (gI(g,b) , b) ∈ / Iq0 and
(gI(g,b) , a) ∈ Iq0 for all a ∈ A. Therefore, Kq0 contains a counterexample to
A → B, hence A → B does not hold in Kq0 .
On the other hand if A → B does not hold in Kq0 then there must be some gq ,
q < q0 such that A ⊆ {gq }′ and B 6⊆ {gq }′ . By definition of {gq }′ this is equivalent
to I(gq , a) > q for all a ∈ A and I(gq , b) ≤ q for some b ∈ B. Since q < q0 it
holds that for this value b in particular I(gq , b) < q0 and I(gq , a) > I(gq , b) for
all a ∈ A. It then follows from (8) that A → B does not hold in K with at least
degree q0 . ⊔
⊓
Notice, that if q1 < q0 then Gq1 ⊆ Gq0 and Iq1 ⊆ Iq0 . This observation, to-
gether with Lemma 2, suggests a levelwise approach as sketched in Algorithm 1.
One starts with the largest value qmax in QK and computes the Duquenne-
Guigues Base for Kqmax . The base serves two purposes. Its implications are added
to the fuzzy set of implications L with degree q, and it serves as background
knowledge in the next iteration. For the context from Table 3 Algorithm 1 yields
the base {1/{Populous,Small}→{HighGDP}, 0.9/{Populous}→{HighGDP}, 0.2/∅→{HighGDP}}.
Lemma 3. Upon termination Algorithm 1 returns a fuzzy set of crisp implica-
tions L that is sound and complete for Kq and has minimal cardinality among
all such sets.
Proof. Soundness follows immediately from Lemma 8. To prove completeness,
assume that U → V holds in K with degree q ∈ QK (notice that for the Gödel
t-norm it always holds that kU → V kK ∈ QK ). Then by Lemma 8 U → V holds
Adapting Fuzzy FCA for Fuzzy Description Logics 173
Table 3. South American Countries Table 4. K1
Populous HighGDP Small Populous HighGDP Small
Argentina 0.2 0.8 0.6 Argentina0.6 ×
Bolivia 0.1 0.2 0.9 Argentina0.2 × ×
Brazil 1.0 0.9 0.0 Bolivia0.2 ×
Chile 0.1 1.0 0.9 Bolivia0.1 × ×
Colombia 0.2 0.5 0.9 Brazil0.9 ×
Ecuador 0.1 0.3 1.0 Brazil0.0 × ×
Guyana 0.0 0.2 1.0 Chile0.9 ×
Paraguay 0.0 0.2 1.0 Chile0.1 × ×
Suriname 0.0 0.5 1.0 Colombia0.5 ×
Uruguay 0.0 1.0 1.0 Colombia0.2 × ×
Venezuela 0.1 0.7 0.9 Ecuador0.3 ×
Ecuador0.1 × ×
Guyana0.2 ×
Guyana0.0 × ×
Paraguay0.2 ×
Paraguay0.0 × ×
Suriname0.5 ×
Suriname0.0 × ×
Uruguay0.0 × ×
Venezuela0.7 ×
Venezuela0.1 × ×
in Kq . Consider D, V and L after the iteration for q in Algorithm 1. Since D ∪ B
is complete for Kq and U → V holds in Kq the implication U → V follows from
D ∪ B = {A → B | L(A → B) ≥ q} in the crisp setting.
We show that then U → V follows to degree q from L in the fuzzy setting.
Assume the contrary, i.e. that there exists a context K̄ for which L is sound,
but in which U → V does not hold to degree at least q. By Lemma 8 this yields
that U → V does not hold in K̄q while all implications from D ∪ B = {A → B |
L(A → B) ≥ q} do hold in K̄q . Because we have shown that U → V follows
from D ∪ B in the crisp setting this is a contradiction. Hence U → V follows to
degree q from L, which proves completeness.
Assume that L̄ is another sound and complete fuzzy set of implications for
K. Then by Lemma 8 for each q ∈ QK the crisp set
L̄q = {A → B | L(A → B) ≥ q}
must be sound and complete for Kq . A simple induction over q ∈ QK can be used
to show that |L̄q | ≥ |Lq | for all q ∈ QK . For q maximal in QK the claim follows
directly from minimality of the Duquenne-Guigues Base. For the induction step
let q ∈ QK where |L̄q̄ | ≥ |Lq̄ | holds for the next larger value q̄ ∈ QK . Both Lq̄
and L̄q̄ are sound and complete for Kq̄ ,in particular they have the same models.
Thus, L̄q = L̄q \ L̄q̄ ∪ L̄q̄ and L̄q \ L̄q̄ ∪ Lq̄ also have the same models, and are
thus both sound and complete for Kq . Minimality of the Lq̄ -Duquenne-Guigues
base implies |L̄q \ L̄q̄ | ≥ |DG Lq̄ (Kq )|. This proves
|L̄q | = | L̄q \ L̄q̄ | + |L̄q̄ | ≥ |DG Lq̄ (Kq )| + |Lq̄ | = |Lq |.
Since this holds for all q ∈ QK we get that L has minimal cardinality among all
bases. ⊔
⊓
174 Felix Distel
5 Conclusion
We have restricted fuzzy FCA by allowing only crisp sets of attributes in the
implications and using identity as the hedge. We have presented a sound and
complete set of deduction rules for this restricted setting. For the Gödel t-norm
the restricted setting corresponds semantically to fuzzy DL. Furthermore, we
have presented a simple algorithm for computing a minimal base for the re-
stricted setting. In the general setting this is only possible with globalization.
We do not claim, that this restriction of expressivity is the only feasible
approach for reconciling the differences between the two fields. In future work it
would be interesting to look at a kind of weighted conjunction in DL (imitating
the semantics of fuzzy attribute sets). It would also be interesting to consider a
version of fuzzy FCA that uses strong conjunction.
References
1. Hájek, P.: Metamathematics of Fuzzy Logic (Trends in Logic). Springer (2001)
2. Belohlavek, R.: Fuzzy Relational Systems: Foundations and Principles. Kluwer
(2002)
3. García-Cerdaña, Á., Armengol, E., Esteva, F.: Fuzzy description logics and t-norm
based fuzzy logics. Int. J. of Approx. Reasoning 51 (2010) 632–655
4. Sertkaya, B.: Computing the hierarchy of conjunctions of concept names and their
negations in a description logic knowledge base using formal concept analysis. In:
Cont. to ICFCA’06, Dresden, Germany (2006) 73–86
5. Baader, F., Ganter, B., Sattler, U., Sertkaya, B.: Completing Description Logic
knowledge bases using Formal Concept Analysis. In: IJCAI’07. (2007)
6. Rudolph, S.: Exploring relational structures via FLE. In: Conceptual Structures
at Work. Springer (2004) 233–233
7. Distel, F.: Learning Description Logic Knowledge Bases from Data Using Methods
from Formal Concept Analysis. PhD thesis, TU Dresden (2011)
8. Belohlavek, R., Vychodil, V.: Attribute implications in a fuzzy setting. In:
ICFCA’06. Springer (2006) 45–60
9. Belohlavek, R., Chlupova, M., Vychodil, V.: Implications from data with fuzzy
attributes. In: AISTA’04. (2004)
10. Bobillo, F., Delgado, M., Gómez-Romero, J., Straccia, U.: Fuzzy description logics
under Gödel semantics. Int. J. of Approx. Reasoning 50(3) (2009) 494–514
11. Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations.
Springer, New York (1997)
12. Guigues, J.L., Duquenne, V.: Familles minimales d’implications informatives ré-
sultant d’un tableau de données binaires. Math. Sci. Humaines 95 (1986) 5–18
13. Stumme, G.: Attribute exploration with background implications and exceptions.
In: Data Analysis and Inf. Sys., Berlin, Springer (1996) 457ff
14. Belohlavek, R., Vychodil, V.: Axiomatizations of fuzzy attribute logic. In: IICAI’05.
(2005)
15. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F.,
eds.: The Description Logic Handbook: Theory, Implementation, and Applica-
tions. Cambridge University Press (2003)
16. Krajči S.: Cluster based efficient generation of fuzzy concepts. Neural Network
World 5 (2003), 521–530