從2個向量中找出最匹配的成對點

我有2個列表，包含點的X，Y座標。列表1包含比列表2更多的點。從2個向量中找出最匹配的成對點

任務是以整體歐氏距離最小化的方式找到點對。

我有一個工作代碼，但我不知道這是否是最好的方法，我想知道我可以改進的結果（更好的算法找到最小值）或速度，因爲列表是每個約2000個元素。

樣本向量中的一輪實現以獲得具有相同距離的點。使用「rdist」功能，所有距離都以「距離」生成。比矩陣中的最小值用於鏈接2點（「dist_min」）。這2個點的所有距離現在由NA代替，循環繼續搜索下一個最小值，直到列表2的所有點都有列表1中的一個點。最後，我添加了一個可視化圖。

require(fields) 

set.seed(1) 
x1y1.data <- matrix(round(runif(200*2),2), ncol = 2) # generate 1st set of points 
x2y2.data <- matrix(round(runif(100*2),2), ncol = 2) # generate 2nd set of points 

distances <- rdist(x1y1.data, x2y2.data) 
dist_min <- matrix(data=NA,nrow=ncol(distances),ncol=7) # prepare resulting vector with 7 columns 

for(i in 1:ncol(distances)) 
{ 
    inds <- which(distances == min(distances,na.rm = TRUE), arr.ind=TRUE) 

    dist_min[i,1] <- inds[1,1]    # row of point(use 1st element of inds if points have same distance) 
    dist_min[i,2] <- inds[1,2]    # column of point (use 1st element of inds if points have same distance) 
    dist_min[i,3] <- distances[inds[1,1],inds[1,2]] # distance of point 
    dist_min[i,4] <- x1y1.data[inds[1,1],1]  # X1 ccordinate of 1st point 
    dist_min[i,5] <- x1y1.data[inds[1,1],2]  # Y1 coordinate of 1st point 
    dist_min[i,6] <- x2y2.data[inds[1,2],1]  # X2 coordinate of 2nd point 
    dist_min[i,7] <- x2y2.data[inds[1,2],2]  # Y2 coordinate of 2nd point 

    distances[inds[1,1],] <- NA # remove row (fill with NA), where minimum was found 
    distances[,inds[1,2]] <- NA # remove column (fill with NA), where minimum was found 
} 

# plot 1st set of points 
# print mean distance as measure for optimization 
plot(x1y1.data,col="blue",main="mean of min_distances",sub=mean(dist_min[,3],na.rm=TRUE))  
points(x2y2.data,col="red")       # plot 2nd set of points 
segments(dist_min[,4],dist_min[,5],dist_min[,6],dist_min[,7]) # connect pairwise according found minimal distance

output with min distance

來源

2012-12-19 user1716533

查找暗物質kaggle競爭問題，也許？ –

僞代碼很容易寫：'for（i in 1st.set.points）{for（j in j 2nd.set.points）{calculate：sqrt（（x1st.set.ponint-x2nd.set.points）^2 +（y1st.set.ponint-y2nd.set.points）^ 2），保存每一個結果值，然後調用min（）函數來確定哪一個具有最低值}} –

您好java_xof，我認爲這就是我的方式做了。？ '距離< - rdist（x1y1.data，x2y2.data）'傳遞所有距離的矩陣和'which（距離== min（距離，na.rm = TRUE），arr.ind = TRUE）'搜索分鐘矩陣。但是，如果有相同的分鐘對。距離我不知道是否選擇哪一對。 – user1716533

這是被稱爲assignment problem組合優化的一個根本問題。一種方法來解決分配問題是在R包線索實施了Hungarian algorithm：

require(clue) 
sol <- solve_LSAP(t(distances))

我們可以驗證它的性能優於天真的解決方案：

mean(dist_min[,3]) 
# [1] 0.05696033 
mean(sqrt(
    (x2y2.data[,1] - x1y1.data[sol, 1])^2 + 
    (x2y2.data[,2] - x1y1.data[sol, 2])^2)) 
#[1] 0.05194625

，我們可以構造一個類似的陰謀到那個在你的問題：

plot(x1y1.data,col="blue")  
points(x2y2.data,col="red") 
segments(x2y2.data[,1], x2y2.data[,2], x1y1.data[sol, 1], x1y1.data[sol, 2])

enter image description here

來源

2012-12-20 00:47:31 orizon

感謝orizon，該圖顯示了對「簡單」算法的重大改進，因爲許多長線可以被消除。 – user1716533

@ user1716533這是一個很好的問題。看到改進的地方很有意思。在採用所有優點時，在簡單方法中的大部分長距離都會在算法中分配得非常晚。我們可以通過改變點並運行算法幾次來改進簡單的方法 - 但是當現有的有效的最優算法的實現沒有多少理由。 – orizon

從2個向量中找出最匹配的成對點

回答

相關問題