Übersicht
● Einordnung in das Themengebiet Datamining● Ähnlichkeitssuche● Zeitreihen● Anwendungen
● Effiziente Ähnlichkeitssuche auf Zeitreihennach Rakesh Agrawal, Christos Faloutsos, Arun N. Swami
● Fouriertransformation● R*-Tree
● Suche auf Teil-Zeitreihen
Datamining
Eine von vielen Definitionen: Datamining ist ...
... „die Anwendung (mathematischer) Methoden
auf einen [üblicherweise großen] Datenbestand,
mit dem Ziel der Mustererkennung“.
Wikipedia - Die freie Enzyklopädie (Hrsg.)Wikipedia DVD-Ausgabe vom 20. September 2006
Artikel “Data-Mining“
Techniken und Methoden
● Entscheidungs- und Klassifikationsbäume
● Neuronale Netze
● Rule-Induction
● Clustering und Ähnlichkeitssuche
● k-Means-Clustering● k-Nearest-Neighbours● Range-Query
Zeitreihen
Agrawal, Faloutsos, Swami
● Erlaubt● Range-Queries● All-Pairs-Queries
● Restriktionen● äquidistante Zeitreihen● identischer Länge● Keine Suche auf Teil-Zeitreihen
● Grundidee● Abbildung der Zeitreihen auf Frequenz-Spektren
mittels Diskreter Fourier-Transformation● Indizierung anhand von drei bis fünf Frequenzen mit einem
R*-Tree
Fourieranalyse: Basis
Fourieranalyse: Fourierreihen
Fourieranalyse: Ähnlichkeit
Fourieranalyse: Rauschen
Fourieranalyse: Folgerungen
● Ähnliche Zeitreihen → Ähnliche Spektren● Niedrige Frequenzen sind signifikant
● auch bei braunem Rauschen ● Störungen = (weißes) Rauschen
● damit ist (als Überlagerung) immer zu rechnen● weißes Rauschen ist „Worst Case“
→ Verwendung der niedrigen Frequenzen zur Indizierung der Zeitreihen möglich!
→ Es kann zu false alerts im Index kommen Es kann nicht zu false dismissals kommen
R*-Tree: Bounding Boxes
● Ursprünglich real-räumliche ausgedehnte Objekte● Nutzung minimaler Bounding-Boxes
● Übertragung auf● Feature-Räume (ggf. multi-dimensional)● Punkte als degenerierte Objekte
R*-Tree: Index
● Bounding Boxes um Objekt-Gruppen
● Gruppierung nachminimalen
● Flächen● Überschneidungen● ...
● Hierarchisch, d.h.Gruppen von Gruppen
→ Baum-Struktur
● Suche nur in Zweigen, deren Bounding Box das gesuchte Objekt umfasst
R*-Tree: Suche
Suche nur in Zweigen, deren Bounding Box ...● das gesuchte Objekt vollständig umfasst● sich mit dem Suchbereich überschneidet
R*-Tree: Updates
● Aufwände für● Berechnung der minimalen Bounding Boxes
über den gesamten Zugriffspfad● Zuordnung zu Gruppen● Reorganisation der Gruppen
● bei überfüllten Knoten● bei degenerierter Gruppierung
→ Tradeoff zwischen● Such-Beschleunigung und● Update-Verzögerung
● Hier liegen Unterschiede zwischen Mitgliedern derR-Tree Familie
Agrawal, Faloutsos, Swami
● Einfügen einer Zeitreihe
● Diskrete Fourier-Transformation durchführen
● Eintrag im R*-Tree
● Range-Query zu einer Anfrage-Zeitreihe durchführen
● Diskrete Fourier-Transformation durchführen
● Suche im R*-Tree nach TreffernKann false alarms enthalten
● PostprocessingBerechnung der wahren Distanz anhand der Zeitreihen
● Ergebnis:Liste von Zeitreihen, die in der Range liegen
Fortentwicklungen
● Zeitreihen unterschiedlicher Länge / Abtast-Rate:Resampling
● Abfrage auf Teil-Zeitreihen● Indizierung
● Minimale Länge für Abfrage-Zeitreihen festlegen: length● “Fenster“ der Länge lenght über die Zeitreihen bewegen→ Traces von Punkten im Feature-Raum● Teil-Traces als ausgedehnte Objekte im R*-Tree indiziert
● Suche ● Länge length: → Einfache Suche im Index● Länge größer length: → Prefix-Suche (ineffektiv)
→ Multi-Suche auf Teil-Stücke mit reduzierter Range; Ergebnis: Vereinigungsmenge