readme

这是一个用于数据挖掘的常用算法的模板库（数据挖掘的C++模板库for UNIX)

NOTE: In order to explain the example better, unlike the previous examples, here we are using ints as the pattern element type.
The tree miner runs with strings as well.

The above trees can be visualized as follows:

1.      1
       /\
      2  3 

2.      3
       /\
      2  1
        /\
       2  3

3.      2
       /
      1

4.     1

5.     3
      /\
     1  2

6.     2

7.      3
       /
      1
     /
    2
   /
  1

8.    1
     /
    3

The command line and output is as follows:

test$ ./tree_test -i ../data/TREE_int_toy.data -s 2 -I -O -p
Command line parameters given were -
infile=../data/TREE_int_toy.data
minsup=2
print flag=1
induced flag=1
ordered flag=1
3 level-1 patterns found
FREQUENT PATTERNS -
2 -- Support: 6

3 -- Support: 5

1 -- Support: 7

2  ---  1 -- Support: 2

3  ---  2 -- Support: 2

3  ---  1 -- Support: 3

3  ---  1  ---  2 -- Support: 2

1  ---  2 -- Support: 3

1  ---  3 -- Support: 3

1  ---  2  <--  3 -- Support: 2

10 patterns found
Timing Data =================:
Wall clock time to read db in:0.00113702
TOTAL wall clock time taken:0.00346684

Interpreting Tree Output:
-------------------------
In the above test, we ran the tree miner to mine induced and ordered trees from the above dataset.
The minimum support was set to 2. 
10 frequent patterns were found. The last pattern '1  ---  2  <--  3' is found in 2 of the above trees.
This pattern can be visualized as:
          1
         /\
        2  3
The '---' between two nodes indicates a forward edge, whereas '<--' between 2 nodes indicates that
you need to go one level towards the root to add the following node.

GRAPH RUN:
----------
test$./graph_test -i ../data/Graph_str_toy2.data -s 2 -p
3 frequent single-edged patterns found

FREQUENT PATTERNS
Canonical code: 
0 1 B 2 B
Support: 2

Canonical code: 
0 1 B 3 C
Support: 2

Canonical code: 
0 1 A 1 B
Support: 2

Canonical code: 
0 1 B 2 B
1 2 B 3 C
Support: 2

Canonical code: 
0 1 A 1 B
1 2 B 2 B
Support: 2

Canonical code: 
0 1 A 1 B
1 2 B 2 B
1 3 B 3 C
Support: 2

Canonical code: 
0 1 A 1 B
1 2 B 3 C
Support: 2

TIMING STATISTICS
Time taken to read db in: 6.69956e-05sec
Time taken in isomorphism checks: 0.00236869sec
Time taken in VAT intersection: 0.000332355sec
Total time taken: 0.006253sec

7 total frequent graphs found

Output help for Graph:
---------------------
In the above graph mining, we got 7 frequent graph, of which 3 of them are single-edge graph.
Our library prints a graph by printing its minimal canonical code. This code lists the edges
of the graph in such an order that the code is minimal. Note that, minimal canonical code of 
a graph is always unique. DMTL representation of canonical code is identical to gspan graph
mining algorithm. Each edge is the code is represented by a 5-tuple. For instance, canonical 
code of an edge(v1, v2) is: <dfs_id_v1, dfs_id_v2, label_v1, label_edge, label_v2>

dfs_id_v1 : Depth-first order of the vertex v1 in the minimal canonical labeling
dfs_id_v2 : Depth-first order of the vertex v2 in the minimal canonical labeling
label_v1: Label of vertex v1
label_v2: label of vertex v2
label_ede: Label of the edge (v1, v2)

For example, the following canonical code(left) represent the following graph (right)

                                                   1              3
0 1 A 1 B	                           A -------------- B ---------- C
1 2 B 3 C    --------------------->         \  			        / 
1 3 B 3 C                                     \ _ _ _ _ _ _ _ _ _ _ __ / 
                                                          3

