L'analisi discriminante lineare (ADL) o analisi discriminante normale o analisi della funzione discriminante è una generalizzazione della discriminante lineare di Fisher, un metodo usato in statistica, nel riconoscimento di pattern, nell'apprendimento automatico per trovare una combinazione lineare di caratteristiche che raggruppano o separano 2 o più classi di oggetti o eventi. La combinazione risultante può essere usata come un classificatore lineare, o più comunemente per una riduzione dimensionale prima di una classificazione statistica.

L'ADL è strettamente correlata all'analisi della varianza (ANOVA) e all'analisi della regressione che anche tentano di esprimere la variabile dipendente come una combinazione lineare di altre caratteristiche o misure. Tuttavia l'ANOVA usa variabili indipendenti qualitative per spiegare una variabile dipendente continua, invece l'analisi del discriminante usa variabili indipendenti continue per spiegare una variabile dipendente qualitativa (per esempio: l'etichetta della classe)Analyzing Quantitative Data: An Introduction for Social Researchers, Debra Wetcher-Hendricks, p.288. La regressione logistica e il modello probit sono più simili all'ADL di quanto lo sia l'ANOVA in quanto spiegano una variabile qualitativa per mezzo di variabili indipendenti continue. Questi altri metodi sono preferibili in applicazioni dove non è ragionevole assumere che le variabili indipendenti siano normalmente distribuite, che è una ipotesi fondamentale del metodo ADL.

Storia L'analisi discriminante dicotomica è stata sviluppata originariamente da Ronald Fisher nel 1936 . Essa si differenzia dall'ANOVA o dalla MANOVA, le quali vengono utilizzate per predire una (ANOVA) o più (MANOVA) variabili continue dipendenti attraverso una o più variabili categoriche indipendenti. L'ADL è utile a determinare se un insieme di variabili sia efficace nel prevedere l'appartenenza a una categoria.

ADL per due classi Si consideri un insieme di osservazioni (dette anche caratteristiche, attributi, variabili o misurazioni) per ogni campione di oggetto o evento di classe nota . L'insieme di campioni (esempi) è detto training set nell'ambito dell'apprendimento supervisionato. Il problema di classificazione è allora quello trovare un buon predittore della classe di ciascun campione dalla stessa distribuzione (non necessariamente appartenente al training set) data la sola osservazione .

La ADL affronta il problema assumendo che le funzioni di densità di probabilità condizionate e siano entrambe normali con parametri di media e covarianza e , rispettivamente. Sotto tale assunzione, la soluzione bayesiana ottimale è predire che i punti appartengano alla seconda classe se il logaritmo dei rapporti delle verosimiglianze è più grande di una data soglia , cosicché:

Se non si fanno altre assunzioni il classificatore risultante viene definito attraverso la cosiddetta analisi discriminante quadratica.

Invece l'ADL fa l'ulteriore assunzione semplificativa di omoschedasticità (i.e. che le covarianze delle classi siano identiche, per cui ) con matrice di covarianza di rango massimo. In tal caso, si possono eliminare diversi termini:

essendo Hermitiana

e il criterio di decisione sopra descritto diventa una soglia posta sul prodotto scalare

per una certa soglia costante , per cui

Ciò significa che il criterio per determinare l'appartenenza dell'esempio alla classe si riduce a una funzione di questa combinazione lineare di osservazioni note.

Spesso è utile riconsiderare questa conclusione in termini geometrici: il criterio per determinare l'appartenenza dell'esempio alla classe è meramente una funzione di proiezione del punto di uno spazio multidimensionale su un vettore (pertanto, si considera solo la direzione). In altre parole, l'esempio appartiene a se è posto su un certo lato di un iperpiano perpendicolare a . La posizione del piano viene definita dalla soglia .

Assunzioni Le asunzioni dell'analisi discriminante sono le stesse di quelle della MANOVA. L'analisi è piuttosto sensibile agli outlier e la dimensione del gruppo più piccolo deve essere superiore al numero delle variabili predittive.

Normalità multivariata: le variabili indipendenti sono normali per ciascun livello della variabile di raggruppamento. Omogeneità della varianza/covarianza (omoschedasticità): le varianze tra le variabili di gruppo sono le stesse nei diversi predittori. Può essere verificata con il test basato sulla statistica M di Box. È tuttavia consigliabile di utilizzare l'analisi discriminante lineare quando le covarianze sono uguali e l'analisi discriminante quadratica quando le covarianze non sono uguali. Indipendenza: si presume che i partecipanti siano campionati in modo casuale e che il punteggio di un partecipante su una variabile sia indipendente dai punteggi su quella variabile per tutti gli altri partecipanti.

