How do you calculate the minimum circle within a cluster set of data points to potentially identify the ones that are most similar?

I have made a PCA plot and I would like to calculate the minimum circle within a cluster set of data points to potentially identify the ones that are most similar, how can I do that?

Answer 1

[John D'Errico]

Let me give an example.

XY = [randn(20,2)*1 + [-5,5];randn(10,2)*1.5 + [3 6];randn(10,2)*1 + [-7 -4]];
plot(XY(:,1),XY(:,2),'o')

How would you draw circles around what appear to be three groups of points here? As I have said many times, I would jsut use kmeans. I know there are three groups. This is a serious problem in any clustering tool, since you need to know how many clusters there are. Lacking that, the problem becomes MUCH more difficult. Again, these are things the human eye/brain combination does very naturally.

clustidx = kmeans(XY,3);
C = [1 0 0;0 1 0;0 0 1];
scatter(XY(:,1),XY(:,2),[],C(clustidx,:))

So k-means has done very nicely. But it really does need to know the number of clusters to search for.

And, now we can draw bounding circles.

hold on
t = linspace(0,2*pi);
C = zeros(3,2);
R = zeros(3,1);
colors = 'rgb';
for i = 1:3
  ind = find(clustidx == i);
  [C(i,:),R(i)] = minboundcircle(XY(ind,1),XY(ind,2));
  plot(C(i,1) + R(i)*cos(t),C(i,2) + R(i)*sin(t),['-',colors(i)])
end
hold off

Now, could I have done the clustering in a different way? Possibly. One idea might be to use graph theoretic tools in MATLAB.

For example, on the same set of data, start with tihe set of interpoint distances.

D = squareform(pdist(XY));

Now, if there are truly 3 distinct clusters, then roughly 66% of the distances between points will be between points from different clusters. So I'll zero out 75% of the distances.

D(D > prctile(D(:),25)) = 0;

Next, create a graph of what remains.

GD = graph(D)

GD = 
  graph with properties:

    Edges: [180×2 table]
    Nodes: [40×0 table]

plot(GD)

The conncomp function will identify the sets of points that are connected to each other.

conncomp(GD)

ans = 1×40

1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3

As you can see, it did indeed identify three main clusters of points, though one point was disconnected from the rest, effectively seen as an outlier. Regardless, I could now have built the same plot as above, using these connected components.

[Neo]

@John D'Errico

figure(1)

clustidx = kmeans(C,3);

J = [1 0 0;0 1 0;0 0 1];

scatter(C(:,1),C(:,2),[],J(clustidx,:))

hold on

t = linspace(0,2*pi);

J = zeros(3,2);

R = zeros(3,1);

colors = 'rgb';

for i = 1:3

ind = find(clustidx == i);

[J(i,:),R(i)] = minboundcircle(C(ind,1),C(ind,2));

plot(J(i,1) + R(i)*cos(t),J(i,2) + R(i)*sin(t),['-',colors(i)])

end

hold off

What i intended my code to do was perform k means on my data matrix C then draw the min bounding circles, here is what the code output.

Was it succesful? Then I can be done with this question, thanks for your help.

[Laura]

@John D'Errico @Neo

Sorry I am curious if this code worked as depicted since I have a similar question. Is the output accurate? Thank you from Australia!

Answer 2

[Image Analyst]

You have the classes to which the cluster is assigned. But I'm not sure, for a particular cluster, what "the minimum circle within a cluster set of data points" means. Do you want to find the pair of points in each cluster that are closest to each other? Do you want to find the minimum containing/bounding circle for each cluster? Do you want the size of each cluster's bounding circle? Please clarify. How many PCs do you have? How many clusters do you have?

See

https://www.mathworks.com/matlabcentral/fileexchange/34767-a-suite-of-minimal-bounding-objects?s_tid=srchtitle

[Neo]

@Image Analyst

To clarify, I have 3 clusters. I want to find the minimum containing/bounding circle for each cluster.

[Image Analyst]

OK, so what happened when you used John's D'Errico's utility?

[Neo]

@Image Analyst

I did not notice he attached it then but I tried it now and was not able to get it to work.

[Image Analyst]

I know I've told you this before but you don't seem to have done it or be taking it to heart so I'll ask again:

If you have any more questions, then attach your data and code to read it in with the paperclip icon after you read this:

TUTORIAL: How to ask a question (on Answers) and get a fast answer

Of course John didn't attach it. He may not even have opened up this discussion thread. You need to download it from the link I gave and call the function in your code (which you're still not sharing with me for some reason).

