교통카드 트랜잭션 데이터베이스에서 순회 패턴 탐사 알고리즘들의 비교 및 분석

Abstract

최근 정보 산업 분야에서 데이터의 양적 팽창과 그러한 데이터를 유용한 정보와 지식으로 바꿔야 하는 필요성으로 인해 데이터 마이닝에 대한 연구가 활발히 이루어지고 있다. 이러한 데이터 마이닝 분야에서 새롭게 연구되고 있는 한 분야가 순회 패턴 탐사이다. 본 논문에서는 순차 패턴 탐사의 한 특별한 경우인 순회 패턴 탐사 문제에 대해 연구하였다. 객체들은 서로 연결되어 상호 접근이 허용되며 객체 사이의 접근은 서로 연결된 경로를 따라 일정한 방향성을 갖는다. 이러한 환경 하에서 객체들을 순차적으로 접근하는 일정한 패턴을 발견하고자 한다. 예를 들어, 버스나 지하철을 이용한 승객들의 이동 경로를 분석하여 일정한 패턴을 발견할 수 있다. 이러한 문제를 해결하기 위해 기존의 알고리즘들을 적용하여 해결하고자 했다. 즉, 순차 패턴 탐사 알고리즘인 GSP와 SPADE를 변형하여 적용한 GSP_V와 SPADE_V를 구현하였으며, 순회 패턴 탐사 알고리즘인 FS를 변형하여 적용한 FS_V를 구현하였다. 그리고 빠른 탐사를 위해 기존에 존재하는 알고리즘의 일부 특성에 다양한 자료구조를 복합 적용한 AVL(Array and Vertical List)를 구현하였다. 이렇게 구현한 알고리즘들에 대해 실세계 데이터인 대용량의 교통 카드 트랜잭션 데이터베이스를 적용시켜 보았고, 최소 지지도나 입력 데이터베이스 크기 등에 따른 각 알고리즘의 성능을 비교 분석해 보았다. |The major reason that data mining has attracted a great deal of attention in the information industry in recent years is due to the wide availability of huge amounts of data and the imminent need for turning such data into useful information and knowledge. Traversal pattern mining is an important data mining problem with broad applications. In this research, we examine the issue of mining traversal patterns among items in a transaction database by transportation cards, where each transaction consists of customer-id, transaction-id, and a list of the items such as stations between origins and destinations in a transaction. We derived algorithms to find out the traversal patterns. We implemented the algorithms and evaluated the performance.