# An Asynchronous Periodic Sequential Pattern Mining Algorithm with Multiple Minimum Item Supports for Ad Hoc Networking

Authors: Xiangzhan Yu; Zhaoxin Zhang; Haining Yu; Feng Jiang; Wen Ji
Journal: Journal of Sensors
 (2015)

---

## Abstract

The original sequential pattern mining model only considers occurrence frequencies of sequential patterns, disregarding their occurrence periodicity. We propose an asynchronous periodic sequential pattern mining model to discover the sequential patterns that not only occur frequently but also appear periodically. For this mining model, we propose a pattern-growth mining algorithm to mine asynchronous periodic sequential patterns with multiple minimum item supports. This algorithm employs a divide-and-conquer strategy to mine asynchronous periodic sequential patterns in a depth-first manner recursively. We describe the process of algorithm realization and demonstrate the efficiency and stability of the algorithm through experimental results.


---

## Body

## 1. Introduction

Ad hoc networking has become a hot issue recently as large-scale nodes exhibit in the network. Heterogeneous devices and heterogeneous environments deepen the difficulty of ad hoc networking. The sequential pattern mining model is used to discover all sequential patterns that occur frequently in a sequence database; the target database is shown in Table1. The spatiotemporal sequence mining model is used to discover all frequent spatiotemporal sequential patterns in a spatiotemporal sequence database; the target database is depicted in Table 2. The periodic pattern mining model is used to discover all periodic patterns in a temporal sequence database; the target database is shown in Table 3.Table 1
Symbolic sequence database.
ID
Sequence
0
a
(
a
b
c
)
(
a
c
)
d
(
c
f
)
1
(
a
d
)
c
(
b
c
)
(
a
e
)
2
(
e
f
)
(
a
b
)
(
d
f
)
c
b
3
e
g
(
a
f
)
c
b
cTable 2
Spatiotemporal sequence database.
ID
Sequence
0
a
t
0
a
b
c
t
1
a
c
t
2
d
t
3
c
f
t
4
1
a
d
t
0
c
t
1
b
c
t
2
a
e
t
3
2
e
f
t
0
a
b
t
1
d
f
t
2
c
t
3
b
t
4
3
e
t
0
g
t
1
a
f
t
2
c
t
3
b
t
4
c
t
5Table 3
Temporal sequence database.
Temporal sequence
a
t
00
a
b
c
t
01
a
c
t
02
d
t
03
c
f
t
04
a
d
t
10
c
t
11
b
c
t
12
a
e
t
13
e
f
t
20
a
b
t
21
d
f
t
22
c
t
23
b
t
24
e
t
30
g
t
31
a
f
t
32
c
t
33
b
t
34
c
t
35According to the three mining models, the time property of a sequence can be divided into two levels.(
1
) Fine-grained time property is as follows: the fine-grained time property is used to annotate each item set of each sequence, such as the subscript t
i of every item set in Table 4. (
2
) Coarse-grained time property is as follows: the coarse-grained time property is used to annotate each sequence, such astid in Table 4. The fine-grained time property is a further division of the coarse-grained time property. The sequential pattern mining model only uses the fine-grained time property to sort items and ignores the coarse-grained time property of a sequence. The fine-grained time property is utilized in the spatiotemporal sequence mining model. This model uses the temporal annotation as a criterion to judge whether two sequences are equal, and deviations of the annotation can be tolerated. Nevertheless, both models only concentrate on the frequency of sequences but ignore the characteristics of the distribution of sequences in a database. The periodic pattern mining model takes the fine-grained time property as a criterion to discover periodic patterns, and it uses periodic patterns within the fine-grained time property to calculate the patterns within the coarse-grained time property. However, the restrictions of the temporal annotations of item sets are too strict (the fine-grained time property should be divided into unit time intervals); besides, frequent deviations of annotations of item sets would not be permitted while mining. In addition, a myriad of sparse periodic patterns with little meaning will be generated by the periodic pattern mining model when the time series is sparse.Table 4
Fine and coarse grained temporally annotated sequence database.
tid
Sequences with temporal annotations
t
i
d
0
a
t
0
a
b
c
t
1
a
c
t
2
d
t
3
c
f
t
4
t
i
d
1
a
d
t
0
c
t
1
b
c
t
2
a
e
t
3
t
i
d
2
e
f
t
0
a
b
t
1
d
f
t
2
c
t
3
b
t
4
t
i
d
3
e
t
0
g
t
1
a
f
t
2
c
t
3
b
t
4
c
t
5The original sequential pattern mining model only considers the occurrence frequencies of sequential patterns and disregards their occurrence periodicity. Therefore, we propose an asynchronous periodic sequential pattern mining model, and, for this model, we propose a pattern-growth mining algorithm to mine asynchronous periodic sequential patterns with multiple minimum supports. The algorithm is a recursive algorithm that uses a divide-and-conquer strategy to mine the patterns, and the search is depth-first.The remainder of this paper is organized as follows. Section2 gives a brief overview of recent related research on sequential pattern mining and periodic sequential pattern mining. In Section 3, definitions of related concepts are introduced. In Section 4, the asynchronous and synchronous periodic sequential pattern mining models are presented. Section 5 proposes a pattern-growth mining algorithm to mine asynchronous periodic sequential patterns with multiple minimum item supports. In Section 6, the experimental results show the efficiency and stability of the algorithm. We present the conclusions of our study in Section 7.


## 2. Related Work

Traditional sequential pattern mining algorithms, such as FreeSpan, PrefixSpan [1], and SPADE [2], discover frequent subsequences as patterns in a sequence database. These traditional algorithms are described in detail in [3]. A spatiotemporal sequence mining algorithm is a special type of sequence mining algorithm. Deviations of temporal annotation and spatial location of a sequence should be considered in this method. In [4], a spatiotemporal sequence mining algorithm based on PrefixSpan is proposed. In this algorithm, temporal annotations not only are used to sort the location or status but also are involved in mining the spatiotemporal sequence directly. However, the complexity of the algorithm would increase dramatically as the spatial dimension aggrandizes.Traditional periodic pattern mining algorithms discover periodic patterns in time-related databases, and these algorithms can be divided into several categories as follows by different characteristics:(1)
the full periodic pattern mining method and partial periodic pattern mining method: full periodic patterns [5] are those in which all items of the time series take part in the periodic behaviour patterns, whereas there are almost no such patterns due to fairly strict constraints; in partial periodic patterns [6], only a portion of the items of the time series reflects the periodicity; compared with full periodic patterns, partial periodic patterns are more loose and realistic;
(2)
the synchronous periodic pattern mining method and asynchronous periodic pattern mining method: synchronous periodic patterns [6] are those in which if one pattern appears at time t
i, it would definitely appear at t
i
+
p
e
r
i
o
d
∗
n (n
>
0), where period represents the length of the period, and the patterns, which do not happen at such fixed times, would be taken as irrelevant patterns; asynchronous periodic patterns [7] are those in which if one pattern appears at time t
i, instead of just taking place at t
i
+
p
e
r
i
o
d
∗
n (n
>
0), the pattern would appear at any time of the time series; synchronous periodic patterns are a special case of asynchronous periodic patterns, and the latter is more realistic.The full periodic pattern mining method has been widely studied in the field of signal analysis. Fast Fourier transforms and Wavelet analysis are often used to find the full periodic patterns in time series data. In [8], a partial periodic pattern mining algorithm based on the downward closure property is proposed. To improve efficiency, this algorithm builds a max-subpattern tree to separate partial periodic patterns. The authors in [9] proposed a convolution-based algorithm employing the improved fast Fourier transform to mine the partial periodic patterns and discover all possible synchronous periodic patterns. Time series are divided into intensive intervals in [10], and then the synchronous periodic patterns are mined. [7, 11] propose an asynchronous periodic sequential pattern mining algorithm called LSI to find the longest periodic subsequence, in which some sequences whose lengths are less than the threshold value can exist. However, the algorithm is not suitable for the condition of multievents, and only the longest subsequence of the asynchronous periodic patterns can be found, with other subsequences being ignored. Aiming to address these shortcomings, an improved algorithm, SMCA, based on a hash table and enumeration, is proposed by [12]. This algorithm not only implements all functions of LSI but also corrects the defects and improves the efficiency. Reference [13] proposes an algorithm for mining periodic patterns that utilizes the method of [3] to preprocess trajectory sequences and uses the max-subpattern tree proposed by [8] to discover periodic patterns. Reference [14] proposes a method to mine periodic-frequent item sets with approximate periodicity using an interval transaction-ids list tree, and it is extended by [15] to fulfill the requirement of mining periodic-frequent patterns in transactional databases. Reference [16] proposes a HACE theorem that characterizes the features of the Big Data revolution and proposes a Big Data processing model, from the data mining perspective. This data-driven model involves demand-driven aggregation of information sources, mining and analysis, user interest modeling, and security and privacy considerations. Reference [17] proposes a trajectory prediction approach for mobile objects by combining semantic features through pattern mining in the geographic trajectory data of user. Reference [18] focuses on dynamic networks to study the related pattern mining method and its applications in biological and social networks. Reference [19] proposes a pattern mining algorithm which is called Multiconstraint Closure Conditional Tree. The algorithm sets different limiting conditions to solve the combinatorial explosion problem and the rare item problem. And, to prevent noise and other uncertainties, this paper introduces similarity-based pattern matching method, making the pattern mining method more robust.


## 3. Basic Concept and Definition

