Dal materiale didattico dei seguenti corsi:

1. Social Media Management - Prof. Antonino Furnari - aa 2020/21
2. Introduzione al Data Mining - Prof. Alfredo Ferro, Prof. Giovanni Micale - aa 2020/21
3. Big Data - Prof. Alfredo Pulvirenti -- aa 2020/21

Dipartimento di matematica e informatica - UniCT

Appunti a cura di Lemuel Puglisi.

Referenze:

• Bishop, Christopher M. Pattern recognition and machine learning;
• Z. Aston Zhang, Zachary Lipton, Mu Li, Alexander Smola, Dive into Deep Learning;

Data mining

1. Introduzione

Il data mining consiste nell'estrazione di regolarità da grandi quantità di dati attraverso analisi, talvolta complesse, ed algoritmi efficienti e scalabili. Le informazioni cercate possono essere di vario genere:

• Dipendenze tra dati
• Individuazione di classi (cluster)
• Descrizione delle classi (cluster)
• Individuazione di outliers / eccezioni

Le aree applicative di tali studi sono generalmente l'analisi ed il supporto alle decisioni. Tuttavia, il target include anche text mining, analisi del web, intelligent query answering etc.

2. Market Basket Analysis

Per introdurre il concetto di regole associative, presentiamo una applicazione paradigmatica di esse: il Market Basket Analysis (MBA). Supponiamo di avere un insieme di oggetti (items) ed un insieme di carrelli (baskets) che correlano gli oggetti tra loro. L' MBA trova la correlazione tra gli oggetti studiando la relazione molti-a-molti con i carrelli. Tale tecnologia si concentra su eventi comuni anziché rari (outliers).

Ipotizziamo di voler trovare l'insieme di oggetti che appare frequentemente all'interno dei carrelli. Sia I l'insieme di oggetti (Itemset), definiamo il supporto (Support) per I come il numero di carrelli contenenti tutti gli oggetti di I. A volte il supporto è espresso in percentuale (relativamente al numero di carrelli totali). Sia s la soglia o support threshold, definiamo insiemi frequenti gli insiemi che appaino in almeno s carrelli.

2.1 Applicazione 1 - Supermercato

Ipotizziamo che i prodotti di un supermercato siano gli oggetti e gli scontrini siano i carrelli, poiché mettono in relazione gli oggetti tra di loro. Una delle possibili applicazioni consiste nel trovare quali sono i prodotti acquistati insieme più frequentemente dai clienti. Una ricerca effettuata in America ha prodotto come risultato la correlazione tra pannolini e birra. Una volta estratta la correlazione, è possibile scontare il prezzo dei pannolini ed aumentare quello della birra (facendo attenzione al verso di acquisto, che in questo caso è pannolini > birra).

2.2 Applicazione 2 - Plagiarism detection

Ipotizziamo che dei documenti testuali siano gli oggetti e che delle frasi siano i carrelli. Più documenti possono contenere la stessa frase, per cui connettono gli oggetti tra loro. È possibile notare come i carrelli non debbano necessariamente contenere gli oggetti, bensì correlarli in qualche modo tra loro. L'obiettivo della computazione potrebbe essere quello di scoprire dei plagi attravero documenti che compaiono spesso insieme, ovvero che formino un insieme frequente.

2.3 Applicazione 3 - Web analysis

Ipotizziamo che delle parole siano gli oggetti e che le pagine web siano i carrelli, poichè esse contengono le parole e le mettono in relazione. Parole che appaiono frequentemente insieme nelle pagine web potrebbero indicare una interessante relazione. Affronteremo nel cap. 13 alcuni cenni di analisi testuale.

3. Regole associative

Le regole associative sono regole del tipo se-allora (if-then) sul contenuto dei basket e sono della forma: $$\{i_1,i_2,...,i_k\}\to j$$ ovvero: "Se il basket contiene gli oggetti $i_1,...,i_k$ allora molto probabilmente conterrà anche $j$". Definiamo la confidenza (confidence) di una regola di associazione come la probabilità di $j$ dati $i_1,...,i_k$.

3.1 Trovare le regole di associazione

Supponiamo di voler trovare tutte le regole di associazione tali che abbiano un supporto maggiore di s ed una confidenza maggiore di c. Si noti che per supporto si intende il supporto dell'itemset alla sinistra della regola. La parte computazionalmente difficile ed onerosa sta nel trovare gli insiemi frequenti.

Osservazione: $$\{i_1,...,i_k\}\to \text{j has high support and high confidence}⟹\{i_1,...,i_k\}\text{ and }\{i_1,...,i_k,j\}\text{ will be frequent}$$

3.2 Problemi pratici

Tipicamente i file contenenti i dati sono memorizzati nel disco (es. flat files, database). Data la massiva cardinalità dei dati, il costo principale degli algoritmi è dato dal numero di letture da disco.

4. Algoritmi di ricerca di coppie frequenti

Analizzando un algoritmo di ricerca degli insiemi frequenti, scoviamo subito che il costo principale è quello di cercare tra tutte le coppie: con 10^k elementi, le coppie sono circa 10^k*2 elementi. In generale, dato l'insieme $I$ formato da $d$ elementi, l'insieme delle parti (power set) ha cardinalità $2^d$, ovvero si avranno $2^d$ itemset da analizzare, per cui la ricerca esaustiva prenderebbe tempo esponenziale $O(2^n)$. Vedremo che sarà meno oneroso il compito di cercare triple, quadruple etc.

In generale: la probabilità di essere insiemi frequenti diminuisce esponenzialmente all'aumentare della dimensione della tupla. Il perché è dimostrabile in termini probabilistici. Vediamo adesso alcuni algoritmi che si occupano della ricerca di coppie frequenti.

4.1 Naive algorithm

L'algoritmo naive legge una sola volta l'intero file e, per ogni basket contenente $n$ elementi, genera $\frac{n(n-1)}{2}$ coppie da analizzare. Il numero di coppie è dato dalle combinazioni degli $n$ item in 2 posizioni, calcolabile attraverso il coefficiente binomiale: $$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n!}{2!(n-2)!}=\frac{n(n-1)(n-2)!}{2(n-2)!}=\frac{n(n-1)}{2}$$ Definiamo una struttura apposita (es. una matrice) che contenga tutti gli item sia nelle righe che nelle colonne. Per ogni coppia di item all'interno del basket incrementa l'occorrenza della coppia nella struttura. Tale algoritmo fallisce se ${\text{(\#items)}}^2$ provoca un overflow in memoria primaria (gli item potrebbero essere dell'ordine dei miliardi). Supponiamo vi siano 10⁵ elementi in memoria e quindi: $$\frac{10^5\ast (10^5-1)}{2}\simeq 5\ast 10^{9}pairs$$ Saranno necessari circa 20 GB di memoria primaria. Vi sono 2 approcci tipici al conteggio delle occorrenze delle coppie: la matrice triangolare e la tabella di triple.

4.1.1 Matrice triangolare

Tale approccio consiste nel contare tutte le coppie attraverso una matrice triangolare. Supponendo che la matrice sia composta da interi, essa richiede 4 byte per paio. Supponiamo che le coppie vengano così considerate: $$\begin{gathered} (1,2),(1,3),...,(1,n)//n-1pairs \\ (2,3),(2,4),...,(2,n)//n-2pairs \\ (i-1,i),(i-1,i+1),...,(i-1,n)//n-(i-1)pairs \end{gathered}$$ Dati gli indici i,j è possibile effettuare una linearizzazione delle posizioni, sfruttando un array monodimensionale di dimensione n(n-1)/2 anziché una matrice. Nello specifico: $$(i,j)=k=(i-1)(n-\frac{i}{2})+j-i$$

4.1.2 Tabella di triple

Un altro approccio consiste nel contare solo le coppie effettivamente presenti nei basket, quindi tenere una tripla di valori (i, j, c) tale che la coppia {i,j} abbia c occorrenze, con c > 0. Ogni tripla richiede 12 bytes, ma non tutte le coppie sono presenti in memoria. Tale approccio risulta conveniente rispetto alla matrice solo se occorrono al più 1/3 delle coppie totali, a causa del triplo della memoria utilizzata per ogni coppia (12 byte rispetto ai 4 della matrice). Potrebbe servire ulteriore spazio per strutture che facilitano l'accesso alla tabella, come delle hash table.

4.2 A-Priori Algorithm

L'algoritmo a-priori è diviso in due passaggi principali e limita la necessità di memoria primaria. L'idea principale è quella della monotonicità (monotonicity): se un insieme S di item appare almeno k volte, allora anche tutti i sottoinsiemi di S appaiono almeno k volte.

Contropositivo per le coppie: Se un item i non appare in almeno s basket, allora nessuna coppia contenente i potrà apparire in almeno s basket.

Passo 1: Leggere tutti i basket e contare in memoria principale le occorrenze di ogni item. Questo passaggio richiede che la memoria sia almeno proporzionale al numero di item. Consideriamo item frequenti (frequent items) gli item che compaiono almeno s volte.

Passo 2: Leggere nuovamente i basket, ma contare in memoria principale solo le coppie formate dagli elementi frequenti trovati al passo 1. Tale passo richiede una memoria proporzionale al quadrato del numero di elementi frequenti, più una lista degli elementi frequenti.

È possibile utilizzare una matrice triangolare che referenzia solo gli item frequenti (o utilizzare il metodo delle triple). La mappatura degli item frequenti nella matrice sarà diversa da quella originale, per questo è consigliato tenere una tabella che ricolleghi gli indici della matrice con quelli originali.

Supponiamo di voler trovare tuple di item di ordine k maggiore al secondo. Per ogni k consideriamo due insiemi:

• C_k = itemset di cardinalità k candidati ad essere frequenti, ovvero con un supporto > s, basandosi sulle informazioni degli itemset di cardinalità k-1.
• L_k = itemset di cardinalità k effettivamente frequenti.

A partire dall'insieme C₁ di tutti gli item viene svolto il primo passo dell'algoritmo e prodotto l'insieme L₁ degli item frequenti. Da quest'ultimo, viene costruito l'insieme delle coppie C2 ed un secondo filtraggio produce gli insiemi frequenti di cardinalità 2 L2. Lo stesso procedimento viene eseguito per k=3, 4, ... e si può dimostrare che all'aumentare di k, l'algoritmo tende ad andare a convergenza più velocemente (in maniera esponenziale).

Per dati tipici nel MBA e un supporto richiesto dell'1%, k=2 richiede la maggior parte della memoria.

Osservazioni:

• C1 rappresenta tutti gli elementi
• Lk è composto da membri di Ck il cui supporto è > s
• Ck+1 è composto da insiemi in cui esiste un sottoinsieme residente in Lk

Clustering

1. Introduzione

Il clustering è un processo che consiste nel raggruppare un insieme di oggetti in gruppi detti cluster, sulla base di una nozione di distanza tra gli oggetti. L'obiettivo del clustering è quello di raggruppare nello stesso cluster oggetti "simili" tra loro (o con bassa distanza reciproca) e in cluster diversi oggetti "dissimili" tra loro (o ad elevata distanza).

1.1 Unsupervised learning

Il clustering è un processo di unsupervised learning (apprendimento non supervisionato): si vuole suddividere un insieme di dati in n classi (o cluster) senza alcuna conoscenza a-priori di quante e quali siano le classi e le loro etichette.

Esistono invece dei task, come la classificazione o la predizione, che necessitano di un apprendimento supervisionato (supervised learning). Partendo da un training set essi allenano un modello in grado di classificare nuovi dati o predire valori.

2. Spazi metrici e funzione distanza

Gli oggetti da raggruppare rappresentano punti appartenenti ad uno spazio metrico, cioè uno spazio in cui è definita una funzione distanza D. La definizione di una funzione distanza è cruciale per effettuare il clustering. Una funzione D definita su una coppia di punti di uno spazio metrico S è una misura di distanza se soddisfa le seguenti proprietà:

$\text{1) }D(X,Y)\ge 0\forall X,Y\in SeD(X,Y)=0⟺X=Y$ $\text{2) simmetria: }D(X,Y)=D(Y,X)\forall X,Y\in S$ $\text{3) prop. triangolare: }D(X,Y)+D(Y,Z)\ge D(X,Z)\forall X,Y,Z\in S$

2.1 Spazio euclideo

