Definiamo formalmente il problema dello squilibrio di classe e poi ricaviamo intuitivamente le soluzioni!
Ultimamente, ho creato un pacchetto per risolvere lo squilibrio di classi in Julia chiamato Imbalance.jl. Mi ci è voluto molto impegno in termini di lettura di articoli e di osservazione delle implementazioni durante la creazione del pacchetto, quindi ho pensato che potesse essere utile condividere ciò che ho imparato sul problema dello squilibrio di classi in generale, insieme ad alcuni degli algoritmi più popolari usato per affrontarlo. Ciò include il sovracampionamento casuale ingenuo, ROSE, SMOTE, SMOTE-Nominal e SMOTE-Nominal Continuous. Per questo articolo ci concentreremo sui primi due.
Prima di iniziare con gli algoritmi, comprendiamo formalmente lo squilibrio di classe.
Il problema dello squilibrio di classe
La maggior parte, se non tutti, gli algoritmi di apprendimento automatico possono essere visti come una forma di minimizzazione empirica del rischio in cui l’obiettivo è trovare i parametri θ che per alcune funzioni di perdita l minimizzare:
Ad esempio, la regressione lineare richiede l per essere una perdita al quadrato, la regressione logistica la considera una perdita di entropia incrociata, SVM la considera una perdita di cerniera, il potenziamento adattivo la considera una perdita esponenziale.
Il presupposto di fondo è che se f_esimo minimizza questo rischio empirico sul set di dati che può essere visto come un campione casuale della popolazione, allora dovrebbe essere abbastanza vicino alla funzione target F che cerchiamo il modello che minimizzi la stessa quantità sull’insieme di dati e inoltre sull’intera popolazione.
In un contesto multiclasse con classi K, possiamo scrivere il rischio empirico come
Lo squilibrio di classe si verifica quando alcune classi hanno molti meno esempi rispetto ad altre classi. In questo caso, i termini corrispondenti contribuiscono in minima parte alla somma, il che rende più facile per qualsiasi algoritmo di apprendimento trovare una soluzione approssimativa al rischio empirico che per lo più si minimizza solo sulle somme significative. Ciò produce un’ipotesi f_esimo potrebbe essere molto diverso dal vero obiettivo F rispetto alle classi minoritarie che possono risultare più rilevanti per l’applicazione in questione.
In conclusione, le seguenti sono le condizioni in cui abbiamo un problema di squilibrio di classe:
1 — I punti del training set non sono distribuiti “equamente” tra le classi; ad alcune classi appartengono molti meno punti rispetto ad altre.
2— Il modello non funziona bene sui punti appartenenti a tali classi minoritarie dopo la formazione.
Il grado in cui questo problema è negativo dipende dall’importanza di tali classi minoritarie per l’applicazione. Molto spesso sono molto più importanti della classe maggioritaria (ad esempio, la classificazione delle transazioni fraudolente).
Risolvere il problema dello squilibrio di classe
Dalla descrizione del problema risulta evidente che un rimedio è quello di ponderare le somme più piccole (cioè quelle appartenenti a classi minoritarie) in modo che un algoritmo di apprendimento eviti più facilmente soluzioni approssimative che sfruttano la loro insignificanza. Spesso è facilmente possibile modificare gli algoritmi di apprendimento automatico a tale scopo; soprattutto quando sono esplicitamente una forma di minimizzazione empirica del rischio e non sono semplicemente equivalenti ad essa per qualche funzione di perdita.
Un altro approccio che tenta di risolvere il problema è il ricampionamento dei dati. Nella sua forma più semplice può essere considerato equivalente all’approccio basato sui costi dell’assegnazione dei pesi. Considera il seguente algoritmo
Dato: Un set di dati sbilanciato con classi K e un numero intero per ciascuna classe
Ricercato: Un set di dati in cui i dati di ciascuna classe vengono replicati in base al numero intero
Operazione: Ripeti ogni punto della classe k, c volte, dove c è il numero intero associato
Dovrebbe essere ovvio, aggiungendo la somma, che ciò equivale all’approccio sensibile ai costi; ricordiamo che minimizzare una funzione equivale a minimizzare un suo multiplo scalare positivo.
Sovracampionamento casuale
Il suddetto algoritmo soffre di un piccolo problema; se la classe A ha 900 esempi e la classe B ha 600 esempi, non esiste un multiplo intero che possiamo utilizzare per sovracampionare la classe B per portare il set di dati all’esatto equilibrio. Possiamo estendere l’algoritmo per gestire rapporti di replica che non sono interi scegliendo i punti da replicare in modo casuale. Ad esempio, se vogliamo sovracampionare 300 esempi per la classe B in modo che il sistema sia portato in equilibrio (equivalente a un rapporto di 1,5), allora possiamo farlo…
1 — Scegliendo casualmente 300 punti dalla classe B
2— Replicare questi punti
Questo algoritmo è chiamato sovracampionamento casuale ingenuo e ciò che formalmente fa è:
1 — Calcola il numero necessario di punti da generare per ciascuna classe (calcolato da alcuni rapporti dati)
2— Supponiamo per la lezione X quel numero è Nxpoi scegli Nx punti in modo casuale con sostituzione dai punti appartenenti a quella classe, quindi aggiungerli per formare il nuovo set di dati
Dovrebbe essere ovvio che questo è in media equivalente all’algoritmo sopra menzionato e quindi anche alla ponderazione della classe. Se il rapporto per la classe X è 2,0 allora in media ogni punto verrà scelto una volta in modo casuale.
Ecco un set di dati sbilanciato casuale che ho generato per tre classi (0, 1, 2) che mostra un istogramma delle classi e un grafico a dispersione dei punti prima e dopo il sovracampionamento.
Si noti che non c’è alcuna differenza visiva nelle due figure in basso perché tutti i punti generati sono repliche di quelli esistenti.
Infine, si noti che se invece di scegliere casualmente esempi da replicare nelle classi minoritarie, scegliessimo casualmente i punti da rimuovere nelle classi maggioritarie, l’algoritmo diventa un ingenuo sottocampionamento casuale. Ciò ha ovviamente lo svantaggio di perdere dati utili, ma a volte l’eliminazione dei dati provenienti dalle classi maggioritarie “non così utili” risolve il problema dello squilibrio e porta a prestazioni molto migliori nei confronti delle classi minoritarie “molto più utili”. In questo e nei prossimi articoli concentreremo la nostra attenzione sui metodi di sovracampionamento.
Esempi di sovracampionamento casuale
È logico che otterremmo risultati migliori rispetto al sovracampionamento casuale ingenuo se aggiungessimo in modo naturale i punti per ciascuna classe raccogliendo più dati nel nostro set di dati. Ad esempio, supponiamo che…
- Vogliamo rilevare se una transazione è fraudolenta
- Abbiamo raccolto un set di dati di 1.000 transazioni fraudolente e 999.000 transazioni valide
Dovrebbe essere ovvio che risolvere il problema dello squilibrio raccogliendo altre 998.000 transazioni fraudolente è di gran lunga più efficace che ripetere quelle esistenti da 1.000 transazioni per 997.000 volte. In particolare, corriamo un alto rischio di adattamento eccessivo ai dati particolari osservati in quest’ultimo caso.
La realtà è ovviamente che in genere non è possibile raccogliere più dati per le classi minoritarie; tuttavia, questo fa luce sul fatto che possiamo fare qualcosa di meglio dell’ingenuo sovracampionamento ripetendo esempi. Sappiamo che tutti i dati aggiuntivi che raccogliamo seguono la distribuzione di probabilità della popolazione sottostante di dati appartenenti alla classe minoritaria, quindi che ne dici di approssimare questa distribuzione di probabilità e poi campionarla per simulare la raccolta di esempi reali. Questo è ciò che fa l’algoritmo degli esempi di sovracampionamento casuale (ROSE).
Ne consegue quindi che ROSE tenta di stimare la distribuzione di probabilità P(x|y=k) per ogni classe X e poi disegna il necessario Nx campioni da esso. È noto che un modo per stimare tale densità è attraverso la stima della densità del kernel che puoi derivare o intuire partendo da versioni più grezze come l’analisi dell’istogramma. Quanto segue descrive KDE:
Dato: punti dati X
Ricercato: Una stima di P(x)
Operazione: Scegli una funzione del kernel K(x) e poi stimare P(x) COME
Tipicamente, vogliamo essere in grado di controllare la scala della funzione del kernel (cioè, comprimerla o allargarla) in quanto ciò può migliorare la stima di P(x) quindi in un senso più generale abbiamo
In sostanza, ciò che fa è posizionare la funzione del kernel sopra ogni punto e quindi sommarli e normalizzarli tutti in modo che si integri a 1.
La scelta della funzione del kernel stessa è un iperparametro; forse, uno che ha dimostrato di non essere così significativo fintanto che soddisfa proprietà di base come levigatezza e simmetria. Una semplice gaussiana con σ come scala è una scelta comune e che ROSE usa per il suo KDE.
ROSE campiona il Nx punti da questa distribuzione eseguendo quanto segue:
- Scegli un punto in modo casuale
- Posiziona la gaussiana su di esso
- Campiona un punto dalla gaussiana
Questo è proprio come il sovracampionamento casuale, tranne per il fatto che dopo aver scelto un punto in modo casuale, posiziona una gaussiana su di esso e campiona la gaussiana per generare il nuovo punto invece di ripetere il punto scelto.
In questo, ROSE imposta la larghezza di banda h (o più in generale la matrice di livellamento in dimensioni superiori che è il parametro della matrice di covarianza nella distribuzione normale) utilizzando una regola empirica chiamata Silverman in modo che il l’errore quadratico medio integrato è ridotto al minimo. In particolare,
dove D_σ è una matrice diagonale delle deviazioni standard di ciascuna delle caratteristiche, d è il numero di caratteristiche e N è il numero di punti.
Nel pacchetto Imbalance.jl, questo viene moltiplicato per un’altra costante S per consentire il controllo facoltativo dell’iperparametro. Per s=1 viene lasciato come nel documento e per s=0, ROSE diventa equivalente al sovracampionamento casuale. La seguente animazione prodotta utilizzando il pacchetto illustra l’effetto dell’aumento di s sui punti generati.
Si noti che i punti originali non si muovono e che aumentando s, i punti sintetici generati a causa di ciascun punto originale scelto casualmente sono ancora più distanti da esso.
Spero che questa storia ti abbia illuminato sul problema dello squilibrio di classe nell’apprendimento automatico e su come può essere risolto. Consideriamo gli algoritmi presentati nel documento SMOTE per il prossima storia.
Riferimento:
(1) G Menardi, N. Torelli, “Addestramento e valutazione delle regole di classificazione con dati sbilanciati”, Data Mining and Knowledge Discovery, 28(1), pp.92–122, 2014.
