TreeMiner

在讲Class Extension的时候：有一个十分重要的定义。
Let P be a prefix class with encoding P,and let (x,i) and (y,j) denote any two elements in the class.And let $P_x$ denote the class representing extensions of element(x,i).

Tree Mining Problem

Let D be a database of trees (ie:a forest).
and let subtree $S \preceq T$ for some $T\epsilon D$ .
Each occurence of S can be identified by its match label,which is given as the set of matching positions (in T) for nodes in S.

what's the match label?
let $\{t_1,t_2,...,t_n\}$ be the nodes in T,so $|T|=n$
let $\{s_1,s_2,...,s_m\}$ be the nodes in S,so $|S|=m$
then S has a match label $\{t_{i_1},t_{i_2},...,t_{i_m}\}$ $iff$
1: $l(s_k)=l(t_{i_k})$ for all k = 1,...,m
2:branch $b(s_j,s_k)$ in S iff $t_{i_j}$ is an ancestor of $t_{i_k}$ in T.

这里有两个Condition.不是很懂。

注意： $l(n_l)$ 是指 $n_l$ 这个node的label. t 和 s 如同n一样的作用。没有其他的意思。

个人认为：
then S has a match label $\{t_{i_1},t_{i_2},...,t_{i_m}\}$ $iff$
应该改成：
then S has a match label $\{i_1,i_2,...,i_m\}$ 使得 $\{t_{i_1},t_{i_2},...,t_{i_m}\}$ $iff$

第4节：使用Scope-List 来加快子树的支持度的计算。
Scope-List Representation：
概念：
X is a k-subtree of a tree T.
$x_k$ refer to the last node of X.
We use the notation $L(X)$ to refer to the scope-list of X.
Each element of the scope-list is a triple(t,m,s).
where t is a tree id (tid) means X.
m is a match label of the (k-1) length prefix of X (base T) (个人添加)。
（recall that the prefix match label gives the positions of nodes in T that match the prefix。）
(Since a given prefix can occur multiple times in a tree ,X can be associated with multiple match label as well as multiple scopes.)
s is the scope of the last item $x_k$
有了上述的概念之后。
4.1：Frequent Subtree Enumeration

Computing $F_1$ and $F_2$ :
Suppose that the initial database is in the horizontal string encode format.
所以D里面的T是一条条串。
看懂代码里面的描述形式：

TreeMiner(D,minsup):
$F_1$ = { classes [] frequent 1-subtrees };
$F_2$ = { classes [P]1 of frequent 2-subtrees };
for all $[P]_1 \epsilon E$ do Enumerate-Frequent-Subtrees( $[P]_1$ );
//注意
Enumerate-Frequent-Subtrees( $[P]$ ):
for each element $(x,i)\epsilon [P]$ do
$[P_x] = \emptyset$
for each element $(y,j)\epsilon [P]$ do
R = {(x,i)+(y,j)};
$L(R) = {L(x) + L(y)}$
if for any $r \epsilon R$ ,r is frequent then
$[P_x] = [P_x] U \{R\}$
Enumerate-Frequent-Subtrees( $[P_x]$ )
里面好这个函数，每次传入的是一个前缀最后加入的是x元素的集合。
其实是前缀集合的子集。就是最后加入的

TreeMiner

Tree Mining Problem

这里有两个Condition.不是很懂。

推荐阅读更多精彩内容