Menu

Algoritmo di crescita del pattern frequente (FP) nel data mining

  • Principale
  • Altro
  • Algoritmo di crescita del pattern frequente (FP) nel data mining

frequent pattern growth algorithm data mining

Prova Il Nostro Strumento Per Eliminare I Problemi

Tutorial dettagliato sull'algoritmo di crescita dei pattern frequenti che rappresenta il database nella forma di un albero FP. Include il confronto tra Crescita FP e Apriori:

Algoritmo Apriori è stato spiegato in dettaglio nel nostro precedente tutorial. In questo tutorial, impareremo a conoscere la Crescita del Pattern Frequente: la Crescita FP è un metodo per estrarre i set di elementi frequenti.

come usare java per aprire un file jar

Come tutti sappiamo, Apriori è un algoritmo per il pattern mining frequente che si concentra sulla generazione di set di elementi e sulla scoperta del set di elementi più frequente. Riduce notevolmente la dimensione del set di elementi nel database, tuttavia Apriori ha anche i suoi difetti.

Leggi il nostro Intera serie di formazione sul data mining per una conoscenza completa del concetto.

Cosa imparerai:

Carenze dell'algoritmo Apriori

  1. L'utilizzo di Apriori richiede una generazione di set di elementi candidati. Questi set di elementi possono essere numerosi se il set di elementi nel database è enorme.
  2. Apriori necessita di più scansioni del database per verificare il supporto di ogni set di elementi generato e questo porta a costi elevati.

Queste carenze possono essere superate utilizzando l'algoritmo di crescita FP.

Algoritmo di crescita del pattern frequente

Questo algoritmo è un miglioramento del metodo Apriori. Viene generato un pattern frequente senza la necessità della generazione di candidati. L'algoritmo di crescita FP rappresenta il database sotto forma di un albero chiamato albero pattern frequente o albero FP.

Questa struttura ad albero manterrà l'associazione tra i set di elementi. Il database viene frammentato utilizzando un elemento frequente. Questa parte frammentata è chiamata 'frammento di pattern'. Vengono analizzati i set di elementi di questi modelli frammentati. Pertanto, con questo metodo, la ricerca di set di elementi frequenti viene ridotta in modo comparativo.

Albero FP

Frequent Pattern Tree è una struttura ad albero creata con i set di elementi iniziali del database. Lo scopo dell'albero FP è di estrarre il pattern più frequente. Ogni nodo dell'albero FP rappresenta un elemento dell'insieme di elementi.

Il nodo radice rappresenta null mentre i nodi inferiori rappresentano i set di elementi. L'associazione dei nodi con i nodi inferiori, ovvero gli insiemi di elementi con gli altri insiemi di elementi, viene mantenuta durante la formazione dell'albero.

Passaggi frequenti dell'algoritmo di pattern

Il metodo di crescita frequente del modello ci consente di trovare il modello frequente senza generazione di candidati.

Vediamo i passaggi seguiti per minare il pattern frequente utilizzando l'algoritmo di crescita del pattern frequente:

# 1) Il primo passo è eseguire la scansione del database per trovare le occorrenze dei set di elementi nel database. Questo passaggio è lo stesso del primo passaggio di Apriori. Il conteggio di 1 set di elementi nel database è chiamato conteggio supporto o frequenza di 1 set di elementi.

#Due) Il secondo passo è costruire l'albero FP. Per questo, crea la radice dell'albero. La radice è rappresentata da null.

i migliori siti per guardare anime soprannominate

# 3) Il passaggio successivo è eseguire nuovamente la scansione del database ed esaminare le transazioni. Esamina la prima transazione e scopri il set di elementi in essa contenuto. Il set di elementi con il conteggio massimo viene preso in alto, il set di elementi successivo con il conteggio inferiore e così via. Significa che il ramo dell'albero è costruito con insiemi di elementi di transazione in ordine decrescente di conteggio.

# 4) Viene esaminata la transazione successiva nel database. I set di elementi sono ordinati in ordine decrescente di conteggio. Se un set di elementi di questa transazione è già presente in un altro ramo (ad esempio nella prima transazione), questo ramo della transazione condividerà un prefisso comune alla radice.

Ciò significa che l'insieme di elementi comune è collegato al nuovo nodo di un altro insieme di elementi in questa transazione.

