如何在有利位置树中进行搜索？
我正在尝试理解vantage点树以及如何使用它们，因此为了做到这一点，我创建了一个简单的示例，并尝试使用vantage点树来解决它，如下所示：
假设我们有S={5,0,6.9,7}，我们想要执行q=8 (在S中搜索离Q最近的邻居)该怎么做？
我的解决方案如下：
首先:构建树：
第二:执行搜索：
根据Wikipedia，我必须找到q=8和有利位置之间的距离，现在是7，这将等于1，因为它小于µ(每个点到有利位置的距离的中位数)是2，所以我转到包含左边更近的点的分支，通过它我转到节点6，但这是错误的答案，因为最近的邻居要么是7，要么是9。
我的问题是：
1-构建的树是否正确？如果不是，请改正并解释。
2-在搜索中，我错过了什么？有没有人可以给我解释一下如何在我的例子中使用它来执行搜索？
回答 1
Stack Overflow用户
发布于 2020-10-30 05:19:35
我想先澄清几件事。
- 如果你想知道数据的前k个值，你需要对数据进行排序并选择前k个元素。
- 如果你想使用优势点树知道前k个值，你需要对一些<>E29数据排序并选择前k个元素。
- 在特殊情况下，S中的每个元素都是一维的。similar.
- Vantage和Vantage点树都是针对高维元素在S.中生成的hiperparameter.
- If点树。KDTree是
- Tau太小了，只会显示几个元素。可能小于k(所以搜索是无用的)。
- 如果Tau太大，几乎所有的数据集都会被评估。
了解这一点可以解决你的问题。
我有S={5,0,6,9,7}
我想知道8的近似值。
VP构建
- 随机或非随机地选择第一个有利位置。
我将选择0作为Vantage Point。
第一个有利位置calculation.的
- mu
如果我取µ(1)为6.05。
- 点树内的数据将为0(Vp)，5，6。
- 点树外部的数据将是9，7。
- 随机或非随机地选择第一个以外的第二个有利位置。
我会选7作为Vantage Point。
- mu在第一个有利位置之外的第二个有利位置。
1将数据分为7(vp)和9。
- 随机或非随机地选择第一个有利位置内的第二个有利位置。
我会选择5作为Vantage Point。
- mu在第一个有利位置内的第二个有利位置。
1将数据分为0和5(vp),6。
VP搜索
8的亲密朋友
让我们选择Tau等于1。
- First step
vp(1)=0和8之间的距离大于τ+µ(1)。
可以忽略VP(0)内的所有点
- 第二步
vp(2out)=7和8之间的距离小于tau +mu2(2out)，但大于tau-mu2(2out)。
所有的值都应该被认为是
vp(2out)=7和8之间的距离小于tan(2out)。
可以忽略VP(0)之外的所有点
https://stackoverflow.com/questions/54538064
复制相似问题
腾讯云开发者
