Euclidean distance without using bsxfun

So, what I would like to do is to generate a column vector containing the square of the Euclidean distance from every point in X to the cluster point with the code below:

[N,~]=size(X);
[c,~]=size(clusters);
dist = zeros(N,c);
for i = 1:c
    dist(:,i) = sum(bsxfun(@minus, X, clusters(i,:)).^2, 2);
end;
[~,label] = min(dist,[],2);

However, I don't want to use bsxfun or repmat. I just want to use elementary operations, which other way could I carry out creating the vector with just elementary operations?

[Image Analyst]

So I guess X is an N by 2 array of (x,y) coordinates. But which point from which array is "the cluster point"? What is the size and shape of "clusters" and which one of it's points do you want to use?

[John D'Errico]

If you don't want to use the capabilities of MATLAB, you should consider switching to another language. Why use an efficient tool (like bsxfun, which lets you compute an entire distance matrix in one line, and do so quickly) when you can use an inefficient scheme like loops and low level adds and subtracts?

In fact, you can write that entire computation in one line in MATLAB, with one call to bsxfun.

dist = squeeze(sum(bsxfun(@minus,X,permute(clusters,[3 2 1])).^2,2));

No loop needed at all.

[candvera]

I'm doing a course where we can only write a kmeans implementation using elementary operations...I guess to have a low-level understanding of Matlab

[John D'Errico]

Ok, so the point is, you need this for homework. Why not say it? Admit it. It is not that you don't want the code you found, but that you cannot use it. You found some code that solves the problem, but your assignment is to write it yourself, using elementary operations.

To do what you want requires nothing more than some nested loops. Subtract, form the square of that difference, and then sum. Euclidean distance is pretty simple, and you are not even asked to take the sqrt.

Do this for each combination of rows of X and cluster. So why not try it? You learn by doing. If you cannot write the simple loops I describe above, then how will you solve the more complex issues in the overall kmeans assignment?

Eat a programming elephant one byte at a time. Don't get lost in the big problem. Break it into small ones.

I'll make a deal with you. How would you form the distance between ONE pair of vectors, thus one row of X and one row of clusters?

Xi = X(ii,:)
clustj = clusters(jj,:)

Each of those vectors has the same number of elements. Show me that you can form the square of the Euclidean distance between them, and I'll help you to put nested loops around the whole thing.

Answer 1

[Image Analyst]

Let's say you have two arrays, points1 and points2, which are two lists of (x.y) coordinates. To find the distances between every point and every other point, you can use pdist() and squareform() if you have the Statistics and Machine Learning Toolbox. Otherwise use the brute force method. Here is a full demo that makes the measurements and puts them in a nice array, then plots it up nice and fancy:

% Demo to demonstrate how pdist() can find distances between all points of 2 sets of points.
% Requires the Statistics and Machine Learning Toolbox because of the pdist() and squareform() functions.
clc;    % Clear the command window.
close all;  % Close all figures (except those of imtool.)
clear;  % Erase all existing variables. Or clearvars if you want.
workspace;  % Make sure the workspace panel is showing.
format short g;
format compact;
fontSize = 28;

numPoints1 = 5;
numPoints2 = 3;
points1 = [ones(numPoints1,1), (41:(41+numPoints1-1))'];
points2 = [2*ones(numPoints2,1), (41:(41+numPoints2-1))'];
% Plot all the points
subplot(2, 2, 1);
plot(points1(:, 1), points1(:, 2), 'bo', 'MarkerSize', 12, 'LineWidth', 1.5);
hold on;
plot(points2(:, 1), points2(:, 2), 'bs', 'MarkerSize', 12, 'LineWidth', 1.5);
xlim([0, 3]);
grid on;
xlabel('X', 'FontSize', fontSize);
ylabel('Y', 'FontSize', fontSize);
title('All Points', 'FontSize', fontSize);
legend('Set #1', 'Set #2')
text(.6, 43.25, 'Point Set #1', 'FontSize', 13, 'Color', 'b');
text(2.1, 43.25, 'Point Set #2', 'FontSize', 13, 'Color', 'b');

% Set up figure properties:
% Enlarge figure to full screen.
set(gcf, 'Units', 'Normalized', 'OuterPosition', [0 0 1 1]);
% Get rid of tool bar and pulldown menus that are along top of figure.
set(gcf, 'Toolbar', 'none', 'Menu', 'none');
% Give a name to the title bar.
set(gcf, 'Name', 'Demo by ImageAnalyst', 'NumberTitle', 'Off')

% Get the distance from every point to every other point.
pDistances = pdist([points1;points2])
% That's hard to interpret though, so
% let's reshape that into a nice table
sfd = squareform(pDistances)
% Extract a table where the row index is the index of point 1,
% and the column index is the index of point 2
distances = sfd(1:numPoints1, numPoints1+1:end)
% No semicolons above so results will be reported in the command window.

% Plot all the lines between points
for p2 = 1 : numPoints2
  x2 = points2(p2, 1);
  y2 = points2(p2, 2);
  subplot(2, 2, p2+1); % Do it in a new plot
  for p1 = 1 : numPoints1
    x1 = points1(p1, 1);
    y1 = points1(p1, 2);
    plot([x1, x2], [y1, y2], 'bo-', 'MarkerSize', 9, 'LineWidth', 1.5);
    hold on;
    xlabel('X', 'FontSize', fontSize);
    ylabel('Y', 'FontSize', fontSize);
    % Label the line with the length that it is.
    lineLabel = sprintf('Distance = %.3f.', distances(p1, p2));
    text(0.3, points1(p1, 2), lineLabel, 'FontSize', 13);
    pointLabel = sprintf('Point %d of Point Set #2', p2);
    text(x2+ 0.1, y2, pointLabel, 'FontSize', 13, 'Color', 'b');
  end
  % Fancy up the plot
  caption = sprintf('Distances to point #%d of Point Set #2', p2);
  title(caption, 'FontSize', fontSize);
  xlim([0, 3]);
  ylim([40, 46]);
  grid on;
end
message = sprintf('Done with demo.\nCheck out command window for a table of distances');
helpdlg(message);