是否有可能優化這個Matlab代碼來做矢量量化與質心從k-均值？

我已經創建了一個使用大小爲4000x300的k-means（4000個質心，每個具有300個特徵）的碼本。然後使用碼本標記一個輸入矢量（以便稍後進行分箱）。輸入向量的大小爲Nx300，其中N是我接收到的輸入實例的總數。是否有可能優化這個Matlab代碼來做矢量量化與質心從k-均值？

要計算標籤，我計算每個輸入向量的最接近的質心。爲此，我將每個輸入向量與所有質心進行比較，並選擇距離最小的質心。標籤就是該質心的索引。

我當前的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

然而，這段代碼仍然是相當緩慢的（對於我而言），我希望有可能會進一步優化代碼的方式。

一個明顯的問題是，有一個for循環，這是Matlab的良好性能的禍根。我一直試圖想出一種方法來擺脫它，但沒有運氣（我研究了與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');

來源

2011-04-20 Abe Schneider

相關：[pdist2相當於MATLAB版本7]（http://stackoverflow.com/a/7774323/97160） – Amro 2012-07-10 20:26:42

可以通過轉換爲電池和使用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);

說明：

我們指定的X每行其在第二行的自己的細胞
這件作品@(x)(sum(bsxfun(@minus,centroids,x).^2,2))是一個匿名函數，它與您的distances=...行相同，並使用cell2mat，我們將它應用於每行X。
這些標籤就是沿着每一列的最小行的索引。

來源

2011-04-20 23:16:22 abcd

它看起來像num2cell（ X）將X的每個元素轉換爲它自己的向量。但是，對於（x-centroids），我們希望每個質心都減去X的每一行。所以它應該讀取：XCell = num2cell（X，2）？ – 2011-04-21 14:38:55

@Abe，你是對的。雖然它肯定會返回相同的答案，但在將其應用於每個元素時會有不必要的函數調用開銷。我修正了這個問題。但是請記住，'bsxfun'和'cellfun'通常只是寫循環的簡單方式，並不一定更快（有時它們是，但並不總是）。定時你的循環和cellfun代碼的矩陣與你的尺寸相同，它們甚至在93秒左右都很漂亮，只有十分之一不同。 – abcd 2011-04-21 15:46:26

太好了，謝謝！是的，我希望Matlab的內部循環可能比它的一般循環更好，但我也沒有看到很大的改進。 for循環也允許'parfor'。最初想要使用GPU，但bsxfun不允許使用foranonymous函數，因此無法傳遞「質心」。我確實找到了一個改進，就是有人在SO上發佈了一個貼在質心而不是數據上的帖子。我有4000個質心，並且在我的數據中有1e5到1e6的任何特徵向量。所以通過在質心上循環，我可以用矩陣數學加快速度。 – 2011-04-21 18:04:29

對於一個真正的矩陣實現，你可以考慮沿着線嘗試一些：

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-22 14:51:40 jmetz

這使用大量內存 - 像任何真正的矢量化版本。（較慢）的替代方案已由@yoda提供。你也許可以用repmat替換kron - 這只是我已經在我自己的項目中使用過的一個版本 – jmetz 2011-04-22 14:57:35

嗯。我會試試這個，因爲我目前的方法將花費4天以上。不過，我對kron並不熟悉，所以我將嘗試使用上面的repmat來重寫它。如果你有機會，你介意驗證嗎？ – 2011-04-22 19:39:44

沒關係。在紙面上，看起來好像是我將兩個矩陣設爲三維（對於大小（質心，1）次重複數據矩陣，並對每個質心重複每個質心大小（數據，1）次，我可以只減去矩形， sum，然後min min，但是我找不到確定第二個矩陣的好方法 – 2011-04-22 19:55:59

使用以下函數計算距離。你應該看到一個數量級的加速

兩個矩陣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-24 11:03:16 twerdster

+1給你。這確實更快。想起來，我不知道我爲什麼不這樣做，而不是使用'cellfun'。最近我一直在使用'cellfun'方式，並且應該暫時從我的工具包中退出，至少:) – abcd 2011-04-24 17:02:16

對於最近鄰搜索，可以使用比蠻力更有效的算法。最流行的方法是Kd-Tree。 O（log（n））平均查詢時間，而不是O（n）蠻力複雜度。關於Maltab實現KD樹的，你可以看看here

來源

2013-11-07 13:28:45 Quant

是否有可能優化這個Matlab代碼來做矢量量化與質心從k-均值？

回答

相關問題