Nell'apprendimento automatico e nella classificazione statistica, la classificazione multiclasse (o multinomiale) è il problema di classificare le istanze in una di tre o più classi possibili (quella in due classi è la classificazione binaria). Ad esempio, decidere se un'immagine mostra una banana, una pesca, un'arancia o una mela è un problema di classificazione multiclasse, con quattro possibili classi (banana, pesca, arancia, mela), mentre decidere se un'immagine contiene o meno una mela è un problema di classificazione binaria (con due possibili classi: mela, nessuna mela).

Sebbene molti algoritmi di classificazione (in particolare la regressione logistica multinomiale) consentano naturalmente l'uso di più di due classi, alcuni sono per loro natura modelli binari; questi possono tuttavia essere trasformati in classificatori multinomiali mediante varie strategie.

La classificazione multiclasse non va confusa con la classificazione multietichetta, in cui è necessario predire anche più etichette per ciascuna istanza (ad esempio, predire che un'immagine contenga sia una mela che un'arancia, caso simile al precedente).

Modelli multiclasse better-than-random Data la matrice di confusione di un modello multiclasse, si può determinare se un modello funziona meglio del caso. Sia il numero di classi, un insieme di osservazioni, un modello della variabile target e sia il numero di osservazioni nell'insieme . Si userà la notazione: , , , e . Si supponga che la matrice di confusione contenga almeno un valore non nullo in ogni riga, ovvero per ogni . Infine si definisce la "matrice di confusione normalizzata" contenente le probabilità condizionali con elementi: .

Spiegazione intuitiva Il lift è un indice che misura la deviazione dall'indipendenza di due eventi e :

Si verifica che se e solo se gli eventi e si verificano simultaneamente con una probabilità maggiore rispetto a quella del caso in cui fossero indipendenti. In altre parole, se si verifica uno dei due eventi, la probabilità di osservare l'altro evento aumenta.

Una prima condizione da soddisfare è avere per ogni e la qualità di un modello (migliore o peggiore del caso) non cambia se si sovra- o sotto-campiona l'insieme dei dati, ossia se moltiplichiamo ogni riga della matrice di confusione per una costante . Pertanto la seconda condizione da soddisfare è che le condizioni necessarie e sufficienti per fare meglio del caso dipendano solo dalla matrice di confusione normalizzata.

La condizione sul lift può essere riformulata con modelli binari Una contro il Resto: per ogni , si definisca la variabile target binaria che è l'indicatore dell'evento e il modello binario di che è l'indicatore dell'evento . Ciascuno dei modelli sarà un modello "Una contro il Resto". dipende solo dagli eventi e , quindi unire o non unire le altre classi non ne modifica il valore. Si ha quindi che e la prima condizione è che tutti i modelli binari Uno contro il Resto siano migliori del caso.

Esempio Se e 2 è la classe di interesse, la matrice di confusione normalizzata è

e si ha

Pertanto . Allo stesso modo, scambiando i ruoli di 1 e 2, troviamo che . Dividendo per si trova che la condizione necessaria e sufficiente sulla matrice di confusione normalizzata è

Questo riporta alla classica condizione binaria: J di Youden deve essere positivo (o nullo per i modelli casuali).

Modelli casuali Un modello casuale è un modello indipendente dalla variabile target. Questa proprietà può essere facilmente formulata attraverso la matrice di confusione.

Proposizione: il modello di è casuale sse la matrice di confusione è di rango 1.

Tale proposizione dimostra che il modello di è poco informativo sse ci sono due famiglie di numeri e tale che per ogni e .

Rapporti di verosimiglianza multiclasse e rapporti di probabilità diagnostici Definiamo rapporti di verosimiglianza generalizzati calcolati facendo riferimento alla matrice di confusione normalizzata: per ogni e , sia . Quando , se la classe di interesse è la 2, si trovano i rapporti di verosimiglianza classici e . I rapporti di verosimiglianza diagnostici multiclasse possono anche essere definiti tramite la formula: Teorema: per ogni , Equivalentemente, se tutti i sono non nulli:

Corollario: Se tutte le probabilità sono fissate, per ogni e si ha: Equivalentemente, se tutti i sono non nulli:

.

Abbiamo visto sopra che un modello migliore del caso deve verificare per qualsiasi e . Secondo il corollario precedente, i rapporti di verosimiglianza sono quindi maggiori o uguali a 1. Viceversa, se i rapporti di verosimiglianza sono maggiori o uguali a 1, il teorema mostra che si ha per ogni e .

Definizione di modelli multiclasse migliori del caso Un modello di è superiore al caso se sono soddisfatte le seguenti condizioni:

Per ogni , si ha . Ci sono i e j distinti tali che .

Se tutti gli elementi della matrice di confusione sono diversi da zero, ciò significa che tutti i rapporti di verosimiglianza sono maggiori o uguali a 1 e almeno una di queste diseguaglianze è stretta. Un modello che soddisfa la prima condizione ma non la seconda è casuale, poiché allora si avrebbe per ogni e .

Si può riscrivere la prima condizione in un modo più familiare, denotando con il valore osservato di , con il valore da stimare di e con l'insieme : per ogni si ha . Se ne deduce che un modello è migliore del caso se e solo se è uno stimatore di massima verosimiglianza della variabile obiettivo.

