apriori algorithm data mining
Esercitazione approfondita sull'algoritmo Apriori per scoprire i set di elementi frequenti nel data mining. Questo tutorial spiega i passaggi in Apriori e come funziona:
In questo Serie di tutorial sul data mining , abbiamo esaminato il Algoritmo dell'albero decisionale nel nostro precedente tutorial.
Esistono diversi metodi per il data mining come associazione, correlazione, classificazione e clustering.
differenza tra qa e qc nei test del software
Questo tutorial si concentra principalmente sul mining utilizzando regole di associazione. In base alle regole di associazione, identifichiamo l'insieme di elementi o attributi che ricorrono insieme in una tabella.
Cosa imparerai:
- Cos'è un Itemset?
- Perché l'estrazione di oggetti frequenti?
- Metodi per migliorare l'efficienza Apriori
- Applicazioni dell'algoritmo Apriori
- Conclusione
Cos'è un Itemset?
Un insieme di elementi viene chiamato insieme di elementi. Se un set di elementi ha k-items, viene chiamato k-itemset. Un set di elementi è costituito da due o più elementi. Un insieme di elementi che si verifica frequentemente è chiamato insieme di elementi frequenti. Pertanto, l'estrazione frequente di set di elementi è una tecnica di estrazione dati per identificare gli elementi che spesso si verificano insieme.
Per esempio , Pane e burro, software per laptop e antivirus, ecc.
Cos'è un set di elementi frequenti?
Un insieme di elementi è chiamato frequente se soddisfa un valore soglia minimo per il supporto e la fiducia. Il supporto mostra le transazioni con articoli acquistati insieme in un'unica transazione. La fiducia mostra le transazioni in cui gli articoli vengono acquistati uno dopo l'altro.
Per il metodo di mining di set di elementi frequenti, consideriamo solo le transazioni che soddisfano i requisiti di supporto e confidenza della soglia minima. Le intuizioni di questi algoritmi di mining offrono molti vantaggi, riduzione dei costi e miglioramento del vantaggio competitivo.
Esiste un tempo di compromesso per estrarre i dati e il volume dei dati per l'estrazione frequente. L'algoritmo di mining frequente è un algoritmo efficiente per estrarre i modelli nascosti dei set di elementi in breve tempo e con un minore consumo di memoria.
Frequent Pattern Mining (FPM)
L'algoritmo di pattern mining frequente è una delle tecniche più importanti di data mining per scoprire le relazioni tra i diversi elementi in un set di dati. Queste relazioni sono rappresentate sotto forma di regole di associazione. Aiuta a trovare le irregolarità nei dati.
FPM ha molte applicazioni nel campo dell'analisi dei dati, bug del software, cross-marketing, analisi delle campagne di vendita, analisi del paniere di mercato, ecc.
I set di elementi frequenti rilevati tramite Apriori hanno molte applicazioni nelle attività di data mining. Compiti come la ricerca di modelli interessanti nel database, la ricerca di sequenze e l'estrazione di regole di associazione sono le più importanti.
Le regole di associazione si applicano ai dati delle transazioni del supermercato, ovvero per esaminare il comportamento del cliente in termini di prodotti acquistati. Le regole di associazione descrivono la frequenza con cui gli articoli vengono acquistati insieme.
Regole dell'Associazione
L'estrazione delle regole di associazione è definita come:
'Sia I = {…} un insieme di attributi binari' n 'chiamati elementi. Sia D = {….} Una transazione chiamata database. Ogni transazione in D ha un ID transazione univoco e contiene un sottoinsieme degli elementi in I. Una regola è definita come un'implicazione del modulo X-> Y dove X, Y? Io e X? Y = ?. L'insieme degli elementi X e Y sono chiamati rispettivamente antecedente e conseguente della regola. '
L'apprendimento delle regole di associazione viene utilizzato per trovare le relazioni tra gli attributi in database di grandi dimensioni. Una regola di associazione, A => B, avrà la forma 'per un insieme di transazioni, un certo valore dell'insieme di elementi A determina i valori dell'insieme di elementi B nella condizione in cui il supporto minimo e la fiducia sono soddisfatti'.
Supporto e fiducia possono essere rappresentati dal seguente esempio:
Bread=> butter (support=2%, confidence-60%)La dichiarazione di cui sopra è un esempio di una regola di associazione. Ciò significa che c'è una transazione del 2% che ha acquistato pane e burro insieme e il 60% dei clienti ha acquistato pane e burro.
Supporto e fiducia per Itemset A e B sono rappresentati da formule:
L'estrazione delle regole di associazione consiste in 2 passaggi:
- Trova tutti i set di elementi frequenti.
- Genera regole di associazione dai frequenti set di elementi di cui sopra.
Perché l'estrazione di oggetti frequenti?
Il set di elementi frequente o il pattern mining è ampiamente utilizzato a causa delle sue ampie applicazioni nelle regole di associazione del mining, nelle correlazioni e nei vincoli di pattern di grafici basati su pattern frequenti, pattern sequenziali e molte altre attività di data mining.
Algoritmo Apriori - Algoritmi di pattern frequenti
L'algoritmo Apriori è stato il primo algoritmo proposto per l'estrazione frequente di set di elementi. Successivamente fu migliorato da R Agarwal e R Srikant e divenne noto come Apriori. Questo algoritmo utilizza due passaggi 'join' e 'pota' per ridurre lo spazio di ricerca. È un approccio iterativo per scoprire i set di elementi più frequenti.
Apriori dice:
La probabilità che l'elemento I non sia frequente è se:
- PI)
- P (I + A)
- Se un set di elementi ha un valore inferiore al supporto minimo, anche tutti i suoi superset scenderanno al di sotto del supporto minimo e quindi possono essere ignorati. Questa proprietà è chiamata proprietà Antimonotone.
- P (I + A)
I passaggi seguiti nell'algoritmo Apriori del data mining sono:
- Unisciti a Step : Questo passaggio genera (K + 1) set di elementi da set di elementi K unendo ogni elemento con se stesso.
- Prune Step : Questo passaggio analizza il conteggio di ogni elemento nel database. Se l'elemento candidato non soddisfa il supporto minimo, viene considerato poco frequente e quindi viene rimosso. Questo passaggio viene eseguito per ridurre le dimensioni dei set di elementi candidati.
Passaggi in Apriori
L'algoritmo Apriori è una sequenza di passaggi da seguire per trovare l'insieme di elementi più frequente nel database specificato. Questa tecnica di data mining segue il join e le fasi di sfoltimento in modo iterativo fino a ottenere il set di elementi più frequente. Una soglia minima di supporto è data nel problema o è assunta dall'utente.
# 1) Nella prima iterazione dell'algoritmo, ogni elemento viene considerato come candidato a 1 set di elementi. L'algoritmo conterà le occorrenze di ogni elemento.
#Due) Lascia che ci sia un supporto minimo, min_sup (ad esempio 2). L'insieme di 1 - gli insiemi di elementi la cui occorrenza soddisfa il sup min vengono determinati. Solo i candidati che contano più o uguale a min_sup vengono portati avanti per l'iterazione successiva e gli altri vengono eliminati.
# 3) Successivamente, vengono rilevati elementi frequenti a 2 elementi con min_sup. Per questo nella fase di unione, il set di 2 elementi viene generato formando un gruppo di 2 combinando gli elementi con se stesso.
# 4) I candidati a 2 elementi vengono eliminati utilizzando il valore soglia minimo sup. Ora la tabella avrà 2 elementi con solo sup min.
# 5) La prossima iterazione formerà 3 -itemsets usando il passaggio di join e prune. Questa iterazione seguirà la proprietà antimonotono dove i sottoinsiemi di 3 elementi, cioè i 2 elementi dell'insieme di ogni gruppo cadono in min_sup. Se tutti i sottoinsiemi di 2 elementi sono frequenti, il superset sarà frequente, altrimenti verrà eliminato.
# 6) Il passaggio successivo seguirà la creazione di un set di 4 elementi unendo il set di 3 elementi con se stesso e l'eliminazione se il suo sottoinsieme non soddisfa i criteri min_sup. L'algoritmo viene interrotto quando viene raggiunto l'insieme di elementi più frequente.
(Immagine fonte )
Esempio di Apriori:Soglia di supporto = 50%, Fiducia = 60%
TABELLA 1
| Transazione | Elenco di elementi |
|---|---|
| T1 | I1, I2, I3 |
| T2 | I2, I3, I4 |
| T3 | I4, I5 |
| T4 | I1, I2, I4 |
| T5 | I1, I2, I3, I5 |
| T6 | I1, I2, I3, I4 |
Soluzione:
Soglia di supporto = 50% => 0,5 * 6 = 3 => min_sup = 3
1. Conteggio di ogni articolo
TAVOLO 2
| Articolo | Contare |
|---|---|
| I1 | 4 |
| I2 | 5 |
| I3 | 4 |
| I4 | 4 |
| I5 | Due |
Due. Fase di potatura: TAVOLO 2 mostra che l'elemento I5 non soddisfa min_sup = 3, quindi viene eliminato, solo I1, I2, I3, I4 soddisfano il conteggio min_sup.
TABELLA-3
| Articolo | Contare |
|---|---|
| I1 | 4 |
| I2 | 5 |
| I3 | 4 |
| I4 | 4 |
3. Fase di partecipazione: Form 2-set di elementi. A partire dal TABELLA 1 scoprire le occorrenze di 2 elementi.
TABELLA-4
| Articolo | Contare |
|---|---|
| I1, I2 | 4 |
| I1, I3 | 3 |
| I1, I4 | Due |
| I2, I3 | 4 |
| I2, I4 | 3 |
| I3, I4 | Due |
Quattro. Fase di potatura: TABELLA -4 mostra che l'insieme di elementi {I1, I4} e {I3, I4} non soddisfa min_sup, quindi viene eliminato.
TABELLA-5
| Articolo | Contare |
|---|---|
| I1, I2 | 4 |
| I1, I3 | 3 |
| I2, I3 | 4 |
| I2, I4 | 3 |
5. Unisci e sfoltisci passo: Modulo 3 elementi. Dal TABELLA 1 scoprire le occorrenze di 3 elementi. A partire dal TABELLA-5 , scopri i sottoinsiemi di 2 elementi che supportano min_sup.
Possiamo vedere che i sottoinsiemi {I1, I2, I3} dell'insieme di elementi {I1, I2}, {I1, I3}, {I2, I3} si verificano in TABELLA-5 quindi {I1, I2, I3} è frequente.
Possiamo vedere per i sottoinsiemi di elementi {I1, I2, I4}, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} non è frequente, poiché non si verifica in TABELLA-5 quindi {I1, I2, I4} non è frequente, quindi viene cancellato.
il posto migliore per guardare anime soprannominate
TABELLA-6
| Articolo |
|---|
| I1, I2, I3 |
| I1, I2, I4 |
| I1, I3, I4 |
| I2, I3, I4 |
Solo {I1, I2, I3} è frequente .
6. Genera regole di associazione: Dal frequente set di elementi scoperto sopra l'associazione potrebbe essere:
{I1, I2} => {I3}
Fiducia = supporto {I1, I2, I3} / supporto {I1, I2} = (3/4) * 100 = 75%
{I1, I3} => {I2}
Fiducia = supporto {I1, I2, I3} / supporto {I1, I3} = (3/3) * 100 = 100%
{I2, I3} => {I1}
Fiducia = supporto {I1, I2, I3} / supporto {I2, I3} = (3/4) * 100 = 75%
{I1} => {I2, I3}
Fiducia = supporto {I1, I2, I3} / supporto {I1} = (3/4) * 100 = 75%
{I2} => {I1, I3}
Fiducia = supporto {I1, I2, I3} / supporto {I2 = (3/5) * 100 = 60%
{I3} => {I1, I2}
Fiducia = supporto {I1, I2, I3} / supporto {I3} = (3/4) * 100 = 75%
Ciò dimostra che tutte le regole di associazione di cui sopra sono valide se la soglia di confidenza minima è del 60%.
L'algoritmo Apriori: pseudo codice
C: Insieme di elementi candidati di dimensione k
L: set di articoli frequenti di dimensione k
(Immagine fonte )
Vantaggi
- Algoritmo di facile comprensione
- I passaggi Join e Prune sono facili da implementare su set di elementi di grandi dimensioni in database di grandi dimensioni
Svantaggi
- Richiede un calcolo elevato se i set di elementi sono molto grandi e il supporto minimo è mantenuto molto basso.
- L'intero database deve essere scansionato.
Metodi per migliorare l'efficienza Apriori
Sono disponibili molti metodi per migliorare l'efficienza dell'algoritmo.
- Tecnica basata su hash: Questo metodo utilizza una struttura basata su hash chiamata tabella hash per generare i k-itemsets e il conteggio corrispondente. Usa una funzione hash per generare la tabella.
- Riduzione delle transazioni: Questo metodo riduce il numero di transazioni scansionate in iterazioni. Le transazioni che non contengono elementi frequenti vengono contrassegnate o rimosse.
- Partizionamento: Questo metodo richiede solo due scansioni del database per estrarre i set di elementi frequenti. Dice che affinché qualsiasi set di elementi sia potenzialmente frequente nel database, dovrebbe essere frequente in almeno una delle partizioni del database.
- Campionamento: Questo metodo seleziona un campione casuale S dal database D e quindi cerca un insieme di elementi frequente in S. Potrebbe essere possibile perdere un insieme di elementi frequente globale. Questo può essere ridotto abbassando min_sup.
- Conteggio dinamico degli elementi: Questa tecnica può aggiungere nuovi set di elementi candidati in qualsiasi punto iniziale contrassegnato del database durante la scansione del database.
Applicazioni dell'algoritmo Apriori
Alcuni campi in cui viene utilizzato Apriori:
- Nel campo dell'istruzione: Estrazione delle regole di associazione nel data mining degli studenti ammessi attraverso caratteristiche e specialità.
- In campo medico: Ad esempio Analisi del database del paziente.
- In silvicoltura: Analisi della probabilità e dell'intensità degli incendi boschivi con i dati sugli incendi boschivi.
- Apriori è utilizzato da molte aziende come Amazon in Sistema di raccomandazione e da Google per la funzione di completamento automatico.
Conclusione
L'algoritmo Apriori è un algoritmo efficiente che esegue la scansione del database solo una volta.
Riduce notevolmente la dimensione degli elementi nel database fornendo una buona prestazione. Pertanto, il data mining aiuta i consumatori e le industrie a migliorare il processo decisionale.
Dai un'occhiata al nostro prossimo tutorial per saperne di più sull'algoritmo di crescita del pattern frequente !!
Tutorial PREV | PROSSIMO Tutorial
Lettura consigliata
- Tecniche di data mining: algoritmi, metodi e principali strumenti di data mining
- Data mining: processo, tecniche e problemi principali nell'analisi dei dati
- Esempi di data mining: applicazioni più comuni del data mining 2021
- Esempi di algoritmi dell'albero decisionale nel data mining
- Processo di data mining: modelli, fasi del processo e sfide coinvolte
- Data mining vs machine learning vs intelligenza artificiale vs deep learning
- I 15 migliori strumenti gratuiti per il data mining: l'elenco più completo
- Parametrizzazione dei dati JMeter mediante variabili definite dall'utente