Подтвердить что ты не робот

Как найти три ближайших (ближайших) значения в векторе?

Я хотел бы узнать три ближайших числа в векторе. Что-то вроде

v = c(10,23,25,26,38,50)
c = findClosest(v,3)
c
23 25 26

Я пытался с sort(colSums(as.matrix(dist(x))))[1:3], и это вроде работает, но он выбирает три числа с минимальным общим расстоянием, а не три ближайших числа.

Для Matlab уже есть ответ, но я не знаю, как перевести его на R:

%finds the index with the minimal difference in A
minDiffInd = find(abs(diff(A))==min(abs(diff(A))));
%extract this index, and it neighbor index from A
val1 = A(minDiffInd);
val2 = A(minDiffInd+1);

Как найти два ближайших (ближайших) значения в векторе в MATLAB?

4b9b3361

Ответ 1

Я предполагаю, что для ближайших значений n важна только разница между v[i] - v[i - (n-1)]. То есть найти минимум diff(x, lag = n - 1L).

findClosest <- function(x, n) {
  x <- sort(x)
  x[seq.int(which.min(diff(x, lag = n - 1L)), length.out = n)]
}

findClosest(v, 3L)

[1] 23 25 26

Ответ 2

Определим "ближайшие числа" по "числам с минимальной суммой расстояний L1". Вы можете достичь того, чего хотите, с помощью комбинации diff и оконной суммы.

Вы могли бы написать гораздо более короткую функцию, но я написал ее шаг за шагом, чтобы было легче следовать.

v <- c(10,23,25,26,38,50)

#' Find the n nearest numbers in a vector
#'
#' @param v Numeric vector
#' @param n Number of nearest numbers to extract
#'
#' @details "Nearest numbers" defined as the numbers which minimise the
#'   within-group sum of L1 distances.
#'   
findClosest <- function(v, n) {
  # Sort and remove NA
  v <- sort(v, na.last = NA)

  # Compute L1 distances between closest points. We know each point is next to
  # its closest neighbour since we sorted.
  delta <- diff(v)

  # Compute sum of L1 distances on a rolling window with n - 1 elements
  # Why n-1 ? Because we are looking at deltas and 2 deltas ~ 3 elements.
  withingroup_distances <- zoo::rollsum(delta, k = n - 1)

  # Now it simply finding the group with minimum within-group sum
  # And working out the elements
  group_index <- which.min(withingroup_distances)
  element_indices <- group_index + 0:(n-1)

  v[element_indices]
}

findClosest(v, 2)
# 25 26
findClosest(v, 3)
# 23 25 26

Ответ 3

Базовая опция R, идея состоит в том, что мы сначала sort вектор и вычитаем каждый i -й элемент с элементом i + n - 1 в отсортированном векторе и выбираем группу с минимальной разницей.

closest_n_vectors <- function(v, n) {
   v1 <- sort(v)
   inds <- which.min(sapply(head(seq_along(v1), -(n - 1)), function(x) 
                     v1[x + n -1] - v1[x]))
   v1[inds: (inds + n - 1)]
}

closest_n_vectors(v, 3)
#[1] 23 25 26

closest_n_vectors(c(2, 10, 1, 20, 4, 5, 23), 2)
#[1] 1 2

closest_n_vectors(c(19, 23, 45, 67, 89, 65, 1), 2)
#[1] 65 67

closest_n_vectors(c(19, 23, 45, 67, 89, 65, 1), 3)
#[1]  1 19 23

В случае связи это вернет числа с наименьшим значением, так как мы используем which.min.


ОРИЕНТИРЫ

Так как у нас есть довольно много ответов, стоит проверить все решения до сих пор

set.seed(1234)
x <- sample(100000000, 100000)

identical(findClosest_antoine(x, 3), findClosest_Sotos(x, 3), 
          closest_n_vectors_Ronak(x, 3), findClosest_Cole(x, 3))
#[1] TRUE

microbenchmark::microbenchmark(
    antoine = findClosest_antoine(x, 3),
    Sotos = findClosest_Sotos(x, 3), 
    Ronak  = closest_n_vectors_Ronak(x, 3),
    Cole = findClosest_Cole(x, 3),
    times = 10
)



#Unit: milliseconds
#  expr      min       lq     mean   median       uq      max neval cld
#antoine  148.751  159.071  163.298  162.581  167.365  181.314    10  b 
#  Sotos 1086.098 1349.762 1372.232 1398.211 1453.217 1553.945    10   c
#  Ronak   54.248   56.870   78.886   83.129   94.748  100.299    10 a  
#   Cole    4.958    5.042    6.202    6.047    7.386    7.915    10 a  

Ответ 4

Идея состоит в том, чтобы использовать библиотеку zoo для выполнения операции прокрутки, т.е.

library(zoo)
m1 <- rollapply(v, 3, by = 1, function(i)c(sum(diff(i)), c(i)))
m1[which.min(m1[, 1]),][-1]
#[1] 23 25 26

Или превратить это в функцию,

findClosest <- function(vec, n) {
    require(zoo)
    vec1 <- sort(vec)
    m1 <- rollapply(vec1, n, by = 1, function(i) c(sum(diff(i)), c(i)))
    return(m1[which.min(m1[, 1]),][-1])
}

findClosest(v, 3)
#[1] 23 25 26