1D Number Array Clustering

user_1053163 0
Viewed 73661

So let's say I have an array like this:

[1,1,2,3,10,11,13,67,71]

Is there a convenient way to partition the array into something like this?

[[1,1,2,3],[10,11,13],[67,71]]

I looked through similar questions yet most people suggested using k-means to cluster points, like scipy, which is quite confusing to use for a beginner like me. Also I think that k-means is more suitable for two or more dimensional clustering right? Are there any ways to partition an array of N numbers to many partitions/clustering depending on the numbers?

Some people also suggest rigid range partitioning, but it doesn't always render the results as expected

partition-problem dimension cluster-analysis data-mining arrays
5 Answers

This simple algorithm works:

points = [0.1, 0.31,  0.32, 0.45, 0.35, 0.40, 0.5 ]

clusters = []
eps = 0.2
points_sorted = sorted(points)
curr_point = points_sorted[0]
curr_cluster = [curr_point]
for point in points_sorted[1:]:
    if point <= curr_point + eps:
        curr_cluster.append(point)
    else:
        clusters.append(curr_cluster)
        curr_cluster = [point]
    curr_point = point
clusters.append(curr_cluster)
print(clusters)

The above example clusters points into a group, such that each element in a group is at most eps away from another element in the group. This is like the clustering algorithm DBSCAN with eps=0.2, min_samples=1. As others noted, 1d data allows you to solve the problem directly, instead of using the bigger guns like DBSCAN.

The above algorithm is 10-100x faster for some small datasets with <1000 elements I tested.

user_11978600

CKwrap is a fast and straightforward k-means clustering function, though a bit light on documentation.

Example Usage

pip install ckwrap

import ckwrap

nums= np.array([1,1,2,3,10,11,13,67,71])
km = ckwrap.ckmeans(nums,3)

print(km.labels)
# [0 0 0 0 1 1 1 2 2]


buckets = [[],[],[]]
for i in range(len(nums)):
    buckets[km.labels[i]].append(nums[i])
print(buckets)
# [[1, 1, 2, 3], [10, 11, 13], [67, 71]]
exit()

I expect the authors intended you to make use of the nd array functionality rather than create a list of lists.

other measures:

km.centers
km.k
km.sizes
km.totss
km.betweenss
km.withinss

The underlying algorithm is based on this article.

user_113382330

Late response and just for the record. You can partition a 1D array using Ckmeans.1d.dp.

This method guarantees optimality and it is O(n^2), where n is the num of observations. The implementation is in C++ and there is a wrapper in R.

user_154284990
Related