Вычисление всех расстояний между одной точкой и группой точек эффективно в R
В первую очередь, я плохо знаком с 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 сделайте все вычисление меньше чем за одну секунду.
3 ответа
Вместо итерации по точкам данных вы можете просто сжать это до матричной операции, то есть вам нужно выполнить итерацию только по 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
на моем ноутбуке.
dist работает быстро, потому что не векторизуется и вызывает внутренние функции C.
Код в цикле можно векторизовать разными способами.
Например, для вычисления расстояния между данными и центрами вы можете использовать внешний :
diff_ij <- function(i,j) sqrt(rowSums((data[i,]-centers[j,])^2))
X <- outer(seq_len(n), seq_len(K), diff_ij)
Это дает матрицу nx K расстояний. И должно быть быстрее, чем цикл.
Затем вы можете использовать max.col , чтобы найти максимум в каждой строке (см. Справку, есть некоторые нюансы, когда максимумов много). X должен быть отрицательным, потому что мы ищем минимум.
CL <- max.col(-X)
Чтобы быть эффективными в R, вам следует по возможности векторизовать. Петли во многих случаях можно заменить векторизованными аналогами. Проверьте справку для rowSums (которые также описывают rowMeans , colSums , rowSums ), pmax , cumsum . Вы можете искать SO, например.
https://stackoverflow.com/search?q= [r] + escape + loop (скопируйте и вставьте эту ссылку, я не знаю, как сделать ее интерактивной) для некоторых примеров.
Возможно, вы захотите взглянуть на функции 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)})
Вы определенно можете оптимизировать его больше, но вы поняли суть, я надеюсь