際際滷

際際滷Share a Scribd company logo

Algoritmi non supervisionati per time series

N
Nicola Procopio

Nell'universo delle time series, oltre al forecasting, esistono tanti problemi che le aziende vogliono risolvere e non per tutti si pu嘆 ricorrere a dataset gi etichettati. In questo meetup verranno introdotti due algoritmi, NON DEEP, usati per risolvere i problemi di profilazione e per fare anomaly detection.

1 of 26
Download to read offline
Algoritmi non supervisionati per time series
Chi sono Nicola Nico Procopio Senior Data Scientist @ Dove ho lavorato Dove potremmo esserci gi incontrati Interessi lavorativi Altro Lettore bulimico Ciclista/Hikers molto amatoriale Indie-Rock fan Innamorato della mia terra
Time Series: Definizione una serie storica si definisce come un insieme di variabili casuali ordinate rispetto al tempo le cui osservazioni sono influenzate dal tempo stesso. Dato un fenomeno Y si indica con Yt losservazione di tale fenomeno al tempo t={1, 2, , T}
Time Series is Dynamic! Cross Sectional Data: una serie di variabili, rappresentative di un fenomeno, osservate in un particolare momento Esempio: abitudini di acquisto durante i saldi, prezzi degli immobili in base alle caratteristiche in un dato periodo Time Series Data: una singola variabile, rappresentativa di un fenomeno, osservata su pi湛 periodi della stessa dimensione Esempio: il PIL negli ultimi 30 anni, la fornitura elettrica bimestrale E le serie storiche MULTIVARIATE?
Problemi pi湛 comuni Forecasting Classification Anomaly Detection
In (MY) Real World Approccio Supervisionato: infinita letteratura e codice on-line da studiare e riciclare poche aziende hanno uno storico di dati etichettati da utilizzare nella fase di training
Possibili soluzioni Etichettare lo storico dati a mano ATTENZIONE: potrebbe nuocere alla salute ATTENZIONE: coinvolgere lesperto di dominio Etichettare lo storico dati con algoritmi non supervisionati
Basics Approccio NON Supervisionato: non c竪 bisogno di dati etichettati lavora sulla similarit, le distanze, la densit ha lobiettivo di creare gruppi pi湛 omogenei possibile al loro interno ed eterogenei tra loro Tecniche pi湛 comuni: Clustering Dimensionality Reduction
Problema: misurare distanza Calcolo della distanza tra osservazioni Ogni Time Series 竪 una singola osservazione
Dynamic Time Warping "Il Dynamic Time Warping, o DTW, 竪 un algoritmo che permette l'allineamento tra due sequenze, e che pu嘆 portare ad una misura di distanza tra le due sequenze allineate. Tale algoritmo 竪 particolarmente utile per trattare sequenze in cui singole componenti hanno caratteristiche che variano nel tempo, e per le quali la semplice espansione o compressione lineare delle due sequenze non porta risultati soddisfacenti." Fonte Wikipedia
DTW: Prerequisiti Per calcolare la distanza tra due sequenze, indipendentemente dalla loro lunghezza, col DTW devono essere presenti i seguenti requisiti: ogni indice della prima sequenza deve poter essere confrontato con tutti gli indici delle altre e viceversa; il primo indice della prima sequenza deve essere associato al primo indice dell'altra sequenza (ma non deve essere la sua unica corrispondenza); l'ultimo indice della prima sequenza deve corrispondere all'ultimo indice dell'altra sequenza (ma non deve essere la sua unica corrispondenza); la mappatura degli indici dalla prima sequenza agli indici delle altre sequenze deve essere monotonicamente crescente. A grandi linee, indipendentemente dalla lunghezza delle serie l'indice iniziale e finale devono coincidere.
DTW: Algoritmo Date due sequenze di lunghezza diversa se volessimo calcolarne la similarit utilizzando il DTW per prima cosa bisogna creare una matrice m x n dove (m,n) sono le lunghezze delle serie + 1
DTW: Cold Start Il cold start 竪 il confronto con i periodi precedenti quando si 竪 al primo passo dell'algoritmo. Impostando una riga fittizia ad infinito non si incorre in situazioni anomale e si evita di implementare condizioni sullo start che appesantirebbero ulteriormente il calcolo.
DTW: Calcolo della distanza Partendo dalla cella [1,1] viene calcolata la distanza euclidea tra ogni punto delle due serie, a questa deve essere aggiunto il minimo tra: il valore precedente sulle righe: cancellazione; il valore precedente sulle colonne: inserimento; il valore precedente in diagonale: corrispondenza. DTW[i,j] := distance[i,j] + min(DTW[i-1, j], DTW[i, j-1], DTW[i-1, j-1])
DTW: Warping Path Partendo da DTW[0,0] costruire un percorso che tocchi il valore minimo muovendo da sinistra verso destra, dallalto verso il basso. spostamento orizzontale: serie_2 竪 accelerata durante questo intervallo. spostamento verticale: serie_2 竪 decelerata durante questo intervallo. spostamento diagonale: durante questo periodo le serie camminano di pari passo.
DTW: Miglioramenti Window Constraint Per rendere pi湛 performante lalgoritmo viene impostata una finestra temporale w su cui calcolare la distanza. Utile per sequenze lunghe che produrrebbero confronti inutili tra periodi molto distanti tra loro. FastDTW E forse la versione pi湛 conosciuta dellalgoritmo. Si basa su alcune approssimazioni che velocizzano il calcolo. Molto studiato e discusso perch竪 non sempre la performance porta a risultati di qualit accettabile.
DTW: Applicazioni Anomaly detection Trovare pattern anomali in ambito health, ad esempio una persona che deambula a velocit diversa, o parla pi湛 lentamente/velocemente potrebbe aiutare nella diagnosi. Customer Segmentation Profilare le abitudini in ambito utilities per proporre nuove offerte o prevenire frodi. Forecasting Evaluation Misurare la distanza tra dato reale e stime.
DTW e K-Means
Dimensionality Reduction In termini estremamente semplicistici: prendo un fenomeno molto complesso, condenso linformazione (con una perdita accettabile) mediante un algoritmo, restituisco lo stesso fenomeno ma con una visione meno dettagliata Time Series? N.B. Non siate estremisti come Drake
SAX Encoding Symbolic Aggregate approXimation Encoding: inventato nel 2002 da Keogh e Lin trasforma le time series in sequenze di simboli robusta ai valori mancanti non supervisionata basata sia sui volumi che sugli andamenti Adolphe Sax inventore del sassofono. Correlazione(SAX, Sax) = 0.00
Preparazione del dataset Il SAX Encoding ha bisogno di serie storiche disposte come segue: per ogni riga una serie storica per ogni colonna uno step temporale i dati devono essere standardizzati dati della protezione civile sul Covid-19
Piecewise Aggregate Approximation Idea riassumere la sequenza in una serie di segmenti che ne riducano la lunghezza ma con la minima perdita di informazione Data una Time Series Y = [Y, Y, ,Yn] pu嘆 essere ridotta in una sequenza X = [X, X, , Xm] con mn utilizzando lequazione: casi particolari: m=n restituisce la serie originale m=1 la nuova sequenza avr un solo valore pari alla media della time series originale
Piecewise Aggregate Approximation Molto importante scegliere la finestra temporale di approssimazione w con un esperto di dominio. Questo influisce sul numero di segmenti, se len(TS)/w non 竪 un intero arrotondare per eccesso cos狸 da non perdere informazioni.
SAX String Per creare una SAX String: scegliere il numero di livelli calcolare i livelli etichettare i periodi generati con la PAA
Anomaly Detection Lanomalia non 竪 una sola osservazione ma unintera serie storica 1. Fissare un limite entro il quale etichettiamo il pattern come anomalo 2. Calcolare la frequenza per ogni SAX String
Grazie a tutti! Domande? Nicola Procopio Breve introduzione al DTW SAX Encoding @nickprock

