# Clustering 1-d array with constraints?

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?

• Consider the Wikipedia page on determining the number of clusters. The fact that you have 1-d data makes your problem simpler, but you still need to take a decision what should be your criterion for the values that are far from 0. Dec 15, 2018 at 7:00
• You might also be interested in hierarchical clustering. Dec 15, 2018 at 7:02

Don't use clustering at all.

Define a threshold, and theshold the data. Done.

Keep it simple and easy to understand.

• The thing is there is no such a fixed threshold in this case. For some data it might be -0.5 to 0.5, for some other it might be -0.3 to 1.2, it really depends on how the values distribute in the input. When manually inspecting I mainly try to find the break points of every density data points to locate the start/end of close-to-0 cluster.
– Lee
Dec 16, 2018 at 1:54
• Try simple statistics, such as 3* the average difference of consecutive points. Or apply a standard change point detection method for time series such as CUSUM to detect a change in mean. Dec 16, 2018 at 15:47
• Thresholding seems the way to go for this task as it is presented. Alternatively, thresholds can be automatically detected on the statistical distribution, for instance, using kernel density distribution and its local minima. Feb 13, 2019 at 15:00
• For above plots, a typical change point analysis should work fine. Much more appropriate than clustering, as this is a standard technique in time series analysis. Feb 13, 2019 at 19:17

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.