2010-02-20 6 views
27

Ho uno scenario in cui ho diverse migliaia di istanze di dati. I dati stessi sono rappresentati come un singolo valore intero. Voglio essere in grado di rilevare quando un'istanza è un valore anomalo estremo.Tecnica di rilevamento anomalie consigliata per uno scenario semplice e monodimensionale?

Ad esempio, con i seguenti dati esempio:

a = 10 
b = 14 
c = 25 
d = 467 
e = 12 

d è chiaramente un'anomalia, e vorrei per eseguire un'azione specifica sulla base di questo.

Sono stato tentato di provare solo a utilizzare la mia conoscenza del dominio particolare per rilevare le anomalie. Ad esempio, calcola una distanza dal valore medio che è utile, e controlla quello, in base all'euristica. Tuttavia, penso che sia probabilmente meglio se indago su tecniche di rilevamento delle anomalie più generali e robuste, che hanno qualche teoria dietro di esse.

Poiché la mia conoscenza pratica della matematica è limitata, spero di trovare una tecnica semplice, come l'uso della deviazione standard. Speriamo che la natura a dimensione singola dei dati renderà questo problema abbastanza comune, ma se sono necessarie più informazioni per lo scenario, si prega di lasciare un commento e darò maggiori informazioni.


Edit: ho pensato di aggiungere altre informazioni sui dati e quello che ho provato nel caso in cui si fa una risposta più corretta di un altro.

I valori sono tutti positivi e diversi da zero. Mi aspetto che i valori formino una distribuzione normale. Questa aspettativa si basa su un'intuizione del dominio piuttosto che attraverso l'analisi, se questa non è una cosa negativa da assumere, per favore fatemelo sapere. In termini di clustering, a meno che non ci siano anche algoritmi standard per scegliere un valore k, troverei difficile fornire questo valore ad un algoritmo k-Means.

L'azione che voglio fare per un anomalia/anomalia è presentarla all'utente e consigliare che il punto dati sia sostanzialmente rimosso dal set di dati (non entrerò nel modo in cui lo farebbero, ma ha senso per il mio dominio), quindi non sarà usato come input per un'altra funzione.

Finora ho provato il test a tre sigma e IQR sul mio set di dati limitato. I valori dei flag IQR non sono abbastanza estremi, three-sigma indica le istanze che meglio si adattano alla mia intuizione del dominio.


Informazioni su algoritmi, tecniche o collegamenti a risorse per conoscere questo scenario specifico sono risposte valide e benvenute.

Che cos'è una tecnica di rilevamento anomalie consigliata per dati unidimensionali semplici?

+0

non sottovalutare il valore della conoscenza scientifica. Le procedure di scatola nera sono raramente la strada da percorrere. Cerca di esprimere le tue conoscenze scientifiche in termini di statistiche semplici. – Tristan

+0

@Tristan: stai dicendo che pensi che dovrei provare a inventare un modello che ha qualche fondamento nelle statistiche, ma alla fine è specifico per il mio dominio problematico? – Grundlefleck

+1

Sto solo dicendo che la tua conoscenza di ciò che è ragionevole (cioè, qual è il modello che genera i dati buoni e i dati cattivi) è un'informazione importante. Dovresti progettare una procedura, come l'utilizzo di IQR, motivata dalla tua conoscenza scientifica del dominio. Non mi piacciono le cose come k-significa perché non è ben motivato ed è intrinsecamente inflessibile, secondo me. – Tristan

risposta

40

Partenza il three-sigma rule:

mu = mean of the data 
std = standard deviation of the data 
IF abs(x-mu) > 3*std THEN x is outlier 

Un metodo alternativo è la IQR outlier test:

Q25 = 25th_percentile 
Q75 = 75th_percentile 
IQR = Q75 - Q25   // inter-quartile range 
IF (x < Q25 - 1.5*IQR) OR (Q75 + 1.5*IQR < x) THEN x is a mild outlier 
IF (x < Q25 - 3.0*IQR) OR (Q75 + 3.0*IQR < x) THEN x is an extreme outlier 

questo esame viene di solito impiegato da Box plots (indicato dalle basette):

boxplot


EDIT:

Per il vostro caso (semplici dati univariati 1D), penso che la mia prima risposta è adatto. Questo tuttavia non è applicabile ai dati multivariati.

