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 analyze 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.
In many real-life applications and research trends in Computer Science, the semantics 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” [
The rest of this contribution is organized as follows. In Section 2 we introduce the basic notions of FCA. Section 3 presents three different generalization schemes, and discusses different scenarios of generalizing both objects and attributes. 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´alaga (Dept. Matem´atica Aplicada), Spain.
In formal concept analysis, a context is a triple K a b c d e f g h K := (G, M, I) where G, M and I stand for a set 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 specialization of every generalization of all concepts in C (u is the supremum of C and is denoted by W C), and there is a concept v of K which is a specialization of every concept in C and a generalization of every specialization of all concepts in C (v is the infimum of C and is denoted by V 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 γg’s and infimum of some µm ’s4. Thus, the set {γg | g ∈ G} is W-dense and the set {µm | m ∈ M } is V-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 [
g∈A m∈B nested line diagrams, . . . ). We believe that using taxonomies on objects and attributes 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
One of the strengths of
FCA is the ability to
pictorially display
knowledge, 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
represented by a node a is
given by all labels in G
from the node a
downwards, 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
drawing 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
structure 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 [
Before we move to generalized patterns, let us see how data are transformed into binary contexts, the suitable format for our data. 2.3
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, Im) with
gImsm : ⇐⇒ m(g)Imsm, 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 for each attribute we get the derived context
KS := (G, N, IS ) where N := S{Mm | m ∈ M } and gIS sm ⇐⇒ m(g)Imsm. 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 [
In the field of data mining, generalized patterns are pieces of knowledge extracted 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 attributes 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
There are mainly three ways to express the relation J : (∃) g J s : ⇐⇒ ∃m ∈ s, g I m. Consider an information table describing companies 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, then it becomes natural to state that a student g succeeds in his comprehensive exam CE.exam if he succeeds in all the exam parts of CE.
|{m∈s |s||g I m}| ≥ αs where αs is a threshold set by the user for the generalized attribute s. This case generalizes the (∃)-case (α = |M1 | ) 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 succeed 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 generalized 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
The α-case discussed here generalizes the alpha Galois lattices investigated
by Ventos et al [
Attribute generalization reduces the number of attributes. One may therefore 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 initial 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.
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
Done simultaneously on attributes and on objects, the generalization will give a
kind of hypercontext (similar to hypergraphs [
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; {a∈A| |{b∈B|a I b}| ≥β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 βB fraction of the attributes in the group B; b∈B| |{a∈A|a I 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| ≥ α, i.e. the density of the rectangle A × B is at least equal |A×B| to α.
Remark 1. The cases 7 and 8 generalize Case 1 (αA := |G1 | , βB := |M1 | for all A and B) and Case 2 (αA := 1, βB := 1 for all A and B). Moreover, Case 7 also generalizes Case 3 (αA := 1, βB := |M| for all A and B) and Case 5 (αA := | G1| , 1 βB := 1 for all A and B). However, Cases 4 and 6 cannot be captured by Case 7, but are captured by Case 8 (αA := 1, βB := |M1 | for all A and B to get Case 4, and αA := | G1| , β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 4.1
Let K be a formal context and (G, S, J ) a context obtained from K via a generalization 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 ).
A nested line diagram [
– There is an α-generalized attribute ms ∈ S with at least one attribute m ∈ ms such that g6 Im and g J ms; hence µm µm s in B(G, M ∪ S, I ∪ J ); i.e µm s is not a generalization of µm . – There is an α-generalized attribute ms ∈ S with at least one attribute m ∈ ms such that g I m and g6 Jms; hence µm s µm in B(G, M ∪ S, I ∪ J ); i.e µm s is not a specialization of µm .
Therefore, there are α-generalized attributes ms that are neither a generalization 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
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 µm 1 and µm 2 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 µm 12 ∧ µm 4 and µm 12 ∧ µm 3 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
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 attribute 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) intices, we can define some mappings. creasing the size of the initial lattice We assume that (ms)s∈S forms a par- (left). m12 = {m1, m2}. 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 example gI = {m ∈ M | g I m} and gJ = {s ∈ S | g J s}. Two canonical maps α and β are defined as follows: α : G → B(G, S, J ) g 7→ γ¯g := (gJ J, gJ) and β : M → B(G, S, J )
m 7→ µm¯ s := (sJ, sJ J), where m ∈ ms The maps α and β induce two order preserving maps ϕ and ψ defined by ϕ : B(G, M, I) → B(G, S, J ) (A, B) 7→ W{αg | g ∈ A} and ψ : B(G, M, I) → B(G, S, J ) (A, B) 7→ V{β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 S{mI | m ∈ ms} is an extent, for any ms ∈ S. Then any grouping does 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 contexts 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 msJ is an extent of (G, M, I). By definition, msJ = [{mI | m ∈ ms} ⊆ [{mI | m ∈ ms}
= ext _{µm | m ∈ ms} II For any g ∈ ext(W{µm | m ∈ ms}) we have γg ≤ W{µm | m ∈ ms} and γg = γm∧_{µm | m ∈ ms} = _{γg∧µm | m ∈ ms} = γg∧µm for some m ∈ ms. Therefore γg ≤ µm , and g ∈ mI . This proves that ext(W{µm | m ∈ ms}) ⊆ msJ , and msJ = ext (W{µ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
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 µm s is reducible. This means that msJ = T{mJ | m ∈ ms} = T{mI | m ∈ ms}, and is an extent of (G, M, I). Therefore, |B(G, S, J )| ≤ |B(G, M ∪ S, I ∪ J )| = |B(G, M, I)|. Theorem 2. The ∀-generalizations on attributes reduce the size of the concept lattice. 6
There are a set of studies [
In [
In association rule mining, there are many efforts to integrate knowledge in
the process of rule extraction to produce generalized patterns [
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 generalized 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 specialization while only the ∃-case is actually an attribute generalization. Different 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 generalized attributes as well as the exploitation of other components of an ontology such as general links (other than is-a hierarchies) between concepts/entities.