Before talking about the asynchronous periodic sequential pattern mining algorithm, some basic concepts will be defined.At first, we assume thatI
=
{
i
1
,
i
2
,
…
i
n
} is the set of all items, and each item is the nonempty subset of I. A sequence is a sequential list of item sets, and it can be expressed as s
=
s
1
,
s
2
,
…
,
s
l, where s
j is an item set and also en element of s, which can be expressed as s
j
=
(
x
1
,
x
2
,
…
,
x
m
), where x
k is an item. To simplify the expression, the parentheses can be omitted if an item only consists of one element; for example, “(x)” can be expressed as “x.” One item can appear merely once or less in one element of a sequence, but more than one item can exist in different elements of a sequence. In general, the elements are sorted lexically, and the number of elements is the length of the sequence. A sequence of length l is called an l-sequence.The target database of asynchronous periodic sequential pattern mining is defined as follows.Definition 1 (temporal symbolic sequence database).
The temporal symbolic sequence database is a set of tuples; that is,TDB = {
t
0
,
t
1
,
…
t
T
D
B
-
1
}, where T
D
B is the number of tuples and t
i represents the tuple (
t
i
d
,
s
), wheretid is the time when symbolic sequence s takes place. In general, tuples ofTDB are sorted in ascending order, and eachtid is evenly spaced. Figure 1 shows a temporal symbolic sequence that consists of 23 tuples.Figure 1
Temporal symbolic sequence database.Definition 2 (subsequence and supersequence).
Sequenceα
=
〈
a
1
a
2
⋯
a
n
〉 is a subsequence of sequence β
=
〈
b
1
b
2
⋯
b
m
〉, and β is the supersequence of α, which can be expressed as α
⊑
β if there exists a set of integers 1
≤
j
1
<
j
2
<
⋯
<
j
n
≤
m, where a
1
⊆
b
j
1 and a
2
⊆
b
j
2
,
…
,
a
n
⊆
b
j
n.Definition 3 (containment and appearance).
t
′
=
(
t
i
d
′
,
s
′
) is one of the tuples ofTDB, and α is a sequence. We can say that t
′ contains α or α appears at t
′ only if α is a subsequence of s
′.For instance, as is shown in Figure1, 〈
(
a
b
)
a
d
f
〉 appears at the tuple (0, 〈
a(abc)(ac)d(cf)〉).Definition 4 (prefix).
Sequenceβ
=
e
1
′
e
2
′
⋯
e
m
′ is the prefix of sequence α
=
e
1
e
2
⋯
e
n (m
≤
n) only if these three requirements are all met: (i) e
i
′
=
e
i, where (i
≤
m
-
1). (ii) e
m
′
⊆
e
m. (iii) All items of e
m
-
e
m
′ are after e
m
′ by lexicographic order.Definition 5 (postfix).
Sequenceβ
=
e
1
e
2
⋯
e
m
-
1
e
m
′ is the prefix of sequence α
=
e
1
e
2
⋯
e
n (m
≤
n), and sequence γ
=
e
m
′′
e
m
+
1
⋯
e
n is called the postfix of α with regard to prefix β, denoted as γ
=
α
/
β or α
=
β
·
γ, where e
m
′′
=
e
m
-
e
m
′.Definition 6 (periodic projected database).
Construct a temporal symbolic sequence databaseTDB, and specify a preset parameter of maximum periodmax_per,max_per
≪(t
i
d
f
-
t
i
d
l), wheretid
f is the first time stamp ofTDB andtid
l is the last time stamp. The periodic projected data ofTDB that starts at time l with a period p is composed by the tuple (t
i
d
l
+
i
∗
p, s
l
+
i
∗
p) (0
≤
i
≤
m), where l
<
p, 1 ≤p ≤max_per, and m
=
⌈
(
t
i
d
l
-
l
)
/
p
⌉, and these data can be expressed as p
r
j
p
,
l
(
T
D
B
).For instance, as is shown in Figure1, the tuples ofprj
3,1(TDB) are as follows: 1: (
b
d
)
c
(
b
c
)
(
a
d
), 4: b
c
(
b
c
)
(
a
d
), 7: c
(
b
c
)
a
b
(
a
b
d
), 10: a
c
(
a
b
c
)
(
a
d
), 13: (
a
c
)
(
a
b
e
)
c
b, 16: (
c
e
f
)
a
(
a
b
)
d
d
b, and 19: b
(
a
c
)
(
a
b
d
).Definition 7 (prefix projected databases).
If sequenceα is an asynchronous periodic sequential pattern inTDB, then the prefix projected database is the subdatabase that is composed of all of the prefixes of α with regard to the postfix of α, denoted as S
α.Definition 8 (contained segments).
Sequenceα with a period of p inTBD contains a segmentL, which is a time list including consecutive tuples of α in p
r
j
p
,
l
(
T
D
B
), where the timestamp l is the remainder of the division of the starting position by p. The contained segment L consists of a quaternion (α, p, r
e
p, b
e
g
i
n), where α is the target sequence,p is the period,rep is the number of times in which α appears, andbegin is the starting position where the repeated appearance of α starts.L can be called the maximum contained segment if α is not contained in the two directions ofL.As is shown in Figure1, the maximum contained segment L
2 is expressed as (〈
a
(
a
b
)
〉, 3, 5, 7), which means that 〈
a
(
a
b
)
〉 starts attid 7 and appears repeatedly a total of 5 times with a period of 3 and thetids at which 〈
a
(
a
b
)
〉 appears are 7, 10, 13, 16, and 19. Similarly, L
1 is expressed as (〈
a
(
a
b
)
〉, 3, 3, 0), L
3 is expressed as (〈
a
(
a
b
)
〉, 3, 3, 14), and both of them are the maximum contained segments with a period of 3.Definition 9 (valid contain segments).
A maximum contained segmentL
=
(
α
,
p
,
r
e
p
,
b
e
g
i
n
) is valid only if the repeat count of L is not less thanmin_rep; that is,L.rep ≥min_rep.As is shown in Figure1, we assume thatmin_rep = 3; then, the maximum contained segments L
1, L
2, and L
3 are the valid contained segments of 〈
a
(
a
b
)
〉 with a period of 3 because the repeat counts of L
1, L
2, and L
3 are 3, 5, and 3, respectively, which are not less than 3.Definition 10 (distance between contained segments).
Given two contained segments,L and L
′ (L.begin < L
′
.begin), the distance,dis, between them is the difference between the starting time of L
′ and the ending time of L; that is,dis = L
′
.begin − [L
.
b
e
g
i
n
+
p
∗
(
L
.
r
e
p
-
1
)]. Ifdis < 0, we can say that L and L
′ intersect; otherwise, they do not.As is shown in Figure1, the distance between L and L
′ is 1 (7
-
6), the distance between L
1 and L
3 is 8 (14
-
6), and the distance between L
2 and L
3 is −5 (14
-
19). Therefore, we can safely draw the conclusions that (L
1, L
2) and (L
1, L
3) are not intersecting, while (L
2, L
3) is intersecting.Definition 11 (sequences of contained segments).
The sequence of contained segments is the sequence that meets the following requirements: (i) contained segments come from the same database and are of the same sequence with the same period; (ii) contained segments must be valid; (iii) contained segments are sorted by increasing starting time; (iv) any two contained segments are not intersecting. The sequence of contained segments of sequenceα with a period of p can be expressed as follows:(1)
Q
p
α
=
L
1
→
d
i
s
1
L
2
→
d
i
s
2
,
…
,
→
d
i
s
n
-
1
L
n
,where L
i is a valid segment, L
i
.
b
e
g
i
n
<
L
i
+
1
.
b
e
g
i
n (1
≤
i
≤
n
-
1) and the distancedis
i between two consecutive segments can be expressed by the following equation: d
i
s
i
=
L
i
+
1
.
b
e
g
i
n
-
[
L
i
.
b
e
g
i
n
+
p
∗
(
L
i
.
r
e
p
-
1
)
].Definition 12 (valid sequences of contained segments).
The sequence of contained segmentsQ
p
α
=
L
1
→
d
i
s
1
L
2
→
d
i
s
2
,
…
,
→
d
i
s
n
-
1
L
n is valid whendis
i ≤max_dis
∗
p and ∑
i
=
1
n
L
i
.
r
e
p
≥
m
i
n
_
s
u
p, wheremax_dis indicates the preset maximum distance coefficients andmin_sup is the preset minimum support of the asynchronous period.Figure1 shows that, in the symbolic database, ifmin_rep = 3,max_dis = 3, andmin_sup = 6, then we can say that (L
1
→
L
2) and (L
1
→
L
3) are valid sequences of the contained segments of a
a
b with a period of 3.


## 4. Periodic Sequential Pattern Mining Model

### 4.1. Synchronous Periodic Sequential Pattern Mining Model

In a temporal symbolic sequence databaseTDB, the synchronous periodic support of sequence α with a period p starting attid
l is the number of tuples that α contains. This is shown as follows:(2)
support
T
D
B
p
,
l
α
=
t
i
d
,
s
∣
t
i
d
,
s
∈
p
r
j
p
,
l
T
D
B
∧
α
⊑
s
.Given a minimum supportmin_sup (0 <min_sup ≤ 1) and a maximum periodmax_per (0 <max_per ≪ T
D
B), sequence α inTBD, which starts at time l, is frequent with the period p if support
T
D
B
p
,
l
α
≥
m
i
n
_
s
u
p and 0 < p ≤max_per. A synchronous periodic-frequent sequence is called a synchronous periodic sequential pattern. The goal of a synchronous periodic sequential pattern mining algorithm is to discover all synchronous periodic sequential patterns whose periods are from 1 tomax_per.


### 4.2. Asynchronous Periodic Sequential Pattern Mining Model

