In questo articolo spiegherò come fare una analisi basilare di un dataset da me creato e di come applicare il modello di Decision Tree con Python. Ho utilizzato Scikit e Pandas per la parte di analisi dati e dataframe, per la parte relativa ai grafici ho scoperto ultimamente questa libreria Seaborn che va a sostituire a matplotlib.
Il dataset che prendo in considerazione è stato costruito da me facendo un semplice scraping della pagina di ogni regione di Booking.com . Dopo avere effettuato lo scraping, fatto a mano dal sito, ho preso ogni singola città e ne ho categorizzato un tipo possibile di turismo.
Esso è costituito da: Nome città, regione, Hotel, Latitudine, Longitudine, tipo di turismo
Nella pratica considero tutte le regioni italiane e elenco le prime 25 città per numero di hotel. Il dataset è disponibile in fondo al blogpost.
L’analisi che farò sarà quella di creare dei Decision Tree sul dataset in base al tipo di turismo, usando più o meno diverse feature in tre casi differenti e vedendo quale dei tre casi funziona meglio. Infine userò le funzioni interne delle librerie di scikit per creare la grafica.
Ecco il gist contenente tutti procedimenti commentati passo passo.
Il Gradient Descent o Discesa del Gradiente è uno dei più popolari algoritmi di ottimizzazione.
La discesa del gradiente è un algoritmo molto usato nelle reti neurali in quanto è alla base dell’algoritmo di backpropagation, attualmente sono tantissime le librerie che implementano questo algoritmo.
L’idea del Gradiente Descent è quello di minimizzare una funzione obiettivo J(θ) formata da N parametri θ, aggiornando il valore dei parametri in base alla differenza con il gradiente negativo di J(θ) rispetto al parametro considerato. L’aggiornamento del parametro viene aggiornato poi passo passo, secondo un dato valore η, chiamato learning rate.
In parole povere, scendiamo una funzioneJ(θ) passo passo, finchè questa non ci porta verso un valore di massimo o di minimo e noi ci fermiamo a questo.
I modi con cui questo algoritmo si può eseguire sono:
Batch Gradient Descent
Stochastic Gradient Descent
Mini Batch Gradient Descent
Batch Gradient Descent
La Batch Gradient Descent (BGD), o Discesa del Gradiente a Batch, computa la discesa del gradiente per la funzione costo su tutto il Training set:
Dove θ è la funzione costo per l’intero Training set. Con questo metodo dobbiamo calcolare la discesa del gradiente una sola volta, siccome usiamo tutto il nostro Training Set, tuttavia essa può essere molto lenta se il dataset è grande e impossibile da fare se il dataset non entra in memoria.
Stochastic Gradient Descent
Lo Stochastic Gradient Descent (SGD), o Discesa del Gradiente Stocastica, computa la discesa del gradiente per ogni elemento del Training set e aggiorna il suo valore volta per volta.
A differenza del Batch Gradient Descent, cioè la discesa del gradiente utilizzando una quantità di dati molto alta, questa tecnica utilizza un solo valore per volta:
Dove θ è la funzione costo per l’intero Training set.
Mini Batch Gradient Descent
La Mini Batch Gradiente Descente (MBGD), o Discesa del Gradiente a MiniBatch, è una via di mezzo fra la SGD e la BGD in quanto effettua degli aggiornamenti ai parametri della funzione con dei minibatch, e non con l’intero dataset o con valori singoli, e in questo modo porta a una più veloce convergenza .
Questi algoritmi per trovare l’ottimo delle funzioni sono disponibili nella libreria Python Scikit, nel prossimo articolo implementerò un classificatore che utilizza il metodo SGD per classificare delle cifre scritte a mano.
In questo articolo spiegherò come creare degli oggetti Clusterizzati in Python usando la libreria SciPy.
SciPy mette a disposizione per noi un sacco di metodi per il Clustering, noi utilizzeremo quelli che abbiamo visto nell’articolo precedente.
Il seguente file IPython fa vedere perfettamente la procedura con un metodo di collegamento fra i cluster di tipo singolo basato sulla distanza euclidea.
Il file ha i commenti che indicano ogni singola operazione avvenuta.
In questo articolo esporrò lo pseudo codice dell’algoritmo A-Priori e una versione funzionante in Go.
L’algoritmo A-Priori si può riassumere nel seguente modo:
Ammettiamo di avere questo Dataset
Transazioni
Cestino
1
{“Mela”,”Lampone”,”Ananas”}
2
{“Mela”,”Kiwi”,”Ananas”}
3
{“Lampone”,”Ananas”}
4
{“Banana”,”Kiwi”,”Ananas”}
5
{“Kiwi”}
6
{“Mela”,”Kiwi”}
Primo passaggio di Apriori
Creiamo un insieme contenente tutti i nostri elementi singoli presi dal Dataset e creiamo una mappa contenete la frequenza dei nostri oggetti
Set = {“Mela”,”Kiwi”,”Ananas”,”Lampone”,”Banana”}
Frequency Set = {“Mela”: 3, “Kiwi”,4 “Ananas”: 4, “Lampone”: 1, “Banana”: 1}
Ammettiamo di avere settato un valore di supporto parti a 0.2, eliminiamo ora tutti gli elementi che nel Frequency Set non hanno supporto pari a 0.2. Otteniamo quindi:
Set = {“Mela”,”Kiwi”,”Ananas”,”Lampone”}
Frequency Set = {“Mela”: 3, “Kiwi”,4 “Ananas”: 4}
Secondo passaggio di A-Priori
Creiamo i nuovi insieme di candidati dal Set precedente a 2 a 2, cioè
Set = {“Mela-Kiwi”,”Mela-Ananas”,”Kiwi-Ananas”}
Questo è il nostro nuovo set di candidati che sottoporremo alla regola del supporto.
Terzo passaggio di A-Priori
Verifichiamo se il set di candidati ha nuovi elementi frequenti:
Set = {“Mela-Kiwi”,”Mela-Ananas”,”Kiwi-Ananas”}
Frequency Set = {“Mela-Kiwi”: 2 ,”Mela-Ananas”: 2,”Kiwi-Ananas”:2}
Quarto passaggio di A-Priori
Creiamo i nuovi set di candidati dal Set precedente a 3 a 3, cioè
Set = {“Mela-Kiwi-Ananas”}
Quinto passaggio di A-Priori:
Set = {“Mela-Kiwi-Ananas”}
Frequency Set = {“Mela-Kiwi-Ananas”: 1}
L’insieme di elementi piu’ frequente generato da A-Priori è “Mela-Kiwi-Ananas”, e ogni sotto insieme generato da questo è a sua volta il più frequente.
Si deduce da questo processo quindi il seguente algoritmo:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Prima filtriamo i dati e poi costruiamo i dati successivi finchè non otteniamo il nostro risultato finale.
Ho scritto un codice in Go che ci permette di applicare A-Priori come specificato dal nostro algoritmo.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
È molto esoso dal punto di vista della computazione. Seppure riducendo il numero di candidati da considerare, il numero di questi è sempre molto grande quando il numero di elementi nei cestini della gente è alto o quando il valore limite di supporto è basso.
Associazioni False. Riducendo il valore limite di supporto per notare alcuni tipi di associazioni, può succede che ci siano delle associazioni non giuste e quindi false. Per ridurre questo problema occorre filtrare prima il Dataset o verificare il valore di supporto e confidenza in un Test Set separato.
Conclusioni
A-Priori si dimostra essere un algoritmo molto interessate per studiare le associazioni all’interno di un Dataset con transazioni. Nonostante abbia delle limitazioni ci sono stati degli algoritmi che lo hanno migliorato come ad esempio l’algoritmo PCY o l’algoritmo Multistage.
