Learning the structure of graphical models based on discrete time series data in the context of ambient assisted living

Abstract

Diese Arbeit hat das Thema ein Wahrscheinlichkeitssystem in einem Ambient Assisted Living Umfeld zu konstruieren. Das langfristige Ziel dieses Forschungsfeldes ist das Leben von älteren Mitmenschen zu erleichtern. Um die wiederkehrenden Muster im Sensor-Datenstrom festzustellen, wird ein Temporal-Pattern (T-Pattern) Algorithmus verwendet und anschließend ein probabilistischer suffix automaton (PSA) generiert.Die Analyse des T-Pattern Algorithmus erfolgt durch die Evaluierung von annotierten realen Umgebungsdaten.Die Ergebnisse des ersten Experiments zeigen, dass der Algorithmus zu viele Muster erkennt und eine Feinabstimmung notwendig ist. Das erfolgt durch mehrere Schritte. Durch eine Parameteranalyse des Signifikanzniveaus kann das Problem visualisiert werden. Während für abnehmendes Signifikanzniveau weniger Muster erkannt werden, kommen die Muster mit niedriger Übereinstimmung mit den annotierten Daten zu häufig vor. Zur Lösung dieses Problems werden nur Muster mit unterschiedlicher Messenger ID berücksichtigt. Dadurch wird eine kürzere zeitliche Distanz zwischen den Beginn und Ende eines Musters erreicht. Die Messenger ID kann für jeden Sensor zwei Werte annehmen. Diese Werte können zwei verschiedene Zustände beschreiben, etwa das Öffnen und Schließen einer Tür oder Bewegung und Stillstand. T-Patterns mit derselben Sensor ID und Messenger ID sind nicht erlaubt, dies gewährleistet kürzere Zeitintervalle zwischen den Mustern und infolgedessen bessere Ergebnisse. T-Patterns mit einem einzigen Sensorereignis werden nicht in Betracht gezogen. Die Feinabstimmung durch eine Analyse mit niedrigen Signifikanzniveau wie etwa alpha = 0.005 liefert in dieser Arbeit die besten Ergebnisse.Ein weiteres Ziel dieser Arbeit ist die Konstruktion eines PSA durch Verwendung von T-Patterns. Zu diesem Zweck wird die Methode des unsupervised Lernens in Verbindung mit realen Sensordaten aus häuslichen Umfeldern verwendet. Weil keine Möglichkeit besteht einen Automaten durch Erzeugung von guten und schlechten Beispielen aus den Daten zu erlernen, können auch nicht die Methoden des supvervised Lernens verwendet werden. Daher wird zuerst ein probabilistic suffix tree (PST) mit den signifikanten T-Pattern generiert. Für jedes signifikante Muster wird ein Knoten erzeugt und diesem Wahrscheinlichkeiten für die nachfolgenden Knoten zugeordnet. Bei der Zuweisung von Wahrscheinlichkeiten werden verschiedene Berechnungsmethoden und Wahrscheinlichkeitsverteilungen erprobt.Die Suche nach einer passenden Methode startet mit der Binomialverteilung. Diese auch in [23] empfohlene Verteilung, erweist sich aber als suboptimal, da es für dünn verstreute Daten und bei Störsignalen falsche Ergebnisse liefert. Der Grund dafür ist, dass die Wahrscheinlichkeit einer Binomialverteilung von der Anzahl der Beobachtungen, der Länge des Zeitintervalls und den diskreten Zeitschritten abhängt.Im Folgenden wird die Methode der Poisson-Prozesse untersucht, wo jeder Schritt als Poisson Prozess angenommen wird. Im nächsten Versuch werden Markov-Prozesse in Betracht gezogen, wobei in jedem Schritt, die momentane Wahrscheinlichkeit von der Wahrscheinlichkeit des vorhergehenden Schrittes abhängt. Aufgrund der großen Zeitspannen ohne signifikante Sensorereignisse liefern diese Markov Prozesse keine zufriedenstellenden Ergebnisse. Unter Verwendung der Poissonverteilung ist die Berechnung der Übergangswahrscheinlichkeiten stabiler.Ein zusätzlich komplizierender Effekt ist die Anforderung an jeden Pattern-Step sich auf eins zu summieren, da ansonsten aus dem PST kein PSA konstruiert werden kann. Das geschieht durch hinzufügen eines zusätzlichen Knotens, welcher für die Wahrscheinlichkeit steht, dass nichts Signifikantes passiert.Der zuvor erwähnte PST kann mit einem Algorithmus in einen PSA transformiert werden. Dieser PSA unterscheidet sich nur durch die Pfeile zwischen den Knoten und nicht durch die Wahrscheinlichkeiten oder die Anzahl der Knoten. Der Automat ist wichtig, weil er im Gegenteil zu einem Baum keinen Endknoten besitzt. Dies garantiert ein System welches benutzt werden kann um Anomalien im Verhalten von älteren Menschen zu detektieren oder um zukünftige Ereignisse vorherzusehen. Basierend auf diesen Ergebnissen können Bewohner eines Smart Homes informiert oder gewarnt werden.

