标签: nearest-neighbor

所以我有一个已经编写的迭代最近点(ICP)算法,它将模型拟合到点云.对于那些不知道ICP的人来说,快速教程是一个简单的算法,它适合模型的点,最终在模型和点之间提供均匀的变换矩阵.

这是一个快速图片教程.

步骤1.在模型集中找到与数据集最近的点:

第2步:使用一堆有趣的数学(有时基于渐变下降或SVD)将云拉得更近并重复直到形成一个姿势:

![图2] [2]

现在这一点很简单并且有效,我想要帮助的是: 我如何判断我的姿势是否合适？

所以目前我有两个想法,但它们有点像hacky:

1. ICP算法中有多少个点.也就是说,如果我几乎没有点,我认为姿势会很糟糕:

   但如果姿势实际上好呢？它可能是,即使只有几点.我不想拒绝好姿势:

所以我们在这里看到的是,如果低点在正确的位置,它们实际上可以成为一个非常好的位置.

因此,调查的另一个指标是提供的点与使用点的比率.这是一个例子

现在我们排除了距离太远的点,因为它们将是异常值,现在这意味着我们需要一个良好的起始位置让ICP工作,但我对此感到满意.现在在上面的例子中,保证会说NO,这是一个不好的姿势,这是正确的,因为包括点与点的比例是:

2/11 < SOME_THRESHOLD

这很好,但在上面显示的三角形颠倒的情况下会失败.它会说倒三角形是好的,因为所有的点都被ICP使用.

你并不需要是对ICP的专家来回答这个问题,我期待的好点子.利用这些要点的知识,我们如何分类它是否是一个好的姿势解决方案？

同时使用这两种解决方案是一个很好的建议,但如果你问我这是一个非常蹩脚的解决方案,非常愚蠢到只是为了达到它的门槛.

关于如何做到这一点有什么好主意？

PS.如果你想添加一些代码,请继续.我在c ++工作.

PPS.有人帮我标记这个问题,我不确定它应该落在哪里.

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

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

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

我有一个充满二维数据的数据库 - 地图上的点.每条记录都有一个几何类型的字段.我需要做的是将一个点传递给一个返回k个最近点的存储过程(k也会传递给sproc,但这很容易).我在http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx找到了一个查询,它获取了单个最近邻居,但我无法想出如何将其扩展到找到k个最近的邻居.

这是当前查询 - T是表,g是几何字段,@x是搜索的点,Numbers是一个整数1到n的表:

DECLARE @start FLOAT = 1000; 
WITH NearestPoints AS
(
     SELECT TOP(1) WITH TIES *,  T.g.STDistance(@x) AS dist
     FROM Numbers JOIN T WITH(INDEX(spatial_index)) 
     ON T.g.STDistance(@x) < @start*POWER(2,Numbers.n)
     ORDER BY n
)
SELECT TOP(1) * FROM NearestPoints
ORDER BY n, dist

内部查询选择最近的非空区域,外部查询然后选择该区域的最高结果; 外部查询可以很容易地更改为(例如)SELECT TOP(20),但如果最近的区域只包含一个结果,那么你就会坚持下去.

我想我可能需要递归搜索包含k个记录的第一个区域,但不使用表变量(这会导致维护问题,因为你必须创建表结构并且它可能会改变 - 有很多字段),我看不出怎么样.

我有一个n维点的集合,我想找到哪两个是最接近的.我可以为2个维度做的最好的是:

from numpy import *
myArr = array( [[1, 2],
                [3, 4],
                [5, 6],
                [7, 8]] )

n = myArr.shape[0]
cross = [[sum( ( myArr[i] - myArr[j] ) ** 2 ), i, j]
         for i in xrange( n )
         for j in xrange( n )
         if i != j
         ]

print min( cross )

这使

[8, 0, 1]

但这对于大型阵列来说太慢了.我可以应用什么样的优化？

有关:

两个不同的Numpy阵列中的点之间的欧几里德距离,而不是在内

我一直在尝试使用与weka机器学习库一起使用的Ibk最近邻算法.

我知道如何对实例进行分类,但我想实现协同过滤功能,因此我需要实际获取最接近感兴趣对象的实际对象列表.

