2

我有一个地板,在地板上的不同位置放置了各种传感器。对于每个传输设备,传感器可能会检测到其读数。地板上可能有 6-7 个传感器,并且某些传感器可能无法检测到特定读数,但可能会被其他一些传感器检测到。

对于我得到的每一个读数,我想确定那个读数在地板上的位置。我们在逻辑上将地板划分为 TILE(5x5 英尺区域),并找到每个 TILE 的理想读数应该由每个传感器设备检测到(基于一些传输路径损耗方程)。

我使用来自每个 TILE 的“N”传感器设备的预计算读数作为 N 维空间中的一个点。当我得到一个真实的生活读数时,我会找到这个读数最近的邻居,并将这个读数分配给那个位置。

我想知道是否有 K 最近邻的变体,其中一个维度可以从考虑中删除。当特定传感器未报告任何读数时,这将特别有用。我知道使用 kd-tree 或 R 树之类的算法不可能对维度进行加权。但是,我想知道在计算最近邻时是否可以丢弃维度。有没有这样的算法?

编辑:

我想知道的是,相同的 R/kd 树是否可以用于具有不同查询的 k 最近搜索,其中每个查询具有不同的维度权重?我不想为每个不同的维度权重构建另一个 kd-tree。

编辑2:

python中是否有任何库,可让您指定自定义距离函数并搜索k个最近邻居?本质上,我想对不同的查询使用不同的自定义距离函数。

4

2 回答 2

0

对于 R-trees 和 kd-trees,使用加权 M​​inkowski 范数很简单。只需将权重放入您的距离方程中!

将权重放入欧里德点到矩形的最小距离是微不足道的,只需查看常规公式并根据需要插入权重即可。

在树构建时使用距离,因此您可以在查询时根据需要改变权重。

于 2013-12-23T11:50:02.230 回答
0

在经历了很多关于stackoverflow的问题,最后进入scipy kd树源代码的细节之后,我意识到以下链接中“celion”的答案是正确的:

KD-Trees 和缺失值(向量比较)

摘录:
“我认为最好的解决方案是在你正在使用的代码中弄脏你的手。大概最近邻搜索计算树叶中的点和查询向量之间的距离;你应该能够修改这可以处理点和查询向量大小不同的情况。例如,如果树中的点以 3D 形式给出,但查询向量的长度仅为 2,那么点之间的“距离”(p0,p1, p2) 和查询向量 (x0, x1) 将是

sqrt( (p0-x0)^2 + (p1-x1)^2 )

我没有深入研究您链接到的 java 代码,但如果您需要帮助,我可以尝试准确找到需要进行更改的地方。

-克里斯

PS - 你可能不需要上面等式中的 sqrt,因为距离的平方通常是等价的。”

于 2014-01-01T09:54:34.020 回答