Un problema molto divertente da risolvere è quello della Bandiera Olandese o in inglese Dutch National Flag Problem.
Il problema e’ stato postulato da Edsger Dijkstra, il famoso informatico per l’algoritmo sui grafi.
Questo problema si formula così: Abbiamo un array non ordinato formato da N valori numerici, che sono o 0 o 1 o 2. Il nostro compito è ordinarlo.
Quindi mi trovo in una situazione del genere:
[0,1,2,0,1,1,2,0,2,1,0,0,1,1,2,2]
Quale è il modo per ordinarli?
La risposta che per prima ci verrebbe in mente è usare un merge sort o un quick sort, per avere una complessita’ computazionale pari a n*log(n).
Addirittura modificando il quicksort si potrebbe ricavare un algoritmo molto molto veloce, in quanto si salterebbe la fase dopo la scelta del pivot (che ricadrebbe sempre su 1).
Tuttavia c’e’ un modo molto piu’ interessante di gestire il problema.
Possiamo pensare all’array come alle tre strisce di una bandiera (da cui il nome del problema), quindi abbiamo 3 tipi di valori che dobbiamo sistemare e sappiamo per certo che ci saranno 2 indici che ne decideranno il limite.
Il primo, che nominerò “basso“, indicherà quando i valori pari a 0 dentro l’array finiranno, Il secondo, che nominerò “alto“, invece si troverà dove i valori pari a 2 inizieranno.
Un terzo indice, che chiamerò “mobile“, indica i valori pari a 1, esso si sposterà dalla posizione 0 e man mano arriverà dove inizieranno quelli pari a 2.
Quando l’indice mobile sarà uguale all’indice alto avremo finito.
Iniziamo settando l’indice basso e l’indice mobile alla posizione 0, e l’indice alto alla fine dell’array.
Essi verranno incrementati o decrementati e usati come posizione per scambiare i valori dentro l’array a seconda dell’elemento corrente che viene esaminato.
Questo approccio ha una complessita’ computazionale pari a N, perche’ varia in funziona del numero di valori dentro l’array e la complessità relativa alla memoria occupata è pari a 1
Lascio sotto il codice scritto in python su github per mostrare questo approccio.
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.
I Decision Tree o Alberi Decisionali sono uno strumento di apprendimento supervisionato, essi risolvono principalmente tematiche di classificazione o regressione. Sono molto facili da interpretare e da applicare, non basandosi su un modello lineare sono capaci di apprendere anche associazioni non lineari. Funzionano sia su dati numerici che categorici.
I Decision Tree si categorizzano rispetto alla variabile in output come:
Categorical Decision Tree
Continuous Decision Tree
Nella figura seguente si vede un esempio di Decision Tree sul dataset di Iris.
Il nodo principale si chiama Root Node o Radice
Quando un nodo porta a una divisione in rami nei sottonodi l’operazione si chiama Splitting
Quando un nodo si divide in più sottonodi senza arrivare a quello finale, i sottonodi si chiamano Decision Node o Nodo di decisione
Una intera sezione dell’albero si chiama Branch o Ramo
Vantaggi dei Decision Tree
Sono facili da capire: Siccome essi offrono una rappresentazione grafica molto facile da interpretare, i Decision Tree sono anche interpretabili dalla gente non propria del campo informatico.
Utili nell’analisi del dataset: Siccome sono un algoritmo molto veloce e semplice da applicare, è utile applicarlo per vedere le relazioni fra le variabili
Svantaggi dei Decision Tree
Sono proni all’overfitting: È il problema più frequente con i Decision Tree, il metodo migliore per risolverlo è settare dei vincoli o fare Pruning dei rami
Divisione in rami
Il criterio secondo il quale l’algoritmo divide in più rami i vari nodi dell’albero è critico per la precisione deloritmo. Esso poi è differente nel caso si scelga un ambito di regressione o un ambito di classificazione. In base ai criteri disponibili abbiamo i seguenti approcci:
Gini Index (o indice Gini): L’indice Gini dice calcola se gli elementi considerati fanno parte della stessa popolazione. Se la popolazione è pura essi devono essere della stessa classe e la probabilità associata a questo evento è 1 (cioè non contiene elementi di classe diverse)
Chi-Square (o Chi quadrato): L’algoritmo Chi Square si preoccupa di trovare una significanza statistica fra i sotto nodi e il nodo padre. Questa la misuriamo sommando il quadrato delle differenze standardizzate fra i valori osservati e i valori che ci aspettiamo
Information Gain: L’algoritmo Information Gain si basa sul principio di entropia di un insieme di dati, e usa questo per calcolare la divisione in rami.
Riduzione della varianza: Questo algoritmo utilizza la formula della varianza per decidere il migliore modo per dividere i rami, minore è la varianza maggiore è la probabilità che quell’attributo venga usato per dividere i rami
Overfitting
Il problema principale dei Decision Tree è dovuto all’overfitting. Essi arriveranno a fare tante osservazioni, fino ad arrivare a fare una foglia per ogni osservazione e raggiungere quindi il 100% di precisione. Per ridurre questo problema ci sono i seguenti approcci:
Si settano dei vincoli sul numero massimo di foglie o sul numero massimo di nodi finali o sul numero massimo di attributi su cui creare nuove foglie. Allo stesso modo anche sul numero minimo di foglie e sul numero minimo di elementi su cui creare nuove foglie
Si fa il Pruning dei rami, cioè si eliminano i rami possibili, attraverso un approccio greedy. Nella pratica si sceglie la strada che attualmente sembra la migliore e si prosegue con quella finchè non se ne trovano di migliori
Quando usiamo un Decision Tree?
Dovremmo usare un Decision Tree quando c’è una relazione complessa fra i vari attributi che è difficile da spiegare, in questo modo l’approccio non lineare del Decision Tree batte l’approccio lineare della Regressione Lineare ad Esempio. Inoltre un Decision Tree è molto utile se dobbiamo spiegare come si effettua una classificazione ai non addetti ai lavori.
Nel prossimo articolo includerò degli esempi in Python con la libreria Scikit per mostrare una implementazione dei Decision Tree su un dataset di Regioni città e Attrazioni.
Un modo molto semplice di implementare lo Stochastic Gradient Descent nei nostri script è quello di usare l’implementazione di Scikit. La classe SGDClassifier implementa un classificatore che utilizza lo Stochastic Gradient Descent per classificare valori. Il mio script in python applica questo classificatore sul MNIST database, un dataset contente dei numeri scritti a mano e utilizzati come dataset d’esempio nei problemi di classificazione.
Ho utilizzato questo semplice script inoltre per gareggiare su Kaggle alla competizione https://www.kaggle.com/c/digit-recognizer, dove si chiede di scrivere un classificatore di cifre e fare il submit del punteggio.
Questo libro offre una buona introduzione pratica agli algoritmi di machine learning, approfondisce via via nei capitoli tematiche sempre più complesse rimanendo ancorati al codice pur avendo una piccola disgressione matematica.
Di seguito l’esempio del mio Notebook Jupyter dove viene implementato questo approccio.
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.
L’analisi del cluster è un processo in cui si raggruppano insiemi di oggetti in modale tale da creare insiemi di oggetti i cui elementi siano piu’ simili fra loro rispetto agli elementi negli altri gruppi. I gruppi vengono detti Cluster
Il clustering è una tecnica base del data mining e viene usata in altri ambiti molto simili (Machine learning, pattern recognition, analisi immagini,ecc)
Per Clustering Gerarchico (Hierarchical Clustering) si intende un metodo di analisi dei cluster che vuole ottenere gerarchie di cluster. Si può effettuare in due modi:
Agglomerativo: Si parte dai dati singoli e si uniscono via via i cluster
Divisorio: Si parte da un unico cluster e si dividono via via
Per capire quale cluster va diviso o unito si fa riferimento alla metrica, cioè una misura di similarità o dissimilarità, la metrica viene usata come distanza fra le coppie.
Le metriche (Metric) sono influenzate dal tipo di dati che abbiamo, esse possono essere:
Distanza Euclidea
Distanza Euclidea Quadra
Distanza di Manhattan
Distanza Massima
Distanza di Mahalanobis
Distanza di Hamming
Distanza di Levenshtein
Per capire invece quando degli insiemi vanno uniti si usano i Criteri di Collegamento (Linkage Criteria). I criteri di collegamento vengono effettuati basandosi sulle distanze fra gli elementi dei cluster e fanno capire se occorre unire i cluster o meno. I criteri sono:
Collegamento Singolo (Single Linkage): la distanza di collegamento fra due cluster viene definita come la distanza minima fra i due elementi del cluster
Collegamento completo (Complete Linkage): la distanza di collegamento fra due cluster viene definita come la distanza massima fra i due elementi del cluster
Collegamento Medio (Average Linkage): la distanza di collegamento fra due cluster viene definita come la distanza media fra tutti i punti del cluster con tutti gli altri punti del cluster
Nel prossimo articolo illustrerò un esempio di clustering gerarchico con codice in Python!
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.