L'esempio più comune di spazio metrico è lo spazio euclideo ad n dimensioni ${\mathbb{R}}^n$, in cui i punti dello spazio sono vettori di numeri reali. La quantità n rappresenta il numero di dimensioni dello spazio. Le componenti dei vettori sono comunemente chiamate coordinate dei corrispondenti punti. Nelle applicazioni reali, le coordinate rappresentano gli attributi (o "features") degli oggetti dello spazio metrico. Una proprietà caratteristica degli spazi euclidei è che la media di un insieme di punti nello spazio è sempre definita ed è un punto nello spazio, chiamato centroide o centro geometrico. Di seguito è riportato un esempio di oggetti (cani) classificati in uno spazio euclideo a 2 dimensioni, secondo 2 attributi: altezza e peso.

2.1.1 Distanze nello spazio Euclideo

Nello spazio euclideo è possibile definire diverse misure di distanza valide (che rispettino le 3 proprietà). La funzione distanza più utilizzata è la distanza euclidea: Siano $x=(x_1,...,x_n)$ e $y=(y_1,...,y_n)$ due punti nello spazio ${\mathbb{R}}^n$, la distanza euclidea è così definita: $$D(x,y)=\sqrt{\sum _{i=1}^n(x_i-y_i{)}^2}$$

Esistono altri tipi di distanze, come la distanza di Manhattan $$D(x,y)=\sum _{i=1}^n|x_i-y_i|$$ La norma $Lr$ è una generalizzazione della distanza euclidea dove sia la radice che l'esponente assumono un valore r, anziché 2: $$D(x,y)=\sqrt[r]{\sum _{i=1}^n(x_i-y_i{)}^r}$$ La norma $L_{\infty }$ prende la distanza massima tra le componenti delle n dimensioni: $$D(x,y)=\underset{1\le i\le n}{\max }|x_i-y_i|$$ La distanza del coseno misura la distanza dal punto di vista angolare: $$D(x,y)=\arccos \frac{{\sum }_{i=1}^n{x}_i\ast y_i}{\sqrt{{\sum }_{i=1}^n{x}_i^2}\sqrt{{\sum }_{i=1}^n{y}_i^2}}$$

2.2 Spazi non euclidei

In uno spazio non euclideo il concetto di centroide non è definito. Tuttavia, si può definire il concetto di 1-mediana come un punto che minimizza la distanza media (o equivalentemente la somma) delle distanza degli altri punti dell'insieme. Esempi di spazi non euclidei sono spazi in cui gli oggetti sono insiemi o stringhe.

Per alcuni spazi non euclidei (come le versioni discrete degli spazi euclidei, o spazi formati da vettori di interi) è possibile utilizzare le distanze euclidee già viste. Nel caso più generale occorre definire metriche alternative.

Es. con insiemi, distanza di Jaccard: Dati due insiemi T ed S, la distanza è definita come il complementare del rapporto tra la cardinalità dell'intersezione e la cardinalità dell'unione. $$D(S,T)=1-\frac{|S\cap T|}{|S\cup T|}$$

2.2.1 Dim. Distanza di Jaccard e proprietà triangolare

Dimostriamo che la distanza di Jaccard rispetta la proprietà triangolare: $$D(S_1,S_2)+D(S_2,S_3)=(1-\frac{|S_1\cap S_2|}{|S_1\cup S_2|})+(1-\frac{|S_2\cap S_3|}{|S_2\cup S_3|})$$ Dato che $S_1\cup S_2$ ha cardinalità minore di $U=S_1\cup S_2\cup S_3$, possiamo maggiorare l'espressione come segue: $$\begin{gathered} \frac{|T_1|+|T_2|}{|S_1\cup S_2|}+\frac{|T_2|+|T_3|}{|S_2\cup S_3|}\ge \frac{|T_1|+|T_2|}{|U|}+\frac{|T_2|+|T_3|}{|U|}= \\ \frac{|T_1|+2|T_2|+|T_3|}{|U|}\ge \frac{|T_1|+|T_2|+|T_3|}{|U|}=1-\frac{|V|}{|U|}\ge D(S_1,S_3) \end{gathered}$$ Per cui la proprietà risulta dimostrata.

2.2.2 Distanza di Edit e distanza di Hamming

Distanza di edit: date due stringhe x e y, la distanza di edit è il minimo numero di operazioni di cancellazione e inserzione da effettuare partendo da x per ottenere y.

    x = "abcde"
    y = "acfdeg"
    #1 cancella b => acde 
    #2 inserisci f dopo c => acfde
    #3 inserisci g dopo e => acfdeg
    D(x,y) = 3

Distanza di Hamming è il numero di componenti in corrispondenza delle quali x e y differiscono. Vediamo un esempio: $$\begin{gathered} x=[1,0,0] \\ y=[1,0,1] \\ D(x,y)=1 \end{gathered}$$ Poiché differisce solo la terza componente.

3. Tassonomie degli algoritmi di clustering

Una classificazione degli algoritmi di clustering si basa sull'approccio utilizzato.

1) Metodi gerarchici o agglomerativi Ciascun punto viene inizialmente posto in un cluster diverso e successivamente i cluster vengono combinati tra loro secondo una nozione di vicinanza definita opportunamente. Il processo di aggregazione di cluster termina sulla base di un opportuno criterio di terminazione (es. raggiungimento di un numero di cluster desiderati).

2) Metodi di partizionamento L'insieme di punti viene partizionato in k cluster, in modo che ciascun punto appartenga ad uno e un solo cluster. Dopo aver stimato dei cluster iniziali, i punti vengono presi in considerazione seguendo un certo ordine e assegnati al cluster più adatto. Alcune varianti permettono di non assegnare un punto a nessun cluster se questo è un outlier (cioè è isolato e lontano dai vari cluster). Rappresentanti di questa categoria sono gli algoritmi k-means.

3) Metodi basati sulla densità I cluster prodotti inizialmente vengono estesi fino a quando la densità (ovvero il numero di punti) in un intorno più o meno grande supera una certa soglia. Tali metodi sono in grado di rilevare outlier e cluster di qualunque forma (non solo sferica come nel partizionamento). Esempi di questa classe sono DBSCAN e OPTICS.

4) Metodi basati sulla griglia Lo spazio viene quantizzato in un numero finito di celle che formano una struttura a griglia. Tutte le operazioni di clustering vengono quindi effettuate sullo spazio quantizzato, garantendo un tempo di elaborazione veloce, dipendente principalmente dal numero di celle di ogni dimensione dello spazio quantizzato. Un esempio è l'algoritmo STING.

5) Metodi basati sul modello Si ipotizza un modello per ogni cluster e si trova la migliore dispozione dei dati rispetto al determinato modello. Esempi di questa categoria sono gli algoritmi EM, COBWEB e SOM.

Altri criteri non meno importanti per distinguere gli algoritmi di clustering sono i tipi di spazio metrico e l'utilizzo della memoria secondaria.

4. Problema della dimensionalità

Spesso si ha a che fare con spazi ad elevata dimensione ed oggetti da clusterizzare con molti attributi. In spazi euclidei ad elevata dimensionalità si osservano delle proprietà interessanti e poco intuitive, riassunte con i termine <<curse of dimensionality>> (o problema della dimensionalità). Queste proprietà rendono molto più complicato il clustering.

Es. Se in un insieme di oggetti avessimo tanti attributi booleani rispetto ad un grande insieme di colori, e pochi attributi realmente rilevanti, la distanza di Hamming tra due oggetti tenderebbe alla dimensione di questi. Ogni oggetto sarebbe pressappoco equidistante dagli altri e formerebbe un cluster assestante. È importante quindi selezionare poche features discriminanti.

Al crescere del numero di features, il numero di dati necessari a rendere il clustering effettivamente utile aumenta in maniera esponenziale.

In generale, quasi tutte le coppie di punti in un insieme finito, definito in uno spazio con moltissime dimensioni, saranno equidistanti tra loro.

4.1 Distribuzione delle distanze in spazi ad alta dimensionalità

Consideriamo $n$ valori $d$-dimensionali; supponiamo che le componenti varino casualmente nel range $[0,1]$. Supponiamo che $d$ sia molto grande e misuriamo la distanza tra i punti attraverso la distanza euclidea. Siano $x=(x_1,...,x_d)$ e $y=(y_1,...,y_d)$ due punti, la distanza è calcolata come segue $$D(x,y)=\sqrt{\sum _{i=1}^d(x_i-y_i{)}^2}$$ Essendo $d$ molto grande, con alta probabilità vi saranno due componenti la cui differenza sarà molto vicina ad 1, quindi il limite inferiore della distanza sarà circa 1. Nel caso limite in cui tutte le componenti differiscano di 1, allora il limite superiore della distanza sarà $\sqrt{d}$. La maggior parte dei punti avrà una distanza vicina alla media tra i due limiti. Se non vi punti vicini risulta complesso il raggruppamento in cluster.

4.2 Fattori chiave per gli algoritmi di clustering

In generale, non esiste un algoritmo di clustering migliore degli altri. La bontà di un algoritmo è legata a diversi fattori, non tutti necessariamente indispensabili per l'applicazione in esame:

• Scalabilità
• Capacità di trattare diversi tipi di attributi
• Capacità di cercare cluster di forma diversa
• Facilità nell'uso e nella comprensione dei parametri in input
• Capacità di gestire dati con outlier e rumore
• Insensibilità all'ordine dei record o all'esaminazione
• Capacità di gestire dati ad alta dimensionalità
• Interpretabilità e usabilità dei risultati ottenuti

5. Algoritmo di clustering gerarchico

Il clustering gerarchico è un metodo di analisi dei cluster che costruisce una gerarchia di cluster. Le caratteristiche salienti del clustering gerarchico sono riassumibili nei seguenti punti:

• Assegnare a ciascun punto un cluster separato.
• Unire i cluster più vicini in un unico cluster.
• Ripetere il secondo passo sino a quando non si è soddisfatto un criterio di terminazione.

Le domande chiave da porsi sono:

• Come rappresentare ciascun cluster?
• Come scegliere quali cluster unire e come definire la vicinanza tra cluster?
• Quale criterio di terminazione scegliere?

5.1 Rappresentazione dei cluster

Iniziamo considerando il caso degli spazi Euclidei: il cluster potrebbe essere rappresentato dal centroide (media o baricentro di tutti i punti del cluster). Il centroide è un punto nello spazio ma, in generale, non corrisponde ad un punto del cluster. Se viene scelto il centroide come rappresentante del cluster, un buon criterio per misurare la distanza tra i cluster consiste nel misurare la distanza dai relativi centroidi. L'algoritmo sceglierà ad ogni passo i due cluster la cui distanza tra i rispettivi centroidi è minima. Ogni qual volta vengono fusi due cluster, viene ricalcolato il centroide del cluster risultante.

5.1.1 Dendogramma

Al clustering gerarchico viene spesso associato un dendogramma, che descrive in che modo i cluster sono stati via via combinati. Tagliando il dendogramma ad un certo livello, i sottoalberi ottenuti rappresentano i cluster prodotti dall'algoritmo in un certo istante di computazione.

5.2 Criteri di terminazione

Elenchiamo alcuni criteri di terminazione comuni:

• Supponendo di conoscere a priori il numero di cluster da ottenere, si termina l'algoritmo quando si ottiene il numero desiderato.
• Si procede sino a concludere il dendogramma per intero. Ciò è utile in contesti in cui il concetto di distanza riflette il concetto di evoluzione ed il dendogramma descrive rapporti evolutivi (es. nel confronto di genomi di specie diverse).
• Si termina l'algoritmo nel momento in cui la fusione di due cluster produce un cluster inadeguato (es. la distanza media dei punti dei cluster dai rispettivi centroidi cresce troppo, allora i cluster erano lontani tra loro, pur avendo la distanza minima tra tutti ).

5.3 Misure alternative di distanza tra cluster

Altre misure di distanza tra cluster che non includano i centrodi sono le seguenti:

• Single link: la distanza minima tra due punti in due cluster X ed Y.
• Complete link: la distanza massima tra due punti un due cluster X ed Y.
• Average link: la distanza media tra le distanze di tutti i punti di X con tutti i punti di Y.

5.3.1 Medoid distance