In many applications, the periodicity of a sequence is usually not perfect and precise, and there may exist noise between segments of a sequence. However, only the noise of a “sequential deficiency,” not the noise of a “sequential offset,” can be recognized by this model; as a result, many sequential patterns with high value cannot be discovered. To some degree, the interruption of noise can be tolerated by the periodic sequential mining algorithm. In addition, “system behaviour” occurs repeatedly, and, then, it disappears or changes. The sequential patterns with such uncertainty only appear periodically in a portion ofTDB.Based on the analysis above, this paper proposes an asynchronous periodic sequential pattern mining model that can discover the patterns that appear periodically in various time periods of theTDB; also, certain noise can be tolerated in this model. The main idea of the model is as follows. At first, to judge if a sequence is a potential asynchronous periodic sequential pattern, the sequence must appear repeatedly, which means that this sequence has significant periodic trends. Then, the time interval within which the sequence appears periodically would be examined to determine whether the time interval is “random noise” or “the change of system behaviour.” Finally, on the premise that the noise is tolerated, the time periods at which the sequence appears periodically would be linked to obtain the maximum periodic time range.Concretely, an asynchronous periodic sequential pattern and its mining model are defined as follows.Definition 13 (asynchronous periodic sequential pattern).
Sequenceα is one asynchronous periodic sequential pattern in the temporal symbolic databaseTDB. If there exists more than one valid sequence of contained segments relating to α, then the period of such sequences is that of α. It is not difficult to find that one asynchronous periodic sequential pattern may have several periods, and each period may involve several valid sequences of contained segments.Definition 14 (asynchronous periodic sequential pattern mining model).
Given the minimum support, the maximum distance coefficients, the minimum repeat count, and the maximum period, the purpose of asynchronous periodic sequence mining is to discover all asynchronous periodic sequential patterns and their valid sequences of contained segments inTDB.


## 4.1. Synchronous Periodic Sequential Pattern Mining Model

In a temporal symbolic sequence databaseTDB, the synchronous periodic support of sequence α with a period p starting attid
l is the number of tuples that α contains. This is shown as follows:(2)
support
T
D
B
p
,
l
α
=
t
i
d
,
s
∣
t
i
d
,
s
∈
p
r
j
p
,
l
T
D
B
∧
α
⊑
s
.Given a minimum supportmin_sup (0 <min_sup ≤ 1) and a maximum periodmax_per (0 <max_per ≪ T
D
B), sequence α inTBD, which starts at time l, is frequent with the period p if support
T
D
B
p
,
l
α
≥
m
i
n
_
s
u
p and 0 < p ≤max_per. A synchronous periodic-frequent sequence is called a synchronous periodic sequential pattern. The goal of a synchronous periodic sequential pattern mining algorithm is to discover all synchronous periodic sequential patterns whose periods are from 1 tomax_per.


## 4.2. Asynchronous Periodic Sequential Pattern Mining Model

In many applications, the periodicity of a sequence is usually not perfect and precise, and there may exist noise between segments of a sequence. However, only the noise of a “sequential deficiency,” not the noise of a “sequential offset,” can be recognized by this model; as a result, many sequential patterns with high value cannot be discovered. To some degree, the interruption of noise can be tolerated by the periodic sequential mining algorithm. In addition, “system behaviour” occurs repeatedly, and, then, it disappears or changes. The sequential patterns with such uncertainty only appear periodically in a portion ofTDB.Based on the analysis above, this paper proposes an asynchronous periodic sequential pattern mining model that can discover the patterns that appear periodically in various time periods of theTDB; also, certain noise can be tolerated in this model. The main idea of the model is as follows. At first, to judge if a sequence is a potential asynchronous periodic sequential pattern, the sequence must appear repeatedly, which means that this sequence has significant periodic trends. Then, the time interval within which the sequence appears periodically would be examined to determine whether the time interval is “random noise” or “the change of system behaviour.” Finally, on the premise that the noise is tolerated, the time periods at which the sequence appears periodically would be linked to obtain the maximum periodic time range.Concretely, an asynchronous periodic sequential pattern and its mining model are defined as follows.Definition 13 (asynchronous periodic sequential pattern).
Sequenceα is one asynchronous periodic sequential pattern in the temporal symbolic databaseTDB. If there exists more than one valid sequence of contained segments relating to α, then the period of such sequences is that of α. It is not difficult to find that one asynchronous periodic sequential pattern may have several periods, and each period may involve several valid sequences of contained segments.Definition 14 (asynchronous periodic sequential pattern mining model).
Given the minimum support, the maximum distance coefficients, the minimum repeat count, and the maximum period, the purpose of asynchronous periodic sequence mining is to discover all asynchronous periodic sequential patterns and their valid sequences of contained segments inTDB.


## 5. AP-PrefixspanM Mining Algorithm

To use the one and only minimum support, we must assume that all the items in the database have the same properties and a similar frequency of occurrence. However, this assumption conflicts with the actual application situation, which leads to the result that the sequential patterns with few but important items are omitted. A perfect asynchronous periodic sequential pattern mining algorithm should support multiple minimum item supports, which means users can identify each item with minimum support, and different requirements of minimum supports can be met by different sequences with different items. With multiple minimum item supports, not only can we prevent the generation of a myriad of meaningless asynchronous periodic sequential patterns, but we can also discover the sequential patterns with few items.In this paper, we propose a pattern-growth mining algorithm to mine asynchronous periodic sequential patterns with multiple minimum item supports; this algorithm is called AP-PrefixspanM (asynchronous periodic prefix projected sequential patterns with multiple minimum item supports).


### 5.1. Relationship between Algorithm Parameters

LetM
i
n
I
S
(
i
) represent the minimum support of item i. The minimum support of the sequential pattern P is the lowest minimum support of all items of P; for example, if the item set of P is i
1
,
i
2
,
…
,
i
k, then the equation of minimum support of P is(3)
m
i
n
_
s
u
p
P
=
m
i
n
M
i
n
I
S
i
1
,
M
i
n
I
S
i
2
,
…
,
M
i
n
I
S
i
k
.LetM
i
n
R
E
P
(
i
) be the minimum repeat count of item i; the minimum repeat count of P is the lowest repeat count of all items; that is(4)
m
i
n
_
r
e
p
P
=
m
i
n
M
i
n
R
E
P
i
1
,
M
i
n
R
E
P
i
2
,
…
,
M
i
n
R
E
P
i
k
.Additionally, letM
a
x
D
i
s
(
i
) be the maximum interference distance of item i, which represents a reasonable bound of disturbance between two valid sequences of contained segments; the maximum interference distance of P is the largest maximum interference distance of all items; that is(5)
m
a
x
_
d
i
s
P
=
m
a
x
M
a
x
D
i
s
i
1
,
M
a
x
D
i
s
i
2
,
…
,
M
a
x
D
i
s
i
k
.To reduce the workload of user settings, we assume that there is a function relationship between the maximum interference distance, the minimum repeat count, and the minimum support. Specifically, the relationship between the minimum repeat count of itemi, M
i
n
R
E
P
(
i
), and the minimum support of item i, M
i
n
I
S
(
i
), is linear increasing, and it can be expressed as follows:(6)
M
i
n
R
E
P
i
=
λ
∗
M
i
n
I
S
i
(
0
<
λ
≤
1
)
.The relationship between the maximum interference distance of itemi, M
a
x
D
i
s
(
i
), and the minimum support of item i, M
i
n
I
S
(
i
), is exponential decreasing, and it can be expressed as follows:(7)
M
a
x
D
i
s
i
=
η
∗
max
⁡
(
M
i
n
I
S
)
M
i
n
I
S
i
,where η is the preset constant of interference distance and max (MinIS) is the largest minimum support ofMinIS.IfMinIS(i
1) ≤MinIS(i
2) ≤ ⋯ ≤MinIS(i
k), thenMinREP(i
1) ≤MinREP(i
2) ≤ ⋯ ≤MinREP(i
k),MaxDis(i
1) ≥
MaxDis(i
2) ≥ ⋯ ≥MaxDis(i
k).


### 5.2. The Main Idea and Steps of the Algorithm