[Neo]

@Image Analyst Sorry I thought you were referring to another Tutorial John attached. Please ignore.

Also I have been using your PCA cluster demo that you have published sorry for not stating that, usually whatever you write I note it and reference it so sorry for not asking my questions coherently. I want to find the minimum containing/bounding circle for each cluster. In a previous thread John suggested "Once you have the data clustered into groups, I would then just use the centroids from k-means itself as the center of the circles." But I did check out his min bound circles code and got the following error:

Not enough input arguments.

Error in minboundcircle (line 55)

x=x(:);

[Image Analyst]

OK, but again you have forgotten to attach your script (not my demo). From what we gather, it seems your script does (or attempt to do):

1. You converted your original coordinates into PC coordinates.
2. And then you did some kind of clustering on it in PC space - perhaps you used kmeans - I don't know.
3. So now you have clusters and you want to extract each cluster individually and call John's min circle function.

So attach your code and data that does all that and we'll try to fix it. But, I'm not sure what a circle in PC space means. Like someone said in one of your other posts, PCs might make intuitive sense, but they might just be a bunch of weighted terms summed up with no intuitive meaning at all. Are you really sure you need to go to PC space to do your clustering and can't just do it in the original coordinate space?

[Image Analyst]

You're plotting the y value of the data (a lot of values) versus the x value of only the centroids which is only 2 values. Not only do the sizes not match, but the concept doesn't even make sense. Explain in words what you are trying to plot with a black X marker.

[Neo]

@Image Analyst

figure(1)

clustidx = kmeans(C,3);

J = [1 0 0;0 1 0;0 0 1];

scatter(C(:,1),C(:,2),[],J(clustidx,:))

hold on

t = linspace(0,2*pi);

J = zeros(3,2);

R = zeros(3,1);

colors = 'rgb';

for i = 1:3

ind = find(clustidx == i);

[J(i,:),R(i)] = minboundcircle(C(ind,1),C(ind,2));

plot(J(i,1) + R(i)*cos(t),J(i,2) + R(i)*sin(t),['-',colors(i)])

end

hold off

What i intended my code to do was perform k means on my data matrix C then draw the min bounding circles, here is what the code output.

Was it succesful? Then I can be done with this question, thanks for your help.

[Neo]

@Image Analyst Though, Why do i need to make a matrix J?

[Image Analyst]

Please attach your C, like in a .mat file with the paperclip icon.

[Neo]

@Image Analyst

By C do you mean the data matrix? Please find the C attached.

sized = size(matrix);

lbs = sized(1);

lVs = sized(2) - 3;

C = zeros(lbs,lVs);

title("k-means with minimum bounding circle");

clust = kmeans(C,3);

J = [1 0 0;0 1 0;0 0 1];

scatter(C(:,1),C(:,2),[],J(clust,:))

hold on

t = linspace(0,2*pi);

J = zeros(3,2);

R = zeros(3,1);

colors = 'rgb';

for i = 1:3

ind = find(clust == i);

[J(i,:),R(i)] = minboundcircle(C(ind,1),C(ind,2));

plot(J(i,1) + R(i)*cos(t),J(i,2) + R(i)*sin(t),['-',colors(i)])

end

hold off

[Neo]

@Image Analyst I will upload my c data matrix tomorrow because i have a daily limit but I deleted the files so I don't know why i cant upload it so I will just wait until tomorrow.

[Neo]

@Image Analyst

Here is my c data matrix referenced in my above code.

To get the 3d scatter plot i substituted the scatter plot line with:

scatter3(C(:,1), C(:,2), C(:,3), 15, J(clust,:));

What i intended my code to do was perform k means on my data matrix C (attached) then draw the min bounding circles, here is what the code output.

Was it succesful? Thanks for your help.

[Laura]

Sorry @Neo I am curious if this code worked as depicted since I have a similar question. Is the output accurate? Thank you from Australia!

[Neo]

@Laura Thanks for your interest. @John D'Errico or @Image Analyst may confirm.

[Neo]

@Laura

I think it is right, though not sure what it means.

Answer 3

