algorithm - 如何在有利位置树中搜索？

Question

我试图了解有利点树以及如何使用它们，所以为了做到这一点，我创建了简单的示例并尝试使用有利点树来解决它，这里是：

假设我们有 S={5,0,6.9,7} 并且我们想要执行 q=8（在 S 中搜索与 q 最近的邻居）怎么做？

我的解决方案如下：

首先：构建树：

第二：执行搜索：

根据维基百科，我必须找到 q=8 和现在为 7 的有利位置之间的距离，这将等于 1，因为它小于 mu（每个点到有利位置的距离的中位数），即2 然后我转到包含剩下的较近点的分支，然后我转到节点 6，但这是错误的答案，因为最近的邻居是 7 或 9。

我的问题：

1-构造的树是否正确？如果不是，请用解释纠正它。

2-在搜索中我错过了什么？请有人向我解释如何将其应用于我的示例进行搜索？

标签： algorithmsearchtreegraph-algorithmnearest-neighbor

Answer 1

我想先澄清几件事。

1. 如果您想在不使用 Vantage Point Tree 的情况下知道前 k 个值，则需要对所有数据进行排序并选择前 k 个元素。
2. 如果您想使用 Vantage Point Tree 了解前 k 个值，则需要对一些数据进行排序并选择前 k 个元素。
3. 在 S 中的每个元素都是一维的特殊情况下。KDTree 和 Vantage Point 树是相似的。
4. Vantage Point 树是为 S 中的高维元素制作的。
5. Tau 是一个超参数。

• 如果 Tau 太小，则只会显示几个元素。可能小于 k（所以搜索没用）。
• 如果 Tau 太大，几乎所有的数据集都会被评估。

了解这一点可以解决您的问题。

我有 S={5,0,6,9,7}
我想知道更接近的值 8。

建设副总裁

• 第一个 Vantage Point 的随机或非随机选择。

我会选择 0 作为 Vantage Point。

• mu 的第一个 Vantage Point 计算。

如果我将 mu(1) 设为 6.05。

1. 点树内的数据将是 0(vp),5,6 。

2. 点树外的数据将是 9,7。

• 随机或不随机选择第二个 Vantage Point OUTSIDE 第一个。

我会选择 7 作为 Vantage Point。

• 在第一个 Vantage Point 之外的第二个 Vantage Point 亩。

1 将数据分为 7(vp) 和 9。

• 随机或不随机选择第二个 Vantage Point 在第一个 Vantage Point 内。

我会选择 5 作为 Vantage Point。

• 在第一个 Vantage Point 内的第二个 Vantage Point 亩。

1 将数据分为 0 和 5(vp),6。

副总裁搜索

8的亲密朋友

让我们选择 Tau 等于 1。

• 第一步

vp(1)=0 和 8 之间的距离大于 tau + mu(1)。

VP(0) 内的所有点都可以忽略

• 第二步

vp(2 Out)=7 和 8 之间的距离小于 tau + mu(2 out)，但大于 tau-mu(2 out)。

应考虑所有值

vp(2 Out)=7 和 8 之间的距离小于 tan-mu(2 out)。

可以忽略 VP(0) 之外的所有点