For the purpose of reducing the search space of asynchronous periodic symbolic sequential pattern mining, the downward closure property is used in the asynchronous periodic sequential pattern mining model with single minimum support.Property (Downward Closure Property). If the sequence α is an asynchronous periodic sequential pattern and its set of valid sequences of contained segments isQSet, then we can say that all the nonempty subsequences of α are also asynchronous periodic sequential patterns, and the set of valid sequences of contained segments of these subsequences is the superset ofQSet.However, because the minimum item support of an asynchronous periodic sequential pattern may be less than its subsequence’s with multiple minimum item supports, the downward closure property cannot be used directly to prune the search space.The main idea of thePrefixspanM algorithm is based on the divide-and-conquer strategy. The problem of asynchronous periodic sequential pattern mining is divided progressively into a series of subproblems that are not intersecting. The framework of database division in thePrefixspanM algorithm is as shown in Figure 2. Two dividing methods can be adopted: (
1
) prune the search space with the downward closure property: at level 1, the database is divided into a series of subdatabases by the minimum support vectors and (
2
) generate asynchronous periodic sequential patterns with pattern-growth: below the second level, the prefix projected database is generated recursively by the prefix.Figure 2
The framework of database division in the AP-PrefixspanM algorithm.Firstly, theAP-PrefixspanM algorithm divides the database based on minimum support vectors. Then, a series of subdatabases are generated and mined by the single minimum support. Each division is based on a frequent item called a key item. The single minimum support utilized is called the minimum support of the key item. The downward closure property will not be destroyed while mining, and the specific splitting steps of data are described as follows.Step 1.
Scan the database TDB and obtain itemx
i, whose real support is at leastMinIS(x
i). Such items x
i are called frequent items, and they are placed in ascending order according to theirMinIS to obtain l
i
s
t
=
x
1
,
x
2
,
…
,
x
n, (x
i
≤
x
i
+
1).Step 2.
The complete set of sequential patterns of asynchronous period inTDB can be divided into the following n mutually disjoint subsets, among which some subsets may be empty: (
1
)
sequential patterns that contain sequencex
1,
(
2
)
sequential patterns that contain sequencex
2 but do not contain x
1,
⋮
(
i
)
sequential patterns that contain sequencex
i but do not contain {
x
1
,
x
2
,
…
,
x
i
-
1
},
⋮
(
n
)
sequential patterns that only containx
n.
DivideTDB by these n subsets, and then mine the n subdatabases to obtain the subsets of these n asynchronous periodic sequential patterns:(
1
)
TDB
1 (key item x
1): delete the infrequent items of tuples and the tuples that do not contain x
1;
(
2
)
TDB
2 (key item x
2): delete the infrequent items of tuples, x
1, and the tuples that do not contain x
2;
⋮
(
i
)
TDB
i (key item x
i): delete the infrequent items of tuples, {
x
1
,
x
2
,
…
,
x
i
-
1
}, and the tuples that do not contain x
i;
⋮
(
n
)
TDB
n (key item x
n): delete all the infrequent items of tuples except for x
n and the tuples that do not contain x
n.Mine the asynchronous periodic sequential patterns in theTDB
i with the minimum support ofMinIS(x
i). This problem can be divided into a series of mutually disjoint subproblems.(1)
Let{
y
1
,
y
2
,
…
,
y
m
} be the complete set of length-l asynchronous periodic sequential patterns inTDB
i, and this complete set can be divided into m mutually disjoint subsets. The subset j (1
≤
j
≤
m) is the set of asynchronous periodic sequential patterns whose prefix is y
j.
(2)
Letα be the asynchronous periodic sequential length-l pattern. {
β
1
,
β
2
,
…
,
β
t
} is the set of asynchronous periodic sequential patterns whose prefix is α and length is l
+
1. Apart from α, the complete set of asynchronous periodic sequential patterns whose prefix is α can be divided into k mutually disjoint subsets. The subsetk (1
≤
k
≤
t) is the subset of asynchronous periodic sequential patterns whose prefix is β
k, as is shown in Figure 3.Figure 3
Division of a subset of asynchronous periodic sequential patterns.Based on the descriptions above, the problem of asynchronous periodic sequential pattern mining can be divided recursively, which suggests that each subset can be further divided. Thus, a divide-and-conquer framework is composed. To mine the subsets of asynchronous periodic sequential patterns, we can construct corresponding prefix projected databases and mine each database recursively. The main step is shown as follows:Step 1 (generate parameters).
RegardingMinIs as the minimum support vector, generate the minimum repeat count vector,MinREP, and the maximum interface distance vector,MaxDis.Step 2 (find the length-1 sequential patterns).
Scan the database once and generate all length-1 asynchronous periodic sequential patterns. The length of all patterns will be increased by 1 when the prefix is extended by those length-1 sequential patterns.Step 3 (divide the search space).
Divide the complete set of asynchronous periodic sequential patterns into the subsets whose prefixes are the patterns whose lengths have been increased by 1.Step 4.
Construct the prefix projected databases, and, then, discover the subsets of each asynchronous periodic sequential pattern recursively. Specifically, repeat the steps above until no length-1 asynchronous periodic sequential patterns can be generated.In the mining process described above, only the asynchronous periodic sequential patterns will be added to the mining result. Other patterns will be deleted after mining.


### 5.3. Implementation of the Algorithm

