隨著基於位置的服務的出現，用戶移動預測已成為許多應用程序的關鍵驅動
因素。在本文中，我們提出了一種具有多對一遞歸神經網絡和加速點挖掘
（MRAPM）的移動預測框架。首先，我們透過提出的POI 挖掘方法- Acceleration
Clustering，從用戶的移動數據中提取用戶經常訪問的地方（Points of interest,
POIs）。然後，我們提出了自適應映射方法來將用戶的軌跡映射到一POI 序列。
接下來，我們使用具有長期短期記憶（Long Short-Term Memory, LSTM）和兩個
輸出層的遞歸神經網絡（Recurrent Neural Network, RNN）來學習用戶的POI 序
列。最後，我們用兩個不同的真實數據集評估預測性能。我們還將MRAPM 與
其他預測框架進行比較，並驗證MRAPM 比以前的作品具有更好的預測準確性。

With the emergence of location-based services, user mobility prediction has become a key driver for many applications. In this paper, we propose a mobility prediction framework with Many-to-one Recurrent neural network and Acceleration Points Mining (MRAPM). First, we extract the place where the user frequently visited (points of interest, POIs) from the user's mobility data through the proposed POI mining method– Acceleration Clustering. Then, we proposed the Adaptive Mapping method to map the user’s trajectory to a series of POIs. Afterward, we use the Recurrent Neural Network (RNN) with Long Short-Term Memory (LSTM) and two output layers to learn the user's POI series. Finally, we evaluate the prediction performance with two different real datasets. We also compare the MRAPM with other prediction frameworks and verify that the MRAPM has better prediction accuracy than previous works.

I. Introduction ........................................................................................................ 1
II. Related Work ...................................................................................................... 4
2.1 POIs Identification ........................................................................................ 4
2.2 Mobility Prediction ........................................................................................ 5
III. Many-to-one Recurrent Neural Network and Acceleration Points Mining
(MRAPM) .......................................................................................................... 9
3.1 Preprocess user’s mobility data ..................................................................... 9
3.2 Find Out the POIs of the User ..................................................................... 10
3.3 Calculate the POI Series of the User ........................................................... 14
3.4 Predictor Training ........................................................................................ 15
3.4.1 Training Data Generator ....................................................................... 16
3.4.2 Data Standardizing ............................................................................... 17
3.4.3 Predictor Designing .............................................................................. 17
IV. Performance Evaluation .................................................................................... 20
4.1 Experiment Definition ................................................................................. 20
4.2 Other Mobility Prediction Frameworks Implementation ............................ 21
4.3 Environment ................................................................................................ 23
4.4 Results ......................................................................................................... 23
V. Conclusion ....................................................................................................... 31
References .................................................................................................................... 32