@smaclell suggerito utilizzando K-mezzo per trovare i valori anomali. Oltre al fatto che si tratta principalmente di un algoritmo di clustering (non proprio una tecnica di rilevamento anomalo), il problema con k-means è che richiede in anticipo un buon valore per il numero di cluster K.

Una tecnica più adatta è il DBSCAN: un algoritmo di clustering basato sulla densità. Fondamentalmente cresce regioni con densità sufficientemente alta in gruppi che saranno il massimo insieme di punti connessi alla densità.

dbscan_clustering

DBSCAN richiede due parametri: epsilon e minPoints. Inizia con un punto arbitrario che non è stato visitato. Quindi trova tutti i punti vicini entro la distanza epsilon del punto di partenza.

Se il numero di vicini è maggiore o uguale a minPoints, è formato un cluster. Il punto di partenza e i suoi vicini vengono aggiunti a questo cluster e il punto di partenza viene contrassegnato come visitato. L'algoritmo quindi ripete ricorsivamente il processo di valutazione per tutti i vicini.

Se il numero di vicini è inferiore a minPoints, il punto è contrassegnato come rumore.

Se un cluster è completamente espanso (tutti i punti a portata di mano vengono visitati), l'algoritmo procede per iterare attraverso i restanti punti non visitati fino a quando non sono esauriti.

Infine l'insieme di tutti i punti contrassegnati come rumore sono considerati valori anomali.

+2

FREDDO! Grazie per la tua meravigliosa risposta e spiegazioni. – smaclell

+2

+1 il tre-sigma e l'IQR sembrano buone tecniche, grazie per la risposta perspicace. – Grundlefleck

+2

Mi piace questo semplice consiglio. La statistica basata su IQR ha il vantaggio di non essere influenzata da valori estremi che cambieranno la media/sd. – Tristan

2

Ci sono una varietà di tecniche di clustering si potrebbe usare per cercare di identificare le tendenze centrali all'interno dei dati. Uno di questi algoritmi che abbiamo usato pesantemente nel mio corso di riconoscimento di pattern è stato K-Means. Ciò consentirebbe di identificare se esistono più set di dati correlati, ad esempio bimodal distribution. Ciò richiede di avere una certa conoscenza di quanti cluster aspettarsi, ma è abbastanza efficiente e facile da implementare.

Dopo si hanno i mezzi si potrebbe poi cercare di scoprire se un qualsiasi punto è lontano da qualsiasi dei mezzi. Puoi definire 'lontano' come vuoi ma consiglio i suggerimenti di @Amro come un buon punto di partenza.

Per una discussione più approfondita degli algoritmi di clustering fare riferimento alla voce wikipedia sul clustering.

+0

concordato. K-Means è una soluzione semplice, efficace e adattabile per questo problema. Creare due cluster, inizializzarli correttamente e uno dei cluster dovrebbe contenere i dati significativi mentre l'altro ottiene i valori anomali. Ma fa attenzione; se non si hanno valori anomali, entrambi i cluster conterranno dati significativi. –

+0

Beh, è ​​qui che si diverte. Spesso è molto difficile determinare il numero di cluster e sarebbe ancora più difficile farlo in un sistema live. Anche in questo caso di un cluster vero e di un altro cluster anomalo si potrebbe sostenere che i valori anomali stanno iniziando a rappresentare una modalità reale per i dati. Aggiungerò altri collegamenti per fornire altre opzioni. – smaclell

+0

Questo mi sembra uno strumento sbagliato per il lavoro. È interessato principalmente alle code grasse, non alle distribuzioni bimodali. – Tristan

0

Vengono spesso utilizzate sia la regola del tre-sigma che il test IQR e vi sono un paio di semplici algoritmi per rilevare le anomalie.

The three-sigma rule is correct 
mu = mean of the data 
std = standard deviation of the data 
IF abs(x-mu) > 3*std THEN x is outlier 

Il test dovrebbe essere IQR:

Q25 = 25th_percentile 
Q75 = 75th_percentile 
IQR = Q75 - Q25   // inter-quartile range 
If x > Q75 + 1.5 * IQR or x < Q25 - 1.5 * IQR THEN x is a mild outlier 
If x > Q75 + 3.0 * IQR or x < Q25 – 3.0 * IQR THEN x is a extreme outlier 
+0

Ho appena notato questo e hai ragione, il mio test IQR non era corretto. Aggiornerò la mia risposta, grazie. – Amro