08-10-2012, 01:38 PM
Mining Cluster-Based Temporal Mobile Sequential Patterns in Location-Based Service Environments
Mining Cluster.pdf (Size: 2.19 MB / Downloads: 46)
Abstract
Researches on Location-Based Service (LBS) have been emerging in recent years due to a wide range of potential
applications. One of the active topics is the mining and prediction of mobile movements and associated transactions. Most of existing
studies focus on discovering mobile patterns from the whole logs. However, this kind of patterns may not be precise enough for
predictions since the differentiated mobile behaviors among users and temporal periods are not considered. In this paper, we propose
a novel algorithm, namely, Cluster-based Temporal Mobile Sequential Pattern Mine (CTMSP-Mine), to discover the Cluster-based
Temporal Mobile Sequential Patterns (CTMSPs). Moreover, a prediction strategy is proposed to predict the subsequent mobile
behaviors. In CTMSP-Mine, user clusters are constructed by a novel algorithm named Cluster-Object-based Smart Cluster Affinity
Search Technique (CO-Smart-CAST) and similarities between users are evaluated by the proposed measure, Location-Based Service
Alignment (LBS-Alignment). Meanwhile, a time segmentation approach is presented to find segmenting time intervals where similar
mobile characteristics exist. To our best knowledge, this is the first work on mining and prediction of mobile behaviors with
considerations of user relations and temporal property simultaneously. Through experimental evaluation under various simulated
conditions, the proposed methods are shown to deliver excellent performance.
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. For the studies considering the
relation between location and service, Chen et al. [8]
proposed the path traversal patterns for mining web user
behaviors. Tseng and Tsui [33] first proposed the problem
of mining associated service patterns in mobile web
environments.
System Framework
Fig. 2 shows the proposed system framework. Our system
has an “offline” mechanism for CTMSPs mining and an
“online” engine for mobile behavior prediction.Whenmobile
users move within the mobile network, the information
which includes time, locations, and service requests will be
stored in the mobile transaction database. Table 1 shows an
example of mobile transaction database which contains seven
records. In the offline data mining mechanism,wedesign two
techniques and the CTMSP-Mine algorithm to discover the
knowledge. First, we propose the CO-Smart-CAST algorithm
to cluster the mobile transaction sequences. In this algorithm,
we propose the LBS-Alignment to evaluate the similarity of
mobile transaction sequences. Second, we propose a GAbased
time segmentation algorithm to find the most suitable
time intervals.
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.
Based on this concept, we specifically design the time penalty
(TP) and the service reward (SR) in the LBS-Alignment. The
base similarity score is set as 0.5. Two mobile transactions can
be aligned if their locations are the same. Otherwise, a
location penalty is generated to decrease their similarity
score.
Segmentation of Mobile Transactions
In a mobile transaction database, similar mobile behaviors
exist under some certain time segments. Hence, it is
important to make suitable settings for time segmentation
so as to discriminate the characteristics of mobile behaviors
under different time segments. We propose a GA-based
method to automatically obtain the most suitable time
segmentation table with common mobile behaviors. Fig. 7
shows the procedure of our proposed time segmentation
method, named Get Number of Time Segmenting Points
(GetNTSP) algorithm. The input data are a mobile transaction
database D and its time length T (line 01). The output
data are the number of time segmenting points (line 02). For
each item, we accumulate the total number of occurrences
at each time point (line 07 to line 11). Therefore, an item
(location, service) can draw a curve of count distribution, as
shown in Fig. 8. For all curves, we found the time points
with the largest change rate (line 13). We defined the change
rate as (c½i þ 1c½iÞ=ð1þc½i), where c½i represents the total
number of occurrences for the item at time point i. We
count occurrences of all these time points (line 15), and find
out the satisfied time points whose counts are larger than or
equal to the average of all occurrences from these ones, and
then, take these satisfied ones as a set of the time point
sequence (TPS) (line 17). In the time point sequence, we
calculate the average time distance a between two neighboring
time points (line 18). We calculate the number of
neighboring time point pairs, in which the time distance is
higher than a (line 19 to line 23). The result represents the
time segmentation count (line 24).
Discovery of CTMSPs
In order to mine the cluster-based temporal mobile
sequential patterns efficiently, we proposed a novel method
named CTMSP-Mine to achieve this mining procedure. The
basic idea of CTMSP-Mine is based on TJPF algorithm
proposed in [37]. However, the TJPF algorithm did not
consider the factors of user cluster and time interval, which
are essential in discovering the complete information
concerning personal mobile behaviors. In CTMSP-Mine,
both factors of user cluster and time interval are taken into
account such that the complete mobile sequential patterns
can be discovered. The entire procedures of CTMSP-Mine
algorithm can be divided into three main steps: 1) Frequent-
Transaction Mining, 2) Mobile Transaction Database Transformation,
and 3) CTMSP Mining.
CONCLUSIONS AND FUTURE WORK
In this paper, we have proposed a novel method, named
CTMSP-Mine, for discovering CTMSPs in LBS environments.
Furthermore, we have proposed novel prediction
strategies to predict the subsequent user mobile behaviors
using the discovered CTMSPs. In CTMSP-Mine, we first
propose a transaction clustering algorithm named COSmart-
CAST to form user clusters based on the mobile
transactions using the proposed LBS-Alignment similarity
measurement. Then, we utilized the genetic algorithm to
generate the most suitable time intervals.