Classificazione a singola classe

Nell'apprendimento automatico, la classificazione a singola classe (OCC, one-class classification), nota anche come classificazione unaria o modellazione di classe, è un approccio all'addestramento di classificatori binari in cui vengono utilizzati solo esempi di una delle due classi.

Esempi includono il monitoraggio dei riduttori degli elicotteri, la previsione dei guasti ai motori, o la valutazione dello stato operativo di una centrale nucleare come "normale". In tali scenari, ci sono pochi esempi (se non addirittura nessuno) di stati catastrofici del sistema - rari valori anomali - ricompresi nella seconda classe. In alternativa, la classe su cui ci si concentra può coprire un piccolo sottoinsieme coerente dei dati e la formazione può basarsi su un approccio a collo di bottiglia informativo.

Panoramica

Il termine classificazione a singola classe è stato coniato da Moya & Hush nel 1996 e in letteratura scientifica si trovano sue molte applicazioni, ad esempio il rilevamento di outlier, il rilevamento di anomalie, il rilevamento di novità. Una caratteristica dell'OCC è che utilizza solo campioni dalla classe assegnata, in modo che non sia strettamente richiesto un campionamento rappresentativo per classi diverse da quella obiettivo.

Introduzione

La classificazione a singola classe basata su SVM si basa sull'identificazione della più piccola ipersfera (con raggio r e centro c) composta da tutti i campioni (della classe). Questo metodo si chiama Support Vector Data Description (SVDD). Formalmente, il problema può essere definito nella seguente forma di ottimizzazione vincolata:

${\begin{aligned}\min _{r,c,\zeta }&\ r^{2}+{\frac {1}{\nu n}}\sum _{i=1}^{n}\zeta _{i}\\{\text{ t.c. }}&||\Phi (x_{i})-c||^{2}\leq r^{2}+\zeta _{i}\;\;\forall i=1,2,...,n\end{aligned}}$

Tuttavia, la formulazione data è altamente restrittiva e sensibile alla presenza di outlier. Pertanto, una formulazione flessibile, che tenga conto della presenza di outlier, può essere formulata come mostrato di seguito:

${\begin{aligned}\min _{r,c}&\ r^{2}\\{\text{ t.c. }}&||\Phi (x_{i})-c||^{2}\leq r^{2}+\zeta _{i}\;\;\forall i=1,2,...,n\end{aligned}}$

Dalle condizioni di Karush-Kuhn-Tucker per l'ottimalità, si ottiene

$c=\sum _{i=1}^{n}\alpha _{i}\Phi (x_{i}),$

dove gli $\alpha _{i}$ si trovano come soluzione al seguente problema di ottimizzazione:

$\max _{\alpha }\sum _{i=1}^{n}\alpha _{i}\kappa (x_{i},x_{i})-\sum _{i,j=1}^{n}\alpha _{i}\alpha _{j}\kappa (x_{i},x_{j})$

tale che, $\sum _{i=1}^{n}\alpha _{i}=1{\text{ e }}0\leq \alpha _{i}\leq {\frac {1}{\nu n}}{\text{ per ogni }}i=1,2,...,n.$

L'introduzione della funzione kernel garantisce maggiore flessibilità all'algoritmo One-class SVM (OSVM).

Apprendimento PU (da positivi e non etichettati)

Un problema simile è l'apprendimento PU, in cui un classificatore binario è costruito tramite apprendimento semi-supervisionato da esempi positivi e non etichettati, (positive unlabeled).

Nell'apprendimento PU, si presume che siano disponibili due serie di esempi per l'addestramento: la serie positiva $P$ e un insieme misto $U$, che si presume contenga campioni sia positivi sia negativi, ma senza che questi ultimi siano etichettati come tali. Ciò contrasta con altre forme di apprendimento semi-supervisionato, in cui si presume la disponibilità di un insieme etichettato contenente esempi di entrambe le classi oltre ai campioni non etichettati. Esistono diverse tecniche per adattare i classificatori supervisionati all'impostazione di apprendimento PU, comprese varianti dell'algoritmo EM. L'apprendimento PU è stato applicato con successo a testo, serie temporali, problemi di bioinformatica, e telerilevamento.

Approcci

Sono stati proposti diversi approcci per risolvere problemi di classificazione a singola classe. Gli approcci possono essere distinti in tre categorie principali:

1. stima della densità
2. metodi di delimitazione
3. metodi di ricostruzione.

Metodi di stima della densità

I metodi di stima della densità si basano sulla stima della densità dei campioni e sulla definizione della soglia. Questi metodi si basano sull'assunzione di distribuzioni, come la distribuzione gaussiana o di Poisson. In seguito, è possibile utilizzare test di discordanza per testare nuovi esempi. Questi metodi sono robusti rispetto alla variazione di scala.

Il modello gaussiano è uno dei metodi più semplici per creare classificatori a singola classe. A causa del Teorema del Limite Centrale (TLC), questi metodi funzionano meglio quando è presente un gran numero di campioni i quali sono perturbati da piccoli errori indipendenti. La distribuzione di probabilità per un oggetto d-dimensionale è data da:

$p_{\mathcal {N}}(\mathbf {z$ ;{\boldsymbol {\mu }};{\boldsymbol {\Sigma }})={\frac {1}{(2\pi )^{\frac {d}{2}}|{\boldsymbol {\Sigma }}|^{\frac {1}{2}}}}\exp \left\{-{\frac {1}{2}}(\mathbf {z} -{\boldsymbol {\mu }})^{T}{\boldsymbol {\Sigma }}^{-1}(\mathbf {z} -{\boldsymbol {\mu }})\right\}}

