Data Mining - Algoritmo apriori Flashcards
Cos’è il Data Mining?
Il data mining, tradotto in italiano come “estrazione dei dati”, è un processo di analisi che consiste nell’esplorazione e nell’estrazione di informazioni significative e utili da grandi quantità di dati. L’obiettivo principale del data mining è scoprire modelli, relazioni e tendenze nascoste nei dati, al fine di trarre informazioni e conoscenze che possono essere utilizzate per prendere decisioni informate, fare previsioni o guidare l’azione.
Il data mining si basa sull’applicazione di algoritmi e tecniche statistiche e matematiche avanzate per esaminare i dati e identificare schemi che potrebbero non essere evidenti a una semplice osservazione. Può coinvolgere diverse fasi, tra cui la preparazione dei dati, l’estrazione delle informazioni, l’analisi dei dati e l’interpretazione dei risultati.
Come funziona il processo di estrazione nel data mining?
Il processo di estrazione dei dati nel data mining può essere suddiviso in diverse fasi principali. Ecco una panoramica di queste fasi:
Definizione degli obiettivi: La prima fase consiste nel definire chiaramente gli obiettivi del progetto di data mining. Questo implica capire cosa si vuole ottenere dall'analisi dei dati e quale tipo di informazioni si desidera estrarre. Raccolta dei dati: In questa fase vengono raccolti i dati pertinenti per l'analisi. I dati possono provenire da diverse fonti, come database aziendali, file di testo, registri di transazioni, dati sensoriali, dati web, social media, e così via. Preparazione dei dati: È necessario preparare i dati per l'analisi. Ciò può richiedere la pulizia dei dati, ovvero l'eliminazione di valori mancanti o duplicati, la riduzione della dimensionalità dei dati, l'integrazione di diverse fonti di dati, e la trasformazione dei dati in un formato adatto per l'elaborazione successiva. Selezione delle caratteristiche: In questa fase vengono selezionate le caratteristiche o le variabili rilevanti per l'analisi. Questo può comportare l'eliminazione di caratteristiche non informative o ridondanti, al fine di focalizzarsi sulle variabili più significative per raggiungere gli obiettivi del progetto. Scelta degli algoritmi: Una volta che i dati sono pronti, viene selezionato l'algoritmo di data mining più adatto per l'analisi. Esistono numerosi algoritmi disponibili, come algoritmi di clustering, algoritmi di classificazione, algoritmi di regressione, algoritmi di associazione, e molti altri. La scelta dell'algoritmo dipende dal tipo di dati e dagli obiettivi dell'analisi. Applicazione degli algoritmi: In questa fase, gli algoritmi selezionati vengono applicati ai dati per estrarre le informazioni desiderate. Gli algoritmi analizzano i dati alla ricerca di modelli, relazioni o tendenze significative. Valutazione e interpretazione dei risultati: Una volta ottenuti i risultati dall'applicazione degli algoritmi, è necessario valutarli e interpretarli. Questo può comportare l'analisi dei modelli scoperti, la verifica dell'accuratezza delle previsioni o la valutazione dell'importanza delle variabili. Utilizzo dei risultati: Infine, i risultati dell'analisi vengono utilizzati per prendere decisioni informate, sviluppare strategie o migliorare i processi aziendali. Le informazioni estratte possono essere integrate nei sistemi esistenti o utilizzate per creare modelli predittivi o sistemi di supporto decisionale.
È importante notare che il processo di estrazione dei dati nel data mining è iterativo, e potrebbe richiedere diverse iterazioni e affinamenti al fine di ottenere risultati significativi e utili.
Regole di associazione
Le regole di associazione sono un concetto fondamentale nel campo del data mining, che riguarda l’individuazione di relazioni interessanti tra gli elementi di un insieme di dati. Le regole di associazione identificano correlazioni o pattern frequenti tra gli elementi di un insieme di dati e vengono spesso utilizzate per analizzare i modelli di acquisto dei clienti nel settore del commercio al dettaglio o per rilevare relazioni tra gli eventi in applicazioni di monitoraggio.
Le regole di associazione sono solitamente espresse come “se X, allora Y”, dove X e Y rappresentano gli elementi o gli insiemi di elementi che sono associati. Le regole di associazione sono valutate in base a due metriche principali:
Supporto (support): Indica la frequenza con cui un particolare insieme di elementi appare nel dataset. Il supporto è calcolato come la proporzione di transazioni nel dataset in cui compare l'insieme di elementi. Ad esempio, se l'insieme di elementi {A, B} appare in 50 transazioni su un totale di 100, allora il supporto è 50/100 = 0,5.
Confidenza (confidence): Indica la probabilità condizionata che Y si verifichi dato che X si è verificato. La confidenza viene calcolata come la proporzione di transazioni contenenti X che contengono anche Y. Ad esempio, se 40 transazioni contengono {A, B} e in 30 di queste transazioni compare anche Y, allora la confidenza è 30/40 = 0,75.
Oltre a supporto e confidenza, ci sono anche altre metriche utilizzate per valutare la forza delle regole di associazione, come il lift e l’interest factor. Il lift indica quanto una regola è dipendente o indipendente, mentre l’interest factor misura l’interesse relativo di una regola rispetto all’insieme di dati considerato.
L’algoritmo più noto per estrarre regole di associazione è l’algoritmo Apriori, che ricerca le combinazioni frequenti di elementi in un dataset e genera regole di associazione basate su queste combinazioni. Esistono anche altre varianti e algoritmi più sofisticati per l’estrazione di regole di associazione, come l’algoritmo FP-Growth e l’algoritmo Eclat.
Le regole di associazione sono utili per comprendere le relazioni nascoste nei dati e possono essere applicate in diversi settori, come il marketing, la raccomandazione di prodotti, la scoperta di conoscenza e altro ancora.
Solitamente abbiamo a disposizione i seguenti dati:
* “I” insieme di items;
* “T” transazioni che contengono un sottoinsieme di I;
* “D” base dati che è l’insieme delle transazioni.
Usiamo le seguenti definizioni:
* Una regola di associazione si definisce così X=>Y
* Supporto(X) = numero di transazioni che contengono X in D
* Supporto(X=>Y) = Supporto(X U Y)
* Confidenza(X=>Y) = Supporto(X U Y) / Supporto(X)
Algoritmo a priori
L’algoritmo Apriori è uno dei più utilizzati per l’estrazione di regole di associazione nel data mining. Prende il nome dal concetto di “principio di Apriori”, secondo il quale se un insieme di elementi è frequente, allora tutti i suoi sottoinsiemi devono essere frequenti. L’algoritmo Apriori sfrutta questo principio per identificare i pattern frequenti nel dataset e generare le regole di associazione corrispondenti.
Ecco una spiegazione dei passi chiave dell’algoritmo Apriori:
Passo 1: Calcolo del supporto: Inizialmente, si calcola il supporto di tutti gli elementi individuali nel dataset, cioè la frequenza di ciascun elemento. Questo viene fatto attraverso l'analisi delle transazioni nel dataset. Passo 2: Generazione dei set candidati frequenti: Viene generato un insieme di candidati frequenti iniziali combinando gli elementi frequenti individuati nel passo precedente. Gli insiemi candidati contengono due o più elementi. Passo 3: Pruning (potatura) dei set candidati: In questa fase, si eliminano gli insiemi candidati che non soddisfano il principio di Apriori. Se un sottoinsieme di un insieme candidato non è frequente, l'insieme candidato stesso non può essere frequente. Pertanto, gli insiemi candidati che contengono sottoinsiemi non frequenti vengono rimossi. Passo 4: Calcolo del supporto degli insiemi candidati frequenti: Il supporto degli insiemi candidati frequenti viene calcolato nuovamente attraverso l'analisi delle transazioni nel dataset. Passo 5: Generazione di regole di associazione: Utilizzando gli insiemi candidati frequenti, si generano le regole di associazione. Le regole vengono create considerando tutti i possibili sottoinsiemi degli insiemi frequenti. Viene calcolata la confidenza per ogni regola e le regole con una confidenza superiore a una soglia prefissata vengono selezionate come regole di associazione interessanti.
Questi passaggi vengono iterati fino a quando non si possono più generare nuovi insiemi candidati frequenti o non rimangono regole di associazione interessanti da estrarre.
L’algoritmo Apriori può essere implementato in modo efficiente utilizzando tecniche come l’hashing e la compressione di database, al fine di ridurre il tempo di calcolo e la complessità spaziale.
L’output dell’algoritmo Apriori sono i pattern frequenti e le regole di associazione che soddisfano le soglie di supporto e confidenza specificate dall’utente. Queste regole possono quindi essere utilizzate per trarre informazioni significative dai dati e prendere decisioni basate su di esse.
Regole di classificazione e regressione nell’algoritmo a priori
L’algoritmo Apriori è specificamente progettato per l’estrazione di regole di associazione, che si concentrano sulla scoperta di relazioni tra gli elementi di un insieme di dati. Non tratta direttamente le regole di classificazione o di regressione.
Tuttavia, è possibile utilizzare i risultati dell’algoritmo Apriori come passo preliminare per la creazione di modelli di classificazione o regressione. Vediamo come:
Regole di Classificazione: Dopo aver estratto le regole di associazione utilizzando l'algoritmo Apriori, è possibile utilizzare queste regole per creare un modello di classificazione. Per fare ciò, si assegna una classe o una categoria specifica a ciascuna regola di associazione basandosi sulle caratteristiche dei dati coinvolti. Successivamente, quando si applica il modello a nuovi dati, si utilizzano le regole di associazione per determinare la classe corrispondente.
Nella valutazione di un classificatore si considerano metriche come:
* Accuratezza
* Velocità di classificazione
* Robustezza in presenza di valori mancanti o errori
* Scalabilità
* Facilità di Interpretazione
Ad esempio, se le regole di associazione estratte mostrano che “se A e B sono presenti, allora C è presente”, si può assegnare la classe “C” quando sia A che B sono presenti nei nuovi dati. In questo modo, le regole di associazione possono essere utilizzate per classificare nuovi esempi in base a regole precedentemente identificate.
Regole di Regressione: Analogamente alle regole di classificazione, le regole di associazione possono essere utilizzate per creare un modello di regressione. Tuttavia, questo richiede una trasformazione delle regole di associazione in regole di regressione.
Un approccio comune consiste nell’assegnare valori numerici alle categorie o classi coinvolte nelle regole di associazione e utilizzarli come variabili di output per un modello di regressione. Ad esempio, se una regola di associazione estratta è “se A e B sono presenti, allora C è presente”, si può assegnare un valore numerico a C, come ad esempio il suo valore medio nel dataset. In questo modo, si può creare un modello di regressione che prevede il valore di C in base alla presenza di A e B.
È importante sottolineare che la trasformazione delle regole di associazione in regole di classificazione o regressione richiede ulteriori passaggi e considerazioni, e dipende anche dalla natura dei dati e degli obiettivi dell’analisi. Pertanto, se si desidera applicare l’algoritmo Apriori per la creazione di modelli di classificazione o regressione, è necessario prendere in considerazione l’adeguamento del processo e adattarlo alle esigenze specifiche del problema.
Similarity Search
L’obiettivo è determinare sequenze simili ad una sequenza data.
Ad esempio, identificazione delle società con comportamento simile di crescita, determinazione di prodotti
con profilo simile di vendita oppure identificazione di azioni con andamento simile.
Utilizza due tipi di interrogazione:
1. Match completo: la sequenza cercata e le sequenze della base dati hanno la stessa lunghezza;
2. Match parziale: la sequenza cercata può essere sotto sequenza di quelle della base dati
