We study the minimal generators (mingens) in multi-relational data mining. The mingens in formal concept analysis are the minimal subsets of attributes that induce the formal concepts. An intent for a formal concept is called a closed pattern. In contrast to the wide attention to closed patterns, the mingens have been paid little attention in Multi-Relational Data Mining (MRDM) field. We introduce an idea of non redundant mingens in MRDM. The notion of mingens in MRDM is led by -subsumption relation among patterns, and is useful to grasp the structure and information in the concepts.
Formal Concept Analysis (FCA) [
While a closure is the maximal pattern presenting a concept, a minimal
generator (mingen) [
Sections 2 and 3 introduce FCA and MRDM. Section 4 describes about mingens. Section 5 provides a definition of minimal generators consisted of relational patterns. Then section 6 reports experimental results on compactness.
Example 1. A Fig. 1 shows a formal context where each object has a set of attributes. A pair (t1t2t3; cdg) (set brackets are omitted) is a formal concept, where t1t2tI3 = cdg and cdgI = t1t2t3. Fig. 2 shows the concept lattice. Each concept is labeled by its intent. 3
While propositional data mining algorithms look for patterns in a single data table, MRDM algorithms look for relational patterns, represented by logical formulae, that involve multiple tables (relations).
Example 2. A Database Rfam in Fig. 3 includes four relations on families, where grandfather(x) meaning x is someone’s grandfather, parent(x; y) meaning x is a parent of y, male(x) for male x, and female(x) for female x. Then a pattern, such as grandfather(X) parent(X; Y ); parent(Y; Z); female(Z), can be found. 2 ut grandfather person01 person07 person12 person19 person20 parent person01 person02 person02 person03 ...
person02 person03 person04 person05 ...
male person01 person05 person07 person10 ... In the above example, the closed itemset bcghi has six mingens, where b, h and i always appear together in each object and thus can be exchanged each other, and similarly for c and g. An SSMG is a representative of each equivalence class, which is defined bellow. A criterion which selects a representative is left to users, because dependence between items is not defined.
De nition 3 (C-equivalence). X; Y M are C-equivalent for a formal concept C of a formal context K = (G; M; I), denoted X C Y , if they satisfy either following condition. 1. There is a concept C0 C such that both X and Y are mingens of C0. 2. There are subsets Z; Z0; M M such that X = W [ Z, Y = W [ Z0, and
Z C Z0. ut De nition 4 (SSMG). Given an order v on M , a succinct system of mingens (SSMG) by the order v for a formal concept C of a formal context K consists of elements satis ed either following condition. 1. If C is a maximal formal concept in the sense of the concept lattice except (G; ;), an SSMG for C holds the following conditions.
{ It is a mingen for C.
{ It is minimal in the sense of v among all mingens in a C-equivalence
class for C.
2. Otherwise, a mingen in a C-equivalence class is an SSMG for C if it does
not include any mingen which is not an SSMG for C0 C.
ut
The definition of SSMGs in [
We construct a formal context K0 = (G; M; I) of property items produced by
Mapix, which we call a formal relational context, where G is a set of instances
of a target (key) relation (e.g., grandfather relation in Fig. 3), M is a set of
property items (e.g., in Table 1), and I is relation among G and M , which
indicates whether an instance satisfies a property item (e.g., K0fam in Fig. 4).
The notion of the formal relational context was discussed in [
De nition 5 (LMG). A mingen for a formal concept C of a formal relational context K0 is called a logical mingen (LMG) for C of K0, if it satis es the following conditions.
{ It is an SSMG by -subsumption order ( ).
{ It is a minimal in the sense of in among all SSMG in C-equivalence class.
ut
1. let LM G := ;;
2. let I := fall attributes associated with property itemsg;
3. let LC := fitems occurring in all transactionsg;
4. call DF S(H := ;; T := I LC; LC);
5. return LMG;
DF S(H; T; LC) :
1. if sup(H) < supmin return;
2. for each x 2 T
3. if sup(H [ fxg) = sup(H) let T := T fxg; LC := LC [ fxg;
4. if (H : LC; sup(H)) construct a new concept with sup(H)
5. for each p 2 LC do if p H then p is removed from LC;
6. add (H : LC; sup(H)) to LMG;
7. else remove clutter; // see [
Example 4. Table 2 shows formal concepts in a formal context K0fam. SSMG for
D = (gf(01)gf(07)gf(12); abcef gh) is g; f e; f h, and LMG for D is only f e. ut
The Mining Algorithm The algorithm in Table 3 follows the depth-first
search framework using a set-enumeration tree (SE-tree) [
Experimental Results and Conclusion We have done experiments on two data sets and compared between the number of patterns, the first one was with Rfam in Fig. 3 and the latter was with supmin(%) 80 60 40 20
Mapix 17 109 1063 4601 SSMG 12 21 39 LMG 6 13 22 Mutagenesis-Bonds. Tables 4 and 5 show the number of patterns generated by Mapix, SSMG, and LMG. In both data sets, though SSMG and LMG had large reduction of patterns compared with Mapix, LMG reduces patterns even more than SSMG. Because of a complex structure of Rfam, SSMG and LMG fault the computation with supmin = 20%.
We still need revise of the algorithm for scalability. We also need examine the efficacy in the intuitive sense, such as readability.