Clustering of Human Movement Trajectories
based on Distributional Representations
Derived from Bi-directional LSTM Networkwith Geographical Coordinates
Hiroki Tanaka, Takeshi Saga, Satoshi Nakamura
Center for Advanced Intelligence Project, RIKENNara Institute of Science and Technology, Japan

2021/11/22

IEEE BigData 2021 workshop Applications of Big Data Technology in the Transport Industry

2021©Tanaka Riken-AIP TIA

Human Movement Trajectories
The ubiquity of such wearable devices as smartphones continues to deepen its
presence in modern societies
Possible to analyze and visualize people who are moving as part of a trajectory ofGPS big data
Cluster human movement trajectories using time-series distributional
representations
Calculated the distance of the representation vectors derived from neural networkmodels2021/11/22

2021©Tanaka Riken-AIP TIA

2/14

Distributional representations
By analyzing the trend of visiting routes, it will beutilized for effective tourism strategies and productdevelopment– Problem: The amount of data is huge and diverse,making it difficult to compare and analyze

The length of the pathways and the places
they pass through are varied and differed– Fixed-length vectorization of pathway:
distributional representationcomparable
2021/11/22

2021©Tanaka Riken-AIP TIA

3Clustering based on distributional representations
Human movement analysis by similarity of time series using distributed
representation [Crivellari+ 2019]– Consider behavioral proximity (semantic closeness of moving sequences)– Based on Mesh2Vec (Word2Vec applied to a human movement trajectories)
ID:12345
ID:12344

ID:12565
ID:12123
ID number for each point

2021/11/22

Similarity and clustering
Distributed representation

Sequence to distributed
representation

2021©Tanaka Riken-AIP TIA4Applying bi-directional LSTM for clustering
Baseline of this study

Human moving prediction using long short-term memory (LSTM) [Crivellari+ 2019]
Obtaining distributed representation of human moving series by using Bi-LSTM[Kubo et al., 2020]– It does not distinguish between forward and backward directions because our purpose is not
only to predict but to analyze human behaviors– Grouping similar distributed representations of time series by using hierarchical clustering

Clustering users based on similarity

ID series for each location

2021/11/22

2021©Tanaka Riken-AIP TIA5Objective of this researchPrevious work
– Use only discrete mesh-IDs as an input
ID:12345, Lat: 35.01, Long: 135.13

Problem in previous research– The geographical coordinates (latitude and longitude) ofeach point is not explicitly shown

Acquisition of distributed representation based on discrete mesh-ID andcontinuous latitude/longitude Information and its validity throughhierarchical clustering

2021/11/22

2021©Tanaka Riken-AIP TIA

ID:12344
Lat... Long...
ID:12565
Lat... .Long...
ID:12123
Lat... .Long...
ID series of moving series

6Proposed approach
Objective: Human movement clustering based on distributed representations
Proposal– Acquisition of distributed representation of time series by Bi-LSTM with additional geographicalcoordinates as the input– Effect of adding geographical coordinates using hierarchical clustering

Acquisition of the timeseries distributed
representation

2021/11/22

2021©Tanaka Riken-AIP TIA

Using the distributed
representation
for clustering

7

Predication and clustering
Step.2

Next Mesh-ID
Prediction

Step.1

Next latitude andlongitude prediction

distributed representation

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTMBi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Mesh-ID series (including embedded layer)

Mesh-ID series (including embedded layer)

latitude and longitude series

latitude and longitude series

2021/11/22

2021©Tanaka Riken-AIP TIA

8

Details of the prediction model

Next Mesh-ID
Prediction
Next latitude andlongitude prediction
Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Bi-LSTM

Mesh-ID series (including embedded layer)
latitude and longitude series

2021/11/22

2021©Tanaka Riken-AIP TIA

Prediction Target :- Last Mesh-ID- Last Latitude (Lat)- Last Longitude(Long)

Loss functionoptimized) :Lmesh : Cross entropy loss
L{Lat,Long} : Mean squared errorα, β : constants (1,1)

9Experimental evaluation
Dataset (provided by Agoop Corp)– Target areas: Tokyo, Japan– Mesh size : 100m squared– Total number of meshes (calculated from the area): 219,396– Period: January to March 2021
– Data separation ratio for training, validation, and testing: 8:1:1– Number of users for training : 35,888– Number of users for clustering : 36 (only more than 200 series length)

Hierarchical clustering– Cluster determination method: Ward's method– Distance measure: cosine distance– Cluster distance threshold: 1.2
2021/11/22

2021©Tanaka Riken-AIP TIA

10

Accuracy – last mesh prediction
We obtained more than 30% of accuracy (baseline: 21.5%)- Because the total number of mesh-IDs in Tokyo prefecture is 21,939 the random prediction would
obtain about 0.004% of accuracy- We had another experiment in data of the Kyoto area where the total number of mesh-IDs isaround 8000
- In such data, we obtained more than 50% of accuracy

2021/11/22

2021©Tanaka Riken-AIP TIA

11

Loss curve
The addition of latitude/longitude reduced the loss faster in the early stageMesh-ID cross entropy loss in a model of MeshID plus latitude/longitude2021/11/22

Mesh-ID cross entropy loss in a model of
Mesh-ID-only2021©Tanaka Riken-AIP TIA

12

Clustering
Clustering in a model of Mesh-ID plus latitude/longitude: four clusters

1

2021/11/22

2

32021©Tanaka Riken-AIP TIA

413

Cluster visualization (1)Clusters number 2 with top three nearest- These users moved around Itabashi-Ku and route 254

2021/11/22

2021©Tanaka Riken-AIP TIA

14

Cluster visualization (2)Clusters number 3 with top three nearest- These users moved around Hachioji and Nishi-Hachioji station

2021/11/22

2021©Tanaka Riken-AIP TIA

15

Conclusions
Proposed Bi-LSTM network and integrated additional geographical coordinates (latitude andlongitude information) into models to accurately predict the last mesh and constructed clusters
based on distributional representations
Future work
– The current method must conduct a heuristic analysis and researchers need to observe it, which is timeconsuming and expensive– To solve this problem, an objective analysis must be studied that incorporates such landmarks as points ofinterest (e.g., popular stores) and geographical features that are likely to be useful for predicting human
movement tendencies

2021/11/22

2021©Tanaka Riken-AIP TIA

16

2021/11/22

2021©Tanaka Riken-AIP TIA

17