Un elemento interessante per calcolare la distanza tra cluster potrebbe essere il medoide (o 1-mediana), ovvero il punto del cluster tale che la somma delle distanze degli altri punti del cluster ad esso è minima. A differenza del centroide, il medoide è sempre un punto del cluster. A questo punto, la medoid distance è la distanza tra due cluster X e Y data dalla distanza tra i medoidi di X e Y.

5.4 Complessità del clustering gerarchico

Prendiamo come esempio il seguente pseudo-codice:

clusters = getClusterFromPoints(initialData)
while (terminationCriteria() == True): 
    
    # starting point 
    minimumDistance = calculateDistance(clusters[0], clusters[1])
    minCluster_a = clusters[0]
    minCluster_b = clusters[1]

    # calculate minimimum distance 
    for currentCluster in clusters: 
        for iterationCluster in clusters: 
            tempDistance = calculateDistance(currentCluster, iterationCluster)
            if (tempDistance < minimumDistance):
                minCluster_a = currentCluster
                minCluster_b = iterationCluster
                minimumDistance = tempDistance

    # add the new cluster 
    clusters.remove(minCluster_a)
    clusters.remove(minCluster_b)
    newCluster = createCluster(minCluster_a, minCluster_b)
    clusters.append(newCluster)
    

Ad ogni passo l'algoritmo deve calcolare la distanza tra ogni coppia di cluster e scegliere la coppia migliore da unire. Il passo iniziale ha complessità $O(n^2)$, i successivi passi dovranno analizzare di volta in volta un cluster in meno, per cui avranno un tempo proporzionale a $O((n-1{)}^2)$, $O((n-2{)}^2)$ ... etc.

Se l'algoritmo procede sino alla fine, dovrà ripetere n passi (iterazioni) prima che si raggiunga un unico grande cluster. Di conseguenza la complessità finale dell'algoritmo è $O(n^3)$. L'algoritmo risulta quindi poco adatto a clusterizzare grandi quantità di dati.

È possibile ridurre leggermente la complessità dell'algoritmo da $O(n^3)$ a $O(n^{2}logn)$ usando le code di priorità. La coda di priorità è una struttura dati che permette di ottenere il minimo in un insieme di valori in tempo costante e consente inserimenti e cancellazioni in tempo $O(logn)$.

In tal caso, ad ogni iterazione l'algoritmo:

• Troverà la distanza minima tra cluster in tempo costante e i due cluster relativi
• Eliminerà le distanze relative ai due cluster selezionati dalla coda (max. 2n cancellazioni)
• Creerà un nuovo cluster fondendo i precedenti
• Calcolerà le distanze tra i cluster esistenti ed il nuovo cluster, aggiungendole alla coda (al più n inserimenti)

Sia il passo 2 che il passo 4 hanno complessità $O(nlogn)$. Nonostante le ottimizzazioni, il clustering gerarchico resta inefficiente per grandi quantità di dati.

5.5 Criteri alternativi di combinazione dei cluster

Anziché scegliere i cluster da combinare attraverso la loro distanza minima (indipendentemente da come essa sia misurata), l'algoritmo potrebbe considerare la coppia di cluster tale che il cluster risultante dalla loro unione abbia raggio o diametro minimo. Definiamo raggio e diametro in un cluster:

• Raggio del cluster: distanza massima tra il centroide e un punto del cluster.
• Diametro del cluster: distanza massima tra due punti qualsiasi del cluster.

Raggio e diametro possono essere utilizzati come parametro di controllo per la terminazione dell'algoritmo, attraverso valori di soglia.

5.6 Clustering agglomerativo e divisivo

Gli algoritmi di clustering gerarchici si dividono in due sottogruppi, a seconda dell'approccio utilizzato per effettuare il clustering:

Clustering agglomerativo È la metodologia precedentemente descritta. Ogni punto forma inizialmente un cluster e ad ogni passo l'algoritmo fonde i due cluster più vicini. È chiamato approccio bottom-up.

Clustering divisivo Tutti i punti appartengono inizialmente ad un cluster. Ad ogni passo un cluster viene suddiviso in due cluster più piccoli a seconda di criteri di ottimalità della separazione. È chiamato anche approccio top-down. Valgono le metriche e i criteri visti precedentemente.

5.7 Clustering gerarchico in spazi non euclidei

Negli spazi non euclidei, il concetto di centroide non è definito. In tal caso, si elegge un punto del cluster rappresentate lo stesso, chiamato clusteroide. Quest'ultimo dovrebbe essere scelto come punto <<centrale>> del cluster (es. potrebbe essere il medoide). Le misure di distanza tra i cluster viste nel caso euclideo, così come i criteri di terminazione, restano validi: basta sostituire nelle definizioni, dove presente, il centroide con il clusteroide.

6. Algoritmo K-means

Con il termine K-means si indica una classe di algoritmi di clustering partizionali basati su assegnamenti di punti. Essi permettono di suddividere un insieme di oggetti in k gruppi sulla base dei loro attributi. Lavorano su spazi euclidei e assumono la conoscenza a-priori del numero di cluster k, che costituisce un iperparametro per l'algoritmo. Sono tuttavia presenti alcune tecniche per dedurre il miglior valore di k attraverso una serie di esperimenti.

6.1 Definizione formale

Fissato k, l'algoritmo prende in input un training set di dati $TR$: $$TR={\left\{x^j\right\}}_j^n{x}_i\in {\mathbb{R}}^n$$ L'obiettivo del k-means è quello di partizionare l'insieme TR in $k$ cluster, il cui contenuto risulta più compatto (o denso) possibile. L'output è quindi una partizione $S$ esprimibile come segue: $$S=\{S_1,...,S_k\}$$ Tale che: $$\forall x^i\exists !S_j\in S:x^i\in S_j$$ Definiremo una funzione $c$ di assegnamento ai cluster: $$c:\{1,...,n\}\to \{1,...,k\}$$ tale che: $$c(i)=j⟺x^i\in S_j$$ Definiremo ${\mu }_j$ il centroide del cluster $S_j$ l'elemento medio: $${\mu }_j=\frac{1}{|S_j|}\times \sum _{x\in S_J}x$$ Il vincolo secondo il quale i cluster debbano essere compatti è misurato attraverso una funzione costo $J(S)$ che, preso in input un determinato partizionamento $S$, calcola la somma della varianza non normalizzata per ogni cluster $S_i\in S$: $$J(S)=\sum _{j=1}^k\sum _{x\in S_j}||x-{\mu }_j|{|}_2^2$$ Il problema dell'algoritmo k-means sta nel trovare la partizione ottimale $\hat{S}$ che minimizzi la funzione $J(S)$.

6.2 Descrizione dell'algoritmo

L'algoritmo è composto da un primo step di inizializzazione ed un altro step di iterazione. Lo step di iterazione si compone di due sotto step, l'assegnamento e l'aggiornamento.

6.2.1 Inizializzazione

• Si scelgono $k$ punti randomici con alta probabilità di finire in cluster differenti
• Si costruiscono $k$ cluster i cui centroidi sono i $k$ punti selezionati.

6.2.2 Iterazione

• Assegnamento: assegna ogni punto al cluster il cui centroide è più vicino

$$c(i)=ar{g}_j\min ||x^i-{\mu }_j|{|}^2$$

• Aggiornamento: calcola la posizione del centroide in ognuno dei cluster $${\mu }_j=\frac{1}{|S_j|}\times \sum _{x\in S_J}x$$

• Vengono ripetuti i primi due passi sino a che non si soddisfa un criterio di terminazione.

6.2.3 Criterio di terminazione

Uno tra i criteri di terminazione più utilizzati consiste nel terminare l'algoritmo quando la differenza tra i valori della funzione costo, tra due iterazioni consecutive, scende al di sotto di una soglia stabilita, ovvero l'algoritmo tende a stabilizzarsi.

6.3 Scelta dei k centroidi iniziali

Per la scelta iniziale dei k punti si potrebbe effettuare il clustering su un piccolo campione di dati (es. utilizzando il clustering gerarchico), fermarsi non appena si ottengono k cluster e utilizzare i punti più vicini ai rispettivi centroidi come i k punti iniziali. Tale approccio è discretamente buono, ma oneroso computazionalmente.

Un approccio alternativo consiste nel selezionare un punto randomicamente dall'insieme e inserirlo in un insieme $S$. Dopodichè aggiungere ad S il punto $P$ che massimizzi la distanza minima di $P$ dai punti in $S$: $$P=\text{arg}\underset{P\notin S}{\max }\left[\underset{x\in S}{\min }D(P,x)\right]$$

Ed iterare il processo sinché $|S|<k$.

6.4 Scelta del valore di k

In molti casi non conosciamo a priori il numero k di cluster attesi. Tuttavia, k è un parametro richiesto dall'algoritmo di cui non possiamo fare a meno (iperparametro, non determinato dall'algoritmo stesso). Occorre quindi eseguire l'algoritmo per diversi valori di k e prendere quello per cui il clustering ottenuto è migliore.

Per misurare la qualità dei cluster, si può far riferimento alla distanza media dei punti dai rispettivi centroidi. Il clustering ottenuto è buono se la distanza media è bassa. Tuttavia:

• All'aumentare di k la distanza media dei punti dai centroidi diminuisce. Essa potrebbe diminuire a tal punto da partizionare un cluster già omogeneo.
• Al diminuire di k la distanza media dei punti dai centroidi aumenta. Di conseguenza potrebbero non essere rilevati alcuni cluster.

Come determinare il valore ideale di k? Osservando il grafico sottostante notiamo che all'aumentare di k, la distanza media dal centroide diminuisce. Il valore ideale di k risiede nel flesso della curva, dove la variazione rallenta.

Nella pratica, l'approccio migliore è dato dalla ricerca binaria nello spazio dei valori di k. Supponiamo che tra due valori x e y assunti dal parametro k ci sia una differenza non trascurabile nella distanza media dai centroidi:

• Prendiamo il valore medio $z=\frac{x+y}{2}$ ed effettuiamo il clustering per $k=z$.
• Se il valore della distanza media dai centroidi è vicino a quello per $k=x$ allora poniamo $y=z$, o viceversa.
• Ripetiamo i passi 1 e 2 sino a quando l'intervallo di ricerca non è sufficientemente piccolo.

6.5 Complessità del k-means

La complessità dell'algoritmo dipende dal numero di iterazioni t e dal numero di cluster k. Generalmente, k e t sono molto più piccoli di n. La complessità risulta essere $O(tkn)$.

Risulta essere più efficiente del clustering gerarchico, ma:

• Spesso converge ad una soluzione localmente ottimale.
• Non è in grado di trovare cluster con forma non convessa o di dimensioni molto diverse.
• È molto sensibile a rumore e outliers: anche in basse quantità, possono influenzare la posizione del centroide.
• Occorre specificare k (eventualmente ricavandolo attraverso ricerche).

<Da wikipedia> In termini di qualità delle soluzioni l'algoritmo non garantisce il raggiungimento dell'ottimo globale: la qualità della soluzione finale dipende largamente dall'insieme di gruppi iniziale e può, in pratica, ottenere una soluzione ben peggiore dell'ottimo globale. Dato che l'algoritmo è di solito estremamente veloce, è possibile applicarlo più volte e scegliere la soluzione più soddisfacente fra quelle prodotte. Un altro svantaggio dell'algoritmo è che esso richiede di scegliere il numero di gruppi k da identificare; se i dati non sono naturalmente partizionati si ottengono risultati strani. Inoltre, l'algoritmo funziona bene solo quando sono individuabili gruppi sferici nei dati.

6.6 K-means su big data

Per clusterizzare grosse quantità di dati in spazi con elevato numero di dimensioni (che non possono risiedere in memoria principale), si utilizzano opportune varianti del K-means, come gli algoritmi BFR e CURE.

L'algoritmo BFR utilizza una rappresentazione compatta dei cluster, riassunti da un insieme di statistiche e valori, e degli insiemi di punti non ancora assegnati ai cluster, per poter effettuare le operazioni di assegnamento direttamente sulla RAM.

L'algoritmo CURE è un estensione del K-means di base per cluster di qualsiasi forma, in cui ogni cluster è descritto da un insieme di punti rappresentativi, che vengono successivamente utilizzati per raffinare gli assegnamenti.

7. Algoritmo density based (DBSCAN)

Il DBscan (Density-Based Spatial Clustering of Applications with Noise) è un algoritmo di clustering basato su densità. Ogni cluster è visto come una regione di punti connessi con densità sufficientemente alta. Per regione densa si intende una regione contenente un numero di punti sufficientemente elevato in un intorno dello spazio sufficientemente limitato.

