Tengo una matriz de dimensiones [batch_size, input_dim] que solo se debe completar con 0 o 1. Necesito que el elemento en cada columna sea distinto del resto de las columnas. He adoptado un enfoque como el siguiente:

 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

Aunque esto garantiza que no se repita ningún elemento (debido al hecho de que cada columna tiene un número diferente de 1 '), todavía hay muchas combinaciones que quedan fuera. Por ejemplo, cuando num_of_one = 1, hay input_dim número de posibilidades, etc. Otra desventaja del método que he seguido es que tanto batch_size como input_dim tienen que ser iguales (de lo contrario, random.sample arroja un error). No quiero enumerar todas las posibilidades, ya que eso tomaría una eternidad en completarse.

¿Hay alguna forma simple de lograr el problema mencionado anteriormente?

4
learner 8 oct. 2019 a las 14:59

4 respuestas

La mejor respuesta

Observe la representación binaria de los números desde 0 a 7:

000
001
010
011
100
101
110
111

¡Cada fila es diferente! Entonces, todo lo que tenemos que hacer es convertir cada fila a columna. p.ej.

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],
]

Además, observe que hemos utilizado todas las posibilidades únicas. Ahora, con 3 filas, no podemos agregar 2**3 + 1 th columna.

En general, si cols > 2**rows, entonces no podemos encontrar una representación única.


Puedes hacer algo como esto:

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)

Complejidad del tiempo: O(rows * cols)

Complejidad espacial: O(rows * cols)

1
Dipen Dadhaniya 9 oct. 2019 a las 15:02

¿Por qué el tuyo no funciona?

El tuyo tiene un problema con esta línea:

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

Debido a que selecciona filas aleatorias para establecerlas en 1, podría repetirlas, y no se garantiza que tenga el número correcto de unidades en cada columna, por lo tanto, puede tener duplicados. Básicamente, esto no es mejor que aleatorizar toda la matriz y esperar que no haya duplicados.

Solución

Puede lograr esto a través de la magia del conteo binario. Cada una de estas columnas es una representación binaria de números diferentes. Hay algunas limitaciones para esto, como lo haría con cualquier solución, donde es imposible tener todas las columnas únicas.

d = np.arange(input_dim)
random.shuffle(d)
train_data = (((d[:,None] & (1 << np.arange(batch)))) > 0).astype(float).T
print( train_data )
1
tituszban 8 oct. 2019 a las 12:31

Su mejor apuesta es algo como np.unpackbits combinado con random.sample de python. random.sample tomará muestras sin reemplazo sin crear una lista de la entrada. Esto significa que puede usar un objeto range sobre enteros arbitrariamente grandes sin ningún riesgo de problemas, siempre que el tamaño de la muestra quepa en la memoria. np.unpackbits luego convierte los enteros en secuencias de bits únicas. Esta idea es una implementación concreta de la respuesta de @ ScottHunter.

batch_size = number_of_bits
input_size = number_of_samples

Primero, decida cuántos bytes necesitará generar y el número entero máximo que necesitará para cubrir el rango. Recuerde, Python admite enteros de precisión arbitrarios, así que enloquezca:

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

Ahora obtenga sus muestras únicas:

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

Los enteros de Python son objetos completos con un to_bytes método que preparará sus muestras para np.unpackbits:

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

El orden de bytes importa si batch_size no es un múltiplo de 8: iban a recortar la matriz final a su tamaño.

Ahora desempaqueta y ya estás lista:

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

Poniendo todo junto en un solo paquete:

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

Me temo que no puedo ver una manera de usar una comprensión de la lista sobre el número de columnas si desea obtener el beneficio de los enteros de precisión arbitrarios de Python.

1
Mad Physicist 8 oct. 2019 a las 13:23

Puede seleccionar un conjunto de números distintos (mirar en itertools) entre 0 y 2 ^ input_dim, y usar sus representaciones binarias para obtener la secuencia de 0 y 1 para cada valor. Dado que los números seleccionados serían distintos, sus representaciones binarias también serían distintas.

1
George Rodgers 8 oct. 2019 a las 13:11
58285940