The pseudocode ofAP-PrefixspanM is described in Algorithm 1. Firstly, regardingMinIS as the minimum support vector, generate the minimum repeat countMinREP and the maximum interference distanceMaxDIS (as is described in steps (
1
) and (
2
) of Algorithm 1).Algorithm 1:
AP-PrefixspanM (TDB, MinIS, and max_per).
Input: target database TDB, minimum support vector MinISand the maximum period max_per.
Output: all the asynchronous periodic sequential patterns and valid contained segments queue.
(1)   MinREP ← generateREP(MinIS);
(2)   MaxDis ← generateDIS(MinIS);
(3)   L ← init_pass(M, TDB);
(4)   P
F
1 ← x
x
∈
L
,
x
.
c
o
u
n
t
≥
M
i
n
I
S
x;
(5)   S
P
F
1 ← sort (P
F
1, ASCEND);
(6)   FOR each x
i in S
P
F
1  DO
(7)   //b
e
f
o
r
e
P
F
1
x
i is the 1-pattern before x
i of S
P
F
1.
(8)
S
U
B
_
T
D
B
x
i ← t
|
t
∈
T
D
B
∧
x
i
∈
t delete b
e
f
o
r
e
P
F
1
x
i;
(9)   MAPPrefixSpan(null, S
U
B
_
T
D
B
x
i, x
i, MinIS(x
i), MaxREP(x
i), MaxDis(x
i));
(1
0) ENDFORThen, scan theTDB once and find all the frequent items x
i for which the real support is more thanMinIS(x
i). Such items are the potential asynchronous periodic sequential patterns whose lengths are 1 (as is described in step (
4
) of Algorithm 1). Obtain the listSPF
1 by sorting the frequent items in ascending order based on the minimum support vectorMinIS (as is described in step (5) of Algorithm 1). Finally, obtain the |
SPF
1
| divided subdatabases, and, for each sub database, call the functionMAPPrefixSpan to mine the asynchronous periodic sequential patterns (as is described in steps (6)–(10) of Algorithm 1).The functionMAPPrefixSpan discovers all synchronous periodic sequential patterns by the method of depth-first search (as is described in Algorithm 2). First, we define a hash maphash_item
item_id, (count,tids) to record each frequent item’s frequency and its time slot (as is described in step (1) of Algorithm 2), whereitem_id is the key of the hash map, two-tuples (count, tids) is the value,count is the frequency ofitem_id, andtids is the time slot queue ofitem_id. Each item x has two possible ways to be extended to the prefix and obtain a new sequential pattern: (
1
) join x to the last item set of the prefix anditem_id of x is expressed as “_x,” and (
2
) join x independently to the prefix, anditem_id of x is expressed as “x.” Scan the projected databaseTDB, and record the frequency and the time slot queues of the two extended ways by the hash map (as is described in steps (2)–(8) of Algorithm 2). Delete the items for which the frequency is less thanmin_sup in the hash map (as is described in steps (9)–(11) of Algorithm 2). At this time, the frequent items ofhash_item may be extended to the current prefix, and a new asynchronous periodic sequential pattern would be generated. For each item, call the functionASPDetector to calculate the possibility of frequent items being extended to the prefix to generate new patterns. If there would be new patterns, then all the valid contained segment queue set of the new pattern would be generated (as is described in step (13) of Algorithm 2). If frequent items can be extended to the prefix, then generate the new prefix after extension (as is described in step (15) of Algorithm 2); meanwhile, call the functionProjectdatabase to generate the prefix projected database D
B
c of the current item. Ifc_item is not included in the prefix, delete the tuple in which the key itemc_item is not included in D
B
c (as is described in steps (16)–(18) of Algorithm 2). If the number of tuples in the filtered D
B
c is not less thanmin_sup, then call the functionMAPPrefixSpan recursively to discover the items that can be extended to the prefix in the smaller prefix projected database, and discover the asynchronous periodic sequential patterns that are growing progressively (as is described in steps (19)-(20) of Algorithm 2). In the process of the recursion above, all the asynchronous periodic sequential patterns and their valid contained segment queues can be discovered.Algorithm 2:
MAPPrefixSpan (prefix,DB, c_item,min_sup,min_rep,max_per, and max_dis).
Input: prefix prefix, temporal symbolic sequence databases TDB, key item c_item, minimum support min_sup, minimum
repeat countmin_rep, maximum period max_per, maximum interference distance max_dis.
(1)   hash_item〈item_id, (count, tids)〉;
(2)    FOR each tuple t in D
B  DO
(3)
IF  x
∈
t
.
s, x
∈
L  THEN
(4)     hash_item[x].count++; hash_item[x].tid ← ∪ t
.
t
i
d;
(5)
IF  p
e
r
f
i
x
.
l
i
t
e
m
s
e
t
,
x
o
r
_
x
∈
t
.
s, x
∈
L  THEN
(6)     //prefix.litemset is the last item of prefix
(7)     hash_item[_
x].count++; hash_item[_
x].tid ← ∪ t
.
t
i
d;
(8)    ENDFOR
(9)    FOR each key c in hash_item  DO
(10)
IF  h
a
s
h
_
i
t
e
m
[
c
]
.
c
o
u
n
t
<
m
i
n
_
s
u
p  THEN delete hash_item[c];
(11)  ENDFOR
(12)  FOR each key c in hash_item  DO
(13)   ASPDetector (c, hash_item[c], c
_item, prefix, min_sup, min_rep, max_per, max_dis);
(14)
IF  c can be extended to prefix  THEN
(15)    newprefix ← extend(c, prefix);
(16)    D
B
c ← Projectdatabase (c, D
B);
(17)    IF  prefix notcontain c
_item  THEN
(18)    delete tuples in D
B
c which not contain c
_item;
(19)    IF  min_sup ≤ D
B
c  THEN
(20)  AP-PrefixspanM(newprefix, D
B
c, c
_item, min_sup, min_rep, max_per, max_dis);
(21) ENDFORThe functionASPDetector is used to judge whether the current item can be extended to the prefix, obtain a new growing asynchronous periodic sequential pattern (a new pattern for short), and discover the new pattern’s valid contained segment queue. The judgment of pattern growth consists of three stages: (
1
) potential period detection (PPD), (
2
) valid segment detection (VSD), and (
3
) valid segment mergence (VSM).The PPD stage (as is described in steps (3)–(9) of Algorithm3) is responsible for detecting all the possible periods of a new pattern. The hash maphash_period
p,count
(initializecount’s value to 1) is used to record the frequency of a period. Scan the time slot queue of the parameteroccur. Start with the first time slot and establish a sliding window of which the length ismax_per, and calculate the time intervals between the first time slot in the sliding window and other time slots behind it. At an arbitrary time slottid
i, calculate the interval p
i
j
=
|
t
i
d
i
-
t
i
d
j
| betweentid
i andtid
j, where i
+
1 ≤j ≤ min(max_per-i, |
o
c
c
u
r
|). If p
i
j ≤max_per, then increase the count of the period p
i
j ofhash_period by one (as is described in step (4) and step (5) of Algorithm 3). Otherwise, stop calculating and slide the window to the time slottid
i+1 beforetid
i, and repeat the calculation process. The requirement for generating a new pattern, for which the period is p
i (1
≤
p
i
≤
m
a
x
_
p
e
r), is that the frequency p
i be not less thanmin_rep; that is,hash_period[p
i] ≥
min_rep.Algorithm 3:
ASPDetector (fitem, occur, c_item, prefix, min_sup, min_rep, max_per, and max_dis).
Input: frequent items fitem, time slot table occur, key item c
_item, prefix prefix, minimum support min_sup, minimum
repeat countmin_rep, maximum period max_per, maximum interference distance max_dis
(1)    hash_period〈
p, count  ←  1〉;
(2)    FOR  each t
i
d
i in occur.tids  DO
(3)
FOR each t
i
d
j in occur.tids, i
<
j  DO
(4)     IF
t
i
d
j
-
t
i
d
i ≤ max_per  THEN
(5)     hash_period [t
i
d
j
-
t
i
d
i].count++;
(6)     ELSE break;
(7)
ENDFOR
(8)    ENDFOR
(9)    FOR each key p
i that hash_period [p
i] ≥ min_rep  DO
(10)   hash_segment〈pos, (rep, last)〉;
(1
1)   vs_set (patten, period, rep, start)  ←  ⌀;
(1
2)
FOR each t
i
d
i in occur.tids  DO
(1
3)    p
o
s
i ← t
i
d
i mod p
i;
(1
4)    IF (t
i
d
i
-
h
a
s
h
_
s
e
g
m
e
n
t
[
p
o
s
i
]
.
l
a
s
t) == p
i  THEN
(1
5)    hash_segment [p
o
s
i].rep++;
(1
6)    hash_segment [p
o
s
i].last ← t
i
d
i;
(1
7)    continue;
(1
8)
IF  hash_segment [p
o
s
i].rep ≥ min_rep  THEN
(1
9)     pattern ← extend(prefix, fitem);
(20)    vs_set ← vs_set
∪ (pattern, p
i, hash_segment[p
o
s
i].rep, hash_segment[p
o
s
i].
l
a
s
t
-
p
i
∗
(
hash_segment[p
o
s
i].
r
e
p
-
1));
(21)   hash_list[p
o
s
i].rep  ←  1;
(22)   hash_list[p
o
s
i].last  ←  t
i
d
i;
(23)
ENDFOR
(24)
FOR each key p
o
s
i that hash_list[p
o
s
i] ≥ min_rep  DO
(25)   pattern ← extend(prefix, fitem);
(26)   vs_set ← vs_set
∪ (pattern, p
i, hash_list[p
o
s
i].rep, hash_list[posi].l
a
s
t
-
p
i
∗
(
hash_list[p
o
s
i
]
.
r
e
p
-
1
));
(27)
ENDFOR
(28)  svs_set ← sort(vs_set);
(29)
FOR each v
s
i in svs_set  DO
(30)  IF (v
s
i.rep ≥ min_sup) && (c
_item∈pattern) THEN
(31)  Output(v
s
i);
(32)  MergeSeg(v
s
i, svs_set, v
s
i.rep, min_sup, max_dis);
(33)
ENDFOR
(34) ENDFORThe VSD stage is responsible for discovering all the valid contained segments of the new pattern. Firstly, for each potential periodp
i, define a hash maphash_segment
pos, (rep,last) to record the contained segments (as is described in step (10) of Algorithm 3), where the keypos is the pattern’s offset, and the value (rep,last) is used to record the repeat count and the new time slot of the contained segments. At an arbitrary time slottid
i,tid
j-hash_segment[pos
i].last (pos
i =tid
i%p
i) is the time interval of two simultaneous occurrences. Iftid
i,tid
j-hash_segment[pos
i].last is equal to p
i, which means that those two occurrences are consecutive in the same contained segment.hash_segment[pos
i].rep records the repeat count of a contained segment. The current contained segment, for which the offset ispos
i, is valid whenhash_segment[pos
i].rep ≥min_rep. Specifically, for each period p
i, the time slot queue should be scanned once, and, for each time slottid
i, the offsetpos
i =tid
j%p
i needs to be calculated (as described in step (13) of Algorithm 3). Iftid
j-hash_segment[pos
i].last is equal to p
i, the current contained segment is growing; incrementhash_segment[pos
i].rep by one, updatehash_segment[pos
i].last totid
i (as described in steps (15) and (16) of Algorithm 3), and then process the next time slot. Otherwise, the current contained segment is interrupted; at that time, ifhash_segment[pos
i].rep ≥min_rep, the current contained segment is valid. It would be recorded as a tetrad invs_set (as described in steps (18)–(20) of Algorithm 3). After the interruption,hash_segment[pos
i].repwould be reset to 1, andhash_segment[pos
i].last would be updated totid
i (as described in steps (21) and (22) of Algorithm 3). After the time slot queue is detected,hash_segment would be detected again to judge whether a valid contained segment exists (as described in steps (24)–(27) of Algorithm 3). Sort all valid contained segments for which the period is p
i in ascending order by their start time slot (as described in step (28) of Algorithm 3). For each contained segment, call the functionMergeSeg to merge all contained segments, and generate a valid contained segment queue, for which the period is p
i; start with the current contained segment (as described in steps (28)–(31) of Algorithm 3), then print the valid contained segment queue for which the key items are included.The VSM stage is responsible for generating the valid contained segment queue. FunctionMergeSeg adopts the depth-first enumeration method to merge all possible contained segments into the queue. Generate a different contained segment queue with different initial contained segments, and, for each contained segment, use the divide-and-conquer strategy to find the segment that can be merged with the initial segments. Then, regard these segments as the initial segments to find other segments that can be merged recursively. Repeat this process until no segments can be merged. Specifically, if the repeat count of an initial segment is not less thanmin_sup, print this segment (as described in steps (29) and (30) of Algorithm 3). For any initial segment, scansvs_set once and find the segment set into which the segment can be merged directly (as described in steps (2)–(7) of Algorithm 4). For the segments of such set, call the functionMergeSeg recursively (as described in step (14) of Algorithm 4) to generate a smaller segment set (as described in step (11) of Algorithm 4), and various longer segment queues can be generated (as described in step (9) of Algorithm 4). Once the sum of the segments’ repeat counts is not less thanmin_sup and key items are included in the pattern while merging, print that segment queue (as described in steps (12) and (13) of Algorithm 4).Algorithm 4:
MergeSeg (prefix_segs, svs_set, prefix_sum, min_sup, andmax_dis).
Input: prefix segments prefix_segs, contain segments set svs_set, repeat count of prefix segments prefix_sum, minimum support
min_sup, maximum interference distance max_dis
(1)   VSQ ← ⌀;
(2)   FOR each v
s
i in svs_set
i
>
1
DO
(3)   tail ← v
s
1.start + v
s
1.p
e
r
i
o
d
∗
(
v
s
1.r
e
p
-
1);
(4)
IF ((v
s
i.s
t
a
r
t
-
t
a
i
l) > m
a
x
_
d
i
s
∗
p) THEN break;
(5)
ELSE IF (tail > v
s
i.start) THEN continue;
(6)
ELSE
VSQ ← VSQ
∪
v
s
i;
(7)   ENDFOR
(8)   FOR each v
s
i in VSQ
DO
(9)   newprefix_segs ← prefix_segs ∪  v
s
i;
(10) newprefix_sum ← prefix_sum + v
s
i.rep;
(11) newsvs_set ← svs_set delete segments before v
s
i;
(12)
IF
(newprefix_sum ≥ min_sup) && (c
_item ∈ pattern) THEN
(13)  Output(newprefix_segs);
(14) MergeSeg (newprefix_segs, newsvs_set, prefix_sum, min_sup, max_dis);
(15) ENDFOR


## 5.1. Relationship between Algorithm Parameters

LetM
i
n
I
S
(
i
) represent the minimum support of item i. The minimum support of the sequential pattern P is the lowest minimum support of all items of P; for example, if the item set of P is i
1
,
i
2
,
…
,
i
k, then the equation of minimum support of P is(3)
m
i
n
_
s
u
p
P
=
m
i
n
M
i
n
I
S
i
1
,
M
i
n
I
S
i
2
,
…
,
M
i
n
I
S
i
k
.LetM
i
n
R
E
P
(
i
) be the minimum repeat count of item i; the minimum repeat count of P is the lowest repeat count of all items; that is(4)
m
i
n
_
r
e
p
P
=
m
i
n
M
i
n
R
E
P
i
1
,
M
i
n
R
E
P
i
2
,
…
,
M
i
n
R
E
P
i
k
.Additionally, letM
a
x
D
i
s
(
i
) be the maximum interference distance of item i, which represents a reasonable bound of disturbance between two valid sequences of contained segments; the maximum interference distance of P is the largest maximum interference distance of all items; that is(5)
m
a
x
_
d
i
s
P
=
m
a
x
M
a
x
D
i
s
i
1
,
M
a
x
D
i
s
i
2
,
…
,
M
a
x
D
i
s
i
k
.To reduce the workload of user settings, we assume that there is a function relationship between the maximum interference distance, the minimum repeat count, and the minimum support. Specifically, the relationship between the minimum repeat count of itemi, M
i
n
R
E
P
(
i
), and the minimum support of item i, M
i
n
I
S
(
i
), is linear increasing, and it can be expressed as follows:(6)
M
i
n
R
E
P
i
=
λ
∗
M
i
n
I
S
i
(
0
<
λ
≤
1
)
.The relationship between the maximum interference distance of itemi, M
a
x
D
i
s
(
i
), and the minimum support of item i, M
i
n
I
S
(
i
), is exponential decreasing, and it can be expressed as follows:(7)
M
a
x
D
i
s
i
=
η
∗
max
⁡
(
M
i
n
I
S
)
M
i
n
I
S
i
,where η is the preset constant of interference distance and max (MinIS) is the largest minimum support ofMinIS.IfMinIS(i
1) ≤MinIS(i
2) ≤ ⋯ ≤MinIS(i
k), thenMinREP(i
1) ≤MinREP(i
2) ≤ ⋯ ≤MinREP(i
k),MaxDis(i
1) ≥
MaxDis(i
2) ≥ ⋯ ≥MaxDis(i
k).


