Vectorize октава/коды MATLAB

Question

Ниже приводится коды октавы (часть kmeans)

centroidSum = zeros(K); 
valueSum = zeros(K, n); 
for i = 1 : m 
    for j = 1 : K  
    if(idx(i) == j) 
     centroidSum(j) = centroidSum(j) + 1; 
     valueSum(j, :) = valueSum(j, :) + X(i, :); 
    end 
    end 
end 

Коды работают, можно ли векторизовать коды? Легко векторизовать коды без оператора if, , но как мы можем векторизовать коды с помощью оператора if?

Answer 1

Я принимаю назначение кода состоит в вычислении центроиды подмножеств множества m точек данных в n-мерном пространстве, где точки сохраняются в матрице X (точки х координат) и вектором idx определяет для каждой точки данных подмножество (1 ... K), к которому принадлежит точка. Тогда частичное векторизация:

centroid = zeros(K, n) 
for j = 1 : K 
    centroid(j, :) = mean(X(idx == j, :)); 
end 

if устраняется путем индексации, в частности логической индексации: idx == j дает булево массив, который указывает, какие точки данных относятся к подмножеству j.

Я думаю, что можно было бы избавиться от второго цикла for-loop, но это приведет к очень запутанному, непонятному коду.

Answer 2

Краткое введение и решение Код

Это может быть один полностью векторизованную подход, основанный на -

• accumarray: Для накопления сложений, как это сделано для calulating valueSum. Это также вводит технику, как можно использовать accumarray on a 2D matrix along a certain direction, что невозможно с ее прямым движением.
• bsxfun: для расчета линейных индексов по всем столбцам для сопоставления индексов строк от idx.

Вот реализация -

%// Store no. of columns in X for frequent usage later on 
ncols = size(X,2); 

%// Find indices in idx that are within [1:k] range, call them as labels 
%// Also, find their locations in that range array, call those as pos 
[pos,id] = ismember(idx,1:K); 
labels = id(pos); 
%// OR with bsxfun: [pos,labels] = find(bsxfun(@eq,idx(:),1:K)); 

%// Find all labels, i.e. across all columns of X 
all_labels = bsxfun(@plus,labels(:),[0:ncols-1]*K); 

%// Get truncated X corresponding to all indices matches across all columns 
X_cut = X(pos,:); 

%// Accumulate summations within each column based on the labels. 
%// Note that accumarray doesn't accept matrices, so we were required 
%// to create all_labels that had same labels within each column and 
%// offsetted at constant intervals from consecutive columns 
acc1 = accumarray(all_labels(:),X_cut(:)); 

%// Regularise accumulated array and reshape back to a 2D array version 
acc1_reg2D = [acc1 ; zeros(K*ncols - numel(acc1),1)]; 
valueSum = reshape(acc1_reg2D,[],ncols); 
centroidSum = histc(labels,1:K); %// Get labels counts as centroid sums 

Бенчмаркинг код

%// Datasize parameters 
K = 5000; 
n = 5000; 
m = 5000; 

idx = randi(9,1,m); 
X = rand(m,n); 

disp('----------------------------- With Original Approach') 
tic 
centroidSum1 = zeros(K,1); 
valueSum1 = zeros(K, n); 
for i = 1 : m 
    for j = 1 : K  
    if(idx(i) == j) 
     centroidSum1(j) = centroidSum1(j) + 1; 
     valueSum1(j, :) = valueSum1(j, :) + X(i, :); 
    end 
    end 
end 
toc, clear valueSum1 centroidSum1 

disp('----------------------------- With Proposed Approach') 
tic 
%// ... Code from earlied mentioned section 
toc 

Продолжительность Результаты

----------------------------- With Original Approach 
Elapsed time is 1.235412 seconds. 
----------------------------- With Proposed Approach 
Elapsed time is 0.379133 seconds. 

Answer 3

Не уверен, что его производительность во время выполнения, но вот , не замысловатая Векторизованные реализации:

b = idx == 1:K; 
centroids = (b' * X) ./ sum(b)'; 

Answer 4

Векторизация расчета делает огромную разницу в производительности. Сопоставительный анализ

1. Оригинальный код,
2. Парциальной векторизации от А.Donda и
3. Полный векторизации от Тома,

дал мне следующие результаты:

Original Code: Elapsed time is 1.327877 seconds. 

Partial Vectorization: Elapsed time is 0.630767 seconds. 

Full Vectorization: Elapsed time is 0.021129 seconds. 

Бенчмаркинг код здесь:

%// Datasize parameters 
K = 5000; 
n = 5000; 
m = 5000; 

idx = randi(9,1,m); 
X = rand(m,n); 

fprintf('\nOriginal Code: ') 
tic 
centroidSum1 = zeros(K,1); 
valueSum1 = zeros(K, n); 
for i = 1 : m 
    for j = 1 : K  
    if(idx(i) == j) 
     centroidSum1(j) = centroidSum1(j) + 1; 
     valueSum1(j, :) = valueSum1(j, :) + X(i, :); 
    end 
    end 
end 
centroids = valueSum1 ./ centroidSum1; 
toc, clear valueSum1 centroidSum1 centroids 

fprintf('\nPartial Vectorization: ') 
tic 
centroids = zeros(K,n); 
for k = 1:K 
    centroids(k,:) = mean(X(idx == k, :)); 
end 
toc, clear centroids 

fprintf('\nFull Vectorization: ') 
tic 
centroids = zeros(K,n); 
b = idx == 1:K; 
centroids = (b * X) ./ sum(b)'; 
toc 

Обратите внимание, я добавил дополнительную строку в исходный код для элементарного разделения значенияSum1 на centroidSum1, чтобы сделать вывод каждого типа кода одинаковым.

Наконец-то я знаю, что это не совсем «ответ», однако у меня недостаточно репутации, чтобы добавить комментарий, и я думал, что эталонные показатели полезны для всех, кто изучает MATLAB (как и я) и требуется дополнительная мотивация для овладевания векторизацией.