Как найти группы смежных истинных значений в двоичном тензоре?

Question

Я только начал с TensorFlow (1.13) и столкнулся с проблемой. У меня есть бинарный трехмерный тензор, выходящий из нейронной сети. В этом тензоре есть «группы» истинных значений. Это где смежные индексы в двоичном тензоре имеют истинные значения. Я хочу извлечь несколько групп, в которых каждая группа хранит индексы, где истинные значения являются смежными.

Например, двумерный случай (в результате получается две группы):

[[ 0 1 1 0 0 ]
 [ 0 1 0 0 0 ]
 [ 0 0 0 0 0 ]
 [ 0 0 0 0 1 ]
 [ 0 1 1 1 0 ]]

Я стремлюсь к следующемувыходные данные:

[[[0, 1], [0, 2], [1, 1]],
 [[3, 5], [4, 1], [4, 2], [4, 3]]]

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

[[0.33, 1.33],
 [3.75, 2.5]]

Я попытался создать ребра между узламикоторые находятся на определенном расстоянии. Что дает мне смежные индексы для данного истинного значения. Для истинного значения в [0, 1] это приводит к [0, 2] и [1, 1]. У меня есть список со всеми этими ребрами, но я не могу сгруппировать их соответственно для целевого вывода.

Что-то вроде кластеризации k-средних может работать, но для этого мне нужно знать количество истинно значимых групп, которое неизвестно.

Вот реализация numpy коллекциисмежные индексы в группы.

import numpy as np

arr = np.array([
    [0, 1],
    [0, 4],
    [1, 4],
    [1, 20],
    [3, 6],
    [6, 9],
    [9, 12],
    [5, 7],
])

# Goal [[0, 1, 4], [3, 6, 9, 12], [5, 7]]

group = []

def search(value, arr):

    nodes, = np.where(arr[:, 0] == value[-1])
    res = arr[nodes]

    if res.size != 0:
        sequence = np.concatenate((value, res), axis=None)
        sequence = np.unique(sequence)
        val = search(sequence, llist)

    return val


while True:

    # search iteratively:
    arr = np.reshape(arr, (-1, 2))
    next_node = search(arr[0], arr)

    group.append(next_node)

    # prevent searches to be restarted and give half results: remove them from array
    mask = np.isin(arr, next_node, invert=True)
    arr = arr[mask]
    if arr.size == 0:
        break

print(group)

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

Answer 1

Это была некоторая работа, но мне удалось реализовать базовый алгоритм затопления с парой tf.while_loop. Идея проста, просто взять элемент, найти соседние элементы, затем сделать то же самое для тех, пока их больше нет, и вы называете это кластером, затем продолжаете с другим неназначенным элементом, и так далее, пока у вас нет никакихбольше элементов. Поскольку тензоры должны иметь компактные формы, вместо использования чего-то вроде рваного тензора я просто форматирую выходные данные как два тензора, один с координатами, а другой с индексом кластера, которому принадлежит (выможет, возможно, изменить формат оттуда, если хотите). Код определенно не будет быстрым, циклы TensorFlow обычно нет, и алгоритм делает квадратичное сравнение на каждой внутренней итерации, но, по крайней мере, он должен дать вам ответ.

В любом случае, вот код:

import tensorflow as tf

def find_clusters(arr):
    # Find coordinates of ones
    coords = tf.where(tf.dtypes.cast(arr, tf.bool))
    s = tf.shape(coords)
    d = coords.shape[1]
    cluster_idx = tf.TensorArray(tf.int32, 0, element_shape=[None],
                                 dynamic_size=True, infer_shape=False)
    cluster_coords = tf.TensorArray(coords.dtype, 0, element_shape=[None, d],
                                    dynamic_size=True, infer_shape=False)
    i = tf.constant(0, tf.int32)
    i_step = tf.constant(0, tf.int32)
    _, _, _, cluster_idx, cluster_coords = tf.while_loop(
        # While there are unassigned coordinates
        lambda i, i_step, coords, cluster_idx, cluster_coords: tf.shape(coords)[0] > 0,
        # Find new cluster
        next_cluster,
        [i, i_step, coords, cluster_idx, cluster_coords],
        parallel_iterations=1,
        shape_invariants=[i.shape, i_step.shape, tf.TensorShape([None, d]),
                          tf.TensorShape(None), tf.TensorShape(None)])
    return cluster_idx.concat(), cluster_coords.concat()

