Analyzing movement predictability using human attributes and behavioral patterns

The ability to predict human mobility, i.e., transitions between a user's significant locations (the home, workplace, etc.) can be helpful in a wide range of applications, including targeted advertising, personalized mobile services, and transportation planning. Most studies on human mobility prediction have focused on the algorithmic perspective rather than on investigating human predictability. Human predictability has great significance, because it enables the creation of more robust mobility prediction models and the assignment of more accurate confidence scores to location predictions. In this study, we propose a novel method for detecting a user's stay points from millions of GPS samples. Then, after detecting these stay points, a long short-term memory (LSTM) neural network is used to predict future stay points. We explore the use of two types of stay point prediction models (a general model that is trained in advance and a personal model that is trained over time) and analyze the number of previous locations needed for accurate prediction. Our evaluation on two real-world datasets shows that by using our preprocessing approach, we can detect stay points from routine trajectories with higher accuracy than the methods commonly used in this domain, and that by utilizing various LSTM architectures instead of the traditional Markov models and advanced deep learning models, our method can predict human movement with high accuracy of more than 40% when using the Acc@1 measure and more than 59% when using the Acc@3 measure. We also demonstrate that the movement prediction accuracy varies for different user populations based on their trajectory characteristics and demographic attributes.     

QS-STT: QuadSection clustering and spatial-temporal trajectory model for location prediction

Location prediction is a crucial need for location-aware services and applications. Given an object’s recent movement and a future time, the goal of location prediction is to predict the location of the object at the future time specified. Different from traditional location prediction using motion function, some research works have elaborated on mining movement behavior from historical trajectories for location prediction. Without loss of generality, given a set of trajectories of an object, prior works on mining movement behaviors will first extract regions of popularity, in which the object frequently appears, and then discover the sequential relationships among regions. However, the quality of the frequent regions extracted affects the accuracy of the location prediction. Furthermore, trajectory data has both spatial and temporal information. To further enhance the accuracy of location prediction, one could utilize not only spatial information but also temporal information to predict the locations of objects. In this paper, we propose a framework QS-STT (standing for QuadSection clustering and Spatial-Temporal Trajectory model) to capture the movement behaviors of objects for location prediction. Specifically, we have developed QuadSection clustering to extract a reasonable and near-optimal set of frequent regions. Then, based on the set of frequent regions, we propose a spatial-temporal trajectory model to explore the object’s movement behavior as a probabilistic suffix tree with both spatial and temporal information of movements. Note that STT is not only able to discover sequential relationships among regions but also derives the corresponding probabilities of time, indicating when the object appears in each region. Based on STT, we further propose an algorithm to traverse STT for location prediction. By enhancing the quality of the frequent region extracted and exploring both the spatial and temporal information of STT, the accuracy of location prediction in QS-STT is improved. QS-STT is designed for individual location prediction. For verifying the effectiveness of QS-STT for location prediction under the different spatial density, we have conducted experiments on four types of real trajectory datasets with different speed. The experimental results show that our proposed QS-STT is able to capture both spatial and temporal patterns of movement behaviors and by exploring QS-STT, our proposed prediction algorithm outperforms existing works.     

A Robust Missing Data-Recovering Technique for Mobility Data Mining

Based on location information, users’ mobility profile building is the main task for making different useful systems such as early warning system, next destination and route prediction, tourist guide, mobile users’ behavior-aware applications, and potential friend recommendation. For mobility profile building, frequent trajectory patterns are required. The trajectory building is based on significant location extraction and the user’s actual movement prediction. Previous works have focused on significant places extraction without considering the change in GSM (global system for mobile communication) network and is based on complete data analysis. Since network operators change the GSM network periodically, there are possibilities of missing values and outliers. These missing values and outliers must be addressed to ensure actual mobility and for the efficient extraction of significant places, which are the basis for users’ trajectory building. In this paper, we propose a methodology to convert geo-coordinates into semantic tags and we also purposed a clustering methodology for recovering missing values and outlier detection. Experimental results prove the efficiency and effectiveness of the proposed scheme.     

A regression-based approach for mining user movement patterns from random sample data

