Database Reference
In-Depth Information
4.1
Sequential Pattern Mining
The problem of sequential pattern mining is closely related to that of frequent pattern
mining. The major difference in this case is that record contain
baskets of items
arranged sequential. For example, each record
R
i
may be of the following form:
R
i
={
Bread
}
,
{
Butter
,
Cake
}
,
{
Chicken
,
Yogurt
}
In this case, each entity within
is a basket of items that are bought together and,
therefore, do not have a temporal ordering. This basket of items is collectively re-
ferred to as an
event
. The length of a pattern is equal to the sum of the lengths of the
complex items in it. For example,
R
i
is a 5-pattern, even though it has 3 events. The
different complex entities (or events) do have a temporal ordering. In the aforemen-
tioned example, it is clear that
{}
.
The problem of sequential pattern mining is that of finding sequences of events that
are present in at least a fraction
s
of the underlying records [
5
]. For example, the
sequence
{
Bread
}
has been bought earlier than
{
Butter
,
Cake
}
{
Bread
}
,
{
Butter
}
,
{
Chicken
}
is present in the afore-mentioned record,
but not the sequence
{
Bread
}
,
{
Cake
}
,
{
Butter
}
. The pattern may also contain
{
}
{
}
complex events. For example, the pattern
is present
in
R
i
. The problem of sequential pattern mining is closely related to that of fre-
quent pattern mining except that it is somewhat more complex to account for both
the presence of complex baskets of items in the database, and the temporal order-
ing of the individual baskets. An extension of a sequential pattern may either be
a set-wise extension of a complex item, or a temporal extension with an entirely
new event. This affects the nature of the extensions of items in the transactions.
Numerous modifications of known frequent pattern mining methods such as
Apriori
and its variants,
TreeProjection
and its variants [
32
], and the
FP-growth
method
and its variants, can be used in order to solve the sequential pattern mining prob-
lem [
5
,
35
,
36
]. The enumeration tree concept can also be generalized to sequential
pattern mining [
32
]. Therefore, in principle, all enumeration tree algorithms can be
generalized to sequential pattern mining. This is a powerful ability because, as we
will see in Chap. 2 all frequent pattern mining algorithms are, implicitly or explicitly,
enumeration-tree algorithms. Sequential pattern mining methods will be discussed
in detail in Chap. 11.
Bread
,
Chicken
,
Yogurt
4.2
Spatiotemporal Pattern Mining
The advent of GPS-enabled mobile phones and wearable sensors has enabled the
collection of large amounts of spatiotemporal data. Such data may include trajectory
data, location-tagged images, or other content. In some cases, the spatiotemporal
data exists in the form of RFID data [
37
]. The mining of patterns from such spa-
tiotemporal data provides numerous insights in a wide variety of applications, such
as traffic control and social sensing [
2
]. Frequent patterns are also used for trajectory
