CODEWITHSUNDEEP
pythonarrayspython-2.7multidimensional-array
Often Right
Often Right

Reputation: 425

How to efficiently find clusters of like elements in a multidimensional array

I have a multidimensional array like so:

array = [[a, b, b, a, a, b]
         [a, a, b, a, b, a]]

What I would like to do is identify the clusters of like elements i.e. look at each element and find a group of 'a's based on whether there is another 'a' above, below, to the left or right of it such that the program finds an array like so:

[a, b, b, a, a, b]

[a, a, b, a, b, a]

It would return an array like so ["0:0", "1:0", "1:1"] for the first cluster of 'a's

My question is, what is the most efficient way of doing this in python?

FYI: I'm using Python 2.7

Upvotes: 1

Views: 2801

Answers (1)

Martin Valgur
Martin Valgur

Reputation: 6322

Using scipy.ndimage.measurements:

from scipy import ndimage 

def find_clusters(array):
    clustered = np.empty_like(array)
    unique_vals = np.unique(array)
    cluster_count = 0
    for val in unique_vals:
        labelling, label_count = ndimage.label(array == val)
        for k in range(1, label_count + 1):
            clustered[labelling == k] = cluster_count
            cluster_count += 1
    return clustered, cluster_count

clusters, cluster_count = find_clusters(array)
print("Found {} clusters:".format(cluster_count))
print(clusters)

ones = np.ones_like(array, dtype=int)
cluster_sizes = ndimage.sum(ones, labels=clusters, index=range(cluster_count)).astype(int)
com = ndimage.center_of_mass(ones, labels=clusters, index=range(cluster_count))
for i, (size, center) in enumerate(zip(cluster_sizes, com)):
    print("Cluster #{}: {} elements at {}".format(i, size, center))

yields:

Found 6 clusters:
[[0 3 3 1 1 4]
 [0 0 3 1 5 2]]
Cluster #0: 3 elements at (0.66666666666666663, 0.33333333333333331)
Cluster #1: 3 elements at (0.33333333333333331, 3.3333333333333335)
Cluster #2: 1 elements at (1.0, 5.0)
Cluster #3: 3 elements at (0.33333333333333331, 1.6666666666666667)
Cluster #4: 1 elements at (0.0, 5.0)
Cluster #5: 1 elements at (1.0, 4.0)

To get the locations of elements within each cluster, you can do clusters == cluster_id, e.g.

In [126]:
clusters == 3
Out[126]:
array([[False,  True,  True, False, False, False],
       [False, False,  True, False, False, False]], dtype=bool)

Or, to get the bounding box of each cluster you can use find_objects from the same SciPy package:

In [128]:
# +1 because zeros would be ignored otherwise
scipy.ndimage.measurements.find_objects(clusters+1)
Out[128]:
[(slice(0, 2, None), slice(0, 2, None)),
 (slice(0, 2, None), slice(3, 5, None)),
 (slice(1, 2, None), slice(5, 6, None)),
 (slice(0, 2, None), slice(1, 3, None)),
 (slice(0, 1, None), slice(5, 6, None)),
 (slice(1, 2, None), slice(4, 5, None))]

Upvotes: 2

Related Questions