=Paper=
{{Paper
|id=None
|storemode=property
|title=Using Taxonomies on Objects and Attributes to Discover Generalized Patterns
|pdfUrl=https://ceur-ws.org/Vol-972/paper28.pdf
|volume=Vol-972
|dblpUrl=https://dblp.org/rec/conf/cla/KwuidaMV12
}}
==Using Taxonomies on Objects and Attributes to Discover Generalized Patterns==
https://ceur-ws.org/Vol-972/paper28.pdf
Using Taxonomies on Objects and Attributes to
Discover Generalized Patterns
Léonard Kwuida1 , Rokia Missaoui2⋆ , Jean Vaillancourt2
1
Bern University of Applied Sciences
kwuida@gmail.com
2
Université du Québec en Outaouais
{rokia.missaoui,jean.vaillancourt}@uqo.ca
Abstract. In this paper, we show how the existence of taxonomies on
objects and/or attributes can be used in formal concept analysis to help
discover generalized patterns in the form of concepts. To that end, we an-
alyze three generalization cases and different scenarios of a simultaneous
generalization on both objects and attributes.
We also contrast the number of generalized patterns against the number
of simple patterns.
1 Introduction
In many real-life applications and research trends in Computer Science, the se-
mantics of data can be advantageously exploited to better retrieve and efficiently
manage information and discover unexpected and relevant patterns which are a
concise and semantically rich representation of data. Patterns can be clusters,
concepts, association rules, outliers, and so on. In this work we analyze some
possible ways to abstract or group objects and/or attributes together to get
generalized concepts by using taxonomies on attributes and/or objects.
Formal Concept Analysis (FCA) is a formalism for knowledge representation
which is based on the formalization of “concepts” and “concept hierarchies” [6].
One recurrent problem in FCA is the number of concepts that can be exponential
in the size of the context. To handle this problem many techniques have been
proposed [2] to use or produce a taxonomy on attributes or objects to control
the size of the context and the corresponding concept lattice.
The rest of this contribution is organized as follows. In Section 2 we intro-
duce the basic notions of FCA. Section 3 presents three different generalization
schemes, and discusses different scenarios of generalizing both objects and at-
tributes. In Section 4 we discuss the visualization issue of generalized patterns
and provide the real meaning of the three generalization cases. In Section 5 the
size of the generalized concept set is compared to the size of the initial (i.e.,
before generalization) concept set. Finally, existing work about combining FCA
with ontology is briefly described in Section 6.
⋆
The second author acknowledges the financial support of the Natural Sciences and
Engineering Research Council of Canada (NSERC).
c 2012 by the paper authors. CLA 2012, pp. 327–338. 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.
328 Léonard Kwuida, Rokia Missaoui and Jean Vaillancourt
2 Formal Concept Analysis and Data Mining
2.1 Elementary information systems, contexts and concepts
In formal concept analysis, a context is a triple
K := (G, M, I) where G, M and I stand for a set K a b c d e f g h
of objects, a set of attributes, and a binary relation 1 × × ×
between G and M respectively. A formal concept 2 × ×× ×
is a pair (A, B) such that B is exactly the set of all 3 × × ×××
properties shared by the objects in A and A is the 4 × ××××
set of all objects that have all the properties in B. 5 × × ×
We set A′ := {m ∈ M | aIm for all a ∈ A} and 6 ××××
B ′ := {g ∈ G | gIb for all b ∈ B}. Then (A, B) 7 ×× ×
is a concept of K iff A′ = B and B ′ = A. The 8 ××× ×
extent of the concept (A, B) is A while its intent
is B. We denote by B(K), Int(K) and Ext(K) the Fig. 1: A formal context
set of concepts, intents and extents of the formal
context K, respectively. A subset X is closed if X ′′ = X. Closed subsets of G are
exactly extents while closed subsets of M are intents of K. Figure 1 describes
items a, . . . , h that appear in eight transactions (customers) of a market basket
analysis application. Such a setting defines a binary relation I between the set
G of objects/transactions and the set M of properties/items.
The concept hierarchy is formalized with a relation ≤ defined on B(K) by
A ⊆ C ⇐⇒ : (A, B) ≤ (C, D) : ⇐⇒ B ⊇ D. This is an order relation, and is
also called a specialization/generalization relation on concepts. In fact, a concept
(A, B) is called a specialization of a concept (C, D), or (C, D) is a generalization
of (A, B) iff (A, B) ≤ (C, D) holds. For any list C of concepts of K, there is a
concept u of K which is more general than every concept in C and is a special-
ization of everyWgeneralization of all concepts in C (u is the supremum of C and
is denoted by C), and there is a concept v of K which is a specialization of
every concept in C and a generalization of every V specialization of all concepts in
C (v is the infimum of C and is denoted by C)3 . Hence, B(K) is a complete
lattice called the concept lattice of the context K.
For g ∈ G and m ∈ M we set g ′ := {g}′ and m′ := {m}′ . The object concepts
(γg := (g ′′ , g ′ ))g∈G and the attribute concepts (µm := (m′ , m′′ ))m∈M form the
“building blocks” of B(K). In fact, every concept of K is a supremum of some
4
W
γg’s and infimum of some V µm’s . Thus, the set {γg | g ∈ G} is -dense and the
set {µm | m ∈ M } is -dense in B(G, M, I).
The size of a concept lattice can be extremely large, even exponential in the
size of the context. To handle such large sets of concepts many techniques have
been proposed [6], based on context decomposition or lattice pruning/reduction
(atlas decomposition, direct or subdirect decomposition, iceberg concept lattices,
3 W V
For two concepts x1 and x2 we set_x1 ∨ x2 := {x1 , x^
2 } and x1 ∧ x2 := {x1 , x2 }.
4
For (A, B) ∈ B(G, M, I) we have γg = (A, B) = µm.
g∈A m∈B
Discovering Generalized Patterns using Taxonomies 329
nested line diagrams, . . . ). We believe that using taxonomies on objects and at-
tributes can contribute to the extraction of unexpected and relevant generalized
patterns and in most cases to the reduction of the size of discovered patterns.
2.2 Labeled line diagrams of concept lattices
One of the strengths of
FCA is the ability to
pictorially display knowl-
edge, at least for contexts
of reasonable size. Finite
concept lattices can be
represented by reduced
labeled Hasse diagrams
(see Figure 2). Each node
represents a concept. The
label g is written below
γg and m above µm. The
extent of a concept rep-
resented by a node a is
given by all labels in G
from the node a down-
wards, and the intent by
all labels in M from a up- Fig. 2: Concept lattice of the context in Fig 1
wards. For example, the
label 5 in the left side of Figure 2 represents the object concept γ5 =
({5, 6}, {a, c, d}). Diagrams are valuable tools for visualizing data. However draw-
ing a good diagram for complex structures is a big challenge. Therefore, we need
tools to abstract the output by reducing the size of the input, making the struc-
ture nicer, or by exploring the diagram layer by layer. For the last case, FCA
offers nested line diagrams as a means to visualize the concepts level-wise [6].
Before we move to generalized patterns, let us see how data are transformed
into binary contexts, the suitable format for our data.
2.3 Information Systems
Frequently, data are not directly encoded in a “binary” form, but rather as a
many-valued context, i.e., a tuple (G, M, W, I) such that G is the set of objects,
M the set of attribute names, W the set of attribute values, I ⊆ G × M × W
and every m ∈ M is a partial map from G to W with (g, m, w) ∈ I iff m(g) = w.
Many-valued contexts can be transformed into binary contexts, via conceptual
scaling. A conceptual scale for an attribute m of (G, M, W, I) is a binary context
Sm := (Gm , Mm , Im ) such that m(G) ⊆ Gm . Intuitively, Mm discretizes or
groups the attribute values into m(G), and Im describes how each attribute
value m(g) is related to the elements in Mm . For an attribute m of (G, M, W, I)
and a conceptual scale Sm we derive a binary context Km := (G, Mm , I m ) with
330 Léonard Kwuida, Rokia Missaoui and Jean Vaillancourt
gI m sm : ⇐⇒ m(g)Im sm , where sm ∈ Mm . This means that an object g ∈ G is
in relation with a scaled attribute sm iff the value of m on g is in relation with
sm in Sm . With a conceptual scale
S for each attribute we get the derived context
KS := (G, N, I S ) where N := {Mm | m ∈ M } and gI S sm ⇐⇒ m(g)I m sm . In
practice, the set of objects remains unchanged; each attribute name m is replaced
by the scaled attributes sm ∈ Mm . The choice of a suitable set of scales depends
on the interpretation, and is usually done with the help of a domain expert. A
Conceptual Information System is a many-valued context together with a set of
conceptual scales [9, 12]. The methods presented in Section 3 are actually a form
of scaling.
3 Generalized Patterns
In the field of data mining, generalized patterns are pieces of knowledge ex-
tracted from data when an ontology is used. In the following we formalize the
way generalized patterns are produced. Let K := (G, M, I) be a context. The at-
tributes of K can be grouped together to form another set of attributes, namely
S, to get a context where the attributes are more general than in K. For the
basket market analysis example, items/products can be generalized into product
lines and then product categories, and customers may be generalized to groups
according to some specific features (e.g., income, education). The context K is
then replaced with a context (G, S, J) as in the scaling process where S can be
seen as an index set such that {ms | s ∈ S} covers M . We will usually identify
the group ms with the index s.
3.1 Types of Generalization
There are mainly three ways to express the relation J:
(∃) g J s : ⇐⇒ ∃m ∈ s, g I m. Consider an information table describing compa-
nies and their branches in USA. We first set up a context whose objects are
companies and whose attributes are the cities where these companies have
branches. If there are too many cities, we can decide to group them into
states to reduce the number of attributes. Then, the (new) set of attributes
is now a set S whose elements are states. It is quite natural to assert that
a company g has a branch in a state s if g has a branch in a city m which
belongs to the state s.
(∀) g J s : ⇐⇒ ∀m ∈ s, g I m. Consider an information system about Ph.D.
students and the components of the comprehensive exam (CE). Assume that
components are: the written part, the oral part, and the thesis proposal, and
a student succeeds in his exam if he succeeds in the three components of
that exam. The objects of the context are Ph.D. students and the attributes
are the different exams taken by students. If we group together the different
components, for example
CE.written, CE.oral, CE.proposal 7→ CE.exam,
Discovering Generalized Patterns using Taxonomies 331
then it becomes natural to state that a student g succeeds in his compre-
hensive exam CE.exam if he succeeds in all the exam parts of CE.
| g I m}|
(α%) g J s : ⇐⇒ |{m∈s |s| ≥ αs where αs is a threshold set by the user
1
for the generalized attribute s. This case generalizes the (∃)-case (α = |M |)
and the (∀)-case (α = 1). To illustrate this case, let us consider a context
describing different specializations in a given Master degree program. For
each program there is a set of mandatory courses and a set of optional ones.
Moreover, there is a predefined number of courses that a student should suc-
ceed to get a degree in a given specialization. Assume that to get a Master in
Computer Science with a specialization in “computational logic”, a student
must succeed seven courses from a set s1 of mandatory courses and three
courses from a set s2 of optional ones. Then, we can introduce two general-
ized attributes s1 and s2 so that a student g succeeds in the group s1 if he
succeeds in at least seven courses from s1 , and succeeds in s2 if he succeeds
in at least three courses from s2 . So, αs1 := |s71 | , αs2 := |s32 | , and
|{m ∈ si | g I m}|
g J si ⇐⇒ ≥ αsi , 1 ≤ i ≤ 2.
|si |
K∃−∀−α a b c d e f g h A B C D S T U V E F H
1 × × × × × ×
2 × ×× ×× ×× × ×
3 ×× ××× ××××× ××
4 × ×××××× ×× × ××
5 × ×× ×× × ×
6 ×××× ×× ×× ×
7 ×× × ×× × ×
8 ××× × ××× × ×
Fig. 3: Three generalizations of the context in Fig. 1 (see Subsection 3.1). The ∃-
generalized attributes are A := {e, g}, B := {b, c}, C := {a, d} and D := {f, h}.
The ∀-generalized attributes are S := {e, g}, T := {b, c}, U := {a, d} and V := {f, h}.
The α-generalized attributes are E := {a, b, c}, F := {d, e, f } and H := {g, h} with
α = 60%.
The α-case discussed here generalizes the alpha Galois lattices investigated
by Ventos et al [14, 10]. In fact, if the set S forms a partition of M and all αs
are equal, then the generalization is an alpha Galois lattice.
Attribute generalization reduces the number of attributes. One may there-
fore expect a reduction in the number of concepts. Unfortunately, this is not
always the case. Therefore, it is interesting to investigate under which condition
generalizing patterns leads to a “generalized” lattice of smaller size than the ini-
tial one. Moreover, finding the connections between the implications and more
generally association rules of the generalized context and the initial one is also
an important problem to be considered.
332 Léonard Kwuida, Rokia Missaoui and Jean Vaillancourt
Fig. 4: Lattices of contexts in Fig 3. ∃-generalization (left), ∀-generalization (middle)
and α-generalization (right)
If data represent customers (transactions) and items (products), the usage
of a taxonomy on attributes leads to new useful patterns that could not be seen
before generalizing attributes. For example, the ∃-case (see Figure 4, left) helps
the user acquire the following knowledge:
– Customer 3 (at the bottom of the lattice) buys at least one item from each
product line
– Whenever a customer buys at least one item from the product line D, then
he/she buys at least one item from the product line A.
From the ∀-case in Figure 4 (middle), one may learn for example that Customers
4 and 6 have distinct behaviors in the sense that the former buys all the items of
the product lines V and S while the latter purchases all the items of the product
lines U and T .
To illustrate the α-case, we put the attributes of M in three groups E :=
{a, b, c}, F := {d, e, f } and H := {g, h} and set α := 60% for all groups. This
α-generalization on the attributes of M is presented in Figure 4 (right). Note
that if all groups have two elements, then any α-generalization would be either
an ∃-generalization (α ≤ 0.5) or a ∀-generalization (α > 0.5). From the lattice in
Figure 4 (right) one can see that any customer buying at least 60% of items in
H necessarily purchases at least 60% of items in F . Moreover, the product line
E (respectively H) seems to be the most (resp. the less) popular among the four
product lines since five out of eight customers (resp. only one customer) bought
at least 60% of items in E (resp. H).
Generalization can also be conducted on objects to replace some (or all) of
them with generalized objects, or even more, can be done simultaneously on
objects and attributes.
3.2 Generalization on Objects and Attributes
Done simultaneously on attributes and on objects, the generalization will give a
kind of hypercontext (similar to hypergraphs [1]), since the objects are subsets
of G and attributes are subsets of M . Let A be a group of objects and B be a
group of attributes related to a context K. Then, the relation J can be defined
using one or a combination of the following cases:
1. A J B iff ∃a ∈ A, ∃b ∈ B such that a I b, i.e. some objects from the group A
are in relation with some attributes in the group B;
Discovering Generalized Patterns using Taxonomies 333
2. A J B iff ∀a ∈ A, ∀b ∈ B a I b, i.e. every object in the group A is in relation
with every attribute in the group B;
3. A J B iff ∀a ∈ A, ∃b ∈ B such that a I b, i.e. every object in the group A has
at least one attribute from the group B;
4. A J B iff ∃b ∈ B such that ∀a ∈ A a I b, i.e. there is an attribute in the group
B that belongs to all objects of the group A;
5. A J B iff ∀b ∈ B, ∃a ∈ A such that a I b, i.e. every property in the group B is
satisfied by at least one object of the group A;
6. A J B iff ∃a ∈ A such that ∀b ∈ B a I b, there is an object in the group A
that has all the attributes in the group B;
|{b∈B|a I b}|
{a∈A| |B|
≥βB }
7. A J B iff |A| ≥ αA , i.e. at least αA fraction of objects in
the group A have each at least β fraction of the attributes in the group B;
B
|{a∈A|a I b}|
b∈B| |A|
≥α A
8. A J B iff |B| ≥ βB , i.e. at least βB % of attributes in the
group B belong altogether to at least αA % of objects in the group A;
9. A J B iff |A×B∩I|
|A×B| ≥ α, i.e. the density of the rectangle A × B is at least equal
to α.
1 1
Remark 1. The cases 7 and 8 generalize Case 1 (αA := |G| , βB := |M | for all A
and B) and Case 2 (αA := 1, βB := 1 for all A and B). Moreover, Case 7 also
1 1
generalizes Case 3 (αA := 1, βB := |M | for all A and B) and Case 5 (αA := |G| ,
βB := 1 for all A and B). However, Cases 4 and 6 cannot be captured by Case 7,
1
but are captured by Case 8 (αA := 1, βB := |M | for all A and B to get Case 4,
1
and αA := |G| , βB := 1 for all A and B to get Case 6).
An example of generalization on both objects and attributes would be one of
customers grouped according to some common features and items grouped into
product lines. We can also assign to each group all items bought by their members
(an ∃-generalization) or only their common items (a ∀-generalization), or just
some of the frequent items among their members (similar to an α-generalization).
4 Visualizing Generalized Patterns on Line diagrams
4.1 Visualization
Let K be a formal context and (G, S, J) a context obtained from K via a gener-
alization on attributes. The usual action is to directly construct a line diagram
of (G, S, J) which contains concepts with generalized attributes (See Fig 4).
However, one may be interested, after getting (G, S, J) and constructing a line
diagram for B(G, S, J), to refine further on the attributes in M or recover the
lattice constructed from K.
When storage space is not a constraint, then the attributes in M and the
generalized attributes can be kept altogether. This is done using the apposition
of K := (G, M, I) and (G, S, J) to get (G, M ∪ S, I ∪ J).
334 Léonard Kwuida, Rokia Missaoui and Jean Vaillancourt
A nested line diagram [6]
can be used to display the re-
sulting lattice, with (G, S, J)
at the first level and K at the
second one, i.e., we construct
a line diagram for B(G, S, J)
with nodes large enough to
contain copies of the line di-
agram of B(K). The general-
ized patterns can then be vi-
sualized by conducting a pro-
jection (i.e., a restricted view) Fig. 5: Projection of the lattice in Figure 2 onto
on generalized attributes, and the ∀-generalized attributes.
keeping track of the effects of
the projection, i.e, we display the projection of the concept lattice B(G, M ∪
S, I ∪ J) on S by marking the equivalence classes on B(G, M ∪ S, I ∪ J). Note
that two concepts (A, B) and (C, D) are equivalent with respect to the projec-
tion on S iff B ∩ S = D ∩ S (i.e., their intents have the same restriction on S
[8]). This is illustrated by Figure 5.
4.2 Are generalized attributes really generalizations?
For attributes a, b ∈ M ∪ S,
we should normally assert
that a is a generalization of
b or b is a specialization of
a whenever µa ≥ µb. For
the ∃-case we have, m′s =
{m′ | m ∈ ms }. Thus,
S
µms ≥ µm for all m ∈ ms ;
i.e. ms is really a gener-
alization of the attributes
m ∈ ms .
ForTthe ∀-case we have,
m′s = {m′ | m ∈ ms }. Thus,
µms ≤ µm, ∀m ∈ ms ; i.e.
ms is rather a specialization
of the attributes m ∈ ms .
1
For the α-case, |M | < α < 1,
Fig. 6: α-generalization with µEkµb. E = {a, b, c},
an object g ∈ G is in rela-
F = {d, e, f }, H = {g, h}, α = 0.6.
tion with an attribute ms
s |g I m}|
iff α ≤ |{m∈m |ms | . The following situations can happen:
– There is an α-generalized attribute ms ∈ S with at least one attribute m ∈
ms such that g6 Im and g J ms ; hence µm µms in B(G, M ∪ S, I ∪ J); i.e
µms is not a generalization of µm.
Discovering Generalized Patterns using Taxonomies 335
– There is an α-generalized attribute ms ∈ S with at least one attribute m ∈
ms such that g I m and g6 Jms ; hence µms µm in B(G, M ∪ S, I ∪ J); i.e
µms is not a specialization of µm.
Therefore, there are α-generalized attributes ms that are neither a gener-
alization of the m’s nor a specialization of the m’s. In Figure 6, the element b
belongs to the group E, but µE is neither a specialization nor a generalization
of µb, since µb µE and µE µb. Thus, we should better call the α-case
an attribute approximation, the ∀-case a specialization and only the ∃-case a
generalization.
5 Controlling the size of generalized concepts
A generalized concept is a concept whose intent (or extent) contains generalized
attributes (or objects). Figure 7 displays an ∃-generalization that leads to a
larger number of concepts. The two concepts µm1 and µm2 will be put together.
Although attributes m1 and m2 are replaced with m12 , the nodes γg2 and γg3 will
remain since they will be obtained as µm12 ∧ µm4 and µm12 ∧ µm3 respectively.
Then we get the configuration on Figure 7 (right) which has one concept more
than the initial concept lattice shown in the left of the same figure.
In the following, we analyze the impact of ∃ and ∀ attribute generalizations
on the size of the resulting set of generalized concepts.
5.1 An ∃-generalization on attributes
Let (G, M, I) be a context and
(G, S, J) a context obtained from an
∃-generalization on attributes, i.e the
elements of S are groups of attributes
from M . We set S = {ms | s ∈ S},
with ms ⊆ M . Then, an object g ∈ G
is in relation with a generalized at-
tribute ms if there is an attribute m
in ms such that g I m. To compare the
size of the corresponding concept lat- Fig. 7: An ∃-generalization (right) in-
tices, we can define some mappings. creasing the size of the initial lattice
We assume that (ms )s∈S forms a par- (left). m = {m , m }.
12 1 2
tition of M . Then for each m ∈ M
there is a unique generalized attribute ms such that m ∈ ms , and g I m implies
g J ms , for every g ∈ G. To distinguish between derivations in (G, M, I) and in
(G, S, J), we will replace ′ by the name of the corresponding relation. For exam-
ple g I = {m ∈ M | g I m} and g J = {s ∈ S | g J s}. Two canonical maps α and
β are defined as follows:
α : G → B(G, S, J) β : M → B(G, S, J)
and
g 7→ γ̄g := (g J J , g J ) m 7→ µ̄ms := (sJ , sJ J ), where m ∈ ms
336 Léonard Kwuida, Rokia Missaoui and Jean Vaillancourt
The maps α and β induce two order preserving maps ϕ and ψ defined by
ϕ : B(G, M, I) → W
B(G, S, J) ψ : B(G, M, I) → V
B(G, S, J)
and
(A, B) 7→ {αg | g ∈ A} (A, B) 7→ {βm | m ∈ B}
If ϕ or ψ is surjective, then the generalized context is of smaller cardinality.
As we have seen on Figure 7 these maps can be both not surjective. Obviously
ϕ(A, B) ≤ ψ(A, B) since g I m implies g J ms and γ̄g ≤ µm¯ s . When do we have
the equality? Does the equality imply surjectivity?
Here are some special cases where the number of concepts does not increase
after a generalization.
Case 1 Every ms has a greatest element ⊤s . Then the context (G, S, J) is a
projection of (G, M, I) on the set MS := {⊤s | s ∈ S} of greatest elements
of ms . Thus B(G, S, J) ∼= B(G, MS , I ∩ (G × MS )) and is a sub-order of
B(G, M, I). Hence |B(G, S, J)| = |B(G, MS , I ∩ G × MS )| ≤ |B(G, M, I)|.
Case 2 {mI | m ∈ ms } is an extent, for any ms ∈ S. Then any grouping does
S
not produce a new concept. Hence the number of concepts cannot increase.
The following result (Theorem 1) gives an important class of lattices for which
the ∃-generalization does not increase the size of the lattice. A context is object
reduced if no row can be obtained as the intersection of some other rows.
Theorem 1. The ∃-generalizations on distributive concept lattices whose con-
texts are object reduced decrease the size of the concept lattice.
Proof. Let (G, M, I) be an object reduced context such that B(G, M, I) is a
distributive lattice. Let (G, S, J) be a context obtained by an ∃-generalization on
the attributes in M . Let ms be a generalized attribute, i.e. a group of attributes
of M . It is enough to prove that mJs is an extent of (G, M, I). By definition,
[ [ II _
mJs = {mI | m ∈ ms } ⊆ {mI | m ∈ ms } = ext {µm | m ∈ ms }
W W
For any g ∈ ext( {µm | m ∈ ms }) we have γg ≤ {µm | m ∈ ms } and
_ _
γg = γm∧ {µm | m ∈ ms } = {γg∧µm | m ∈ ms } = γg∧µm for some m ∈ ms .
µm, and g ∈ mI . This proves that ext( {µm | m ∈ ms }) ⊆ mJs ,
W
Therefore γg ≤W
and mJs = ext ( {µm | m ∈ ms }).
Remark 2. The above discussed cases are not the only ones where the size does
not increase. Therefore, it would be interesting to describe the classes of lattices
on which ∃-generalizations do not increase the size.
5.2 A ∀-generalization on attributes
Let (G, S, J) be a context obtained from (G, M, I) by a ∀-generalization. In the
context (G, M ∪ S, I ∪ J), each attribute concept µms is reducible. This means
that mJ
T J
{m | m ∈ ms } = {mI | m ∈ ms }, and is an extent of (G, M, I).
T
s =
Therefore, |B(G, S, J)| ≤ |B(G, M ∪ S, I ∪ J)| = |B(G, M, I)|.
Discovering Generalized Patterns using Taxonomies 337
Theorem 2. The ∀-generalizations on attributes reduce the size of the concept
lattice.
6 Related work
There are a set of studies [2–5, 7, 13, 15] about the possible collaborations be-
tween formal concept analysis and ontology engineering (e.g., ontology merging
and mapping) to let the two formalisms benefit from each other strengths. For ex-
ample, starting from the observation that both domain ontologies and FCA aim
at modeling concepts, [2] show how FCA can be exploited to support ontology
engineering (e.g., ontology construction and exploration), and conversely how
ontologies can be fruitfully used in FCA applications (e.g., extracting new knowl-
edge). In [13], the authors propose a bottom-up approach called F CA−M ERGE
for merging ontologies using a set of documents as input. The method relies
on techniques from natural language processing and FCA to produce a lattice
of concepts. Starting from a set of domain specific texts, [7] proposes a semi-
automatic method for ontology extraction and design based on FCA and Horn
clause model. [5] studies the role of FCA in reusing independently developed
domain ontologies. To that end, an ontology-based method for evaluating simi-
larity between FCA concepts is defined to perform some Semantic Web activities
such as ontology merging and ontology mapping. In [15] an approach towards
the construction of a domain ontology using FCA is proposed. The resulting
ontology is represented as a concept lattice and expressed via the Semantic Web
Rule Language to facilitate ontology sharing and reasoning.
In [4], a method for ontology mapping, called FCA-Mapping, is defined based
on FCA and allows the identification of equal and subclass mapping relations.
In [3], FCA is also used to propose an ontology mediation method for ontology
merging. The resulting ontology includes new concepts not originally found in
the input ontologies but excludes some redundant or irrelevant concepts.
In association rule mining, there are many efforts to integrate knowledge in
the process of rule extraction to produce generalized patterns [11].
7 Conclusion
In this paper we have studied the problem of using a taxonomy on objects
and/or attributes in the framework of formal concept analysis under three main
cases of generalization (∃, ∀, and α) and have shown that (i) the set of general-
ized concepts is in some cases smaller than the set of patterns extracted from the
original set of attributes (before generalization), and (ii) the generalized concept
lattice not only embeds new patterns on generalized attributes but also reveals
particular features of objects and may unveil a new taxonomy on objects. A
careful analysis of the three cases of attribute generalization led to the following
conclusion: the α-case is an attribute approximation, the ∀-case is an attribute
338 Léonard Kwuida, Rokia Missaoui and Jean Vaillancourt
specialization while only the ∃-case is actually an attribute generalization. Dif-
ferent scenarios of a simultaneous generalization on objects and attributes are
also discussed based on the three cases of generalization.
Since we focused our analysis on the integration of taxonomies in FCA to
produce generalized concepts, our further research concerns the theoretical study
of the mapping between a rule set on original attributes and a rule set of gener-
alized attributes as well as the exploitation of other components of an ontology
such as general links (other than is-a hierarchies) between concepts/entities.
References
1. Claude Berge. Graphs and hypergraphs, volume 6 of North - Holland Mathematical
Library. North-Holland, Elsevier, Amsterdam, repr. of the 2., rev. ed. edition, 1979.
2. Philipp Cimiano, Andreas Hotho, Gerd Stumme, and Julien Tane. Conceptual
knowledge processing with formal concept analysis and ontologies. In ICFCA,
pages 189–207, 2004.
3. Olivier Curé and Robert Jeansoulin. An fca-based solution for ontology mediation.
In ONISW ’08: Proceeding of the 2nd int. workshop on Ontologies and nformation
systems for the semantic web, pages 39–46, New York, NY, USA, 2008. ACM.
4. Liya Fan and Tianyuan Xiao. An automatic method for ontology mapping. In
Knowledge-Based Intelligent Information and Engineering Systems, pages 661–669,
2007.
5. Anna Formica. Ontology-based concept similarity in formal concept analysis. Inf.
Sci., 176(18):2624–2641, 2006.
6. Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foun-
dations. Springer-Verlag New York, Inc., 1999. Translator-C. Franzke.
7. Hele-Mai Haav. A semi-automatic method to ontology design by using fca. In
CLA, 2004.
8. Léonard Kwuida, Rokia Missaoui, Beligh Ben Amor, Lahcen Boumedjout, and
Jean Vaillancourt. Restrictions on concept lattices for pattern management. In
Concept Lattices and Applications (CLA), pages 235–246, 2010.
9. Patrick Scheich, Martin Skorsky, Frank Vogt, Cornelia Wachter, and Rudolf Wille.
Conceptual data systems. In O. Opitz, B. Lausen, and R. Klar, editors, Information
and Classification, pages 72–84. Springer, Berlin-Heidelberg, 1993.
10. Henry Soldano and Véronique Ventos. Abstract concept lattices. In ICFCA, pages
235–250, 2011.
11. Ramakrishnan Srikant and Rakesh Agrawal. Mining generalized association rules.
In VLDB, pages 407–419, 1995.
12. Gerd Stumme. Conceptual On-Line Analytical Processing. In K. Tanaka,
S. Ghandeharizadeh, and Y. Kambayashi, editors, Information Organization and
Databases, chapter 14, pages 191–203. Kluwer, 2000.
13. Gerd Stumme and Alexander Maedche. FCA-MERGE: Bottom-up merging of
ontologies. In IJCAI, pages 225–234, 2001.
14. Véronique Ventos and Henry Soldano. Alpha galois lattices: An overview. In
ICFCA, pages 299–314, 2005.
15. Jian Wang and Keqing He. Towards representing fca-based ontologies in seman-
tic web rule language. In CIT ’06: Proceedings of the Sixth IEEE International
Conference on Computer and Information Technology, page 41, Washington, DC,
USA, 2006. IEEE Computer Society.