4

我在一个大而稀疏的矩阵〜（1000000x1000）上使用k-means和matlab。现在这是问题所在 - 使用余弦相似度作为距离函数，我在几分钟内得到“内存不足。为您的选项键入 HELP MEMORY”消息。但是，如果我使用欧几里得距离，它会完美运行（相同的矩阵）。

这有点奇怪，因为距离是成对计算的，每次距离计算只需要一个小的常量内存。

在较小的矩阵（1000x1000，虽然不是那么稀疏）上使用 k-means 时，余弦效果很好。

技术细节：该机器为 64 位，配备 8GB RAM。如果你想尝试：矩阵可以在这里找到（它在 sendspace 上，所以它可以使用几周）。

文件为稀疏格式：[row]\t[column]\t[value]\n

matlab代码：

f=load(filename);
v=spconvert(f);
c=kmeans(v,9);
c=kmeans(v,9,'distance','cosine');

  1. 顺便说一句，关于内存使用差异的任何想法。余弦和欧几里得距离？

  2. 关于如何处理它并在大矩阵上实际使用余弦的任何想法？

谢谢！

4

1 回答 1

6

如果您检查该kmeans.m函数，则余弦距离的代码归结为两个可能引发内存不足错误的关键部分。首先让我介绍一下涉及的主要变量：

  • X：行是观察向量，列是维度（数据）
  • C：行是质心，列是维度（簇质心）

1)

第一段代码是将数据行规范化为单位长度（之前在@John的已删除答案中指出了这一点，尽管出于错误的原因）：

[n,p] = size(X);              %# in your case, X is a matrix of size 1000000x1000

Xnorm = sqrt(sum(X.^2, 2));   %# norm of each instance vector
X = X ./ Xnorm(:,ones(1,p));  %# normalize to unit length

上面尝试使用 ONE-indexing 对操作进行矢量化，以将范数向量重复数据所具有的列数，然后进行逐元素除法。只需检查变量大小以了解这种方法的问题：

>> whos X Xnorm
  Name             Size                 Bytes  Class     Attributes

  X          1017564x1000            83056640  double    sparse    
  Xnorm      1017564x1               12210776  double    sparse

因此Xnorm(:,ones(1,p))将尝试分配一个大小的临时矩阵，12210776*1000 bytes = 11.3722 GB这显然是导致内存不足错误的原因......

X（对于那些感兴趣的人，内部需要双稀疏矩阵12*nnz(X) + 4*size(X,2) bytes来存储，而完整的表示需要prod(size(X))*8 bytes. 在您的情况下，大约需要 80MB 和 11.5GB 的内存！）

这条线可以用不同的（可能更慢）的方式编写，避免了通常是矢量化缺点的巨大空间需求。只需遍历每一行并除以范数。更好的是，我们可以使用专门为这种情况设计的 BSXFUN 函数（避免使用 REPMAT 和索引技巧）：

X = bsxfun(@rdivide, X, Xnorm);

有趣的是，在 KMEANS 文件的其他地方有注释的代码部分，明确考虑了这个问题，因此选择使用较慢的 for 循环，但保证不会耗尽内存......

2)

第二个关键部分是实际计算距离的地方。感兴趣的代码如下：

n = size(X,1);
nclusts = size(C,1);

D = zeros(n,nclusts);
for i = 1:nclusts
    D(:,i) = max(1 - X*C(i,:)', 0);
end

基本上，它计算每个数据实例与每个集群质心（一次一个质心，针对整个数据向量）的内积。同样，如果这会导致问题，您可以简单地将矢量化产品展开到逐步循环中，例如：

for i = 1:nclusts
    for j = 1:n
        D(j,i) = max(1 - dot(X(j,:),C(i,:)), 0);
    end
end

所以你明白了；当您的矩阵非常大时，您必须小心会产生大量中间结果的操作，并在可能的情况下用在较小规模上操作的显式循环替换它们。

顺便说一句，使用欧几里德距离时您不会遇到同样的问题，因为它是用循环而不是单线矢量化解决方案编写的。这是计算距离函数的部分：

for i = 1:nclusts
    D(:,i) = (X(:,1) - C(i,1)).^2;
    for j = 2:p
        D(:,i) = D(:,i) + (X(:,j) - C(i,j)).^2;
    end
    % D(:,i) = sum((X - C(repmat(i,n,1),:)).^2, 2);    %# <--- commented code
end

尽管如此，我很惊讶 BSXFUN 再次没有被使用：

for i=1:nclusts
    D(:,i) = sum(bsxfun(@minus, X, C(i,:)).^2, 2);
end

请注意，在完成之前我没有尝试对整个数据进行聚类。我在 4GB 的 32 位机器上运行（其中 MATLAB 由于架构限制只能访问 3GB），所以请报告建议的更改是否真的对您的 64 位/8GB 硬件产生影响；）

于 2011-08-24T23:03:23.833 回答