如何使用K最近邻算法检索与输入树最接近的树？

我想使用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最近邻算法。你对如何使用这种方法解决这个问题有任何建议吗？

回答：

你需要为树定义一个距离度量来应用KNN算法。树的度量有很多选择，其中最常用的是树编辑距离（如何计算树编辑距离？）

KNN不是一种搜索算法。它不是用来寻找最接近的对象，而是将对象分类到预定义的标签之一。它只是搜索给定点X的K个最近邻居，并返回大多数邻居拥有的标签。

要找到最接近的树，假设你已经定义了TED（树编辑距离），只需遍历trees中的所有tree，并选择使TED(tree,X)最小化的那个即可。

学技术