Il DBscan richiede due iperparametri:

• il raggio $ϵ$ legato alla grandezza dei cluster.
• $MinPts$, che rappresenta il numero minimo di punti che un cluster deve avere.

7.1 Definizione formale

Diamo un paio di definizioni preliminari:

• Definiamo $ϵ$-intorno di un punto Q l'insieme $N_{ϵ}(Q)$ dei punti a distanza al più $ϵ$ da Q.

• Definiamo P punto direttamente raggiungibile per densità da Q, rispetto a $ϵ$ e $MinPts$ se:

  • P appartiene a $N_{ϵ}(Q)$
  • Q è un core-point, ovvero $|N_{ϵ}(Q)|\ge MinPts$

• Definiamo P punto raggiungibile per densità da Q, rispetto a $ϵ$ e $MinPts$, se e solo se esiste una catena di punti $A_1,...,A_n$ con $A_1=Q$ e $A_n=P$ tali che $A_{i+1}$ sia direttamente raggiungibile per densità da $A_i$.

• Definiamo P punto connesso per densità a un punto Q, rispetto a $ϵ$ e $MinPts$, se esiste un punto O tale che sia P che Q siano raggiungibili per densità da O, rispetto a $ϵ$ e $MinPts$,

Un cluster in DBscan è definito come un insieme massimale di punti connessi per densità. Formalmente, se D è l'insieme di tutti i punti da clusterizzare, un cluster C, rispetto a $ϵ$ e $MinPts$, è un sottoinsieme non vuoto di punti di D tale che:

• $\forall P,Q\in D$ se $P\in C$ e $Q$ è raggiungibile per densità da P rispetto a $ϵ$ e $MinPts$, allora $Q\in C$ (Massimalità).
• $\forall P,Q\in C$, P è connesso per densità a Q (Connettività).

7.2 Procedura generale

La procedura generale seguita dal DBSCAN è la seguente:

• Si sceglie un punto random P non ancora visitato.
• Si calcola l'intorno $N_{ϵ}(P)$: se è un core point, allora crea un cluster C e va al passo successivo, altrimenti marca P come outlier o rumore e torna al passo 1.
• Aggiunge P e tutti i punti appartenenti a $N_{ϵ}(P)$ al nuovo cluster C.
• Per ogni punto $X\in N_{ϵ}(P)$, aggiunge ricorsivamente tutti i punti appartenenti a $N_{ϵ}(X)$, ovvero quei punti raggiungibili per densità da P finché possibile.
• Si ripete il passo 1 sino a che tutti i punti non sono stati visitati.

Al termine della procedura, si formeranno diversi cluster e possibili outlier. I punti inizialmente marcati come outlier potrebbero successivamente entrare a far parte di cluster.

7.3 Scelta dei parametri

La scelta dei parametri è basata su euristiche, generalmente si pone $MinPts\ge D+1$, dove D è la dimensione dello spazio. Per ottenere cluster più significativi, conviene assegnare valori tanto più alti del valore minimo D+1 per $MinPts$ quanto:

• Più alto è il dataset di punti
• Maggiore è il rumore presente

Una volta stimato $MinPts=k$, si passa a stimare il valore del raggio $ϵ$: per stimare $ϵ$ si possono ordinare i punti del dataset sulla base della distanza dal k-esimo elemento più vicino, dalla distanza più alta a quella più bassa e plottare tali distanze ordinate. La curva che si ottiene e simile a quella vista per il clustering gerarchico. Il valore ottimale di $ϵ$ è l'ordinata del punto del grafico in cui la curva <<piega>> maggiormente. Scegliendo valori troppo bassi di $ϵ$, molti punti non verrebbro clusterizzati, mentre valori troppo alti porterebbero a cluster troppo grandi.

7.4 Complessità di DBscan

La funzione chiave che determina la complessità di DBscan è quella che calcola l'$ϵ$-intorno di un punto. Con l'utilizzo di strutture indicizzate (es. mappe hash) è possibile ottenere l'$ϵ$-intorno di un punto in tempo $O(logn)$. Dal momento che l'$ϵ$-intorno è calcolato una sola volta per ogni punto, la complessità dell'algoritmo è $O(nlogn)$.

7.5 Vantaggi e svantaggi

I vantaggi dell'algoritmo sono i seguenti:

• Non richiede la conoscenza del numero di cluster
• Può trovare cluster di forma arbitraria
• Contempla la nozione di outlier
• L'assegnamento ai cluster è poco influenzato dall'ordine di esaminazione (meno che per i punti di bordo).

Mentre i principali svantaggi sono:

• La determinazione di due iperparametri strettamente dipendenti dal tipo di dato.
• Non è in grado di individuare cluster con notevoli differenze di densità.

8. Coefficiente di Silhouette

Il coefficiente di Silhouette è una metrica utile per la validazione del clustering effettuato, e quindi per verificare la qualità di un determinato metodo di clustering.

8.1 Calcolo del coefficiente

Per ogni osservazione $i$ viene calcolata la distanza media $D_i$ tra tutti i punti appartenenti allo stesso cluster. Dopodiché si calcola la distanza media tra il punto $i$ e tutti gli altri cluster e si seleziona il cluster con la distanza media più piccola, chiamata $C_i$. Il coefficiente di Silhouette è dato dalla seguente formula: $$S_i=\frac{C_i-D_i}{\max (C_i,D_i)}$$ Analizziamo i casi:

• $S_i>0$ indica che l'osservazione è ben clusterizzata. Di fatto il cluster $X$ è più lontano rispetto al cluster di appartenenza. Più il valore è vicino ad 1, meglio i dati sono clusterizzati. Si considerano discretamente ottimali valori al di sopra di 0.5.
• $S_i<0$ indica che l'osservazione è stata posizionata in un cluster sbagliato, di fatto il cluster $X$ è mediamente più vicino rispetto al cluster di appartenenza.
• $S_i=0$ indica che l'osservazione sta a metà tra $X$ ed il cluster di appartenenza, per cui comporta un caso dubbio.

Classificazione

1. Introduzione

Nell'asserzione statistica, la classificazione è definita come un problema di identificazione della classe di appartenza di una osservazione, rispetto ad un insieme di classi, sulle basi di un training set contenente osservazioni la cui classi di appartenenza sono note. Nel machine learning, la classificazione è considerata un metodo di apprendimento supervisionato (supervised learning). Essa è un esempio di pattern recognition. Il prodotto di un algoritmo di classificazione è detto modello. Data in input una nuova osservazione, il modello è in grado di assegnare una classe a tale osservazione con un certo grado di accuratezza. Spesso il modello è basato su parametri interni affinati attraverso il training set, e (talvolta) parametri esterni configurati manualmente, chiamati iperparametri.

1.1 Definizione formale

Sia $e\in E$ un esempio in input, dove $E$ è l'insieme di tutti i possibili esempi utilizzabili dall'algoritmo. Definiamo $C=\{0,\dots ,M-1\}$ l'insieme delle possibili classi ed ipotizziamo che $e$ appartenga ad una di esse, nello specifico ad $y\in C$. Definiamo un algoritmo di classificazione come una funzione: $$c:E\to C$$ Il classificatore $c$ effettuerà una predizione $\hat{y}=c(e)$ sulla classe di appartenenza di $e$. Il cappello nella $\hat{y}$ indica che la classe è stata predetta, al contrario di $y$ che rappresenta la classe corretta di $e$. Vogliamo che il nostro classificatore predica correttamente la classe, quindi che $\hat{y}=y$.

1.2 Classificazione e predizione

Ambo classificazione e predizione sono due metodi di tipo supervised learning. Entrambe utilizzano le feature delle osservazioni per classificare / predire un risultato. È possibile creare confusione tra le due tecniche, per cui evidenziamo la differenza principale: la classificazione predice l'etichetta della classe categoriale di appartenenza (discreta o nominale), mentre la predizione modella funzioni continue e consente la predizione di dati sconosciuti o mancanti.

1.3 Procedimento generale di un classificatore

Lo schema generale per la classificazione si suddivide nella creazione del modello e nell'utilizzo di quest'ultimo. Nella prima fase si utilizza un insieme di tuple, chiamato training set, dove ogni tupla (o osservazione) è caratterizzata da vari attributi (o features) e da una classe di appartenenza. Il modello viene costruito attraverso varie tecniche (alberi decisionali, principi probabilistici o geometrici, etc.) a partire dai dati di training.

• Costruzione del training set
• Scelta del metodo di apprendimento
• Allenamento del modello

Una volta finita la fase di creazione, si applica il modello a dei nuovi dati appartenenti ad un test set e si controlla che le etichette predette corrispondano alle etichette originali: viene quindi misurata la performance del classificatore. Il test set è fortemente indipendente dal training set, al fine di produrre un modello più generico possibile. Se la misura di performance è discretamente alta, allora si utilizza il modello per classificare nuovi dati.

• Si applica il modello al test set
• Si misurano le performance
• Si accetta o rigetta il modello in base ai risultati

1.4 Requisiti dei classificatori o predittori

I requisiti principali di un classificatore o di un predittore sono i seguenti:

• Accuratezza: predire correttamente le etichette delle classi / corretto valore di un attributo
• Velocità, intesa come:
  • Tempo impiegato nella costruzione del modello (training time).
  • Rapidità con cui il modello performa una classificazione / predizione (classification / prediction time).
• Robustezza: la capacità di manipolare dati con rumore o con feature mancanti.
• Scalabilità: mantenere l'efficienza all'aumentare dei dati, quindi manipolare anche dati in memoria secondaria.
• Interpretabilità dei risultati.

2. Alberi decisionali

Gli alberi decisionali sono uno strumento noto nei campi del machine learning, data mining e della statistica. Ogni nodo interno dell'albero contiene un test su uno o più attributi, tale test stabilisce quale dei sottoalberi deve essere visitato. Un test tipicamente valuta una feature, in tal caso si parla di alberi univariati, o una combinazione di feature, nel caso di alberi multivariati. Ogni foglia contiene una etichetta di classe.

Alcune importanti osservazioni:

• La classe di una osservazione (o tupla) si ottiene seguendo il percorso che va dalla radice dell'albero ad una foglia che determina la classe, sulla base dei test residenti nei nodi interni.
• Ad ogni nodo interno $X$ è possibile associare l'insieme $S_X$ delle tuple che soddisfano le condizioni testate partendo dalla radice sino ad arrivare al nodo X.
• La conoscenza rappresentata nell'albero decisionale può essere estratta e rappresentata in forma di regole di produzione if-then. Le regole estratte sono poi utilizzate per la classificazione di nuovi oggetti.

2.1 Esempio esplicativo

Ipotizziamo di avere il seguente training set, dove ogni osservazione è formata da 4 feature: $$\{Outlook,Temperature,Humidity,Windy\}$$ e da tali attributi si decide di giocare una partita di pallone o meno (P = Play, N = Not play). In tal caso il task del classificatore è quello di creare un modello in grado di analizzare le condizioni giornaliere in input e determinare se è il caso di giocare una partita o meno.

Attraverso un algoritmo di classificazione viene creato un albero decisionale come quello raffigurato nell'immagine sottostante. Più l'albero è bilanciato, più si ridurrà il tempo di classificazione / predizione di una osservazione. Tuttavia, è bene considerare anche il numero di rami uscenti da un nodo interno, poiché molti rami uscenti indicano test computazionalmente costosi. Una production rule tirata fuori da tale albero potrebbe essere la seguente:

if outlook == 'Sunny' and humidity == 'Normal':
    return 'PLAY'

2.2 Costruzione di un albero decisionale

Un albero decisionale può essere costruito in maniera top-down. Partendo dalla radice, è possibile applicare una serie di passi ricorsivamente.

• Supponiamo di essere al nodo t.
• Vi sono due possibilità:
  • Tutte le tuple associate all'insieme $S_t$ assumono la stessa classe y (quindi t si dice nodo puro)$\to$ t diventa una foglia di classe y
  • Altrimenti il nodo t si definisce impuro e:
    • Se è presente un attributo A tra gli attributi ancora non utilizzati:
      • Si partiziona $S_t$ sulla base dei valori di A (splitting)
      • Si creano tanti figli del noto t quante sono le partizioni create
      • Per ciascun figlio si reitera il processo.
    • Altrimenti si crea una foglia di classe y, dove la classe y è di maggioranza nell'insieme delle tuple associate al nodo (*).

