di ·0 commenti

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.

di ·0 commenti

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.

di ·0 commenti

Mining of Massive Datasets è un libro scritto da Jure Leskovec, Anand Rajaraman, Jeff Ullman basato sul corso di studi tenuto a Stanford riguardante il Data Mining.

Ogni lezione è poi corredata sul web da dei video presenti su Youtube che spiegano le tematiche dei capitoli, la qualità del corso è molto alta e sono facili da seguire.

Capitoli del libro

Il libro è diviso nei seguenti Capitoli:

  • Data Mining: Il capitolo è una introduzione al libro, parla degli aspetti dei Big Data, del perchè si fa data mining, delle sfide e dei problemi.
  • Map-Reduce and the new Software Stack: Questo capitolo parla di Map-Reduce, del perchè è stato inventato questo approccio, quanto si riesce ad essere più performanti, del perchè è stato inventato in Google e dei problemi che va a risolvere. Si parla inoltre dei sistemi Opensource che implementano MapReduce fra cui Hadoop.
  • Finding Similar Items: Questo capitolo parla di come misurare i dati, cioè di come decidere delle distanze fra i dati e permettere di capire quanto due dati generici possano essere uguali. Tratta delle distanze classiche fra numeri e stringhe e dell’hashing per trovare i dati similin.
  • Mining Data Streams: Questo capitolo tratta degli Stream e come fare Sampling, contare elementi distinti, applicare il Bloom Filter, stimare i Momenti, stimare il numero di elementi in una finestra temporale.
  • Link Analysis: Questo capitolo parla di PageRank, dell’implementazione e il modello su cui si basa, il rischio di avere attacchi spam che possano deviare il risultato di PageRank delle pagine e i metodi per evitare questo tipo di attacchi.
  • Frequent Itemsets: Questo capitolo parla degli insiemi di oggetti frequenti e delle regole di associazione, spiega inoltre l’algoritmo A-Priori e l’algoritmo PCY con ulteriori spunti.
  • Clustering: Questo capitolo tratta il clustering, sia gerarchico che non, esplorando gli algoritmi KMeans, BFR, Cure
  • Advertising on the Web: Questo capitolo tratta del problema della pubblicità sul web, cioè come fare linking fra annunci e oggetti e migliore offerta sulla pubblicità in quel momento.
  • Recommendation Systems: Questo capitolo parla dei sistemi di raccomandazione esponendo quale è il problema della raccomandazione e come si tenta di risolverlo tramite un approccio semantico basato sui tag o tramite un approccio sulle relazioni fra gli oggetti basato sull’algebra lineare
  • Mining Social Network Graphs: Questo capitolo parla delle connessioni nei social network e nelle community applicando algoritmi e rappresentazioni.
  • Dimensionality Reduction: Questo capitolo parla della riduzione delle dimensioni in un dataset e di come applicare la decomposizione SVD e la decomposizione CUR al nostro dataset.
  • Large-Scale Machine Learning: Questo capitolo spiega i concetti di Training Set, Test Set, allenamento in batch o online, e algoritmi classici di machine learning come il Perceptron, le reti neurali e il Nearest-Neighbor

Perchè dovrei leggerlo?

Questo libro esplora le basi del data mining e del machine learning, fornendo le nozioni per argomento via via più complessi. E’ di per sé un libro teorico universitario, non si troverà codice, ma solo pseudo codice e ottime spiegazioni. Il libro inoltre non si perde in teoria inutile, ma va dritto al punto fornendo però il contesto adatto. Ogni algoritmo trattato nel libro può essere poi trovato implementato facilmente online da altri programmatori.

Link

Il corso video si può trovare su youtube:
https://www.youtube.com/channel/UC_Oao2FYkLAUlUVkBfze4jg/videos 

Il libro e le slide invece sono disponibili gratuitamente qui nella versione 2:
http://www.mmds.org/

Nel caso vogliate acquistare invece il libro è possibile comprarlo su amazon al link:

Mining of Massive Datasets

di ·0 commenti

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.



Loading

Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.

view raw

clustering.ipynb

hosted with ❤ by GitHub

di ·0 commenti

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:


L[1] = Genera gli elementi di dimensione 1
Calcola la frequenza degli elementi di dimensione 1 che superano minsup
C[1] = L[1]
Per K=2, finchè L[K-1] != vuoto; k++ {
C[K] = genera le coppie da L[K-1] con cardinalità K
L[K] = Calcola la frequenza degli elementi in C[K] che superano minsup
}
Ritorna L[K]

view raw

gistfile1.txt

hosted with ❤ by GitHub

Il pattern con cui ci muoviamo è quindi questo:
Schermata del 2017-08-22 19-28-54

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.


package main
import (
"github.com/deckarep/golang-set"
"strings"
"fmt"
"sort"
)
func main() {
dataset := [][]string{
[]string{"pane", "cereali", },
[]string{"pane", "latte", "caffè"},
[]string{"latte", "cereali"},
[]string{"latte", "caffè"},
[]string{"pane", "latte", "cereali"},
[]string{"latte", "cereali"},
[]string{"pane", "cereali"},
[]string{"pane", "latte", "te"},
[]string{"pane", "latte", "cereali", "te"},
[]string{"pane", "te"},
[]string{"pane","caffè"},
}
minimumSupport := 0.4
minConfidence := 0.2
apriori(dataset, minimumSupport, minConfidence)
}
func apriori(dataset [][]string, support float64, confidence float64) {
elements := elements(dataset)
freqSet := make(map[string]float64)
largeSet := make(map[int]mapset.Set)
oneCSet := returnItemsWithMinSupport(elements, dataset, support, &freqSet)
currentLSet := oneCSet
k := 2
for currentLSet.Cardinality() != 0 {
largeSet[k-1] = currentLSet
currentLSet = joinSet(currentLSet, k)
currentCSet := returnItemsWithMinSupport(currentLSet, dataset, support, &freqSet)
currentLSet = currentCSet
k = k + 1
}
fmt.Println(largeSet)
}
func returnItemsWithMinSupport(itemSet mapset.Set, dataset [][]string, minSupport float64, freqSet *map[string]float64) mapset.Set {
localItemSet := mapset.NewSet()
localSet := make(map[string]float64)
for _, item := range (itemSet.ToSlice()) {
dkey := strings.Split(item.(string), "-")
sort.Strings(dkey)
for _, line := range(dataset) {
if contains(line, dkey) {
key := strings.Join(dkey, "-")
(*freqSet)[key] += 1.0
localSet[key] += 1.0
}
}
}
for item, count := range (localSet) {
support := count / float64(len(dataset))
if support >= minSupport {
localItemSet.Add(item)
}
}
return localItemSet
}
func joinSet(itemSet mapset.Set, length int) mapset.Set {
ret := mapset.NewSet()
for _, i := range (itemSet.ToSlice()) {
for _, j := range (itemSet.ToSlice()) {
i := i.(string)
j := j.(string)
i_a := strings.Split(i, "-")
j_a := strings.Split(j, "-")
dkey := (union(i_a, j_a))
if len(dkey) == length {
sort.Strings(dkey)
key := strings.Join(dkey, "-")
ret.Add(key)
}
}
}
return ret
}
func union(a []string, b []string) []string {
ret := mapset.NewSet()
for _, v := range (a) {
ret.Add(v)
}
for _, v := range (b) {
ret.Add(v)
}
rets := []string{}
for _, v := range (ret.ToSlice()) {
rets = append(rets, v.(string))
}
return rets
}
func elements(dataset [][]string) mapset.Set {
ret := mapset.NewSet()
for i := 0; i < len(dataset); i++ {
for j := 0; j < len(dataset[i]); j++ {
if ret.Contains(dataset[i][j]) == false {
ret.Add(dataset[i][j])
}
}
}
return ret
}
func contains_dataset(s [][]string, e []string) bool {
ret := false
for _, v := range (s) {
ret = contains(v, e)
if ret == true {
break
}
}
return ret
}
func contains_element(s []string, e string) bool {
ret := false
for _, a := range s {
if a == e {
ret = true
break
}
}
return ret
}
func contains(s []string, e []string) bool {
count := 0
if len(s) < len(e) {
return false
}
mm := make(map[string]bool)
for _, a := range e {
mm[a] = true
}
for _, a := range s {
if _, ok := mm[a]; ok {
count += 1
}
}
return count == len(e)
}

view raw

Apriori.go

hosted with ❤ by GitHub

Limitazioni di A-Priori

  • È 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.