Project topics and materials
Get Complete Project Material File(s) Now! »
Habit characterization and discovery
Habits are behaviors each individual tends to follow given a particular context.
The context may be temporal (time, day, season), a personal feeling (hunger, thirst, tiredness), a situation or an event that just occurred (it started raining, mail was delivered, etc.). The behavior the user puts into action to react to the condition is personal: two individuals are unlikely to share the same habits, react in the same way, or share the same daily organization.
Habits can usually be described using a natural language thanks to sentences such as: “When <condition>, the person usually <does something>”
The <condition> can also be a combination of conditions. Table 2.1 provides some examples of such habits. In the context of ambient assisted living, we monitor the ADLs, and habits related to the ADLs are of particular interest, since they characterize normal behaviors and landmarks to assess safety and well-being. Deviations from usual habits and missing regular behaviors can hint a problem. Habits triggered by an event and habits triggered by a temporal context call for different tools to formalize and detect habits. For example, usual reactions to an event that just occurred or a feeling (examples 2 and 3 in table 2.1) are usually detected thanks to association rules (Rodner and Litz, 2013) and temporal association rules to exhibit causality (Nazerfard et al., 2010b), or thanks to frequent sequences (Rashidi and Cook, 2010). In this thesis, we extend these approaches by focusing on habits triggered by temporal contexts (time, date, such as examples 1 and 4 in table 2.1). Such habits can also be expressed as: “Every <period>, around <time position within the period>, the user usually <does something>” Some of the habits described in table 2.1 can be reformulated with this (<period>, <time position>) formalism (table 2.2). We focus here on the detection of this kind of behaviors.
The rhythm at which activities tend to occur (i.e. the period) varies from one activity to the other. For example, waking up and meals occur daily (even several times a day for the meals), shopping is weekly, visits to the physician may occur once or twice a month, etc.
Periodicity as a Gaussian mixture model
We argue that a good way to apprehend periodicity is to describe the clusters of occurrences, such as they are represented in figure 2.1, which we propose to do thanks to Gaussian Mixture Models (GMM). Gaussian Mixture Models are frequently used to model the behaviors of random variables. We apply them here to periodicity description. This description covers the desirable characteristics of a periodicity description for the characterization of behaviors emanating from living species: in particular, it is not perturbed by missing occurrences, and shows robustness with regard to the presence of shifted or extra occurrences (see the coming paragraphs for more detail). It also characterizes how and how often these unexpected behaviors occur. The next paragraphs describe how the mixtures models are used in xED and sxED.
Relative timestamps. For a period T (e.g. one day, one week, one month), and a timestamp t, the relative timestamp tr refers to the position of t within the period: tr = t mod T. For example, with a period of one day, the relative timestamp corresponding to 2015-11-24 10:21:00 is the time: 10:21:00. With a period of one week, it is the combination of the day within the week and time: Tuesday, 10:21:00. The periodicity description with GMMs aims at the description of the distribution of the relative timestamps for a given period T. Gaussian Mixture Models In this formalism, the periodicity (for a period T) of each habit E is described with a Gaussian Mixture Model MTE , that is to say a list of components, described by their means and standard deviations: MTE = f(1; 1); : : : ; (m; m)g
Related work: Episode Discovery
To the best of our knowledge, algorithms used in SHAAL systems are not designed for the same purposes as xED, that is to say: periodic episode discovery and usual variability characterization. The closest algorithm is Episode Discovery, the main focus of which is also the periodic episode discovery (but with a different periodicity definition). This section details how Episode Discovery works, and discusses its limitations. Episode Discovery (ED) (Heierman et al., 2004) is based on the Minimum Description Length (MDL) principle (Rissanen, 1989), which states that the best model to represent data is the one with the shortest description. Following this principle, ED replaces the occurrences of periodically reoccurring episodes by a single header, describing the episodes and when they occur. This allows the rewriting of the dataset into more compact representations. ED iteratively follows three steps:
1. Generation of a list of candidate episodes
2. Periodicity analysis of each candidate. Two periodicity descriptions are computed, with different granularities (the timestamps are truncated):
a fine-grained periodicity (truncation to the full hour),
a coarse-grained periodicity (truncation to the full day).
In ED, the periodicity of an episode is based on repeating cycles of time intervals. For an episode E occurring at times t0; t1; :::; tn, the periodicity analysis goes as follows:
Truncation of the timestamps to the currently investigated granularity
(hour or day): the resulting timestamps are t0 0; t0 1; :::; t0 n.
Computation of the intervals between the occurrences t1; :::; tn, with ti = t0 i t0 i1 for 1 i n.
Estimation of the most likely length l of the repeating cycle of intervals, thanks to an autocorrelation measure.
Processing of the occurrences: The first l intervals.
Table of contents :
List of Tables
List of Figures
List of Algorithms
List of Acronyms
General introduction
Research scope
Objectives
Outline
1 Ambient assisted living and activity monitoring
1.1 Socio-demographic context
1.2 Activities of daily living
1.3 Smart homes and ambient assisted living
1.4 Sensors
1.5 Activity recognition
1.6 Unsupervised activity analysis
1.7 Positioning
2 Habit monitoring
2.1 Introduction
2.2 Habit characterization and discovery
2.3 Periodicity analysis
2.4 Periodicity as a Gaussian mixture model
2.5 Conclusion
3 Periodic episode discovery in static databases
3.1 Introduction
3.2 Habits and episodes
3.3 Related work: Episode Discovery
3.4 Extended Episode Discovery
3.4.1 Candidate episode search in xED
3.4.2 Periodicity and variability characterization
3.4.3 Dataset rewriting
3.4.4 Illustration with example 3.1
3.5 Case studies
3.5.1 KA dataset
3.5.2 Synthetic results for six real-life datasets
3.5.3 Comparison between ED and xED
3.5.4 Discussion
3.6 Conclusion
4 Periodic frequent episode discovery in event streams
4.1 Introduction
4.2 Mining event sequences: formalisms and related work
4.2.1 Episode families
4.2.2 Episode support measures
4.2.3 Types of searched patterns
4.2.4 Conclusion
4.3 Frequent periodic pattern discovery and update: the sxED algorithm
4.3.1 Time queues
4.3.2 Episode Lattice
4.3.3 Recently modified nodes
4.3.4 Lattice update
4.3.5 Periodicity discovery
4.3.6 General workflow
4.4 Experimentation
4.4.1 Experiments with three activity datasets
4.4.2 Parameter influence
4.4.3 Qualitative comparison with xED on KA dataset
4.5 Conclusion
5 Top-k regular episodes
5.1 Introduction
5.2 Literature Review: regularity
5.3 Problem definition
5.4 Proposed TKRES algorithm
5.4.1 k-tree
5.4.2 Initial mining
5.4.3 Mining new incoming batches
5.5 Experimental study on home activity monitoring datasets
5.5.1 Performance assessment
5.5.2 Qualitative analysis
5.6 Conclusion
6 Conclusion
6.1 Summary and contributions
6.2 Future work
6.2.1 Periodicity characterization and evaluation
6.2.2 Handling uncertainty
6.2.3 Trend analysis and anomaly detection
6.2.4 Episode and activity recognition
6.2.5 Feedback towards the users
A MDE approach for ADL supervision
A.1 Introduction
A.2 Understanding model
A.2.1 Event Logs and Activities
A.2.2 Automated design of the understanding model
A.2.3 Illustration on the KA dataset
A.3 Intervention model
A.3.1 Sequence pruning based on critical sequences
A.3.2 System using anomaly detection
A.3.3 Experimental results
A.4 Conclusion and Perspectives
B Activity pattern visualization
C Experiment: sxED on the Travian game dataset
D Full results for TKRES, on the Aruba datasets (sensors and activities)
Bibliography
