ツリーのカーネル: ツリー構造の data_html/css_WEB-ITnose 間の類似性の定量化-htmlチュートリアル-php.cn

36 Big Data 特別記事、この記事は 36 Big Data Translation Team-Yunni によって書かれており、翻訳者と出典、およびこの記事へのリンクが示されていないコンテンツは http://www.36dsj.com/archives です。 /43411 は侵害です。

数値 (データ構造名詞)

ツリー図は、n (n>=1) 個の限定されたノードで構成される一連の階層関係であるデータ構造です。根が上を向き、葉が下を向いている、逆さまの木に見えることから「ツリー」と呼ばれています。次の特徴があります: 各ノードは 0 個以上の子ノードを持ち、親ノードを持たないノードはルートノードと呼ばれます。ルートノードを除く各非ルートノードは 1 つの親ノードのみを持ち、各子ノードは分割できます。複数の互いに素なサブツリーへの変換

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

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

分類は機械学習とデータ分析の重要な部分です。一般に、分類は教師付きまたは教師なしで行うことができます。教師あり分類では、分類が既知であり、トレーニングデータから分類モデルが構築されます。このトレーニングデータには正しい分類が与えられています。対照的に、教師なし分類では、既知の部分が存在しないクラスを見つけようとし、何らかの類似性の尺度に基づいてデータをクラスにグループ化します。教師なし分類法をグラフ理論と組み合わせて、類似したツリーネットワークを識別できます。ツリーデータ構造は、いくつかのドメインモデルオブジェクトに使用されます。たとえば、自然言語処理 (NLP) では、解析ツリーは順序付けされたラベル付きツリーとしてモデル化されます。自動推論では、多くの問題が検索によって解決され、検索空間はツリーとして表され、その頂点は検索状態に対応し、エッジは推論ステップを表します。さらに、HTML や XML ドキュメントなどの半構造化データは、順序付けられたタグ付きツリーとしてモデル化できます。

これらの領域は、教師なし分類手法を通じて効果的に分析できます。自然言語処理 (NLP) では、分類を使用して、一連の文を質問、コマンド、およびステートメントに自動的に分離できます。同様に、HTML ソース識別分類方法を通じて、類似した Web サイトのグループを識別できます。いずれの場合も、必要なのは、2 つの木が互いにどの程度「似ているか」を測定する方法です。

次元性の呪い

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

多くの分類手法が次元入力を効率的にスケールできないことを考慮すると、これは重大な欠点になる可能性があります。言い換えれば、入力の次元が増加するにつれて、分類能力は低下します。この問題は「次元性の呪い」と呼ばれます。

このパフォーマンス低下の理由を理解するために、次元 D の空間 X を考えてみましょう。 X に一様に分布した点のセットが含まれているとします。 X の次元数が増加すると、同じ密度を維持するために必要な点の数が指数関数的に増加する必要があります。言い換えれば、入力の次元が大きくなるほど、データが疎になる可能性が高くなります。一般に、まばらなデータセットでは、データ要素間の相関が検出アルゴリズムに対して弱すぎるため、適切な分類を確立するのに十分な情報が得られません。

次元の呪い

各特徴空間には 8 つのデータポイントが含まれています。 1 次元空間では、左側の 5 つの点のグループと右側の 3 つの点のグループを識別するのは簡単です。高等関数 (次元など) で点を引き伸ばすと、グループを見つけることが難しくなります。実際のアプリケーションでは、特徴空間は簡単に数百の次元を持つことができます。

構造化データのベクトル化は、ドメインに関する情報を効果的に使用して管理可能な一連の機能を選択できる場合に適しています。この情報が利用できない場合は、ベクトル空間で演算を実行せずに構造化データを直接処理する手法を使用することができます。

カーネルメソッド

