In this paper we propose a streaming approach for the discovery and monitoring of frequent patterns (the episodes) within the recent past of an event stream. This approach is based on the heuristic computation of the estimated support of the episodes of interest, and allows the fast discovery of frequent episodes with limited information storage. In particular, we do not even need to store the window of interest, which is necessary for exact frequent episode discovery. The proposed algorithm, FEM-ASC (Frequent Episode Mining, with Approximate Support Counting) is still at an early development stage, but already shows promising results on an activity monitoring task. In particular, FEM-ASC yields results very similar to those produced by an exact method, while requiring much fewer resources.
Frequent pattern mining is a traditional unsupervised data mining task, with
applications in di erent elds, such as sale monitoring, or human activity
monitoring. We propose here to mine the frequent episodes in a stream of events.
The data used in the experiment comes from a sensor network in a smart home.
Instead of considering the whole event history, we propose to focus on the recent
past exclusively. The originality of the developed approach lies in its capacity to
mine frequent episodes without keeping track of the history. In particular, we do
not store the contents of the window of interest. In order to do so, we devise a
heuristic strategy for support counting that uses decay strategies.
Contributions. We propose FEM-ASC, which stands for Frequent Episode Mining
using Approximate Support Counting. This heuristic algorithm estimates the
expected support of the episodes, and handles the monitoring of the frequent
episodes. FEM-ASC complies with the constraints linked to stream mining [
Outline. The remainder of the paper is organised as follows. Section 2 introduces episode mining and relevant related work. Section 3 presents the formalisms and notations used throughout this work, while section 4 details how FEM-ASC works. Initial testing and validation results are presented in section 5. Finally, section 6 draws some conclusions and plans for future work. 2
2.1
Frequent episode mining is a data mining task introduced by Mannila et al. [
Episode mining. Episode minig is the task of nding relevant episodes (see de
nition 2). If Mannila et al. [
quence S if there are events in S having the same labels as those of E and respecting the order constraints. These events then form an occurrence of E.
If it is fairly straightforward to count the support of an itemset in a
transactional database, it is however harder to settle on a single de nition when it
comes to episodes. Several main trends have thus emerged:
Window-based support [
De nition 4 (Minimal occurrence - MO). Let E = fe1; :::eng be an episode, and o an occurrence of E starting at timestamp t1 and nishing at timestamp tn. We refer to the interval [t1; tn] as the span of E. o is a minimal occurrence if there is no other, shorter occurrence whose span is included in [t1; tn]. That is to say, there cannot be an occurrence o0 of E starting in t01 and nishing in t0n such that t1 t01, t0n tn and t0n t01 < tn t1.
Maximal count of distinct occurrences. With both previous methods, some events
participate in several occurrences of an episode. This lead researchers to look
for the maximal number of distinct [
Hybrid measures. In order to bene t from the properties of di erent support
families, the measures may be combined. For example, minimal occurrences are
sometimes counted only if they are distinct from previous minimal occurrences
[
a threshold Tep constraints the maximal occurrence duration (longer occurrences are discarded). We de ne a hybrid support as the count of the non-overlapping minimal occurrences within the lastest window of interest [t TW ; t] (duration TW ). Occurrences satisfying these constraints are refered to as Tep-NOMO.
The support veri es the downward closure property [
De nition 5 (Expected support). At each time t, we de ne the expected support S^(t) of the episode as: >8S^last > S^(t) = <0 >>:S^last 1 t tlast
TW t0 > t t
tlast otherwise
TW
TW (1) The rst case considers the initial monitoring of the support: all occurrences are too recent to be outdated. The second case is the situation when all occurrences are outdated. Finally, the third emuates the expected support decrease: the term t tlast corresponds to the proportion of the occurrences that we expect occurred
TW between tlast TW and t TW and are thus now outdated.
If a new non-overlapping occurrence is detected (see the conditions in section 3.2) at time t, the approximate support is updated: S^last S^(t) + 1, as is tlast t. Figure 1 presents the evolution of the real and expected supports for episode fAg on a toy stream with a window of size TW = 6. The expected support does not follow exactly the real support, and unfortunately, the divergence between the real and expected supports may be important, for example if the temporal distribution of the occurrences follows burst patterns. But if we consider a fairly homogeneous occurrence distribution over the window of interest, the discovered trends are very similar to the real support evolution.
Support of fAg
Indeed, minimal occurrences have convenient properties, as mentioned for
instance in [
E a new occurrence of E0 spanning [ tlast:start; t] { Moreover, this occurrence is minimal if tlEast starts strictly after tlEa0st.
Then, we can update tlEa0st as [ tlEast:start; t]. { Finally, if this new tlEa0st starts after tlEa0st, this occurrence does not overlap previous Tep-NOMOs: it counts for the support, S^last and tlEa0st are updated.
We refer to the process of building the next minimal occurrence of E0 from the last occurrence of E and a new event (e; t) as augmenting E with (e; t). This gives a particular importance to the minimal occurrences that started less than Tep before the event currently under consideration. The episodes whose last minimal occurrence started less than Tep ago are said to be recently observed. Figure 2 illustrates some of the possible con gurations (minimal and non-minimal new occurrences). 4 4.1
Frequent episode mining with FEM-ASC
The event stream is processed one event at the time, chronologically. The arriving event (e; t) is susceptible of augmenting any recently observed episode. The e tlEa0st E tlast not minimal e t (a) New minimal occurrence (b) Not a new minimal occurrence Size of the period of interest. Older events are outdated, and should not appear in the support. 0 < Tep < TW
Occurrences longer than Tep are not counted
Support threshold for an episode to be
considered as frequent
Support threshold for an episode to be considered as subfrequent, and thus maintained in the lattice 0 < Ssub < Smin
E tlast new MO of E0
Name
TW Maximal episode duration Tep
Frequency threshold Smin
threshold Ssub recently observed episodes are thus traversed in order to check if they can be augmented. Any new minimal occurrence discovered leads to the update of the corresponding episode, thus making it a candidate for future augmentations.
The key to e cient update is the use of a lattice structure for the storage of the episodes. The lattice is described in section 4.2, and the lists for the retrieval of the recently observed episodes in section 4.3. The update procedures are detailed in section 4.4. We use two support thresholds, which allows us to make a compromise between the size of the search space and the reactivity to concept drifts: a frequency threshold Smin, and a subfrequency threshold Ssub, with Ssub Smin. Table 2 summarizes the parameters used to tune FEM-ASC. 4.2
The relevant episodes are stored in a frequent episode lattice (FEL). Each node in the lattice corresponds to an episode E, and contains the information required for the approximate support computation and update. That is to say: { The date t0 at which started the rst recorded occurrence for E { The span of its last minimal occurrence tlEast { The end of the last non-overlapping minimal occurrence tlEast { The support approximated at time tlEast: S^last ... root
C
C A
fBg t0 = 51 S^last = 3 tlast = (56; 56) tlast = 56
A
D fCg t0 = 52 S^last = 1 tlast = (52; 52) tlast = 52 Legend episode statistics
fDg t0 = 54 S^last = 1 tlast = (54; 54) tlast = 54
fAg
However, not every episode is stored in the lattice, it would otherwise grow impractical. We choose to maintain a node in the lattice if: (i) it is at least subfrequent: it may then be a candidate for augmentation, or (ii) it was created less than TW ago: we do not know yet if it is going to be frequent. This strategy choice means that an episode needs to be monitored for a while, until it gets at least subfrequent before we start considering longer episodes containing it. Formerly frequent episodes also remain in the lattice until they fall under the subfrequency threshold. This reduces the repetitive addition / deletion of nodes, and allows faster adaptation to drifts in the data distribution.
The parents of a node (located at depth d) correspond to its sub-episodes of length d 1, and its children to its super-episodes of length d + 1. The edges linking two episodes are indexed on the only event label that is present in the child but not in the parent. In spite of its possibly big edge count, the lattice structure was preferred to the standard pre x tree: it allows faster episode retrieval. As pointed out in section 3.2, the recently observed episodes may be augmented with a new incoming event to form an occurrence of a longer episode. It is thus necessary to easily retrieve the recently observed episodes that are at least Algorithm 1 Update of the lattice when a new event is recorded subfrequent. We use doubly linked lists to iterate over the recently observed episodes for each depth level in the lattice. The order of the nodes in each linked list does not in uence the occurrence discovery, but all the nodes at a given depth d should be considered for augmentation before the traversal of depth d + 1. Otherwise, this may lead to inconsistencies in the lattice. Figure 3 presents the lattice on a toy dataset after the rst 7 events have been introduced, with the parameters Ssub = 2, Smin = 3, Tep = 3, and TW = 6. 4.4
When a new event (e; t) arrives, the lattice update follows algorithm 1: the episode E represented by each of the recently modi ed node is considered as a candidate for augmentation. Some candidates are pruned: those who already contain e, and those added in the RMN-lists too long ago and thus do not belong there any more. Then, two cases arise: either the node for episode E [feg already exists, and we need to gure out whether we have a new minimal occurrence; or the node does not exist, and we must decide whether it should be created. Removal of outdated information. Regular sweeps over the lattice enable the removal of outdated nodes and branches. An alternative strategy has also been considered: we check whether a node is outdated when it is updated. This alternative strategy misses outdated nodes: those not traversed via the updates with the new events. The alternative strategy has not been evaluated yet.
TW Tep Smin Ssub
In uence of TW
In uence of Tep
In uence of Smin 1 min, 1 hour, 1 day, 1 week, 2 weeks, 4 weeks min(30 min, TW )
4 weeks 1 min, 30 min, 1 hour, 12 hours
30 min median label support over the dataset divided by TW , with a minimal of 3 (3, 3, 3, 9, 17, 33)
Smin=2 Smin=2 Table 3: Detailed setting used in the experiments
median label support over the dataset divided 17, 33, 66, 99, 131, 164 by TW (33)
Smin=2 5
Initial experimental results on activity monitoring
This section presents the initial results of FEM-ASC on a dataset coming from
the activity recognition community: the CASAS Aruba dataset1 [
Two aspects are considered: (i) the scalability of FEM-ASC, and (ii) its ability
to yield good results in spite of its heuristic nature. The scalability is evaluated
via the evolutions of the size of the episode lattice and of the length of the
RMN linked list during the execution of FEM-ASC: it is expected to remain fairly
constant. The quality of the results yielded by FEM-ASC are compared with those
produced by an exact frequent episode miner. We use the one described in [
We note T P the number of true positives; { An episode is said to be a false positive if FEM-ASC considers it frequent, but it is actually not. We note F P the number of false positives; { An episode is said to be a false negative if it is discovered by the exact method but missed by FEM-ASC. We note F N the number of false negatives; { The precision p and recall r are de ned as p =
T P T P + F P r =
T P T P + F N
We evaluate the in uence of three parameters on the scalability and quality of FEM-ASC: the size of the window of interest TW (see gure 4), the maximal 1 http://ailab.wsu.edu/casas/datasets/aruba.zip ●●●● ●●●●●●●●●● ●●●●●● ● ● ● ●●●●●● ●●●●●● ●●●●●●●●● 1 minute 1 hour 1 day 1 week 2 weeks 1 month (a) Size of the lattice 1 minute 1 hour 1 day 1 week 2 weeks 1 month
(b) Size of RMN 5 2 0 2 5 1 0 1 5
Fig. 5: In uence of the episode duration Tep
33 66 99 131 (a) Size of the lattice 164 17 33 66 99 (b) Size of RMN 131
164 ●●●●●●●●●●●●●● ●●● ● ● ● ●●●●● ●● ●● ●●●
●●● duration of the occurrences Tep ( gure 5), and the minimal support threshold Smin ( gure 6). Table 3 details the experimental settings, and we observe the size of the lattice (sub gures (a)), the length of the RMN list (sub gures (b)), the precision (sub gures (c)) and recall (sub gures (d)). For each evaluation metric, we plot the boxplot representing the distribution of the measures throughout the processing of the dataset.
For every setting, the size of the lattice and RMN list remains mostly stable throughout the execution. The variations are linked to the varying event densities, but not to the size of the history. Both precision and recall are usually very close to 100%, with occasional lower values. The performance in terms of precision and recall do not seem signi cantly in uenced by the parameters investigated. However, the resources required for the processing and mining of the dataset are: longer windows, longer episodes durations and lower support thresholds result in a higher number of interesting episodes and thus increase the size of the lattice. The e ciency of the RMN list for the reduction of the search space for the monitoring of new occurrences is directly related to the maximal duration of the considered occurrences, and is thus the main scalability limit. 6
In this paper, we introduce FEM-ASC, an algorithm for the discovery and the monitoring of frequent episodes in a stream of events. If its heuristic construction o ers no guaranty on the quality of the approximated support, it shows in practice good results on real-life datasets with progressive distribution changes.
This work is however simply at an early development stage, and requires further experimentation. The two strategies for the removal of outdated nodes need to be thoroughly compared. The performances of FEM-ASC should also be assessed in di erent contexts, and in the presence of di erent kinds of concept drifts. The in uence of SSmsuibn should also be assessed on both the scalability, the recall, and the reaction speed to concept drifts.
Acknowledgement. This work is supported by the NanoSTIMA Project: Macroto-Nano Human Sensing: Towards Integrated Multimodal Health Monitoring and Analytics/NORTE-01-0145-FEDER-000016 which is nanced by the North Portugal Regional Operational Programme (NORTE 2020), under the PORTUGAL 2020 Partnership Agreement, and through the European Regional Development Fund (ERDF)