# 5) Inoltre, il conteggio dell'insieme di elementi viene incrementato man mano che si verifica nelle transazioni. Sia il nodo comune che il conteggio del nuovo nodo vengono aumentati di 1 man mano che vengono creati e collegati in base alle transazioni.

# 6) Il passaggio successivo consiste nel minare l'albero FP creato. Per questo, il nodo più basso viene esaminato per primo insieme ai collegamenti dei nodi più bassi. Il nodo più basso rappresenta la lunghezza del pattern di frequenza 1. Da questo, attraversare il percorso nell'albero FP. Questo percorso o percorsi sono chiamati base del modello condizionale.

La base del modello condizionale è un database secondario costituito da percorsi di prefisso nell'albero FP che si verificano con il nodo (suffisso) più basso.

# 7) Costruisci un albero FP condizionale, formato da un conteggio di set di elementi nel percorso. I set di elementi che soddisfano il supporto della soglia sono considerati nella struttura FP condizionale.

# 8) I pattern frequenti vengono generati dall'albero FP condizionale.

Esempio di algoritmo di crescita FP

Soglia di supporto = 50%, Fiducia = 60%

Tabella 1

TransazioneElenco di elementi
Utilizzo della memoria
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Soluzione:

Soglia di supporto = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Conteggio di ogni articolo

Tavolo 2

ArticoloContare
I14
I25
I34
I44
I5Due

2. Ordinare il set di elementi in ordine decrescente.

Tabella 3

ArticoloContare
I25
I14
I34
I44

3. Costruisci albero FP