Mobile computing systems usually express a user movement trajectory as a sequence of areas that capture the user movement trace. Given a set of user movement trajectories, user movement patterns refer to the sequences of areas through which a user frequently travels. In an attempt to obtain user movement patterns for mobile applications, prior studies explore the problem of mining user movement patterns from the movement logs of mobile users. These movement logs generate a data record whenever a mobile user crosses base station coverage areas. However, this type of movement log does not exist in the system and thus generates extra overheads. By exploiting an existing log, namely, call detail records, this article proposes a Regression-based approach for mining User Movement Patterns (abbreviated as RUMP). This approach views call detail records as random sample trajectory data, and thus, user movement patterns are represented as movement functions in this article. We propose algorithm LS (standing for Large Sequence) to extract the call detail records that capture frequent user movement behaviors. By exploring the spatio-temporal locality of continuous movements (i.e., a mobile user is likely to be in nearby areas if the time interval between consecutive calls is small), we develop algorithm TC (standing for Time Clustering) to cluster call detail records. Then, by utilizing regression analysis, we develop algorithm MF (standing for Movement Function) to derive movement functions. Experimental studies involving both synthetic and real datasets show that RUMP is able to derive user movement functions close to the frequent movement behaviors of mobile users.     

A personal route prediction system based on trajectory data mining

This paper presents a system where the personal route of a user is predicted using a probabilistic model built from the historical trajectory data. Route patterns are extracted from personal trajectory data using a novel mining algorithm, Continuous Route Pattern Mining (CRPM), which can tolerate different kinds of disturbance in trajectory data. Furthermore, a client-server architecture is employed which has the dual purpose of guaranteeing the privacy of personal data and greatly reducing the computational load on mobile devices. An evaluation using a corpus of trajectory data from 17 people demonstrates that CRPM can extract longer route patterns than current methods. Moreover, the average correct rate of one step prediction of our system is greater than 71%, and the average Levenshtein distance of continuous route prediction of our system is about 30% shorter than that of the Markov model based method.     

基于自监督学习的社交网络用户轨迹预测模型

针对当前用户轨迹数据建模中存在的签到点稀疏性、长时间依赖性和移动模式复杂等问题,提出基于自监督学习的社交网络用户轨迹预测模型SeNext,对用户轨迹进行建模和训练来预测用户的下一个兴趣点（POI）。首先,使用数据增强的方式来丰富训练数据样本,以解决数据不足及个别用户足迹太少导致的模型泛化能力不足的问题;其次,将循环神经网络（RNN）、卷积神经网络（CNN）和注意力机制分别用于当前轨迹和历史轨迹的建模中,以此从高维稀疏的数据中提取有用的表示,用来匹配用户过去最相似的移动方式。最后,通过结合自监督学习并引入对比损失优化噪声对比估计（InfoNCE）,SeNext在潜在空间学习隐含表示来预测用户的下一个POI。实验结果表明,在纽约数据集上,SeNext比最新的VANext（Variational Attention based Next）模型的预测准确度在Top@1上提高了11.10%左右。     

Location query based on moving behaviors

The importance of location prediction is rapidly increasing with the current trend of database applications in mobile computing environment. However, current personal communication services network could only provide currently maintained location information of non-idle mobile terminals. Pertinent researches predict the future location based on tangent velocity approaches, which require mobile terminals to spend lots of precious electronic power to sense and then measure a sequence of positions for predicting the future tangent velocity, and the prediction is effective only within a short range of time. In this study, we propose an approach to predict future locations of mobile terminals based on the moving behaviors mined from their long-term moving history. Location prediction based on moving behavior requires no power consumption for position measurement, and the prediction results are effective for a long time without requiring the queried clients to be non-idle. With the help of moving behavior, we propose several location prediction operators for location query. Finally, we demonstrate the accuracy of the location query operators through simulation statistics. The experimental results show that the predictions are accurate enough for regular moving mobile terminals.     

基于Period-Near算法的用户移动位置预测

