group numbers in an array by step value changes

Viewed 2741

i have an array like [101, 107, 106, 199, 204, 205, 207, 306, 310, 312, 312, 314, 317, 318, 380, 377, 379, 382, 466, 469, 471, 472, 557, 559, 562, 566, 569...]

In this array, after a few integers, there will be a step change in value.(like between [101,107,106] and [199,204,...]) Or put it in another way, the array is made up of groups of integers, each group with values centered around an unknown mean. But i won't know how many groups are there in total ,and the number of integers in each is uncertain.

How could i group those integers in each step change into different arrays.

Thanks

3 Answers

You could try this: Determine the difference for each pair of consecutive numbers, and from those determine the average difference.

nums = [101, 107, 106, 199, 204, 205, 207, 306, 310, 312, 312, 314, 317, 318, 
        380, 377, 379, 382, 466, 469, 471, 472, 557, 559, 562, 566, 569]
pairs = list(zip(nums, nums[1:]))
diffs = [abs(x-y) for x, y in pairs]
avg_diff = sum(diffs) / len(diffs)  # ~ 18.31

Now, you can group the numbers by whether the difference to the previous number is lower or higher than that average:

groups = [[nums[0]]]          # first group already has first number
for (x, y), d in zip(pairs, diffs):
    if d < avg_diff:
        groups[-1].append(y)  # add to last group
    else:
        groups.append([y])    # start new group

Or if you prefer one-liners spanning three lines, this one might be for you:

groups = [functools.reduce(lambda A, b: A+(b[1],) if A else b, group, None) 
          for key, group in itertools.groupby(zip(nums, nums[1:]), 
                  key=lambda t: abs(t[0]-t[1]) < 18.3) if key]

Result for your example is this:

[[101, 107, 106],
 [199, 204, 205, 207],
 [306, 310, 312, 312, 314, 317, 318],
 [380, 377, 379, 382],
 [466, 469, 471, 472],
 [557, 559, 562, 566, 569]]

Of course, this breaks down if there are groups with vastly different group-internal differences, as in [1, 4, 2, 5, 1042, 1230, 920, 3, 2, 5]. If that is the case, you might try the relative difference of numbers instead, e.g. max(x,y)/min(x,y) instead of abs(x-y).

I took a stab at doing what I suggested in my comment. I think this will give a good solution to a more generalized problem, but I caution that I haven't thought about all edge cases or considered algorithmic complexity here.

import numpy as np

# function to initialize clusters
def init_clusters(x, num_elements_per_cluster=3):
    # initialize clusters by splitting into n groups
    x.sort()  # sort the list
    nclusters = len(x) / num_elements_per_cluster
    clusters = {i: {'values': []} for i in range(nclusters)}

    # assign to clusters (helps that list is sorted)
    for i in range(len(x)):
        index = min(i/num_elements_per_cluster, nclusters-1)
        clusters[index]['values'].append(x[i])

    # compute variance
    for index in clusters:
        clusters[index]['var'] = np.var(clusters[index]['values'])

    return clusters

def get_avg_var(clusters):
    total_var = 0.0
    denom = 0.0
    for index in clusters:
        total_var += clusters[index]['var'] * len(clusters[index]['values'])
        denom += len(clusters[index]['values'])
    return total_var / denom  # possible div by 0, but shouldn't happen

def assign_value_to_cluster(clusters, value):
    """
    add value to a cluster such that results in the lowest variance
    """
    new_cluster_vars = []
    indices = []
    for index in clusters:
        new_cluster_vars.append(np.var(clusters[index]['values'] + [value]))
        indices.append(index)

    index_min_new_cluster_var = indices[np.argmin(new_cluster_vars)]
    clusters[index_min_new_cluster_var]['values'].append(value)
    # update the variances
    clusters[index_min_new_cluster_var]['var'] = new_cluster_vars[index_min_new_cluster_var]


def purify(clusters):
    curr_var = get_avg_var(clusters)
    prev_var = curr_var*10
    max_iter = 1000
    iter_count = 0
    while(curr_var < prev_var):
        if iter_count > max_iter:
            break

        prev_var = curr_var

        # start with the cluster with the highest variance
        sorted_vars = sorted(
            [{'index': i, 'var': clusters[i]['var']} for i in clusters],
            key=lambda x: x['var'], 
            reverse=True
        )
        highest_var_index = sorted_vars[0]['index']

        vals = clusters[highest_var_index]['values']
        if len(vals) > 2:
            # find the element that when removed will minimize the variance of this cluster
            dropout_variance = [np.var([vals[j] for j in range(len(vals)) if j != i]) for i in range(len(vals))]
            index_to_drop = np.argmin(dropout_variance)
            value_to_reassign = clusters[highest_var_index]['values'].pop(index_to_drop)
            # update the variances
            clusters[highest_var_index]['var'] = dropout_variance[index_to_drop]
            assign_value_to_cluster(clusters, value_to_reassign)
        else:
            # break this cluster and assign values to others
            clusters.pop(highest_var_index)
            for val in vals:
                assign_value_to_cluster(clusters, val)

        curr_var = get_avg_var(clusters)
        print "after iter %04d: %04.2f" % (iter_count, curr_var) 
        iter_count += 1

    return clusters

Run the algorithm on the sample data OP provided:

# vector x of values that we want to cluster
x = [
    101, 107, 106, 199, 204, 205, 207, 306, 310, 312,
    312, 314, 317, 318, 380, 377, 379, 382, 466, 469,
    471, 472, 557, 559, 562, 566, 569
]

clusters = init_clusters(x)
final_clusters = purify(clusters)

# print values of the final clusters
[final_clusters[y]['values'] for y in final_clusters]

Output:

[[101, 106, 107],
 [204, 205, 207, 199],
 [306, 310],
 [312, 312, 314],
 [317, 318],
 [379, 380, 382, 377],
 [466, 469, 471, 472],
 [557, 559],
 [562, 566, 569]]

Edit: Fixed a bug in get_avg_var() and realized I was not updating the cluster variances. This is sensitive to the initialization, but it will generally provide reasonable clusters. That being said, you can define your own optimization parameter (rather than using average cluster variance as I did).

It seems from your posted code that a step occurs when abs(array[i]-array[i+1]) > 6. You can use this:

final = []
current = []   
arr = [101, 107, 106, 199, 204, 205, 207, 306, 310, 312, 312, 314, 317, 318, 380, 377, 379, 382, 466, 469, 471, 472, 557, 559, 562, 566, 569]
for i in range(len(arr)-1):
   if abs(arr[i] - arr[i+1]) > 6:
      current.append(arr[i])
      final.append(current)
      current = []
   else:
       current.append(arr[i])

Output:

[[101, 107, 106], [199, 204, 205, 207], [306, 310, 312, 312, 314, 317, 318], [380, 377, 379, 382], [466, 469, 471, 472]]
Related