[1] Q. Lv, Y. Qiao, N. Ansari, J. Liu, and J. Yang, “Big Data-Driven Hidden Markov
Model Based Individual Mobility Prediction at Points of Interest,” IEEE
Transactions on Vehicular Technology, Vol. 66, No. 6, pp. 5204-5216, Sep. 2016.
[2] X. Chen, D. Shi, B. Zhao, and F. Liu, “Periodic Pattern Mining Based on GPS
Trajectories,” 2016 International Symposium on Advances in Electrical,
Electronics and Computer Engineering, pp. 181-187, Guangzhou, China, Mar.
2016
[3] J. A. Lozano, J. A. G. Macías, and E. Chávez, “Crowd Location Forecasting at
Points of Interest,” International Journal of Ad Hoc and Ubiquitous Computing,
Vol. 18, Issue 4, pp. 191-204, Nov. 2015.
[4] J. H. Kang, W. Welbourne, B. Stewart, and G. Borriello, “Extracting Places from
Traces of Locations,” Proceedings of the 2nd ACM International Workshop on
Wireless Mobile Applications and Services on WLAN Hotspots, pp. 110-118,
Philadelphia, Pennsylvania, USA, Oct. 2004.
[5] M. H. Wong, V. S. Tseng, J. C. C. Tseng, S. W. Liu, and C. H. Tsai, “Long-Term
User Location Prediction Using Deep Learning and Periodic Pattern Mining,”
Advanced Data Mining and Applications: 13th International Conference, pp.
582-594, Singapore, Oct. 2017
[6] H. Ko, J. Lee, and S. Pack, “MALM: Mobility-Aware Location Management
Scheme in Femto/Macrocell Networks,” IEEE Transactions on Mobile Computing,
Vol. 16, Issue 11, pp. 3115-3125, Mar. 2017.
[7] Y. Endo, K. Nishida, H. Toda, and H. Sawada, “Predicting Destinations from
Partial Trajectories Using Recurrent Neural Network,” Pacific-Asia Conference on
Knowledge Discovery and Data Mining, pp. 160-172, Jeju, Korea, Aug. 2017
[8] Q. Liu, S. Wu, L. Wang, and T. Tan, “Predicting the Next Location: A Recurrent
Model with Spatial and Temporal Contexts,” Proceedings of the Thirtieth AAAI
Conference on Artificial Intelligence (AAAI-16), pp. 194-200, Phoenix, Arizona,
USA, Feb. 2016.
[9] A. Y. Xue, J. Qi, X. Xie, R. Zhang, J. Huang, and Y. Li, “Solving the Data Sparsity
Problem in Destination Prediction,” The VLDB Journal, Vol. 24, Issue 2, pp.
219-243, Apr. 2015.
[10] K. Greff, R. K. Srivastava, J. Koutník, B. R. Steunebrink, and J. Schmidhuber,
“LSTM: A Search Space Odyssey,” IEEE Transactions on Neural Networks and
Learning Systems, Vol. 28, Issue 10, pp. 2222-2232, Jul. 2016.
[11] J. C. Chen [Personnel survey]. Unpublished raw data, Department of Computer
Science, National Chiao Tung University, 2017.
33
[12] Y. Zheng, L. Zhang, X. Xie, and W. Y. Ma, “Mining Interesting Locations and
Travel Sequences from GPS Trajectories,” Proceedings of the 18th International
Conference on World Wide Web, pp. 791-800, Madrid, Spain, Apr. 2009.
[13] Y. Zheng, Q. Li, Y. Chen, X. Xie, and W. Y. Ma, “Understanding Mobility Based
on GPS Data,” Proceedings of ACM conference on Ubiquitous Computing
(UbiComp 2008), pp. 312-321, Seoul, Korea, Sep. 2008.
[14] Y. Zheng, X. Xie, and W. Y. Ma, “GeoLife: A Collaborative Social Networking
Service among User, Location, and Trajectory,” IEEE Data Engineering Bulletin.
33, pp. 32-40. Jun. 2010.
[15] A. Furno, M. Fiore, R. Stanica, C. Ziemlicki, and Z. Smoreda, “A Tale of Ten
Cities: Characterizing Signatures of Mobile Traffic in Urban Areas,” IEEE
Transactions on Mobile Computing, Vol. 16, Issue 10, pp. 2682-2696, Dec. 2016.
[16] M. Ester, H. P. Kriegel, J. Sander, and X. Xu, “A Density-Based Algorithm for
Discovering Clusters in Large Spatial Databases with Noise,” KDD'96 Proceedings
of the Second International Conference on Knowledge Discovery and Data Mining,
pp. 226-231, Portland, Oregon, USA, Aug. 1996.
[17] J. Krumm and E. Horvitz, “Predestination: Inferring Destinations from Partial
Trajectories,” International Conference on Ubiquitous Computing, pp. 243-260,
Orange County, California, USA, Sep. 2006.
[18] B. D. Ziebart, A. L. Maas, A. K. Dey, and J. A. Bagnell, “Navigate Like a Cabbie:
Probabilistic Reasoning from Observed Context-Aware Behavior,” UbiComp '08
Proceedings of the 10th International Conference on Ubiquitous Computing, pp.
322-331, Seoul, Korea, Sep. 2008.
[19] M. T. H. Elbatta and W. M. Ashour, “A Dynamic Method for Discovering Density
Varied Clusters,” International Journal of Signal Processing, Image Processing
and Pattern Recognition, Vol. 6, No. 1, pp. 123-134, Feb. 2013.
[20] S. A. Yaseen, O. Q. Aziz, and B. H. A. Bakar, “Prediction of Shear Strength of
Ultra High-Performance Reinforced Concrete Deep Beams without Stirrups by
Neural Network,” Eurasian Journal of Science & Engineering, Vol. 3, Issue. 1,
pp.142-164, Sep. 2017.
[21] A. L. Maas, A. Y. Hannun, and A. Y. Ng, “Rectifier Nonlinearities Improve
Neural Network Acoustic Models,” Proceedings of the 30th International
Conference on Machine Learning, Atlanta, Georgia, USA, Jun. 2013
[22] C. M. Bishop, Pattern Recognition and Machine Learning, New York : Springer,
pp. 198, 2007.
[23] P. T. D. Boer, D. P. Kroese, S. Mannor, and R. Y. Rubinstein, “A Tutorial on the
Cross-Entropy Method,” Annals of Operations Research, Vol. 134, Issue 1, pp.
19-67, Feb. 2005.
34
[24] D. P. Kingma and J. L. Ba, “Adam: A Method for Stochastic Optimization,”
International Conference on Learning Representations, pp. 1-15, San Diego,
California USA, May 2015.
[25] hmmlearn: https://github.com/hmmlearn/hmmlearn
[26] Keras: https://keras.io/
[27] scikit-learn.DBSCAN:
http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html