新浪微博是一种允许大量用户彼此分享包括位置在内的个人信息的电子媒介,它使得掌握用户的运动轨迹成为可能。尽管用户的运动和移动模式有着高度的自由性和多样性,但是周期性的运动是非常频繁的现象,因此寻找用户的周期行为对于了解用户的动作至关重要。在本文中将这个问题定义为“预测用户将要去哪里”,该问题涉及2个子问题：如何发现用户的历史行为以及如何应用用户的历史行为来预测其将来的行为。假设用户的行为是周期性的,并且如果用户在一个位置的时间足够长,那么他/她将会一直待在这个位置。基于这2个假设,提出一个4阶段算法Period-Near来解决这个问题。在算法的第1阶段挖掘用户的周期性行为,第2阶段发现其较为频繁的移动,第3阶段了解用户在最近一段时间所处的位置,第4阶段是根据前3个阶段来预测用户接下来将要去哪里。无论是在综合数据上还是实际数据上的实验研究均表明本文方法具有一定的有效性。     

Indexing Future Trajectories of Moving Objects in a Constrained Network

Advances in wireless sensor networks and positioning technologies enable new applications monitoring moving objects. Some of these applications, such as traffic management, require the possibility to query the future trajectories of the objects. In this paper, we propose an original data access method, the ANR-tree, which supports predictive queries. We focus on real life environments, where the objects move within constrained networks, such as vehicles on roads. We introduce a simulation-based prediction model based on graphs of cellular automata, which makes full use of the network constraints and the stochastic traffic behavior. Our technique differs strongly from the linear prediction model, which has low prediction accuracy and requires frequent updates when applied to real traffic with velocity changing frequently. The data structure extends the R-tree with adaptive units which group neighbor objects moving in the similar moving patterns. The predicted movement of the adaptive unit is not given by a single trajectory, but instead by two trajectory bounds based on different assumptions on the traffic conditions and obtained from the simulation. Our experiments, carried on two different datasets, show that the ANR-tree is essentially one order of magnitude more efficient than the TPR-tree, and is much more scalable.     

Mining moving patterns for predicting next location

Next location prediction has been an essential task for many location based applications such as targeted advertising. In this paper, we present three basic models to tackle the problem of predicting next locations: the Global Markov Model that uses all available trajectories to discover global behaviors, the Personal Markov Model that focuses on mining the individual patterns of each moving object, and the Regional Markov Model that clusters the trajectories to mine the similar movement patterns. The three models are integrated with linear regression in different ways. We then seek to further improve the accuracy of prediction by considering the time factor, with a focus on clustering the trajectories in different time periods, and present three methods to train the time-aware models to mine periodic patterns. Therefore, our proposed models have the following advantages: (1) we consider both individual and collective movement patterns in making prediction, (2) we consider the similarity between different trajectories, (3) we consider the time factor and build models that are suited to different time periods. We have conducted extensive experiments on a real dataset, and the results demonstrate the superiority of our proposed models over existing methods.     

Popular route planning with travel cost estimation from trajectories

With the increasing number of GPS-equipped vehicles,more and more trajectories are generated continuously,based on which some urban applications become feasible,such as route planning.In general,popular route that has been travelled frequently is a good choice,especially for people who are not familiar with the road networks.Moreover,accurate estimation of the travel cost(such as travel time,travel fee and fuel consumption)will benefit a wellscheduled trip plan.In this paper,we address this issue by finding the popular route with travel cost estimation.To this end,we design a system consists of three main components.First,we propose a novel structure,called popular traverse graph where each node is a popular location and each edge is a popular route between locations,to summarize historical trajectories without road network information.Second,we propose a self-adaptive method to model the travel cost on each popular route at different time interval,so that each time interval has a stable travel cost.Finally,based on the graph,given a query consists of source,destination and leaving time,we devise an efficient route planning algorithmwhich considers optimal route concatenation to search the popular route from source to destination at the leaving time with accurate travel cost estimation.Moreover,we conduct comprehensive experiments and implement our system by a mobile App,the results show that our method is both effective and efficient.     

情景感知驱动的移动对象多模式轨迹预测技术综述