(*) Nel caso di un nodo impuro ed in assenza di ulteriori attributi da utilizzare, è possibile stabilire una distribuzione di probabilità P tale che: per ogni classe C nell'insieme S del nodo, si assegna una probabilità P(C) data dal rapporto di osservazioni di classe C in S su osservazioni totali in S.

2.3 Splitting

Il processo di splitting incontrato nella costruzione dell'albero decisionale va attenzionato in base al tipo di attributo scelto. Consiste nel partizionare l'insieme di tuple S rispetto ad un nodo t in base ai valori che l'attributo può assumere.

Ipotizziamo di trovarci al nodo impuro X con un insieme di osservazioni $S_X$ e di aver scelto un attributo A:

• (a) Se A è un attributo categoriale, allora le osservazioni assumono uno tra i k valori finiti di A. Si formano k nodi figli di X e si partiziona l'insieme $S_X$ in k sottoinsiemi $S_1,...,S_k$ sulla base dei valori di A e si assegnano ai rispettivi nodi figli.
• (b) Se l'attributo è continuo allora si definisce un valore di soglia $\sigma$ e si partiziona l'insieme $S_X$ a seconda se $A\ge \sigma$ o $A<\sigma$. La soglia è scelta in modo che ogni partizione abbia un numero minimo di elementi. Si aggiungono due figli ad X a cui sono associate rispettivamente le partizioni create.
• (c) Se l'attributo è booleano allora si partiziona $S_X$ in due insiemi $S_1$ e $S_2$ a seconda che $A=true$ oppure $A=false$. Si aggiungono due figli ad X a cui sono associate rispettivamente le partizioni create.

2.3.1 Scelta degli attributi

La costruzione dell'albero decisionale è fortemente influenzata dall'ordine in cui si considerano gli attributi per lo splitting. Al variare dell'ordine, l'albero in output differisce; l'obiettivo consiste nello scegliere l'albero più semplice e compatto possibile. Nell'immagine che segue troviamo due alberi costruiti a partire dallo stesso training set, con un criterio di scelta degli attributi differente:

Ovviamente l'albero a destra è più compatto, comprensibile ed efficiente di quello a sinistra. Trovare l'albero minimale (con altezza minore) è un problema NP-Hard, per cui occorre utilizzare degli algoritmi approssimati che cerchino un ottimo locale sfruttando una strategia greedy. Un' euristica ricorrente è la seguente:

Si sceglie ad ogni passo l'attributo che divide le osservazioni in insiemi che sono relativamente puri.

L'obiettivo è quindi quello di effettuare scelte che portino più rapidamente ai nodi foglia. Esistono varie nozioni di purezza che esamineremo in seguito, e prendono il nome di misure di goodness.

2.3.2 Algoritmo greedy ricorsivo

Descriviamo l'algoritmo greedy ricorsivo come segue:

• Passo base:

  • Se tutte le osservazioni in S associato al nodo t assumono la stessa classe, quindi t è un nodo puro, allora si crea una foglia contenente tutti i dati.
  • Altrimenti, se non vi sono ulteriori attributi da selezionare per lo splitting, si crea un nodo foglia con l'etichetta di maggioranza.

• Passo ricorsivo:

  • Si seleziona l'attributo A che massimizza una misura di goodness;
  • Si effettua lo splitting di S rispetto al nodo t sulla base di A.
  • Si applica ricorsivamente l'algoritmo sui figli del nodo t.

build_decision_tree (S, attributes):
	if observations in S have the same class: 
		make a new leaf with this class
	else: 
		if the node is impure but there are no attributes: 
			make a new leaf with the most frequent class in S
		else: 
			A = attribute that maximize the goodness measurement 
			partitions = split(S, A)
			for partition in partitions: 
				build an internal node, son of the current node 
				build_decision_tree(partition, attributes - {A})

2.3.3 Splitting su attributi continui

Nel caso di attributi continui occorre scegliere un valore di soglia, per cui lo splitting effettuato in questo caso dipende anche da questo parametro. Se l'attributo è continuo è necessario quindi calcolare più valori di goodness per lo stesso attributo e prendere come riferimento quello con la goodness più alta. Questo aggiunge un layer di complessità alla scelta degli attributi.

2.4 Misure di goodness

Una misura di goodness quantifica la purezza dei nodi prodotti dallo splitting, scegliendo uno tra gli attributi. Conosciamo tre misure più ricorrenti:

• Information gain (utilizzata nell'algoritmo ID3)
• Gain ratio (utilizzata nell'algoritmo C4.5)
• Gini index (utilizzata nell'algoritmo CART)

2.4.1 Information gain (algoritmo ID3)

La scelta di un attributo mira alla riduzione progressiva dell'entropia. La nozione di purezza è descritta come "quanto un insieme di istanze è prossimo alla situazione ideale", ovvero contenente osservazioni di una sola classe.

• L'entropia massima si ha quando le classi delle osservazioni associate ad un nodo hanno la stessa frequenza.
• L'entropia minima si ha quando tutte le osservazioni associate ad un nodo hanno la stessa classe (nodo puro).

Sia $S_X$ l'insieme delle osservazioni associate ad un nodo X dell'albero, se X è la radice allora $S_X$ è l'intero set di osservazioni. Se X è un nodo interno allora $S_X$ è l'insieme di osservazioni che soddisfano i test imposti dagli archi dell'albero nel percorso effettuato per arrivare dalla radice ad X.

La quantità di informazione è definita nella teoria della informazione come segue: $$I(x)=-log(P(x))$$ L'entropia, descritta come il grado di incertezza in una distribuzione di probabilità P è definita come segue: $$H(X)=E_X[I(x)]=-\sum _{x}P(x)\ast log(P(x))$$ Assumiamo di avere solo due classi, P ed N. Ipotizziamo che $S_X$ contenga p osservazioni di classe P ed n osservazioni di classe N. Definiamo la probabilità di una classe in modo frequentista, data quindi dal rapporto di casi favorevoli (osservazioni della data classe in $S_X$) su casi possibili (osservazioni in $S_X$).

Nel nostro esempio, le classi P ed N hanno rispettivamente probabilità: $$P(P)=\frac{p}{p+n}eP(N)=\frac{n}{p+n}$$ Per cui l'entropia dell'insieme $S_X$ è così definita: $$H(S_X)=-\frac{p}{p+n}\ast log(\frac{p}{p+n})-\frac{n}{p+n}\ast log(\frac{n}{p+n})$$ Supponiamo di scegliere l'attributo A come attributo per lo splitting. L'insieme $S_X$ verrà partizionato in $S_1,S_2,...,S_k$ insiemi. Supponiamo che l'i-esimo insieme $S_i$ contenga $p_i$ osservazioni di classe P e $n_i$ osservazioni di classe N. Allora l'entropia dell'insieme $S_i$ è data come: $$H(S_i)=-\frac{p_i}{p_i+n_i}\ast log(\frac{p_i}{p_i+n_i})-\frac{n_i}{p_i+n_i}\ast log(\frac{n_i}{p_i+n_i})$$ Definiamo l'entropia media di $S_X$ rispetto ad A la seguente media pesata delle entropie dei singoli sottoinsiemi $S_i$: $${\bar{H}}_A(S_X)=\sum _{i=1}^k\frac{p_i+n_i}{p+n}H(S_i)$$ Generalizziamo il concetto e ipotizziamo che in $S_X$ le osservazioni assumano n classi differenti $C_1,...,Cn$. Allora l'entropia di $S_X$ è data da: $$H(S_X)=-\sum _{i=1}^{n}P(C_i)\ast log(P(C_i))$$ Sia A un attributo avente i seguenti valori $\{a_1,...,a_n\}$. Effettuando lo splitting di $S_X$ nei vari $S_i$ a seguito del test su A, l'entropia media di $S_X$ rispetto ad A sarà la media ponderata delle entropie dei singoli sottoinsiemi, ovvero: $$INFO(A)={\bar{H}}_A(S_X)=\sum _{i=1}^k\frac{|S_i|}{|S_X|}H(S_i)$$ L'information gain è definito come la riduzione di entropia ottenuta dal partizionamento di $S_X$ scegliendo l'attributo A, ovvero: $$gain(A)=H(S_X)-{\bar{H}}_A(S_X)$$ Ad ogni passo di splitting, l'algoritmo sceglierà l'attributo A che massimizza l'information gain. Ciò equivale a selezionare l'attributo A tale che ${\bar{H}}_A(S_X)$ sia minimo, in quanto $H(S_X)$ è lo stesso (dato il nodo) qualunque sia l'attributo selezionato. Questo approccio minimizza il numero atteso di test necessario per classificare una data tupla. Garantisce inoltre la costruzione di un albero semplice (non necessariamente il più semplice, essendo un approccio greedy).

2.4.2 Svantaggi dell'information gain

L'information gain risulta fortemente sbilanciato in favore dei test che hanno molti esiti. In determinati casi si verifica che un test, che può essere molto discriminante ai fini della divisione dell'albero e quindi con un forte potere predittivo, non venga effettuato perché si basa su un attributo con pochi valori possibili, in favore di un altro test con molti esiti possibilmente poco significativi in termini di predizione.

Ad esempio, se uno degli attributi è un ID, allora ogni partizione sulla base di questo attrbuto avrà una sola tupla. Di conseguenza ogni nodo creato dalla partizione sarà puro e l'entropia media delle partizioni sarà zero, ovvero l'information gain sarà massimo.

2.4.3 Gain ratio (algoritmo C4.5)

Rispetto ad ID3, l'algoritmo C4.5 utilizza una misura di goodness diversa chiamata Gain ratio, che riduce il bias introdotto dall'information gain. Il Gain ratio prende in considerazione il numero e la dimensione delle partizioni ottenute scegliendo un attributo, senza considerare informazioni specifiche sulle singole classi.

Le potenziali informazioni sullo split generato da un attributo A sono rappresentate dallo $splitInfo$: $$splitInfo(A)=-\sum _{i=1}^k\frac{|S_i|}{|S_X|}lo{g}_2(\frac{|S_i|}{|S_X|})$$ Il Gain ratio è dato da: $$GainRatio(A)=\frac{Gain(A)}{SplitInfo(A)}$$ Attributi che determinano molte partizioni con pochi elementi avranno un valore di $SplitInfo$ maggiore, quindi un minore $GainRatio$.

2.4.4 Gini index (algoritmo CART)

Il Gini index, anche chiamato Gini impurity, misura l'impurità di un insieme di osservazioni $S_X$ associato ad un nodo dell'albero decisionale. Consideriamo una classe $C_i$ ed una tupla x di classe $C_i$ scelta a caso dal dataset T. Supponiamo di assegnare casualmente ad x una classe $C_j$ sulla base della distribuzione delle frequenze delle classi nel dataset. Il Gini index misura, per ogni classe, la probabilità che $i\ne j$. Chiamiamo $p_i$ la probabilità di scegliere una osservazione del dataset di classe $C_i$, la probabilità di scegliere una classe $C_j$ diversa da $C_i$ a partire dalla distribuzione delle frequenze delle classi è:

$$P(C_j\ne C_i)=\sum _{j=1,j\ne i}^n{p}_j=1-p_i$$ Supponiamo di avere n classi, il gini index calcola l'impurità di un nodo sommando, per ogni classe $C_i$ con $i=1,...,n$, la probabilità che si scelga una classe errata (ovvero $1-p_i$). Tale valore viene bilanciato attraverso la probabilità $p_i$: $$gini(S_X)=\sum _{i=1}^n{p}_i(1-p_i)=\sum _{i=1}^n{p}_i-p_i^2=1-\sum _{i=1}^n{p}_i^2$$ Dunque, dato un insieme di osservazioni $S_x$ con n classi, il Gini index è definito come segue: $$gini(S_X)=1-\sum _{i=1}^n{p}_i^2$$ Dove $p_i$ è la frequenza relativa della classe $C_i$ in $S_X$.

Supponiamo che, scegliendo un attributo A per lo split, l'insieme $S_X$ venga partizionato in k sottoinsiemi $S_1,...,S_k$. Il Gini index dello split è definito come segue: $$gin{i}_{split}(S_X)=\sum _{i=1}^k\frac{|S_i|}{|S_X|}\ast gini(S_i)$$ L'attributo A che minimizza $gin{i}_{split}(S_X)$ è selezionato come attributo di splitting.

2.5 Pruning

L'elevato numero di attributi in un training set o la particolare distribuzione dei valori degli attributi può far crescere notevolmente la dimensione di un albero. Ciò può portare alla costruzione di un modello più complesso, fatto "su misura" sul training set, ma non in grado di classificare correttamente nuovi dati. Questo fenomeno è chiamato overfitting. Rende più difficile la classificazione (dovuto ad outliers) ed è associato ad un aumento non giustificato di errori. Per evitare questo, gli algoritmi di classificazione effettuano un pruning (potatura).

Il pruning consiste nel rimuovere i rami che non contribuiscono ad una corretta classificazione, producendo qualcosa di meno complesso e più comprensibile. Il pruning deve essere fatto senza aumentare eccessivamente il tasso di errore di classificazione del modello.

2.5.1 Pre-pruning e post-pruning

Vi sono varie tipologie di pruning:

• Pre-pruning: è attivato in fase di costruzione dell'albero, nel momento in cui si decide se dividere ulteriormente o meno un determinato sottoinsieme. Fissato un valore di soglia (threshold) t, i rami per cui si ottiene un gain inferiore a t vengono troncati. In alternativa, possono essere utilizzati metodi statistici per effettuare il troncamento.
• Post-pruning: questa tipologia di pruning è utilizzata dagli algoritmi CART e C4.5. Si rimuovono rami e nodi a costruzione dell'albero già avvenuta, sostituendo un intero sotto-albero con una foglia.

Il post pruning, sebbene più dispendioso, consente una analisi più approfondita delle partizioni producendo un albero più realistico. Il C4.5 utilizza un algoritmo di post-pruning chiamato pessimistic pruning o reduced error pruning. Il CART utilizza un algoritmo di post-pruning chiamato cost-complexity pruning.

2.5.2 Pessimistic pruning

Dato un sottoalbero T di radice X, definiamo l'error rate (tasso di errore) atteso di T $E(T)$ il numero di osservazioni di $S_X$ che sono classificate in maniera errata. Una strategia semplice di pruning consiste nel potare un sottoalbero in funzione della variazione di error rate predetto che porterebbe all'intero albero. Se tale variazione è positiva, ovvero il tasso di errore aumenta in presenza del sottoalbero, allora il sottoalbero stesso può essere potato e sostituito con una foglia.

Il pruning pessimistico si basa sul calcolo di questa variazione di errore ed è chiamato pessimistico poiché sovrastima leggermente (di una quantità $ϵ$) il tasso di errore atteso in ogni sottoalbero.

Vediamo la procedura generale:

• Calcoliamo una stima pessimistica $E_p(T)$ dell'error rate atteso sul training set prima di fare lo splitting di un nodo X su un attributo A, considerando il nodo X come una foglia con l'etichetta di maggioranza nel sottoalbero.

Avendo considerato la classe di maggioranza c sostitutiva al sottoalbero, l'error rate sarà calcolato come segue: $$E(T)=\frac{\#tuplediclasse{c}^{\prime }\ne cin{S}_X}{\#tupleinT}$$ La stima pessimistica è calcolata aggiungendo un fattore $ϵ$: $$E_p(T)=\frac{(\#tuplediclasse{c}^{\prime }\ne cin{S}_X)+ϵ}{\#tupleinT}$$

• Calcoliamo una stima pessimistica $E_p^{\prime }(T)$ dell'error rate atteso dopo aver eseguito lo splitting di X su A, utilizzando quindi il sottoalbero.

Essendovi uno splitting del nodo X, vi saranno k sottoinsiemi di $S_X$: $S_1,...,S_k$. Calcoliamo l'error rate, considerato il sottoalbero, come segue: $$E^{\prime }(T)=\frac{{\sum }_{i=1}^k\#tuplediclasse{c}^{\prime }\ne cin{S}_i}{\#tupleinT}$$ La stima pessimistica è calcolata aggiungendo un fattore $ϵ$: $$E_p^{\prime }(T)=\frac{{\sum }_{i=1}^k(\#tuplediclasse{c}^{\prime }\ne cin{S}_i+ϵ)}{\#tupleinT}=\frac{({\sum }_{i=1}^k\#tuplediclasse{c}^{\prime }\ne cin{S}_i)+k\ast ϵ}{\#tupleinT}$$

• Se $E_p^{\prime }(T)>E_p(T)$ allora:
  • Viene sostituito il sottoalbero radicato in X con un nodo foglia.
  • Viene assegnata ad X l'etichetta di maggioranza tra le foglie del vecchio sottoalbero.

Vediamo un esempio di pruning pessimistico:

2.5.3 Cost complexity pruning

L'algoritmo CART utilizza un algoritmo di post pruning chiamato Cost Complexity pruning. Tale algoritmo costruisce iterativamente m alberi decisionali $T_0,T_1,...,T_m$ , dove $T_0$ l'albero decisionale completo e $T_m$ è l'albero formato dalla sola radice.

Alla i-esima iterazione, l'albero $T_i$ è ottenuto a partire dall'albero $T_{i-1}$ rimuovendo un sottoalbero t di $T_{i-1}$ e sostituendolo con un nodo foglia con associata etichetta di maggioranza ( o distribuzione delle classi). Se $E(T_i)$ è l'error rate atteso per il sottoalbero $T_i$, il sottoalbero da rimuovere in questa iterazione è quello tale da minimizzare la seguente funzione: $$argmi{n}_j\frac{E(prune(T_i,t_j))-E(T_i)}{|leaves(T_i)|-|leaves(prune(T_i,t_j))|}$$ Dove $prune(T_i,t_j)$ è l'albero ottenuto rimuovendo da $T_i$ il sottoalbero $t_j$, mentre con $|leaves(T)|$ intendiamo genericamente il numero di foglie in un albero. Uno dei vantaggi di tale algoritmo è che non è necessario stimare un parametro $ϵ$.

2.6 Estrazione di regole da un albero decisionale

A partire dall'albero decisionale è possibile estrarre delle production rules del tipo IF (condizione) THEN (etichetta). Esiste una regola per ogni cammino che porta dalla radice ad una foglia. Le coppie (attributo, valore) lungo un percorso entrano a far parte della condizione della regola, legate attraverso congiunzione (AND). Il valore contenuto nella foglia determina la predizione finale della classe. Le regole sono mutuamente esclusive ed esaustive.

Vediamo un esempio:

2.6.1 Qualità di una regola

Per stabilire la qualità di una regola per una classe C si utilizzano due misure:

• Copertura (coverage): numero relativo di osservazioni coperte dalla regola, ovvero che soddisfano le condizioni della regola.
• Accuratezza (accuracy): numero relativo di osservazioni di classe C coperte dalla regola.

Una buona regola dovrebbe avere alta coverage per una specifica classe C (ovvero coprire quante più tuple di classe C) ed elevata accuratezza (ovvero classificare bene la maggior parte delle osservazioni di classe C coperte).

Definiamo gli esempi positivi come le osservazioni di classe C coperte dalla regola, mentre gli esempi negativi come le tuple di classe diversa da C coperte dalla regola.

2.6.2 Risoluzione dei conflitti

Idealmente, ogni regola sulla classe C dovrebbe coprire insiemi di osservazioni differenti. Tuttavia, è possibile avere ridondanze o conflitti con due o più regole che coprono più o meno lo stesso insieme di osservazioni. Occorre risolvere un problema di minimal set covering, ovvero trovare il più piccolo insieme di regole sulla classe C che coprono gli esempi positivi. Ciò deve essere fatto producendo regole che abbiano un livello sufficientemente alto di accuratezza.

Alcuni algoritmi noti per la ricerca del minimal set covering sono FOIL, AQ, CN2, RIPPER. Le regole vengono costruite in maniera sequenziale. L'obiettivo è individuare una regola per una classe C che copra molte tuple di classe C (esempi positivi) e nessuna (o poche) tuple delle altre classi (esempi negativi). Lo schema generale è il seguente:

• Sia S il set formato da tutte le osservazioni del training set.
• Le regole vengono apprese una per volta seguendo un criterio greedy basato sulla qualità della soluzione.
• Ogni volta che una nuova regola viene appresa, gli esempi positivi vengono rimossi da S.
• Il processo viene ripetuto sino a quando S non diventa vuoto.

2.6.3 Algoritmi FOIL e RIPPER

Gli algoritmi FOIL e RIPPER utilizzano una strategia greedy e depth-first per generare la regola da aggiungere ad ogni passo.

Sia C la classe; partiamo dalla radice dell'albero decisionale e consideriamo la regola più generale per ottenere la classe C, ovvero quella senza condizioni: $$IFTrueTHENC$$ Da tale regola otterremo il massimo punteggio di copertura (coverage) poiché tutte le osservazioni rispettano tale condizione, ma anche una pessima accuratezza (accuracy), ovvero saranno incluse anche tutte le osservazioni di classe diversa da C, quindi molti esempi negativi.

Dopodiché si scenderà lungo l'albero scegliendo la condizione che mantenga una ampia copertura e ottimizzi la accuratezza per la classe C. $$\begin{gathered} IFA=aTHENC \\ IFA=aANDB=bTHENC \\ ... \end{gathered}$$ Inevitabilmente, durante l'aggregazione di nuove condizioni scenderanno sia gli esempi positivi che gli esempi negativi della classe C, la scelta va ponderata in base al miglior rapporto (che enfatizza la diminuzione degli esempi negativi, mentre scoraggia quella dei positivi).

Vi è la necessità di introdurre una metrica che diriga l'algoritmo nell'effettuare la scelta migliore. Nel caso dell'algoritmo FOIL si introduce il FOIL gain: le condizioni vengono aggiunte sino a quando la regola ottenuta mantiene un livello di qualità superiore ad una certa soglia, sulla base del FOIL gain.

2.6.4 FOIL gain

Siano $pos$ e $neg$ rispettivamente il numero di esempi positivi e negativi ottenuti prima della costruzione della regola. Siano $po{s}^{\prime }$ e $ne{g}^{\prime }$ rispettivamente il numero di esempi positivi e negativi ottenuti dopo della costruzione della regola. $$FOILGain(R)=po{s}^{\prime }\ast [lo{g}_2\frac{po{s}^{\prime }}{po{s}^{\prime }+ne{g}^{\prime }}-lo{g}_2\frac{pos}{pos+neg}]$$ Il FOIL gain cerca quindi di favorire regole che hanno alta accuratezza e coprono molti esempi positivi.

3. Classificatori generativi

I classificatori generativi (o classificatori Bayesiani) producono un modello probabilistico traendo informazioni dai dati e predicono la classe di appartenenza più probabile per un nuovo dato a partire dal modello sviluppato. Esempi di classificatori generativi sono le Bayesian networks ed i Gaussian Mixture Models, entrambi basati sul teorema di Bayes.

3.1 Teorema di Bayes

Consideriamo un insieme di alternative $A_1,\dots ,A_n$ che partizionano lo spazio degli eventi $\Omega$. Si trova la seguente espressione per la probabilità condizionata: $$P(A_i\mid E)=\frac{P(E\mid A_i)P(A_i)}{P(E)}=\frac{P(E\mid A_i)P(A_i)}{{\sum }_{j=1}^{n}P(E\mid A_j)P(A_j)}$$ Dove:

• $P(A)$ è la probabilità a priori o probabilità marginale (nessuna informazione su $E$).
• $P(A\mid E)$ è la probabilità a posteriori, dato che deriva dal valore di $E$.
• $P(E\mid A)$ è la verosimiglianza (likelihood).
• $P(E)$ è l'evidenza, che funge da costante di normalizzazione.

3.2 Maximum a Posteriori (MAP)

Consideriamo l'evento stocastico "$x$ è di classe $c$" dove $x$ è una osservazione d'esempio e $c\in \{0,\dots ,M-1\}$ è una delle $M$ possibili classi nel problema di classificazione. Consideriamo la probabilità $P(c\mid x)$ che risponda alla domanda "qual è la probabilità che si osservi la classe $c$, data l'osservazione $x$?". Se quantifichiamo tale probabilità per ogni classe $c$ tra le $M$ esistenti, abbiamo una distribuzione di probabilità condizionata sulle classi, dato l'input $x$. Risulta naturale attribuire all'input $x$ la classe $\bar{c}$ che massimizzi la distribuzione di probabilità condizionata: $$\bar{c}=\text{arg}\underset{c}{\max }P(c\mid x)$$ Ricollegandoci al teorema di Bayes, la probabilità da massimizzare è chiamata probabilità a posteriori, da cui il nome del metodo di classificazione: Maximum A Posteriori (MAP). Sostituiamo con la formula precedente: $$\bar{c}=\text{arg}\underset{c}{\max }\frac{P(x\mid c)P(c)}{P(x)}$$ Dal momento in cui l'evidenza costituisce una costante di normalizzazione, massimizzare tale espressione equivale a massimizzare la seguente: $$\bar{c}=\text{arg}\underset{c}{\max }P(x\mid c)P(c)$$

3.2.1 Calcolo delle probabilità

La semplificazione del metodo Maximum a Posteriori attraverso l'utilizzo del teorema di Bayes ci permette di passare da una stima altamente complessa di $P(C\mid X)$ a due stime relativamente semplici, quali la probabilità a priori e la likelihood.

Calcolo della probabilità a priori

Data una classe $C$, il calcolo della probabilità a priori $P(C)$ è relativamente semplice. È sufficiente calcolare in maniera frequentista il rapporto di osservazioni nel dataset facenti parte della classe $C$ rispetto alle osservcazioni totali:

P(C) = \frac {\text{#obs. of class C}} {\text{#obs.}}

Calcolo della likelihood

La likelihood $P(X\mid C)$ è più semplice da stimare rispetto alla probabilità a posteriori $P(C\mid X)$ poiché il termine condizionante è discreto e finito. Per ogni classe $C$ consideriamo la variabile aleatoria $X_c$ composta da sole le osservazioni di classe $C$, quindi $X_c$ è un sottoinsieme di $X$. La probabilità $P(X_c)=P(X|C)$.

Per semplicità consideriamo $X_c$ univariata e distinguiamo due casi:

• $X_c$ è discreta e finita, allora è possibile calcolare la probabilità $P(X_c)$ in maniera frequentista.
• $X_c$ è continua o discreta ma non finita, allora utilizziamo una distribuzione di probabilità nota.

3.2.2 Esempio discreto

Consideriamo una versione semplificata della classificazione degli Iris di Fisher dove troviamo due sole variabili: SepalWidth e SepalLength. Le variabili sono discrete e finite e possono assumere 3 soli valori: small, medium e large, rispetto alla dimensione del sepalo. Sia $X=[SepalWidth,SepalLength]$ una variabile aleatoria bidimensionale. L'esempio può appartenere a una tra le classi Setosa, Virginica e Versicolor. Definiamo 3 diverse verosimiglianze $P(X_{set})$, $P(X_{vir})$ e $P(X_{ver})$ a partire dalle seguenti tabelle:

Le righe nelle tabelle rappresentano la larghezza del sepalo (SepalWidth) mentre le colonne la lunghezza (SepalLength). Ogni tabella contiene la frequenza assoluta delle occorrenze per ognuna delle possibili combinazioni delle due variabili. Possiamo trasformare queste tabelle in una distribuzione di probabilità dividendo ogni elemento per il totale delle osservazioni del sottoinsieme considerato.

Supponiamo di assegnare una probabilità a priori equa di $\frac{1}{3}$ ad ognuna delle tre classi e stimiamo la classe di un esempio $X=[medium,medium]$. Per il metodo Maximum a Priori, è necessario prendere in considerazione la classe $c$ che massimizzi $P(X\mid C)\times P(C)$. $$f([medium,medium])=\text{arg}\underset{c}{\max }\left(P(X\mid C)P(C)\right)$$ Quindi calcoliamo per ognuna delle 3 classi tale espressione:

• $P(X\mid Setosa)P(Setosa)=0\times \frac{1}{3}=0$
• $P(X\mid Versicolor)P(Versicolor)=0.4\times \frac{1}{3}=0.13$
• $P(X\mid Virginica)P(Virginica)=0.34\times \frac{1}{3}=0.11$

Classificheremo l'esempio $X=[medium,medium]$ come Versicolor, dato che tale classe massimizza la probabilità a posteriori.

3.2.3 Esempio continuo

Supponiamo di voler classificare il genere di una persona (uomo, donna) in base alla sua altezza $h$ ed al suo peso $w$. Supponiamo che $C=1$ se il soggetto è una donna, mentre $C=0$ se il soggetto è un uomo. Introduciamo la variabile aleatoria $X=(h,w)$.

Ipotizziamo che il dataset di esempi sia bilanciato e che quindi le probabilità a priori siano $\frac{1}{2}$ per ognuna delle due classi. Adesso è necessario calcolare la likelihood per entrambe le classi, ma le variabili sono continue, per cui non è possibile costruire una tabella.

Consideriamo il seguente grafico che mostra la distribuzione degli input di sesso femminile ($X=1$) in base ad altezza e peso:

La distribuzione è molto simile ad una gaussiana bidimensionale. Possiamo modellare $P(X\mid C=1)$ considerando tutti e soli gli esempi di sesso femminile e calcolando i parametri della gaussiana bidimensionale: $$N(x;\mu ,\Sigma )=\sqrt{\frac{1}{(2\pi {)}^2\det (\Sigma )}}\exp (-\frac{1}{2}(x-\mu {)}^T{\Sigma }^{-1}(x-\mu ))$$ Siano $x_F$ gli input di sesso femminile, calcoliamo i parametri della gaussiana bidimensionale: $${\mu }_F=\frac{1}{n}\sum _j{x}_F^{(j)}$$

$${\Sigma }_F=Cov(x_f)$$

Facciamo lo stesso considerando solo gli input di sesso maschile $x_M$ e calcoliamo le rispettive likelihood come segue:

• $P(X\mid C=0)=N(x;{\mu }_M,{\Sigma }_M)$;
• $P(X\mid C=1)=N(x;{\mu }_F,{\Sigma }_F)$;

Classificheremo l'esempio $x$ come femmina se $P(x\mid 1)p(1)>P(x\mid 0)p(0)$, maschio altrimenti.

3.3 Classificatore Naïve Bayes

Il calcolo della likelihood potrebbe essere oneroso nel caso la variabile $X$ abbia molte dimensioni. Il classificatore Naïve Bayes assume in maniera naïve che gli attributi di $X$ siano condizionalmente indipendenti tra loro, ovvero indipendenti fissata la classe $C$ di appartenenza: $$X_i\perp X_j\mid C,\forall i\ne j$$ Tale assunzione è spesso non vera, ma semplifica notevolmente il calcolo e procura generalmente buoni risultati. Per le proprietà di indipendenza condizionata possiamo riscrivere la likelihood come segue: $$P(X\mid C_i)=\prod _{k=1}^{n}P(x_k\mid C_i)=P(x_1\mid C_i)\times \cdots \times P(x_n\mid C_i)$$ E la regola di classificazione MAP: $$f(x)=\text{arg}\underset{c}{\max }\left[P(x_1\mid C)\times \cdots \times P(x_n\mid C)\times P(C)\right]$$ I singoli termini $P(x_i\mid C)$ sono semplici da stimare dato che $x_i$ è monodimensionale. Nella pratica viene scelta una distribuzione tra la Gaussiana e la Multinomiale per modellare approssimare la distribuzione reale dei dati. Se viene utilizzata la distribuzione gaussiana, allora il classificatore prende il nome di "Gaussian Naïve Bayes", mentre nel caso della multinomiale "Multinomial Naïve Bayes".

3.3.1 Gaussian Naïve Bayes

Consideriamo nuovamente la classificazione dei sessi basata su altezza e peso (esempio 3.2.3). Se i dati assumono approssimatamente una distribuzione gaussiana e considerando la assunzione naïve, le probabilità $P(H\mid C)$ ed $P(W\mid C)$ possono essere modellate singolarmente attraverso una gaussiana monodimensionale. Eseguiamo il calcolo per ognuna delle classi, ottenendo 4 espressioni più semplici da calcolare:

• $P(H=h\mid C=0)=N(x;{\mu }_1,{\sigma }_1)$
• $P(H=h\mid C=1)=N(x;{\mu }_2,{\sigma }_2)$
• $P(W=w\mid C=0)=N(x;{\mu }_3,{\sigma }_3)$
• $P(W=w\mid C=1)=N(x;{\mu }_4,{\sigma }_4)$

Dopodiché classificheremo l'esempio $x=(h,w)$ come femmina (1) se: $$P(h\mid 1)P(w\mid 1)P(1)>P(h\mid 0)P(w\mid 0)P(0)$$ maschio altrimenti.

3.3.2 Multinomial Naïve Bayes

Nell'esempio precedente si è fatto uso di variabili aleatorie continue, per cui è necessario considerare una PDF (Probability Density Function) come una distribuzione gaussiana. Quando gli attributi dei dati sono discreti, ha senso utilizzare una PMF (Probability Mass Function).

La distribuzione multinomiale di parametri $((p_1,\dots ,p_s),n)$ con $p_1+\cdots +p_s=1$, descrive la probabilità per ogni $s$-upla $(n_1,\dots ,n_s)$ con $n_1+\cdots +n_s=n$ di assumere i risultati $x_1,\dots ,x_s$ in $n$ prove indipendenti, ognuna delle quali ha probabilità $p_i$ di fornire $x_i$.

Consideriamo l'esempio della text classification. Ipotizziamo di rappresentare un documento d'esempio con la rappresentazione Bag of Words (conteggio delle occorrenze di parole in un vocabolario). Dato un vocabolario $V$ di lunghezza $s$, ogni input $x$ avrà $s$ attributi $(x_1,\dots ,x_s)$, con $x_i\in \mathbb{N}$ che rappresenta il numero di occorrenze nel documento della $i$-esima parola nel vocabolario.

La likelihood di un esempio $x$ sarà $P(x_1,\dots x_s\mid C)$. Utilizzando l'assunzione naïve diciamo che il numero di occorrenze della $i$-esima parola nel documento di classe $C$ è indipendente dal numero di occorrenze della parola $j$-esima. Possiamo utilizzare la distribuzione multinomiale per calcolare la probabilità $P(x_1,\dots ,x_s\mid C)$, ma è necessario fissare alcuni parametri:

• Il numero di esperimenti $n$ sarà il numero totale di parole nel documento ${\sum }_{i=1}^n{x}_i$
• $(n_1,\dots ,n_s)$ rappresenta le occorrenze delle $s$ parole nel vocabolario $V$ in un documento
• La probabilità $p_{ci}$ sarà la probabilità di trovare la parola $i$-esima del vocabolario $V$ fissata una classe $C$

È possibile calcolare la probabilità $p_{ci}$ in maniera frequentista: $$p_{ci}=\frac{{\sum }_j^n[y^{(j)}=c]x_i^{(j)}}{{\sum }_j^n{\sum }_k^s[y^{(j)}=c]x_k^{(j)}}$$ Dove $[\cdot ]$ denota le parentesi di Iverson, che valgono 1 se la condizione all'interno è soddisfatta, 0 altrimenti. La probabilità corrisponde al numero di occorrenze della parola $i$-esima in tutti i documenti di classe $c$ rispetto al numero totale di parole nei documenti di classe $c$.

È possibile risolvere il problema di classificazione con il metodo MAP: $$f(x_1,\dots ,x_s)=\text{arg}\underset{c}{\max }P(x_1,\dots ,x_s\mid c)P(c)$$ Sostituendo la likelihood con la formula analitica della distribuzione multinomiale: $$f(x_1,\dots ,x_s)=\text{arg}\underset{c}{\max }P(c)\left[\frac{({\sum }_i{x}_i)!}{x_1!\times \cdots \times x_s!}{p}_{c1}^{x_1}\times \cdots \times p_{cs}^{x_s}\right]$$ Il rapporto $\frac{({\sum }_i{x}_i)!}{x_1!\times \cdots \times x_n!}$ è analogo qualunque sia la classe $c$ considerata, per cui massimizzare tale espressione equivale a massimizzare: $$f(x_1,\dots ,x_s)=\text{arg}\underset{c}{\max }P(c)\left[p_{c1}^{x_1}\times \cdots \times p_{cs}^{x_s}\right]$$

3.3.3 Zero probability e underflow

Il metodo Naive Bayes richiede che le probabilità condizionali siano diverse da 0, altrimenti la likelihood risulterà nulla. Inoltre, se le probabilità condizionali sono molto piccole, un prodotto di tante quantità prossime allo 0 può portare problemi di precisione e di underflow.

Per ovviare al primo problema, si può utilizzare la correzione Laplaciana, ovvero aggiungere 1 ad ogni probabilità condizionale.

Per ovviare a entrambi i problemi, si può considerare il log-likelihood, ovvero il logaritmo di $P(X|C_i)$, che si traduce in una somma anziché un prodotto dei termini: $$\begin{gathered} \log P(X|C_i)=\log \prod _{k=1}^{n}P(x_k|C_i)= \\ =\log P(x_1|C_i)+...+\log P(x_n|C_i)= \\ =\sum _{k=1}^n\log P(X_k|C_i) \end{gathered}$$

3.3.4 Conclusioni

Il classificatore Naive Bayes è facile da implementare, discretamente veloce nella classificazione e produce buoni risultati. Tuttavia, l'assunzione naive non è sempre vera e può provocare una perdita di accuratezza. Le dipendenze tra più attributi, sempre a causa dell'assunzione, non possono essere modellate.

4. Classificatori discriminativi

4.1 Introduzione

I classificatori discriminativi cercano di predire la classe direttamente a partire dai dati osservati, facendo poche assunzioni sulla loro distribuzione. Esempi di classificatori discriminativi sono il Perceptron ed SVM.

4.1.1 Differenze tra generativo e discriminativo

Il classificatore generativo sviluppa un modello probabilistico sui dati a partire da un insieme di assunzioni e predice la classe più probabile per un nuovo dato. Il classificatore discriminativo costruisce una funzione di decisione $F$ a partire dai dati osservati stimando pesi calcolati per ogni attributo e dipendenti dai valori dell'attributo stesso. Se $X$ è un nuovo dato, si calcola $F(X)$ ed il valore ottenuto è la classe di $X$.

4.1.2 Vantaggi e svantaggi

Vantaggi dei classificatori discriminativi:

• Maggiore accuratezza in generale
• Robusti in presenza di errori nel training set
• Facile calcolo del valore della funzione di decisione $F$ su un nuovo dato

Svantaggi:

• Tempo di addestramento lungo
• Difficile interpretare i pesi della funzione di decisione calcolata
• Non è semplice incorporare conoscenza a priori (nei metodi Bayesiani risulta molto semplice)

Si rimedia alla difficile interpretazione dei pesi attraverso la explainable artificial intelligence, ovvero tutta una serie di metodi per rendere il risultato di una soluzione comprendibile dagli umani.

4.2 Classificazione lineare vs non lineare

Nella classificazione lineare la classificazione di una osservazione $X$ è basata sul valore di una funzione lineare $f$, ovvero una combinazione lineare degli attributi di $X$: $$y=f(X)=\sum _{i=1}^k{w}_i\ast x_i$$ Dove $w_1,...,w_n$ sono i pesi della combinazione lineare.

Nella classificazione non lineare la classificazione di $X$ è effettuata utilizzando una funzione non lineare degli attributi di X, ovvero dove gli attributi possono assumere potenze diverse dalla prima.

4.2.1 Esempio: lineare binaria vs non lineare binaria

Nella classificazione binaria le osservazioni possono essere separate in due classi differenti. Utilizzare la classificazione lineare binaria si traduce nel trovare un iperpiano separatore che possa suddividere le osservazioni nelle due classi. Si utilizza una classificazione non binaria quando non esiste una funzione lineare in grado di separare tali dati.

4.3 Perceptron

Perceptron è un algoritmo di classificazione lineare binaria. La classificazione viene effettuata sulla base di una funzione predittiva lineare che si ottiene combinando un insieme di pesi con il vettore degli attributi dell'oggetto. In generale, l'algoritmo perceptron è utilizzabile solo quando il dataset risulta separabile linearmente.

Supponiamo di avere due classi $\{0,1\}$, data l'osservazione $X$, la funzione predittiva è: $$f(X)=\{\begin{array}{l}1ifwX+b>0\\ 0otherwise\end{array}$$ con w vettore di pesi con cardinalità pari a quella degli attributi + 1. Perceptron effettua un apprendimento online: gli elementi del training set vengono processati uno per volta e i pesi aggiornati ogni volta che un nuovo elemento è preso in esame. Il modello prodotto, chiamato anche single-layer Perceptron, è una rete neurale single-layer. Esistono anche multi-layer Perceptron, che combinano più funzioni di aggregazione.

4.3.1 Definizioni preliminari

Introduciamo alcune notazioni:

• Sia $D=\{(x_1,d_1),...,(x_n,d_n)\}$ il training set, con $x_j$ una tupla e $d_j$ la rispettiva classe (0 o 1).
• Sia $r$ il learning rate, un valore tra 0 e 1 che determina la grandezza della variazione dei pesi ad ogni passo, $r$ è un iperparametro.
• Sia $y_j=f(x_j)$ la classe di output predetta dal perceptron (0 o 1) per la j-esima tupla del training set D.
• $x_{j,i}$ rappresenta l' i-esimo attributo della j-esima tupla $x_j$ del training set D.
• Si pone convenzionalmente $x_{j,0}=1$ (l'attributo di indice 0).
• Sia $w_i(t)$ il peso della i-esima feature al passo t.

Dal momento che $x_{j,0}=1$, allora $w_0(t)$ equivale alla costante b nell'espressione $f(X)$.

4.3.2 Procedura

Supponiamo che ogni tupla del dataset abbia k attributi, l'algoritmo Perceptron esegue i seguenti passaggi

• (1) Inizializza i pesi $w_i(t=0)$ al valore 0 o ad un valore random piccolo.

• (2) Per ogni coppia $(x_i,d_i)\in D$ :

  • (2.1) Calcola l'output attuale:

  $$y_j(t)=f[w(t)\ast x_i]=f[w_0(t)x_{j,0}+w_1(t)x_{j,1}+...+w_k(t)x_{j,k}]$$

  • (2.2) Aggiorna ognuno dei pesi $w_j$:

  $$w_j(t+1)=w_j(t)+r\ast (d_i-y_i(t))\ast x_{i,j}$$

• (3) Nel caso di learning offline, ripeti il passo n.2 sino a quando l'errore medio di classificazione è inferiore ad una soglia $\gamma$, oppure un numero predefinito di iterazioni è stato completato.

N.B. L'errore medio di classificazione è ottenuto attraverso la seguente formula: $$E=\frac{1}{n}\sum _{i=1}^n|d_i-y_j(t)|$$ Nella pratica, il passo 2 viene iterato affinché la retta (o in generale, l'iperpiano) trovi i coefficienti adatti a separare l'intero dataset in due classi distinte. Ipotizziamo che al tempo t vi sia un errore, l'aggiornamento dei pesi ridefinirà ognuno dei pesi (da utilizzare al prossimo passo $t+1$) come segue: $$w_j(t+1)=w_j(t)+r\ast (d_i-y_i(t))\ast x_{i,j}$$ Dove:

• $w_j(t)$ è la componente j-esima del vettore dei pesi al tempo t
• $d_i-y_i(t)$ sarà nullo nel caso in cui la classificazione sia corretta, -1 nel caso in cui il punto sta al di sotto della retta (o dell'iperpiano), 1 nel caso in cui sia al di sopra.
• $x_{i,j}$ è la j-esima componente del punto $x_i$, classificato al tempo t.
• r è il learning rate, che a seconda della grandezza definisce con quale velocità la retta (o l'iperpiano) converge alla posizione ideale. Tuttavia, un learning rate alto potrebbe causare più errori durante il procedimento.

5. Support Vectors machines

5.1 Idea generale

Il metodo Support Vectors Machines è un metodo di classificazione binaria, ovvero le osservazioni sono classificate in due sole classi. Se i dati del training set sono linearmente separabili, allora l'SVM trova l'iperpiano separatore ottimale, ovvero quell'iperpiano che li separi al meglio. Se i dati non sono linearmente separabili, allora essi vengono prima trasferiti in uno spazio con un numero di dimensioni maggiore, attraverso una operazione di mapping. Con l'aumentare delle dimensioni aumenta anche il volume dello spazio e, di conseguenza, i dati tendono a separarsi maggiormente, per cui è molto più probabile che diventino linearmente separabili. Si può dimostrare che per ogni insieme di dati esiste uno spazio con un numero di dimensioni sufficientemente grande tale che i dati siano linearmente separabili. Una volta eseguito il mapping, SVM procede trovando l'iperpiano separatore ottimale.

5.2 Iperpiano ottimale e vettori di supporto

Definiamo i vettori di supporto (support vectors) come le osservazioni più vicine all'iperpiano separatore. Tali osservazioni sono le più complesse da classificare; in generale più un punto è lontano dall'iperpiano separatore, più è certa la appartenenza alla classe.

I vettori di supporto servono a stabilire quale tra gli iperpiani che separano linearmente i punti è quello ottimale. Introduciamo i margini come le distanze tra questi vettori di supporto e l'iperpiano. L'iperpiano separatore ottimale è quello che massimizza i margini.

5.3 Condizioni sui punti

Possiamo rappresentare un iperpiano a $k$ dimensioni con la seguente equazione: $$\begin{gathered} \bar{w}\ast \bar{x}+b=0 \\ {w}_1\ast x_1+...+w_k\ast x_k+b=0 \end{gathered}$$ Dove con $\bar{w}\ast \bar{x}$ si intende il prodotto scalare tra un vettore dei pesi $\bar{w}$ e delle incognite $\bar{x}$, e $b$ è uno scalare detto bias. Essendovi due classi, possiamo stabilire la classe di una osservazione a seconda che stia sopra o sotto l'iperpiano. Sia $\bar{x}$ una osservazione, allora: $$\begin{gathered} \bar{w}\ast \bar{x}+b>0\Rightarrow class(\bar{x})=+1 \\ \bar{w}\ast \bar{x}+b<0\Rightarrow class(\bar{x})=-1 \end{gathered}$$ Tuttavia, utilizzando solo questa condizione andrebbe bene qualsiasi iperpiano che separi le due classi. Imponiamo invece che ogni punto al di sopra dell'iperpiano rispetti la seguente condizione: $$(1)class(\bar{x})=+1⟺\bar{w}\ast \bar{x}+b\ge +1$$ Simmetricamente, per i punti al di sotto dell'iperpiano: $$(2)class(\bar{x})=-1⟺\bar{w}\ast \bar{x}+b\le -1$$ Se un punto rappresenta un vettore di supporto, ovvero risiede nella frontiera della separazione, allora: $$\begin{gathered} (1.1)class(\bar{x})=+1and\bar{x}issupportvector⟺\bar{w}\ast \bar{x}+b=+1 \\ (2.1)class(\bar{x})=-1and\bar{x}issupportvector⟺\bar{w}\ast \bar{x}+b=-1 \end{gathered}$$ Risulta scomodo dover considerare due condizioni (1, 2) da applicare ai punti. È possibile ridurre entrambe le espressioni ad una sola espressione, introducendo la variabile $y_i$ come segue:
$$y_i=\{\begin{array}{l}+1ifclass(x_i)=+1\\ -1ifclass(x_i)=-1\end{array}$$ Le condizioni vengono ridotte alla seguente espressione: $$(3.1)y_i(\bar{w}\ast \bar{x}+b)\ge 1$$ O anche: $$(3.2)y_i(\bar{w}\ast \bar{x}+b)-1\ge 0$$ Esempio: consideriamo un punto al di sotto dell'iperpiano separatore, per cui $y_i=-1$. Se il punto rispetta il vincolo (2), producendo un certo scalare $a<-1$, allora il prodotto rispetta il vincolo (3): $$y_i(\bar{w}\ast \bar{x}+b)\ge 1=(-1)(a)\ge 1$$ Analogamente per i punti al di sopra dell'iperpiano.

5.4 Larghezza del margine

L'obiettivo principale è quello di massimizzare il margine, ovvero la distanza tra i vettori di supporto delle due diverse classi. Ma come otteniamo la larghezza del margine? Consideriamo un vettore di supporto $v$ di classe $+1$ ed un vettore di supporto $u$ di classe $-1$. Ipotizziamo di avere il versore w normale all'iperpiano: