# Analisi discriminante

L'analisi discriminante è una disciplina statistico-matematica sviluppata per separare oggetti ed osservazioni in classi distinte (clustering) e per allocare nuove osservazioni in una delle classi precedentemente definite (classificazione). Gli oggetti possono essere immagini (come foto, documenti scritti, video), impronte digitali, visi di persone, segnali elettromagnetici, raggi cosmici, esami del sangue o in generale qualsiasi tipo di misurazione che necessita di una classificazione. Quando la classificazione degli oggetti in classi viene operata da sistemi basati sull’intelligenza artificiale (machine intelligence), sistemi cioè realizzati con il preciso scopo di prendere decisioni, tali oggetti vengono indicati con il termine generico di pattern mentre le variabili osservate si dicono features. In tale contesto si è soliti riferirsi all’analisi discriminante con il termine di riconoscimento di pattern.

## Analisi discriminante lineare

L’analisi discriminante si definisce lineare quando i classificatori impiegati sono funzioni lineari nelle osservazioni e godono della proprietà di discriminare le osservazioni tra le classi meglio di qualsiasi altra funzione lineare. Esempi di applicazione dell’analisi discriminante lineare sono:
* la misurazione delle variabili economiche e finanziarie estratte dai bilanci societari (indici di bilancio) le quali concorrono al punteggio complessivo della funzione discriminante. Sulla base dei punteggi ottenuti si determina la probabilità di insolvenza/bancarotta delle società (z-score di Altman)
* la distinzione tra flussi di protoni e neutrini nell’analisi energetica della composizione spettrale dei raggi cosmici (Osservatorio Pierre Auger, ultra high-energy comsic rays)
* l’analisi delle dichiarazioni dei redditi nella lotta all’evasione fiscale nota come studio di settore
Se ad esempio sono assegnati 2 campioni costituiti rispettivamente da $n_{1}$ e $n_{2}$ oggetti e si considera un numero p di variabili ${\mathbf {x} }=(x_{1},\ldots ,x_{p})$ da misurare allora una volta effettuate le p misurazioni $x_{1},\ldots ,x_{p}$ su ciascuno degli $n_{1}+n_{2}$ oggetti la funzione discriminante lineare è della forma
    $z=f(x)=b_{1}x_{1}+\ldots +b_{p}x_{p}$
