Die Ähnlichkeitssuche von Zeitreihen mit Indexen ist eine wichtige Voraussetzung für viele Data-Mining-Aufgaben und eine Herausforderung in der Forschung. Eine Zeitreihe ist ein hoch-dimensionaler Datentyp, dessen Repräsentation speicher- und dessen Vergleich zeitaufwändig ist. Form-basierte Repräsentationstechniken wie Symbolic Aggregate Approximation (SAX) lösen diese Herausforderungen durch eine reduzierte und indexierbare Repräsentation mit einem effizienten Distanzmaß. Darüber hinaus berücksichtigen die saison- und trend-bereinigte SAX-Repräsentation, sSAX und tSAX, das deterministische Saison- und Trend-Verhalten, das in einer Vielzahl von Domänen auftritt. Bisher wurden die Distanzmaße für sSAX und tSAX nur für den symmetrischen Vergleich zweier Zeitreihen definiert. Ziel dieser Bachelorarbeit ist die Entwicklung eines asymmetrischen Distanzmaßes und deren Einsatz in einem baum-basierten Index, durch den die Ähnlichkeitssuche noch effizienter gestaltet werden kann.
Zeitreihen sind eine wichtige Datenquelle für die Automatisierung und für Data-Mining-Aufgaben in vielen Domänen. Eine wichtige Voraussetzung dieser Anwendungen ist die Ermittlung ähnlicher Zeitreihen, die Ähnlichkeitssuche. Aufgrund ihrer Länge sind Zeitreihen hoch-dimensional. Üblicherweise werden sie nicht direkt miteinander verglichen, sondern durch eine Repräsentation in geringerer Dimension und mit einem Distanzmaß, welches den Vergleich durch die Euklidische Distanz abschätzt.
Die formbasierte Repräsentation Symbolic Aggregate Approximation (SAX) ist für die Ähnlichkeitssuche gut geeignet [1, 2]. Sie zerlegt eine Zeitreihe in Segmente und repräsentiert jedes Segment durch seinen Mittelwert, welcher zusätzlich noch diskretisiert wird. Dadurch ergibt sich eine kleine Repräsentation und ein schnelles Distanzmaß. Diese Distanz bildet dabei eine untere Schranke für die Euklidische Distanz zweier Zeitreihen, welche ein effizientes Pruning bei der Ähnlichkeitssuche ermöglicht. Ferner ist die SAX-Repräsentation indexierbar, wie durch iSAX gezeigt wurde [3].
Basierend auf SAX wurde die saison- und trend-bereinigte Repräsentation, sSAX und tSAX, entwickelt. Die Berücksichtigung dieser zwei Komponenten Saison und Trend, die in vielen Domänen auftreten, ermöglicht eine verbesserte Symbolverteilung, eine genauere Repräsentation und letztlich eine effizientere Ähnlichkeitssuche, was anhand eines symmetrischen Ähnlichkeitsmaßes nachgewiesen wurde [4].
Aufgabe dieser Bachelorarbeit ist die Entwicklung eines asymmetrischen Distanzmaßes für sSAX und tSAX und dessen Einsatz in einem Index. Als asymmetrische Distanz wird dabei der Vergleich einer reellwertigen mit einer diskretisierten Repräsentation verstanden. Dabei sind folgende Teilaufgaben zu erfüllen:
Lin, J., Keogh, E., Lonardi, S., & Chiu, B. (2003). A Symbolic Representation of Time Series, with Implications for Streaming Algorithms. In Workshop Proc. of SIGMOD (pp. 2–11). https://doi.org/10.1145/882082.882086
Lin, J., Keogh, E., Wei, L., & Lonardi, S. (2007). Experiencing SAX: A novel symbolic representation of time series. Data Min Knowl Discov, 15(2), 107–144. https://doi.org/10.1007/s10618-007-0064-z
Shieh, J., & Keogh, E. J. (2008). iSAX: Indexing and Mining Terabyte Sized Time Series. In SIGKDD (pp. 623–631). https://doi.org/10.1145/1401890.1401966
Kegel, L., Hartmann, C., Thiele, M., & Lehner, W. (2019). Season- and Trend-aware Symbolic Approximation for Efficient Time Series Matching. – nicht veröffentlichtes Manuskript