Esempi di algoritmi dell'albero decisionale nel data mining

decision tree algorithm examples data mining

Questo tutorial approfondito spiega tutto sull'algoritmo dell'albero decisionale nel data mining. Imparerai a conoscere gli esempi, l'algoritmo e la classificazione dell'albero decisionale:

Abbiamo dato un'occhiata a un paio di Esempi di data mining nel nostro precedente tutorial in Serie di formazione gratuita sul data mining .

Il Decision Tree Mining è un tipo di tecnica di data mining utilizzata per creare modelli di classificazione. Crea modelli di classificazione sotto forma di una struttura ad albero, proprio come il suo nome. Questo tipo di mining appartiene all'apprendimento in classe supervisionato.

Nell'apprendimento supervisionato, il risultato target è già noto. Gli alberi decisionali possono essere utilizzati sia per i dati categoriali che per i dati numerici. I dati categoriali rappresentano sesso, stato civile, ecc. Mentre i dati numerici rappresentano età, temperatura, ecc.

ripper dvd freeware per windows 8

Di seguito è mostrato un esempio di albero decisionale con il set di dati.

(Immagine fonte )

Cosa imparerai:

• A cosa serve un albero decisionale?
• Analisi della classificazione
• Analisi di regressione
• Come funziona un albero decisionale?
• Algoritmo di induzione dell'albero decisionale
• Induzione dell'albero decisionale
• CARRELLO
• Induzione dell'albero decisionale per l'apprendimento automatico: ID3
• Che cos'è la divisione binaria ricorsiva avida?
• Come selezionare gli attributi per la creazione di un albero?
  • # 1) Guadagno di informazioni
  • # 2) Rapporto di guadagno
  • # 3) Indice Gini
• Overfitting negli alberi decisionali
• Cos'è la potatura degli alberi?
• Che cos'è la modellazione predittiva?
• Vantaggi della classificazione dell'albero decisionale
• Svantaggi della classificazione dell'albero decisionale
• Conclusione
• Lettura consigliata

A cosa serve un albero decisionale?

L'albero decisionale viene utilizzato per creare modelli di classificazione e regressione. Viene utilizzato per creare modelli di dati che prevederanno le etichette oi valori delle classi per il processo decisionale. I modelli vengono costruiti a partire dal set di dati di formazione fornito al sistema (apprendimento supervisionato).

Utilizzando un albero decisionale, possiamo visualizzare le decisioni che lo rendono facile da capire e quindi è una tecnica di data mining popolare.

Analisi della classificazione

La classificazione dei dati è una forma di analisi che costruisce un modello che descrive importanti variabili di classe.Per esempio, un modello creato per classificare le richieste di prestito bancario come sicure o rischiose. I metodi di classificazione vengono utilizzati nell'apprendimento automatico e nel riconoscimento di modelli.

L'applicazione della classificazione include il rilevamento delle frodi, la diagnosi medica, il marketing mirato, ecc. L'output del problema di classificazione viene considerato come 'Modalità' di tutti i valori osservati del nodo terminale.

Viene seguito un processo in due fasi per costruire un modello di classificazione.

1. Nella prima fase, ad esempio apprendimento: viene creato un modello di classificazione basato sui dati di addestramento.
2. Nella seconda fase, ovvero Classificazione, viene verificata l'accuratezza del modello e quindi il modello viene utilizzato per classificare i nuovi dati. Le etichette delle classi presentate qui sono sotto forma di valori discreti come 'sì' o 'no', 'sicuro' o 'rischioso'.

Di seguito viene fornito l'approccio generale per i modelli di classificazione degli edifici:

(Immagine fonte )

Analisi di regressione

L'analisi di regressione viene utilizzata per la previsione di attributi numerici.

Gli attributi numerici sono anche chiamati valori continui. Un modello creato per prevedere i valori continui invece delle etichette di classe è chiamato modello di regressione. Il risultato dell'analisi di regressione è la 'media' di tutti i valori osservati del nodo.

Come funziona un albero decisionale?

Un albero decisionale è un algoritmo di apprendimento supervisionato che funziona sia per variabili discrete che continue. Divide il set di dati in sottoinsiemi sulla base dell'attributo più significativo nel set di dati. Il modo in cui l'albero decisionale identifica questo attributo e come viene eseguita questa suddivisione viene deciso dagli algoritmi.

Il predittore più significativo è designato come nodo radice, la divisione viene eseguita per formare sottonodi chiamati nodi decisionali ei nodi che non si dividono ulteriormente sono nodi terminali o foglia.

