在R中有效計算一點和一組點之間的所有距離

我有兩組分，data和centers，大小n的第一個和大小K的第二（例如，n = 3823和K = 10），並在第一組中的每個i，我需要找到j在第二個與最小距離。

我的想法很簡單：每個i，讓dist[j]是i和j之間的距離，我只需要使用which.min(dist)找到我所期待的。

各點是的64雙打陣列，所以

> dim(data) 
[1] 3823 64 
> dim(centers) 
[1] 10 64

我與

for (i in 1:n) { 
    for (j in 1:K) { 
    d[j] <- sqrt(sum((centers[j,] - data[i,])^2)) 
    } 
    S[i] <- which.min(d) 
}

這是非常慢的嘗試（與n = 200，它需要比40秒更多！）。我寫的最快的解決方法是

distance <- function(point, group) { 
    return(dist(t(array(c(point, t(group)), dim=c(ncol(group), 1+nrow(group)))))[1:nrow(group)]) 
} 

for (i in 1:n) { 
    d <- distance(data[i,], centers) 
    which.min(d) 
}

即使做了很多，我不使用（因爲dist(m)計算的m所有行之間的距離）計算的，它是一個比另一個多路快（任何人都可以解釋爲什麼？），但它不足以滿足我需要，因爲它不會只使用一次。而且，distance代碼非常難看。我試圖用

distance <- function(point, group) { 
    return (dist(rbind(point,group))[1:nrow(group)]) 
}

但這似乎是兩次慢。我也嘗試每對使用dist，但它也比較慢。

我不知道現在該做什麼。看來我正在做一些非常錯誤的事情。任何想法如何更有效地做到這一點？

ps：我需要這個來實現k-means手工（我需要這樣做，它是一個任務的一部分）。我相信我只需要歐幾里德距離，但我還不確定，所以我寧願有一些代碼可以很容易地替換距離計算。 stats::kmeans在不到一秒內完成所有計算。

來源

2010-06-12 dbarbosa

人民輪在這裏種-A-鴕鳥政策樣做任務......因此要儘量集中在一個特定的問題。 – aL3xa 2010-06-12 19:38:45

您可以將其壓縮爲矩陣運算，而不是遍歷數據點，這意味着您只需遍歷K即可。

# Generate some fake data. 
n <- 3823 
K <- 10 
d <- 64 
x <- matrix(rnorm(n * d), ncol = n) 
centers <- matrix(rnorm(K * d), ncol = K) 

system.time(
    dists <- apply(centers, 2, function(center) { 
    colSums((x - center)^2) 
}) 
)

奔跑在：

utilisateur  système  écoulé 
     0.100  0.008  0.108

我的筆記本電腦。

來源

2010-06-12 21:35:15

+1我的方式來計算矩陣矩陣。這是自動複製向量從矩陣中添加或減去的好技巧。 – Marek 2010-06-12 23:00:44

我正在嘗試使用您的解決方案，但您的矩陣已轉置。有沒有像你用列一樣去減行的方法？ – dbarbosa 2010-06-12 23:12:45

我嘗試使用apply進行減法運算，但並不像解決方案那麼快。我現在正在轉換矩陣並使用您的代碼，它非常快！非常感謝！！！另外，感謝您用一個小例子和system.time的使用來給出完整的答案。 Merci beaucoup :) – dbarbosa 2010-06-12 23:35:35

您可能想看看apply函數。

例如，這個代碼

for (j in 1:K) 
    { 
    d[j] <- sqrt(sum((centers[j,] - data[i,])^2)) 
    }

可以很容易地像

dt <- data[i,] 
d <- apply(centers, 1, function(x){ sqrt(sum(x-dt)^2)})

來取代你一定可以更加優化，但你明白了吧，我希望

來源

2010-06-12 18:52:06 nico

謝謝......它比我寫的第一個代碼更快，但使用'distance'甚至不會接近奇怪的代碼。 – dbarbosa 2010-06-12 19:19:38

@dbarbosa：好的，顯然'stats :: kmeans'包使用的編譯代碼明顯更快。只需鍵入'kmeans'，你就會看到它的源代碼。 :) – nico 2010-06-12 20:58:06

dist工程快因爲它不是矢量化的，而是調用內部的C函數。
您在循環中的代碼可以通過多種方式進行矢量化。

例如計算data之間的距離centers你可以使用outer：

這給你n x K矩陣距離。而且應該比循環更快。

然後，您可以使用max.col在每一行中查找最大值（請參閱幫助，當有很多最大值時，會有一些細微差別）。 X必須否定因爲我們搜索最小。

CL <- max.col(-X)

爲了提高R的效率，您應儘可能進行矢量化。在許多情況下，循環可以用矢量化替代替代。檢查幫助rowSums（其中描述rowMeans,colSums,rowSums），pmax,cumsum。您可以搜索SO，例如 https://stackoverflow.com/search?q=[r]+avoid+loop（複製&粘貼此鏈接，我不知道如何使它可點擊）的一些例子。

來源

2010-06-12 21:22:34 Marek

嗨，我想使用你的代碼，但它不工作。我試着用@Jonathan Chang編寫的相同代碼來使用它，並添加：'system.time（outer（seq_len（n），seq_len（K），function（i，j）sqrt（rowSums（（x [，i] - （dj，dY）：dims [product 38230]與長度不匹配的錯誤對象[64]' 您是否看到有什麼問題？ – dbarbosa 2010-06-12 22:46:19

其實我並不理解'outer'（我認爲它是爲每一對調用一次函數）。現在我明白了，謝謝，它可以是有用的！另外，謝謝你告訴'max.col'。 – dbarbosa 2010-06-12 23:53:48

我的解決辦法：

# data is a matrix where each row is a point 
# point is a vector of values 
euc.dist <- function(data, point) { 
    apply(data, 1, function (row) sqrt(sum((point - row)^2))) 
}

，您可以嘗試，如：

x <- matrix(rnorm(25), ncol=5) 
euc.dist(x, x[1,])

來源

2016-09-23 17:16:37

rdist（）是由{字段}包A R函數，其能夠兩組之間計算距離快速點矩陣格式。

https://www.image.ucar.edu/~nychka/Fields/Help/rdist.html

用法：

library(fields) 
#generating fake data 
n <- 5 
m <- 10 
d <- 3 

x <- matrix(rnorm(n * d), ncol = d) 
y <- matrix(rnorm(m * d), ncol = d) 

rdist(x, y) 
      [,1]  [,2]  [,3]  [,4]  [,5] 
[1,] 1.512383 3.053084 3.1420322 4.942360 3.345619 
[2,] 3.531150 4.593120 1.9895867 4.212358 2.868283 
[3,] 1.925701 2.217248 2.4232672 4.529040 2.243467 
[4,] 2.751179 2.260113 2.2469334 3.674180 1.701388 
[5,] 3.303224 3.888610 0.5091929 4.563767 1.661411 
[6,] 3.188290 3.304657 3.6668867 3.599771 3.453358 
[7,] 2.891969 2.823296 1.6926825 4.845681 1.544732 
[8,] 2.987394 1.553104 2.8849988 4.683407 2.000689 
[9,] 3.199353 2.822421 1.5221291 4.414465 1.078257 
[10,] 2.492993 2.994359 3.3573190 6.498129 3.337441

來源

2016-10-20 09:30:25 Deuterium

在R中有效計算一點和一組點之間的所有距離

回答

相關問題