비트맵을 사용한 닫힌 빈발 시퀀스 마이닝
Mining Frequent Closed Sequences using a Bitmap Representation
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
순차 패턴 탐사에 대한 연구는 대용량의 데이터베이스에서 사용자에 의해 주어지는 최소 지지도를 만족하는 빈발 시퀀스를 찾는 문제를 다룬다. 하지만 현재까지 이루어진 순차 패턴 탐사 방법은 빈발 시퀀스들의 길이가 길어지거나 최소 지지도가 상대적으로 낮게 주어진 상황에서는 생성되는 시퀀스가 기하급수적으로 많아져서 성능이 급격히 저하되는 문제점을 가지고 있다. 본 논문에서는 이 문제를 해결하기 위해서 모든 빈발 시퀀스의 정보를 포함하며 그 수가 현저히 적은 닫힌 빈발 시퀀스를 찾는 방법을 제안한다. 제안하는 알고리즘은 효율적으로 가지치기를 수행하기 위해서 깊이우선 탐색 방법으로 후보 시퀀스를 생성하고 데이터베이스를 비트맵으로 표현하여 비트 연산으로 지지도를 효율적으로 계산한다. 또한, 비트맵으로 표현된 시퀀스 특성을 이용하여 가지치기할 시퀀스를 적은 연산 비용으로 찾을 수 있다. 이런 장점을 통하여 제안한 방법이 지금까지 제안된 알고리즘보다 훨씬 빨리 닫힌 빈발 시퀀스를 찾는 것을 성능 실험을 통하여 확인하였다.
Abstract
Sequential pattern mining finds all of the frequent sequences satisfying a minimum support threshold in a large database. However, when mining long frequent sequences, or when using very low support thresholds, the performance of currently reported algorithms often degrades dramatically. In this paper, we propose a novel sequential pattern algorithm using only closed frequent sequences which are small subset of very large frequent sequences. Our algorithm generates the candidate sequences by depth-first search strategy in order to effectively prune. Using bitmap representation of underlying databases, we can effectively calculate supports in terms of bit operations and prune sequences in much less time. Performance study shows that our algorithm outperforms the previous algorithms.
참고문헌 (17)
- "Mining Association Rules in Large Databases", washington d.c. (1993)
- "Fast Algorithms for Mining Association Rules", santiago, pp.1994~
- "An Effective Hash-Based Algorithm for Mining Association Rules", san jose (1995)
- "An Efficient Algorithm for Mining Association Rules in Large Databases", zurich (1995)
- "Sampling Large Databases for Association Rules", bombay (1996)
- "Mining Sequential Patterns", taipei, pp.1995~
- "Mining Sequential Patterns : Generalizations and Performance Improvements", pp.3~17 (1996)
- "Discovering Frequent Episodes in Sequences" (1995)
- "Sequential Pattern Mining with Regular Expression Constraints" (1999)
- "Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth" (2001)
- "An Efficient Algorithm for Mining Frequent Sequences" (2001)
- "Sequential Pattern Mining using a Bitmap Representation" (2002)
- "An Efficient Algorithm for Mining Frequent Closed Itemsets" (2000)
- "A Maximal Frequent Itemset Algorithm for Transactional Databases" (2001)
- "An Efficient Algorithm for Closed Itemset Mining" (2002)
- "Mining Closed Sequential Patterns in Large Datasets" (2003)
- "Efficient Mining of Frequent Closed Sequences" (2004)