如何利用多源异构时空数据进行准确的轨迹预测并且反映移动对象的移动特性是轨迹预测领域的核心问题.现有的大多数轨迹预测方法是长序列轨迹模式预测模型,根据历史轨迹的特点进行预测,或将当前移动对象的轨迹位置放入时空语义场景根据历史移动对象轨迹预测位置.综述当前常用的轨迹预测模型和算法,涉及不同的研究领域.首先,阐述了多模式轨迹预测的主流工作,轨迹预测的基本模型类;其次,对不同类的预测模型进行总结,包括数学统计类、机器学习类、滤波算法,以及上述领域具有代表性的算法;再次,对情景感知技术进行了介绍,描述了不同领域的学者对情景感知的定义,阐述了情景感知技术所包含的关键技术点,诸如情景感知计算、情景获取和情景推理的不同类模型,分析了情景感知的不同分类、过滤、存储和融合以及它们的实现方法等.详细介绍了情景感知驱动的轨迹预测模型技术路线及各阶段任务的工作原理.给出了情景感知技术在真实场景中的应用,包括位置推荐,兴趣点推荐等,通过与传统算法对比,分析情景感知技术在此类应用中的优劣.详细介绍了情景感知结合LSTM (long short-term memory)技术应用于行人轨迹预测领域的新方法.最后,总结了...     

Human mobility synthesis using matrix and tensor factorizations

Human mobility prediction is of great advantage in route planning and schedule management. However, mobility data is a high-dimensional dataset in which multi-context prediction is difficult in a single model. Mobility data can usually be expressed as a home event, a work event, a shopping event and a traveling event. Previous works have only been able to learn and predict one type of mobility event and then integrate them. As the tensor model has a strong ability to describe high-dimensional information, we propose an algorithm to predict human mobility in tensors of location context data. Using the tensor decomposition method, we extract human mobility patterns with multiple expressions and then synthesize the future mobility event based on mobility patterns. The experiment is based on real-world location data and the results show that the tensor decomposition method has the highest accuracy in terms of prediction error among the three methods. The results also prove the feasibility of our multi-context prediction model.     

Reducing the network overhead of user mobility–induced virtual machine migration in mobile edge computing

With the popularity of mobile devices (such as smartphones and tablets) and the development of the Internet of Things, mobile edge computing is envisioned as a promising approach to improving the computation capabilities and energy efficiencies of mobile devices. It deploys cloud data centers at the edge of the network to lower service latency. To satisfy the high latency requirement of mobile applications, virtual machines (VMs) have to be correspondingly migrated between edge cloud data centers because of user mobility. In this paper, we try to minimize the network overhead resulting from constantly migrating a VM to cater for the movement of its user. First, we elaborate on two simple migration algorithms (M-All and M-Edge), and then, two optimized algorithms are designed by classifying user mobilities into two categories (certain and uncertain moving trajectories). Specifically, a weight-based algorithm (M-Weight) and a mobility prediction–based heuristic algorithm (M-Predict) are proposed for the two types of user mobilities, respectively. Numerical results demonstrate that the two optimized algorithms can significantly lower the network overhead of user mobility–induced VM migration in mobile edge computing environments.     

Path prediction and predictive range querying in road network databases

In automotive applications, movement-path prediction enables the delivery of predictive and relevant services to drivers, e.g., reporting traffic conditions and gas stations along the route ahead. Path prediction also enables better results of predictive range queries and reduces the location update frequency in vehicle tracking while preserving accuracy. Existing moving-object location prediction techniques in spatial-network settings largely target short-term prediction that does not extend beyond the next road junction. To go beyond short-term prediction, we formulate a network mobility model that offers a concise representation of mobility statistics extracted from massive collections of historical object trajectories. The model aims to capture the turning patterns at junctions and the travel speeds on road segments at the level of individual objects. Based on the mobility model, we present a maximum likelihood and a greedy algorithm for predicting the travel path of an object (for a time duration h into the future). We also present a novel and efficient server-side indexing scheme that supports predictive range queries on the mobility statistics of the objects. Empirical studies with real data suggest that our proposals are effective and efficient.     

基于非参数密度估计的不确定轨迹预测方法