dove, ${\boldsymbol {\mu }}$ è la media e ${\boldsymbol {\Sigma }}$ è la matrice di covarianza. Calcolando l'inversa della matrice di covarianza ( ${\boldsymbol {\Sigma }}^{-1}$) è l'operazione più costosa e nei casi in cui i dati non sono riscalati correttamente o i dati hanno pseudo-inverse ${\boldsymbol {\Sigma }}^{+}$ a direzioni singolari viene utilizzato per approssimare l'inverso e viene calcolato come ${\boldsymbol {\Sigma }}^{T}({\boldsymbol {\Sigma }}{\boldsymbol {\Sigma }}^{T})^{-1}$.

Metodi di delimitazione

I metodi basati sulla delimitazione si concentrano sulla definizione di confini attorno a una serie di punti, chiamati punti obiettivo. Questi metodi cercano di ottimizzare il volume. I metodi basati sulla delimitazione si basano sulle distanze e quindi non sono robusti rispetto alla variazione di scala. Il metodo K-centers, NN-d e SVDD sono alcuni degli esempi principali.

K-centers Nell'algoritmo K-centers, si posizionano $k$ piccole sfere con raggio uguale per minimizzare la distanza massima tra tutte le distanze minime tra le istanze di addestramento e i centri. Formalmente, si deve minimizzare il seguente errore,

$\varepsilon _{k{\text{-center}}}=\max _{i}(\min _{k}\|{\boldsymbol {x}}_{i}-{\boldsymbol {\mu }}_{k}\|^{2})$

L'algoritmo utilizza un metodo di ricerca in avanti con inizializzazione casuale, in cui il raggio è determinato dalla distanza massima dell'istanza che ogni data sfera dovrebbe catturare. Una volta determinati i centri, per qualsiasi istanza di test ${\boldsymbol {z}}$ la distanza può essere calcolata come,

$d_{\textit {k-center}}({\boldsymbol {z}})=\min _{k}\|{\boldsymbol {z}}-{\boldsymbol {\mu }}_{k}\|^{2}$

Metodi di ricostruzione

I metodi di ricostruzione utilizzano conoscenze pregresse e un processo generativo per costruire un modello generativo che si adatti al meglio ai dati. Nuove istanze possono essere descritte in termini di stato del modello generativo. Alcuni esempi di metodi di ricostruzione per OCC sono il clustering con k-means, la quantizzazione vettoriale LVQ, le mappe auto-organizzate, ecc.

Applicazioni

Classificazione dei documenti

Il modello-base di Support Vector Machine (SVM) viene addestrato utilizzando esempi sia positivi sia negativi, tuttavia è stato dimostrato che ci sono molte valide ragioni per utilizzare solo esempi positivi. Quando l'algoritmo SVM viene modificato per utilizzare solo esempi positivi, il processo è considerato una classificazione a singola classe. Una situazione in cui questo tipo di classificazione potrebbe rivelarsi utile per il paradigma delle SVM è quella in cui si cerca di identificare i siti di interesse per un browser web basandosi esclusivamente sulla cronologia di navigazione dell'utente.

Studi biomedici

La classificazione a singola classe può essere particolarmente utile nell’ambito della biomedicina, dove spesso i dati di altre classi possono essere difficili o impossibili da ottenere. Nello studio dei dati biomedici, può essere difficile e/o costoso ottenere l'insieme di dati etichettati dalla seconda classe necessario per eseguire una classificazione a due classi. Uno studio del Scientific World Journal ha rilevato che l'approccio basato sulla tipicità è il più utile nell'analisi dei dati biomedici perché può essere applicato a qualsiasi tipo di dataset (continuo, discreto o nominale). L'approccio basato sulla tipicità si fonda sul clustering dei dati esaminandoli e inserendoli in cluster nuovi o esistenti. Per applicare la tipicità alla classificazione a singola classe per le analisi biomediche, ogni nuova osservazione, $y_{0}$, viene confrontata con la classe target, $C$, e identificata come outlier o appartenente alla classe target.

Rilevamento non supervisionato della deriva concettuale

La classificazione a singola classe presenta somiglianze con il rilevamento non supervisionato del concept drift, in quanto entrambi mirano a identificare se i dati non osservati condividono caratteristiche simili ai dati iniziali. Un concetto è definito come la distribuzione di probabilità fissa da cui vengono estratti i dati. Nel rilevamento non supervisionato del concept drift, l'obiettivo è rilevare se la distribuzione dei dati cambia ma senza utilizzare etichette di classe. Nella classificazione a singola classe, il flusso di dati non è importante. I dati non osservati vengono classificati come tipici o anomali a seconda delle loro caratteristiche, indipendentemente dal fatto che provengano o meno dal concetto iniziale. Tuttavia, il rilevamento non supervisionato del drift monitora il flusso di dati e segnala una situazione di drift in caso di variazioni o anomalie significative. Il rilevamento non supervisionato del concept drift può essere identificato come la forma online della classificazione a singola classe. I classificatori a singola classe vengono utilizzati per rilevare casi di concept drift.

Voci correlate

• Rilevamento delle anomalie
• Apprendimento supervisionato