Определите кластеры, связанные дельтой слева и другой треугольник справа

Рассмотрим отсортированный массив a:

a = np.array([0, 2, 3, 4, 5, 10, 11, 11, 14, 19, 20, 20])

Если я задал левую и правую дельты,

delta_left, delta_right = 1, 1

Тогда я ожидаю, что кластеры будут назначены:

#   a = [ 0  .  2  3  4  5  .  .  .  . 10 11  .  . 14  .  .  .  . 19 20
#                                         11                         20
#
#                                     [10--|-12]                 [19--|-21]
#           [1--|--3]                 [10--|-12]                 [19--|-21]
#    [-1--|--1]   [3--|--5]         [9--|-11]                 [18--|-20]
#   +--+--|--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--|
#              [2--|--4]                       [13--|-15]
#
#         │    ╰──┬───╯                 ╰┬─╯        │              ╰┬─╯
#         │   cluster 2                Cluster 3    │           Cluster 5
#     Cluster 1                                 Cluster 4

ПРИМЕЧАНИЕ: Несмотря на то, что интервал [-1, 1] разделяет ребро с помощью [1, 3], ни один из интервалов не содержит смежную точку и поэтому не соединяет их соответствующие кластеры.

Предполагая, что назначения кластера были сохранены в массиве с именем clusters, я ожидаю, что результаты будут выглядеть так:

print(clusters)
[1 2 2 2 2 3 3 3 4 5 5 5]

Однако предположим, что я изменяю левую и правую дельтами на разные:

delta_left, delta_right = 2, 1

Это означает, что для значения x он должен быть объединен с любой другой точкой в ​​интервале [x - 2, x + 1]

#   a = [ 0  .  2  3  4  5  .  .  .  . 10 11  .  . 14  .  .  .  . 19 20
#                                         11                         20
#
#                                   [9-----|-12]              [18-----|-21]
#        [0-----|--3]               [9-----|-12]              [18-----|-21]
# [-2-----|--1][2-----|--5]      [8-----|-11]              [17-----|-20]
#   +--+--|--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--|
#           [1 ----|--4]                    [12-----|-15]
#
#         ╰─────┬─────╯                 ╰┬─╯        │              ╰┬─╯
#           cluster 1                Cluster 2      │           Cluster 4
#                                               Cluster 3

ПРИМЕЧАНИЕ.. Несмотря на то, что интервал [9, 12] разделяет ребро с помощью [12, 15], ни один из интервалов не содержит смежную точку и поэтому не объединяет их соответствующие кластеры.

Предполагая, что назначения кластера были сохранены в массиве с именем clusters, я ожидаю, что результаты будут выглядеть следующим образом:

print(clusters)
[1 1 1 1 1 2 2 2 3 4 4 4]

Ответы

Ответ 1

Мы будем использовать np.searchsorted и логику для поиска краев кластера.

Во-первых, давайте более подробно рассмотрим, что делает np.searchsorted:

Найти индексы в отсортированном массиве a так, чтобы, если соответствующие элементы из v были вставлены перед индексами, порядок a был бы сохранен.

Я сделаю np.searchsorted с a с помощью a - delta_left. Давайте посмотрим, что для delta_left = 1

# a =
# [ 0  2  3  4  5 10 11 11 14 19 20 20]
# 
# a - delta_left
# [-1  1  2  3  4  9 10 10 13 18 19 19]
  • -1 будет вставлен в позицию 0 для поддержания порядка
  • 1 будет вставлен в позицию 1 для поддержания порядка
  • 2 также будет вставлен в позицию 1, указывая, что 2 может находиться в том же кластере, что и 1
  • 3 будет вставлен в позицию 2, указав, что 3 может находиться в том же кластере, что и 2
  • и так далее и т.д.

Мы заметили, что только когда элемент с меньшей дельта будет вставлен в текущую позицию, мы рассмотрим запуск нового кластера.

Мы делаем это снова для правой стороны с разницей. Разница заключается в том, что по умолчанию, если группа элементов одинакова, np.searchsorted предполагает вставить в начало значений. Чтобы определить концы кластеров, мне захочется вставить после идентичных элементов. Поэтому я буду использовать paramater side='right'

Если 'left, указатель первого подходящего местоположения найден. Если "правильно", верните последний такой индекс. Если нет подходящего индекса, верните либо 0, либо N (где N - длина a).

Теперь логика. Кластер может начинаться только в том случае, если предыдущий кластер закончился, за исключением первого кластера. Затем мы рассмотрим сдвинутую версию результатов нашего второго np.searchsorted

Теперь определим нашу функцию

def delta_cluster(a, dleft, dright):
    # use to track whether searchsorted results are at correct positions
    rng = np.arange(len(a))

    edge_left = a.searchsorted(a - dleft)
    starts = edge_left == rng

    # we append 0 to shift
    edge_right = np.append(0, a.searchsorted(a + dright, side='right')[:-1])
    ends = edge_right == rng

    return (starts & ends).cumsum()

демонстрация

с левыми, правыми дельтами, равными 1 и 1

print(delta_cluster(a, 1, 1))

[1 2 2 2 2 3 3 3 4 5 5 5]

с левыми, правыми дельтами, равными 2 и 1

print(delta_cluster(a, 2, 1))

[1 1 1 1 1 2 2 2 3 4 4 4]

Дополнительный кредит
Что делать, если a не сортируется?
Я буду использовать информацию, полученную из этого сообщения

def delta_cluster(a, dleft, dright):

    s = a.argsort()

    size = s.size

    if size > 1000:
        y = np.empty(s.size, dtype=np.int64)
        y[s] = np.arange(s.size)
    else:
        y = s.argsort()

    a = a[s]

    rng = np.arange(len(a))

    edge_left = a.searchsorted(a - dleft)
    starts = edge_left == rng

    edge_right = np.append(0, a.searchsorted(a + dright, side='right')[:-1])
    ends = edge_right == rng

    return (starts & ends).cumsum()[y]

демонстрация

b = np.random.permutation(a)
print(b)

[14 10  3 11 20  0 19 20  4 11  5  2]

print(delta_cluster(a, 2, 1))

[1 1 1 1 1 2 2 2 3 4 4 4]

print(delta_cluster(b, 2, 1))

[3 2 1 2 4 1 4 4 1 2 1 1]

print(delta_cluster(b, 2, 1)[b.argsort()])

[1 1 1 1 1 2 2 2 3 4 4 4]