- Mit der Zunahme von Streaming- und IoT-Daten ist Anomalieerkennung in Zeitreihen zu einer zentralen Analyseaufgabe geworden, um in Bereichen wie Cybersicherheit, Finanzmärkten, Strafverfolgung und Medizin zwischen normal und abnormal zu unterscheiden
- Da sich traditionelle, statistisch geprägte Anomalieerkennung mit neueren Machine-Learning-Ansätzen vermischt, wird eine Taxonomie benötigt, die zeitliche Reihenfolge und Struktur von Zeitreihen berücksichtigt
- Anomalien treten nicht nur in einzelnen Werten auf, sondern auch in Teilsequenzen; Punktanomalien, Kontextanomalien und kollektive Anomalien lassen sich nur unterscheiden, wenn auch umgebende Muster und zeitlicher Kontext berücksichtigt werden
- Die meisten Methoden folgen einer Pipeline aus Vorverarbeitung → Erkennungsmodell → Scoring → Nachverarbeitung; dabei werden Zeitreihen per Sliding Window in eine Matrix umgewandelt und anschließend Anomalie-Scores berechnet
- Dieses Review ordnet Methoden in distanzbasierte, dichtebasierte und vorhersagebasierte Ansätze ein und soll Vergleichslücken zwischen Forschungsgemeinschaften verringern, die unterschiedliche Datensätze, Baselines und Evaluationsmetriken verwenden
Warum Anomalieerkennung in Zeitreihen schwierig ist
- Eine Zeitreihe ist eine geordnete Folge reeller Werte, die über die Zeit aufgezeichnet wurden; wenn die Ordnung nicht von der Zeit, sondern von Dimensionen wie Winkel, Masse oder Position abhängt, werden auch die Begriffe Datenreihe oder Datensequenz verwendet
- Zeitreihenanalyse wird in vielen Bereichen benötigt, darunter Astronomie, Biologie, Wirtschaftswissenschaften, Energiewissenschaften, Ingenieurwesen, Umweltwissenschaften, Medizin, Neurowissenschaften und Sozialwissenschaften
- Die Komplexität des Datenerzeugungsprozesses, Unvollkommenheiten von Messsystemen und Interaktionen mit böswilligen Akteuren können in den erfassten Daten abnormale Phänomene erzeugen
- Mit der Verbreitung von IoT-Anwendungen wächst die Zahl der erzeugten Zeitreihen, und es ist zu erwarten, dass auch die Zahl der Anomalien zunimmt, die innerhalb von Zeitreihensammlungen gefunden werden müssen
- Anomalien bezeichnen Datenpunkte oder Gruppen von Punkten, die nicht zur Normalität oder zum erwarteten Verhalten auf Basis früherer Beobachtungsdaten passen
- Begriffe wie outlier, novelty, exception, peculiarity, aberration, deviant und discord werden ebenfalls verwendet
- Je nach Anwendung können Anomalien Rauschen sein, das entfernt oder korrigiert werden sollte, oder Ereignisse von Interesse, die wie Ausfälle oder Verhaltensänderungen Gegenstand weiterer Analysen sind
Definitionen und Typen von Anomalien
- Es gibt keine einzelne, universell präzise Definition von Anomalien
- Traditionell ist eine Anomalie eine Beobachtung, die stark von der Mehrheit der Stichproben einer Verteilung abweicht und den Verdacht nahelegt, dass sie durch einen anderen Mechanismus als die übrigen Daten erzeugt wurde
- Wenn Fachleute die Funktionsweise eines Systems genau kennen, können sie Verteilung und Parameter des Normalzustands festlegen und Punkte, die mehr als 3 Standardabweichungen vom Mittelwert entfernt sind, als Anomalien markieren
- In realen Problemen ist es schwierig, die datenerzeugende Verteilung und die verschiedenen Einflussfaktoren genau zu kennen; auch praktische Verteilungen sind komplex, sodass sich Anomalien schwer allein über die Distanz zu einem von Fachleuten definierten Mittelwert identifizieren lassen
- Fortschritte bei der Rechenleistung ermöglichen es, Verteilungen aus Rohdaten zu schätzen und Ansätze zu nutzen, bei denen Algorithmen Anomalien ohne Expertenwissen erkennen
- Solche Methoden hängen stark von Qualität und Kontext des Datensatzes ab
-
Drei Arten von Zeitreihenanomalien
- Punktanomalie (point anomaly): ein einzelner Datenpunkt, der deutlich vom Rest der Daten abweicht
- Kontextanomalie (contextual anomaly): ein Datenpunkt, der innerhalb des erwarteten Bereichs der Gesamtverteilung liegt, in einem bestimmten Kontext wie einem Fenster jedoch von der erwarteten Verteilung abweicht
- Kollektive Anomalie (collective anomaly): eine Sequenz von Punkten, die ein typischerweise beobachtetes Muster nicht wiederholt
- Punktanomalien und Kontextanomalien werden als point-based anomaly klassifiziert, kollektive Anomalien als sequence-based anomaly
- Die Erkennung ganzer Sequenzen ist ein Fall der Teilsequenz-Anomalieerkennung, bei dem die gesamte Zeitreihe selbst als Bewertungsobjekt dient; sie wird in Szenarien zur Sensorbereinigung eingesetzt, in denen abnormale Sensoren unter normalen Sensoren gefunden werden sollen
Datendimensionalität und Lerneinstellungen
- Univariate Zeitreihen bestehen aus einer geordneten Folge reeller Werte in einer Dimension; Anomalien werden anhand eines einzelnen Merkmals erkannt
- Multivariate Zeitreihen sind eine Menge mehrerer geordneter Folgen gleicher Länge oder eine geordnete Folge reeller Vektoren
- Im multivariaten Fall können einzelne Merkmalswerte normal erscheinen, während die gesamte Sequenz abnormal ist
- Eine Teilsequenz kann im univariaten Fall als Vektor und im multivariaten Fall als Matrix dargestellt werden, deren Zeilen jeweils die Teilsequenz einer Dimension enthalten
-
Unüberwachte, semi-überwachte und überwachte Erkennung
- Unüberwachte Verfahren werden eingesetzt, wenn keine Experteninformationen darüber vorliegen, welche Anomalien erkannt werden sollen
- Sie können ohne große Sammlungen bekannter Anomalien funktionieren
- Sie können unbekanntes abnormales Verhalten automatisch erkennen
- Sie können für die Überwachung des Systemzustands oder das Mining historischer Zeitreihen verwendet werden
- Semi-überwachte Verfahren erkennen Anomalien auf Basis von Beispielen normaler Sequenzen, die von Fachleuten bereitgestellt wurden
- In vielen Veröffentlichungen wird diese Kategorie ebenfalls als unüberwacht bezeichnet
- Es gibt jedoch die Abgrenzung, dass sie schwer in dieselbe Kategorie wie vollständig unüberwachte Verfahren einzuordnen ist, da Vorwissen über normale Beispiele erforderlich ist
- Überwachte Verfahren liegen vor, wenn Fachleute das zu erkennende Muster genau kennen und eine Sammlung gelabelter anomaler Zeitreihen vorhanden ist
- Mithilfe von Teilsequenzen vor einer anomalen Teilsequenz lässt sich eine abnormale Teilsequenz vorhersagen
- Solche vorausgehenden Teilsequenzen können als Vorläufer (precursor) bezeichnet werden
Gemeinsame Erkennungspipeline
- Algorithmen zur Anomalieerkennung in Zeitreihen folgen im Allgemeinen dem Ablauf Vorverarbeitung → Erkennungsmethode → Scoring → Nachverarbeitung
- In der Vorverarbeitung ist ein fensterbasierter Ansatz üblich, bei dem eine Zeitreihe in eine Matrix umgewandelt wird, deren Zeilen aus Sliding-Window-Segmenten bestehen
- Zusätzliche Vorverarbeitung unterscheidet sich etwa durch Extraktion statistischer Merkmale, Anpassung von Machine-Learning-Modellen oder Aufbau neuronaler Netze
- In der Erkennungsphase werden auf dem verarbeiteten Datensatz Methoden wie Distanzberechnung, Anpassung einer Klassifikations-Hyperebene oder der Vergleich erzeugter Teilsequenzen mit den ursprünglichen Teilsequenzen angewendet
- In der Scoring-Phase werden die Erkennungsergebnisse in reellwertige Anomalie-Scores umgewandelt, die die Abnormalität jeder Teilsequenz ausdrücken
- Dieser Score wird verwendet, um Scores einzelner Punkte abzuleiten
- Die resultierende Score-Zeitreihe hat dieselbe Länge wie die ursprüngliche Zeitreihe
- In der Nachverarbeitung werden aus der Anomalie-Score-Zeitreihe anomale Punkte oder Abschnitte extrahiert
- Üblicherweise wird ein Schwellenwert festgelegt, und Punkte, deren Score den Schwellenwert überschreitet, werden als Anomalien markiert
Prozessorientierte Taxonomie
- Methoden zur Anomalieerkennung in Zeitreihen lassen sich grob in distanzbasierte, dichtebasierte und vorhersagebasierte Ansätze unterteilen
- Die zweite Ebene der Klassifikation ist nicht gegenseitig ausschließend
- Ein Modell kann Zeitreihendaten komprimieren und zugleich eine discord-basierte Identifikationsstrategie verwenden
-
Distanzbasierte Methoden
- Distanzbasierte Methoden erkennen Anomalien, indem sie numerische Werte der rohen Zeitreihe mithilfe eines Distanzmaßes vergleichen
- Im Allgemeinen wird eine Distanz
d(A, B)zwischen zwei Sequenzen gleicher Länge definiert; wenn beide Sequenzen identisch sind, ist die Distanz 0 - Häufig verwendete Distanzen sind Euclidean distance und Z-normalized Euclidean distance
- Dynamic Time Warping (DTW) wird häufig genutzt, um Probleme mit Ausrichtungsfehlern zu behandeln
- Wichtige Unterkategorien sind proximitätsbasierte, clustering-basierte und discord-basierte Ansätze
- Proximitätsbasiert (proximity-based): Beurteilt Anomalien danach, wie stark eine Teilsequenz von ihren nächsten Nachbarn isoliert ist
- Clustering-basiert (clustering-based): Für die Berechnung des Anomalie-Scores kann herangezogen werden, in welchem Maß eine Teilsequenz nicht zu gelernten Clustern gehört, welche Cluster-Distanz vorliegt oder welche Cluster-Kapazität besteht
- Discord-basiert (discord-based): Findet effizient discords, also Teilsequenzen, deren Distanz zum nächsten Nachbarn unter allen Teilsequenzen am größten ist
-
Dichtebasierte Methoden
- Dichtebasierte Methoden betrachten Zeitreihen nicht nur als einfache Zahlenfolgen, sondern verarbeiten sie auf Darstellungen, in denen die Dichte von Punkten oder Teilsequenzräumen gemessen werden kann
- Darstellungen können vielfältig sein, etwa Graphen, Bäume, Histogramme oder grammatikinduzierte Regeln
- Wichtige Unterkategorien sind verteilungsbasierte, graphbasierte, baumbasierte und encoding-basierte Ansätze
- Verteilungsbasiert (distribution-based): Erzeugt aus statistischen Merkmalen von Punkten oder Teilsequenzen eine Verteilung und rekonstruiert über die Merkmalsverteilung normaler Teilsequenzen ein zugehöriges statistisches Modell, um Abnormalität abzuleiten
- Graphbasiert (graph-based): Stellt Zeitreihen und Teilsequenzen als Graphen dar und erkennt Anomalien anhand von Graphmerkmalen wie Knoten- und Kantengewichten oder Knotengraden
- Baumbasiert (tree-based): Teilt Punkte oder Teilsequenzen in einem Baum auf und beurteilt Anomalien anhand von Statistiken und Merkmalen wie der Baumtiefe
- Encoding-basiert (encoding-based): Interpretiert Zeitreihen als kontextfreie diskrete Symbole oder Zustandssequenzen und nutzt etwa Grammatikregeln der extrahierten Symbole zur Anomalieerkennung
-
Vorhersagebasierte Methoden
- Vorhersagebasierte Methoden erkennen Anomalien, indem sie auf Basis von Trainingszeitreihen oder Teilsequenzen erwartetes normales Verhalten vorhersagen
- Sie beruhen auf der Annahme, dass normale Daten leicht vorherzusagen sind, während Anomalien unerwartet sind und daher große Vorhersagefehler verursachen
- Diese Annahme gilt, wenn der Trainingssatz keine oder nur sehr wenige Anomalien enthält
- Vorhersagebasierte Methoden eignen sich in der Regel besser für semi-überwachte Settings
- Wichtige Unterkategorien sind forecasting-basierte und rekonstruktionsbasierte Ansätze
- Forecasting-basiert (forecasting-based): Nimmt Punkte oder Teilsequenzen vor einem bestimmten Zeitpunkt als Eingabe, sagt den nächsten Wert oder die nächste Teilsequenz voraus und verwendet die Differenz zwischen Ist- und Vorhersagewert als Anomalie-Score
- Rekonstruktionsbasiert (reconstruction-based): Komprimiert die Eingabe-Zeitreihe oder Teilsequenz in einen kleineren latenten Raum, rekonstruiert sie anschließend und verwendet die Differenz zwischen Eingabe und Rekonstruktion als Anomalie-Score
Evaluation und Brüche im Forschungsvergleich
- Verschiedene Forschungsbereiche sind weitgehend voneinander getrennt, da sie unterschiedliche Datensätze, Baselines und Evaluationsmetriken verwenden
- Neue Algorithmen werden häufig nur mit einigen wenig repräsentativen Ansätzen verglichen, wodurch es schwierig ist, für einen bestimmten Anwendungsfall den State-of-the-Art-Ansatz zu finden
- Die prozessorientierte Taxonomie ermöglicht es, verschiedene Erkennungsmethoden zu Gruppen von Algorithmen mit ähnlichen Ansätzen zusammenzufassen und zu vergleichen
- Literaturstatistiken zeigen Trends der Ansatztypen und Forschungsbereiche im Zeitverlauf
- Zudem werden bestehende Benchmarks, die als gemeinsame Evaluationsgrundlage dienen können, sowie Vor- und Nachteile und Grenzen von Evaluationsmetriken für die Anomalieerkennung in Zeitreihen zusammengefasst
1 Kommentare
Kommentare auf Hacker News
Das Matrix Profile ist eines der unterschätzten Werkzeuge in der Zeitreihenanalyse und sehr effizient. Es eignet sich gut, um Motive und Ausreißer zu finden, ohne wie bei traditionellen Verfahren stark an Fenstergröße und Schwellenwerten drehen zu müssen, und funktioniert robust in vielen Bereichen, etwa bei Sensordaten in der Fertigung, EKG-Analysen und Erdbebenerkennung
https://www.cs.ucr.edu/~eamonn/MatrixProfile.html
Diese Einführung derselben Forschungsgruppe ist besser
https://matrixprofile.org/
Da die Systemauslastung eine starke wöchentliche Saisonalität aufweist, bilde ich den Durchschnitt der Werte einer Metrik von vor 1, 2, 3 und 4 Wochen und vergleiche ihn mit dem aktuellen Wert. So lassen sich Alarm-Schwellenwerte dynamisch für Tag/Nacht und Werktage/Wochenenden setzen, und man vergleicht mit dem Durchschnitt für den jeweiligen Wochentag bzw. die jeweilige Tageszeit
GitLab hat einen Beitrag, der diesen Ansatz ausführlicher erklärt
https://about.gitlab.com/blog/2019/07/23/anomaly-detection-u...
Mit Feiertagen wird es etwas komplizierter, aber man kann das tatsächlich in Prometheus programmieren
https://promcon.io/2019-munich/slides/improved-alerting-with...
Ich kenne mich in diesem Gebiet nicht gut aus, aber Forecasting und Anomalieerkennung scheinen ziemlich verwandt zu sein. Kann mich auch irren
Zum Beispiel haben zeitreihenbasierte Modelle wie Granite TS, die frühere Kollegen entwickelt haben, in meinen Experimenten ziemlich gut funktioniert
Die Erkenntnis darüber, wie man über Modelle zur Anomalieerkennung nachdenken kann, war letztlich: Man sagt die nächsten N Schritte voraus und schaut dann, ob die tatsächlich gemessenen Werte „ausreichend anders“ als die Erwartungswerte sind. Bei einem einzelnen Signal lässt sich das leicht ans Whiteboard zeichnen, aber dass es auch multivariat funktioniert, ist ziemlich interessant
[1] https://huggingface.co/ibm-granite/granite-timeseries-ttm-r1
[0] https://scikit-learn.org/stable/modules/generated/sklearn.en...
Diese Geräte können Lecks erkennen und den Wasserverbrauch auf Anlagenebene schätzen. Leckerkennung ist letztlich die Identifikation von Ausreißern in Zeitreihen, und die im Paper erwähnte verteilungsbasierte Anomalieerkennung ist dafür relevant. Interessanterweise können Wohnräume wegen der Temperaturänderungen in den Leitungen zwischen warmer und kalter Jahreszeit mehrere Verteilungen erfordern
Bisher ist es nicht allzu schlecht, hat aber ziemlich große Schwächen
Ich dachte, das ginge mit Microsofts C#-Bibliothek, aber die war wirklich ein Desaster. Es wäre gut, wenn jemand die Zeit und den Willen hätte, eine ordentliche Bibliothek zu implementieren
Dieser Bereich wäre ideal für ein konfigurierbares SaaS- oder Open-Source-Tool mit fortgeschrittenem Reporting und Benachrichtigungsmechanismen. Datadog hat auch ein ordentliches Produkt, ist aber ziemlich teuer
Insbesondere ist es standardmäßig so ausgelegt, dass es offline funktioniert. Wir integrieren KI in die Geräte und schicken Daten weder an Server Dritter noch an unsere eigenen Server. Denn wir sehen viele verpasste Kundenchancen, weil keine Online-Verbindung möglich ist. Wenn jemand nach einer Lösung zur Überwachung industrieller Maschinen sucht oder sich für sicherheitskritische Industriesoftware interessiert, würden wir gern ins Gespräch kommen. Wir entwickeln auch einen Data Historian: www.sentineldevices.com
Ich habe ein System gebaut, das Ausnahmen erkennt und darauf reagiert, bevor sie auftreten, etwa indem es die Request-Rate proaktiv drosselt, bevor es zu einer Erschöpfung der Datenbank kommt — in der Hoffnung, dass das in der Praxis besser ist, als die Ausnahme einfach auftreten zu lassen.
Damals hatte ich das Gefühl, dass es in diesem Bereich wirklich viel zu tun gibt, und ich bedauere ein wenig, dass ich nicht wieder daran gearbeitet habe.
Ein weiteres zentrales Problem ist, streng und präzise zu definieren, was eine Anomalie ist und was nicht.
Auch wenn sie nicht das Kernprodukt ist, hilft sie meist bei der Optimierung des Betriebs. In der Fertigung kann Computer Vision fehlerhafte Teile auf der Montagelinie aussortieren, und im Betrieb lassen sich mit Beschleunigungs-/Temperatursensoren und Frequenzanalyse Anzeichen von Ausfällen erkennen, um Predictive Maintenance zu ermöglichen. Im Vertrieb kann man durch Zeitreihenanalysen von Kennzahlen oder Support-Anfragen Signale für steigenden oder sinkenden Cashflow, Kundenzufriedenheit usw. erkennen.
https://youtu.be/vzPgHF7gcUQ?si=rKQvOjK_qjiSSvKE