0

我已经像这样在 Matlab 中实现了余弦相似度。事实上，我有一个 50×50 的二维矩阵。要获得余弦，我应该逐行比较项目。

for j = 1:50
    x = dat(j,:);
    for i = j+1:50
        y = dat(i,:);
        c = dot(x,y);
        sim = c/(norm(x,2)*norm(y,2));
    end
end

这个对吗？问题是：wath 是这种状态下的复杂度还是 O(n)？

4

2 回答 2

2

只是关于使用向量化和矩阵运算（在 MATLAB 中进行了优化）有效实现同一事物的说明。对于大型矩阵，这可以节省大量时间： 

dat = randn(50, 50);

OP（双换）实现：

sim = zeros(size(dat));
nRow = size(dat,1);
for j = 1:nRow
    x = dat(j, :);
    for i = j+1:nRow
        y = dat(i, :);
        c = dot(x, y);
        sim(j, i) = c/(norm(x,2)*norm(y,2));
    end
end

向量化实现：

normDat = sqrt(sum(dat.^2, 2));           % L2 norm of each row 
datNorm = bsxfun(@rdivide, dat, normDat); % normalize each row 
dotProd = datNorm*datNorm';               % dot-product vectorized (redundant!) 
sim2 = triu(dotProd, 1);                  % keep unique upper triangular part

1000 x 1000 矩阵的比较：（MATLAB 2013a、x64、Intel Core i7 960 @ 3.20GHz）

Elapsed time is 34.103095 seconds.
Elapsed time is 0.075208 seconds.
sum(sum(sim-sim2))
ans =
    -1.224314766369880e-14
于 2013-08-14T19:26:37.680 回答
1

最好以 49 结尾。也许您还应该为 sim 添加索引？

for j = 1:49
  x = dat(j,:);
  for i = j+1:50
      y = dat(i,:);
      c = dot(x,y);
      sim(j) = c/(norm(x,2)*norm(y,2));
  end
end

复杂度应该大致像 o(n^2)，不是吗？也许你应该看看相关函数......我没有得到你想要写的确切内容，但看起来你想做类似的事情。Matlab中有内置的相关函数。

于 2013-08-14T10:10:01.213 回答