이동 시퀀스의 빈발도를 이용한 최적 이동 패턴 탐사 기법
A Method for Optimal Moving Pattern Mining using Frequency of Moving Sequence
0
조회
0
다운로드
3
인용
0
참고문헌
키워드
초록
기존의 패턴 탐사 기법들은 제한된 시간 및 공간영역에서 발생하는 다양한 이동 패턴들 중 단순히 사용자 요구에 적합할 것으로 추정되는 불특정한 빈발 이동 패턴만을 탐사하기 때문에 특정지점들 간의 최적 이동 경로나 정해진 시간 내의 스케줄링 경로 탐색과 같은 복합적인 시간 및 공간 제약 조건을 갖는 최적 이동 패턴을 탐사하는 문제에는 적용하기 어렵다. 이에 본 논문에서는 방대한 이동 객체의 이력 데이터 집합으로부터 복합적인 시간 및 공간 제약을 갖는 최적 이동 패턴을 탐사하는 문제를 보이고, 적용 가능한 위치 기반 서비스로서 최적 이동 경로에 해당하는 패턴을 탐색하기 위한 새로운 패턴 탐사 기법인 STOMP-F를 제안한다. 제안된 기법은 특정한 지점들 사이를 이동한 객체의 패턴들 중 객체가 가장 빈번하게 이동한 경로를 탐색하여 최적 경로로 결정하는 패턴 빈발도를 이용한 탐색 방법으로, 최적 이동 패턴 탐사 과정의 이동 시퀀스 생성 단계에서 객체의 위치 값과 공간영역 간의 위상 관계를 고려하여 이동 객체의 위치 속성에 대한 최하위 수준에서의 공간 일반화를 통해 보다 효율적으로 패턴 탐사를 수행할 수 있다. 제안 방법을 Dijkstra 알고리즘과 A* 알고리즘을 대상으로 실험 평가한 결과 A* 알고리즘의 휴리스틱 가중치에 따라 차이는 있으나 연산 처리 시간을 기준으로 타 알고리즘들 보다 효과적임을 알 수 있다.
Abstract
Since the traditional pattern mining methods only probe unspecified moving patterns that seem to satisfy users' requests among diverse patterns within the limited scopes of time and space, they are not applicable to problems involving the mining of optimal moving patterns, which contain complex time and space constraints, such as 1) searching the optimal path between two specific points, and 2) scheduling a path within the specified time. Therefore, in this paper, we illustrate some problems on mining the optimal moving patterns with complex time and space constraints from a vast set of historical data of numerous moving objects, and suggest a new moving pattern mining method that can be used to search patterns of an optimal moving path as a location-based service. The proposed method, which determines the optimal path(most frequently used path) using pattern frequency retrieved from historical data of moving objects between two specific points, can efficiently carry out pattern mining tasks using by space generalization at the minimum level on the moving object's location attribute in consideration of topological relationship between the object's location and spatial scope. Testing the efficiency of this algorithm was done by comparing the operation processing time with Dijkstra algorithm and A* algorithm which are generally used for searching the optimal path. As a result, although there were some differences according to heuristic weight on A* algorithm, it showed that the proposed method is more efficient than the other methods mentioned.
참고문헌 (16)
- D. O. Kim, "STMPE : An Efficient Movement Pattern Extraction Algorithm for Spatio-temporal Data Mining", proc. on International Conference on Computational Science and Its Applications(ICCSA), pp.259~269 (2006)
- N. Mamoulis, "Mining, Indexing and Querying Historical Spatio-Temporal Data", proc. on the International Conference on Knowledge Discovery and Data Mining (2004)
- H. Cao, "Mining Frequent Spatio-Temporal Sequential Patterns", proc. on the 5th IEEE International Conference on Data Mining(ICDM), pp.82~89 (2005)
- Y. Huang, "Finding Sequential Patterns from a Massive Number of Spatio-Temporal Events" (2006), SDM, SIAM
- J. W. Lee, "Temporal Moving Pattern Mining for Location-Based Service", The Journal of Systems and Software, 73 (2004)
- G. Yavas, "A Data Mining Approach for Location Prediction in Mobile Environmensts", Data & Knowledge Engineering, 54, pp.121~146 (2005)
- S. Y. Hawng, "Mining Mobile Group Patterns : A Trajectory-based Approach", PAKDD, Lecture Notes in Computer Science, 3518, pp.713~718 (2005), Springer
- Y. Wnag, "On Mining Group Patterns of Mobile Users", DEXA, Lecture Notes in Computer Science, 2736, pp.287~296 (2003), Springer
- J. Gudmundsson, "Efficient Detection of Motion Patterns in Spatio-Temporal Data Sets", proc. on the 12th annual ACM international workshop on Geographic Information Systems(GIS), pp.250~257 (2004)
- P. Laube, "Analyzing Relative Motion within Groups of Trackable Moving Point Object", GIScience, Notes in Computer Science, 2478, pp.132~144 (2002), Springer
- 백옥현, "위치 기반 서비스를 위한 이동 객체의 시간 패턴 탐사 기법", 석사, pp.2002
- 이준욱, "위치 기반 서비스를 위한 이동 객체의 시간 패턴 탐사 기법", 정보과학회논문지 : 데이타베이스, 29(5), pp.335~346 (2002), 한국정보과학회
- 이준욱, "지식 탐사 프레임워크 기반의 시공간 이동 패턴 탐사 기법", 박사, pp.2003
- 한선영, "시공간 이동 시퀀스 패턴 마이닝 기법", 석사, pp.2006
- 박지웅, "시공간 이동 패턴 추출을 위한 효율적인 알고리즘", 박사, pp.2006
- 고현, "R*-Tree와 Grid를 이용한 이동 객체의 위치 일반화 기법", 한국컴퓨터정보학회논문지, 12(2), pp.231~242 (2007), 한국컴퓨터정보학회