## 5.2. The Main Idea and Steps of the Algorithm

For the purpose of reducing the search space of asynchronous periodic symbolic sequential pattern mining, the downward closure property is used in the asynchronous periodic sequential pattern mining model with single minimum support.Property (Downward Closure Property). If the sequence α is an asynchronous periodic sequential pattern and its set of valid sequences of contained segments isQSet, then we can say that all the nonempty subsequences of α are also asynchronous periodic sequential patterns, and the set of valid sequences of contained segments of these subsequences is the superset ofQSet.However, because the minimum item support of an asynchronous periodic sequential pattern may be less than its subsequence’s with multiple minimum item supports, the downward closure property cannot be used directly to prune the search space.The main idea of thePrefixspanM algorithm is based on the divide-and-conquer strategy. The problem of asynchronous periodic sequential pattern mining is divided progressively into a series of subproblems that are not intersecting. The framework of database division in thePrefixspanM algorithm is as shown in Figure 2. Two dividing methods can be adopted: (
1
) prune the search space with the downward closure property: at level 1, the database is divided into a series of subdatabases by the minimum support vectors and (
2
) generate asynchronous periodic sequential patterns with pattern-growth: below the second level, the prefix projected database is generated recursively by the prefix.Figure 2
The framework of database division in the AP-PrefixspanM algorithm.Firstly, theAP-PrefixspanM algorithm divides the database based on minimum support vectors. Then, a series of subdatabases are generated and mined by the single minimum support. Each division is based on a frequent item called a key item. The single minimum support utilized is called the minimum support of the key item. The downward closure property will not be destroyed while mining, and the specific splitting steps of data are described as follows.Step 1.
Scan the database TDB and obtain itemx
i, whose real support is at leastMinIS(x
i). Such items x
i are called frequent items, and they are placed in ascending order according to theirMinIS to obtain l
i
s
t
=
x
1
,
x
2
,
…
,
x
n, (x
i
≤
x
i
+
1).Step 2.
The complete set of sequential patterns of asynchronous period inTDB can be divided into the following n mutually disjoint subsets, among which some subsets may be empty: (
1
)
sequential patterns that contain sequencex
1,
(
2
)
sequential patterns that contain sequencex
2 but do not contain x
1,
⋮
(
i
)
sequential patterns that contain sequencex
i but do not contain {
x
1
,
x
2
,
…
,
x
i
-
1
},
⋮
(
n
)
sequential patterns that only containx
n.
DivideTDB by these n subsets, and then mine the n subdatabases to obtain the subsets of these n asynchronous periodic sequential patterns:(
1
)
TDB
1 (key item x
1): delete the infrequent items of tuples and the tuples that do not contain x
1;
(
2
)
TDB
2 (key item x
2): delete the infrequent items of tuples, x
1, and the tuples that do not contain x
2;
⋮
(
i
)
TDB
i (key item x
i): delete the infrequent items of tuples, {
x
1
,
x
2
,
…
,
x
i
-
1
}, and the tuples that do not contain x
i;
⋮
(
n
)
TDB
n (key item x
n): delete all the infrequent items of tuples except for x
n and the tuples that do not contain x
n.Mine the asynchronous periodic sequential patterns in theTDB
i with the minimum support ofMinIS(x
i). This problem can be divided into a series of mutually disjoint subproblems.(1)
Let{
y
1
,
y
2
,
…
,
y
m
} be the complete set of length-l asynchronous periodic sequential patterns inTDB
i, and this complete set can be divided into m mutually disjoint subsets. The subset j (1
≤
j
≤
m) is the set of asynchronous periodic sequential patterns whose prefix is y
j.
(2)
Letα be the asynchronous periodic sequential length-l pattern. {
β
1
,
β
2
,
…
,
β
t
} is the set of asynchronous periodic sequential patterns whose prefix is α and length is l
+
1. Apart from α, the complete set of asynchronous periodic sequential patterns whose prefix is α can be divided into k mutually disjoint subsets. The subsetk (1
≤
k
≤
t) is the subset of asynchronous periodic sequential patterns whose prefix is β
k, as is shown in Figure 3.Figure 3
Division of a subset of asynchronous periodic sequential patterns.Based on the descriptions above, the problem of asynchronous periodic sequential pattern mining can be divided recursively, which suggests that each subset can be further divided. Thus, a divide-and-conquer framework is composed. To mine the subsets of asynchronous periodic sequential patterns, we can construct corresponding prefix projected databases and mine each database recursively. The main step is shown as follows:Step 1 (generate parameters).
RegardingMinIs as the minimum support vector, generate the minimum repeat count vector,MinREP, and the maximum interface distance vector,MaxDis.Step 2 (find the length-1 sequential patterns).
Scan the database once and generate all length-1 asynchronous periodic sequential patterns. The length of all patterns will be increased by 1 when the prefix is extended by those length-1 sequential patterns.Step 3 (divide the search space).
Divide the complete set of asynchronous periodic sequential patterns into the subsets whose prefixes are the patterns whose lengths have been increased by 1.Step 4.
Construct the prefix projected databases, and, then, discover the subsets of each asynchronous periodic sequential pattern recursively. Specifically, repeat the steps above until no length-1 asynchronous periodic sequential patterns can be generated.In the mining process described above, only the asynchronous periodic sequential patterns will be added to the mining result. Other patterns will be deleted after mining.


## 5.3. Implementation of the Algorithm

