Clustering 1-d array with constraints?

Question

I have following kind of 1-d array data to cluster with a few constraints:

The array has length from 50 to 300, floating, some of them close to 0 and some far away.

Goal: divide the array into n clusters so the values close to 0 are in one cluster and others in separate clusters.

E.g. array 1

[2.56, 5.02, 4.67, 3.14, 5.46, 3.07, 3.96, 4.21, 5, 2.12, 4.43, 5.51, 3.31, 2.98, 2.9, 4.66, 0.2, 1.24, 0.78, 1.41, 0.15, 0, 0, 1.58, 2.84, 0.9, 0.85, 1.69, 1.14, 0.74, -0.19, -0.38, 0.55, 0.17, -0.52, 0.52, 1.34, 0.19, 0, 1.72, 0.55, 0.98, -0.61, 0, -0.16, 1.53, 0.3, 0.39, 0.6, -0.31, -1.38, 0.39, 1.26, 0.47, -0.38, -0.48, 0, 0, 82.13, 0, 0, 97.17, 184.07, 185.12, 187.8, 167.22, 169.34, 165.76, 162.82, 187.24, 179.31, 189.49, 187.27, 179.29, 157.42, 0.24, -0.7, 1.23]

Scatter chart for array 1:

E.g. array 2

[2.7, 3.85, 3.08, 2.94, 2.98, 3.59, 3.13, 3.83, 3.25, 3.34, 3.73, 3.2, 2.77, 3.18, 3.62, 2.17, 3.29, 3.12, 3.98, 3.72, 3.87, 3.45, 3.21, 3.7, 4.5, 3.4, 3.67, 3.65, 3.65, 3.14, 3.94, 3.47, 3.03, 4.38, 3.01, 3.38, 4.06, 3.43, 3.81, 4.01, 2.96, 3.04, 3.51, 2.85, 3.84, 4.33, 2.81, 2.65, 2.66, 3.54, 4.89, 3.17, 3.46, 2.51, 3.36, -15.1, 3.12, 3.12, 3.63, 3.07, 5.48, 4.88, 4.3, 2.91, 0.3, 1.06, -0.1, 0.81, -0.62, 0.58, 1.22]

Scatter chart for array 2:

For array 1 the slice [16:60] (approx.) should be identified into the cluster close to 0, and [0:16] and [60:] should be other clusters.

For array 2 the slice [64:] (approx.) should be identified into the cluster close to 0 and [0:64] be other cluster.

I tried kmeans and dbscan from sklearn.cluster lib but could not get ideal result.

kmeans: it has to be given n_clusters, which is uncertain in my case. If the num is small or big, the cluster would cover more or less than I want.

dbscan: it is impacted by the eps and min_samples values which are also uncertain in my case.

My current idea is to sort the array, find the gap in the values in array and cluster the values between each gap. However I don't get a solid implementation.

Any other idea or suggestion to my idea?

Answer 1

Don't use clustering at all.

Define a threshold, and theshold the data. Done.

Keep it simple and easy to understand.

Answer 2

Well, you can sort the data and find the maximally distant clusters by calculating the distance between the mean of all points in each cluster. Then, recursively perform this operation using a tree to split the data into clusters. However, this approach also needs a minimum number of samples (I'd recommend using a min of 2 samples).

Here's some code for how to find the best split on your first example array -

from itertools import tee
import numpy as np

def pairwise(iterable):
    """Generates pairwise elements
    s -> (s0,s1), (s1,s2), (s2, s3), ...
    """

    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

# Splits data on a point and returns distance of the means of the two splits
def split(arr, split_on):
        return np.abs(np.mean(arr[arr < split_on]) - np.mean(arr[arr > split_on]))

a = [2.56, 5.02, 4.67, 3.14, 5.46, 3.07, 3.96, 4.21, 5, 2.12, 4.43, 5.51, 3.31, 2.98, 2.9, 4.66, 0.2, 1.24, 0.78, 1.41, 0.15, 0, 0, 1.58, 2.84, 0.9, 0.85, 1.69, 1.14, 0.74, -0.19, -0.38, 0.55, 0.17, -0.52, 0.52, 1.34, 0.19, 0, 1.72, 0.55, 0.98, -0.61, 0, -0.16, 1.53, 0.3, 0.39, 0.6, -0.31, -1.38, 0.39, 1.26, 0.47, -0.38, -0.48, 0, 0, 82.13, 0, 0, 97.17, 184.07, 185.12, 187.8, 167.22, 169.34, 165.76, 162.82, 187.24, 179.31, 189.49, 187.27, 179.29, 157.42, 0.24, -0.7, 1.23]

# Sort the data
x = np.array(sorted(a))
# Find midpoints of data (generates splits for the data)
mids = [np.median(np.array(i)) for i in pairwise(x)]

max_dist = None
index = None
for mid in mids:
    if max_dist is None or max_dist < split_max(x, mid):
        max_dist = split_max(x, mid)
        index = mid
    else:
        pass


In [23]: x[x < index]
Out[23]: 
array([-1.38, -0.7 , -0.61, -0.52, -0.48, -0.38, -0.38, -0.31, -0.19,
       -0.16,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,  0.  ,
        0.15,  0.17,  0.19,  0.2 ,  0.24,  0.3 ,  0.39,  0.39,  0.47,
        0.52,  0.55,  0.55,  0.6 ,  0.74,  0.78,  0.85,  0.9 ,  0.98,
        1.14,  1.23,  1.24,  1.26,  1.34,  1.41,  1.53,  1.58,  1.69,
        1.72,  2.12,  2.56,  2.84,  2.9 ,  2.98,  3.07,  3.14,  3.31,
        3.96,  4.21,  4.43,  4.66,  4.67,  5.  ,  5.02,  5.46,  5.51,
       82.13, 97.17])

In [24]: x[x > index]
Out[24]: 
array([157.42, 162.82, 165.76, 167.22, 169.34, 179.29, 179.31, 184.07,
       185.12, 187.24, 187.27, 187.8 , 189.49])

When you finish building a tree that does this you can essentially only pick those leaves whose mean is close to 0. This is basically a different implementation of a kd-tree. Here's a link to space partition using kd-trees.