- trovare il sottogruppo meno comune

a sono oggetti con più "categorie", b's, ad esempio a1 ha tre cestini b1, b2, b3. Il problema è, ridurre il numero di categorie (che possono crescere piuttosto grandi), in gruppi che si verificano sempre insieme. Una cosa "più grande sottoinsieme comune".- trovare il sottogruppo meno comune

Così, per esempio, dato il seguente set di dati:

a1{ b1,b2,b3 } 
a2{ b2,b3 } 
a3{ b1,b4 }

possiamo trovare che b2 e b3 viene sempre insieme ..

b23 = {b2,b3}

..e siamo in grado di ridurre la categoria impostata su this:

a1{ b1, b23 } 
a2{ b23 } 
a3{ b1,b4 }

Quindi, il mio problema è trovare un algoritmo per risolvere questo problema.

Ho iniziato a esaminare il problema Longest Common Sequence e potrebbe essere una soluzione. Ad esempio qualcosa come raggruppare ripetutamente categorie come questa b' = LCS(set_of_As) fino a quando tutte le categorie sono state attraversate. Tuttavia, questo non è completo. Devo limitare il dominio di input in qualche modo per renderlo possibile.

Mi manca qualcosa di ovvio? Qualche suggerimento su un dominio problematico a cui puoi indirizzarmi? Qualcuno riconosce un altro approccio a tale problema.

fonte

2012-10-23 Petter Nordlander

È molto probabile che sia corretto. LCS è sicuramente uno che avrebbe funzionato per il problema in questione. E la ** risposta più breve alla tua domanda principale ** è ** no non ti sei perso nulla di ovvio **. Sembra un bel problema però. –

In realtà, tutto ciò che devi fare è eseguire lo stesso algoritmo di pairing come hai fatto per ottenere la coppia b23. Ripeti fino a quando non ci sono cambiamenti nei set. Prima corsa attraverso le coppie, la seconda corsa farebbe coppie di coppie o coppie di una coppia e una singola. Quindi avresti terzine e quadruple ricorrenze coperte allora. – Ghlitch

Penso che tu possa migliorare le tue prestazioni dicendo che le tue categorie sono ordinate. Quindi, se disegni una matrice con tutte le categorie x tutti gli oggetti (matrice axb) tutto ciò che devi fare è trovare le colonne uguali. Lo so, è abbastanza grande, ma potrebbe essere più veloce :) –

Trasformate il vostro set di avere insiemi di b è che includono un portfolio:

b1 { a1, a3 } 
b2 { a1, a2 } 
b3 { a1, a2 } 
b4 { a3 }

Assicurarsi che il contenuto delle nuove serie B sono ordinati.

Ordina i tuoi gruppi b in base al loro contenuto.

Ogni due set adiacenti con gli stessi elementi sono b che si verificano nello stesso set.

fonte

2012-10-23 18:46:18

Un'ottimizzazione aggiuntiva sarebbe quella di ordinare i b set prima per lunghezza, poi per contenuto. – coproc

Grazie! non ci ho pensato. –

Penso che tu sia sulla strada giusta con la LCS se puoi imporre un ordinamento alle catagorie (altrimenti l'algoritmo LCS non può riconoscere {b3, b4} e {b4, b3}). Se è possibile imporre e ordinare e ordinarli, allora penso che qualcosa del genere potrebbe funzionare:


As = {a1={b1, b2},a2={b3},...} 
while ((newgroup = LCS(As)) != empty) { 
    for (a in As) { 
    replace newgroup in a 
    } 
}

fonte

2012-10-23 18:46:22

- trovare il sottogruppo meno comune

risposta

Problemi correlati