High Utility Itemset Mining Using Transaction Utility of Itemsets
Serin Lee, Jong Soo Park · KIPS Transactions on Software and Data Engineering · 2015
높은 유틸리티 항목집합 마이닝은 트랜잭션 데이터베이스에서 사용자가 지정한 최솟값 이상의 유틸리티를 갖는 항목집합들을 항목의 수량과 가중치값을 동시에 고려하여 찾아내는 것이다. 최근에 연구된 유틸리티-리스트 기반의 높은 유틸리티 항목집합 마이닝 알고리즘은 많은 후보 항목집합들을 피하기 위해 제안되었으며 비용이 높은 조인 연산을 수행한다. 본 논문은 유틸리티-리스트 구조에 항목집합의 트랜잭션 유틸리티와 공통 유틸리티 속성을 추가한 새로운 알고리즘을 제안한다. 이 새로운 알고리즘은 조인 연산의 수를 줄이고 탐색 공간을 효과적으로 가지치기한다. 생성 데이터와 실 환경 데이터상의 실험 결과를 통해 제안된 알고리즘이 다른 최근 알고리즘들에 비해 실행 시간 면에서 아주 우수하고, 특히 데이터가 조밀하거나 항목집합의 길이가 긴 경우에 더 효율적이라는 것을 보여준다. High utility itemset(HUI) mining refers to the discovery of itemsets with high utilities which are not less than a user-specified minimum utility threshold, by considering both the quantities and weight factors of items in a transaction database. Recently the utility-list based HUI mining algorithms have been proposed to avoid numerous candidate itemsets and the algorithms need the costly join operations. In this paper, we propose a new HUI mining algorithm, using the utility-list with additional attributes of transaction utility and common utility of itemsets. The new algorithm decreases the number of join operations and efficiently prunes the search space. Experimental results on both synthetic and real datasets show that the proposed algorithm outperforms other recent algorithms in runtime, especially when datasets are dense or contain many long transactions.