This thesis addresses the issue of building a probabilistic system in and ambient assisted living environment to ensure a proper living for older adults. The aim in this context is to detect recurrent patterns in a stream of domestic sensor data using the Temporal-Pattern (T-Pattern) algorithm and to automatically generate probabilistic finite-state automata. This also includes the analysis of the T-Pattern algorithms and measurement of their performance.The analysis of the T-Pattern algorithm is done via evaluation of a real environment annotated dataset. The aim is to find out, if the T-Pattern algorithm is feasible for the mentioned purposes.The results of the first attempt show that the algorithm detects too many patterns and further fine-tuning is required. Fine-tuning is being done over several steps. By making a parameter analysis of the significance level the problem is visualized. Even though less patterns are found for decreasing significance levels, the patterns which have a low intersection interval with the annotated dataset still occur too frequently.To solve this problem only patterns with different messenger Ids are taken into account to get shorter temporal distances between the beginning and ending of the patterns. The messenger Ids can assume two values for each sensor which describes, for example, opening or closing the door, motion or no-motion. T-Patterns with the same sensor Id and the same messenger Id are not allowed, which guarantees a more appropriate result with shorter time intervals in between the patterns. T-Patterns from a single sensor event are ignored. The fine-tuning with a low significance level analysis like alpha = 0.005 provides the best results to work further with.Another objective of this thesis is to build a probabilistic suffix automaton (PSA) out of the T-Patterns. Therefore unsupervised learning is used, because of the domestic senor data in real environments. There is no way to learn the automaton straight forward, that means good and bad examples cannot be generated out of the data and cannot be considered to learn the machine. This means supervised learning methods are ineligible. Therefore a probabilistic suffix tree (PST) is built first with the significant T-Patterns. For every significant pattern a node is constructed and next symbol probabilities are assigned to them. The assignment of probabilities has been a long process of trying different calculation and distribution methods.The search of finding good methods starts with a binomial distribution, but the binomial distribution as proposed in [23]turned out to be suboptimal. This distribution provided invalid results when applied to sparse patterns in noisy data streams. Since the probability of the binomial distribution depends on the number of overall events, the length of the observed time interval and the discrete time steps, respectively. Further research lead to Poisson Processes, where each step is seen as a Poisson Process. In the next attempt one order Markov Processes were considered, where in each step the probability is dependent on the probability of the step before. These Markov Processes perform badly due to the large time durations without significant sensor events. With the Poisson distribution the computation of the next symbol probabilities becomes more reliable.Another complicated aspect is that in every pattern step the probabilities must sum up to one, as otherwise no automaton can be constructed out of the tree. This is done by adding an additional node, which describes the probability of nothing significant happening.The already stated PST can be transformed into a PSA by means of an algorithm. This PSA only differs in the arcs between the nodes and not in the probabilities or the number of nodes. The automaton is important, as there is no end node in contrast to a tree. This guarantees a system which can be used to detect anomalies in the elderly adults behavior or predict events occurring in the future. Based on this outcomes inhabitants of a smart home can be informed or warned.