quale certificazione di test del software è la migliore
  1. Considerando il nodo radice nullo.
  2. La prima scansione della Transazione T1: I1, I2, I3 contiene tre elementi {I1: 1}, {I2: 1}, {I3: 1}, dove I2 è collegato da bambino a root, I1 è collegato a I2 e I3 è collegato a I1.
  3. T2: I2, I3, I4 contiene I2, I3 e I4, dove I2 è collegato alla radice, I3 è collegato a I2 e I4 è collegato a I3. Ma questo ramo condividerebbe il nodo I2 tanto comune quanto è già utilizzato in T1.
  4. Aumenta il conteggio di I2 di 1 e I3 è collegato da bambino a I2, I4 è collegato da bambino a I3. Il conteggio è {I2: 2}, {I3: 1}, {I4: 1}.
  5. T3: I4, I5. Allo stesso modo, un nuovo ramo con I5 è collegato a I4 quando viene creato un bambino.
  6. T4: I1, I2, I4. La sequenza sarà I2, I1 e I4. I2 è già collegato al nodo radice, quindi verrà incrementato di 1. Allo stesso modo I1 verrà incrementato di 1 poiché è già collegato con I2 in T1, quindi {I2: 3}, {I1: 2}, {I4: 1}.
  7. T5: I1, I2, I3, I5. La sequenza sarà I2, I1, I3 e I5. Quindi {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
  8. T6: I1, I2, I3, I4. La sequenza sarà I2, I1, I3 e I4. Quindi {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

Albero FP

4. L'estrazione di FP-tree è riassunta di seguito:

  1. L'elemento del nodo più basso I5 non viene considerato in quanto non ha un conteggio minimo di supporto, quindi viene eliminato.
  2. Il prossimo nodo inferiore è I4. I4 si presenta in 2 rami, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Quindi considerando I4 come suffisso i percorsi del prefisso saranno {I2, I1, I3: 1}, {I2, I3: 1}. Questo costituisce la base del modello condizionale.
  3. La base del modello condizionale è considerata un database delle transazioni, viene costruito un albero FP. Questo conterrà {I2: 2, I3: 2}, I1 non è considerato in quanto non soddisfa il numero minimo di supporti.
  4. Questo percorso genererà tutte le combinazioni di pattern frequenti: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
  5. Per I3, il percorso del prefisso sarebbe: {I2, I1: 3}, {I2: 1}, questo genererà un albero FP a 2 nodi: {I2: 4, I1: 3} e vengono generati schemi frequenti: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
  6. Per I1, il percorso del prefisso sarebbe: {I2: 4} questo genererà un albero FP a nodo singolo: {I2: 4} e vengono generati schemi frequenti: {I2, I1: 4}.
ArticoloBase del modello condizionaleAlbero FP condizionaleSchemi frequenti generati
I4{I2, I1, I3: 1}, {I2, I3: 1}{I2: 2, I3: 2}{I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
I3{I2, I1: 3}, {I2: 1}{I2: 4, I1: 3}{I2, I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}
I1{I2: 4}{I2: 4}{I2, I1: 4}

Il diagramma riportato di seguito mostra l'albero FP condizionale associato al nodo condizionale I3.

albero FP condizionale associato al nodo condizionale I3

Vantaggi dell'algoritmo di crescita FP

  1. Questo algoritmo deve eseguire la scansione del database solo due volte rispetto ad Apriori che analizza le transazioni per ogni iterazione.
  2. L'abbinamento degli elementi non viene eseguito in questo algoritmo e questo lo rende più veloce.
  3. Il database è archiviato in una versione compatta in memoria.
  4. È efficiente e scalabile per il mining di pattern frequenti sia lunghi che brevi.

Svantaggi dell'algoritmo di crescita FP

  1. FP Tree è più ingombrante e difficile da costruire di Apriori.
  2. Potrebbe essere costoso.
  3. Quando il database è grande, l'algoritmo potrebbe non essere contenuto nella memoria condivisa.

Crescita FP vs Apriori

Crescita FPA priori
Generazione di pattern
La crescita FP genera pattern costruendo un albero FPApriori genera pattern abbinando gli elementi in singleton, coppie e terzine.
Candidate Generation
Non esiste una generazione di candidatiApriori utilizza la generazione di candidati
Processi
Il processo è più veloce rispetto ad Apriori. Il tempo di esecuzione del processo aumenta linearmente con l'aumento del numero di set di elementi.Il processo è relativamente più lento di FP Growth, il runtime aumenta esponenzialmente con l'aumento del numero di set di elementi
Viene salvata una versione compatta del databaseLe combinazioni di candidati vengono salvate in memoria

ECLAT

Il metodo precedente, Apriori e crescita FP, estrae i set di elementi frequenti utilizzando il formato dati orizzontale. ECLAT è un metodo per estrarre set di elementi frequenti utilizzando il formato dati verticale. Trasformerà i dati nel formato dati orizzontale nel formato verticale.

Per esempio,Utilizzo di Apriori e crescita FP:

TransazioneElenco di elementi
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

L'ECLAT avrà il formato della tabella come:

ArticoloSet di transazioni
I1{T1, T4, T5, T6}
I2{T1, T2, T4, T5, T6}
I3{T1, T2, T5, T6}
I4{T2, T3, T4, T5}
I5{T3, T5}

Questo metodo formerà 2 set di elementi, 3 set di elementi, k set di elementi nel formato dati verticale. Questo processo con k viene aumentato di 1 finché non vengono trovati set di elementi candidati. Alcune tecniche di ottimizzazione come diffset vengono utilizzate insieme ad Apriori.

Questo metodo ha un vantaggio rispetto a Apriori in quanto non richiede la scansione del database per trovare il supporto di k + 1 set di elementi. Questo perché il set di transazioni riporterà il conteggio delle occorrenze di ogni elemento nella transazione (supporto). Il collo di bottiglia arriva quando ci sono molte transazioni che richiedono un'enorme memoria e tempo di calcolo per intersecare gli insiemi.

Conclusione

L'algoritmo Apriori viene utilizzato per le regole di associazione mineraria. Funziona in base al principio, 'anche i sottoinsiemi non vuoti di insiemi di elementi frequenti devono essere frequenti'. Forma candidati k-itemset da (k-1) set di elementi ed esegue la scansione del database per trovare i set di elementi frequenti.

Frequent Pattern Growth Algorithm è il metodo per trovare pattern frequenti senza generazione di candidati. Costruisce un albero FP invece di utilizzare la strategia di generazione e test di Apriori. L'obiettivo dell'algoritmo di crescita FP è sulla frammentazione dei percorsi degli elementi e sull'estrazione di modelli frequenti.

Ci auguriamo che questi tutorial nella serie Data Mining abbiano arricchito le tue conoscenze sul Data Mining !!

Tutorial PREV | PRIMO Tutorial

Lettura consigliata

^