标签: kdtree

我有一组要为其构建KD树的点.一段时间后,我想定期为这个KDTree添加几点.在scipy实现中有没有办法做到这一点

在用于kd树的维基百科条目上,提出了一种用于在kd树上进行最近邻居搜索的算法.我不明白的是步骤3.2的解释.你怎么知道没有一个更接近的点只是因为搜索点的分裂坐标和当前节点之间的差异大于搜索点的分裂坐标与当前最佳点之间的差异？

最近邻搜索NN在2D中使用KD树搜索的动画

最近邻居(NN)算法旨在找到树中最接近给定输入点的点.通过使用树属性快速消除搜索空间的大部分,可以有效地完成此搜索.在kd树中搜索最近邻居的过程如下:

1. 从根节点开始,算法以递归方式向下移动树,其方式与插入搜索点时相同(即,它向右或向左移动,具体取决于该点是大于还是小于当前节点.分裂维度).
2. 一旦算法到达叶节点,它就将该节点保存为"当前最佳"
3. 该算法展开树的递归,在每个节点执行以下步骤:1.如果当前节点比当前节点更接近,则它变为当前最佳节点.2.该算法检查在分裂平面的另一侧是否可能存在比当前最佳点更接近搜索点的任何点.在概念上,这通过使分裂超平面与搜索点周围的超球面相交来完成,该超球面具有等于当前最近距离的半径.由于超平面都是轴对齐的,因此将其实现为简单的比较,以查看搜索点的分割坐标与当前节点之间的差异是否小于从搜索点到当前最佳的距离(总坐标).1.如果超球面穿过平面,则在平面的另一侧可能存在更近的点,因此算法必须从当前节点向下移动树的另一个分支,寻找更近的点,遵循与之相同的递归过程.整个搜索.2.如果超球面不与分裂平面相交,则算法继续向上走树,并且消除该节点另一侧的整个分支.
4. 当算法完成根节点的此过程时,搜索完成.

通常,算法使用平方距离进行比较以避免计算平方根.另外,它可以通过在变量中保持平方电流最佳距离来进行比较来节省计算.

我用过kd-tree algoritham并制作树.

但是我发现树不平衡所以我的问题是如果我们使用kd-tree algoritham那么树总是平衡的,如果没有那么我们怎样才能使它平衡？

我们可以使用另一个algoritham喜欢AVL或Red-Black来平衡kd树吗？

我有一些示例数据,我使用kd-tree algoritham,但树不平衡.

 (14,31), (15,32), (17,42), (16,44), (18,52), (16,62)

操作 使用连通分量基于距离和标签对点进行聚类。

问题 NetworkX 节点存储属性和 Pandas DataFrame 之间的来回切换

• 看起来太复杂
• 查找节点时的索引/键错误

尝试 使用不同的函数，如 Scikit NearestNeighbours，但导致数据的来回移动相同。

问题 是否有更简单的方法来执行此连接组件操作？

例子

import numpy as np
import pandas as pd
import dask.dataframe as dd
import networkx as nx
from scipy import spatial

#generate example dataframe
pdf = pd.DataFrame({'x':[1.0,2.0,3.0,4.0,5.0],
                    'y':[1.0,2.0,3.0,4.0,5.0], 
                    'z':[1.0,2.0,3.0,4.0,5.0], 
                    'label':[1,2,1,2,1]}, 
                   index=[1, 2, 3, 4, 5])
df = dd.from_pandas(pdf, npartitions = 2)

object_id = 0
def cluster(df, object_id=object_id):
    # create kdtree
    tree = spatial.cKDTree(df[['x', 'y', 'z']])

    # get neighbours within distance for every point, store …

我必须实现k个最近邻居在kd-tree中搜索10维数据.

但问题是我的算法对于k = 1来说非常快,但是对于k> 1(k = 2,5,10,20,100),我的算法慢了2000倍

对于kd树来说这是正常的,还是我在做什么？

我有一个包含大约100万个文档的MongoDB.这些文档都有一个字符串,表示一个1位和0位的256位bin,如:

0110101010101010110101010101

理想情况下,我想查询近二进制匹配.这意味着,如果两个文件具有以下数字.是的,这是汉明距离.

Mongo目前不支持此功能.所以,我不得不在应用程序层中这样做.

因此,鉴于此,我试图找到一种方法来避免在文档之间进行单独的汉明距离比较.这使得时间基本上不可能完成.

我有很多内存.并且,在ruby中,似乎有一个伟大的宝石(算法)可以创建许多树,我似乎没有任何工作(还)可以减少我需要做的查询数量.

理想情况下,我想制作100万个查询,找到接近重复的字符串,并能够更新它们以反映这一点.

任何人的想法将不胜感激.

Python中是否有任何包允许对球体表面的经度/纬度进行类似kdtree的操作？(这需要适当考虑球面距离,以及经度环绕).

我有大量的2D线段.所以,我知道; 每个线段的行号,Begin(X,Y,Z)和End(x,Y,Z).我想获得给定线段的接近线段.同样对所有人.

为了找到距离,我可以应用它

如果我说我的数据是;

所以,最后我希望将接近线作为每个线段的矢量.我听说这种矢量矢量可以用r树数据结构.我正在搜索它,但仍然无法找到相关的一个.我也看了一下opencv,有一个r-tree但它说了一些关于分类器和训练阶段...所以,我想它不适合我.

任何人都可以知道如何得到 行号,然后它的邻居行为前;

1 = {2,4,,7,66,32,12}

2 = {1,4,5,6}

3 = {...} .. ..这种类型的矢量使用r树.

我知道,我们可以使用kd-tree获得这种类型的向量.但它是专为点数据而设计的.因此,我认为很难在这种情况下使用kd-tree.请帮忙,谢谢.

我想为我实现一些空间索引数据结构之王MKAnnotations.目前,当我尝试根据距离标准过滤它们时非常慢(3-4k的位置,目前非常慢,只有一个简单的双for...).

我想创建群集MKAnnotations,以确定它是否接近另一个群集.此外,这些位置处于某种(创建)顺序,并且需要"先前"/"下一步"功能来"跳跃"(这不是必须的).我已经阅读了有关kd-tree和r-tree结构的信息,它们似乎都满足了过滤/聚类的快速距离/邻居获取选项,但我不确定哪种选择最适合我,或者是否还有其他选项.我应该使用什么算法/数据结构？

更新:我将这些位置存储在Core Data数据库中,它们代表一个路径.打开地图时,它们被提取到一个数组中,然后我只使用该数组进行距离计算和注释创建.当用户移动/缩放地图时,我会遍历它们并确定需要在地图上更改的内容,因此整个内容都是静态的.据我所知,如果我要使用树,我可以在那里存储位置,当发生缩放/移动时,我只搜索它并获得新区域中的那些.这是真的 ？

即使在动态情况下,当我可以向此数组添加新位置时,它也只是一次插入而且很少发生.

我试图弄清楚哪种结构对点,kd树或八叉树的半径搜索更好？在这个问题中已经提到过,但没有答案.在我看来,由于八叉树具有固定的叶子大小,它已经可以计算出我需要访问的分支,而对于kd-tree,你必须迭代地访问分支,直到覆盖半径.