Journal of Internet Computing and Services (인터넷정보학회논문지)

Korean Society for Internet Information (한국인터넷정보학회)
권호 표지

Optimal Moving Pattern Mining using Frequency of Sequence and Weights

시퀀스 빈발도와 가중치를 이용한 최적 이동 패턴 탐사

  • 이연식 (군산대학교 컴퓨터정보공학과) ;
  • 박성숙 (한국폴리텍 V 김제 대학)
  • Published : 2009.10.30
Download PDF
⟨ Previous Next ⟩

Abstract

For developing the location based service which is individualized and specialized according to the characteristic of the users, the spatio-temporal pattern mining for extracting the meaningful and useful patterns among the various patterns of the mobile object on the spatio-temporal area is needed. Thus, in this paper, as the practical application toward the development of the location based service in which it is able to apply to the real life through the pattern mining from the huge historical data of mobile object, we are proposed STOMP(using Frequency of sequence and Weight) that is the new mining method for extracting the patterns with spatial and temporal constraint based on the problems of mining the optimal moving pattern which are defined in STOMP(F)[25]. Proposed method is the pattern mining method compositively using weighted value(weights) (a distance, the time, a cost, and etc) for our previous research(STOMP(F)[25]) that it uses only the pattern frequent occurrence. As to, it is the method determining the moving pattern in which the pattern frequent occurrence is above special threshold and the weight is most a little bit required among moving patterns of the object as the optimal path. And also, it can search the optimal path more accurate and faster than existing methods($A^*$, Dijkstra algorithm) or with only using pattern frequent occurrence due to less accesses to nodes by using the heuristic moving history.

사용자들의 특성에 맞게 개인화되고 세분화된 위치 기반 서비스를 개발하기 위한 목적으로 시공간 상에서 발생하는 이동 객체의 다양한 패턴들 중 의미있는 유용한 패턴을 추출하기 위한 시공간 패턴 탐사가 필요하다. 이에 본 논문에서는 방대한 이동 객체의 이력 데이터로부터 패턴 탐사를 통해 실세계에 적용 가능한 위치 기반 서비스의 개발에 대한 응용으로, STOMP(F)[25]에서 정의한 최적의 이동 패턴을 탐사하는 문제들을 기반으로 시간 및 공간 제약을 갖는 패턴을 추출하기 위한 새로운 탐사 기법인 STOMP(FW)를 제안한다. 제안된 기법은 패턴 빈발도 만을 이용한 기존 연구(STOMP(F)[25])에 가중치(거리, 시간, 비용 등)를 복합적으로 이용하는 패턴 탐사 방법으로, 특정한 지점들 사이를 이동한 객체의 이동 패턴들 중 패턴 빈발도가 특정 임계치 이상이고 가중치가 가장 적게 소요되는 이동 패턴을 최적 경로로 결정하는 방법이다. 제안된 방법의 패턴 탐사는 경험적인 이동 이력을 사용함으로써 기존의 최적 경로 탐색 기법들($A^*$, Dijkstra 알고리즘)이나 빈발도 만을 이용한 방법들 보다 접근하는 노드 수가 상대적으로 적어 보다 빠르고 정확하게 최적 패턴을 탐색할 수 있음을 보인다.

Keywords