def next_cluster(i, i_step, coords, cluster_idx, cluster_coords):
    current = coords[:1]
    coords = coords[1:]
    cluster_idx = cluster_idx.write(i_step, [i])
    cluster_coords = cluster_coords.write(i_step, current)
    i_step += 1
    s = tf.TensorShape([None, coords.shape[1]])
    i, i_step, coords, _, cluster_idx, cluster_coords = tf.while_loop(
        # While new elements are added to the cluster
        (lambda i, i_step, coords, current, cluster_idx, cluster_coords:
             tf.not_equal(tf.shape(current)[0], 0)),
        # Find new neighbors
        find_neighbors,
        [i, i_step, coords, current, cluster_idx, cluster_coords],
        parallel_iterations=1,
        shape_invariants=[i.shape, i_step.shape, s, s,
                          tf.TensorShape(None), tf.TensorShape(None)])
    return i + 1, i_step, coords, cluster_idx, cluster_coords

def find_neighbors(i, i_step, coords, current, cluster_idx, cluster_coords):
    # Find coordinates at distance exactly one of previous coordinates
    dist = tf.reduce_sum(tf.abs(tf.expand_dims(current, 1) - coords), axis=-1)
    is_close = tf.reduce_any(tf.equal(dist, 1), axis=0)
    # Split between neighbors and the rest
    coords, current = tf.dynamic_partition(coords, tf.dtypes.cast(is_close, tf.int32), 2)
    # Write newly found cluster coordinates
    cluster_idx = cluster_idx.write(i_step, tf.fill([tf.shape(current)[0]], i))
    cluster_coords = cluster_coords.write(i_step, current)
    i_step += 1
    return i, i_step, coords, current, cluster_idx, cluster_coords

# Test
with tf.Graph().as_default(), tf.Session() as sess:
    data = tf.constant([[0, 1, 1, 0, 0],
                        [0, 1, 0, 0, 0],
                        [0, 0, 0, 0, 0],
                        [0, 0, 0, 0, 1],
                        [0, 1, 1, 1, 0]])
    cluster_idx, cluster_coords = find_clusters(data)
    for cluster, coord in zip(*sess.run((cluster_idx, cluster_coords))):
        print(f'{coord}: cluster {cluster}')

Вывод:

[0 1]: cluster 0
[0 2]: cluster 0
[1 1]: cluster 0
[3 4]: cluster 1
[4 1]: cluster 2
[4 2]: cluster 2
[4 3]: cluster 2

РЕДАКТИРОВАТЬ:

Если вы хотите, чтобы вывод был рваным тензором, вот простая функция для преобразования предыдущего форматав это:

import tensorflow as tf

def clusters_to_ragged(cluster_idx, cluster_coords):
    d = cluster_idx[1:] - cluster_idx[:-1]
    s = tf.where(d > 0)[:, 0] + 1
    starts = tf.concat([[0], s], axis=0)
    limits = tf.concat([s, [tf.shape(d)[0] + 1]], axis=0)
    r = tf.ragged.range(starts, limits)
    return tf.gather(cluster_coords, r)

# Test
with tf.Graph().as_default(), tf.Session() as sess:
    # Result in previous format
    cluster_idx = tf.constant([0, 0, 0, 1, 2, 2, 2])
    cluster_coords = tf.constant([[0, 1],
                                  [0, 2],
                                  [1, 1],
                                  [3, 4],
                                  [4, 1],
                                  [4, 2],
                                  [4, 3]])
    ragged = clusters_to_ragged(cluster_idx, cluster_coords)
    print(*sess.run(ragged).to_list(), sep='\n')
    # [[0, 1], [0, 2], [1, 1]]
    # [[3, 4]]
    # [[4, 1], [4, 2], [4, 3]]