Линейная / сохраняющая порядок кластеризация в Python

Question

Я хочу сгруппировать числа в списке, основываясь на том, насколько «велики» числа по сравнению с их соседями, но я хочу делать это непрерывно и, если возможно, с помощью кластеризации. Для пояснения приведу пример:

Предположим, у вас есть список

lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2]

тогда, если у нас есть 3 группы, очевидно, как кластеризовать. Запуск алгоритма k-средних из sklearn (см. Код) подтверждает это. Но когда цифры в списке не такие «удобные», у меня возникают проблемы. Предположим, у вас есть список:

lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5]

Моя проблема теперь двоякая:

1. Мне нужна какая-то «линейная» кластеризация с сохранением порядка, которая учитывает порядок данных. Для приведенного выше списка алгоритм кластеризации должен дать мне желаемый результат вида

   lst = [0,0,1,1,1,1,1,1,2,2]
   

2. Если вы посмотрите на этот вывод выше, вы также увидите, что я хочу, чтобы значение 6,2 кластеризовалось во втором кластере, т.е. я хочу, чтобы алгоритм кластера рассматривал его как выброс, а не как совершенно новый кластер ,

3. РЕДАКТИРОВАТЬ Для пояснения я хочу иметь возможность указать количество кластеров в процессе линейной кластеризации, то есть «конечную сумму» кластеров.

Код:

import numpy as np
from sklearn.cluster import KMeans

lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2]

km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 2]: OK output

lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5]
km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 1 1 0 0]. Desired output: [0 0 1 1 1 1 1 1 2 2]

Answer 1

Как уже упоминалось, я думаю, что простой (ish) способ получить желаемые результаты состоит в том, чтобы просто использовать обычную кластеризацию K-средних, а затем изменить сгенерированный вывод по желанию.
Объяснение: Идея состоит в том, чтобы получить выходные данные K-средних, а затем выполнить итерацию по ним: отслеживание группы кластеров предыдущего элемента и текущей группы кластеров и управление новыми кластерами, созданными в условиях. Пояснения в коде.

import numpy as np
from sklearn.cluster import KMeans

lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2]

km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 2]: OK output

lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5]
km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 1 1 0 0]. Desired output: [0 0 1 1 1 1 1 1 2 2]


def linear_order_clustering(km_labels, outlier_tolerance = 1):
    '''Expects clustering outputs as an array/list'''
    prev_label = km_labels[0] #keeps track of last seen item's real cluster
    cluster = 0 #like a counter for our new linear clustering outputs
    result = [cluster] #initialize first entry
    for i, label in enumerate(km_labels[1:]):
        if prev_label == label: 
            #just written for clarity of control flow, 
            #do nothing special here
            pass 
        else: #current cluster label did not match previous label
            #check if previous cluster label reappears 
            #on the right of current cluster label position 
            #(aka current non-matching cluster is sandwiched 
            #within a reasonable tolerance)
            if (outlier_tolerance and 
                prev_label in km_labels[i + 1: i + 2 + outlier_tolerance]):                     label = prev_label #if so, overwrite current label
            else:
                cluster += 1 #its genuinely a new cluster
        result.append(cluster)
        prev_label = label
    return result

Обратите внимание, что я проверил это только с допуском для 1 выброса и не могу обещать, что он работает "как есть" во всех случаях. Это должно помочь вам начать.

Выход:

print(km.labels_)
result = linear_order_clustering(km.labels_)
print(result)
[1 1 0 0 0 2 0 0 1 1]
[0, 0, 1, 1, 1, 1, 1, 1, 2, 2]

Answer 2

Определить порог.

Если значения x [i] и x [i-1] слишком сильно различаются, начинается новый сегмент .

Для лучших результатов посмотрите на подходы KDE и CUSUM.

Не используйте кластеризацию. У него другая цель.

Answer 3

Я бы подошел к этому за пару проходов.Сначала у меня была бы первая функция / метод, чтобы выполнить анализ, чтобы определить центры кластеризации для каждой группы и вернуть массив этих центров.Затем я бы взял эти центры вместе со списком в другую функцию / метод, чтобы собрать список идентификаторов кластеров для каждого числа в списке.Затем я бы вернул отсортированный список.