カーネルメソッドを使用すると、データをベクトル形式に変換する必要がなくなります。彼らが必要とする唯一の情報は、データセット内の各ペアの類似性の尺度です。この尺度をカーネルと呼び、それを決定する関数をカーネル関数と呼びます。特徴空間におけるカーネルメソッドは線形関係を見つけます。機能的には、これらは特徴空間内の 2 つのデータポイントの内積に相当し、真の機能設計、つまりカーネル内の機能設計は依然として有用なステップである可能性があります。ただし、カーネル法は、カーネル関数が対称であり、正定関数を入力として使用できる限り、点積をカーネル関数で置き換えることができることが示されているため、特徴空間での直接操作を回避します。オリジナル空間データ。

組み込み関数を使用する利点は、特徴空間のサイズではなく、カーネル関数の複雑さに依存する計算の複雑さで巨大な特徴空間を解析できることです。これは、カーネルアプローチが次元に依存しないことを意味します。

有限データセットの窒素の例を考えると、サイズが常に nxn であるカーネル行列を生成することによって、データ内の類似性の完全な表現を得ることができます。各パーソナライゼーションの例では、このマトリックスのサイズは独立して設定されます。このプロパティは、サンプルの小さなデータセットに分析すべき大きな特徴空間がある場合に役立ちます。一般に、カーネルのアプローチは、データの質問に対するさまざまな回答に基づいています。入力ポイントを特徴空間にマッピングする代わりに、データはカーネル行列のペアごとの比較によって表され、すべての関連する分析は組み込み行列に対して実行できます。

多くのデータマイニング手法をカーネル化できます。ツリー構造のデータを分類する場合、サポートベクターマシンなどのカーネル法が使用されます。カーネル法は、ツリーカーネルとも呼ばれる有効な (正定値の) カーネル関数 K: T×T→R を定義できます。実際に有用なツリーカーネルを設計する場合、ツリーカーネルがツリーのサイズに応じて多項式時間で計算可能であり、等構造グラフを検出できる必要があります。このようなツリーのカーネルは完全ツリーカーネルと呼ばれます。

ツリーカーネル

さて、木の類似性を測定するために役立ついくつかのツリーカーネルを紹介しましょう。主なアイデアは、ツリーのグループを分類するために使用できるカーネルマトリックスを構築するために、ツリーのペアごとにカーネルを計算することです。

文字列カーネル

まず最初に、文字列カーネルについて簡単に説明します。これは、文字列ツリーへの変換に基づく別のカーネルアプローチを導入するのに役立ちます。

numy(S) を文字列内の部分文字列の出現数として定義し、Y、|s| は文字列の長さを表します。ここで説明する文字列カーネルは次のように定義されます:

ここで、F は S1 と S2 に現れる部分文字列のセットであり、パラメータは重みパラメータとして使用されます (たとえば、重要な部分文字列を強調するため)。このカーネルは、共通の部分文字列が多数ある場合に、より高い値を提供することがわかります。

ツリーから文字列への変換に基づくツリーカーネル

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

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

T をターゲットツリーと T ラベルノードのラベル (NS) を表すものとします。 NS 文字列ラベル (NS) は、NS をルートとする T のサブツリーの文字列表現を指します。したがって、それが T のルートノードである場合、tag(nroot) はツリー T 全体の文字列表現になります。