[John D'Errico]

How many times will you ask the same question? You keep on talking about a minimal circle. Sometimes it is to draw a minimal circle. And sometimes you seem to be confusing different algorithms. (Why I pretty much gave up on responding to your posts. Sorry, but I did.) This time it is to use the minimal circle to identify a cluster of similar points, but you don't say how the cluster would be identified.

The problem is, your question does not seem to understand there are several issues here. If you have a cluster of points, you can trivially find the minimal bounding circle. But a mimimal bounding circle algorithm is not a clustering tool. So you cannot use that bounding circle code to find a cluster of points that you have not first identified.

I really am sorry, but it just seems as if you want to do something, but have no idea what is involved in doing what you want. So you just keep on asking the same question over and over again.

So, you have some points (currently in 2-d, the result of a PCA.) They may be pretty sparse, at least from the pictures drawn, which makes EVERYTHING more difficult. And what your eye sees are several groups of points. What you want is some automatic code that will draw a circle around the various clusters that your eye sees. This seems to be the gist of the last 3 or more questions that you have asked. The problem is, you need to use the tools we have been suggesting, at least if you want to do this in a way that is automatic.

First, perform a clustering analysis. There are MANY clustering algorithms available, but kmeans has some of the most commonly used tools.

Or, you could simply choose the clusters for any similar group of points yourself. For example, I have posted code on the file exchange (selectdata) that will allow a user to select groups of points using a lasso. Just draw a curve around the points in one group, and it will tell you which points they were. Or you can tell the code to use a circular shape, then you click on the figure, and expand that circle until it contains the points you want. The idea is, you surely know what you want to see. So do it using a mouse. But if not, then you NEED TO USE A CLUSTERING TOOL. A minimal bounding circle is not a tool for clustering.

Can I explain why a minimal bounding circle does not work as a tool for clustering? That might be a good question. The point is a bounding circle is almost always controlled by 3 points, and sometimes rarely only 2 points. If you drop one or more of those points, the minimal bounding circle changes dramatically. This makes the bounding circle rather an unstable thing, since it does not depend on any of the other data points inside the circle. And that means you cannot use it to perform clustering. You need to use some other scheme first. PLEASE READ AND UNDERSTAND THIS LAST PARAGRAPH. A bounding circle is not in itself a clustering tool, nor can it be made to work as one. At least not well.

Once you have the points identified in any one similar cluster, then use a tool as I have shown to find the circle and then draw it. I don't see the problem, or why this requires so many repeated questions on the topic.

Again, break down the problem into smaller ones. First you need to use clustering though. We dont know enoiugh about your problem to know which clustering scheme might be best, but very likely just selecting the points with a mouse might be the best.

[Neo]

@John D'Errico to clarify I want to use the minimal circle to identify a cluster of similar points, the cluster would be identified by PCA. (I understand it just reduces the dimensionality and does not know which values belong where).

Since I want to use the automatic way I have investigated PCA and T-SNE as my clustering algorithms and now want to draw the smallest cirlce that can identify automatically the closest points in relevance. So I guess that brings me back to my question that I thought i asked (sorry english is one of languages I speak) which is how to draw minimal curcle that automatically identifies a cluster of similar points by their values.

[John D'Errico]

But again, you cannot do that in any stable way. A minimal circle is a poor thing to identify a cluster of points, because that minimal circle is ALWAYS based on only a few points in any set. You really don't want to do exactly what it is you think you want to do. For example:

xy = randn(20,2);
[C,R] = minboundcircle(xy(:,1),xy(:,2))

C = 1×2

0.0982 0.5052

R = 2.4690

t = linspace(0,2*pi,100);
plot(xy(:,1),xy(:,2),'bo',R*cos(t) + C(1), R*sin(t) + C(2),'-r')
axis equal

Do you see that only 3 points ALWAYS control the position and size of the circle? In some cases, only 2 points may control the circle. And if you were to delete one or more of those points, then the circle changes in a very unstable, totally unpredictable way. The rest of the points inside that circle have no impact at all on the circle itself.

You cannot use a minimal bounding circle to perform clustering. You CAN use it AFTER you have performed the clustering. But not to do the clustering itself. And I know that when you look at a set of points in a picture, you see a circle that contains them. So you think the circle can be made to do what you want. But your eye/brain combination can do many things that are exceedingly difficult to do using a computer, and to do it robustly.