我怎么在weka中使用它的Java API实际上这样做？

在我的教科书的摘录中,它说减少K运行这个算法的价值实际上增加了复杂性,因为它必须运行更"平滑".

任何人都可以向我解释这个吗？

我的理解是1NN,你在训练集中喂它.您在测试集上进行测试.假设您的测试集中有一个点.它在训练集中找到与它最接近的一个点,并返回该值.

当然,这比找到最近的3个点更简单3NN,加上它们的值并除以3？

我误解或忽视了什么？

我有一个csv文件,其中每一行都是表示数据点的数字向量.我想从命令行使用weka来计算csv文件中每个数据点的最近邻居.我知道如何从命令行执行k最近邻分类,但这不是我想要的.我想要真正的邻居.我该怎么做呢？

我想用weka而不是其他工具来做这件事.

编辑2: 请看一下TLDR的这个交叉路口.

编辑:鉴于粒子被分割成网格单元(比如16^3网格),让每个网格单元运行一个工作组和一个工作组中的多个工作项是一个更好的想法,因为可以有最大数量的每格网格的粒子？

在这种情况下,我可以将相邻单元格中的所有粒子加载到本地内存中,并通过它们迭代计算一些属性.然后我可以将特定值写入当前网格单元格中的每个粒子.

这种方法是否有利于为所有粒子运行内核以及每次迭代(大多数时间是相同的)邻居？

另外,理想的比例是number of particles/number of grid cells多少？

我正在尝试为OpenCL 重新实现(和修改)CUDA Particles,并使用它来查询每个粒子的最近邻居.我创建了以下结构:

• 缓冲区P保持所有粒子的3D位置(float3)

• 缓冲Sp存储int2粒子id对及其空间哈希值.Sp根据哈希值排序.(哈希只是从3D到1D的简单线性映射 - 还没有Z-indexing.)

• 缓冲区L存储缓冲区int2中特定空间哈希值的起始和结束位置对Sp.示例:L[12] = (int2)(0, 50).

  • L[12].x是具有空间散列Sp的第一个粒子的索引(in )12.
  • L[12].y是具有空间散列Sp的最后一个粒子的索引(in )12.

现在我拥有了所有这些缓冲区,我想迭代遍历所有粒子P并为每个粒子迭代它们最近的邻居.目前我有一个看起来像这样的内核(伪代码):

__kernel process_particles(float3* P, int2* Sp, int2* L, int* …

如果我在2D空间中有一组N个点,由它们位置的向量X和Y定义.什么是有效的算法

1. 选择要删除的固定数量(M)点,以便最大化剩余点之间的最短最近邻距离.
2. 移除最小数量的点,以使剩余点之间的最短最近邻距离大于固定距离(D).

按点按最短的最近邻距离进行排序并删除具有最小值的点不会给出正确的答案,因为您删除了两个紧密对的点,而您可能只需要删除这些对中的一个点.

对于我的情况,我通常处理1,000-10,000点,我可以删除50-90%的积分.

我想检索另一组点的给定范围内的所有点.比方说,找到距离任何地铁站500米范围内的所有商店.

我写了这个查询,这很慢,并且想要优化它:

SELECT DISCTINCT ON(locations.id) locations.id FROM locations, pois
WHERE pois.poi_kind = 'subway'
AND ST_DWithin(locations.coordinates, pois.coordinates, 500, false);

我正在使用最新版本的Postgres和PostGis(Postgres 9.5,PostGis 2.2.1)

这是表元数据:

                                         Table "public.locations"
       Column       |            Type             |                       Modifiers
--------------------+-----------------------------+--------------------------------------------------------
 id                 | integer                     | not null default nextval('locations_id_seq'::regclass)
 coordinates        | geometry                    |
Indexes:
    "locations_coordinates_index" gist (coordinates)


                                      Table "public.pois"
   Column    |            Type             |                     Modifiers
-------------+-----------------------------+---------------------------------------------------
 id          | integer                     | not null default nextval('pois_id_seq'::regclass)
 coordinates | geometry                    |
 poi_kind_id | integer                     |
Indexes:
    "pois_pkey" PRIMARY KEY, btree (id)
    "pois_coordinates_index" gist (coordinates)
    "pois_poi_kind_id_index" …