查找最近值数组的向量化函数

Question

我仍在全神贯注于矢量化，我在尝试解决我创建的以下函数时遇到了困难...

for i = 1:size(X, 1)
  min_n = inf;
  for j=1:K
    val = X(i,:)' - centroids(j,:)';
    diff = val'*val;
    if (diff < min_n)
      idx(i) = j;
      min_n = diff;
    end
  end
end

X 是 (x,y) 坐标的数组...

2    5
5    6
...
...

本例中的

centroids 限制为 3 行。也是(x,y)格式，如上图

对于 X 中的每一对，我正在计算最接近的 centroids 对。然后我将质心的索引存储在 idx.

中

所以idx(i) = j意味着我将质心的索引j存储在索引i处，其中i对应于X的索引.这意味着最接近 X(i, :) 对的质心位于 idx(i).

我可以通过向量化来简化这个吗？我努力对内部循环进行矢量化。

Answer 1

可以使用 pdist2 - 两个矩阵的行之间的成对距离：

% random data
X = rand(500,2);
centroids = rand(3,2);
% pairwise distances
D = pdist2(X,centroids);
% closest centroid index for each X coordinates
[~,idx] = min(D,[],2)
% plot
scatter(centroids(:,1),centroids(:,2),300,(1:size(centroids,1))','filled');
hold on;
scatter(X(:,1),X(:,2),30,idx);
legend('Centroids','data');

Answer 2

这里有三个选项。但是请注意，与双循环相比，矢量化的缺点是它一次存储所有差异运算结果，这意味着如果您的矩阵有很多行，您可能运行内存不足。另一方面，矢量化方法可能要快得多。

选项 1

如果您有权访问 Statistics and Machine Learning Toolbox, you can use the function pdist2 以获取两个矩阵的行之间的所有成对距离。然后，min 函数为您提供结果中每一列的最小值。它的第一个返回值是最小值，第二个是索引，这是 idx:

所需要的

diff = pdist2(centroids,X);
[~,idx] = min(diff);

选项 2

如果您无法访问工具箱，可以使用 bsxfun。这将使您可以计算两个矩阵之间的差分运算，即使它们的维度不一致。您需要做的就是使用 shiftdim 将 X' 重塑为大小 [1,size(X,2),size(X,1)]，然后 reshapedX 和 centroids 与其尺寸兼容（请参阅bsxfun) 的文档。这使您可以获取它们的值之间的差异。结果是一个三维数组，您需要沿第二个维度求和以获得行之间差异的范数。此时您可以按照选项 1 进行操作。

reshapedX = shiftdim(X',-1);
diff = bsxfun(@minus,centroids,reshapedX);
diff = squeeze(sum(diff.^2,2));
[~,idx] = min(diff);

注意：从Matlab 2016b版开始，the bsxfun is used implicitly不再需要调用。所以带有 bsxfun 的行可以用更简单的行 diff = centroids-reshapedX.

代替

选项 3

使用函数 dsearchn，它完全满足您的需求：

idx = dsearchn(centroids,X);

查找最近值数组的向量化函数

Vectorize function that finds an array of nearest values

math

matlab

vector

vectorization

octave

选项 1

选项 2

选项 3