25 views (last 30 days)

Show older comments

Hello,

I have a 1-dimensional array with index values of extremes I found in a much larger dataset, ordered from lowest to highest. I wish to seek out if there is any data clustering within this array. What's the simplest way to do this? The total amount of clusters is unknown beforehand. A cluster can be defined as any values that are within a certain predefined distance from each other. I'd like to know the amount of clusters found, and an array with the number of values found within each cluster.

I made a simple illustration of what I'd like in the figure below. The crosses indicate values in the array on the number line. Values close together (removed less than a given distance), are grouped together and counted.

So, in this case, the output would be;

5 (number of clusters found)

[3, 2, 1, 1, 5] (size of each cluster)

Thanks in advance!

Kelly Kearney
on 21 Aug 2021

If the cluster tolerance defines how close points need to be to their nearest neighbor in order to be called a cluster, then you just need to check for where the gaps are larger than that tolerance:

% The data

tol = 0.1;

x = [1 1 1 2 2 3 4 5 5 5 5 5];

x = x + rand(size(x))*tol-tol/2;

% Find clusters

dx = diff(x);

isnew = dx > tol;

idx = cumsum([1 isnew]);

ncluster = max(idx)

nper = splitapply(@length, idx, idx)

If instead your tolerance sets the maximum distance a point can be from all points in its cluster, then things get a bit trickier.

Image Analyst
on 21 Aug 2021

Edited: Image Analyst
on 21 Aug 2021

If you have the Statistics and Machine Learning Toolbox, there is a function that does this. It's called dbscan() after the clustering algorithm of the same name (which should probably be more famous than it is.)

See attached dbscan demo, and Wikipedia description:

Basically it finds all points within a specified distance from other points by daisy chaining its way along. All those points that can be connected by a daisy chain length less than what you specified belong to one cluster. Then it moves on to other unclassified points to find more clusters. Points that are farther away from any point than your distance are not clusters, or in other words they're a cluster of only 1 point.

Here's a very well commented demo that is more tailored to your data:

% First define the data.

x = [1 1 1 2 2 3 4 5 5 5 5 5];

y = zeros(1, length(x));

% Plot it.

plot(x, y, 'rx', 'MarkerSize', 20, 'LineWidth', 3);

ax = gca;

ax.XAxisLocation = 'origin';

grid on;

% Now find clusters.

minDistance = 0.5; % Need to be closer than this to be in the same cluster.

minPointsPerCluster = 2; % A cluster must have at least 2 points to be a valid cluster.

indexes = dbscan([x',y'], minDistance, minPointsPerCluster)

% The value of indexes say what cluster number that point belongs to.

% If the value is -1, it does not belong to a cluster and is a single, isolated point.

% Find the number (count) in each cluster

pointCounts = hist(indexes, -1 : max(indexes))

% It says there are 2 points not in a cluster (single isolated points),and

% then the counts are 3, 2, and 5 for the 3 clusters it found.

Image Analyst
on 22 Aug 2021

You can do this in a single line of code with a call to findgroups() and histcounts():

% First define the data.

x = [1 1 1 2 2 3 4 5 5 5 5 5];

% Now find groups.

g1 = findgroups(x)

% Count the number in each group.

counts1 = histcounts(g1)

% Now with another group of 1's on the end, separated from the first group of 1's.

x = [1 1 1 2 2 3 4 5 5 5 5 5 1 1];

counts2 = histcounts(findgroups(x)) % Combining 2 statements into 1.

You see:

counts1 =

3 2 1 1 5

counts2 =

5 2 1 1 5

as you should.

Image Analyst
on 22 Aug 2021

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!