Можно ли оптимизировать этот код Matlab для выполнения векторного квантования с центроидами из k-средних? - PullRequest
Новая
       14

Можно ли оптимизировать этот код Matlab для выполнения векторного квантования с центроидами из k-средних?

2 голосов
/ 21 апреля 2011

Я создал кодовую книгу с использованием k-средних размера 4000x300 (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

Однако, этот код все еще довольно медленный (для моих целей), и я надеялся, что может быть способ оптимизировать код дальше.

Одна очевидная проблема заключается в том, что существует цикл for, который является препятствием для хорошей производительности на Matlab. Я пытался найти способ избавиться от него, но безуспешно (я изучал использование arrayfun в сочетании с bsxfun, но так и не получил этого). В качестве альтернативы, если кто-то знает какой-либо другой способ ускорить это, я был бы очень признателен.

Обновление

После некоторого поиска я не смог найти отличного решения с использованием 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)

, который использует биномиальную форму евклидова расстояния ((x-y) ^ 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 голосов
/ 24 апреля 2011

Используйте следующую функцию для расчета расстояния. Вы должны увидеть порядок ускорения

Две матрицы A и B имеют столбцы в качестве измерений и строки в качестве каждой точки. А это твоя матрица центроидов. 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';
1 голос
/ 07 ноября 2013

Вы можете использовать более эффективный алгоритм поиска ближайшего соседа, чем перебор.Самый популярный подход - Kd-Tree.O (log (n)) среднее время запроса вместо O (n) грубой силы сложности.Что касается реализации Ktab-деревьев в Maltab, вы можете посмотреть здесь

1 голос
/ 22 апреля 2011

Для истинной реализации матрицы вы можете попробовать что-то вроде: 

  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 ...; ...]

1 голос
/ 21 апреля 2011

Вы можете векторизовать его, преобразовав в ячейки и используя 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.
  • В этом случае метки являются индексами минимальной строки по каждому столбцу.
...