====== 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.


===== Density Based =====
Z.B. DBSCAN

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

===== Model Based =====
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.