Nell'albero decisionale, il set di dati è suddiviso in regioni omogenee e non sovrapposte. Segue un approccio dall'alto verso il basso poiché la regione superiore presenta tutte le osservazioni in un unico punto che si divide in due o più rami che si dividono ulteriormente. Questo approccio è anche chiamato a approccio avido in quanto considera solo il nodo corrente tra i nodi lavorati senza concentrarsi sui nodi futuri.

Gli algoritmi dell'albero decisionale continueranno a funzionare fino al raggiungimento di un criterio di interruzione come il numero minimo di osservazioni, ecc.

Una volta creato un albero decisionale, molti nodi possono rappresentare dati anomali o rumorosi. Il metodo di potatura degli alberi viene applicato per rimuovere i dati indesiderati. Questo, a sua volta, migliora l'accuratezza del modello di classificazione.

Per trovare l'accuratezza del modello, viene utilizzato un set di test composto da tuple di test ed etichette di classe. Le percentuali delle tuple del set di test vengono classificate correttamente dal modello per identificare l'accuratezza del modello. Se il modello viene ritenuto accurato, viene utilizzato per classificare le tuple di dati per le quali le etichette di classe non sono note.

Alcuni degli algoritmi dell'albero decisionale includono l'algoritmo di Hunt, ID3, CD4.5 e CART.

Esempio di creazione di un albero decisionale