È stato suggerito che l'analisi discriminante sia relativamente robusta rispetto a lievi violazioni di queste ipotesi ed è stato anche dimostrato che l'analisi discriminante può essere comunque affidabile quando si utilizzano variabili dicotomiche (dove spesso viene violata l'assunzione di normalità multivariata).

ADL di Fisher I termini discriminante lineare di Fisher e LDA sono spesso usati in modo intercambiabile sebbene l'articolo originale di Fisher descriva in realtà un discriminante leggermente differente, che non fa alcune delle assunzioni della ADL come la normalità della distribuzione delle classi o l'uguaglianza delle covarianze delle classi.

Si supponga che le due classi di osservazioni abbiamo medie e covarianze . Allora la combinazione lineare di feature avrà media e varianze per . Fisher ha definito la separazione tra queste due distribuzioni come il rapporto fra la varianza tra le classi e la varianza nelle classi:

Tale misura è, in un certo senso, una misura del rapporto segnale/rumore per l'etichettatura delle classi. Si può dimostrare che la separazione è massima quando

.

Quando sono soddisfatte le assunzioni della ADL, l'equazione precedente è equivalente alla ADL.

Si noti che il vettore è normale rispetto all'iperpiano discriminante. Ad esempio, in un problema bidimensionale, la retta che meglio divide i due gruppi è perpendicolare a .

In generale, i punti da discriminare sono proiettati su ; poi si sceglie la soglia che meglio separi i dati in base all’analisi della distribuzione mono-dimensionale. Non c'è una regola generale per la soglia. Tuttavia, se le proiezioni dei punti di entrambe le classi esibiscono approssimativamente le stesse distribuzioni, una buona scelta sarebbe quella dell'iperpiano tra le proiezioni delle due medie, e . In tal caso il parametro c nella condizione di soglia può essere trovato esplicitamente:

.

Il metodo di Otsu è correlato al discriminante lineare di Fisher ed è stato creato per binarizzare l'istogramma dei pixel in una immagine in scala di grigi scegliendo in modo ottimale la soglia bianco/nero che minimizza la varianza intra-classe e massimizzi la varianza inter-classe all'interno/fra scale di grigio assegnate alle classi di pixel bianchi e neri.

ADL Multiclasse Nel caso in cui vi siano più di due classi, l'analisi utilizzata nella derivazione del discriminante di Fisher può essere estesa per trovare un sottospazio che possa contenere tutta la variabilità di ciascuna classe. Garson, G. D. (2008). Discriminant function analysis. Tale generalizzazione è dovuta a C. R. Rao. Si supponga che ciascuna delle classi abbia una media e la stessa covarianza . Allora la dispersione tra le variabilità delle classi può essere definita dalla covarianza campionaria delle medie delle classi

dove è la media delle medie delle classi. In tal caso la separazione delle classi in una certa direzione sarà data

Ciò significa che quando è un autovettore di la separazione sarà uguale all'autovalore corrispondente.

Se è diagonalizzabile, la variabilità fra feature sarò contenuta nel sottospazio generato dagli autovettori corrispondenti ai autovalori più grandi (dato che ha al più rango ). Questi autovettori sono utilizzati principalmente nella riduzione delle feature, come nella PCA. Gli autovettori corrispondenti agli autovalori più piccoli tenderanno ad essere molto sensibili alla scelta esatta dei dati di addestramento, e spesso è necessario ricorrere alla regolarizzazione, come descritto nella sezione successiva.

Se si desidera effettuare la classificazione anziché la riduzione della dimensionalità, esistono diverse tecniche alternative. Ad esempio, è possibile partizionare le classi e utilizzare un discriminante di Fisher standard o un ADL per classificare ciascuna partizione. Una modalità comune è quella “uno contro tutti”, in cui gli esempi di una classe vengono inseriti in un gruppo e tutti gli altri in un altro, quindi viene applicato l'ADL. Ciò darà luogo a classificatori, i cui risultati vengono combinati. Un altro metodo comune è la classificazione a coppie, in cui viene creato un nuovo classificatore per ogni coppia di classi (ottenendo un totale di classificatori), con i singoli classificatori combinati per produrre una classificazione finale.

ADL Incrementale L'implementazione tipica della ADL richiede che tutti i campioni siano disponibili in anticipo. Tuttavia, ci sono situazioni in cui non è disponibile l'intero insieme di dati in quanto i dati di input vengono osservati come flusso. In tal caso, è auspicabile che l'estrazione delle caratteristiche ADL sia in grado di aggiornare le caratteristiche ADL calcolate sulla base dei nuovi campioni senza ri-eseguire l'algoritmo sull'intero insieme di dati. Ad esempio, in molte applicazioni in tempo reale come la mobilità robotica o il riconoscimento facciale online, è importante aggiornare le feature ADL estratte allorché si rendano disponibili nuove osservazioni. Una tecnica di estrazione delle feature ADL in grado di aggiornare le feature semplicemente sulla base di nuovi campioni è un algoritmo ADL incrementale, un'idea ampiamente investigata negli ultimi due decenni. Chatterjee e Roychowdhury hanno proposto un algoritmo ADL incrementale auto-organizzato per l'aggiornamento delle feature. In un altro lavoro, Demir e Ozmehmet hanno proposto algoritmi di apprendimento locale online per l'aggiornamento incrementale delle feature che utilizzano regole di correzione degli errori e apprendimento di Hebb. Successivamente, Aliyari et al. hanno derivato algoritmi incrementali veloci per aggiornare le feature ADL in base a nuovi campioni.

Applicazioni Predizione di bancarotta Riconoscimento dei volti Marketing Studi biomedici Scienze della terra

Note

Altri progetti

Collegamenti esterni

contains open-source LDA implementation in C# / C++ / Pascal / VBA.

Categoria:Algoritmi di classificazione