ツリーカーネル：ツリー構造データ間の類似性の定量化

公開: 2022-03-11

ネットワークまたはグラフは、ノードの形式の構造化データの一種であり、ノード間の関係はリンクまたはエッジによって記述されます。 グラフのノードとエッジには、数値またはカテゴリ、あるいはさらに複雑な属性がいくつかある場合があります。

今日、大量のデータがネットワークまたはグラフの形式で利用可能です。 たとえば、Webページとハイパーリンク、ソーシャルネットワーク、セマンティックネットワーク、生物学的ネットワーク、科学文献の引用ネットワークなどを備えたWorldWideWebです。

ツリーは特殊なタイプのグラフであり、多くのタイプのデータを表すのに自然に適しています。 樹木の分析は、コンピューターとデータサイエンスの重要な分野です。 この記事では、ツリーのリンク構造の分析について説明します。 特に、ツリーグラフを相互に比較する方法であるツリーカーネルに焦点を当て、それらの類似点または相違点の定量化可能な測定値を取得できるようにします。 これは、分類やデータ分析など、多くの最新のアプリケーションにとって重要なプロセスです。

構造化データの類似性を測定することは、データサイエンスと機械学習の重要な分野です。

構造化データの教師なし分類

分類は、重要なコンポーネントの機械学習とデータ分析です。 一般に、分類は教師ありまたは教師なしのいずれかです。 教師あり分類では、クラスはすでに既知であり、分類モデルは、正しいクラスがすでに与えられているトレーニングデータから構築されます。 対照的に、教師なし分類は、何も知られていないクラスを識別しようとし、それらの類似性の測定に基づいてデータをカテゴリにグループ化します。

教師なし分類をグラフ理論と組み合わせて、類似したツリーネットワークのグループを識別することができます。 ツリーデータ構造は、複数のドメインからのオブジェクトをモデル化するために使用されます。 たとえば、自然言語処理（NLP）では、解析ツリーは順序付けられたラベル付きツリーとしてモデル化されます。 自動推論では、検索によって多くの問題が解決されます。検索スペースは、頂点が検索状態に関連付けられているツリーとして表され、エッジは推論ステップを表します。 また、HTMLやXMLドキュメントなどの半構造化データは、順序付けられたラベル付きツリーとしてモデル化できます。

これらのドメインは、教師なし分類手法を使用して有効に分析できます。 NLPでは、分類を使用して、一連の文を質問、コマンド、およびステートメントに自動的にグループ化できます。 同様に、類似したWebサイトのグループは、分類方法をHTMLソースに適用することで識別できます。 これらの各ケースで必要なのは、2本の木が互いにどの程度「類似」しているかを測定する方法だけです。

次元の呪い

ほとんどの分類アルゴリズムでは、データをベクトル化された形式に変換し、特徴空間でのデータの特徴の値を表す必要があります。これにより、データは線形代数を使用して特徴空間で分析できます。 ツリーのような構造化データまたは半構造化データでは、特徴空間が構造に関する情報を保持する必要があるため、結果のベクトルの次元（つまり、特徴空間内の特徴の数）が非常に高くなる可能性があります。

多くの分類手法では入力の次元に効果的にスケーリングできないことを考えると、これは重大な欠点となる可能性があります。 言い換えると、入力の次元数が増えると、分類力は低下します。 この問題は、次元の呪いとして知られています。

このパフォーマンスの低下の理由を理解するために、次元dのスペースXを考えてみます。 Xに均一に分布した点のセットが含まれているとします。 Xの次元数が増えると、同じ密度を維持するために必要な点の数が指数関数的に増える必要があります。 つまり、入力の次元が多いほど、そのデータはスパースである可能性が高くなります。 一般に、データ要素間の相関が弱すぎてアルゴリズムが検出できないため、スパースデータセットは適切な分類子を構築するのに十分な情報を提供しません。

次元の呪い

上記の各フィーチャスペースには、8つのデータポイントが含まれています。 1次元空間では、左側に5つのポイント、右側に3つのポイントのグループを簡単に識別できます。 これらのポイントを多数のフィーチャ（つまりディメンション）に拡張すると、これらのグループを見つけるのがより困難になります。 実際のアプリケーションでは、フィーチャスペースは簡単に数百の次元を持つことができます。

