Humboldt-Universit?t zu Berlin

A time series?is a sequence?of real valued?numbers?ordered in time. Motif?discovery?is?the problem?of?finding?frequently?occurring?patterns, ?so-called?motifs, in a time series. This fundamental problem?is?used??across?many?domains, such as?medicine, biology, meteorology?and??robotics. In literature, multiple motif?definitions?are?foundfinding?the top latent motif, i.e. with?highest?number?of?occurrences, has?received a lot?of?attention in recent?research, its?complexity?is?still unknown. In this?work, we?show?that?it?is NP complete.

Furthermore, the?motif?length?is a parameter?that?is?hard?to?determine?in practical applications. However, state-of-the-art algorithms?for?latent motif?discovery?either?require the?length?to?be?set?explicitly?or?they find approximate?results. In this?work, we?propose VLCM, which?is?the?first?exact?algorithm?that?discovers latent motifs?of variable length?and thus?eliminates?the?need?to?accurately?set?the?motif?length. Our?algorithm?solves?the top latent motif?discovery?problem?by?reducing?it?to?the?maximum?clique?problem. To find motifs?of variable length, VLCM computes?the top latent motif?for?each?length in a given range. A naive method?would?run a state-of-the-art fixed-length?algorithm?once?for?each length. We?use multiple pruning?techniques?to?greatly?reduce?the?number?of?calculations needed. This results in VLCM being an order?of?magnitude?faster?than?the naive approach.

In our?evaluation?we?compare?our?algorithm?against?state-of-the-art methods in terms?of runtime, memory?consumption?and?motif?quality. The results?show?that VLCM processes time series?up?to?length 60‘000 within?one?hour, while?having a memory?consumption?of less?than 6 GiB. The algorithm also finds?the?highest?quality?motifs. First, VLCM’s?motifs contain 2 to 10 times?as?many?occurrences?as?approximate?methods?given?the same similarity?threshold. Second, it?has?the?highest?accuracy?across all state-of-the-art methods?when?analyzing?motifs?found on datasets?with?annotated?ground-truth?motifs.

?

?

Deutsche Version

Eine Zeitreihe ist eine zeitlich geordnete Folge reeller Zahlen. ?Motif?Discovery“ ist das Problem, h?ufig vorkommende Muster, sogenannte Motive, in einer Zeitreihe zu finden. Dieses grundlegende Problem wird in vielen Bereichen verwendet, bspw. der Medizin, Biologie, Meteorologie und Robotik. In der Literatur finden sich mehrere Motivdefinitionen.

In dieser Arbeit sollen latente Motive gefunden werden, bei denen sich die Vorkommen nur approximativ ?hneln müssen. Obwohl das Finden des besten latenten Motivs, also mit der h?chsten Anzahl an Vorkommen, in jüngster Forschung viel Aufmerksamkeit erhalten hat, ist seine Komplexit?t noch unbekannt. In dieser Arbeit wird bewiesen, dass es zu der Klasse der NP-vollst?ndigen Probleme geh?rt.

Weiterhin ist die Motivl?nge ein Parameter, der in praktischen Anwendungen schwer zu bestimmen ist. Moderne Algorithmen zur Erkennung latenter Motive erfordern jedoch entweder die explizite Angabe der L?nge oder sie finden nur ungenaue Ergebnisse. In dieser Arbeit wird VLCM vorgestellt: der erste exakte Algorithmus, der latente Motive variabler L?nge findet. Dadurch beseitigt er die Notwendigkeit, die Motivl?nge genau einzustellen. Der Algorithmus findet das beste latente Motiv, indem er es das Problem auf das Finden der maximalen Clique in einem speziellen konstruierten Graphen zurückführt. Um Motive variabler L?nge zu finden, berechnet VLCM das beste latente Motiv für jede L?nge in einem gegebenen Intervall. Ein naives Verfahren würde einen aktuellen?Algorithmus mit fester L?nge je einmal für jede L?nge ausführen. VLCM verwendet jedoch mehrere Pruning-Techniken, um die Anzahl der erforderlichen Berechnungen erheblich zu reduzieren. Dies führt dazu, dass VLCM um das Zehnfache schneller ist als der naive Ansatz.

In der Auswertung wird der Algorithmus hinsichtlich Laufzeit, Speicherverbrauch und Motivqualit?t mit den modernsten Methoden verglichen. Die Ergebnisse zeigen, dass VLCM Zeitreihen bis zu einer L?nge von 60‘000 innerhalb einer Stunde verarbeitet, wobei weniger als 6 GiB Arbeitsspeicher verbraucht werden. Der Algorithmus findet zudem die?hochwertigsten Motive. Zun?chst enthalten die Motive von VLCM 2- bis 10-mal so viele Vorkommen wie andere Verfahren. Au?erdem zeigt VLCM die h?chste Genauigkeit beim Finden des besten latenten Motivs.

?