Recent advances in sensing techniques enabled the possibility to gain precise information about switched-on devices in smart home environments. One is particularly interested in exploring di erent patterns of electrical usage of indoor appliances and using them to predict activities. This in turns results with many useful applications like inferring e ective energy saving procedures. The necessity to derive this knowledge in the real time and the huge size of generated data initiated the need for a precise stream sequential pattern mining approach. Most available approaches are less accurate due to their batch-based nature. We present a smart home application of the PBuilder algorithm which uses a batch-free approach to mine sequential patterns of a real dataset collected from appliances. Additionally, we present the StrPMiner which uses the PBuilder to nd sequential patterns within multiple streams. We show through an extensive evaluation over a smart home real dataset the superiority of the StrPMiner algorithm over a state-of-the-art approach.
Careful usage of indoor electrical devices is an important topic in the eld of energy saving and sustainability. Understanding the usage patterns of appliances during a typical day is the key to induce savings of electrical energy. If a domain expert nds anomalies in the electricity usage of one house, which consumes a lot of energy, he can help the householder by suggesting lesser consuming patterns. Recent advances in sensing techniques enabled the possibility to gain precise information about di erent switched-on devices in a smart home environment. This information contains the time and the duration when a particular appliance was turned on. Gaining knowledge about correlation patterns between the activation of di erent devices is possible with an o ine visualization of a smallsized data collected from a limited number of appliances (cf. Figure 1). This tends to be sophisticated when one requires an instant knowledge about the usage needed during the collection time. Additionally, the number of devices and even the houses should usually be big enough to gain useful patterns. This signals the necessity to apply data mining methods to collect handy usage patterns.
A data stream produces an in nite and continuous ow of data. Regularities can often be found in those streams, which give information about the connection between the events in the data. To nd this hidden information, sequential pattern mining algorithms can be used over the data stream. A suitable algorithm is able to reveal electric devices that are often used with or implied by each other. Sequential pattern mining is a special case of frequent item set mining, where patterns have to be frequent subsequences of the stream. Each pattern has to appear a certain number of times within a part of the stream (called batch) to count as a sequential pattern.
Additional challenges arise when looking at multiple streams at once, as patterns can be part of one or multiple streams. This is the case in a smart home environment, as each electric device provides a di erent data stream, feeding us with new information. For this a special treatment of data is needed, so that a useful connection among multiple electric devices can be found.
Coffee machine
Alarm
TV Light
Multiple algorithms were proposed in the literature to mine sequential
patterns from data streams. Most of them use a batch approach, like the SS-BE
algorithm [
In this work, we present an application over a real smart home dataset using
two algorithms [
The remainder of this paper is organized as follows: Section 2 presents some related work. Section 3 looks at the preliminaries of sequential pattern mining. Additionally it will highlight the problem with the batch approach. In Section 4 two algorithms are presented. The algorithm StrPMiner is then tested against the SS-BE algorithm in Section 5, where we will also prove its superior accuracy. The paper is concluded with a summary and an outlook in Section 6. 2
Optimizing sequential pattern mining is an important task in the streaming data
mining eld, which leads to a lot of di erent algorithms. A base algorithm for
many approaches [
Since the streaming approach allows to only look at data once, algorithms
have to make compromises in order to provide fast results. [
In a static data set, all information needed for the algorithm is provided from
the beginning, while in the streaming approach new data arrives every second,
thus, patterns that were not frequent in the beginning may become frequent later
on. Yet, it is impossible to save every pattern and its information. The FP-stream
[
The algorithms mentioned above only provide solutions for frequent pattern
mining or nd sequential patterns by using batches. The stream pattern miner
(StrPMiner) algorithm which uses the PBuilder was rst introduced in [
We are given a set S = fS1; S2; : : : ; SjSjg of jSj di erent streams arriving from di erent observed parameters collected from the smart home. Each stream Sk is represented by streaming, time-stamped interval-based events that evolve over the time. Thus, the rst n items of stream Sk are represented as Sk = fs1k; s2k; : : : ; skng where sik is an observed event that occurs at time ti where ti < t(i+1) for all i = 1; : : : ; n. Each event is additionally described by its label. A sequential pattern is a combination of multiple events that follow each other. These patterns can be used to nd correlations in the data.
We are asked to obtain the di erent frequent patterns that appear within a single stream Sk and also within multiple streams from S (also called multimodal streams). The sequential pattern mining problem di ers from the normal frequent item set mining in the fact that the order of items (events) matters. The problem of mining sequential patterns is de ned as follows: Let I = fi1; i2; : : : ; ijIjg be a set of jIj items, each item consists of a timestamp and a duration. A pattern is represented here by a sequence, which is an ordered list of items from I denoted by hp1; p2; : : : ; pki. Thus, a sequence p = ha1; a2; : : : ; aqi is a subsequence of a sequence p0 = hb1; b2; : : : ; bri if there exists integers i1 < i2 < < iq such that a1 = bi1 ; a2 = bi2 ; : : : ; aq = biq .
This de nition of sequential pattern mining is very feasible for the continuously emerging characteristics of stream data. A stream Sk in this context is an arbitrarily large list of sequences pi. A sequence p in the data stream Sk contains another sequence p0 from Sk if p0 is a subsequence of p. The count of a sequence p, denoted as count(p), is de ned by the number of sequences that contain p in the stream Sk. If the frequency of a pattern (p) within a window w of the stream Sk is greater or equal to a user de ned threshold min supp, then the sequence p is a frequent sequence or a sequential pattern in that window of Sk.
Following the apriori principle [
To provide di erent views on the data, three di erent window concepts are used by the StrPMiner. The algorithm works with the Landmark Window, the Sliding Window and the Damped Window concept. In the Landmark Window, a point in time is de ned as the landmark. All data is then collected starting from the landmark. This concept allows to look at big parts of the data. The Sliding Window concept uses a xed window size and slides it over the data. Thus, only a snapshot of the data will be monitored at any given time. An advantage is that old patterns will be forgotten eventually, which leaves only current information. The Damped Window weights the objects to re ect their age. New items will be more important than old ones. This allows a compromise between the Landmark Window and the Sliding Window concept. A good solution to nd sequential patterns in a streaming environment is the batch approach. It allows to use the Apriori principle, since each batch provides a static data set. However it comes at a cost. Given a support threshold of 2, meaning a pattern has to appear two times within one batch to be counted as frequent, a batch size of 3 and following sequence: (A; B; C; A; C; C; A; D; C; A:::) with A, B, C, D being items of a stream. The online component would cut the data stream in following batches: 1. (A, B, C ) 2. (A, C, C ) 3. (A, D, C ) 4. (A, ...) 5. ...
In this case, no pattern would be frequent. Looking at the whole data without cutting it into batches would reveal that the pattern C; A appears three times, which is over the support threshold of 2. This would lead to a frequent pattern. Additionally, all items except for C in the second batch, would be pruned away, although the item A and C appear in every batch. This leads to two reasons for errors through the batch approach: First: Patterns that appear between batches will not be found. Second: Items and patterns that do not appear often in one batch will be pruned, although they are frequent in the whole data set. The StrPMiner was designed to avoid the batch approach because of these two reasons which result into false statistics for sequential patterns. 4
Since the Pre xSpan algorithm only scales well when the candidates for sequential patterns can be pruned, the StrPMiner reverses the idea of the Pre xSpan and uses a new algorithm called the Pattern Builder (PBuilder ). This allows the StrPMiner to work on each data item step by step as it comes in.
To provide a more focused view on the order of the items, the de nition of sequential patterns was changed slightly. As stated previously, a sequential pattern is a frequent subsequence. We rede ne subsequences, and sequential patterns, as only allowed to be a list of ordered items that directly follow each other. Thus, p is considered a subsequence of q if p = (p1; p2; :::; pn), q = (q1; q2; :::; qm) and there exist integers i1 < i2 < ::: < im such that p1 = qi1 ; p2 = qi2 ; :::; pn = qin for n < m and for all k; l with l; k < m and l = k + 1.
The StrPMiner handles arriving data from multiple streams at once. For this, we assume that at each point in time only one item can arrive per stream. If multiple items from multiple streams arrive at the same time, they will be put into an ordered list and the algorithm handles each item after another. First an item will be compressed, as only the label and the timestamp are relevant for creating sequential patterns. Then the StrPMiner passes the item to the PBuilder. The PBuilder then uses this data to create sequential pattern candidates. After this, the StrPMiner saves the candidates in the T0 tree structure and keeps track of those candidates and their corresponding statistics. Currently this is the count value, which allows to calculate the support and con dence value of a pattern. The tree will be updated with the new count values and if a pattern was not part of the tree a new node will be created. This approach allows full accuracy, and exibility in the output, as the support threshold can be changed at every output request. This is not possible when using the Pre xSpan, since the threshold has to be previously set. 4.1
The PBuilder The PBuilder creates only patterns that contain the newly arrived item. Since it is the last arrived item, all created patterns will end with this item. Given an item A as the newly arrived item, the PBuilder starts with this item as a pattern of length one. After this, the algorithm recursively adds older items as a pre x to the previously created post x. To ensure that the StrPMiner only nds direct sequential patterns, the pre x is a direct predecessor of the post x. As visible in the pseudocode, visible in Agorithm 1, the ItemList only contains the latest items ordered by their appearance. The newest item is the last item in the list. In the rst iteration, the currentPattern parameter is empty. Line 7 will then recursively add a pre x to our current pattern. The resulting pattern will be inserted into the tree, as visible in Line 9. This will be repeated, until the complete ItemList was included.
For each created pattern, the PBuilder algorithm calls the update function of the T0 tree. An example of the tree can be seen in Figure 2.
8 9 10 end
Algorithm 1: The PBuilder explained with pseudo code 1 PBuilder
Data: ItemList, currentPattern 2 //ItemList contains the latest compressed items and is limited by maxPatternLength. The newly arrived item is at the last position
Result: The new patterns that can be created with the new item 3 int index = ItemList.length; 4 //create patterns until maxPatternLength is reached 5 while currentPattern.length ItemList.length do 6 //add the next item to the pattern 7 currentPattern = ItemList.get(index-currentPattern.length) + currentPattern; //update the tree with the new pattern updateTree(currentPattern); 4.2
Maximum Pattern Length as a Solution for Exponential Growth In contrast to a static database, where all information is available from the beginning, the streaming approach does not have any information on what future items and their frequency might look like. This means that any item and pattern that is currently not frequent in a stream, can become frequent at any later point in time. The support of every pattern changes with every new arriving item. To ensure that at every time the user requests an output all sequential patterns are part of the output, every possible pattern and its information have to be saved. This causes an exponential increase of the calculation time, as with every new arriving item more patterns can be created. Additionally, the memory space will eventually collapse, as the amount of data that has to be saved also increases exponentially.
To stop the exponential growth, the StrPMiner introduces a parameter called maxPatternLength, as an upper Bound for the pattern length. This variable restricts the PBuilder to only look at the last maxPatternLength items. A maxPatternLength of ve, will cause patterns to maximally contain ve items, as only those are given to the algorithm. Given this bound, the calculation time in each step only scales with the size of the maxPatternLength parameter. Additionally this parameter bounds the maximum growth of the required memory space. On the one hand, as the parameter will not change over the time, the calculation time for each new arriving item will be constant. On the other hand this upper bound lters patterns, before they have been created. Sequential patterns that have a length higher than the given bound, will not be found. With this in mind, a careful selection of the upper bound is important, as it provides a trade o between the calculation time and accuracy. 4.3
Di erent Window Models
As previously mentioned, the StrPMiner uses the T0 tree introduced by [
The sliding window model helps to provide another view on the data, as it only contains knowledge of recent data and forgets old data. This helps in cases, where the data changes drastically over the duration of the stream. The landmark window would still show old patterns even though they did not reappear for a long time. In general, the whole algorithm works the same, as in the landmark window, except for an extra pruning step. For this the time stamp of the corresponding item and the patterns created with it have to be deleted from the T0 tree, which is one path. 5
Because of the problems that come with the batch approach, the StrPMiner, unlike the SS-BE algorithm, does not use the Pre xSpan. Instead it uses the PBuilder, which handles each newly arriving item immediately, without using the batch approach. In this section we compare the presented algorithm to the SS-BE, since it is a current state of the art algorithm that nds sequential patterns in a stream environment. Other algorithms we looked at did not ful ll both of these criteria.
For the experimental evaluation of both algorithms we used the REDD
dataset [
Since we are only interested of direct sequential patterns, we adapted the Pre xSpan in such a way that it will only create direct sequential patterns. The adaption will additionally e ect the results output by the SS-BE algorithm, as it is dependent on the results produced by the Pre xSpan.
The support threshold, the only parameter used by both algorithms, was set to 1%.
For the StrPMiner we set the maximum pattern length at 200. As explained in 4.2, this parameter strongly in uences the patterns that we nd and our runtime. The runtime of the StrPMiner is slower than the runtime of the SS-BE, but with this parameter setting we still ensure real time results. Our assumption is, that, with this setting, the PBuilder will nd every pattern that is shorter than 200. This result into full accuracy for those patterns. In this evaluation we only want to look at the strong accuracy of the StrPMiner, we will only use the Landmark Window here. The Sliding Window and the Damped Window show similar results.
The parameters we set for the SS-BE algorithm were the signi cance
threshold with 0:0099 and the pruning period to 10. Those settings are close to
those used by the authors [
In a rst evaluation we compared both algorithms against a ground truth, which contains all patterns with a support of at least 1%. As the SS-BE algorithm uses the batch approach, an output can only be generated after batch (a) Comparing each time stamp.
(b) The evaluated time stamps were binned and then compared.
Fig. 3. A comparison of the StrPMiner to the SS-BE algorithm after evaluating one house. The y-axis displays the accuracy, while the x-axis shows the time. The batch length was set to 200. length amount of items were evaluated. This means in our case, that only after each 200 or 300 items, an output is available. In contrast to this, the StrPMiner can produce a valid output after each item, as it will treat each item directly. In Figure 3 we compared the result of both algorithms to the output after each 200 items. Additionally another comparison is created, where we bin the single time steps. As visible in this gure, the StrPMiner has a signi cantly higher accuracy, which is 30% points higher at each single time step for the given data. Two other things are also visible in this gure. First, the accuracy of the StrPMiner stays 100% for the rst few time steps, as long as there are no frequent patterns found with a higher length than 200. Second, there is a noticeable drop in the accuracy during the rst third of the evaluation. A closer look into the data reveals, that during this time the amount of patterns, that have a higher length than 200, is rising. But, all of those patterns are single stream patterns, with a switching on and o event of one single device, happening in a few seconds. The binning is used to smooth out those abrupt changes and provide a focused view on the general direction of the results.
Although the accuracy of the SS-BE algorithm rises with a higher batch length, all three observations are still visible in Figure 4. We tested the algorithms against multiple houses, in which the accuracy of the algorithms changed slightly, but the general direction was the same, revealing the higher accuracy of the StrPMiner. In houses with less noisy data, we were even able to maintain full accuracy with the StrPMiner, as there were no frequent patterns with a high batch length.
In most of the evaluation the higher batch length setting shows to be more accurate, but still has a lower accuracy of nearly 20% points.
In a next step we wanted to prove our assumption. Only looking at the most important patterns, meaning the top 100 patterns with the highest support, reveals that the PBuilder has a full accuracy for all patterns with a length lower than the maximum pattern length. A comparison to the SS-BE algorithm is visible in Figure 5. This gure shows, how many of the hidden patterns in the data could be found. In this case, the SS-BE algorithm has a high accuracy of over 90%, but is still beaten by the full accuracy of the StrPMiner.
Taking a closer look at the order of the top 100 reveals, that, due to the full accuracy, the StrPMiner is able to show all important patterns in the correct order, sorted by their support value. The SS-BE algorithm is not able to keep the correct position of the patterns. Figure 6 shows the deviation of the patterns at each time step. The gure shows the mean deviation over all patterns, and the maximal deviation of one pattern.
Although these results show the higher accuracy for the StrPMiner, they only represent the average case, formed by looking at all patterns. The open question is, how can these results help in an application case, where we want to nd and keep track of speci c interesting patterns? The open assumption we want to test is, that both algorithms are able to nd meaningful patterns. This means, patterns that show an existing connection between the items contained in it. To test this assumption, we created a correlation matrix for the devices in the data set. A snapshot of it is shown in Table 1, which gives information about how often the items were turned on or o together. A higher value means that the on and o time of those two items is close to each other. With this correlation matrix we may not gain information about the speci cs of the connection of two items, but we can safely say, that there is a connection between those items. (a) (b) (a) The deviation for a batch length of 200 (b) The deviation for a batch length of 300 reaches up to 60. reaches only to 20.
This is also re ected in the results of the StrPMiner, as patterns between two items with a high correlation, are the multimodal patterns with the highest support. Item combinations with a correlation of over 0.6 are part of the frequent patterns. These patterns, like oven 3+, oven 4+ and oven 3-, oven 4- show that both items are often used with each other. Six of those multimodal patterns have a higher support than 1% in the ground truth and can be found with full accuracy in the results of the StrPMiner. In contrast to this, the SS-BE algorithm can nd three of those with an error rate of over 5%. The other 3 items are not part of the results at all, as they were pruned out of lost between batches of SS-BE. 6
In this paper we have presented a smart home application over a recent
algorithm, the PBuilder [
In the future we plan to improve the time e ciency of our algorithm.
Although our algorithm is able to calculate the results in real time, it is slower
than the SS-BE algorithm. We found the bottleneck in the insertion step of the
data into the T0 tree. First changes could improve the runtime signi cantly. We
would like additionally to test our approach in distributed, multi-source sensor
streaming environments [