유틸리티-리스트 기반의 Top-K 높은 유틸리티 패턴 마이닝

Abstract

Top-k 높은 유틸리티 패턴 마이닝은 사용자가 지정한 k 값을 이용해 트랜잭션 데이터베이스에서 항목의 유틸리티를 기준으로 상위 k개의 항목집합을 찾아내는 것이다. 기존의 top-k 높은 유틸리티 패턴 알고리즘은 재귀적으로 트리를 구축하여 패턴을 성장시키는 기법을 기반으로 두 단계에 걸쳐 마이닝을 수행한다. 이는 많은 후보 생성과 그 후보들의 실제 유틸리티를 계산하기 위한 추가적인 데이터베이스 스캔을 필요로 한다. 본 논문에서는 효율적으로 top-k 높은 유틸리티 패턴을 찾기 위해 새로운 알고리즘, TKUL-Miner를 제안한다. 이 알고리즘은 탐색 트리에서 항목집합을 마이닝하기 위해 각 노드에 필요한 정보를 저장하는 유틸리티-리스트 구조를 이용한다. 제안하는 알고리즘은 패턴의 최대 유틸리티가 높은 구간을 먼저 탐색하는 탐색 순서 전략으로 최소 유틸리티를 빠르게 증가시킨다. 그리고 보다 작은 유틸리티 상한 값을 계산하는 두 개의 추가적인 전략들로 유망하지 않은 항목집합들을 효과적으로 가지치기 한다. 다양한 데이터에 대한 실험 결과를 통해 제안하는 알고리즘이 최신 알고리즘들 보다 실행시간과 사용 메모리 관점에서 모두 성능을 개선하고, 특히 조밀한 분포의 데이터인 경우와 평균 트랜잭션의 길이가 긴 경우 제안 알고리즘의 성능이 더욱 효율적이라는 것을 보여준다.|Top-k high utility itemset mining refers to the discovery of top-k patterns using given user-specified value k by considering the utility of items in a transactional database. Since existing top-k high utility itemset mining algorithms are based on pattern-growth method, they search the patterns in two steps. Therefore, the generation of many candidates and additional database scan for calculating exact utilities are unavoidable. In this paper, we propose a new algorithm, TKUL-Miner, to mine top-k high utility itemsets efficiently. It utilizes a new utility-list structure which stores necessary information at each node on the search tree for mining the itemsets. The proposed algorithm has a strategy using search order for specific region to raise the border minimum utility threshold rapidly. Moreover, two additional strategies for calculating smaller overestimated utilities are suggested to prune unpromising itemsets effectively. Experimental results on various datasets showed that the TKUL-Miner outperforms other recent algorithms both in runtime and memory efficiency.