两个阵列的高效匹配（如何使用KDTree）

我有两个2d阵列，obs1和obs2。它们代表两个独立的测量系列，并且两者都具有dim0 = 2，并且略有不同，例如obs1.shape = (2, 250000)和obs2.shape = (2, 250050)。 obs1[0]和obs2[0]表示时间，obs1[1]和obs2[1]表示一些空间坐标。两个数组都是（或多或少）按时间排序。时间和坐标应该在两个测量系列之间是相同的，但实际上它们不是。另外，obs1中的每个测量值都不是obs2中的相应值，反之亦然。另一个问题是时代可能存在轻微的偏差。两个阵列的高效匹配（如何使用KDTree）

我正在寻找一种有效的算法，将obs2中的最佳匹配值与obs1中的每个测量相关联。目前，我不喜欢这样写道：

define dt = some_maximum_time_difference 
define dx = 3 
j = 0 
i = 0 
matchresults = np.empty(obs1.shape[1]) 
for j in obs1.shape[1]: 
    while obs1[0, j] - obs2[0, j] < dt: 
     i += 1 
    matchresults[j] = i - dx + argmin(abs(obs1[1, i] - obs2[1, i-dx:i+dx+1]))

这就产生了良好的效果。但是，它非常缓慢，循环运行。

我会非常感谢有关如何快速改进此算法的想法，例如，使用KDtree或类似的东西。

来源

2013-03-20 andreas-h

能否请您扩大'first_obs2_index_with_time_difference_lessthan_delta_t resulting_i位= I + argmin（ABS（OBS1 [1，I] - OBS2 [1，I-delta_x：1 + delta_x + 1]）'假设你是不是？在这里执行另一个循环，我不相信KDTrees会加速太多事情。 – 2013-03-20 13:58:16

@MikyDinescu感谢您的问题;我更新了原始文章中的算法。 – 2013-03-20 14:06:07

您可以发布一些数据和您的预期结果吗？ – Jeff 2013-03-20 17:57:49

使用cKDTree这种情况下看起来像：

from scipy.spatial import cKDTree 

obs2 = array with shape (2, m) 
obs1 = array with shape (2, n) 

kdt = cKDTree(obs2.T) 
dist, indices = kdt.query(obs1.T)

其中indices将包含列索引中obs2对应于每个观察obs1。请注意，我必须转置obs1和obs2。

来源

2014-10-17 12:51:26

两个阵列的高效匹配（如何使用KDTree）

回答

相关问题