08-11-2012, 04:53 PM
Mining Cluster-Based Temporal Mobile Sequential Patterns in Location-Based Service Environments
Mining Cluster-Based Temporal.pdf (Size: 2.19 MB / Downloads: 37)
INTRODUCTION
THE advancement of wireless communication techniques
and the popularity of mobile devices such as mobile
phones, PDA, and GPS-enabled cellular phones, have
contributed to a new business model. Mobile users can
request services through their mobile devices via Information
Service and Application Provider (ISAP) from anywhere
at any time [35]. This business model is known as
Mobile Commerce (MC) that provides Location-Based
Services (LBS) [34] through mobile phones. MC is expected
to be as popular as e-commerce in the future [27] and it is
based on the cellular network composed of several base
stations. The communication coverage of each base station
is called a cell [20] as a location area. The average distance
between two base stations is hundreds of meters and the
number of base stations is usually more than 10,000 in a
city. When users move within the mobile network, their
locations and service requests are stored in a centralized
mobile transaction database. Fig. 1 shows an MC scenario,
where a user moves in the mobile network and requests
services in the corresponding cell through the mobile
devices.
RELATED WORK
In this section, we review previous related studies, which
can be classified into four categories: mobile pattern mining
techniques, clustering methods, temporal pattern mining
techniques, and mobile behavior predictions.
In recent years, a number of studies have discussed the
usage of data mining techniques to discover useful rules/
patterns from WWW [25], transaction databases [1], [2], [3],
[13], [23], and mobility data [10], [19], [29], [33], [37]. Mining
association rules [1] are proposed to find important items in
a transaction database. Agrawal and Srikant [2] proposed
the Apriori algorithm to mine the association rules. Park
et al. [23] proposed the DHP algorithm to improve the
performance of association rule mining. Pei et al. [25]
proposed an algorithm named WAP-Mine to efficiently
discover web access patterns in web logs, using a tree-based
data structure without candidate generation. Sequential
pattern mining was first introduced in [3] to search for timeordered
patterns, known as sequential patterns within
transaction databases.
Clustering of Mobile Transaction Database
In a mobile transaction database, users in the different user
groups may have different mobile transaction behaviors.
The first task we have to tackle is to cluster mobile
transaction sequences. We proposed a parameter-less
clustering algorithm CO-Smart-CAST.
Before performing the CO-Smart-CAST, we have to
generate a similarity matrix S, based on the mobile
transaction database. The entry Sij in matrix S represents
the similarity of the mobile transaction sequences i and j in
the database, with the degrees in the range of [0, 1]. A
mobile transaction sequence can be viewed as a sequence
string, where each element in the string indicates a mobile
transaction. The major challenge we have to tackle is to
measure the content similarity between mobile transactions.
We propose LBS-Alignment, which can obtain the
similarity based on the concept of DNA alignment [4]. LBSAlignment
is based on the consideration that two mobile
transaction sequences are more similar, when the orders and
timestamps of their mobile transactions are more similar.
Frequent-Transaction Mining
In this phase, we mine the frequent transactions (FTransactions)
in each user cluster and time interval by
applying a modified Apriori algorithm [2]. Table 1 shows
the mobile transaction database. In Sections 4.2 and 4.3,
there are two user clusters and two time intervals in the
database, i.e., C1 ¼ f1; 2; 4; 7g; C2 ¼ f3; 5; 6g; T1 ¼ f1-20g,
and T2 ¼ f21-32g. At first, the support of each cell and
service is counted in each user cluster and time interval
according to the user cluster table and time interval table.
We keep the patterns, i.e., frequent 1-transactions, whose
support satisfies the user-specified minimal support threshold
TSUP (TSUP sets as 2 in this example). A candidate 2-
transaction is generated by joining two frequent 1-transactions
if their user clusters, time intervals, and cells are the
same. For example, the candidate 2-transaction fS3; S4g is
generated by joining fS3g and fS4g, because the user
clusters, time intervals, and cells of both of them are
ðC1; T1; FÞ. Then, we keep the patterns, i.e., frequent 2-
transactions, whose support is larger than TSUP . Finally, the
same procedures are repeated until no candidate transaction
is generated. The frequent transactions are shown in
Table 3. Besides, we construct a service mapping table to
transform services into F-Transactions in Table 3.