matlab中的k-means是根据距离函数的内存不足？

Question

我在一个大而稀疏的矩阵〜(1000000x1000)上使用k-means和matlab.现在这里是问题 - 使用余弦相似度作为距离函数我得到"内存不足.在几分钟内键入HELP MEMORY for your options"msg.但是,如果我使用欧氏距离,它会完美运行(相同的矩阵).

这有点奇怪,因为距离是成对计算的,并且每个距离计算不应该需要多于一个小的常数存储器.

当在较小的矩阵(1000x1000,尽管不稀疏)上使用k-means时,余弦效果很好.

技术细节:机器是64位,8GB RAM.如果你想尝试:矩阵可以在这里找到(它在发送空间上,所以它可以使用几周).

该文件采用稀疏格式:[row]\t [column]\t [value] \n

matlab代码:

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

1. 关于内存使用量差异的任何想法btw.余弦和欧几里德的距离？

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

谢谢!

Answer 1

如果检查该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

请注意,我没有尝试将整个数据集中到完成.我在一台32GB的4GB机器上运行(由于架构限制,其中MATLAB只能访问3GB),所以请报告建议的更改是否真的对64位/ 8GB硬件产生影响;)