如何在向量中找到离另一个向量最近的值？

Question

我有两个大小相等的向量，例如：

A=[2.29 2.56 2.77 2.90 2.05] and
B=[2.34 2.62 2.67 2.44 2.52].

我想要找到两个同样大小的向量A和B中最接近（几乎相等）的值，即在A中的所有元素中，哪个值最接近B中的任何一个元素？解决方案应该能够扩展到任意数量（相同大小）的向量。也就是说，能够在一组同样大小的向量A、B和C中找到最接近的值。得到的两个结果可以来自任意两个向量中的元素。

为了清晰起见，我不是要在单个向量中找到最接近的值。以上例子的答案是值2.56和2.52。

- erbal

Answer 1

这适用于 通用数量 的向量，其长度可能 不同：

vectors = {[2.29 2.56 2.77 2.90 2.05] [2.34 2.62 2.67 2.44 2.52] [1 2 3 4]}; 
    % Cell array of data vectors; 3 in this example
s = cellfun(@numel, vectors); % Get vector lengths
v = [vectors{:}]; % Concatenate all vectors into a vector
D = abs(bsxfun(@minus, v, v.')); % Compute distances. This gives a matrix.
    % Distances within the same vector will have to be discarded. This will be
    % done by replacing those values with NaN, in blocks
bb = arrayfun(@(x) NaN(x), s, 'uniformoutput', false); % Cell array of blocks
B = blkdiag(bb{:}); % NaN mask with those blocks
[~, ind] = min(D(:) + B(:)); % Add that mask. Get arg min in linear index
[ii, jj] = ind2sub(size(D), ind); % Convert to row and column indices
result = v([ii jj]); % Index into concatenated vector

- Luis Mendo

---

哇，好棒的解决方案！ - edwinksl

我借用了你的 blkdiag 想法 ;) +1, - Robert Seifert

@thewaywewalk 很好！回答也很棒！ - Luis Mendo

@Divakar 啊，那不是瞬间的。是的，这很有道理。让我想起了基于这个想法的这个PPCG挑战。 - Luis Mendo

@Divakar 你是指这个东西吗？还是其他什么？ - Luis Mendo

Answer 2

使用bsxfun作为两个向量的起点：

%// data
A = [2.29 2.56 2.77 2.90 2.05]
B = [2.34 2.62 2.67 2.44 2.52]

%// distance matrix 
dist = abs(bsxfun(@minus,A(:),B(:).'));

%// find row and col indices of minimum
[~,idx] = min(dist(:))
[ii,jj] = ind2sub( [numel(A), numel(B)], idx)

%// output 
a = A(ii)
b = B(jj)

现在你可以将它放入循环中等。顺便说一下：

dist = abs(bsxfun(@minus,A(:),B(:).'));

等价于更明显的：

dist = pdist2( A(:), B(:) )

但我更倾向于采用第一种解决方案来避免额外的开销。

---

最后，针对多个向量的完全矢量化方法：

%// data
data{1} = [2.29 2.56 2.77 2.90 2.05];
data{2} = [2.34 2.62 2.67 2.44 2.52];
data{3} = [2.34 2.62 2.67 2.44 2.52].*2;
data{4} = [2.34 2.62 2.67 2.44 2.52].*4;
%// length of each vector
N = 5;

%// create Filter for distance matrix
nans(1:numel(data)) = {NaN(N)};
mask = blkdiag(nans{:}) + 1; 

%// create new input for bsxfun
X = [data{:}];

%// filtered distance matrix 
dist = mask.*abs(bsxfun(@minus,X(:),X(:).'));

%// find row and col indices of minimum
[~,idx] = min(dist(:))
[ii,jj] = ind2sub( size(dist), idx)

%// output 
a = X(ii)
b = X(jj)

- Robert Seifert

---

代码对于两个向量运行良好。如何将其扩展到三个或更多向量？ - erbal

@erbal 所有向量长度都相同吗？ - Robert Seifert

@erbal 这是一个相对较新的函数，在这里搜索一下，你会找到一个替代品。 - Robert Seifert

@erbal，我通过使用blkdiag（灵感来自Luis Mendo）改进了我的解决方案，现在不再需要使用repelem函数了，并且占用的内存也更少 ;) - Robert Seifert

现在正在尝试更新代码，因为找不到repelem的位置。 - erbal

Answer 3

就像一段很长的注释一样，如果您可以访问统计和机器学习工具箱，那么您可以使用K-最近邻函数，它们具有一些优点，例如：

1. 处理不同长度的数组，例如当size(A)= [M, 1] 和 size(B)=[N, 1]时

2. 处理二维数组，例如当size(A)=[M, d] 和 size(B)=[N, d]时

3. 处理不同的距离类型，例如：欧几里得距离、曼哈顿距离、切比雪夫距离等等，甚至可以使用自定义距离。

4. 对于某些特殊情况，使用KDTree算法可以获得极佳的性能。

虽然在您的情况下，“Luis Mendo” 的答案似乎非常好，但它并不能像工具箱中的K-最近邻函数一样可扩展。

更新：示例代码

% A and B could have any Dimension, just same number of columns (signal Dimension)
A = rand(1000,4);
B = rand(500,4);

% Use any distance you like, some of them are not supported for KDTreeSearcher,
% and you should use ExhaustiveSearcher
myKnnModel= KDTreeSearcher(A, 'Distance', 'minkowski');

% you can ask for many (K) Nearest Neighbors and you always have access to it for later uses
[Idx, D] = knnsearch(myKnnModel, B, 'K',2);

% and this is answer to your special case
[~, idxA] = min(D(:, 1))
idxB = Idx(idxA)

- eulerleibniz

---

这看起来很有前途。也许加上两个或三个向量的示例，使其成为一个真正的答案？ - Luis Mendo

@LuisMendo。我已经更新了我的答案，并提供了一段示例代码，请检查并告诉我您的想法。 - eulerleibniz

这是一个非常好的概括。我认为你交换了idxB和idxA：应该是[~, idxB] = min(D(:, 1)); idxA = Idx(idxB);，对吗？也许还要补充一下，所需的最接近向量是A(idxA,:)和B(idxB,:)。 - Luis Mendo

@LuisMendo。我目前没有访问MATLAB来检查代码。只需检查D的大小，如果size(D, 1) == size(B, 1)，那么你是正确的。 - eulerleibniz

@LuisMendo：我无法解读这段代码。如果您有Matlab访问权限，请重新发布/更正此代码以解决我的问题。 - erbal

只需将最后两行替换为我上面的评论中的内容（如果我是正确的） - Luis Mendo