search - 检索最近的树到具有 k 个最近邻居的输入树？

Question

我想使用 K-最近邻方法从数据集中检索与输入树最近的树。树中的节点具有值，但每棵树中的分支没有标签。

例如：

树 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 近邻来解决这个问题。你有什么想法使用这种方法来解决这个问题吗？

score 2 · Accepted Answer

您必须为树定义距离度量以应用KNN算法。树有许多可能的度量标准，最流行的选择之一是树编辑距离 （如何计算树编辑距离？）

KNN不是搜索算法。它不用于查找最近的对象，而是用于将对象分类为预定义标签之一。它只是搜索给定点 X 的 K 个最近邻居，并返回一个包含大多数邻居的标签。

为了找到最近的树，假设您已经定义了TED(tree edit distance) 将简单地遍历 all treeintrees并选择最小化的树TED(tree,X)。

1 回答 1