Route prediction is one of the main areas of trajectory data mining, which is to predict the next location of a moving object from the partial historical trajectory. To predict the next location of the moving object, it is important to know the next locations reachable from the current location. A road network has various types of topologies, and the trajectories are generated constrained by the topology of the road network. Using topology information helps a prediction model to get better route prediction performance because it lets the model know the next locations reachable from the current location. Existing methods of grid embedding for trajectory data mining consider mostly spatial proximity between two grids during the embedding process. However, this approach is not suitable for the route prediction because it embeds the locations which are spatially close but unreachable as similar representations into latent space. In this paper, we propose a grid embedding method considering the topology of road networks, which defines topological similarities between grids based on their spatial proximity and connectivity. As a result, our method improves route prediction performance by embedding topologically similar grids close together in a latent space. Experiments on real taxi trajectory data demonstrate that our method improves accuracy by 3.0~220.7% compared with existing methods.
이동경로 예측은 움직이는 객체가 지나온 경로로부터 다음 위치를 예측하는 작업으로 이동경로 데이터마이닝의 주요 분야 중 하나이다. 이동경로를 예측하기 위해서는 현재 위치로부터 도달가능한 다음 위치들을 파악하는 것이 중요하다. 도로 네트워크에는 다양한 형태의 토폴로지가 존재하며 이동경로는 도로 네트워크의 토폴로지에 따라 제약적으로 생성된다. 이러한 도로 네트워크의 토폴로지 정보는 현재 위치로부터 도달 가능한 다음 위치들에 대한 내용를 포함하고 있어 이를 이동경로 예측 모델에 활용하면 예측 성능을 향상시킬 수 있다. 이동경로 데이터마이닝을 위해 그리드 임베딩을 수행한 기존 연구는 임베딩 과정에서 그리드들 간의 공간적 근접성을 고려하였다. 하지만, 이는 공간적 거리는 가깝지만 도달할 수 없는 지역을 잠재 공간 내에 서로 가깝게 임베딩하게되는 문제가 발생하기 때문에 이동경로 예측 문제에 적합하지 않다. 본 연구에서는 도로 네트워크의 토폴로지를 고려하는 그리드 임베딩 방법을 제안한다. 제안하는 방법론은 공간적 근접성과 연결성을 기반으로 그리드들 간의 토폴로지적 유사도를 정의하고 서로 유사한 그리드들을 잠재 공간에서 서로 가깝게 임베딩하여 이동경로 예측 성능을 향상시킨다. 실제 택시 이동경로 데이터를 활용한 이동경로 예측 실험에서 제안한 방법론이 기존의 방법들보다 3.0~220.7% 높은 정확도를 보였다.