(L'esempio è tratto dai concetti di data mining: Han e Kimber)

# 1) Fase di apprendimento: I dati di allenamento vengono immessi nel sistema per essere analizzati da un algoritmo di classificazione. In questo esempio, l'etichetta della classe è l'attributo, ovvero 'decisione di prestito'. Il modello costruito da questi dati di addestramento è rappresentato sotto forma di regole decisionali.

# 2) Classificazione: I set di dati di test vengono inviati al modello per verificare l'accuratezza della regola di classificazione. Se il modello fornisce risultati accettabili, viene applicato a un nuovo set di dati con variabili di classe sconosciute.

Algoritmo di induzione dell'albero decisionale

Induzione dell'albero decisionale

L'induzione dell'albero decisionale è il metodo per apprendere gli alberi decisionali dal set di formazione. Il set di addestramento è costituito da attributi ed etichette di classe. Le applicazioni dell'induzione dell'albero decisionale includono astronomia, analisi finanziaria, diagnosi medica, produzione e produzione.

Un albero decisionale è una struttura ad albero del diagramma di flusso composta dalle tuple del set di addestramento. Il set di dati è suddiviso in sottoinsiemi più piccoli ed è presente sotto forma di nodi di un albero. La struttura ad albero ha un nodo radice, nodi interni o nodi decisionali, nodo foglia e rami.

Il nodo radice è il nodo più in alto. Rappresenta il miglior attributo selezionato per la classificazione. I nodi interni dei nodi di decisione rappresentano un test di un attributo del nodo foglia del set di dati o del nodo terminale che rappresenta la classificazione o l'etichetta di decisione. I rami mostrano l'esito del test eseguito.

Alcuni alberi decisionali hanno solo nodi binari , ciò significa esattamente due rami di un nodo, mentre alcuni alberi decisionali non sono binari.

L'immagine sotto mostra l'albero decisionale per il set di dati del Titanic per prevedere se il passeggero sopravviverà o meno.

(Immagine fonte )

CARRELLO

Il modello CART, ovvero i modelli di classificazione e regressione, è un algoritmo dell'albero decisionale per la creazione di modelli. Il modello dell'albero decisionale in cui i valori obiettivo hanno una natura discreta è chiamato modelli di classificazione.

Un valore discreto è un insieme di valori finito o numerabile infinito, Per esempio, età, dimensione, ecc. I modelli in cui i valori target sono rappresentati da valori continui sono generalmente numeri chiamati modelli di regressione. Le variabili continue sono variabili a virgola mobile. Questi due modelli insieme sono chiamati CART.

CART utilizza l'indice Gini come matrice di classificazione.

Induzione dell'albero decisionale per l'apprendimento automatico: ID3

Tra la fine degli anni '70 e l'inizio degli anni '80, J. Ross Quinlan era un ricercatore che ha creato un algoritmo ad albero decisionale per l'apprendimento automatico. Questo algoritmo è noto come ID3, dicotomizzatore iterativo . Questo algoritmo era un'estensione dei sistemi di apprendimento concettuale descritti da E.B Hunt, J e Marin.

ID3 in seguito divenne noto come C4.5. ID3 e C4.5 seguono un avido approccio dall'alto verso il basso per la costruzione di alberi decisionali. L'algoritmo inizia con un set di dati di addestramento con etichette di classe che vengono suddivise in sottoinsiemi più piccoli durante la costruzione dell'albero.

# 1) Inizialmente, ci sono tre parametri, ad es. elenco degli attributi, metodo di selezione degli attributi e partizione dei dati . L'elenco degli attributi descrive gli attributi delle tuple del set di addestramento.

#Due) Il metodo di selezione degli attributi descrive il metodo per selezionare l'attributo migliore per la discriminazione tra le tuple. I metodi utilizzati per la selezione degli attributi possono essere Guadagno di informazioni o Indice Gini.

# 3) La struttura dell'albero (binario o non binario) è decisa dal metodo di selezione degli attributi.

# 4) Quando si costruisce un albero decisionale, inizia come un singolo nodo che rappresenta le tuple.

# 5) Se le tuple del nodo radice rappresentano etichette di classe diverse, chiama un metodo di selezione degli attributi per dividere o partizionare le tuple. Il passaggio porterà alla formazione di rami e nodi decisionali.

# 6) Il metodo di suddivisione determinerà quale attributo deve essere selezionato per partizionare le tuple di dati. Determina inoltre i rami da coltivare dal nodo in base al risultato del test. Il motivo principale dei criteri di suddivisione è che la partizione in ogni ramo dell'albero decisionale dovrebbe rappresentare la stessa etichetta di classe.

Di seguito è riportato un esempio di attributo di divisione:

un. La porzionatura di cui sopra è a valore discreto.

b. La porzionatura di cui sopra è per valore continuo.

# 7) I passaggi di partizionamento precedenti vengono seguiti in modo ricorsivo per formare un albero decisionale per le tuple del set di dati di addestramento.

# 8) Il porzionamento si interrompe solo quando vengono create tutte le partizioni o quando le tuple rimanenti non possono essere ulteriormente suddivise.

# 9) La complessità dell'algoritmo è descritta da n * | D | * log | D | dove n è il numero di attributi nel set di dati di addestramento D e | D | è il numero di tuple.

Che cos'è la divisione binaria ricorsiva avida?

Nel metodo di suddivisione binaria, le tuple vengono suddivise e viene calcolata ciascuna funzione di costo di suddivisione. Viene selezionata la suddivisione del costo più basso. Il metodo di divisione è binario formato da 2 rami. È di natura ricorsiva poiché lo stesso metodo (calcolo del costo) viene utilizzato per suddividere le altre tuple del set di dati.

Questo algoritmo è chiamato greedy in quanto si concentra solo sul nodo corrente. Si concentra sulla riduzione del costo, mentre gli altri nodi vengono ignorati.

Come selezionare gli attributi per la creazione di un albero?

Le misure di selezione degli attributi sono anche chiamate regole di suddivisione per decidere come le tuple verranno divise. I criteri di suddivisione vengono utilizzati per suddividere al meglio il set di dati. Queste misure forniscono una classifica agli attributi per il partizionamento delle tuple di addestramento.

I metodi più popolari per selezionare l'attributo sono il guadagno di informazioni, l'indice di Gini.

# 1) Guadagno di informazioni

Questo metodo è il metodo principale utilizzato per creare alberi decisionali. Riduce le informazioni necessarie per classificare le tuple. Riduce il numero di test necessari per classificare la tupla data. Viene selezionato l'attributo con il maggior guadagno di informazioni.

Le informazioni originali necessarie per la classificazione di una tupla nel set di dati D sono fornite da:

Dove p è la probabilità che la tupla appartenga alla classe C. L'informazione è codificata in bit, quindi viene utilizzato il log in base 2. E (s) rappresenta la quantità media di informazioni richieste per scoprire l'etichetta di classe dell'insieme di dati D.Questo guadagno di informazioni è anche chiamato Entropia .

Le informazioni necessarie per la classificazione esatta dopo il porzionamento sono date dalla formula:

Dove P (c) è il peso della partizione. Queste informazioni rappresentano le informazioni necessarie per classificare il set di dati D sulla porzionatura per X.

Il guadagno di informazioni è la differenza tra le informazioni originali e quelle attese necessarie per classificare le tuple del set di dati D.

converti youtube in mp3 per più di 20 minuti

Il guadagno è la riduzione delle informazioni richieste conoscendo il valore di X. L'attributo con il maggior guadagno di informazioni viene scelto come 'migliore'.

# 2) Rapporto di guadagno

Il guadagno di informazioni a volte potrebbe risultare in porzioni inutili per la classificazione. Tuttavia, il rapporto di guadagno divide il set di dati di addestramento in partizioni e considera il numero di tuple del risultato rispetto alle tuple totali. L'attributo con il rapporto di guadagno massimo viene utilizzato come attributo di divisione.

# 3) Indice Gini

L'indice Gini viene calcolato solo per le variabili binarie. Misura l'impurità nelle tuple di addestramento del set di dati D, come

P è la probabilità che la tupla appartenga alla classe C.L'indice di Gini calcolato per il dataset binario D dall'attributo A è dato da:

Dove n è l'ennesima partizione del set di dati D.

La riduzione dell'impurità è data dalla differenza dell'indice Gini del set di dati originale D e dell'indice Gini dopo la partizione per attributo A.

La riduzione massima di impurità o indice Gini massimo è selezionato come miglior attributo per la divisione.

Overfitting negli alberi decisionali

L'overfitting si verifica quando un albero decisionale cerca di essere il più perfetto possibile aumentando la profondità dei test e quindi riduce l'errore. Ciò si traduce in alberi molto complessi e porta a un overfitting.

L'overfitting riduce la natura predittiva dell'albero decisionale. Gli approcci per evitare l'eccessivo adattamento degli alberi includono la pre potatura e la post potatura.

Cos'è la potatura degli alberi?

La potatura è il metodo per rimuovere i rami inutilizzati dall'albero decisionale. Alcuni rami dell'albero decisionale potrebbero rappresentare dati anomali o rumorosi.

La potatura degli alberi è il metodo per ridurre i rami indesiderati dell'albero. Ciò ridurrà la complessità dell'albero e consentirà un'analisi predittiva efficace. Riduce l'overfitting in quanto rimuove i rami non importanti dagli alberi.

Esistono due modi per potare l'albero:

# 1) Prepotatura : In questo approccio, la costruzione dell'albero decisionale viene interrotta in anticipo. Significa che si è deciso di non suddividere ulteriormente i rami. L'ultimo nodo costruito diventa il nodo foglia e questo nodo foglia può contenere la classe più frequente tra le tuple.

Le misure di selezione degli attributi vengono utilizzate per scoprire il peso della divisione. I valori di soglia sono prescritti per decidere quali frazionamenti sono considerati utili. Se la porzionatura del nodo determina una divisione al di sotto della soglia, il processo viene interrotto.

# 2) Post potatura : Questo metodo rimuove i rami anomali da un albero completamente cresciuto. I rami indesiderati vengono rimossi e sostituiti da un nodo foglia che denota l'etichetta di classe più frequente. Questa tecnica richiede più calcoli rispetto alla pre-potatura, tuttavia è più affidabile.

Gli alberi potati sono più precisi e compatti rispetto agli alberi non potati ma portano uno svantaggio di replicazione e ripetizione.

La ripetizione si verifica quando lo stesso attributo viene testato più e più volte lungo un ramo di un albero. Replica si verifica quando nell'albero sono presenti sottoalberi duplicati. Questi problemi possono essere risolti con divisioni multivariate.

L'immagine sotto mostra un albero non potato e potato.

Esempio di algoritmo dell'albero decisionale

Esempio fonte

Costruire un albero decisionale

Facciamo un esempio del set di dati meteorologici degli ultimi 10 giorni con attributi outlook, temperatura, vento e umidità. La variabile di risultato sarà giocare a cricket o no. Useremo l'algoritmo ID3 per costruire l'albero decisionale.

Passo 1: Il primo passo sarà creare un nodo radice.

Passo 2: Se tutti i risultati sono sì, verrà restituito il nodo foglia 'sì' altrimenti verrà restituito il nodo foglia 'no'.

Step3: Scopri l'entropia di tutte le osservazioni e l'entropia con l'attributo 'x' che è E (S) ed E (S, x).

Step4: Scopri il guadagno di informazioni e seleziona l'attributo con un elevato guadagno di informazioni.

Passaggio 5: Ripeti i passaggi precedenti finché tutti gli attributi non sono stati coperti.

Calcolo dell'entropia:

si No

9 5

convertitore da youtube a mp3 che funziona

Se l'entropia è zero, significa che tutti i membri appartengono alla stessa classe e se l'entropia è uno significa che metà delle tuple appartiene a una classe e una di esse appartiene a un'altra classe. 0.94 significa distribuzione equa.

Trova l'attributo guadagno di informazioni che fornisce il massimo guadagno di informazioni.

Per esempio 'Wind', richiede due valori: Strong e Weak, quindi x = {Strong, Weak}.

Scopri H (x), P (x) per x = debole ex = forte. H (S) è già calcolato sopra.

Debole = 8

Forte = 8

Per il vento 'debole', 6 di loro dicono 'Sì' per giocare a cricket e 2 di loro dicono 'No'. Quindi l'entropia sarà:

Per il vento 'forte', 3 hanno detto 'No' per giocare a cricket e 3 hanno detto 'Sì'.

Questo mostra una perfetta casualità poiché metà degli oggetti appartengono a una classe e la metà rimanente appartiene ad altre.

Calcola il guadagno di informazioni,

Allo stesso modo, il guadagno di informazioni per altri attributi è:

L'attributo outlook ha l'estensione massimo guadagno di informazioni di 0,246, quindi viene scelto come radice.

Overcast ha 3 valori: Sunny, Overcast e Rain. Nuvoloso quando si gioca a cricket è sempre 'Sì'. Quindi finisce con un nodo foglia, 'sì'. Per gli altri valori 'Sunny' e 'Rain'.

La tabella per Outlook come 'Sunny' sarà:

L'entropia per 'Outlook' 'Sunny' è:

Il guadagno di informazioni per attributi rispetto a Sunny è:

Il guadagno di informazioni per l'umidità è massimo, quindi viene scelto come nodo successivo. Allo stesso modo, l'entropia viene calcolata per Rain. Il vento fornisce il maggior guadagno di informazioni .

L'albero decisionale sarebbe simile a quello seguente:

Che cos'è la modellazione predittiva?

I modelli di classificazione possono essere utilizzati per prevedere i risultati di un insieme sconosciuto di attributi.

Quando un set di dati con etichette di classe sconosciute viene inserito nel modello, gli assegnerà automaticamente l'etichetta di classe. Questo metodo di applicazione della probabilità per prevedere i risultati è chiamato modellazione predittiva.

Vantaggi della classificazione dell'albero decisionale

Di seguito sono elencati i vari meriti della classificazione dell'albero delle decisioni:

1. La classificazione dell'albero decisionale non richiede alcuna conoscenza del dominio, quindi è appropriata per il processo di scoperta della conoscenza.
2. La rappresentazione dei dati sotto forma di albero è facilmente comprensibile dall'uomo ed è intuitiva.
3. Può gestire dati multidimensionali.
4. È un processo rapido con grande precisione.

Svantaggi della classificazione dell'albero decisionale

Di seguito sono riportati i vari demeriti della classificazione dell'albero decisionale:

1. A volte gli alberi decisionali diventano molto complessi e vengono chiamati alberi sovradimensionati.
2. L'algoritmo dell'albero decisionale potrebbe non essere una soluzione ottimale.
3. Gli alberi decisionali possono restituire una soluzione distorta se qualche etichetta di classe la domina.

Conclusione

Gli alberi decisionali sono tecniche di data mining per la classificazione e l'analisi di regressione.

Questa tecnica ora copre molte aree come la diagnosi medica, il marketing mirato, ecc. Questi alberi sono costruiti seguendo un algoritmo come ID3, CART. Questi algoritmi trovano modi diversi per suddividere i dati in partizioni.

È la tecnica di apprendimento supervisionato più conosciuta che viene utilizzata nell'apprendimento automatico e nell'analisi dei modelli. Gli alberi decisionali prevedono i valori della variabile obiettivo costruendo modelli attraverso l'apprendimento dal set di formazione fornito al sistema.

Ci auguriamo che tu abbia imparato tutto su Decision Tree Mining da questo tutorial informativo !!

Tutorial PREV | PROSSIMO Tutorial

Lettura consigliata

• Esempi di data mining: applicazioni più comuni del data mining 2021
• Tecniche di data mining: algoritmi, metodi e principali strumenti di data mining
• Data mining: processo, tecniche e problemi principali nell'analisi dei dati
• Struttura dati B Tree e B + Tree in C ++
• Struttura dei dati dell'albero binario in C ++
• Processo di data mining: modelli, fasi del processo e sfide coinvolte
• Struttura dei dati ad albero e heap AVL in C ++
• Data mining vs machine learning vs intelligenza artificiale vs deep learning