ドメインに関する情報を効果的に使用して管理可能な機能のセットを選択できる場合は、構造化データのベクトル化された表現が適切です。 そのような情報が利用できない場合は、ベクトル空間で操作を実行せずに、構造化データを直接処理できる手法を利用することが望ましいです。

カーネル法

カーネル法は、データをベクトル形式に変換する必要性を回避します。 彼らが必要とする唯一の情報は、データセット内のアイテムの各ペアの類似性の測定です。 この測定値はカーネルと呼ばれ、それを決定するための関数はカーネル関数と呼ばれます。 カーネル法は、特徴空間で線形関係を探します。 機能的には、これらは特徴空間内の2つのデータポイントの内積を取ることと同等であり、実際、特徴の設計はカーネル関数の設計において依然として有用なステップである可能性があります。 ただし、カーネル法は、カーネル関数がデータを入力として受け取ることができる対称の正半定値関数である限り、内積をカーネル関数に置き換えることができることを示すことができるため、特徴空間を直接操作することを避けます。元のスペースで。

したがって、カーネル関数を使用する利点は、特徴空間のサイズではなく、カーネル関数の複雑さに依存しない計算の複雑さで巨大な特徴空間を分析できることです。つまり、カーネルメソッドは呪いに苦しむことはありません。次元の呪い。

n個の例で構成される有限データセットを検討すると、サイズが常にn×nであるカーネル行列を生成することにより、データ内の類似性の完全な表現を取得できます。 このマトリックスは、個々の例のサイズとは無関係です。 このプロパティは、大きな特徴空間を持つ例の小さなデータセットを分析する場合に役立ちます。

一般に、カーネル法は、データ表現の質問に対する異なる答えに基づいています。 入力ポイントを特徴空間にマッピングする代わりに、データはカーネル行列Kのペアワイズ比較によって表され、関連するすべての分析をカーネル行列に対して実行できます。

データをカーネル行列に変換します。

多くのデータマイニング方法をカーネル化できます。 サポートベクターマシンなどのカーネルメソッドを使用してツリー構造のデータインスタンスを分類するには、有効な（対称正定値）カーネル関数k：T×T→ R （ツリーカーネルとも呼ばれる）を定義するだけで十分です。 実用的に有用なツリーカーネルの設計では、ツリーのサイズ全体で多項式時間で計算可能であり、同型グラフを検出できる必要があります。 このようなツリーカーネルは、完全なツリーカーネルと呼ばれます。

ツリーカーネル

それでは、木の類似性を測定するための便利なツリーカーネルをいくつか紹介しましょう。 主なアイデアは、カーネルマトリックスを構築するために、データセット内のツリーの各ペアのカーネルを計算することです。カーネルマトリックスは、ツリーのセットを分類するために使用できます。

文字列カーネル

まず、文字列カーネルの簡単な紹介から始めます。これは、ツリーを文字列に変換することに基づく別のカーネルメソッドを紹介するのに役立ちます。

num y （s）を、文字列s内の部分文字列yの出現数として定義しましょう。 s | 文字列の長さを示します。 ここで説明する文字列カーネルは、次のように定義されます。

K文字列（S 1 、S 2 ）= Σs∈Fnums （ S 1 ）num s （ S 2 ）w s

ここで、 FはS1とS2の両方で発生するサブストリングのセットであり、パラメーターwsは重みパラメーターとして機能します（たとえば、重要なサブストリングを強調するため）。 ご覧のとおり、このカーネルは、多くの共通のサブストリングを共有している場合、ストリングのペアにより高い値を与えます。

ツリーを文字列に変換することに基づくツリーカーネル

この文字列カーネルを使用して、ツリーカーネルを構築できます。 このカーネルの背後にある考え方は、ツリーの構造をエンコードする体系的な方法で2つのツリーを2つの文字列に変換し、次に上記の文字列カーネルをそれらに適用することです。

次のように、2つのツリーを2つの文字列に変換します。

Tがターゲットツリーの1つを示し、 label（n s ）がTのノードnsの文字列ラベルであるとします。 tag（n s ）は、nsをルートとするTのサブツリーの文字列表現を示します。 したがって、 n rootがTのルートノードである場合、 tag（n root ）はツリーT全体の文字列表現です。