随着大量移动设备的出现，准确和高效的轨迹预测有助于提高面向位置的应用和服务的质量和水平.针对现有方法对轨迹不确定性缺乏有效建模的问题，提出了基于非参数密度估计的不确定轨迹终点预测方法.在轨迹建模及模型训练阶段，利用非参数估计对起点与终点相同的轨迹构建基于密度分布的不确定轨迹模型；在轨迹预测阶段，将待预测轨迹视为轨迹数据流，并通过KS（Kolmogorov-Smirnov）检验方法与具有相同起点的不确定轨迹模型进行匹配，其中匹配程度最高的不确定轨迹即为预测轨迹.通过真实轨迹数据集上的实验表明，与现有各类主要轨迹预测方法相比，本方法在不同条件下的预测效率与准确性都有较明显优势.     

Where are you going? Using human locomotion models for target estimation

To explore virtual environments that are larger than the available physical tracking space by real walking, it is necessary to use so-called redirected walking. Redirection techniques allow the user to explore an unlimited virtual environment in a limited tracking space by introducing a small mismatch between a user’s real and virtual movement, thus preventing the user from colliding with the physical walls of the tracking space. Steering algorithms are used to select the most suitable redirection technique at any given time, depending on the geometry of the real and virtual environment. Together with prediction of a user’s future walking path, these algorithms select the best redirection strategy by an optimal control scheme. In this paper, a new approach for the prediction of a person’s locomotion target is presented. We use various models of human locomotion together with a set of possible targets to create a set of expected paths. These paths are then compared to the real path the user already traveled to calculate the probability of a certain target being the one the user is heading for. A new approach for comparing paths with each other is introduced and is compared to three others. For describing the human’s path to a given target, four different models are used and compared. To gather data for the comparison of the models against the real path, a user study was conducted. Based on the results of the user study, the paper concludes with a discussion on the prediction performance of the different approaches.     

多模式移动对象不确定性轨迹预测模型

以移动设备、车辆、飞机、飓风等移动对象不确定性轨迹预测问题为背景,将大规模移动对象数据作为研究对象,以频繁轨迹模式挖掘、高斯混合回归技术为主要研究手段,提出多模式移动对象轨迹预测模型,关键技术包括:1）针对单一运动模式,提出一种基于频繁轨迹模式树FTP-tree的轨迹预测方法,利用基于密度的热点区域挖掘算法将轨迹点划分成不同的聚簇,构建轨迹频繁模式树,挖掘频繁轨迹模式预测移动对象连续运动位置.不同数据集上实验结果表明基于FTP-tree的轨迹预测算法在保证时间效率的前提下预测准确性明显优于已有预测算法.2）针对复杂多模式运动行为,利用高斯混合回归方法建模,计算不同运动模式的概率分布,将轨迹数据划分为不同分量,利用高斯过程回归预测移动对象最可能运动轨迹.实验证明,相比于基于隐马尔科夫模型和卡尔曼滤波的预测方法,所提方法具有较高的预测准确性和较低的时间代价.     

An experimental characterization of reservoir computing in ambient assisted living applications

In this paper, we present an introduction and critical experimental evaluation of a reservoir computing (RC) approach for ambient assisted living (AAL) applications. Such an empirical analysis jointly addresses the issues of efficiency, by analyzing different system configurations toward the embedding into computationally constrained wireless sensor devices, and of efficacy, by analyzing the predictive performance on real-world applications. First, the approach is assessed on a validation scheme where training, validation and test data are sampled in homogeneous ambient conditions, i.e., from the same set of rooms. Then, it is introduced an external test set involving a new setting, i.e., a novel ambient, which was not available in the first phase of model training and validation. The specific test-bed considered in the paper allows us to investigate the capability of the RC approach to discriminate among user movement trajectories from received signal strength indicator sensor signals. This capability can be exploited in various AAL applications targeted at learning user indoor habits, such as in the proposed indoor movement forecasting task. Such a joint analysis of the efficiency/efficacy trade-off provides novel insight in the concrete successful exploitation of RC for AAL tasks and for their distributed implementation into wireless sensor networks.