頻繁なサブツリーマイニング

サブツリー${\displaystyle S=(V_{s},E_{s})}$は、${\displaystyle T=(V,E)}$かつその場合に限り${\displaystyle V_{s}\subseteq V}$そして${\displaystyle E_{s}\subseteq E}$つまり、S 内の任意の 2 つのノードがエッジで直接接続されている場合は、T 内でも直接接続されます。S 内の任意のノード A と B について、ノード A が S 内のノード B の親である場合、ノード A は T 内のノード B の親でもあります。

サブツリー${\displaystyle S=(V_{s},E_{s})}$は埋め込みサブツリーです${\displaystyle T=(V,E)}$かつその場合に限り${\displaystyle V_{s}\subseteq V}$また、S 内の任意のエッジの 2 つのエンドポイント ノードは、T のルートからリーフ ノードへの同じパス上にあります。言い換えれば、S 内の任意のノード A と B について、ノード A が S 内のノード B の親である場合、ノード A は T 内のノード B の祖先でなければなりません。誘導サブツリーも埋め込みサブツリーであり、したがって埋め込みサブツリーの概念は誘導サブツリーの一般化です。このように、埋め込みサブツリーは、従来の誘導サブツリー マイニングでは見落とされているツリー内の隠れたパターンを特徴付けます。サイズ k のサブツリーは、しばしば k-サブツリーと呼ばれます。

サブツリーのサポートとは、データベース内でそのサブツリーを含むツリーの数を指します。サブツリーのサポートがユーザー指定の閾値（多くの場合、minsupと表記される）以上であれば、そのサブツリーは頻繁に出現するとみなされます。TreeMinerの目的は、サポートが最小サポート以上であるすべての埋め込みサブツリーを見つけることです。

ツリー構造をエンコードする方法はいくつかあります。TreeMiner は、効率的なツリー操作とサポートカウントのために、ツリーの文字列表現を使用します。初期状態では、文字列は次のように設定されます。${\displaystyle \varnothing }$木の根から始めて、深さ優先探索の順序でノードラベルが文字列に追加されます。探索プロセスが子から親に戻るたびに、文字列に -1 が追加されます。たとえば、根に A、左の子に B、右の子に C のラベルが付いた単純な二分木は、文字列 AB -1 C -1 で表すことができます。

2 つの k サブツリーは、文字列表現が (k-1) 番目のノードまで同一である場合、同じ接頭辞同値類に属すると言われます。言い換えれば、接頭辞同値類のすべての要素は、最後のノードのみが異なります。たとえば、文字列表現が AB -1 C -1 と AB -1 D -1 の 2 つのツリーは、要素が (C, 0) と (D,0) である接頭辞同値類 AB に属します。接頭辞クラスの要素は、ノードラベルと、それが接続されているノードの 0 ベースの深さ優先インデックスの組み合わせによって指定されます。この例では、接頭辞クラス AB の両方の要素が、インデックス 0 のルートに接続されています。

ノードAのスコープは、2つの数値の組で表されます。${\displaystyle [l,r]}$ここで、lとrは、Aを根とする部分木における最小および最大のノードインデックスです。言い換えれば、lはAのインデックスであり、rはAの子孫の中で最も右にある葉のインデックスです。したがって、Aの子孫のインデックスは必ずAの範囲内にある必要があり、これは部分木のサポートを数える際に非常に有用な特性となります。

頻出部分木パターンは反単調性に従います。言い換えれば、k-部分木のサポートは、その(k-1)-部分木のサポート以下です。既知の頻出パターンのスーパーパターンのみが頻出である可能性があります。この性質を利用して、接頭辞クラス拡張による頻出(k-1)-部分木に基づいてk-部分木候補を生成できます。Cを2つの要素(x,i)と(y,j)を持つ接頭辞同値クラスとします。C'を要素(x,i)の拡張を表すクラスとします。C'の要素は、C内の2つの(k-1)-部分木に対して結合操作を実行することによって追加されます。(x,i)と(y,j)に対する結合操作は次のように定義されます。

• もし${\displaystyle i>j}$次に、(y,j)をC'に加えます。
• もし${\displaystyle i=j}$次に、C' に (y,j) と (y, ni) を追加します。ここで ni は C における x の深さ優先インデックスです。
• もし${\displaystyle i<j}$C'には要素を追加することはできません

この操作は、C 内の順序付けられた、ただし必ずしも異なるとは限らない任意の 2 つの要素に対して繰り返され、k-サブツリーの拡張プレフィックスクラスが構築されます。

TreeMiner は、サブツリーのスコープ リスト表現を使用して深さ優先候補生成を実行し、サポート カウントを高速化します。k サブツリー S は、トリプレット (t,m,s) で表現できます。ここで、t はサブツリーの由来となるツリー ID、m はプレフィックス一致ラベル、s は S の最後のノードのスコープです。データベース全体で S が異なるツリーにどのように出現するかによって、S は異なるスコープ リスト表現を持つことができます。TreeMiner は、サブツリーのスコープ リスト表現に対してクラス拡張を実行するスコープ リスト結合を定義します。2 つのサブツリーが存在する場合、2 つの要素 (x,i) と (y,j) を結合できます。${\displaystyle (t_{x},m_{x},s_{x})}$そして${\displaystyle (t_{y},m_{y},s_{y})}$以下のいずれかの条件を満たすもの。

• 対象範囲内のテスト:${\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}\subset s_{x}}$これは、${\displaystyle i=j}$。
• 範囲外テスト：${\displaystyle t_{x}=t_{y},m_{x}=m_{y},s_{y}>s_{x}}$これは、${\displaystyle i>j}$。

スコープリストテストで使用される個別のツリーIDを追跡することで、サブツリーのサポートを効率的に計算できます。