The pseudocode ofAP-PrefixspanM is described in Algorithm 1. Firstly, regardingMinIS as the minimum support vector, generate the minimum repeat countMinREP and the maximum interference distanceMaxDIS (as is described in steps (
1
) and (
2
) of Algorithm 1).Algorithm 1:
AP-PrefixspanM (TDB, MinIS, and max_per).
Input: target database TDB, minimum support vector MinISand the maximum period max_per.
Output: all the asynchronous periodic sequential patterns and valid contained segments queue.
(1)   MinREP ← generateREP(MinIS);
(2)   MaxDis ← generateDIS(MinIS);
(3)   L ← init_pass(M, TDB);
(4)   P
F
1 ← x
x
∈
L
,
x
.
c
o
u
n
t
≥
M
i
n
I
S
x;
(5)   S
P
F
1 ← sort (P
F
1, ASCEND);
(6)   FOR each x
i in S
P
F
1  DO
(7)   //b
e
f
o
r
e
P
F
1
x
i is the 1-pattern before x
i of S
P
F
1.
(8)
S
U
B
_
T
D
B
x
i ← t
|
t
∈
T
D
B
∧
x
i
∈
t delete b
e
f
o
r
e
P
F
1
x
i;
(9)   MAPPrefixSpan(null, S
U
B
_
T
D
B
x
i, x
i, MinIS(x
i), MaxREP(x
i), MaxDis(x
i));
(1
0) ENDFORThen, scan theTDB once and find all the frequent items x
i for which the real support is more thanMinIS(x
i). Such items are the potential asynchronous periodic sequential patterns whose lengths are 1 (as is described in step (
4
) of Algorithm 1). Obtain the listSPF
1 by sorting the frequent items in ascending order based on the minimum support vectorMinIS (as is described in step (5) of Algorithm 1). Finally, obtain the |
SPF
1
| divided subdatabases, and, for each sub database, call the functionMAPPrefixSpan to mine the asynchronous periodic sequential patterns (as is described in steps (6)–(10) of Algorithm 1).The functionMAPPrefixSpan discovers all synchronous periodic sequential patterns by the method of depth-first search (as is described in Algorithm 2). First, we define a hash maphash_item
item_id, (count,tids) to record each frequent item’s frequency and its time slot (as is described in step (1) of Algorithm 2), whereitem_id is the key of the hash map, two-tuples (count, tids) is the value,count is the frequency ofitem_id, andtids is the time slot queue ofitem_id. Each item x has two possible ways to be extended to the prefix and obtain a new sequential pattern: (
1
) join x to the last item set of the prefix anditem_id of x is expressed as “_x,” and (
2
) join x independently to the prefix, anditem_id of x is expressed as “x.” Scan the projected databaseTDB, and record the frequency and the time slot queues of the two extended ways by the hash map (as is described in steps (2)–(8) of Algorithm 2). Delete the items for which the frequency is less thanmin_sup in the hash map (as is described in steps (9)–(11) of Algorithm 2). At this time, the frequent items ofhash_item may be extended to the current prefix, and a new asynchronous periodic sequential pattern would be generated. For each item, call the functionASPDetector to calculate the possibility of frequent items being extended to the prefix to generate new patterns. If there would be new patterns, then all the valid contained segment queue set of the new pattern would be generated (as is described in step (13) of Algorithm 2). If frequent items can be extended to the prefix, then generate the new prefix after extension (as is described in step (15) of Algorithm 2); meanwhile, call the functionProjectdatabase to generate the prefix projected database D
B
c of the current item. Ifc_item is not included in the prefix, delete the tuple in which the key itemc_item is not included in D
B
c (as is described in steps (16)–(18) of Algorithm 2). If the number of tuples in the filtered D
B
c is not less thanmin_sup, then call the functionMAPPrefixSpan recursively to discover the items that can be extended to the prefix in the smaller prefix projected database, and discover the asynchronous periodic sequential patterns that are growing progressively (as is described in steps (19)-(20) of Algorithm 2). In the process of the recursion above, all the asynchronous periodic sequential patterns and their valid contained segment queues can be discovered.Algorithm 2:
MAPPrefixSpan (prefix,DB, c_item,min_sup,min_rep,max_per, and max_dis).
Input: prefix prefix, temporal symbolic sequence databases TDB, key item c_item, minimum support min_sup, minimum
repeat countmin_rep, maximum period max_per, maximum interference distance max_dis.
(1)   hash_item〈item_id, (count, tids)〉;
(2)    FOR each tuple t in D
B  DO
(3)
IF  x
∈
t
.
s, x
∈
L  THEN
(4)     hash_item[x].count++; hash_item[x].tid ← ∪ t
.
t
i
d;
(5)
IF  p
e
r
f
i
x
.
l
i
t
e
m
s
e
t
,
x
o
r
_
x
∈
t
.
s, x
∈
L  THEN
(6)     //prefix.litemset is the last item of prefix
(7)     hash_item[_
x].count++; hash_item[_
x].tid ← ∪ t
.
t
i
d;
(8)    ENDFOR
(9)    FOR each key c in hash_item  DO
(10)
IF  h
a
s
h
_
i
t
e
m
[
c
]
.
c
o
u
n
t
<
m
i
n
_
s
u
p  THEN delete hash_item[c];
(11)  ENDFOR
(12)  FOR each key c in hash_item  DO
(13)   ASPDetector (c, hash_item[c], c
_item, prefix, min_sup, min_rep, max_per, max_dis);
(14)
IF  c can be extended to prefix  THEN
(15)    newprefix ← extend(c, prefix);
(16)    D
B
c ← Projectdatabase (c, D
B);
(17)    IF  prefix notcontain c
_item  THEN
(18)    delete tuples in D
B
c which not contain c
_item;
(19)    IF  min_sup ≤ D
B
c  THEN
(20)  AP-PrefixspanM(newprefix, D
B
c, c
_item, min_sup, min_rep, max_per, max_dis);
(21) ENDFORThe functionASPDetector is used to judge whether the current item can be extended to the prefix, obtain a new growing asynchronous periodic sequential pattern (a new pattern for short), and discover the new pattern’s valid contained segment queue. The judgment of pattern growth consists of three stages: (
1
) potential period detection (PPD), (
2
) valid segment detection (VSD), and (
3
) valid segment mergence (VSM).The PPD stage (as is described in steps (3)–(9) of Algorithm3) is responsible for detecting all the possible periods of a new pattern. The hash maphash_period
p,count
(initializecount’s value to 1) is used to record the frequency of a period. Scan the time slot queue of the parameteroccur. Start with the first time slot and establish a sliding window of which the length ismax_per, and calculate the time intervals between the first time slot in the sliding window and other time slots behind it. At an arbitrary time slottid
i, calculate the interval p
i
j
=
|
t
i
d
i
-
t
i
d
j
| betweentid
i andtid
j, where i
+
1 ≤j ≤ min(max_per-i, |
o
c
c
u
r
|). If p
i
j ≤max_per, then increase the count of the period p
i
j ofhash_period by one (as is described in step (4) and step (5) of Algorithm 3). Otherwise, stop calculating and slide the window to the time slottid
i+1 beforetid
i, and repeat the calculation process. The requirement for generating a new pattern, for which the period is p
i (1
≤
p
i
≤
m
a
x
_
p
e
r), is that the frequency p
i be not less thanmin_rep; that is,hash_period[p
i] ≥
min_rep.Algorithm 3:
ASPDetector (fitem, occur, c_item, prefix, min_sup, min_rep, max_per, and max_dis).
Input: frequent items fitem, time slot table occur, key item c
_item, prefix prefix, minimum support min_sup, minimum
repeat countmin_rep, maximum period max_per, maximum interference distance max_dis
(1)    hash_period〈
p, count  ←  1〉;
(2)    FOR  each t
i
d
i in occur.tids  DO
(3)
FOR each t
i
d
j in occur.tids, i
<
j  DO
(4)     IF
t
i
d
j
-
t
i
d
i ≤ max_per  THEN
(5)     hash_period [t
i
d
j
-
t
i
d
i].count++;
(6)     ELSE break;
(7)
ENDFOR
(8)    ENDFOR
(9)    FOR each key p
i that hash_period [p
i] ≥ min_rep  DO
(10)   hash_segment〈pos, (rep, last)〉;
(1
1)   vs_set (patten, period, rep, start)  ←  ⌀;
(1
2)
FOR each t
i
d
i in occur.tids  DO
(1
3)    p
o
s
i ← t
i
d
i mod p
i;
(1
4)    IF (t
i
d
i
-
h
a
s
h
_
s
e
g
m
e
n
t
[
p
o
s
i
]
.
l
a
s
t) == p
i  THEN
(1
5)    hash_segment [p
o
s
i].rep++;
(1
6)    hash_segment [p
o
s
i].last ← t
i
d
i;
(1
7)    continue;
(1
8)
IF  hash_segment [p
o
s
i].rep ≥ min_rep  THEN
(1
9)     pattern ← extend(prefix, fitem);
(20)    vs_set ← vs_set
∪ (pattern, p
i, hash_segment[p
o
s
i].rep, hash_segment[p
o
s
i].
l
a
s
t
-
p
i
∗
(
hash_segment[p
o
s
i].
r
e
p
-
1));
(21)   hash_list[p
o
s
i].rep  ←  1;
(22)   hash_list[p
o
s
i].last  ←  t
i
d
i;
(23)
ENDFOR
(24)
FOR each key p
o
s
i that hash_list[p
o
s
i] ≥ min_rep  DO
(25)   pattern ← extend(prefix, fitem);
(26)   vs_set ← vs_set
∪ (pattern, p
i, hash_list[p
o
s
i].rep, hash_list[posi].l
a
s
t
-
p
i
∗
(
hash_list[p
o
s
i
]
.
r
e
p
-
1
));
(27)
ENDFOR
(28)  svs_set ← sort(vs_set);
(29)
FOR each v
s
i in svs_set  DO
(30)  IF (v
s
i.rep ≥ min_sup) && (c
_item∈pattern) THEN
(31)  Output(v
s
i);
(32)  MergeSeg(v
s
i, svs_set, v
s
i.rep, min_sup, max_dis);
(33)
ENDFOR
(34) ENDFORThe VSD stage is responsible for discovering all the valid contained segments of the new pattern. Firstly, for each potential periodp
i, define a hash maphash_segment
pos, (rep,last) to record the contained segments (as is described in step (10) of Algorithm 3), where the keypos is the pattern’s offset, and the value (rep,last) is used to record the repeat count and the new time slot of the contained segments. At an arbitrary time slottid
i,tid
j-hash_segment[pos
i].last (pos
i =tid
i%p
i) is the time interval of two simultaneous occurrences. Iftid
i,tid
j-hash_segment[pos
i].last is equal to p
i, which means that those two occurrences are consecutive in the same contained segment.hash_segment[pos
i].rep records the repeat count of a contained segment. The current contained segment, for which the offset ispos
i, is valid whenhash_segment[pos
i].rep ≥min_rep. Specifically, for each period p
i, the time slot queue should be scanned once, and, for each time slottid
i, the offsetpos
i =tid
j%p
i needs to be calculated (as described in step (13) of Algorithm 3). Iftid
j-hash_segment[pos
i].last is equal to p
i, the current contained segment is growing; incrementhash_segment[pos
i].rep by one, updatehash_segment[pos
i].last totid
i (as described in steps (15) and (16) of Algorithm 3), and then process the next time slot. Otherwise, the current contained segment is interrupted; at that time, ifhash_segment[pos
i].rep ≥min_rep, the current contained segment is valid. It would be recorded as a tetrad invs_set (as described in steps (18)–(20) of Algorithm 3). After the interruption,hash_segment[pos
i].repwould be reset to 1, andhash_segment[pos
i].last would be updated totid
i (as described in steps (21) and (22) of Algorithm 3). After the time slot queue is detected,hash_segment would be detected again to judge whether a valid contained segment exists (as described in steps (24)–(27) of Algorithm 3). Sort all valid contained segments for which the period is p
i in ascending order by their start time slot (as described in step (28) of Algorithm 3). For each contained segment, call the functionMergeSeg to merge all contained segments, and generate a valid contained segment queue, for which the period is p
i; start with the current contained segment (as described in steps (28)–(31) of Algorithm 3), then print the valid contained segment queue for which the key items are included.The VSM stage is responsible for generating the valid contained segment queue. FunctionMergeSeg adopts the depth-first enumeration method to merge all possible contained segments into the queue. Generate a different contained segment queue with different initial contained segments, and, for each contained segment, use the divide-and-conquer strategy to find the segment that can be merged with the initial segments. Then, regard these segments as the initial segments to find other segments that can be merged recursively. Repeat this process until no segments can be merged. Specifically, if the repeat count of an initial segment is not less thanmin_sup, print this segment (as described in steps (29) and (30) of Algorithm 3). For any initial segment, scansvs_set once and find the segment set into which the segment can be merged directly (as described in steps (2)–(7) of Algorithm 4). For the segments of such set, call the functionMergeSeg recursively (as described in step (14) of Algorithm 4) to generate a smaller segment set (as described in step (11) of Algorithm 4), and various longer segment queues can be generated (as described in step (9) of Algorithm 4). Once the sum of the segments’ repeat counts is not less thanmin_sup and key items are included in the pattern while merging, print that segment queue (as described in steps (12) and (13) of Algorithm 4).Algorithm 4:
MergeSeg (prefix_segs, svs_set, prefix_sum, min_sup, andmax_dis).
Input: prefix segments prefix_segs, contain segments set svs_set, repeat count of prefix segments prefix_sum, minimum support
min_sup, maximum interference distance max_dis
(1)   VSQ ← ⌀;
(2)   FOR each v
s
i in svs_set
i
>
1
DO
(3)   tail ← v
s
1.start + v
s
1.p
e
r
i
o
d
∗
(
v
s
1.r
e
p
-
1);
(4)
IF ((v
s
i.s
t
a
r
t
-
t
a
i
l) > m
a
x
_
d
i
s
∗
p) THEN break;
(5)
ELSE IF (tail > v
s
i.start) THEN continue;
(6)
ELSE
VSQ ← VSQ
∪
v
s
i;
(7)   ENDFOR
(8)   FOR each v
s
i in VSQ
DO
(9)   newprefix_segs ← prefix_segs ∪  v
s
i;
(10) newprefix_sum ← prefix_sum + v
s
i.rep;
(11) newsvs_set ← svs_set delete segments before v
s
i;
(12)
IF
(newprefix_sum ≥ min_sup) && (c
_item ∈ pattern) THEN
(13)  Output(newprefix_segs);
(14) MergeSeg (newprefix_segs, newsvs_set, prefix_sum, min_sup, max_dis);
(15) ENDFOR


