We consider the problem of mining closed patterns from multi-relational databases in a distributed environment. Given two local databases (horizontal partitions) and their sets of closed patterns (concepts), we generate the set of closed patterns in the global database by utilizing the merge (or subposition) operator, studied in the field of Formal Concept Analysis. Since the execution times of the merge operations increase with the increase in the number of local databases, we propose some methods for improving the merge operations. We also present some experimental results using a distributed computation environment based on the MapReduce framework, which shows the effectiveness of the proposed methods.
Multi-relational data mining (MRDM) has been extensively studied for more
than a decade (e.g., [
On the other hand, Formal Concept Analysis (FCA) has been developed as
a field of applied mathematics based on a clear mathematization of the notions
of concept and conceptual hierarchy [
The notion of iceberg query lattices , proposed by Stumme [
We consider in this paper the problem of mining closed patterns (or queries) in multi-relational data, particularly applying the notion of iceberg query lattices to a distributed mining setting. The assumption that a given dataset is distributed and stored in different sites will be reasonable for some situations where we might not be able to move local datasets into a centralized site due to too much data size and/or privacy concerns.
Given two local databases (horizontal partitions) and their sets of closed
patterns (concepts), the set of closed patterns in the global database can be
constructed by using subposition) operator [
The organization of the rest of this paper is as follows. After summarizing some basic notations and definitions of closed patterns mining in MRDM in Sect. 2, we consider distributed closed pattern mining in MRDB and the merge operator in Sect. 3. We then explain our approach to improving the merge operations in Sect. 4. In Section 5, we show the effectiveness of our methods by some experimental results. Finally, we give a summary of this work in Section 6. 2
2.1
In the task of frequent pattern mining in multi-relational databases, we assume
that we have a given database r, a language of patterns, and a notion of
frequency which measures how often a pattern occurs in the database. We use
datalog, or Prolog without function symbols other than constants, to represent
data and patterns. We assume some familiarity with the notions of logic
programming (e.g., [
Example 1. Consider a multi-relational database r in Fig. 1 (above), which consists of five relations, Customer; Parent; Buys; Male and Female. For each relation, we introduce a corresponding predicate, i.e., customer ; parent ; buys; male and female, respectively.
key allen carol diana fred
SR. allen allen carol diana fred fred JR. bill jim bill eve eve hera key(X) {a, c, d, f} Buys key allen carol diana fred item pizza pizza cake cake
person bill jim Female person eve hera key(X), buys(X, pizza) {a, c} key(X), parent(X, Y )
key(X), buys(X, cake) {(a, b), (a, j), (c, b), (d, e), (f, e), (f, h)}
{d, f} key(X), buys(X, pizza), parent(X, Y ), male(Y ) {(a, b), (a, j), (c, b)} key(X), buys(X, cake),
parent(X, Y ), female(Y ) {(d, e), (f, e), (f, h)}
Consider the following pattern P = customer (X); parent (X; Y ); buys(X; pizza). For a substitution , P is logically entailed by r, denoted by r |= P , if there exists a tuple (a1; a2) such that a1 ∈ Customer, (a1; a2) ∈ Parent, and tuple (a1; pizza) ∈ Buys. Then, answerset (P; r) = {{X=allen; Y =bill }; {X=allen; Y =jim}, {X=carol ; Y =bill }}. 2
An atom (or literal ) is an expression of the form p(t1; : : : :tn), where p is a predicate (or relation) of arity n, denoted by p=n, and each ti is a term, i.e., a constant or a variable.
A substitution = {X1=t1; : : : ; Xn=tn} is an assignment of terms to variables. The result of applying a substitution to an expression E is the expression E , where all occurrences of variables Vi have been simultaneously replaced by the corresponding terms ti in . The set of variables occurring in E is denoted by Var (E).
A pattern is expressed as a conjunction of atoms (literals) l1 ∧· · ·∧ln, denoted simply by l1; : : : ; ln. A pattern is sometimes called a query . We will represent conjunctions in list notation, i.e., [l1; : : : ; ln]. For a conjunction C and an atom p, we denote by [C; p] the conjunction that results from adding p after the last element of C.
Let C be a pattern (i.e., a conjunction) and a substitution of Var (C). When C is logically entailed by a database r, we write it by r |= C . Let answerset (C; r) be the set of substitutions satisfying r |= C .
In multi-relational data mining, one of the predicates is often specified as a
key (or target ) (e.g., [
Let r be a database and Q be a query containing a key atom key(X). Then, the support (or frequency) of Q, denoted by supp(Q; r; key), is defined to be the number of different keys that answer Q (called the support count or absolute support ), divided by the total number of keys. Q is said to be frequent , if supp(Q; r; key) is no less than some user defined threshold min sup.
A pattern containing a key will not be always meaningful; for example, let
C = [customer (X); parent (X; Y ); buys(Z; pizza)] be a conjunction in Example 1.
Variable Z in C is not linked to variable X in key atom customer (X); an object
represented by Z will have nothing to do with key object X. It will be
inappropriate to consider such a conjunction as an intended pattern to be mined. In
ILP, the following notion of linked literals [
Definition 1 (Linked Literal). [
Given a database r and a key atom key(X), we assume that there are predefined finite sets of predicate (resp. variables; resp. constant symbols), and that, for each literal l in a conjunction C, it is constructed using the predefined sets. Moreover, each pattern C of conjunctions satisfies the following conditions: key(X) ∈ C and, for each l ∈ C; l is linked to key(X): In the following, we denote by Q the set of queries (or patterns) satisfying the above bias condition.
We now consider the notion of a formal context in MRDM, following [
From this formal context, we can define the concept lattice the same way as
in [
Definition 3 (Closed Query). Let r be a datalog database and ∼r the equivalence relation on a set of datalog queries Q. A query (or pattern) Q is said to be closed (w.r.t. r and Q), iff Q is the most specific query among the equivalence class to which it belongs: {Q1 ∈ Q | Q ∼r Q1}. 2
For any query Q1, its closure is a closed query Q such that Q is the most specific query among {Q ∈ Q | Q ∼r Q1}. Since it uniquely exists, we denote it by Clo(Q1; r). We note again that Var (Q1) = Var (Clo(Q1; r)) by definition. We refer to this as the range-restricted condition here.
Stumme [
For queries Q1 and Q2, we denote by lg (Q1; Q2) the least generalization of Q1 and Q2. Moreover, the join of Q1 and Q2, denoted by Q1 ∨ Q2, is defined as: Q1 ∨ Q2 = lg (Q1; Q2)|Q, where, for a query Q, Q|Q is the restriction of Q to Q, defined by a conjunction consisting of every literal l in Q which is linked to key (X), i.e., deleting every literal in Q not linked to key (X).
Definition 4. [
Our purpose in this work is to mine global concepts in a distributed setting, where a global database is supposed to be horizontally partitioned appropriately, and stored possibly in different sites. We first consider the notion of a horizontal decomposition of a multi-relational DB. Since a multi-relational DB consists of multiple relations, its horizontal decomposition is not immediately clear. Definition 5. Let r be a multi-relational datalog database with a key predicate key . We call a pair r1; r2 a horizontal decomposition of r, if (i) keyr = keyr1 ∪· keyr2 , i.e., the key relation keyr in r is disjointly decomposed into keyr1 and keyr2 in r1 and r2, respectively, and (ii) for any query Q, answerset (Q; r) = answerset (Q; r1) ∪ answerset (Q; r2). 2 The second condition in the above states that the relations other than the key relation in r are decomposed so that any answer substitution in answerset (Q; r) is computed either in partition r1 or r2, thereby being preserved in this horizontal decomposition. An example of a horizontal decomposition of r is shown in Example 3 below.
Given a horizontal decomposition of a multi-relational DB, we can utilize
any preferable concept (or closed pattern) mining algorithm for computing local
concepts on each partition, as long as the mining algorithm is applicable to
MRDM and its resulting patterns satisfy our bias condition. We use here an
algorithm called ffCLM [
To compute the set of global closed patterns from the sets of local closed patterns in MRDM, we need the following merge operator ⊕. For patterns C1 and C2, we denote by C1 ∩ C2 a possibly empty conjunction of the form: l1 ∧ · · · ∧ lk (k ≥ 0) such that, for each li (i ≤ k), li ∈ C1 and li ∈ C2.
Theorem 2. [
The set of global closed patterns C is obtained by the union of the local closed patterns C1 and C2, and, in addition to that, by intersecting each pattern C1 ∈ C1 and C2 ∈ C2. Furthermore, the pattern obtained by the intersection, C1 ∩ C2, should satisfy the bias condition (Def. 1). We note that C1 ∩ C2 does not necessarily satisfy the linkedness condition; for example, suppose that C1 (C2) is a closed pattern of the form: C1 = key(X); p(X; Y ); m(Y ) (C2 = key(X); q(X; Y ); m(Y )), respectively. Then, C1 ∩ C2 = key(X); m(Y ), which is not linked to key (X), and thus does not satisfy the bias condition.
We note that, in the case of transaction databases, the above theorem
coincides with the one by Lucchese et al. [
Example 3. We consider a horizontal decomposition r1; r2 of r in Example 1 such that the key relation keyr (i.e., Customer) in r is decomposed into keyr1 = {allen; carol} and keyr2 = {dian; fred}, and the other relations than Customer are decomposed so that they satisfy the second condition of Def. 5.
Consider a globally closed pattern C = [key (X); parent (X; Y )] in Fig. 1. In r1, there exists a closed pattern C1 of the form: [C; buys(X; pizza); male(Y )], while, in r2, there exists a closed pattern C2 of the form: [C; buys(X; cake); female(Y )]. Then, we have that C coincides with C1 ∩ C2. 2
We can now formulate our problem as follows: Mining Globally Closed Patterns from Local DBs: Input: A set of local databases {DB 1; : : : ; DB n} Output: the set of global closed patterns C1..n.
In order to compute C1..n, our approach consists of two phases: we first compute each set Ci (i = 1; : : : ; n) of local closed patterns from DB i, and then we compute C1..n by applying the merge operators. We call the first phase the mining phase, while we call the second phase the merge phase. 4
In the merge operation in conventional data mining such as itemsets, computing the intersection of two sets in the merge operation ⊕ is straightforward. In MRDM, on the other hand, the computation of ⊕ operator becomes somewhat involved due to handling variables occurring in patterns. Namely, two additional tests are required: checking the bias condition (linkedness), and checking equivalence modulo variable renaming for eliminating duplicate patterns.
For closed patterns C1 and C2, we must check whether the intersection C1∩C2 satisfies the linkedness condition. Moreover, we must check whether C1 ∩ C2 is equivalent (modulo variable renaming) to the other patterns obtained so far. For example, let C1 (C2) be a pattern of the form: C1 = key(X); p(X; Y ); m(Y ) (C2 = key(X); p(X; Z); m(Z)), respectively. Then, C1 is equivalent to C2 modulo variable renaming.
When implementing a data mining system, such handling variables in patterns will necessarily require string manipulations, and such string operations would lead to undesirable overhead in actual implementation. In the following, we therefore propose two methods for reducing the computational costs in the merge operation. 4.1
When computing the merge operation, we can use the following property: Proposition 1. Let DB = DB1 ∪ DB2, and C (Ci) the set of closed patterns of DB (DBi) (i = 1; 2), respectively. Then, Proof. Let C be a closed pattern in C such that C is linked with key. From Theorem 2, it suffices to show that there exist patterns Ci ∈ Ci (i = 1; 2) such that C = C1 ∩ C2 and Var (C1) = Var (C2).
Let Ci = Clo(C; DB i) (i = 1; 2). Then, we have from the definition of Clo(·; ·) that Var (C) = Var (C1) = Var (C2). Moreover, we can show that C = C1 ∩ C2, which is to be proved. 2
From the above proposition, when computing the intersection of each pair of patterns C1 ∈ C1 and C2 ∈ C2 in (1), we can perform the intersection of only those pairs (C1; C2) containing the same set of variables, i.e., Var (C1) = Var (C2). When compared with the original definition of the merge operator ⊕ (Theorem 2), the above property will be utilized to reduce the cost of the merge operations. 4.2
Next, we consider another method for making the merge operation efficient,
which is based on the following simple observation:
Observation 1. Given sets of closed patterns C1 and C2, let D1 = C1 \ C2 and
D2 = C2 \ C1, namely, Di is a difference set (diff-set for short) (i = 1; 2). Suppose
that C is a new (or generator [
That is, a new closed pattern C will be generated only when intersecting
those patterns in the difference sets in D1 and D2. This fact easily follows from
the property that the set of closed patterns is a semi-lattice: suppose otherwise
that C1 ∈ D1, while C2 ̸∈ D2. Then, C2 ∈ C1. Since both C1 and C2 are in C1, we
have that C = C1 ∩ C2 is a closed pattern also in C1, which implies that C is not
a new pattern. Algorithm 1 shows the above-mentioned method based on the
difference sets. In the algorithm, the computation of supports (or occurrences)
is omitted, which is done similarly in [
Algorithm 1: Diff-Set Merge(C1; C2) input : sets of closed patterns C1; C2 output: C1..2 = C1 ⊕ C2 1 C = C1 ∩ C2; D1 = C1 \ C2; D2 = C2 \ C1; 2 foreach pair (C1; C2) ∈ D1 × D2 do 3 C ← C1 ∩ C2; 4 if C satis es the bias condition and C ̸∈ C then 5 C ← C ∪ {C}; 6 end 7 end 8 return C 5
To see the effectiveness of our approach to distributed mining, we have made some experiments. As for the mining phase, we implemented our approach by using Java 1.6.0 22. Experiments of the phase were performed on 8 PCs with Intel Core i5 processors running at 2.8GHz, 8GB of main memory, and 8MB of L2 cache, working under Ubuntu 11.04. We used Hadoop 0.20.2 using 8 PCs, and 2 mappers working on each PC. On the other hand, experiments of the merging phase were performed on one of the PCs.
We use two datasets, often used in the field of ILP; one is the mutagenesis dataset1, and the other is an English corpus of the Penn Treebank Project2.
The mutagenesis dataset, for example, contains 30 chemical compounds. Each compound is represented by a set of facts using predicates such as atom, bond , for example. The size of the set of predicate symbols is 12. The size of key atom (active(X )) is 230, and minimum support min sup = 1=230. We assume that patterns contain at most 4 variables and they contain no constant symbols. The number of the closed patterns mined is 5; 784.
Fig. 2 (left) summarizes the results of the execution times for a test data on the mutagenesis dataset. We can see from the figure that the execution times t1 of the mining phase are reduced almost linearly with the number of partitions. On the other hand, the execution times t2 of the merging phase for obtaining global closed patterns increase almost linearly with the number p of partitions from 1 (i.e., no partitioning) to 16. This is reasonable; the number of applying the merge operators is (p − 1) when we have p partitions. Note that the execution time for the merge phase in the case of a single partition means some start-up overheads such as opening/reading a file of the results of the mining phase, followed by preparing the inputs of the merge operation.
In this particular example, the time spent in the merge phase is relatively small when compared with that for the mining phase. This is because the number of partitions and the number of local closed patterns are rather small. When the number of partitions of a global database becomes larger, however, the execution times for the merging phase will become inevitably larger. Considering efficient merge algorithms is thus an important issue for scalability in MRDM.
To see the effect of using Proposition 1, Fig. 2 (right) shows the numbers of closed patterns in a merge computation C1 ⊕ C2 with input sets C1; C2 of closed patterns for the mutagenesis dataset with 16 partitions. Each table shows the number of patterns in Ci (i = 1; 2) containing k variables for 1 ≤ k ≤ 4. The number of computing intersection operations based on Proposition 1 has been reduced to about 80% of that of the original computation. The execution times in Fig. 2 (left) are the results obtained by using this method. 1 http://www.cs.ox.ac.uk/activities/machlearn/mutagenesis.html 2 http://www.cis.upenn.edu/ treebank/ Fig. 2. Execution Times of the Mining Phase and the Merge Phase (left) and No. of
Each number in a quadrangle is the size of a closed pattern set. D1 = C1 \ C2 and D2 = C2 \ C1.
We have considered the problem of mining closed patterns from multi-relational databases in a distributed environment. For that purpose, we have proposed two methods for making the merge (or subposition) operations efficient, and we have then exemplified the effectiveness of our method by some preliminary experimental results using MapReduce/Hadoop distributed computation framework in the mining process.
In MRDM, efficiency and scalability have been major concerns [
In this work, we have confined ourselves to horizontal partitions of a global
MRDB. It will be interesting to study vertical partitioning and their mixture in
MRDM, where the apposition operator studied by Valtchev et al. [
Acknowledgement The authors would like to thank anonymous reviewers for their useful comments on the previous version of the paper.