Encuentra la sub matriz subnsa "más grande" en una gran matriz dispersa

Question

Dada una gran matriz dispersa (digamos 10k + por 1M +) Necesito encontrar un subconjunto, no necesariamente continuo, de las filas y columnas que forman una matriz densa (todas elementos distintos de cero). Quiero que esta matriz secundaria sea lo más grande posible (no la suma más grande, pero la mayor cantidad de elementos) dentro de algunas restricciones de relación de aspecto.

¿Existen soluciones exactas o aproximadas conocidas para este problema?

Un escaneo rápido en Google parece dar muchos resultados cercanos, pero no exactamente. ¿Qué términos debería estar buscando?

---

edición: sólo para aclarar; la matriz secundaria no necesita ser continua. De hecho, el orden de filas y columnas es completamente arbitrario, por lo que la adyacencia es completamente irrelevante.

---

un pensamiento basado en la idea de Chad Okere

1. Orden de las filas de mayor recuento para contar más pequeño (no es necesario, pero podrían ayudar perf)
2. Seleccionar dos filas que tienen un solapamiento "grande"
3. Agrega todas las otras filas que no va a reducir el solapamiento
4. registro que establece
5. añadir lo que reduce la fila ov ERLAP por el
6. Repita por lo menos en la posición # 3 hasta que el resultado se pone a pequeña
7. Empezar de nuevo en la posición # 2 con un par de partida diferente
8. Continuar hasta que se decida el resultado es lo suficientemente bueno

Answer 1

Supongo que quieres algo como esto. Tiene una matriz como

1100101 
1110101 
0100101 

¿Quiere las columnas 1,2,5,7 y las filas 1 y 2, ¿verdad? Esa submatriz serí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 que no sea 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á completamente distinta de cero.

Por lo tanto, para la matriz anterior, si agregó 1,1 y 2,2, tendría las filas 1,2 y las columnas 1,2 en su colección. Si intentaste agregar 3,7, causaría un problema porque 1,3 es cero. Entonces no podrías agregarlo. Podría agregar 2,5 y 2,7 ​​sin embargo. Creando la submatriz 4x2.

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

Entonces simplemente pare cuando no pueda encontrar nada más después de un tiempo.

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

Answer 2

EDITAR. Este no es el mismo que el problema de abajo .. Mi mal ...

Pero basado en el último comentario más abajo, se podría equivilent a lo siguiente:

1. Encuentra más lejos par de cero separados verticalmente puntos que no tienen punto cero entre ellos.
2. ¿Busca el par separado más horizontal de puntos cero que no tengan ceros entre ellos?

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

   Este problema exacto es discutido en una gema de un libro llamado "Programming Pearls" por Jon Bentley, y, según recuerdo, aunque hay una solución en una dimensión, no hay una respuesta fácil para la 2-d o variantes de dimensiones superiores ...

el problema 1 = D está, efectivamente, encontrar la mayor suma de un subconjunto contiguo de un conjunto de números:

recorrer los elementos, hacer el seguimiento de una ejecución total de un elemento previo específico, y el subtotal máximo visto hasta el momento (y el elemento inicial y final que lo generó) ...En cada elemento, si el subtotal maxrunning es mayor que el total máximo visto hasta ahora, el máximo visto hasta ahora y el endelemnte se restablecen ... Si el total máximo de ejecución es inferior a cero, el elemento inicial se restablece al elemento actual y el el total acumulado se restablece a cero ...

El problema 2-D surgió de un intento de generar un algoritmo de procesamiento de imagen visual, que intentaba encontrar, dentro de una secuencia de valores de brillo que representaban píxeles en una imagen de 2 colores , encuentre el área rectangular "más brillante" dentro de la imagen. es decir, encontrar 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, saqué mi copia de la segunda edición de este libro, y en ella, Jon Bentley dice "La versión en 2-D sigue sin resolverse a medida que se imprime esta edición. . "que fue en 1999.

Answer 3

¿Es esto un Netflix problem?

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

¿Tiene la intención de escribir la suya propia?

Tal vez el enfoque 1D para cada fila lo ayude. El algoritmo podría tener este aspecto:

1. bucle sobre cada fila
2. Encontrar el índice del primer elemento distinto de cero
3. Encontrar el índice de la fila de elementos no nulo con la mayor distancia entre no- cero columnas en cada fila y almacenar ambas.
4. Ordene las filas del tramo más grande al más pequeño entre las columnas distintas de cero.

En este punto empiezo a ser borroso (lo siento, no es un diseñador de algoritmos). Intentaba recorrer cada fila, alinear los índices del punto de partida y buscar la máxima cantidad posible de índices de columnas que no fueran cero.

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

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

Answer 4

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

Así, después de darse cuenta que esto es un problema NP-duro (por reducción a MAX-clique) decidí subir con una heurística que ha funcionado bien para mí hasta ahora:

dado una N x M matriz binaria/booleano, se encontró una gran submatriz densa:

Parte I: Generar submatrices candidatos razonables

1. Considere cada uno de los N filas ser un -dimensional vector binario M, v_i, donde i = 1 a N
2. calcular una matriz de distancia para los N vectores usando la distancia de Hamming
3. Usa el (Método Grupo par no ponderado con media aritmética) UPGMA algoritmo para vectores de racimo

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

Parte II: Partitura y candidatos rango submatrices

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

También tuve algunas consideraciones sobre el número mínimo de filas que se necesita para ser preservado de la matriz completa inicial, y me descartar cualquier submatrices candidatos que no cumplían este criterio antes de seleccionar una submatriz con valor máximo de D.