兩個陣列的高效匹配（如何使用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）

回答

相關問題