MULTISET RUN:
------------
test$ cat ../data/MS_str_toy.data 
1 1 8 AC CA AB BC CC CA AA AA
2 2 6 CB BC CA AC CC CA
3 3 4 CB BC CA AC
4 4 3 CA AC CB

test$ ./multiset_test -i ../data/MS_str_toy.data -s 2 -p
Command line parameters given were -
infile=../data/MS_str_toy.data
minsup=2
print flag=1
Size of length one patterns = 5
AC CA -- Support: 4
AC BC -- Support: 3
AC CC -- Support: 2
AC CB -- Support: 3
AC CA CA -- Support: 2
AC CA BC -- Support: 3
AC CA CC -- Support: 2
AC CA CB -- Support: 3
AC CA CA BC -- Support: 2
AC CA CA CC -- Support: 2
AC CA CA BC CC -- Support: 2
AC CA BC CC -- Support: 2
AC CA BC CB -- Support: 2
AC BC CC -- Support: 2
AC BC CB -- Support: 2
CA CA -- Support: 2
CA BC -- Support: 3
CA CC -- Support: 2
CA CB -- Support: 3
CA CA BC -- Support: 2
CA CA CC -- Support: 2
CA CA BC CC -- Support: 2
CA BC CC -- Support: 2
CA BC CB -- Support: 2
BC CC -- Support: 2
BC CB -- Support: 2
AC -- Support: 4
CA -- Support: 4
BC -- Support: 3
CC -- Support: 2
CB -- Support: 3

The following statistics are purely for performance measurement
Wall clock time taken to read db in:0.00028491

TOTAL wall clock time taken:0.00306416
31 patterns found

Interpreting Output for Multiset:
--------------------------------
The output of multiset mining is similar as that of itemset mining. The only difference being that items
can reapeat in a single transaction. For example the pattern {CA, CA} has a support 2, i.e. {CA, CA} appeared in 2
transaction of the above datasets given in file MS_str_toy.data


NOTES FOR DEVELOPERS:
=====================

DMTL is a generic pattern mining algorithm. It uses template arguments to dispatch right algorithm
to mine a specific pattern. User need to specify through templates, what kind of pattern they
like to mine and what kind of mining approach they like to use.

Each pattern in represented as a collection of relational properties, like directed, no_edges,
undirected, cyclic, indegree_lte_one (indegree <= 1), outdegree_lte_one (outdegree <= 1), etc.
A list of property is passed as template argument to instantiate a pattern. See the test files
in the test directory, to see how the properties were passed for common pattern mining. Note that,
a proplist data structure is used that recursively define the list of properties for a pattern.
To keep the code clean, we used #define to shorthand the long recursive definition of this 
pattern template arguments.  Similarly we defined the variation of mining algorithms 
by a list of mining properties. We specified these also through proplist and again used the
#define directive. 

Available properties are listed in the file called properties.h in the src/common directory. 
Note that properties in a proplist data structure should be ordered according to a property 
hierarchy. The hierarchy is shown in a file called 'prop_hierarchy.eps' in the 'doc' directory.

Please read the doxygen documentation to learn more about different templated class and how to instantiate
those. For any further question, please email to: [e-mail]

EXTENDING DMTL:
===============

The objective of DMTL is to employ the generic programming idea to develop a mining library that is highly
flexible to future extension. One obvious extension is to mine some other complex pattern.
If your pattern can be defined by the properties that we already defined, it's  great. Otherwise, just
add new properties in properties.h file. Now any mining algorithm needs to have three major operation:

1. Candidate generation
2. Isomorphism checking
3. Support Counting

Our current library provides these algorithm for four different patterns. If your pattern can share
any of the above four, you can use them right away, otherwise provide code for that operation only.
For a detail discussion, see our paper (lcsd05.pdf) in doc directory. For any further question, please
email to the authors (emails are available in AUTHORS file).