Outlier in Time Series Databases

Sequence TIme-Delay Embedding (Hofmeyr et al. 1998) Man hat Datenbank normaler Sequenzen (z.B. durch SAX) und vergleicht die Anzahl der Missmatches von Sequenzen (nach Windowing). Wenn Grenzwert überschritten, liegt Anomaly vor.

TIme-Delay Embedding Für jedes Element in einer normalen Sequenz werden die Elemente in Distanz 1,2,…,k in der Sequenz gespeichert.

Negative and Mixed Pattern DB Approaches - Anomaly dictionaries

Outlier Subsequences in a Test Time Series

Untersequenz p ist Outlier wenn Häufigkeit in Test Zeitreihe t sich von der erwarteten Häufigkeit unterscheidet.

http://www.siam.org/meetings/sdm13/gupta.pdf

Clustering-Based Anomaly Detection

Outlier Score: Grad zu dem ein Punkt nicht zu irgendeinem Cluster gehört. Oder Distanz zum Zentroid des Clusters.

Bei K-Means ist es die Differenz des SSE (Standard Squared Errors). Bei großer Differenz nach Entfernung des Punkts aus dem Cluster, liegt ein hoher Outlier Score vor.

Einfachste Berechnung des Outlier Scores: Distanz des Punkts zum Zentroid (allerdings nicht besonders sinnvoll, wenn es mehrere unterschiedliche dichte Cluster gibt). Daher: Relative Distanz. D.h. Distanz des Punktes zum Zentroiden / Median Distanz aller Punkte des Clusters zum Zentroid.

Z.B. DBSCAN

K-NN Algorithmus. Outlier Score ist die Distanz eines Punktes zu dessen k-nächsten Nachbarn.

Lernen eines erzeugenden Models aus den Daten mit mathematischer Struktur und eine Menge von Parametern. Für sequentielle Daten wird typischerweise ein Hidden Markov Model verwendet.

Literaturverweis: Rabiner

HMM Parameter: $\theta = (N,M,A,\pi,B)$

  • N: Anzahl von Zuständen
  • M: Anzahl der Symbole, die durch jeden Zustand generiert werden.
  • A: Übergangsmatrix
  • $\pi$: Initialzustandswahrscheinlichkeiten
  • B: NxM Matrix mit Wahrscheinlichkeit, ein bestimmtes Symbol in einem der N Zustände beobachten zu können.

Wenn die Parameter eines HMM gelernt wurden, können wichtige Statistiken berechnet werden, wie die Wahrscheinlichkeit eine neue Sequenz beobachten zu können oder die wahrscheinlichste Sequenz.

Probleme von HMMs:

Skalieren nicht gut Training erfordert manuelle Intervention, Datenerfahrung und Parameterwahl.