References

  1. A. P. Sistla, O. Wolfson, S.Chamberlain and S. Dao, “Querying the Uncertain Position of Moving Objects”, Temporal Databases: Research and Practice, Springer Verlag Lecture Notes in Computer Science number 1399, 1998.
  2. O. Wolfson, S. Chamberlain, S. Dao, L. Jiang and G. Mendez, “Cost and Imprecision in Modeling the Position of Moving Objects”, in proc. on the 14th International Conference on Data Engineering, 1998.
  3. O. Wolfson, A. P. Sistla, B. Xu, J. Zhou and S. Chamberlain, “DOMINO : Databases fOr MovINg Objects tracking”, in proc. ACM SIGMOD Symp. on the Management of Data, 1999.
  4. O. Wolfson, B. Xu, J. Zhou, S. Chamberlain, Y. Yesha and N. Rishe, “Tracking Moving Objects Using Database Technology in DOMINO”, in proc. on The Fourth Workshop on Next Generation Information Technologies and Systems(NGITS), pp.112-119, July 1999.
  5. D. O. Kim, H. K. Kang, D. S. Hong, J. K. Yun and K. J. Han, “STMPE : An Efficient Movement Pattern Extraction Algorithm for Spatio-temporal Data Mining”, in proc. on International Conference on Computational Science and Its Applications(ICCSA), pp.259-269, 2006.
  6. N. Mamoulis, H. Cao, G. Kollios, M. Hadjieleftheriou, Y. Tao and D. W. Cheung, “Mining, Indexing and Querying Historical Spatio-Temporal Data”, in proc. on the International Conference on Knowledge Discovery and Data Mining, 2004.
  7. H. Cao, N. Mamoulis and D. W. Cheung, “Mining Frequent Spatio-Temporal Sequential Patterns”, in proc. on the 5th IEEE International Conference on Data Mining(ICDM), pp.82-89, 2005.
  8. Y. Huang, L. Zhang and P. Zhang, “Finding Sequential Patterns from a Massive Number of Spatio-Temporal Events”, SDM, SIAM, 2006.
  9. J. W. Lee, O. H. Paek and K. H. Ryu, “Temporal Moving Pattern Mining for Location-Based Service”, The Journal of Systems and Software, Vol.73. 2004.
  10. G. Yavas, D. Katsaros, O. Ulusoy and Y. Manolopoulos, “A Data Mining Approach for Location Prediction in Mobile Environmensts”, Data & Knowledge Engineering, Vol.54, pp.121-146, 2005. https://doi.org/10.1016/j.datak.2004.09.004
  11. S. Y. Hawng, Y. H. Liu, J. K. Chiu and E. P. Lim, “Mining Mobile Group Patterns : A Trajectory-based Approach”, PAKDD, Lecture Notes in Computer Science, Springer, Vol.3518, pp.713-718, 2005.
  12. Y. Wnag, E. P. Lim and S. Y. Hwang, “On Mining Group Patterns of Mobile Users”, DEXA, Lecture Notes in Computer Science, Springer, Vol.2736, pp.287-296, 2003.
  13. J. Gudmundsson, M. V. Kreveld and B. Speckmann, “Efficient Detection of Motion Patterns in Spatio-Temporal Data Sets”, in proc. on the 12th annual ACM international workshop on Geographic Information Systems(GIS), pp.250- 257, 2004.
  14. P. Laube and S. Imfeld, “Analyzing Relative Motion within Groups of Trackable Moving Point Object”, in GIScience, Notes in Computer Science, Springer, Vol.2478, pp.132-144, 2002.
  15. 김도현, 진희채, “텔레메틱스와 위치 기반 서비스를 위한 차세대 통신 기술”, 한국멀티미디어학회지, 제7권, 제4호, pp.40-51. 2003.
  16. 최희옥, 김남진, “웹 서비스를 이용한 텔레매틱스 기술의 응용”, 한국정보처리학회지 논문지,제9권, 제4호, 2002.
  17. 유한경, “SMS와 GPS를 활용한 실시간 물류상황 관제시스템의 개발”, 인천대학교 대학원, 석사학위논문, 2004.
  18. 안윤애, 김동호, 류근호, “차량위치 추적을 위한 이동객체 관리 시스템의 설계”, 한국정보처리학회 논문지, 제9-D권, 제5호, 2002.
  19. 안윤애, 류근호, “이동 객체의 불확실한 과거 및 미래의 위치 추정”, 한국정보처리학회 논문지 : 데이터베이스, 제29권, 제6호, 2002.
  20. 안윤애, 류근호, “이동 객체의 과거 및 미래의 위치 연산을 위한 데이터 모델”, 한국정보처리학회 논문지, 제10-D권, 제1호, 2003.
  21. 백옥현, “위치 기반 서비스를 위한 이동 객체의 시간 패턴 탐사 기법”, 충북대학교 대학원, 석사학위논문, 2002.
  22. 이준욱, “위치 기반 서비스를 위한 이동 객체의 시간 패턴 탐사”, 한국정보과학회 논문지, 제29권, 제5호, 2002.
  23. 이준욱, “지식 탐사 프레임워크 기반의 시공간이동 패턴 탐사 기법”, 충북대학교 대학원, 박사학위논문, 2003.
  24. 한선영, “시공간 이동 시퀀스 패턴 마이닝 기법”, 이화여자대학교 대학원, 석사학위논문, 2006.
  25. 고 현, 이연식, “이동 시퀀스의 빈발도를 이용한 최적 이동 패턴 탐사 기법”, 한국정보처리학회논문지, 제16-D권, 제1호, 2009.