Pubblichiamo in questa pagina un contributo di Maurizio Rosina sull’individuazione degli outliers nei dati.
Maurizio Rosina è laureato in Ingegneria Elettronica presso l’Università La Sapienza Roma. Attualmente lavora nell’ambito delle attività di stategia ed innovazione digitale presso un’importante azienda di Information Technology a carattere pubblico.
Data-Driven + Outliers = Wrong Decisions
un nuovo processo per l’individuazione di outliers
Maurizio Rosina email: maurizio-rosina@libero.it
Introduzione
“L’operazione è perfettamente riuscita, ma il paziente è morto.” Quante volte abbiamo sentito questo detto. Purtroppo la sua (nefasta) profetica validità è più che mai di attualità. Prendiamo il caso delle decisioni prese ‘automaticamente’ a fronte di una ‘automatica’ elaborazione di grandi moli di dati (big data & data-driven decisions). La ‘automatica’ decisione sarà sempre corretta? La domanda sembrerebbe retorica, in quanto si può considerare quasi un assioma che è che i ‘corretti’ algoritmi facciano ‘correttamente’ il loro lavoro e quindi la automatica decisione sarà ‘corretta’. Ma l’uomo ha previsto di porre in opera tutti i necessari algoritmi che consentano di giungere ad una ‘corretta’ automatica decisione?
Poniamo il caso che nel set di dati da elaborare siano presenti un po’ di outliers, ovvero dei dati anomali, in grado di distorcere, ad esempio, i parametri statistici fondamentali quali la media, la varianza, lo scarto quadratico medio ecc. E supponiamo ancora che proprio i valori dei parametri statistici fondamentali fungano da interruttori in grado di innescare (trigger) una decisione ‘automatica’. Ebbene, qualora nei dati da elaborare vi fossero degli outliers l’operazione (l’elaborazione) riuscirebbe perfettamente (i valori dei parametri statistici calcolati sarebbero ‘formalmente’ correttissimi), ma il paziente potrebbe morire (la decisione presa in ‘automatico’ potrebbe essere fattualmente sbagliata).
Nuvole di punti acquisite nei modi più vari e Big Data sono le parole d’ordine e le realtà con cui oggigiorno sempre più occorre misurarsi, e talvolta bastano un po’ di outliers per mandare in ‘crisi’ elaborazioni formalmente correttissime, ma che non prevedano la (anche sporadica) presenza di outliers, con il risultato di giungere a risultati finali definiamoli perlomeno ‘fuorvianti’. La tematica dell’individuazione degli outliers assume quindi la massima importanza per poter giungere a risultati quanto più possibile accurati e significativi. Inoltre talvolta gli outliers assumono persino il ruolo del ‘risultato’ cercato, e ciò proprio in ragione della loro ‘anomalia’ che li differenzia dal resto dei dati, e magari era proprio tale valore ‘anomalo’ quello cercato ed in grado di attivare il trigger della decisione ‘automatica’. La ricerca degli eventuali valori anomali dovrebbe quindi divenire una fase di ‘default’, propedeutica a qualsiasi altra elaborazione, e dovrebbe essere condotta con tecniche che quanto più possibile non presuppongano una conoscenza a priori della tipologia di distribuzione che i dati in esame hanno o dovrebbero avere.
Il nuovo processo per l’individuazione di outliers
Il nuovo processo per l’individuazione di outliers nello spazio R2 fruisce di tecniche geometrico/statistiche largamente indipendenti dalla tipologia di distribuzione dei dati. Tale nuovo approccio si fonda su quattro consolidati pilastri metodologici: le tecniche di clustering, il metodo del convex hull peeling, una specifica metrica (ideata da italiani), e la diseguaglianza di Chebyshev, che è valida per una qualsiasi tipologia di distribuzione univariata di valori.
Per clustering si intende un insieme di tecniche di analisi multivariata dei dati volte alla selezione e raggruppamento degli elementi in classi omogenee rispetto a qualche specifica caratteristica. Le tecniche di clustering sono tante e molto note, ad es. il classico algoritmo K-means o l’altrettanto noto DBSCAN, e spesso si specializzano quando devono affrontare l’elaborazione di grandi moli di dati [3]. Il convex hull peeling è una tecnica che può essere descritta come lo ‘sbucciare una cipolla’. Dato un insieme di elementi se ne calcola il suo inviluppo complesso (lo stato iniziale e più esterno della cipolla), lo si elimina (si toglie tale strato dello cipolla) e si calcola l’inviluppo convesso dei restanti dati (ovvero il nuovo strato esterno della cipolla), lo si elimina … e così via, sino a giungere all’ultimo strato eliminabile. Spero che l’immaginifico esempio non abbia fatto inorridire qualche matematico/ingegnere/statistico/fisico … o qualche cipolla. Per metrica (o distanza) si intende una funzione su di un insieme X che soddisfa delle specifiche proprietà matematiche. Ed infine la diseguaglianza di Chebyshev, ci dice che in una distribuzione X di valori con il valore medio pari a μ, fissata una costante k maggiore di zero (k>0), la percentuale di elementi compresa nell’intervallo μ-kσ, μ+kσ è almeno 1-1/k2. Tutto questo corredo logico/matematico sarà utilizzato per individuare un nuovo processo di individuazione di outlier in dati bivariati.
Il nuovo processo opera con una logica di divide et impera, ovvero per prima cosa si individuano i vari cluster in cui i dati iniziali possono essere suddivisi, quindi su ogni cluster si opera l’individuazione degli outliers. Vediamo la logica del nuovo processo nei suoi passi logici fondamentali.
Data una nuvola di punti nello spazio R2:
-
Individuazione dei vari cluster di punti.
Poi, per ciascun cluster.
-
Individuazione, tramite la tecnica del convex hull peeling [2], del particolare convex hull (CH50) che al suo interno contiene non più del 50% dei punti del cluster, e calcolo su tali punti interni (che sono il ‘core’ del cluster) del baricentro (ora robusto) tramite una operazione di media.
-
Utilizzo di una tecnica di mapping (che realizza una specifica metrica) che porta tutti i punti che giacciono sul CH50 a trovarsi ad un fattore di distanza pari ad uno dal baricentro; che è come dire che il CH50 viene ad assume la forma di un cerchio con centro nel baricentro e raggio pari ad uno [4][6]. Tale tecnica, illustrata più in dettaglio nel seguito, è applicata a tutti i punti del cluster. Con questa tecnica tutti i punti strettamente contenuti in CH50 avranno un fattore di distanza dal baricentro minore di uno e tutti i punti esterni al CH50 avranno un fattore di distanza dal baricentro maggiore di uno. A seguito di questa tecnica si potrà nel seguito operare su tali valori di distanza, che tengono conto della ‘forma’ del CH50 (‘forma’ che si considera rappresentativa dell’intero cluster di dati). Applicato tale mapping, si potranno nel seguito condurre elaborazioni sulle sequenze di valori di distanze che tengono in conto la forma del cluster, ovvero elaborazioni sui dati nello spazio R1 (dati univariati) e non più su coordinate nello spazio R2.
-
Utilizzo, sulle distanze calcolate nel passo precedente, della diseguaglianza di Chebyshev, che è valida per una qualsiasi tipologia di distribuzione univariata di valori. La distribuzione di Chebyshev garantisce che per una distribuzione qualsiasi di valori, una volta calcolata la sua media (μ), il suo scarto quadratico medio (σ) e fissata una costante k >0, al massimo il [(1/k2)*100]% dei valori potranno risultare esterni all’intervallo [μ-kσ .. μ+kσ]. Ciò permette, su base statistica, di definire in modo ‘fine’ come outlier un qualsiasi punto la cui distanza dal baricentro ricada all’esterno dell’intervallo μ-kσ, μ+kσ. Molto spesso nell’utilizzo della diseguaglianza di Chebyshev piuttosto che fissare la costante k si preferisce fissare un valore di probabilità (p), in quanto per una distribuzione unimodale di valori tra k e p sussiste la relazione p = 1/k2, quindi fissato p è immediato risalire al relativo $$k=\sqrt{1/p}$$. Quindi, in definitiva, più si pone per k un valore grande più si cercano outliers con valori molto distanti dal valore medio; ciò che in termini di probabilità p, data la relazione che sussiste tra p e k, si traduce nel fatto che più si pone per p un valore piccolo più si cercano outliers con valori molto distanti dal valore medio. La ricerca degli outliers viene quindi condotta, per ciascun cluster, individuando come outliers i punti le cui distanze dal valore medio siano esterne all’intervallo sopra illustrato [1].
Tramite i quattro passi metodologici sopra solo sommariamente descritti si giunge, senza alcuna ipotesi preventiva sulla tipologia di distribuzione dei dati, a poter individuare la presenza di eventuali outliers rispetto ai vari cluster individuati.
Inoltre, è di tutta evidenza che l’approccio proposto è teoricamente facilmente espandibile a dati nello spazio R3, con i vari convex hull che potrebbero assumere la struttura di politopi di minima chiusura convessa di punti nello spazio R3.
Il dettaglio delle operazioni
Una delle caratteristiche del processo individuato è di essere altamente modulare, in quanto può ridursi se i dati iniziali sono già univariati, ed è piuttosto flessibile nella algoritmica utilizzabile. Ad esempio il passo 1 non impone alcuno specifico metodo nella individuazione dei cluster (si può utilizzare il metodo e l’algoritmica che si ritiene più opportuna), tanto che, se ritenuto opportuno, tale passo può persino essere saltato, vedendo la nuvola dei punti in esame come un unico cluster, su cui operare con i passi successivi. Inoltre, nel caso di analisi condotte su dati originali univariati, già il solo passo 4, saltando tutti i precedenti, risulterebbe teoricamente sufficiente all’individuazione di eventuali outliers.
Il baricentro calcolato nel passo 2, risulta essere particolarmente robusto, in quanto calcolato sui punti strettamente contenuti nel CH50.
La tecnica utilizzata nel passo 3, permettere di giungere ad una metrica particolarmente interessante [4] ed in grado di tenere conto della ‘forma’ assunta dal cluster. Nello stimare se un punto appartiene o no ad un determinato cluster è infatti pratica generale assumere che più un punto è vicino al baricentro (robusto) del cluster, più è verosimile che il punto appartenga al cluster. Bisogna però anche tenere in considerazione se l’insieme dei punti del cluster è distribuito simmetricamente o asimmetricamente rispetto al baricentro, per poter decidere se la valutazione di una distanza dal baricentro è significativa per l’individuazione di un outlier. Occorre, quindi, tenere conto della ‘forma’ del cluster nel calcolo del ‘fattore di distanza’ del generico punto dal baricentro (robusto). Tramite la trasformazione utilizzata, i punti che individuano l’inviluppo convesso del cluster avranno tutti la stessa distanza dal baricentro del cluster (che è come dire che l’inviluppo convesso del cluster si trasformerà in un cerchio con centro nel baricentro robusto). La trasformazione adottata per il calcolo di un fattore di distanza che tenga in conto tale ‘forma’ è particolarmente semplice. Detto O il baricentro (robusto) del cluster, per il generico punto P si calcola il punto di intersezione P’ con il CH50 generato dalla semiretta con origine O e passante per P, quindi si calcola il rapporto dp=OP/OP’, che assume il significato di fattore di distanza del punto P dal baricentro O. Risulta di tutta evidenza che qualsiasi punto P che giaccia sul CH50 avrà un fattore di distanza dp = 1, ovvero un fattore di distanza unitaria dal baricentro; viceversa qualsiasi punto P strettamente contenuto entro il CH50 avrà un fattore di distanza dp < 1, e qualsiasi punto esterno al CH50 avrà un fattore di distanza dp >1 (vedi figura 1).
Figura 1 – calcolo del fattore di distanza dei punti dal baricentro robusto sulla base del CH50
Tramite tale calcolo ogni punto del cluster viene rimappato, secondo il nuovo fattore di distanza calcolato, lungo la semiretta che lo congiunge al baricentro robusto (vedi figura 2). Questa trasformazione definisce una (nuova) metrica sull’insieme dei punti, ed il fattore di distanza dal baricentro permette di poter tenere conto della ‘forma’ del cluster, che si assume sia definita dalla forma del CH50. Forse a qualcuno tutto ciò può ricordare quanto è ottenibile, ma in modo assai più complesso, tramite la distanza di Mahalanobis, la quale però opera correzioni basandosi esclusivamente su forme strettamente ellissoidali.
Figura 2 – il mapping dei punti sulla base dei nuovi fattori di distanza calcolati – si noti in particolare come i punti del CH50 giacciano su di un cerchio (di raggio 1) con centro nel baricentro
Il passo 4 opera sulle distanze (dati univariati) calcolate dalla nuova metrica ottenuta nel passo 3 precedente. In questo quarto e finale passo, si è voluto seguire la tecnica di utilizzare, su ciascun cluster, in sequenza due volte la disuguaglianza di Chebyshev con parametri diversi. Il primo utilizzo di Chebyhev serve ad individuare il sottoinsieme dei dati (delle distanze dal baricentro) che costituiscono il ‘core’ del cluster, e consentiranno di condurre il successivo calcolo tramite Chebyshev (quello che individuerà le distanze ‘anomale’, descrittive di punti outlier) su parametri statistici significativi e ‘robusti’. Vediamo con un minimo di dettaglio le due applicazioni in sequenza della diseguaglianza di Chebyshev.
Per ciascun cluster inizialmente vengono calcolate media μ e scarto quadratico medio σ di tutti i suoi valori (valori che sono le distanze dei punti del cluster dal baricentro, ottenute nel passo 3 precedente) e viene applicata la diseguaglianza di Chebyshev con un fattore k piuttosto basso (che è come dire, data la relazione $$k=\sqrt{1/p}$$ che sussiste tra k e la probabilità p, imponendo un valore di p piuttosto alto), che si traduce nel selezionare, come valori ‘core/fondamentali’ del cluster solo quelli molto prossimi alla media (ovvero quelli con valori a distanza di pochi kσ rispetto alla media μ). Su tali valori ‘core/fondamentali’ si calcolano nuovamente media μ1 e scarto quadratico medio σ1 (che ora si ritengono parametri molto rappresentativi e ‘robusti’) e si effettua la effettiva ricerca degli outliers, ancora tramite la diseguaglianza di Chebyshev, in cui si utilizzano i nuovi e robusti valori μ1 e σ1, ma si applica un fattore k più alto del precedente (o, il che è dire lo stesso, un valore p più piccolo del precedente), ciò che si traduce nell’individuare come outliers solo i punti che presentano valori di distanze molto distanti dal valore medio μ1, valori che dimostrano che tali punti, che presentano tali ‘anomale’ distanze, ‘sicuramente’ non appartengono al cluster. Modulando opportunamente i valori con cui attivare in sequenza le due diseguaglianze di Chebyshev si giunge ad una individuazione quanto si vuole ‘fine’ degli outliers, ottenuta in base a parametri statistici dichiarabili ed ad una metodologia praticamente indipendente dalla tipologia di distribuzione dei dati.
Un esempio su POI localizzati sul territorio
Nel seguito vengono presentati due esempi, entrambi attivi su di un campione di dati relativo a 3280 coordinate relative a localizzazioni di POI (Points Of Interest – punti di interesse) posizionati sulle province di Viterbo e Frosinone. Nella figura 3 viene presentato il campione dei dati da elaborare. La figura 4 propone i 2 cluster individuati tramite il classico algoritmo DBSCAN. Le figure 5 e 6 presentano, per ciascuno dei due cluster, il CH50 ed il baricentro ricavato dai punti strettamente contenuti nel CH50, quindi la successiva fase di mapping, attivata sia sui punti del cluster. Tale mapping, come detto, ha l’effetto di portare:
a) tutti i punti che giacciono sul CH50 ad un fattore di distanza pari ad uno dal baricentro;
b) tutti i punti strettamente contenuti entro il CH50 ad un fattore di distanza dal baricentro minore di uno;
c) tutti i punti esterni al CH50 ad un fattore di distanza maggiore di uno.
Infine nelle figure e 7 e 8 vengono riportati due esempi di conduzione della individuazione degli outliers. I due esempi avranno in comune la fase di individuazione dei cluster, e si differenzieranno per i valori che verranno posti nelle diseguaglianze di Chebishev. Per tale ragione la conduzione dei calcoli che dà origine alle figure 7 ed 8 sarà oggetto, nel seguito, di un accurato approfondimento.
Figura 3 – il campione dei dati – 3280 coordinate relative a localizzazioni di POI presenti nelle province di Viterbo e Frosinone.
Figura 4 – i due cluster individuati, rappresentati in colori diversi (algoritmo Dbscan)
Figura 5 – primo cluster (quello in alto nella figura 4) – a sinistra l’immagine del cluster con evidenziato il suo CH50 ed il baricentro ricavato dai punti strettamente contenuti nel CH50. A destra l’immagine del mapping attivato sui punti del cluster, che porta i punti sul CH50 a giacere su di un cerchio con centro nel baricentro. Le distanze dei punti dal baricentro (nella figura di destra) saranno l’oggetto dell’analisi volta all’individuazione di outliers che verrà condotta nella fase successiva tramite l’utilizzo della diseguaglianza di Chebyshev.
Figura 6 – il secondo cluster (quello in basso nella figura 4) – a sinistra l’immagine del cluster con evidenziato il suo CH50 ed il baricentro ricavato dai punti strettamente contenuti nel CH50. A destra l’immagine del mapping attivato sui punti del cluster, che porta i punti sul CH50 a giacere su di un cerchio con centro nel baricentro. Le distanze dei punti dal baricentro (nella figura di destra) saranno l’oggetto dell’analisi volta all’individuazione di outliers che verrà condotta nella fase successiva tramite l’utilizzo della diseguaglianza di Chebyshev.
Gli outlier proposti nelle figure 7 ed 8 che seguono saranno relativi a condizione diverse (differenti valori dei parametri) che vorranno poste nelle diseguaglianze di Chebishev, ciò che permetterà di individuare con minore o maggiore ‘rigore’ la presenza di outliers nei due cluster. Nel primo esempio si porranno delle condizioni che permetteranno di rilevare come outliers valori non estremamente distanti dal valore medio (quindi si individueranno ‘molti’ outliers). Nel secondo esempio si porranno delle condizioni più ‘severe’, ciò che condurrà ad individuare come outlier solo quelli che presentano valori veramente molto diversi dal valore medio. In entrambi gli esempi, condotti sugli stessi dati iniziali, per ogni cluster individuato la disuguaglianza di Chebyshev verrà utilizzata una prima volta per individuare/selezionare i valori ‘core/fondamentali’ del cluster, sui quali calcolare dei nuovi valori di media μ1 e scarto quadratico medio σ1 (che ottenuti in tal modo si ritengono parametri estremamente ‘rappresentativi’ del cluster e ‘robusti’). Quindi la disuguaglianza di Chebyshev verrà utilizzata una seconda volta, con i valori di media μ1 e scarto quadratico medio σ1 precedentemente calcolati, al fine di individuare gli outliers.
Nel primo esempio, illustrato nella figura 7, per ricavare i valori ‘core/fondamentali’ nella diseguaglianza di Chebyshev si è fissato quale valore di probabilità p = 0.3 (che corrisponde a fissare un valore di k =1.8), valore che assicura che al massimo il 70% dei dati di ogni cluster potrà risultare esterno ai rispettivi intervalli [μ1-1.8σ1..μ1+1.8σ1] e [μ2-1.8σ2..μ2+1.8σ2], in cui μ e σ rappresentano la media e lo scarto quadratico medio ed i pedici indicano i valori ottenuti per i due cluster. Le condizioni poste individuano dei ‘core’ piuttosto ristretti per i due cluster (ciascuno composto da almeno il 30% dei dati del rispettivo cluster) e su di essi si sono calcolate le nuove medie μ11, μ22 ed i nuovi scarti quadratici medi σ11 e σ22 per ciascuno dei due cluster (valori che ora si ritengono estremamente rappresentativi dei cluster e molto ‘robusti’). Quindi si è fissato quale nuovo valore di probabilità p = 0.02, valore in realtà non particolarmente ‘severo’ (che corrisponde al fissare un k=7.1), in quanto assicura che un massimo del 2% dei dati di ogni cluster possa giacere esternamente ai rispettivi intervalli [μ11-7.1σ11..μ11+7.1σ11] e [μ22-7.1σ22..μ22+7.1σ22]. La ricerca degli outliers è quindi stata effettuata individuando i punti le cui distanze sono esterne a tale intervallo. Tale processo, come detto, è condotto su ciascuno dei cluster individuati, e si sono individuati un totale di ben 104 outliers, presenti su entrambi i cluster (vedi fig. 7).
Figura 7 – gli agglomerati dei punti in rosso corrispondono a 104 outliers, appartenenti ad entrambi i cluster
Per ottenere quanto illustrato nella figura 8 si è si è fissato nel primo utilizzo della diseguaglianza di Chebyshev un valore di probabilità analogo a quello dell’esempio precedente, ovvero p = 0.3, mentre nel secondo utilizzo della diseguaglianza si è fissato un valore p=0.005 (corrispondente a fissare k=14.1), ovvero un valore ben più ‘severo’ del precedente, e che assicura che un massimo dello 0.5% dei dati di ogni cluster possa giacere esternamente ai rispettivi intervalli [μ11-14.1σ11..μ11+14.1σ11] e [μ22-14.1σ22..μ22+14.1σ22]. Utilizzando tali valori di probabilità si sono individuati solo 2 outliers, entrambi appartenenti ad uno solo dei due cluster (vedi fig 8).
Figura 8 – I due punti in rosso in basso corrispondono ai due outliers individuati
Conclusioni
Big Data, Data-Driven e Decisioni (più o meno assistite da elaborazioni) ‘automatiche’, sono oramai divenute imprescindibili parole d’ordine, che sempre più spesso risuonano nei convegni e negli eventi. Spesso però tali termini divengono meri slogan, asserviti più ad attività di marketing che volti ad individuare e proporre dei reali e corretti metodi e processi automatici dei quali persone, aziende e/o collettività possano, con fiducia, far uso. Infatti molti (e molte società) si occupano di ottenere risultati elaborando dati, ma molti meno si preoccupano di dichiarare se si è verificato che nei dati da elaborare erano presenti valori anomali ed aberranti (outliers). È ben noto che valori anomali (outliers) presenti anche in minime quantità possono rendere assai poco consistenti i risultati delle elaborazioni, ed ancor meno consistenti le eventuali decisioni che su tali risultati si basino. La ricerca e l’individuazione di outliers è quindi un passo fondamentale, generalmente propedeutico alle elaborazioni volte ad ottenere risultati consistenti.
Il nuovo approccio per l’individuazione di outliers nello spazio R2 qui presentato fruisce di tecniche geometrico/statistiche largamente indipendenti dalla tipologia di distribuzione dei dati, e poggia su quattro pilastri metodologici: il clustering, la tecnica del convex hull peeling, una specifica metrica e la diseguaglianza di Chebyshev. In particolare la metrica applicata ha il pregio di permettere di tenere in conto la ‘forma’ del cluster, e l’utilizzo della diseguaglianza di Chebyshev ha la specificità di essere valida per una qualsiasi tipologia di distribuzione univariata di valori. La modularità e la generalità dell’approccio presentato, accoppiati alla ricerca ed alla individuazione di outliers in base a parametri strettamente statistici, quindi fanno del processo presentato un utile strumento metodologico per chi debba elaborare dati bivariati per gli scopi più vari, con la sicurezza di poter verificare la presenza di outliers sulla base di specifici intervalli di confidenza.
Riferimenti
-
B. G. Amidan, T. A. Ferryman, S. K.Cooley – Data Outlier Detection using the Chebyshev Theorem – IEEE Aerospace Conference Proceedings – 2005;
-
G. C. Porzio, G. Ragozini – Peeling multivariate data sets: a new approach – Quaderni di Statistica – Vol. 2, 2000;
-
M. Ester, H-P. Kriegel, J. Sander, X. Xu – A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise – Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining – 1996;
-
M. Riani, S. Zani – Generalized Distance Measures for Asymmetric Multivariate Distributions – Advances in Data Science and Classification – Springer – 1998
-
R. Savage – Probability Inequalities of the Tchebycheff Type – Journal of Research of the National Bureau of Standards – B. Mathematics and Mathematical Physics – Vol. 65B, No.3 – 1961;
-
S. Zani, M. Riani, A. Corbellini – Robust bivariate boxplots and multiple outlier detection – Computational Statistics & Data Analysis – Elsevier – 1998;
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Ancora nessun commento