È FPGrowth ancora considerato “stato dell'arte” in frequenti modello di data mining?

Question

Per quanto ne so lo sviluppo di algoritmi per risolvere il problema pattern frequente Mining (FPM), la strada di miglioramenti hanno alcuni punti di controllo principale. In primo luogo, il Apriori algoritmo è stato proposto nel 1993, da Agrawal et al. , insieme con la formalizzazione del problema. L'algoritmo è stato in grado di strip-off alcuni set dai set 2^n - 1 (Powerset) utilizzando un reticolo per mantenere i dati. Un inconveniente del metodo è stata la necessità di ri-leggere il database per calcolare la frequenza di ogni set ampliato.

Più tardi, il 1997, Zaki et al. proposto l'algoritmo Eclat , che Inserito la frequenza risultante di ciascuna serie all'interno del reticolo . Ciò è stato fatto aggiungendo, ad ogni nodo del reticolo, il set di transazione-id che avevano i prodotti da radice al nodo di cui. Il contributo principale è che non si devono rileggere l'intero set di dati di conoscere la frequenza di ogni set, ma la memoria necessaria per mantenere tale struttura di dati costruito può superare la dimensione dell'insieme di dati stessa.

Nel 2000, Han et al proposto un algoritmo denominato FPGrowth , insieme a una struttura di dati di prefisso-albero di nome FPTree. L'algoritmo è stato in grado di fornire una notevole compressione dei dati, mentre anche ammettendo che itemset frequenti solo verrebbe ceduto (senza candidato generazione itemset). Ciò è stato fatto principalmente di classificare gli elementi di ogni transazione in ordine decrescente, in modo che gli articoli più frequenti sono quelli con meno ripetizioni nella struttura dati ad albero. Poiché la frequenza scende solo mentre attraversa l'albero in profondità, l'algoritmo è in grado di strip-off set di elementi non frequenti.

Modifica :

Per quanto ne so, questo può essere considerato un algoritmo di state-of-the-art, ma mi piacerebbe sapere su altre soluzioni proposte. Quali altri algoritmi per FPM sono considerati "state-of-the-art"? Qual è il intuizione / main-contributo di tali algoritmi?

è l'algoritmo FPGrowth ancora considerato "stato dell'arte" in frequenti modello di data mining? In caso contrario, l'algoritmo (s) può estrarre itemset frequenti da grandi quantità di dati in modo più efficiente?

Answer 1

Stato dell'arte come in:? Utilizzato nella pratica o lavorato in teoria

APRIORI viene utilizzato in tutto il mondo, tranne che per lo sviluppo di nuovi algoritmi di itemset frequenti. E 'facile da implementare e facile da riutilizzare in molto diversi domini. Troverete centinaia di Apriori implementazioni di varia qualità. Ed è facile da ottenere APRIORI sbagliato, in realtà.

FPgrowth è molto più difficile da realizzare, ma anche molto più interessante. Quindi, da un punto di vista accademico, cerca a tutti di migliorare FPgrowth -. Ottenere il lavoro sulla base di APRIORI accettato sarà molto difficile ormai

Se si dispone di un'implementazione buono, ogni algoritmo ha è buono ed è situazioni negative a mio parere. Una buona implementazione APRIORI sarà solo necessità di eseguire la scansione del database di k volte per trovare tutti i set di elementi frequenti di lunghezza k . In particolare se i vostri attacchi di dati nella memoria principale questo è a buon mercato. Che cosa può uccidere APRIORI è troppi frequenti 2-set di elementi (in particolare quando non utilizzano un trie e tecniche di accelerazione simili, ecc). Funziona meglio su grandi quantità di dati con un basso numero di set di elementi frequenti.

Eclat funziona sulle colonne; ma ha bisogno di leggere ogni colonna molto più spesso. V'è un certo lavoro da diffsets per ridurre questo lavoro. Se i dati non entra nella memoria principale, Eclat soffre probabilmente più di Apriori. Andando profondità prima, sarà anche in grado di restituire un primo risultato interessante molto prima di Apriori, ed è possibile utilizzare questi risultati per regolare i parametri; quindi è necessario meno iterazioni di trovare buoni parametri. Ma in base alla progettazione, non può exploit potatura come ordinatamente come fece Apriori.

FPGrowth comprime l'insieme di dati in l'albero. Questo funziona meglio quando si hanno un sacco di record duplicati. Probabilmente si può trarre di abbastanza alcune guadagni per Apriori e Eclat anche se si può presort i dati ed i duplicati di unione in vettori pesati. FPGrowth fa ad un livello estremo. Lo svantaggio è che l'attuazione è molto più difficile; e una volta che questo albero non è adatta alla memoria di più diventa un pasticcio da implementare.

Per quanto riguarda i risultati delle prestazioni e parametri di riferimento - non si fidano di loro. Ci sono così tante cose da implementare in modo non corretto. Prova 10 implementazioni diverse, e si ottiene 10 risultati molto diversi di prestazioni. In particolare per APRIORI, ho l'impressione che la maggior parte delle implementazioni sono rotti nel senso di perdere alcuni dei principali contributi di APRIORI ... e di quelli che hanno da queste parti a destra, la qualità di ottimizzazioni varia molto.

In realtà ci sono anche i documenti su come implementare in modo efficiente questi algoritmi:

implementazioni efficienti di Apriori e Eclat
. Christian Borgelt
Laboratorio di elemento frequente Set Mining Implementazioni (FIMI 2003, Melbourne, FL, Stati Uniti d'America).

Si consiglia inoltre di leggere queste indagini su questo dominio:

• Goethals, Bart. "Indagine sulle frequenti modello di data mining." Univ. di Helsinki (2003).

• Ferenc Bodon, un sondaggio sul frequente itemset Mining, Technical Report, Budapest University of Technology e economica 2006,

• Articolo frequente Set Mining
  Christian Borgelt
  Wiley Interdisciplinary Reviews: Data Mining e di Knowledge Discovery 2 (6): 437-456. 2012

Answer 2

La maggior parte del recente modello di frequente si avvicina a quello che ho visto in letteratura si basano sull'ottimizzazione FPGrowth. Devo ammettere, non ho visto molti sviluppi all'interno della letteratura in FPM in molti anni.

Questo wikibook evidenzia molte delle varianti su FPGrowth che sono fuori lì.