次に、string(t)=tag(nroot) で T の文字列を表します。以下の手順を再帰的に適用して、ボトムアップ方式で文字列 (T) を取得します:

 ノード NS がリーフ構造の場合、tag(ns) = “[” + label(ns) + "]" とします。 (ここで + は文字列連結演算子です)。

ノード NS がリーフ構造ではなく、C 個の子 n1、n2、…、nc を持つ場合、ボキャブラリ内の tag(n1)、tag(n2)、…、tag(nc) をソートして tag(n1*) を取得します、タグ(n2*)、…、タグ(nc*)、タグ(ns) = “[” + ラベル(ns) + タグ(n1*) + タグ(n2*) + … + タグ(nc*) + 「]」。

下の図は、このレッスンでのツリーから文字列への変換の例を示しています。結果は、"[" などの開始区切り文字で始まり、"]" などの開始区切り文字で終わる文字列になります。ネストされた二重対応するサブツリーはそれぞれ、特定のノード区切り文字をルートとします。

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

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

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

上記のツリーカーネルは、水平方向のツリーカーネル、または最初のツリーカーネルを使用します。 width ツリーを文字列に変換するメソッド。この方法は単純ですが、この変換は、元の形式のツリーに対して直接操作できないことを意味します。

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

ルートから多くの葉の 1 つまでのパスのサブパスのセット。ツリー内のすべてのサブパスの設定が含まれます:

2 つのツリー T1 と T2 の間にツリーカーネル関数 K(T1,T2) を定義するとします。サブパスのセットを使用して、このツリーのカーネルを定義できます:

数値 (T)はツリー T に発生するサブパスの数 P、P は P 個の子ノードの数、P は T1 と T2 のすべてのサブパスのセットです。 W|P| は、前のセクションで紹介したものと同様の重みです。

ここでは、深さ制限された検索を使用したこのカーネルの簡単な実装を提案します。このアルゴリズムは二次時間で実行されますが、サフィックスツリーとサフィックス配列、または拡張された複数アイテムのクイックソートアルゴリズムを使用したより効率的なアルゴリズムが存在し、平均して線形時間を達成できます

(O(|T1|log|T2|))

この例では、重み付けパラメーター w|s| w|p| を使用します。これにより、すべてのサブパスに同じ重みが与えられます。ただし、多くの場合、K ラインの重み、または動的に割り当てられた重み値を使用することが適切です。

Web サイトをさらに深く掘り下げる

まとめの前に、実際のツリー分類である機密 Web サイトを簡単に見てみましょう。多くのデータマイニングのコンテキストでは、どのサイトからどのような「タイプ」のデータが取得されているかを知ることが有益です。同様のページは同様のサービスで構造化されているため、ツリーを使用してさまざまな Web サイトから低レベルのページを分類することは非常に効果的です。

どうやってやるの？ HTML ドキュメントの論理的な入れ子構造は、ツリーによく似ています。各ドキュメントにはルート要素が含まれており、その中にネストされた他の要素が含まれています。 HTML タグ内にネストされた要素は、論理的にはこのタグの子ノードと同等です。

HTML ドキュメントをツリーに配置できるコードを見てみましょう:

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

実際、上記はいくつかの便利な Python ライブラリを利用しています: networkx 、ネットワークからデータを取得し、複雑なグラフ構造のファイルを操作します。

私たちは 1000 の Web サイトのトップページでグループを見つけたいと考えています。各 Web ページをそのようなツリーに変換すると、たとえば前のセクションで説明したパスツリーカーネルを使用して、それらを相互に比較できます。これらの測定された類似性を通じて、たとえば、電子商取引 Web サイト、ニュース Web サイト、ブログ、教育 Web サイトの類似性を簡単に判断できることがわかります。

結論

この記事では、ツリー構造のデータ要素の比較を紹介し、カーネルメソッドを適用してそれらの類似性の定量化可能な尺度を取得する方法を示しました。カーネルメソッドは、高次元空間の一般的なケースでツリー構造を扱う場合に良い選択であることが証明されています。これらの技術は、カーネルマトリックス段階で動作するリサーチ手法を使用して、大規模なツリーセットのさらなる分析を提供します。

ツリー構造は、XML や HTML ドキュメント、化合物、自然言語処理、特定の種類のユーザー行動など、多くの実世界のドメインで使用されます。 HTML からツリーを構築する例で示されているように、これらの技術を使用すると、これらの領域で有意義な分析を実行できます。

元のアドレス: ツリーカーネル: ツリー構造データ間の類似性の定量化

End.

このウェブサイトの声明

この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。