Research On The Semantic Location-aware Computing Based On Trajectory Data Mining

Pervasive computing, merging the physical world we living in and the virtual world in the information space, make it possible to transparently obtain digital service everytime and everywhere. The most outstanding feature of pervasive computing is context awareness, and context-aware computing means that the information space is able to be aware of the condition change of the physical world based on the contextual information, and trigger corresponding functions or provide corresponding services automatically to proactively adapt to the demand of the users. Location-aware computing is one of the most important research topics of the context-aware computing. The mission of location-aware computing is to automatically adjust the conditions and behaviors of the system to adapt to the users’demand by estimating the current location context, analyzing the historical location context and predicting the future location context.How to design intelligent, natural and efficient location-aware system based on location information is one of the most important problems of the pervasive computing domain. Since human movement is usually of high spatial and temporal regularity, discovering users’mobility regularity based on trajectory data analysis and utilizing it in combination with their current contextual information for information adaptation is regarded as an effective approach to improve the interaction efficiency and intelligence level of location-aware systems. However, there are two problems with the existing works. First, most of the existing works use spatio-temporal data with strong regularity for analysis, and thus cannot adapt to the uncertainty characterstics of the trajectory data in the pervasive computing environment (e.g. heterogeneous, noisy, incomplete, etc.). Second, existing works mostly focus on mobility regularity mining, and have not extracted the implicit personal semantic information (e.g. intention, living habits, social relations, etc.) from trajectory data. Therefore, it is difficult to represent the users’high-level context with the extracted low-level information. Besides, there lacks design guidance for the location-aware systems based on trajectory data mining. Aimming at these problems, this paper proposes the semantic location-aware computing based on trajectory data mining, which is to firstly extract users’high-level semantic information from three aspects (i.e. intention, behavioral regularity and social relations) based on trajectory data mining and then provide appropriate and efficient information adaptation based on the extracted semantic information. The purpose of the semantic location-aware computing is to tackle the low usability level and interaction efficiency problems of location-aware systems. This paper focuses on three aspects of problems, i.e. personal places and mobility patterns mining, high-level semantic information (i.e. intention, behavioral regularity and social relations) extraction, and the corresponding information adaptation methods. In general, the main contents and achievements of this paper consisit of the following aspects.(1) This paper proposes an approach for mining personally semantic places from GPS trajectories. The approach firstly adopts a hierarchical clustering algorithm which combines time-based clustering algorithm and density-based clustering algorithm to extract physical places in consideration of the temporal characteristic of the trajectory data, and then analyzes the temporal and spatial features of the physical places by using machine learning technique and a customized POI (Place of Interest) database to label them with semantic meanings. The proposed approach can obtain personal places with higher semantic level as compared with the existing places mining techniques.(2) This paper proposes mobility patterns mining algorithms with respect to trajectory data recorded based on two kinds of positioning technologies (i.e. GPS based positioning and cellular network based positioning). In GPS trajectory data based mobility patterns mining, the algorithm preprocesses the raw GPS trajectory data through three steps, i.e. path segmentation, candidate origin/destination extraction and space partitioning based abstraction, and then extracts mobility patterns by using a variant of the PrefixSpan algorithm. The proposed algorithm can tolerate the uncertainty characteristics of the personal GPS trajectory data to a great extent while maintaining the continuous property of mobility patterns so as to derive longer and more complete patterns. In cellular trajectory data based mobility patterns mining, the algorithm preprocesses the raw GSM trajectory data through segmentation, windowization, grouping and clustering, and then extracts mobility patterns by using an association rule mining algorithm. The proposed algorithm can effectively extract mobility patterns by countering the imprecision, oscillation and overlapping problems of cellular trajectory data.(3) For user intention semantics extraction problem, this paper proposes approaches for future movement prediction, including an adaptive multi-order Markov model used to improve location prediction performance and an integrated destination and future route prediction approach based on mobility patterns. The adaptive multi-order Markov model can improve prediction accuracy as well as reduce the influence of training data quality on prediction results by automatically adapting to appropriate order of Markov model according to the correlation between training data and input data. The integrated prediction approach creates index based on a prefix tree structure, and finds candidate mobility patterns through pattern matching procedure. The destination and future route are then predicted integratedly according to the probabilistic model of the tree. The proposed approach has the advantage of predicting longer future route.(4) For user behavior semantics extraction problem, this paper proposes an approach for routine behavior modeling and mining based on personal places extraction. The approach uses place preference matrix to model routine behaviors, and clusters place preference matrices to obtain routine behavior patterns. On the basis of routine behavior mining, this paper proposes a routine behavior based user similarity calculation approach to measure the similarity of their long-term living habits. The experimental results show that users could be effectively discriminated according to their occupation profiles based on the proposed similarity calculation approach, and thus demonstrate the effectiveness of representing users’long-term living habits based on their routine behavior patterns.(5) For user relation semantics extraction problem, this paper proposes an inter-human social relationship estimation approach for mobile social network and a personalized POI recommendation approach for location-based social network. For social relationship estimation, the approach estimates two users’social relationship types by analyzing their encounter patterns based on personally semantic places mining and proximity data. For personalized POI recommendation, the approach extracts POIs, social relation intensity and preference similarity based on collaborative trajectory data mining, and makes personalized recommendation in consideration of both users’social network and preference to improve the acceptable level of the POIs.(6) Based on the proposed trajectory data mining algorithms and user semantics extraction approaches, this paper implements a prototype of semantic location-aware computing platform. Taking advantage of the platform, this paper also designs and implements an intelligent daily tasks reminder system iReminder based on user intention semantics as a representative application. The analysis of the reminder system demonstrates the advantages of the semantic-based location-aware systems in comparison with the traditional location-based location-aware systems.