Encuentra el & # 8220; más grande & # 8221; submatriz densa en una gran matriz dispersa

Question

Dada una matriz dispersa grande (digamos 10k + por 1M +) necesito encontrar un subconjunto, no necesariamente continuo, de las filas y columnas que forman una matriz densa (todos los elementos distintos de cero). Quiero que esta submatriz sea lo más grande posible (no la suma más grande, sino el mayor número de elementos) dentro de algunas restricciones de relación de aspecto.

¿Hay alguna solución exacta o aproximada conocida para este problema?

Un escaneo rápido en Google parece dar muchos resultados cercanos pero no exactamente. ¿Qué términos debo buscar?

---

editar: solo para aclarar; la submatriz no necesita ser continua . De hecho, el orden de las filas y columnas es completamente arbitrario, por lo que la adyacencia es completamente irrelevante.

---

Un pensamiento basado en la idea de Chad Okere

1. Ordene las filas desde el recuento más grande al más pequeño (no es necesario, pero podría ayudar a perf)
2. Seleccione dos filas que tengan un " grande " superposición
3. Agregue todas las demás filas que no reducirán la superposición
4. Grabar ese conjunto
5. Agregar cualquier fila reduce al mínimo la superposición
6. Repita en el n. ° 3 hasta que el resultado sea pequeño
7. Comience de nuevo en el n. ° 2 con un par inicial diferente
8. Continúa hasta que decidas que el resultado es lo suficientemente bueno

Answer 1

Asumo que quieres algo como esto. Tienes una matriz como

1100101
1110101
0100101

¿Quieres columnas 1,2,5,7 y filas 1 y 2, verdad? Esa submatriz tendría 4x2 con 8 elementos. O podría ir con las columnas 1,5,7 con las filas 1,2,3 que serían una matriz de 3x3.

Si desea un método 'aproximado', puede comenzar con un único elemento distinto de cero, luego buscar otro elemento distinto de cero y agregarlo a su lista de filas y columnas. En algún momento, se encontrará con un elemento distinto de cero que, si se agregaron filas y columnas a su colección, su colección ya no sería completamente distinta de cero.

Entonces, para la matriz anterior, si agregaras 1,1 y 2,2 tendrías filas 1,2 y 1,2 en tu colección. Si trató de agregar 3,7, causaría un problema porque 1,3 es cero. Entonces no pudiste agregarlo. Sin embargo, puede agregar 2,5 y 2,7. Creando la submatriz 4x2.

Básicamente, iteraría hasta que no pueda encontrar más filas y columnas nuevas para agregar. Eso también te daría un mínimo local. Podría almacenar el resultado y comenzar de nuevo con otro punto de inicio (tal vez uno que no encaja en su solución actual).

Luego, deténgase cuando no pueda encontrar más después de un tiempo.

Eso, obviamente, llevaría mucho tiempo, pero no sé si podrá hacerlo más rápido.

Answer 2

¿Es este un problema de Netflix ?

MATLAB o algunas otras bibliotecas de matriz dispersas pueden tener formas de manejarlo.

¿Tu intención es escribir la tuya?

Quizás el enfoque 1D para cada fila te ayudaría. El algoritmo podría verse así:

1. Recorre cada fila
2. Encuentra el índice del primer elemento distinto de cero
3. Encuentre el índice del elemento de fila distinto de cero con el mayor intervalo entre columnas distintas de cero en cada fila y almacene ambos.
4. Ordene las filas de mayor a menor envergadura entre columnas distintas de cero.

En este punto empiezo a ponerme borroso (lo siento, no soy un diseñador de algoritmos). Intentaba recorrer cada fila, alineando los índices del punto de partida, buscando la ejecución máxima de índices de columnas que no sea cero que pudiera.

No especifica si la matriz densa debe ser cuadrada o no. Asumiré que no.

No sé qué tan eficiente es esto o cuál sería su comportamiento Big-O. Pero para empezar es un método de fuerza bruta.

Answer 3

EDITAR. Esto NO es lo mismo que el siguiente problema ... Mi problema ...

Pero según el último comentario a continuación, podría ser equivalente a lo siguiente:

1. Encuentra el par de puntos cero más alejado verticalmente que no tienen punto cero entre ellos.
2. ¿Encuentra el par de puntos cero más alejado horizontalmente que no tienen ceros entre ellos?

3. ¿Entonces la región horizontal que estás buscando es el rectángulo que se ajusta entre estos dos pares de puntos?

   Este problema exacto se discute en una joya de un libro llamado "Perlas de programación". por Jon Bentley, y, según recuerdo, aunque hay una solución en una dimensión, no hay una respuesta fácil para las variantes bidimensionales o de dimensiones superiores ...

El problema 1 = D es, efectivamente, encontrar la suma más grande de un subconjunto contiguo de un conjunto de números:

iterar a través de los elementos, realizar un seguimiento de un total acumulado de un elemento anterior específico, y el subtotal máximo visto hasta ahora (y el elemento de inicio y fin que lo generó) ... En cada elemento, si el subtotal maxrunning es mayor que el total máximo visto hasta el momento, el máximo visto hasta ahora y el endeble se restablecen ... Si el total máximo corriente es inferior a cero, el elemento inicial se restablece al elemento actual y el total acumulado se restablece a cero ...

El problema 2D surgió de un intento de generar un algoritmo de procesamiento de imagen visual, que intentaba encontrar, dentro de un flujo de valores de brillo que representaran píxeles en una imagen de 2 colores, encontrar el "más brillante". Área rectangular dentro de la imagen. es decir, encuentre la submatriz 2-D contenida con la suma más alta de valores de brillo, donde " Brillo " se midió por la diferencia entre el valor de brillo del píxel y el brillo promedio general de toda la imagen (muchos elementos tenían valores negativos)

EDITAR: Para buscar la solución 1-D, dragué mi copia de la segunda edición de este libro, y en él, Jon Bentley dice "La versión 2-D sigue sin resolverse a medida que esta edición se imprime ... . " que fue en 1999.

Answer 4

Sé que ya no estás trabajando en esto, pero pensé que alguien podría tener la misma pregunta que yo en el futuro.

Entonces, después de darme cuenta de que este es un problema NP-difícil (por reducción a MAX-CLIQUE) decidí crear una heurística que me ha funcionado bien hasta ahora:

Dada una N x M matriz binaria / booleana, encuentre una gran submatriz densa:

Parte I : Generar submatrices de candidatos razonables

1. Considere que cada una de las filas N es un vector binario tridimensional M , v_i , donde i = 1 a N
2. Calcule una matriz de distancia para los vectores N utilizando la distancia de Hamming
3. Use el algoritmo UPGMA (Método de grupo de pares no ponderados con media aritmética) para agrupar vectores

Inicialmente, cada uno de los vectores v_i es un clúster singleton. El paso 3 anterior (agrupamiento) ordena que los vectores se combinen en submatrices. Por lo tanto, cada nodo interno en el árbol de agrupamiento jerárquico es una submatriz candidata.

Parte II : Puntuación y clasificación de submatrices candidatas

1. Para cada submatriz, calcule D , el número de elementos en el subconjunto denso de los vectores para la submatriz eliminando cualquier columna con uno o más ceros.
2. Seleccione la submatriz que maximiza D

También tuve algunas consideraciones con respecto al número mínimo de filas que debían preservarse de la matriz completa inicial, y descartaría cualquier submatriz candidata que no cumpliera con este criterio antes de seleccionar una submatriz con un máximo de D valor.