Applicazioni Spazio ROC L'insieme delle matrici di confusione normalizzate è chiamato spazio ROC, un sottospazio di . Se denota il sottoinsieme dello spazio ROC costituito da modelli casuali o modelli che funzionano meglio del caso, si può dimostrare che il confine topologico di è l'insieme degli elementi di per cui almeno uno dei rapporti di verosimiglianza è uguale a 1. E i modelli casuali sono quei modelli i cui rapporti di verosimiglianza sono tutti uguali a 1. Quando , il confine tra i modelli che funzionano meglio del caso e i modelli cattivi è uguale all'insieme dei modelli casuali (vedere la voce sulla curva roc per maggiori dettagli), ma è strettamente più grande non appena E se , possiamo calcolare il volume occupato dai modelli errati nello spazio ROC: occupano il 90% di questo spazio, mentre solo il 50% quando .

Strategie algoritmiche generali Le tecniche di classificazione multiclasse esistenti possono essere categorizzate come segue:

trasformazione in casi binari estensione dei casi binari classificazione gerarchica.

Trasformazione in casi binari Questa sezione discute le strategie per ridurre il problema della classificazione multiclasse a problemi di classificazione binaria multipla. Ciò può essere categorizzato in uno contro il resto e uno contro uno. Le tecniche sviluppate sulla base della riduzione del problema multiclasse in problemi binari multipli possono anche essere chiamate tecniche di trasformazione del problema.

Uno-contro-resto La strategia Uno-contro-resto o uno-contro-tutti (acronimi in inglese OvR e OvA) prevede l'addestramento di un singolo classificatore per classe, con i campioni di quella classe come campioni positivi e tutti gli altri campioni come negativi. Questa strategia richiede che i classificatori di base producano un punteggio a valori reali per la sua decisione (vedere anche la regola di assegnazione punteggio), piuttosto che una semplice etichetta di classe; le sole etichette di classe discrete possono portare ad ambiguità, dove più classi sono predette per un singolo campione.

L'algoritmo in pseudo-codice per l'addestramento per un modello OvR costruito su un modello di classificazione binaria L è il seguente:

Input: L, modello (classificatore) binario campioni X etichette y dove yi ∈ {1, … , K} è l'etichetta per il campione Xi Output: elenco di classificatori fk per k ∈ {1, …, K} Procedura: Per ogni k in {1, …, K} Costruire un nuovo vettore di etichette z dove zi = yi se yi = k e zi = 0 altrimenti Applicare L a X, z per ottenere fk

Prendere decisioni significa applicare tutti i classificatori a un campione non visto x e predire l'etichetta k per la quale il classificatore corrispondente riporta il punteggio di confidenza più alto:

Sebbene questa strategia sia popolare, è un'euristica che soffre di diversi problemi. In primo luogo, la scala dei valori di confidenza può differire tra i classificatori binari. In secondo luogo, anche se la distribuzione delle classi è bilanciata nel set di addestramento, i modelli di classificazione binaria vedono distribuzioni sbilanciate perché in genere l'insieme dei valori negativi che vedono è molto più ampio dell'insieme dei valori positivi.

Uno-contro-uno Nella riduzione uno contro uno (OvO), si addestrano K (K−1) / 2 classificatori binari per un problema multiclasse K-ario; ognuno riceve i campioni di una coppia di classi dal training set originale e deve imparare a distinguere queste due classi. Al momento della previsione, viene applicato uno schema di voto: tutti K(K−1)/2 classificatori vengono applicati a un campione non visto e la classe che ha ottenuto il numero più alto di predizioni "+1" viene predetta dal classificatore combinato.

Come OvR, OvO è affetto da problemi di ambiguità in quanto alcune regioni del suo spazio di input possono ricevere lo stesso numero di voti.

Estensione dei modelli binari Questa sezione discute le strategie per estendere i classificatori binari esistenti per risolvere problemi di classificazione multiclasse. Sono stati sviluppati diversi algoritmi basati su reti neurali, alberi di decisione, k-nearest neighbor, naive Bayes, macchine a vettori di supporto e macchine di apprendimento estremo per affrontare problemi di classificazione multiclasse. Questi tipi di tecniche possono anche essere chiamate tecniche di adattamento degli algoritmi.

Reti neurali I percettroni multiclasse forniscono un'estensione naturale al problema multiclasse. Invece di avere un solo neurone nello strato di output, con output binario, si potrebbero avere N neuroni binari che portano alla classificazione multiclasse. In pratica, l'ultimo strato di una rete neurale è solitamente uno strato di funzioni softmax, che è la semplificazione algebrica di N classificatori logistici, normalizzati per classe dalla somma degli altri N-1 classificatori logistici. La classificazione basata sulle reti neurali ha portato miglioramenti significativi e prospettive di pensare sotto diversi punti di vista.

Macchine di apprendimento estreme Le macchine di apprendimento estremo (ELM) sono un caso speciale di reti neurali feed-forward a singolo strato nascosto (SLFN), in cui i pesi di input e i termini noti dei nodi nascosti possono essere scelti casualmente. Sono state apportate numerose varianti e sviluppi alle ELM per la classificazione multiclasse.

k-vicini più prossimi L'algoritmo kNN basato sui k-vicini più prossimi è considerato tra i più vecchi algoritmi di classificazione non parametrica. Per classificare un esempio sconosciuto, viene misurata la distanza tra quell'esempio e ogni altro esempio di addestramento. Vengono identificate le k distanze più piccole e la classe più rappresentata da questi k vicini più prossimi viene considerata l'etichetta della classe di output.

Bayes ingenuo Il Naive Bayes è un classificatore di successo basato sul principio del massimo a posteriori (MAP). Questo approccio è naturalmente estensibile al caso di più di due classi e ha dimostrato di funzionare bene nonostante l'ipotesi semplificativa sottostante di indipendenza condizionata delle bariabili di input data la classe.

Alberi decisionali