In this paper, we revisit an original proposition on pattern structures for structured sets of attributes. There are several reasons for carrying out this kind of research work. The original proposition does not give many details on the whole framework, and especially on the possible ways of implementing the similarity operation. There exists an alternative definition without any reference to pattern structures, and we would like to make a parallel between two points of view. Moreover we discuss an efficient implementation of the intersection operation in the corresponding pattern structure. Finally, we discovered that pattern structures for structured attribute sets are very well adapted to the classification and the analysis of RDF data. We terminate the paper by an experimental section where it is shown that the provided implementation of pattern structures for structured attribute sets is quite efficient.
In this paper, we want to make precise and develop a section of [
Accordingly, in this paper, we will go back to the two original definitions and
show how they are related. For completing the history, it is worth mentioning
that antichains, whose intersection is the basis of the similarity operation in
the pattern structure for structured attribute sets, our paper, are studied in the
book [
Then, we proceed to present a way of efficiently working with antichains and intersection of antichains, which can be very useful, especially in case of large sets of data. The last section details a series of experiments where it is shown that pattern structures can be implemented with an efficient intersection operation and that they have a generally better behavior than scaled contexts. 2 2.1
Formal Concept Analysis [
A pattern structure is a triple (G, (D, u), δ), where G is the set of objects, (D, u) is a meet-semilattice of descriptions, and δ : G → D maps an object to its description. In other words, a pattern structure composed of a set of objects, a set of descriptions equipped with a similarity operation denoted by u. This similarity operation is idempotent, commutative and associative. If (G, (D, u), δ) is a pattern structures then the derivation operators (Galois connection) are defined as:
A := l δ(g) g∈A d := {g ∈ G|d v δ(g)} for A ⊆ G for d ∈ D Each element in D is referred to as a pattern. The natural order on (D, u), given by c v d ⇔ c u d = c is called the subsumption order. Now a pattern concept can be defined as follows: Definition 1 (Pattern Concept). A pattern concept of a pattern structure (G, (D, u), δ) is a pair (A, d) where A ⊆ G and d ∈ D such that A = d and A = d , where A is called the concept extent and d is called the concept intent.
A pattern extent corresponds to the maximal set of objects A whose descriptions subsume the description d, where d is the maximal common description for objects in A. The set of all pattern concepts is partially ordered w.r.t. inclusion on extents, i.e., (A1, d1) ≤ (A2, d2) iff A1 ⊆ A2 (or, equivalently, d2 v d1), making a lattice, called pattern lattice. 2.2
We briefly recall two original propositions supporting the present study. The first
work is firstly published by Carpineto & Romano in [
In [
In other words, this intersection operation corresponds to the intersection of
two antichains as this is explained in [
{m ∈ P | ∃ac1 ∈ AC1, ∃ac2 ∈ AC2, m ≤ ac1 and m ≤ ac2}.
There is a “canonical representation context” (or an associated scaling operator) for the pattern structure (G, (D, u), δ) related to structured attribute sets, which is defined by the set of “principal ideals ↓ p” as follows: (G, P, I) with (g, p) ∈ I ⇐⇒ p ≤ δ(g).
In the next section, we make precise and discuss the pattern structure for
structured attribute sets by taking the point of view of filters and not of ideals
in agreement with the order from [
An important case of structured attributes is “tree-shaped attributes”, i.e., when the attributes are organized within a partial order corresponding to a rooted tree. If it is the case, then the root of the tree, denoted by >, can be matched against the description of any object, while the leaves of this tree are the most detailed descriptions. For example, the root can correspond to the attribute ‘Animal’ and a leaf can correspond to the attribute ‘Cat’; somewhere in between there could be attribute ‘Mammal’.
An example of such kind of data naturally appears in the domain of semantic web data. For example, Figure 1 gives a small part of ACCS1. This attribute tree will be used as a running example and should be read as follows. If an object belongs to class C1 (and probably to some other classes), then it necessarily belongs to classes C10, C12, and >, e.g., if an object is a cat, then it is a mammal and an animal. Accordingly, the description of an object can include several classes, e.g., classes C1, C5 and C8. Thus, some of the tree-shaped attributes can be omitted from the description of an object. However, they should be always taken into account when computing the intersection between descriptions. Thus, in order to avoid redundancy in the descriptions, we can allow only antichains of the tree as possible elements in the set D of descriptions, and then, accordingly compute the intersection of antichains.
An efficient way of computing intersection of antichains is explained in the next section. Here it is important to notice that although it is a hard task to efficiently compute intersection of antichains in an arbitrary partial order of attributes, the intersection of antichains in a tree can help in computing this more general intersection. Indeed, in a partial order of attributes, we can add an artificial attribute > that can be matched against any description. Then, instead of considering an intersection of antichains in an arbitrary poset we can take a spanning tree of it with > taken as the root. Although we have lost some relations between attributes, and, thus, the size of the antichains is probably larger, we can apply the efficient intersection of antichains of tree discussed below. 2.4
In this subsection we show how to efficiently solve the problem of intersection of antichains in a tree. The problem is formalized as follows. A partial order is
C12 C10
C11 >
C6 C13
C8 C1
C2
C4
C5
C7
C9 described by the Hasse diagram corresponding to the tree. The root is denoted by > and it is larger w.r.t. the partial order than any other element in the tree. Given a rooted tree T and two antichains X and Y , we should find an antichain Z such that (1) for all x ∈ X ∪ Y there is z ∈ Z such that x ≤ z and (2) no z ∈ Z can be removed or changed to z˜ < z without violating requirement (1).
If the cardinality of antichains X and Y is 1 then this task is reduced to
the well-known problem of a Least Common Ancestor (LCA). In 1984 it was
already shown that the LCA problem can be reduced to Range Minimum Query
(RMQ) problem [
Reduction of LCA to RMQ. Given an array of numbers, the RMQ problem consists in efficient answering queries on the position of the minimal value in a given range (interval) of positions for this array. For example, given an array
Array [ 2 1 0 3 2 ]
Positions 1 2 3 4 5
where the first value is in position 1 and the last value is in position 5, the answer
to the query on the position of the minimal number in the range 2–4, i.e., the
corresponding part of array is [1;0;3], is 3 (the value of the 3rd element in the
array is 0 and it is the minimal value in this range). Accordingly, the position
of the minimal number in the range 1–2 (the part of the array is [2;1]) is 2. The
good point about this problem is that it can be solved in O(n) preprocessing
computational time and in O(1) computational time per one query [
In order to introduce the reduction of LCA to RMQ we need to know what is the depth of a tree vertex. The depth of a vertex in a rooted tree is the number of edges in the shortest path from that vertex to the root of the tree.
We create the array of depths of the vertices in the tree that is used as an input array for RMQ. We build this array in the following way. We traverse the tree in depth first order (see Figure 2). Every time the algorithm considers a
2 1 4 0 3 6 5 7 Depth array D [ 0 1 2 1 2 3 2 3 2 1 0 1 2 1 0 ] Corresponding vertex v0 v1 v2 v1 v3 v4 v3 v5 v3 v1 v0 v6 v7 v6 v0 Positions 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 vertex, i.e., the first visit or a return to the vertex, we should put the depth of that vertex at the end of the depth array D. We also keep track of a vertex corresponding to each depth in D. The depth array D has 2|T | − 1 values, where |T | is the number of vertices in the tree.
Now for any value in D we know the corresponding vertex of the tree and
any vertex of the tree is associated with several positions in D. For example, in
Figure 2 the value in the first position of D, i.e., D[
Given two vertices A, B ∈ T , let a be one of the positions in D corresponding to vertex A, let b be one of the positions in D corresponding to B. Then it can be shown that the vertex corresponding to the minimal value in D in the range a–b is the least common ancestor of A and B. For example, to find LCA between vertices 3 and 6 in Figure 2, one should first take two positions in D corresponding to vertices 3 and 6. Positions 5,7, and 9 in array D correspond to vertex 3, positions 12 and 14 correspond to vertex 6. Thus, we can query RMQ for ranges 5–14, 7–14, 7–12, etc. The minimal value in D for all these ranges is 0 located at position 11 in D, i.e., RMQ(5, 14) = 11. Thus, the vertex corresponding to position 11, i.e., vertex 0, is the least common ancestor for vertices 3 and 6.
Let us notice that if A ∈ T is an ancestor of B ∈ T and a and b are two positions corresponding to the vertices A and B, then the position RMQ(a, b) in D always corresponds to the vertex A, in most of the cases RMQ(a, b) = a. Thus we are also able to check if a vertex of T is an ancestor of another vertex of T .
Now we know how to solve the LCA problem in O(|T |) preprocessing computational time and O(1) computational time per query. Let us return to the problem of intersecting antichains of a tree.
Antichain intersection problem. Let us first discuss the naive approach to this problem. Given two antichains A, B ⊂ T , one can compute the set D [ 0 1 2 3 2 3 2 1 2 3 2 3 2 1 0 1 2 3 2 3 2 3 2 1 0 ] > C12 C10 C1 C10 C2 C10 C12 C11 C4 C11 C5 C11 C12 > C6 C13 C7 C13 C8 C13 C9 C13 C6 > 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 {LCA(a, b) | ∀a ∈ A and ∀b ∈ B}. Then this set should be filtered for removing the comparable elements in order to get an antichain. It is easy to see that the result is the intersection of A and B but it requires at least |A|·|B| operations.
Let us reformulate this naive approach in terms of RMQ. Given a depth array D and two sets of indices A, B ⊆ N|D| forming an antichain, we should compute the set Z = {RMQ(a, b) | ∀a ∈ A and ∀b ∈ B} and then remove all elements z ∈ Z such that there is x ∈ Z \ {z} with the position RMQ(z, x) corresponding to the same vertex as z, i.e., elements z corresponding to an ancestor of another element from Z.
Let us consider for example the tree T given in Figure 1. Figure 3 shows the depth array, the corresponding vertices, and indices of this array. Let us show how to compute the intersection of A = {C1, C5, C8} and B = {C1, C7, C9}. The expected result is {C1, C13}. First we translate the sets A and B to the indices in array D for RMQ, i.e., A = {4, 12, 20} and B = {4, 18, 22}. Then we compute RMQ for all pairs from A and B:
{RMQ(4, 4) = 4, RMQ(4, 18) = 15, RMQ(4, 22) = 15, · · · , RMQ(20, 18) = 19, · · · }. Now we should remove positions corresponding to ancestors in the tree, e.g., RMQ(4, 15) = 15 and, hence, 15 should be removed. The result is {4, 13} representing exactly {C1, C13}.
Let us discuss two points that help us to reduce the complexity of the naive
approach. Consider the positions i ≤ l ≤ m ≤ j and k = RMQ(i, j), n = RMQ(l, m).
Then the depth in the position k is not larger than the depth in the position
n, D[k] ≤ D[n]. Hence the position RMQ(k, n) corresponds to the same vertex as
position k. For example, in Figure 3 RMQ(4, 6) = 5 and RMQ(2, 7) = 2. The value
in position 5 in the array D is D[
Thus, given two sets of indices A, B ⊆ N|D| corresponding to antichains, we can modify the naive algorithm by ordering the set A ∪ B and computing RMQ only for consecutive elements from different sets, rather then for all pairs from different sets. For example, for intersecting A = {4, 12, 20} and B = {4, 18, 22}, we join them to the set Z = {4A, 4B, 12A, 18B, 20A, 22B}. Then, we compute RMQ only for consecutive elements from different sets, i.e., RMQ(4, 4) = 4, RMQ(4, 12) = 8, RMQ(12, 18) = 15, RMQ(18, 20) = 19, and RMQ(20, 22) = 21. The cardinality of A ∪ B is less then |A| + |B|, hence, the number of the consecutive elements is O(|A| + |B|), and, thus, the number of RMQs of consecutive elements is O(|A| + |B|).
However, the set Z of RMQs of consecutive elements does not not necessarily correspond to an antichain in T . Thus we should filter this set, in order to remove all ancestors of another elements form Z. Accordingly, it is clear that to filter the set Z it is enough to check only consecutive elements of Z. For example, the intersection of A = {4, 12, 20} and B = {4, 18, 22} gives us the following set Z = {4, 8, 15, 19, 21}. Let us now check the RMQs of consecutive elements. RMQ(4, 8) = 8, thus, 8 is an ancestor of 4 and 8 can be removed. Since 8 is removed, we compare RMQ(4, 15) = 15, thus, 15 should be also removed. Then we compute RMQ(4, 19) = 15, i.e., the indices 4 and 19 are not ancestors and both are kept. Now we compute RMQ(19, 21) = 19 and, thus, 19 should be removed (actually positions 19 and 21 correspond to the same vertex C13 and one of them should be removed). Thus, the result of intersecting A and B is {4, 21} corresponding to the antichain {C1, C13}.
Since the number of elements in the set Z is O(|A| + |B|), then overall complexity of computing intersection for two antichains A, B ⊂ T of a tree T is O(|A| + |B|) or, taking into account that the cardinality of an antichain in a tree is less then the number of leaves (vertices having no descendants) in this tree, the complexity of computing intersection of two antichains is O(|Leaves(T )|). Antichain intersection by scaling. An equivalent approach for computing intersection of antichains is to scale the antichains to the corresponding filters. A filter corresponding to an antichain in a poset is the set of all elements of the poset that are larger then at least one element from the antichain. For example, let us consider a tree-shaped poset in Figure 1. A filter corresponding to the antichain {C1, C5, C8} is the set of all ancestors of all elements from the antichain, i.e., it is equal to {C1, C10, C12, >, C5, C11, C8, C13, C6}.
The set-intersection of filters corresponding to the given antichains is a filter corresponding to the antichain resulting from intersection of the antichains. However this approach has a higher complexity. Indeed, the size of a filter is O(|T |) and, thus, the computational complexity of intersecting two antichains by means of a scaling is O(|T |) which is harder then O(|Leaves(T )|) for intersecting antichains directly. Indeed, the number of leaves in a tree can be dramatically smaller than the number of vertices in this tree. For example, the number of vertices in Figure 1 is 13, while the number of leaves is only 7. Thus, the direct intersection of antichains is more efficient than the intersection by means of a scaling procedure.
Relation to intersection of antichains in partially ordered sets of attributes. As it was mentioned in the previous section, the intersection of antichains in arbitrary posets can be reduced to the intersection of antichains in a tree. However, the size of the antichain representing a description of an object can increase. Indeed, since we have reduced a poset to a tree, some relations have been lost, and thus the attributes that are subsumed in the poset for a given antichain A are no more subsumed in the tree for A, and hence should be added to A. However, the reduction is still more computationally efficient than
(a) Real data experiments.
computing the intersection of antichains in a poset by means of a scaling as it
is discussed in the previous paragraph. However, for the reduction it could be
interesting to find the spanning tree with the minimal number of leaves.
Unfortunately, this is an NP-complete task and it thus cannot be applied for increasing
the computational efficiency [
Several experiments are conducted using publicly available data on a MacBook with a 1.3GHz Intel Core i5, 4GB of RAM running OS X Yosemite 10.3. We have used FCAPS2 software developed in C++ for dealing with different kinds of pattern structures. It can build a concept lattice starting from a standard formal context or from object descriptions given as antichains of a given tree. The last one is based on the similarity operation that is discussed above.
We performed our experiments on two datasets from different domains namely DBLP and biomedical data. In these datasets, object descriptions are given as subsets of attributes. A taxonomy of the attributes is already known based on domain knowledge. We compute a concept lattice in two different ways. In the first one, we directly compute the concept lattice from the antichains in a taxonomy. In the second one we scale every description to the corresponding filter of the taxonomy. After this we do not rely on the taxonomy and process the scaled context with standard FCA.
The first data set is DBLP, from which we extracted a subset of papers with their keywords published in conferences in Machine Learning domain. The taxonomy used for classifying such kind of triples is ACM Computing Classification System (ACCS)3.
The second data set belongs to the domain of life sciences. It contains information about drugs, their side effects (SIDER4), and their categories (DrugBank5). The taxonomies related to this dataset are MedDRA 6 for side effects and MeSH7 for drug categories.
The parameters of the datasets and the computational results are shown in Table 1a. It can be noticed that for DBLP the context consists of 5293 objects and 33207 attributes, in the taxonomy of the attributes we have 33198 leaves meaning that most of attributes are mutually incomparable. It took 45 seconds to produce a lattice having 10134 concepts directly from the descriptions given by antichains of the taxonomy. To produce the same lattice starting from a scaled context the program only takes 21 seconds. However, if we consider the biomedical data, the approach based on antichains is better. Indeed, it takes 145 seconds, while the computation starting from the scaled contexts takes 162 seconds. In this case, the dataset contains 1490 attributes with 933 leaves. Thus, the direct approach works faster if the number of leaves is significantly smaller than the number of vertices. It is worth noticing that the size of antichains is significantly smaller than the size of the filters, and thus our approach is more efficient. However, when the number of leaves is comparable to the number of vertices, our approach is slower. Although in this case our approach has the same
3 https://www.acm.org/about/class/2012 4 http://sideeffects.embl.de/ 5 http://www.drugbank.ca/ 6 http://meddra.org/ 7 http://www.ncbi.nlm.nih.gov/mesh/ computational complexity as the scaling approach, the antichain intersection problem requires more efforts than the set intersection.
Since the efficiency of the antichain approach is high for the trees with a low number of leaves, we can use this method to increase efficiency of standard FCA for special kind of contexts. In a context (G, M, I) an attribute m1 can be considered as an ancestor of another attribute m2 if any object containing the attribute m2 also contains the attribute m1. Accordingly we can construct an attribute tree T and rely on it for computing intersection operation. In this case the set of attributes M and the set of vertices of T are the same and |M | = |T |. The second part of the experiment was based on this observation.
We used numerical data from Bilkent University in the second part of the
experiments8. It was converted to formal contexts by the standard interodinal
scaling. The scaled attributes are closely connected, i.e., there are a lot of pairs
of attributes (m1, m2) such that the set of objects described by m1 is a subset
of objects described by m2, i.e., (m1)0 ⊆ (m2)0. Thus, we can say that m1 ≤ m2.
Using this property we built attribute trees from the scaled contexts. These
trees have many more vertices than leaves, thus, the approach introduced in this
paper should be efficient. We compare our approach with the scaling approach.
Moreover, recently, it was shown that interval pattern structures (IPS) can be
efficiently used to process such kind of data [
The results are shown in Table 1b. Compared to Table 1a it has several additional columns. First of all, since for numerical data we typically got large lattices, in most of the cases we considered only part of the objects. The actual number of used objects is given in the column |G|, while the total size of the dataset is given in the column ‘#objects’, e.g., BK dataset contained 96 objects, while we have used only 35. In addition for every dataset we also provide the number of the numerical attributes, e.g., BK has 5 numerical attributes. We should notice that when we built the lattice from some datasets by standard FCA, the lattice was so large that the memory was swapping and we stopped the computation. It was not the case for our approach since antichains requires less memory to store than the corresponding filters. The fact of swapping is shown by ‘*’ next to computational time in column tK. In addition we also show the time for IPS to process the same dataset. For example, the processing of BK dataset took 37 seconds by our approach, took more than 42 seconds by standard FCA and memory had started swapping, and took 19 seconds by IPS.
This experiment shows that our approach takes not only less time to compute concept lattice, but also requires less memory, since there is no memory swapping. We can also see that the computation time for IPS is smaller than for our approach. However, IPS is only applicable for numerical data, while our approach can be applied for all cases when attributes of a context are structured. For example, we can deal with graph data scaled to the set of frequent subgraphs where many such attributes are subgraphs of other attributes. 8 http://funapp.cs.bilkent.edu.tr/DataSets/
In this paper we recalled two approaches for dealing with structured attributes and explained how we can compute intersection of antichains in tree-shaped posets of attributes, an essential operation for working with structured attributes. Our experiments showed the computational efficiency of the proposed approach. Accordingly, we are interested in applying our approach to other kinds of data such as graph data. Moreover, the generalization of our approach to other kinds of posets is also of high interest.