4

大きくてスパースな行列〜（1000000x1000）でmatlabを使用してk-meansを使用しています。ここに問題があります。距離関数としてコサイン類似度を使用すると、数分以内に「メモリ不足です。オプションのHELPMEMORYと入力してください」というメッセージが表示されます。ただし、ユークリッド距離を使用すると、完全に実行されます（同じ行列）。

距離はペアごとに計算され、距離の計算ごとに小さな定数メモリ以上を必要としないため、これは少し奇妙です。

小さい行列（スパースではありませんが、1000x1000）でk-meansを使用する場合、正弦はうまく機能します。

技術的な詳細：マシンは64ビットで8GBのRAMを搭載しています。試してみたい場合：マトリックスはここにあります（sendspaceにあるので、数週間利用できます）。

ファイルはスパース形式です：[行] \t[列]\t[値]\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と、余弦距離のコードは、メモリ不足エラーをスローする可能性のある2つのクリティカルセクションに要約されます。まず、関係する主な変数を紹介します。

  • 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インデックスを使用して操作をベクトル化し、データが持つ列の数だけノルムベクトルを繰り返してから、要素ごとの除算を実行しようとします。このようなアプローチの問題を理解するには、変数のサイズを確認してください。

>> 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）

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

基本的に、すべてのクラスター重心（データベクトル全体に対して一度に1つの重心）を使用して、各データインスタンスの内積を計算します。繰り返しになりますが、これが問題を引き起こす可能性がある場合は、ベクトル化された製品を次のようなステップバイステップのループに展開するだけです。

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 に答える