Генерация массива битовых векторов без повторяющихся столбцов

Question

У меня есть массив измерений [batch_size, input_dim], который должен быть заполнен только 0 или 1. Мне нужен элемент в каждом столбце, чтобы отличаться от остальных столбцов. Я выбрал следующий подход:

 train_data = np.zeros(shape=[batch, input_dim])
 num_of_ones = random.sample(range(input_dim + 1), batch)
 for k in range(batch):
     num_of_one = num_of_ones[k]
     for _ in range(num_of_one):
         train_data[k][np.random.randint(0, input_dim)] = 1

Хотя это гарантирует, что ни один элемент не повторяется (из-за того, что каждый столбец имеет различное число 1), все еще существует много комбинаций, которыеопущены. Например, когда num_of_one = 1, существует input_dim количество возможностей и так далее. Еще один недостаток этого метода заключается в том, что и batch_size, и input_dim должны быть одинаковыми (иначе random.sample выдает ошибку). Я не хочу перечислять все возможности, так как это займет целую вечность.

Есть ли какой-нибудь простой способ решить вышеуказанную проблему?

Answer 1

Ваша лучшая ставка - что-то вроде np.unpackbits в сочетании с питоном random.sample. random.sample будет производить выборку без замены без создания списка входных данных. Это означает, что вы можете использовать объект range над сколь угодно большими целыми числами без риска возникновения проблем, если размер выборки помещается в памяти. np.unpackbits затем преобразует целые числа в уникальные битовые последовательности. Эта идея является конкретной реализацией ответа @ ScottHunter .

batch_size = number_of_bits
input_size = number_of_samples

Сначала определите, сколько байтов вам нужно сгенерировать, и максимальное целое число, которое вам нужно покрыть. диапазон. Помните, что Python поддерживает произвольные целые числа точности, поэтому сходите с ума:

bytes_size = np.ceil(batch_size / 8)
max_int = 1<<batch_size

Теперь получите ваши уникальные образцы:

samples = random.sample(range(max_int), input_size)

Целые числа Python - полноценные объекты с to_bytes метод, который подготовит ваши семплы к np.unpackbits:

data = np.array([list(x.to_bytes(bytes_size, 'little')) for x in samples], dtype=np.uint8).T

Порядок байтов имеет значение, если batch_size не кратно 8: собирались урезать конечный массив до размера.

Теперь распакуйте, и все готово:

result = np.unpackbits(data, axis=0)[:batch, :]

Соберите все это в одну упаковку:

def random_bit_columns(batch_size, input_size):
    samples = random.sample(range(1 << batch_size), input_size)
    data = np.array([list(x.to_bytes(np.ceil(batch_size / 8), 'little')) for x in samples], dtype=np.uint8).T
    result = np.unpackbits(data, axis=0)[:batch, :]
    return result

Боюсь, я не вижувыход из использования понимания списка по количеству столбцов, если вы хотите получить выгоду от произвольных прецизионных целых чисел python.

Answer 2

Соблюдайте двоичное представление чисел от 0 до 7:

000
001
010
011
100
101
110
111

Каждая строка отличается! Итак, все, что нам нужно сделать, это преобразовать каждую строку в столбец. Например,

arr = [
    [0, 0, 0, 0, 1, 1, 1, 1],
    [0, 0, 1, 1, 0, 0, 1, 1],
    [0, 1, 0, 1, 0, 1, 0, 1],
]

---

Также обратите внимание, что мы использовали все уникальные возможности. Теперь, с 3 строками, мы не можем добавить 2**3 + 1-й столбец.

В общем, если cols > 2**rows, то мы не можем найти уникальное представление.

---

Вы можете сделать что-то вроде этого:

rows = 3
cols = 8

if 2**rows < cols:
    print('Not possible')

arr = [[None] * cols for _ in range(rows)]

for col_idx in range(cols):
    binary = bin(col_idx)[2:]
    binary = binary.zfill(rows)

    for row_idx in range(rows):
        arr[row_idx][col_idx] = int(binary[row_idx])

for row in arr:
    print(row)

Сложность времени: O(rows * cols)

Сложность пространства: O(rows * cols)

Answer 3

Почему у вас не работает

У вас есть проблема с этой строкой:

    for _ in range(num_of_one):
        train_data[k][np.random.randint(0, input_dim)] = 1

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

Решение

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

d = np.arange(input_dim)
random.shuffle(d)
train_data = (((d[:,None] & (1 << np.arange(batch)))) > 0).astype(float).T
print( train_data )

Answer 4

Вы можете выбрать набор различных чисел (смотрите itertools) в диапазоне от 0 до 2 ^ input_dim и использовать их двоичные представления, чтобы получить последовательность из 0 и 1 для каждого значения. Поскольку выбранные числа будут отличаться, их двоичные представления также будут отличаться.