궤적 그래프 집합 유사도 측정 기법 = A Method for Measuring Similarity between Trajectory Graph Sets

국문 초록 (Abstract)

GPS 센서가 내장된 스마트폰의 대중화에 따라 궤적 데이터 데이타베이스 구축이 용이해졌다. 최근 개인의 생활패턴을 반영할 수 있는 그래프 기반 궤적 데이터 모델링 방법이 제안되었다. 그러나 이 연구는 궤적 데이터 모델링 방법을 주로 제안하여, 개인화 서비스와 같은 응용 분야에 사용할 수 있는 마이닝 기법들은 제안하지 않았다. 본 논문에서는 궤적 그래프 집합으로 표현되는 사용자들 간의 유사도를 효과적으로 측정하는 기법을 제안한다. 제안하는 유사도 측정 기법은 사용자마다의 고유한 생활패턴 특징을 잘 반영할 수 있는 대표 빈발 부분그래프들을 찾아 유사도를 비교한다. 유사도를 효과적으로 계산하기 위하여, 집합 간의 거리 측정 알고리즘인 Hausdorff 거리와 두 그래프간의 유사도 측정 알고리즘인 최대 공통 부분그래프를 이용한 그래프 집합 유사도 측정 알고리즘을 제안한다. 실험을 통하여 제안하는 유사도측정 기법이 사용자 간의 유사도를 효과적으로 측정할 수 있음을 보인다.

다국어 초록 (Multilingual Abstract)

As a number of people use smart phones with embedded GPS sensors, it becomes easy to construct a trajectory data database. Recently, a graph based trajectory modeling study has been performed, which can reflect personal lifestyles. However, the study mainly has focused on a modeling method but not suggested mining techniques that can be used for applications such as personalized services. In this paper, we propose a method that measures a similarity between users represented by sets of trajectory graphs. The proposed method measures the similarity between users" feature frequent subgraphs, which imply each user"s essential lifestyles, rather than trajectory graphs. In order to effectively calculate the similarity, we propose a graph set similarity algorithm using Hausdorff distance for calculating a set similarity and maximum common subgraph for calculating a graph similarity. In the experiment, we show our proposed method can measure similarities between users effectively.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 궤적 그래프 집합의 유사도 측정
• 4. 실험 결과 및 분석
• 5. 결론 및 향후 연구
• 참고문헌

참고문헌 (Reference)

1 X. Yan, "gSpan: Graph-based substructure pattern mining" 2002

2 B. George, "Spatio- Temporal Sensor Graphs(STSG): A data model for the discovery of spatio-temporal patterns" 2009

3 H. Bunke, "Graph Distance Metric Based on the Maximal Common Subgraph" 19 (19): 255-259, 1998

4 Y. Zheng, "GeoLife: A Collaborative Social Networking Service among User, location and trajectory" 2010

5 D. P. Huttenlocher, "Comparing images using the Hausdor distance" 15 : 850-863, 1993

6 X. Gao, "A survey of graph edit distance" 2010

7 M. Dubuisson, "A Modified Hausdorff Distance for Object Matching" 1994

8 Jihye Hong, "A Method for Spatio-temporal Graph Modeling for Personalized Social Service" 39 (39): 22-24, 2012