3

目前我正在使用pdistMatlab 中的函数来计算三维笛卡尔系统中各个点之间的欧几里得距离。我这样做是因为我想知道哪个点与所有其他点（中心点）的平均距离最小。的语法pdist如下所示：

% calculate distances between all points
distances = pdist(m);

但是因为 pdist 返回距离的一​​维数组，所以没有简单的方法可以（直接）确定哪个点的平均距离最小。这就是我使用squareform然后计算最小平均距离的原因，如下所示：

% convert found distances to matrix of distances
distanceMatrix = squareform(distances);

% find index of point with smallest average distance
[~,j] = min(mean(distanceMatrix,2));

对每列的距离进行平均，变量j是具有最小平均距离的列（和点）的索引。

这行得通，但是 squareform 需要很多时间（这段代码重复了数千次），所以我正在寻找一种优化它的方法。有谁知道一种更快的方法来从结果中推断出平均距离最小的点pdist？

4

4 回答 4

3

我认为对于您的任务，使用 SQUAREFORM 函数是从矢量化角度来看的最佳方式。如果您通过以下方式查看此功能的内容

edit squareform

你会看到它执行了很多当然需要时间的检查。由于您知道您对 squareform 的输入并且可以确定它会起作用，因此您可以仅使用 squareform 的核心来创建您的自定义函数。

[r, c] = size(m);
distanceMatrix = zeros(r);
distanceMatrix(tril(true(r),-1)) = distances;
distanceMatrix = distanceMatrix + distanceMatrix';

然后运行与查找 medioid 相同的代码。

于 2012-03-12T05:41:32.510 回答
1

这是一个不需要调用 squareform 的实现：

N1 = 10;
dim = 5;

% generate points
X = randn(N1, dim);

% find mean distance
for iter=N1:-1:1
    d_mean(iter) = mean(pdist2(X(iter,:),X([1:(iter-1) (iter+1):end],:),'euclidean'));
    % D(iter,:) = pdist2(X(iter,:),X([1:(iter-1) (iter+1):end],:),'euclidean');
end

[val ind] = min(d_mean);

但是在不了解您的问题的情况下，我不知道它是否会更快。

如果这是您程序性能的关键，您可能需要考虑其他加速选项，例如 mex。

祝你好运。

于 2012-03-12T00:19:41.120 回答
1

当 pdist 计算观测值对之间的距离 (1,2,...,n) 时，距离按以下顺序排列：

(2,1), (3,1), ..., (m,1), (3,2), ..., (m,2), ..., (m,m–1))

为了证明这一点，请尝试以下操作：

> X = [.2 .1 .7 .5]';
> D = pdist(X)
.1  .5  .3   .6  .4  .2

在此示例中，X 存储 n=4 个观察值。结果 D 是观测值 (2,1)、(3,1)、(4,1)、(3,2)、(4,2)、(5,4) 之间的距离向量。这种排列对应于以下 n×n 矩阵的下三角部分的条目：

M=
 0 0 0 0
.1 0 0 0
.5 .6 0 0
.3 .4 .2 0

请注意，D( 1 )=M( 2,1 )、D( 2 )=( 3,1 ) 等等。因此，获得 M 中与 D(k) 对应的索引对的一种方法是计算 M 中 D(k) 的线性索引。这可以按如下方式完成：

% matrix size
n = 4;
% r(j) is the no. of elements in cols 1..j, belonging to the upper triangular part 
r = cumsum(1:n-1);       
% p(j) is the no. elements in cols 1..j, belonging to the lower triangular part 
p = cumsum(n-1:-1:1);
% The linear index of value D(k)
q = find(p >= k, 1);
% The subscript indices of value D(k)
[i j] = ind2sub([n n], k + r(q));

请注意，n、r 和 p 只需设置一次。从那时起，您可以使用最后两行找到任何给定 k 的索引。让我们检查一下：

for k = 1:6
   q = find(p >= k, 1);
   [i, j] = ind2sub([n n], k + r(q));
   fprintf('D(%d) is the distance between observations (%d %d)\n', k, i, j);
end

这是输出：
D(1) 是观测值之间的距离 (2 1)
D(2) 是观测值之间的距离 (3 1)
D(3) 是观测值之间的距离 (4 1)
D(4) 是距离观测值之间 (3 2)
D(5) 是观测值之间的距离 (4 2)
D(6) 是观测值之间的距离 (4 3)

于 2016-12-21T18:37:57.840 回答
0

无需使用squareform：

distances = pdist(m);
l=length(distances);
n=(1+sqrt(1+4*l))/2;
m=[];
for i=1:n
  idx=[1+i:n:length(distances)];
  m(i)=mean(distances(idx));
end

j=min(m);

我不确定，但也许这也可以向量化，但现在为时已晚。

于 2012-03-12T01:27:11.633 回答