次に、 string（T）= tag（n root ）がTの文字列表現を表すとします。 次の手順をボトムアップ方式で再帰的に適用して、 string（T）を取得します。

  • ノードnsがリーフの場合、 tag（n s ）=“ [” + label（n s ）+“]”とします（ここで、 +は文字列連結演算子です）。
  • ノードnsがリーフではなく、 c個の子n 1 、n 2 、…、n cがある場合、 tag（n 1 ）、tag（n 2 ）、…、tag（n c ）を辞書式順序でソートしてタグを取得します（n 1 * ）、tag（n 2 * ）、…、tag（n c * ） 、およびlet tag（n s ）=“ [” + label（n s ）+ tag（n 1 * ）+ tag（n 2 * ）+…+ tag（n c * ）+“]” 。

次の図は、このツリーから文字列への変換の例を示しています。 結果は、「[」などの開始区切り文字で始まり、対応する終了文字「]」で終わる文字列です。ネストされた区切り文字の各ペアは、特定のノードをルートとするサブツリーに対応します。

文字列カーネルで使用するための、ツリー構造のデータの文字列表現。

これで、上記の変換を2つのツリーT1とT2に適用して、2つの文字列S1とS2を取得できます。 そこから、上記の文字列カーネルを簡単に適用できます。

2つの文字列S1とS2を介したT1とT2の間のツリーカーネルは、次のように指定できます。

Kツリー（T 1 、T 2 ）= K文字列（文字列（T 1 ）、文字列（T 2 ））= K文字列（S 1 、S 2 ）= Σs∈Fnums （ S 1 ）num s （S 2 ）w s

ほとんどのアプリケーションでは、重みパラメータはw |になります。 s | 、長さに基づいて部分文字列に重みを付ける| s | 。 wの一般的な重み付け方法| s | それは：

  • 一定の重み付け（ w | s | = 1 ）
  • kスペクトル均等化（ | s | =kの場合はw|s | = 1 、それ以外の場合はw | s | = 0 ）
  • 指数加重（ w | s | =λ | s |ここで、 0≤λ≤1は減衰率です）

カーネルを計算するには、すべての一般的な部分文字列Fを決定し、それらがS1とS2で発生する回数を数えるだけで十分です。 一般的な部分文字列を見つけるこの追加の手順は、よく研究された問題であり、接尾辞木または接尾辞配列を使用して、 O（ | S 1 | + | S 2 | ）で実行できます。 ノードのラベルを記述するために必要な文字の最大数（ビット、バイト、文字など）が一定であると仮定すると、変換される文字列の長さは|です。 S 1 | = O（ | T 1 | ）および| S 2 | = O（ | T 2 | ） 。 したがって、カーネル関数の計算の計算の複雑さはO（ | T 1 | + | T 2 | ）であり、これは線形です。

サブパスに基づくツリーカーネル

上記のツリーカーネルは、ツリーを文字列に変換するために、水平または幅優先のアプローチを使用していました。 このアプローチは非常に単純ですが、この変換は、元の形式で直接ツリーを操作できないことを意味します。

このセクションでは、ツリーの垂直構造を操作するツリーカーネルを定義し、カーネルがツリーを直接操作できるようにします。

ルートからリーフの1つへのパスのサブセクションはサブパスと呼ばれ、サブパスセットはツリーに含まれるすべてのサブパスのセットです。

ツリーカーネルのサブパスセット。

2つのツリーT1とT2の間にツリーカーネルK（T 1 、T 2 ）を定義するとします。 サブパスセットを使用することで、このツリーカーネルを次のように定義できます。

K（T 1 、T 2 ）= Σp∈Pnump （ T 1 ）num p （ T 2 ）w | p |

ここで、 num p （T）は、サブパスpがツリーTで発生する回数です。 p | はサブパスp内のノードの数であり、 PはT1とT2内のすべてのサブパスのセットです。 w | p | は前のセクションで紹介したものと同様の重量です。

