K-nearest neighbor アプローチを使用して、データセットから入力ツリーに最も近いツリーを取得したいと考えています。ツリーのノードには値がありますが、各ツリーのブランチにはラベルがありません。
例えば：
ツリー 1: (S (V c) (N (P y)) (V (V o) (N (D t) (N d))))
ツリー 2: (S (V (V p) (P (R o)) (N (D t) (N d))))
この問題に k-nearest neighbor を使用したいと思います。この問題にこのアプローチを使用する考えはありますか?
KNNアルゴリズムを適用するには、木の距離測定を定義する必要があります。ツリーで使用できるメトリックは多数ありますが、最も一般的な選択肢の 1 つはツリー編集距離です
(ツリー編集距離を計算するにはどうすればよいですか? ) 。
KNNは検索アルゴリズムではありません。最も近いオブジェクトを見つけるために使用されるのではなく、定義済みのラベルの 1 つにオブジェクトを分類するために使用されます。与えられた点 X の K 個の最近傍を単純に検索し、ほとんどの近傍を含むラベルを返します。
最も近いツリーを見つけるには、(ツリーの編集距離) が既に定義されていると仮定すると、すべてをTED反復処理して最小化するものを選択するだけです。treetreesTED(tree,X)
Tree Edit Distance に関する非常に優れたリソースもここにあります: http://www.inf.unibz.it/dis/projects/tree-edit-distance/tree-edit-distance.php