2

サイズ4000x300のk-means（4000セントロイド、それぞれ300の機能）を使用してコードブックを作成しました。次に、コードブックを使用して、入力ベクトルにラベルを付けます（後でビニングするため）。入力ベクトルのサイズはNx300です。ここで、Nは私が受け取る入力インスタンスの総数です。

ラベルを計算するために、各入力ベクトルに最も近い重心を計算します。そのために、各入力ベクトルをすべての重心と比較し、最小距離の重心を選択します。その場合、ラベルはその重心の単なるインデックスになります。

私の現在のMatlabコードは次のようになります。

function labels = assign_labels(centroids, X)
labels = zeros(size(X, 1), 1);

% for each X, calculate the distance from each centroid
for i = 1:size(X, 1)
    % distance of X_i from all j centroids is: sum((X_i - centroid_j)^2)
    % note: we leave off the sqrt as an optimization
    distances = sum(bsxfun(@minus, centroids, X(i, :)) .^ 2, 2);
    [value, label] = min(distances);
    labels(i) = label;
end

ただし、このコードは（私の目的では）まだかなり遅いので、コードをさらに最適化する方法があるのではないかと期待していました。

明らかな問題の1つは、Matlabでの良好なパフォーマンスの悩みの種であるforループがあることです。私はそれを取り除く方法を考え出そうとしていましたが、運がありませんでした（bsxfunと組み合わせてarrayfunを使用することを検討しましたが、それが機能するようにはなりませんでした）。あるいは、誰かがこれをスピードアップする他の方法を知っているなら、私はそれを大いに感謝します。

アップデート

検索を行った後、Matlabを使用した優れたソリューションが見つからなかったため、Pythonのscikits.learnパッケージで「euclidean_distance」（短縮）に使用されているものを確認することにしました。

 XX = sum(X * X, axis=1)[:, newaxis]
 YY = Y.copy()
 YY **= 2
 YY = sum(YY, axis=1)[newaxis, :]
 distances = XX + YY
 distances -= 2 * dot(X, Y.T)
 distances = maximum(distances, 0)

これは、ユークリッド距離の二項形式（（xy）^ 2-> x ^ 2 + y ^ 2- 2xy）を使用します。これは、私が読んだものから、通常はより高速に実行されます。私の完全にテストされていないMatlabの翻訳は次のとおりです。

 XX = sum(data .* data, 2);
 YY = sum(center .^ 2, 2);
 [val, ~] = max(XX + YY - 2*data*center');
4

4 に答える 4

4

次の関数を使用して、距離を計算します。桁違いにスピードアップするはずです

2つの行列AとBには、次元としての列と各点としての行があります。Aは重心のマトリックスです。Bはデータポイントのマトリックスです。

function D=getSim(A,B)
    Qa=repmat(dot(A,A,2),1,size(B,1));
    Qb=repmat(dot(B,B,2),1,size(A,1));
    D=Qa+Qb'-2*A*B';
于 2011-04-24T11:03:16.487 に答える
1

真のマトリックス実装の場合、次の方針に沿って何かを試すことを検討してください。

  P2 = kron(centroids, ones(size(X,1),1));
  Q2 = kron(ones(size(centroids,1),1), X);

  distances = reshape(sum((Q2-P2).^2,2), size(X,1), size(centroids,1));

注 これは、データが[x1 y1 ...; x2 y2 ...; ...]

于 2011-04-22T14:51:40.200 に答える
1

セルに変換して以下を使用することにより、ベクトル化できますcellfun。

[nRows,nCols]=size(X);
XCell=num2cell(X,2);
dist=reshape(cell2mat(cellfun(@(x)(sum(bsxfun(@minus,centroids,x).^2,2)),XCell,'UniformOutput',false)),nRows,nRows);
[~,labels]=min(dist);

説明：

  • の各行をX2行目の独自のセルに割り当てます
  • このピースはあなたの行@(x)(sum(bsxfun(@minus,centroids,x).^2,2))と同じ無名関数であり、を使用して、の各行に適用します。distances=...cell2matX
  • ラベルは、各列に沿った最小行のインデックスになります。
于 2011-04-20T23:16:22.630 に答える
1

ブルートフォースよりも最近傍探索に効率的なアルゴリズムを使用できます。最も一般的なアプローチはKd-Treeです。O（n）ブルートフォースの複雑さではなく、O（log（n））平均クエリ時間。Kd-TreesのMaltab実装については、こちらをご覧ください。

于 2013-11-07T13:28:45.647 に答える