ここでは、深さ優先探索を使用したこのカーネルの簡単な実装を示します。 このアルゴリズムは2次時間で実行されますが、接尾辞木または接尾辞配列、または平均線形時間（ O（ | T 1 | log | T 2 | ） ）を達成できるマルチキークイックソートアルゴリズムの拡張を使用するより効率的なアルゴリズムが存在します。

 subpath_track = {} def generate_subpaths(path, l): if l == len(path): if tuple(path) not in subpath_track: subpath_track[tuple(path)] = 1 else: subpath_track[tuple(path)] += 1 else: index = 0 while l+index-1 < len(path): if tuple(path[index: l+index]) not in subpath_track: subpath_track[tuple(path[index: l+index])] = 1 else: subpath_track[tuple(path[index: l+index])] += 1 index += 1 generate_subpaths(path, l+1) def get_subpaths(graph, root, track, path): track[root] = True if graph.degree(root) == 1: generate_subpaths(path, 1) else: for node in graph.neighbors(root): if node not in track: get_subpaths(graph, node, track, path + [node, ]) def kernel_subpath(t1, t2, common_track): kernel_v = 0 for p in subpath_track: kernel_v += common_track[t1][p]*common_track[t2][p] return kernel_v

この例では、重みパラメータw |を使用しました。 s | w | p | =1 。 これにより、すべてのサブパスに等しい重みが与えられます。 ただし、 kスペクトルの重み付け、または動的に割り当てられた重み値を使用することが適切な場合が多くあります。

マイニングウェブサイト

まとめる前に、ツリー分類の実際のアプリケーションの1つであるWebサイトの分類について簡単に見てみましょう。 多くのデータマイニングのコンテキストでは、一部のデータがどの「タイプ」のWebサイトからのものであるかを知ることは有益です。 同様のサービスのWebページの構造が類似しているため、ツリーを使用してさまざまなWebサイトのページを非常に効果的に分類できることがわかりました。

どうすればいいですか？ HTMLドキュメントは、ツリーに非常によく似た論理的なネスト構造を持っています。 各ドキュメントには1つのルート要素が含まれ、追加の要素が内部にネストされています。 HTMLタグ内のネストされた要素は、そのタグの子ノードと論理的に同等です。

HTMLをツリーに変換します。

HTMLドキュメントをツリーに変換できるコードを見てみましょう。

 def html_to_dom_tree(root): node_id = 1 q = deque() graph = nx.Graph() q.appendleft({'element': root, "root_id": node_id}) while len(q): node = q.pop() if node and node['element'].name == "body": graph.add_node(node_id, element=node['element'].name) node_id += 1 root_id = node['root_id'] labels[root_id] = node['element'].name for t in node['element'].contents: if t and t.name: graph.add_node(node_id, element=t.name) graph.add_edge(root_id, node_id) q.appendleft({"element": t, "root_id": node_id}) node_id += 1 return graph

これにより、次のようなツリーデータ構造が生成されます。

HTMLドキュメントツリー。

上記の実装では、いくつかの便利なPythonライブラリを使用しています。複雑なグラフ構造を操作するためのNetworkXと、Webからデータを取得してドキュメントを操作するためのBeautifulSoupです。

html_to_dom_tree(soup.find("body"))を呼び出すと、Webページの<body>要素をルートとするNetworkXグラフオブジェクトが返されます。

1,000のWebサイトホームページのセットでグループを検索するとします。 各ホームページをこのようなツリーに変換することで、たとえば前のセクションで示したサブパスツリーカーネルを使用して、それぞれを比較できます。 これらの類似性の測定により、たとえば、eコマースサイト、ニュースサイト、ブログ、教育サイトは、相互の類似性によって簡単に識別できることがわかりました。

結論

この記事では、ツリー構造のデータ要素を相互に比較する方法を紹介し、カーネル法をツリーに適用して、それらの類似性の定量化可能な測定値を取得する方法を示しました。 カーネル法は、高次元空間で操作する場合に優れた選択肢であることが証明されています。これは、ツリー構造を操作する場合の一般的な状況です。 これらの手法は、カーネルマトリックス上で動作する十分に研究された方法を使用して、ツリーの大規模なセットをさらに分析するための準備を整えます。

ツリー構造は、XMLおよびHTMLドキュメント、化合物、自然言語処理、または特定のタイプのユーザーの動作など、多くの実際の単語領域で発生します。 HTMLからツリーを構築する例で示されているように、これらの手法により、これらのドメインで意味のある分析を実行できます。