## 6. Experimental Analysis

This paper first proposes an asynchronous periodic sequential pattern mining model, and, to confirm the validity and stability of the algorithm, we also design a synthetic dataset generation algorithm, which is shown in Algorithm5.Algorithm 5:
DataGenerator (N
,
S
,
H
i
g
h
,
M
e
d
i
u
m
,
L
o
w
,
C
,
P
,
T
,
I
,
R
,
and
D).
Input: parameters and their meaning are shown in Table 5
Output: simulation data set
(1)   FOR  i
=
1 to C  do
(2)   p.period = GaussianDist(P, MAXPER);
(3)   p.pattern = GenPattern(p.period, T, I);
(4)   position = UniformDist(N
/
5);
(5)
WHILE (1) DO
(6)    p.local = GeometricDist(R, MAX = N
/
P);
(7)    IF (N-position < p.local * p.period) THEN break;
(8)
FOR  j
=
1 to p.local  DO
(9)     position+=p.period;
(10)   insert p.pattern into TIDS[position];
(11)
ENDFOR
(12)   p.disturbance = p.period * GeometricDist(D, MAXDIS);
(13)   postion+=p.disturbance;
(14)
ENDWHILE
(15)  ENDFOR
(16)  FOR  i
=
1  to N  DO
(17)
t = PoissonDist(I, MAX = N);
(18)
k = t
-
T
I
D
S
i;
(19)  random generate k symbols with T
I
D
S
[
i
];
(20) ENDFORTable 5
Parameters of synthetic dataset generation algorithm.
Parameters
Meaning
Value
N
Scale of temporal symbolic sequences
5000
S
Total number of items
300
High
Proportion of high frequency items
1/3 (60%)
Medium
Proportion of medium frequency items
1/3 (30%)
Low
Proportion of low frequency items
1/3 (10%)
C
Possible number of asynchronous periodic sequential patterns
5
P
Average periodic length of sequential patterns
5
T
Average number of item sets of sequential patterns
8
I
Average number of items
2
R
Average repeat count of contained segments
25
D
Average ratio of random disturbance to period
8At first,C possible asynchronous periodic sequential patterns would be generated by the algorithm, and their periodic lengths are generated by aP-expectation normal distribution. The average number of items is generated by aT-expectation normal distribution. The appearance probability consists of three levels,High,Medium, andLow, and the starting position of patterns is determined by an (N/5)-expectation normal distribution. Then, for each asynchronous periodic sequential pattern, a set of contained segments is generated until the end of the time slot is reached. Also, according to the contained segments, the pattern would be inserted into the corresponding time slot. The repeat counts of the contained segments are generated by anR-expectation normal distribution. Finally, scan this time slot; some items will be compensated for in the sequences, and the total number of items is generated by a (T
∗
I)-expectation Poisson distribution.A synthetic dataset is generated by the dataset generation algorithm, and this algorithm is as shown in Table5. TheAP-PrefixspanM algorithm is used to mine asynchronous periodic sequential patterns of the synthetic dataset. The maximum period is 20, λ is 0.2, and η is 10.The mining results of theAP-PrefixspanMalgorithm are shown in Table 6. When the minimum support is between 0.2 and 0.4, the mining results contain 5 asynchronous periodic sequential patterns that are preset in the dataset generation algorithm. The insert mode of the largest valid contained segment queue corresponds to these 5 sequential patterns, which means that theAP-PrefixspanM algorithm can precisely discover asynchronous periodic sequential patterns and their valid contained segment queue.Table 6
Experimental results (length : number).
Support
Length
Period
Length of valid contained segment queue
0.3
(1 : 94), (2 : 553), (3 : 2132)(4 : 4994), (5 : 7306), (6 : 6567)(7 : 3330), (8 : 729)
(5 : 25705)
(1 : 1), (2 : 5)(3 : 18526), (5 : 2)(4 : 7170), (6 : 1)
0.35
(1 : 61), (2 : 380), (3 : 1510)(4 : 3567), (5 : 5178), (6 : 4572)(7 : 2268), (8 : 486)
(5 : 18022)
(2 : 3), (3 : 10849)(4 : 7169), (5 : 1)
0.4
(1 : 37), (2 : 248), (3 : 1014)(4 : 2544), (5 : 4014), (6 : 3888)(7 : 2106), (8 : 486)
(5 : 14337)
(2 : 2), (3 : 7168)(4 : 7167)
0.5
(1 : 1)
(5 : 1)
(3 : 1)
0.5∣0.5∣0.1
(1 : 5927), (2 : 2902)
(4 : 636)(5 : 2209)(8 : 126)(10 : 4278)(12 : 251)(15 : 735)(16 : 108)(20 : 486)
(1 : 27), (2 : 162)(3 : 572), (4 : 921)(5 : 962), (6 : 914)(7 : 858), (8 : 870)(9 : 924), (10 : 909)(11 : 723), (12 : 453)(13 : 264), (14 : 162)(15 : 81), (16 : 24)(17 : 3)
0.4∣0.3∣0.2
(1 : 59), (2 : 265), (3 : 1018)(4 : 2544), (5 : 4014), (6 : 3888)(7 : 2106), (8 : 486)
(5 : 14377)(10 : 3)
(2 : 8), (3 : 7202)(4 : 7170)Figure4 shows the distribution of lengths of asynchronous periodic sequential patterns with different minimum supports. The results show that the scale and number of sequential patterns will increase when the minimum support increases. There will only be one length-1 asynchronous periodic sequential pattern when the minimum support reaches 5%. When the minimum supports of high frequency items and medium frequency items are set very high, such as 5%, but the minimum supports of low frequency items are set very low, such as 1%, a myriad of length-1 or length-2 asynchronous periodic sequential patterns will appear, which suggests that even low frequency items are focused on. Many meaningless sequential patterns would still appear if the minimum support was set very low, which means that theAP-PrefixspanM algorithm can effectively mine the asynchronous periodic sequential patterns with sparse items and also can avoid the generation of many meaningless patterns.Figure 4
Distribution of lengths of asynchronous periodic sequential patterns.Figure5 shows the distribution of periodic lengths of asynchronous periodic sequential patterns with different minimum supports. The results show that, except for when the minimum supports of high, medium, and low items are set as 5%, 5%, and 1%, the periodic lengths of asynchronous periodic sequential patterns are all nearly 5, which corresponds to the preset parameter P
=
5. However, under the condition that the minimum supports of high, medium, and low items are set as 5%, 5%, and 1%, periodic lengths are random, which means that there are a great number of meaningless sequential patterns.Figure 5
Distribution of periods of asynchronous periodic sequential patterns.Figure6 shows the distribution of lengths of valid contained segment queues of asynchronous periodic sequential patterns with different minimum supports. The results show that, except for when the minimum supports of high, medium, and low items are set as 5%, 5%, and 1%, the lengths of most valid contained segment queues are 3 or 4. Although the preset parameter R of the dataset generation algorithm is 25, because of the independent insertion and the random supplement of sequential patterns, the repeat counts of many short sequential patterns are larger than 25; therefore, the lengths of most valid contained segment queues are 3 or 4.Figure 6
Distribution of valid contained segment queues of asynchronous periodic sequential patterns.These experiments show that theAP-PrefixspanM algorithm is stable and efficient for mining asynchronous periodic sequential patterns.


## 7. Conclusions

In this paper, an asynchronous periodic sequential pattern mining model was proposed to discover sequential patterns that not only occur frequently but also appear periodically and to recognize the time range of their occurrences. Based on this mining model, we further propose a pattern-growth mining algorithm named theAP-PrefixspanM algorithm to mine asynchronous periodic sequential patterns with multiple minimum item supports. This algorithm applies a divide-and-conquer strategy to divide the problem of mining asynchronous periodic sequential patterns into a series of mutually disjoint subproblems progressively and then to mine the patterns in such subdatabases. During the process of dividing the database, growing asynchronous periodic sequential patterns and their valid contained segment queues are generated. This is exactly what the algorithm targets. Experimental results show the efficiency and stability of the algorithm. The data which can be applied in this algorithm are those regular and frequent happening data, such as entity movement trajectory data. The algorithm can mine the regular pattern of entity movement trajectory data and predict the future movement.The next work is to extend theAP-PrefixspanM algorithm and make it possible to mine asynchronous periodic spatiotemporal sequential patterns in spatiotemporal sequential databases with multiple minimum item supports.



---

*Source: 461659-2015-08-04.xml*