More Related Content

Algoritmi non supervisionati per time series

  • 2. Chi sono Nicola Nico Procopio Senior Data Scientist @ Dove ho lavorato Dove potremmo esserci gi incontrati Interessi lavorativi Altro Lettore bulimico Ciclista/Hikers molto amatoriale Indie-Rock fan Innamorato della mia terra
  • 3. Time Series: Definizione una serie storica si definisce come un insieme di variabili casuali ordinate rispetto al tempo le cui osservazioni sono influenzate dal tempo stesso. Dato un fenomeno Y si indica con Yt losservazione di tale fenomeno al tempo t={1, 2, , T}
  • 4. Time Series is Dynamic! Cross Sectional Data: una serie di variabili, rappresentative di un fenomeno, osservate in un particolare momento Esempio: abitudini di acquisto durante i saldi, prezzi degli immobili in base alle caratteristiche in un dato periodo Time Series Data: una singola variabile, rappresentativa di un fenomeno, osservata su pi湛 periodi della stessa dimensione Esempio: il PIL negli ultimi 30 anni, la fornitura elettrica bimestrale E le serie storiche MULTIVARIATE?
  • 5. Problemi pi湛 comuni Forecasting Classification Anomaly Detection
  • 6. In (MY) Real World Approccio Supervisionato: infinita letteratura e codice on-line da studiare e riciclare poche aziende hanno uno storico di dati etichettati da utilizzare nella fase di training
  • 7. Possibili soluzioni Etichettare lo storico dati a mano ATTENZIONE: potrebbe nuocere alla salute ATTENZIONE: coinvolgere lesperto di dominio Etichettare lo storico dati con algoritmi non supervisionati
  • 8. Basics Approccio NON Supervisionato: non c竪 bisogno di dati etichettati lavora sulla similarit, le distanze, la densit ha lobiettivo di creare gruppi pi湛 omogenei possibile al loro interno ed eterogenei tra loro Tecniche pi湛 comuni: Clustering Dimensionality Reduction
  • 9. Problema: misurare distanza Calcolo della distanza tra osservazioni Ogni Time Series 竪 una singola osservazione
  • 10. Dynamic Time Warping "Il Dynamic Time Warping, o DTW, 竪 un algoritmo che permette l'allineamento tra due sequenze, e che pu嘆 portare ad una misura di distanza tra le due sequenze allineate. Tale algoritmo 竪 particolarmente utile per trattare sequenze in cui singole componenti hanno caratteristiche che variano nel tempo, e per le quali la semplice espansione o compressione lineare delle due sequenze non porta risultati soddisfacenti." Fonte Wikipedia
  • 11. DTW: Prerequisiti Per calcolare la distanza tra due sequenze, indipendentemente dalla loro lunghezza, col DTW devono essere presenti i seguenti requisiti: ogni indice della prima sequenza deve poter essere confrontato con tutti gli indici delle altre e viceversa; il primo indice della prima sequenza deve essere associato al primo indice dell'altra sequenza (ma non deve essere la sua unica corrispondenza); l'ultimo indice della prima sequenza deve corrispondere all'ultimo indice dell'altra sequenza (ma non deve essere la sua unica corrispondenza); la mappatura degli indici dalla prima sequenza agli indici delle altre sequenze deve essere monotonicamente crescente. A grandi linee, indipendentemente dalla lunghezza delle serie l'indice iniziale e finale devono coincidere.
  • 12. DTW: Algoritmo Date due sequenze di lunghezza diversa se volessimo calcolarne la similarit utilizzando il DTW per prima cosa bisogna creare una matrice m x n dove (m,n) sono le lunghezze delle serie + 1
  • 13. DTW: Cold Start Il cold start 竪 il confronto con i periodi precedenti quando si 竪 al primo passo dell'algoritmo. Impostando una riga fittizia ad infinito non si incorre in situazioni anomale e si evita di implementare condizioni sullo start che appesantirebbero ulteriormente il calcolo.
  • 14. DTW: Calcolo della distanza Partendo dalla cella [1,1] viene calcolata la distanza euclidea tra ogni punto delle due serie, a questa deve essere aggiunto il minimo tra: il valore precedente sulle righe: cancellazione; il valore precedente sulle colonne: inserimento; il valore precedente in diagonale: corrispondenza. DTW[i,j] := distance[i,j] + min(DTW[i-1, j], DTW[i, j-1], DTW[i-1, j-1])
  • 15. DTW: Warping Path Partendo da DTW[0,0] costruire un percorso che tocchi il valore minimo muovendo da sinistra verso destra, dallalto verso il basso. spostamento orizzontale: serie_2 竪 accelerata durante questo intervallo. spostamento verticale: serie_2 竪 decelerata durante questo intervallo. spostamento diagonale: durante questo periodo le serie camminano di pari passo.
  • 16. DTW: Miglioramenti Window Constraint Per rendere pi湛 performante lalgoritmo viene impostata una finestra temporale w su cui calcolare la distanza. Utile per sequenze lunghe che produrrebbero confronti inutili tra periodi molto distanti tra loro. FastDTW E forse la versione pi湛 conosciuta dellalgoritmo. Si basa su alcune approssimazioni che velocizzano il calcolo. Molto studiato e discusso perch竪 non sempre la performance porta a risultati di qualit accettabile.
  • 17. DTW: Applicazioni Anomaly detection Trovare pattern anomali in ambito health, ad esempio una persona che deambula a velocit diversa, o parla pi湛 lentamente/velocemente potrebbe aiutare nella diagnosi. Customer Segmentation Profilare le abitudini in ambito utilities per proporre nuove offerte o prevenire frodi. Forecasting Evaluation Misurare la distanza tra dato reale e stime.
  • 19. Dimensionality Reduction In termini estremamente semplicistici: prendo un fenomeno molto complesso, condenso linformazione (con una perdita accettabile) mediante un algoritmo, restituisco lo stesso fenomeno ma con una visione meno dettagliata Time Series? N.B. Non siate estremisti come Drake
  • 20. SAX Encoding Symbolic Aggregate approXimation Encoding: inventato nel 2002 da Keogh e Lin trasforma le time series in sequenze di simboli robusta ai valori mancanti non supervisionata basata sia sui volumi che sugli andamenti Adolphe Sax inventore del sassofono. Correlazione(SAX, Sax) = 0.00
  • 21. Preparazione del dataset Il SAX Encoding ha bisogno di serie storiche disposte come segue: per ogni riga una serie storica per ogni colonna uno step temporale i dati devono essere standardizzati dati della protezione civile sul Covid-19
  • 22. Piecewise Aggregate Approximation Idea riassumere la sequenza in una serie di segmenti che ne riducano la lunghezza ma con la minima perdita di informazione Data una Time Series Y = [Y, Y, ,Yn] pu嘆 essere ridotta in una sequenza X = [X, X, , Xm] con mn utilizzando lequazione: casi particolari: m=n restituisce la serie originale m=1 la nuova sequenza avr un solo valore pari alla media della time series originale
  • 23. Piecewise Aggregate Approximation Molto importante scegliere la finestra temporale di approssimazione w con un esperto di dominio. Questo influisce sul numero di segmenti, se len(TS)/w non 竪 un intero arrotondare per eccesso cos狸 da non perdere informazioni.
  • 24. SAX String Per creare una SAX String: scegliere il numero di livelli calcolare i livelli etichettare i periodi generati con la PAA
  • 25. Anomaly Detection Lanomalia non 竪 una sola osservazione ma unintera serie storica 1. Fissare un limite entro il quale etichettiamo il pattern come anomalo 2. Calcolare la frequenza per ogni SAX String
  • 26. Grazie a tutti! Domande? Nicola Procopio Breve introduzione al DTW SAX Encoding @nickprock