La funzione discriminante risulta essere una combinazione lineare delle variabili $x_{1},\ldots ,x_{p}$ con coefficienti gli scalari $b_{1},\ldots ,b_{p}$. I coefficienti della funzione discriminante vengono scelti in modo tale da meglio distinguere gli oggetti di una classe da quelli dell’altra. La distinzione tra le classi viene operata grazie al valore numerico $z$ assunto dalla funzione discriminante rispetto ad un valore di riferimento $z_{0}$.
Nell’esempio delle due classi si dice che la generica osservazione ${\mathbf {x} '}=(x'_{1},\ldots ,x'_{p})$ appartiene alla classe 1 se risulta
$z'=b_{1}x'_{1}+\ldots +b_{p}x'_{p}>z_{0}$
Diversamente si attribuisce l’osservazione $x'$ alla classe 2 se risulta
$z'=b_{1}x'_{1}+\ldots +b_{p}x'_{p}<z_{0}$
Compito primario dell'analisi discriminante lineare è trovare le combinazioni lineari delle variabili tali per cui la differenza tra le classi è massima. Il punto di partenza fondamentale per determinare i coefficienti della funzione discriminante risiede nella misura che si intende adottare per valutare la somiglianza, la similarità tra le osservazioni in esame. La misura della similarità per variabili di tipo quantitativo si attua ricorrendo ad una funzione opportuna che prende il nome di distanza o metrica.

## Regola di classificazione

Una volta adottata una distanza d capace di esprimere la nozione di vicinanza per le osservazioni, risulta possibile introdurre una regola di classificazione per le osservazioni rispetto ad un rappresentante di ciascuna classe. Il carattere statistico dell'analisi discriminante scaturisce dal fatto che la media o la media campionaria delle popolazioni in esame viene scelta essere il rappresentante di ciascuna classe. Nell’esempio delle due classi, indicato con $m_{1}$ la media della prima popolazione e con $m_{2}$ la media della seconda popolazione, si attribuisce l’osservazione $x$ alla classe 1 se
    $d(m_{1},x)<d(m_{2},x)$
ossia se $x$ è più vicino a $m_{1}$. Ricordato che ogni prodotto scalare definito positivo $\langle \mathbf {.} ,\mathbf {.} \rangle$ induce una norma e che a sua volta la norma induce una metrica, risulta possibile introdurre un prodotto scalare opportuno per definire la regola di classificazione. È sufficiente considerare $d^{2}(m,x)=\|m-x\|^{2}=\langle \mathbf {m} -x,\mathbf {m} -x\rangle$ per esprimere la regola di appartenenza alla classe 1 in termini di prodotto scalare come
    $\langle \mathbf {m} _{1}-x,\mathbf {m} _{1}-x\rangle <\langle \mathbf {m} _{2}-x,\mathbf {m} _{2}-x\rangle$
La relazione appena scritta, sfruttando la proprietà di bilinearità del prodotto scalare, può riscriversi dopo semplici passaggi come
    $\langle \mathbf {m} _{1}-m_{2},\mathbf {x} -1/2(m_{1}+m_{2})\rangle >0$
Indicato con
    $x_{0}=1/2(m_{1}+m_{2})$
la regola di classificazione per gli elementi della classe 1 diviene
    $C_{1}:\langle \mathbf {m} _{1}-m_{2},\mathbf {x} -x_{0}\rangle >0$
mentre per gli elementi della classe 2 è
    $C_{2}:\langle \mathbf {m} _{1}-m_{2},\mathbf {x} -x_{0}\rangle <0$

## L'iperpiano discriminante

Vediamo ora il caso in cui $x$ è tale per cui risulta $\langle \mathbf {m} _{1}-m_{2},\mathbf {x} -x_{0}\rangle =0$. L’equazione appena scritta rappresenta l’equazione normale di un iperpiano che passa per $x_{0}$ ed è perpendicolare al vettore $m_{1}-m_{2}$. Si è soliti chiamare tale iperpiano come iperpiano discriminante e consiste di tutti i vettori $x$ per i quali $x-x_{0}$ risulta ortogonale al vettore $m_{1}-m_{2}$. Lo spazio delle variabili risulta così diviso dall’iperpiano discriminante in due semispazi aperti: $C_{1}$ e $C_{2}$. Si osservi che il prodotto scalare adottato essendo definito positivo risulta essere non degenere, per cui valendo $\langle \mathbf {m} _{1}-m_{2},\mathbf {x} -x_{0}\rangle =0$ per qualsiasi $m_{1}-m_{2}$ necessariamente deve essere $x-x_{0}=0$, in altre parole non è possibile discriminare a quale classe appartenga l’osservazione $x$ qualora si abbia $x=x_{0}$. Il punto individuato dal vettore $x_{0}$ viene detto cut-off point.

## La funzione discriminante lineare

L’espressione matriciale di una forma bilineare simmetrica $\langle \mathbf {.} ,\mathbf {.} \rangle$ applicata ai vettori$m_{1},m_{2},x$ è la seguente
    $\langle \mathbf {m} _{1}-m_{2},\mathbf {x} -x_{0}\rangle =(m_{1}-m_{2})^{t}A_{R}(x-x_{0})$
dove $A_{R}$ è la matrice associata al prodotto scalare nel sistema di riferimento $R$.
I vettori della Classe 1 sono soluzione della disequazione matriciale seguente
    $(m_{1}-m_{2})^{t}A_{R}(x)>(m_{1}-m_{2})^{t}A_{R}(x_{0})$
Note le medie delle due classi $m_{1}$ e $m_{2}$, l'espressione
    $(m_{1}-m_{2})^{t}A_{R}(x)$
risulta essere una funzione lineare nelle osservazioni $x$ e a tale espressione ci si riferisce con il termine di funzione discriminante lineare.
Posto $a=m_{1}-m_{2}$ ed indicato con $a_{0}=\langle \mathbf {m} _{2}-m_{1},\mathbf {x} _{0}\rangle$ si giunge ad una scrittura più snella e compatta per la funzione discriminante. Adottato come notazione per il prodotto scalare il simbolo $\cdot$ si può scrivere
    $z=f(x)=a\cdot x+a_{0}$
Si attribuisce l'osservazione $x$
* alla classe 1 se risulta $z=a\cdot x>a_{0}$
* alla classe 2 se risulta $z=a\cdot x<a_{0}$

### La funzione discriminante lineare nella sua forma più semplice

Scelto come riferimento R una base qualsiasi, la regola di classificazione per la Classe 1 scritta per esteso è
$\sum _{i=1}^{p}\sum _{j=1}^{p}c_{i,j}\cdot a_{i}\cdot x_{j}>-1/2\sum _{i,j=1}^{p}c_{i,j}\cdot (m_{1i}-m_{2i})\cdot (m_{1j}+m_{2j})$
dove si è indicato con $c_{i,j}$ l'azione del prodotto scalare sui vettori della base. Si ricerca quindi di individuare un diverso riferimento R’ per il quale l’espressione polinomiale risulti essere più semplice. Dal momento che il prodotto scalare adottato è stato ipotizzato essere definito positivo, si può essere certi che esiste un riferimento R’ ortonormale rispetto al quale la matrice associata a $\langle \mathbf {.} ,\mathbf {.} \rangle$ risulti essere diagonale. Indicata con $M_{R}^{R^{'}}$ la matrice del cambiamento delle variabili nel passaggio dal riferimento R al riferimento R’ (sostituzione lineare delle variabili), il teorema spettrale garantisce la riduzione in forma diagonale della matrice $A_{R}$
$\langle \mathbf {a} ,\mathbf {x} \rangle =x^{t}\cdot (M_{R}^{R^{'}}\cdot A_{R}\cdot M_{R^{'}}^{R})\cdot a=x^{t}\cdot D_{R^{'}}\cdot a$
Rispetto al sistema di riferimento R’ il prodotto scalare $\langle \mathbf {.} ,\mathbf {.} \rangle$ risulta quindi essere esprimibile come un polinomio omogeneo di secondo grado con ciascun dei due gruppi di p variabili che separatamente presentano grado uno:
    $z=\langle \mathbf {a} ,\mathbf {x} \rangle =\sum _{i=1}^{p}\lambda _{i}a_{i}x_{j}=\lambda _{1}a_{1}x_{1}+...+\lambda _{p}a_{p}x_{p}$
dove $\lambda _{i}$ sono gli elementi posti sulla diagonale principale della matrice $D_{R^{'}}$.
Posto $b_{i}=\lambda _{i}a_{i}$ per ogni $i=1,...,p$ la forma più semplice della funzione discriminante è la seguente
    $z=b_{1}x_{1}+...+b_{p}x_{p}$
Il punteggio di soglia $z_{0}$ nel riferimento R' è dato da
    $z_{0}=\langle \mathbf {m} _{2}-m_{1},\mathbf {0} ,5(m_{1}+m_{2})\rangle =0,5l_{1}(m_{21}^{2}-m_{11}^{2})+...+0,5l_{p}(m_{2p}^{2}-m_{1p}^{2})$

## Storia

La statistica antropologica aveva sviluppato metodi per attribuire degli individui "dubbi" ad un gruppo piuttosto che ad un altro. Questi metodi erano però talmente legati all'antropologia che era difficile usarli in altri ambiti.
Nel 1936 R. A. Fisher pubblicò in The use of multiple measurements in taxonomic problems il primo metodo astratto per la suddivisione di "individui" in gruppi che non fosse legato ad una particolare scienza. Tale metodo è quello oggi noto come analisi discriminante lineare e venne poi sviluppato ulteriormente fino alla analisi discriminante multivariata. Fisher nello specifico determinò la regola per ripartire, classificare 50 fiori di Iridacee coltivati assieme nella medesima serra tra due specie: una era l'Iris setosa e l'altra era l'Iris versicolore. La distinzione venne compiuta sulla base dei valori assunti da quattro variabili (caratteri, features, fattori) quantitative ed oggetto di misurazione: la lunghezza del sepalo $x_{1}$, la larghezza del sepalo $x_{2}$, la lunghezza del petalo $x_{3}$ e la larghezza del petalo $x_{4}$. La ripartizione tra i due gruppi (Iris setosa o Iris versicolore) venne effettuata da Fisher esprimendo le quattro variabili come combinazione lineare con il parametro ${\mathbf {a} }=(a_{1},\ldots ,a_{4})$. Ciascuna componente del parametro $a_{i}$ venne scelta in modo da discriminare le miglior modo l'appartenenza di un fiore ad uno dei gruppi sulla base delle misure ${\mathbf {x} }=(x_{1},\ldots ,x_{4})$ per esso disponibili. Il parametro ${\mathbf {a} }$ venne scelto in modo da massimizzare il rapporto tra le medie dei due gruppi e la deviazione standard (o varianza) all'interno di ciascun gruppo.
    $f({\mathbf {x} })=a_{1}x_{1}+\ldots +a_{4}x_{4}$
La funzione discriminante ottenuta veniva così a costituire la regola di assegnazione dei fiori alle due specie: il carattere previsionale dell’analisi risiedeva nel fatto che la funzione discriminante fu generata da 2 gruppi (sotto-popolazioni o campioni) per i quali si conoscevano 50 osservazioni delle 4 variabili- Per ciascuna osservazione era noto a quale specie appartenesse il fiore in esame. L’applicazione della funzione discriminante ad un nuovo fiore di cui non si fosse conosciuta la specie di appartenenza avrebbe consentito di assegnare, grazie alla misurazione delle quattro variabili, la specie di appartenenza del fiore.

## Analisi discriminante lineare ed Intelligenza Artificiale

In generale un algoritmo riceve un insieme di valori in ingresso (dati di input) e da questi genera un valore di uscita detta soluzione (dato di output). Scrivere un algoritmo significa definire una funzione $f$ che associ ad ogni dato di input $x$ la corrispondente uscita. Una volta fornita all'elaboratore la sequenza delle istruzioni che descrivono $f$ e che permettono di calcolare il risultato $y=f(x)$, l’elaboratore sarà in grado di determinare la soluzione $y$ in corrispondenza dello specifico dato di input $x$. Qualora il programmatore non specifichi all'elaboratore le operazioni per giungere da $x$ al risultato $y$, ma fornisce allo stesso l’abilità di apprendere attraverso esempi come giungere alla soluzione del problema si entra nel campo dell'apprendimento automatico supervisionato (supervised learning). Formalmente un modello matematico di apprendimento automatico consiste di un dominio $X$ (insieme dei dati di input) e di un insieme di arrivo $Y$ (insieme degli output). L’apprendimento automatico si interessa di scoprire o di stimare la funzione $f\colon X\to Y$ tale che $y=f(x)$.
Il termine supervisionato deriva dal fatto che è disponibile un insieme di esempi (training set) di coppie di dati etichettati:
    Training Set, $T:=\left\{(x_{1},y_{1}),(x_{2},y_{2}),\ldots ,(x_{m},y_{m})\right\}$
sulla base dei quali si dovrà determinare la funzione $f$. Il carattere predittivo della funzione $f$ risiede nel fatto che $f$ è in grado di prevedere l’output $y$ per valori non osservati di $x$, ossia non appartenenti al training set. Questo modo di agire dell’elaboratore ricalcherebbe quel processo psichico tipico dell'apprendimento animale per prove ed errori che consiste nell'imparare da esempi etichettati (esperienza) per poi modificare l'output di risposta a seguito di un input dato. Si riscontra dunque una sorta di apprendimento cognitivo in quanto vengono colte le relazioni essenziali nel problema: si tratta di un processo di acquisizione di conoscenza consistente nello scoprire l’associazione esistente tra i dati $(x,y)$ perpetrata attraverso l’analisi di un campione ridotto di dati (training set), ed estesa poi alla totalità della popolazione dei dati di input $X$ e dei dati di output $Y$.
Nei problemi di classificazione gli elementi $y$ di $Y$ sono classi nel senso che rappresentano le categorie con cui i diversi dati di input vengono etichetti. Agli input $x_{i}$ del training set è assegnata (etichettata) una classe $1\leq j\leq k$ e si è interessati a determinare la funzione $f$ che assegni ogni $\mathbf {x} \in X\subseteq \mathbb {R} ^{n}$ ad una delle $k$ classi disgiunte $C_{1},C_{2},\ldots ,C_{k}$ laddove $C_{j}\subseteq \mathbb {R} ^{n}$ per $j=1,2,\ldots ,k$ e $C_{i}\cap C_{j}=\varnothing$ per $i\neq j$.
Formalmente per $j=1,\ldots ,k$ si ha
    $f(\mathbf {x} )=\left\{{\begin{array}{l}y_{i}\quad se\mathbf {\quad } \mathbf {x} \in C_{j}\\0\quad altrimenti\\\end{array}}\right.$

### Esempi

I seguenti esempi di classificazione costituiscono modelli di classificazione binari lineari in quanto la funzione $f(\mathbf {x} )$ è rappresentata da una funzione lineare di $\mathbf {x}$ che separa gli elementi delle due classi per mezzo di un iperpiano. I diversi modelli si differenziano per il diverso metodo di apprendere (calcolare) i parametri incogniti di $\mathbf {a}$ e $a_{o}$ che definiscono l’iperpiano separatore $f(\mathbf {x} )=\langle \mathbf {a} ,\mathbf {x} \rangle$; la notazione $\langle \mathbf {a} ,\mathbf {x} \rangle$ rappresenta un prodotto scalare opportuno.

#### Classificazione binaria secondo R. Fisher (1936)

    $Y=\mathbb {R} ,f\colon X\subseteq \mathbb {R} ^{n}\to \mathbb {R}$
    $f(\mathbf {x} )=\langle \mathbf {a} ,\mathbf {x} \rangle +a_{0}=\left\{{\begin{array}{l}>0\quad se\mathbf {\quad } \mathbf {x} \in C_{1}\\<0\quad se\mathbf {\quad } \mathbf {x} \in C_{2}\\\end{array}}\right.$

#### Classificazione binaria secondo F. Rosenblatt (perceptrone, 1958).

La convergenza dell’algoritmo ai valori di $\mathbf {a}$ e $a_{0}$ venne fornita da A. Novikoff nel 1962 sotto l’ipotesi che le due classi fossero linearmente separabili.

#### Classificazione binaria secondo V. Vapnik - A. Cherrnovenkis (macchine a vettori di supporto, 1963)

    $Y=\mathbb {R} ,f\colon X\subseteq \mathbb {R} ^{n}\to \mathbb {R}$
    $f(\mathbf {x} )=\langle \mathbf {a} ,\mathbf {x} \rangle +a_{0}=\left\{{\begin{array}{l}\geq 1\qquad se\mathbf {\quad } \mathbf {x} \in C_{1}\\\leq -1\quad se\mathbf {\quad } \mathbf {x} \in C_{2}\\\end{array}}\right.$