Trova & # 8220; più grande & # 8221; matrice secondaria densa in una matrice sparsa grande

Question

Data una matrice sparsa di grandi dimensioni (diciamo 10k + per 1M +) ho bisogno di trovare un sottoinsieme, non necessariamente continuo, delle righe e delle colonne che formano una matrice densa (tutti gli elementi diversi da zero). Voglio che questa sotto matrice sia il più grande possibile (non la somma più grande, ma il maggior numero di elementi) entro alcuni limiti delle proporzioni.

Esistono soluzioni esatte o aproxamate note a questo problema?

Una rapida scansione su Google sembra dare molti risultati vicini ma non esattamente. Quali termini dovrei cercare?

---

modifica: Giusto per chiarire; la matrice secondaria non deve essere continua . In effetti l'ordine delle righe e delle colonne è completamente arbitrario, quindi l'adiacenza è completamente irrilevante.

---

Un pensiero basato sull'idea di Chad Okere

1. Ordina le righe dal conteggio più grande al conteggio più piccolo (non necessario ma potrebbe aiutare perf)
2. Seleziona due righe che hanno un " large " sovrapposizione
3. Aggiungi tutte le altre righe che non ridurranno la sovrapposizione
4. Registra quel set
5. Aggiungi qualunque riga riduce la sovrapposizione del minimo
6. Ripeti al punto 3 fino a quando il risultato non diventa piccolo
7. Ricomincia da # 2 con una coppia iniziale diversa
8. Continua finché non decidi che il risultato è abbastanza buono

Answer 1

Presumo che tu voglia qualcosa del genere. Hai una matrice come

1100101
1110101
0100101

Vuoi le colonne 1,2,5,7 e le righe 1 e 2, giusto? Quel sottomatrix sarebbe 4x2 con 8 elementi. Oppure potresti andare con le colonne 1,5,7 con le righe 1,2,3 che sarebbero una matrice 3x3.

Se si desidera un metodo "approssimativo", è possibile iniziare con un singolo elemento diverso da zero, quindi continuare a trovare un altro elemento diverso da zero e aggiungerlo all'elenco di righe e colonne. Ad un certo punto ti imbatterai in un elemento diverso da zero che, se le righe e le colonne fossero aggiunte alla tua raccolta, la tua raccolta non sarebbe più completamente diversa da zero.

Quindi, per la matrice sopra, se aggiungi 1,1 e 2,2 avresti righe 1,2 e colonne 1,2 nella tua raccolta. Se si provasse ad aggiungere 3,7 ciò causerebbe un problema perché 1,3 è zero. Quindi non puoi aggiungerlo. Puoi aggiungere 2,5 e 2,7 però. Creazione della matrice secondaria 4x2.

Dovresti praticamente iterare fino a quando non trovi più nuove righe e colonne da aggiungere. Anche per te sarebbe un minimo locale. È possibile memorizzare il risultato e ricominciare con un altro punto di partenza (forse uno che non si adattava alla soluzione corrente).

Quindi fermati quando non riesci più a trovare dopo un po '.

Ciò, ovviamente, richiederebbe molto tempo, ma non so se sarai in grado di farlo più rapidamente.

Answer 2

È un Problema di Netflix ?

MATLAB o alcune altre librerie di matrici sparse potrebbero avere dei modi per gestirlo.

Il tuo intento è scrivere il tuo?

Forse l'approccio 1D per ogni riga ti potrebbe aiutare. L'algoritmo potrebbe apparire così:

1. Scorri ogni riga
2. Trova l'indice del primo elemento diverso da zero
3. Trova l'indice dell'elemento di riga diverso da zero con l'intervallo più grande tra le colonne diverse da zero in ogni riga e memorizza entrambi.
4. Ordina le righe dalla più grande alla più piccola tra colonne diverse da zero.

A questo punto inizio a diventare confuso (scusate, non un progettista di algoritmi). Proverei a fare il ciclo su ogni riga, allineando gli indici del punto iniziale, cercando la corsa massima diversa da zero degli indici di colonna che potrei.

Non si specifica se la matrice densa deve essere quadrata o meno. Presumo di no.

Non so quanto sia efficiente o quale sarebbe il suo comportamento Big-O. Ma è un metodo di forza bruta per cominciare.

Answer 3

EDIT. Questo NON è lo stesso del problema qui sotto ... Mio cattivo ...

Ma in base all'ultimo commento di seguito, potrebbe essere equivalente al seguente:

1. Trova la coppia più lontana di punti zero separati verticalmente che non hanno punti zero tra di loro.
2. Trova la coppia di punti zero separata più in orizzontale che non ha zeri tra di loro?

3. Quindi la regione orizzontale che stai cercando è il rettangolo che si adatta tra queste due coppie di punti?

   Questo esatto problema è discusso in una gemma di un libro intitolato "Perle di programmazione" di Jon Bentley e, come ricordo, anche se esiste una soluzione in una dimensione, non esiste una risposta facile per le varianti bidimensionali o di dimensioni superiori ...

Il problema 1 = D è, effettivamente, trovare la somma più grande di un sottoinsieme contiguo di un insieme di numeri:

iterare attraverso gli elementi, tenendo traccia di un totale parziale di uno specifico elemento precedente e il totale parziale totale visto finora (e l'elemnt iniziale e finale che lo ha generato) ... Ad ogni elemento, se il totale parziale massimo è maggiore del totale massimo visto finora, il massimo visto finora e endelemnt vengono ripristinati ... Se il totale corrente massimo scende al di sotto di zero, l'elemento iniziale viene ripristinato sull'elemento corrente e il totale corrente viene ripristinato a zero ...

Il problema 2-D è venuto dal tentativo di generare un algoritmo di elaborazione di immagini visive, che stava cercando di trovare, all'interno di un flusso di valori di luminosità che rappresentano i pixel in un'immagine a 2 colori, trovare il "più luminoso" area rettangolare all'interno dell'immagine. vale a dire, trova la sotto-matrice 2D contenuta con la somma più alta di valori di luminosità, dove "Luminosità" è stato misurato dalla differenza tra il valore di luminosità del pixel e la luminosità media complessiva dell'intera immagine (quindi molti elementi avevano valori negativi)

EDIT: per cercare la soluzione 1-D ho raccolto la mia copia della 2a edizione di questo libro, e in esso, Jon Bentley dice " La versione 2-D rimane irrisolta mentre questa edizione va in stampa .. . " che era nel 1999.

Answer 4

So che non ci stai più lavorando, ma ho pensato che qualcuno potesse avere la mia stessa domanda in futuro.

Quindi, dopo aver realizzato che questo è un problema NP-difficile (riducendo a MAX-CLIQUE) ho deciso di inventare un euristico che finora ha funzionato bene per me:

Data una N x M matrice binaria / booleana, trova una grande sottostruttura densa:

Parte I : genera ragionevoli candidati candidati

1. Considera ciascuna delle N come un vettore binario tridimensionale M , v_i , dove i = Da 1 a N
2. Calcola una matrice di distanza per i vettori N usando la distanza di Hamming
3. Utilizza l'algoritmo UPGMA (metodo del gruppo di coppie non ponderate con media aritmetica) per raggruppare i vettori

Inizialmente, ciascuno dei vettori v_i è un cluster singleton. Il passaggio 3 sopra (raggruppamento) indica l'ordine in cui i vettori devono essere combinati in sottogruppi. Pertanto, ogni nodo interno nella struttura gerarchica del clustering è una sottomessa candidata.

Parte II : segna e classifica le matrici secondarie candidate

1. Per ogni sottotrix, calcola D , il numero di elementi nel sottoinsieme denso dei vettori per la sottotrix eliminando qualsiasi colonna con uno o più zeri.
2. Seleziona la matrice secondaria che massimizza D

Avevo anche preso alcune considerazioni riguardo al numero minimo di righe che dovevano essere preservate dalla matrice completa iniziale e avrei scartato tutte le sotto-matrici candidate che non soddisfacevano questi criteri prima di selezionare una sotto-matrice con max D valore.