FP-tree를 이용하여 항목 제한 조건을 만족하는 연관 규칙 탐사

Abstract

데이터 마이닝이란 대용량의 데이터베이스로부터 숨겨져 있는 규칙적인 패턴이나 유용한 정보를 추출하는 방법론을 의미한다. 데이터 마이닝의 중요한 분야 중 하나인 연관 규칙 탐사는 그 동안 많은 연구가 이루어져왔다. 연관 규칙 탐사란 데이터베이스에서 항목들 간의 상관성을 찾아내는 것을 말한다. 연관 규칙 탐사 후 많은 규칙들이 발견되지만, 실제로 사용자들에게 관심 있는 규칙들인지는 알기 어렵다. 본 논문에서는 이러한 문제를 해결할 수 있는 방법에 대해 연구하였다. 사용자들이 지정한 항목들과 관련된 연관 규칙들을 찾아내기 원하는 경우 항목 제한 조건을 만족하는 규칙들을 찾아내는 방법이 필요하며, 발견된 규칙들은 사용자들에게 매우 관심 있는 규칙들일 것이다. 본 논문에서는 제한 조건들 중에서도 특정 항목을 포함하고 있는 연관 규칙들만을 찾아내도록 하는 항목 제한 조건을 주어 연관 규칙을 탐사하는 방법에 대하여 연구하였다. Apriori 알고리즘을 바탕으로 한 방법과 그보다 더 효율적인 FP-tree를 사용하는 FP-growth 알고리즘을 이용하여 찾아낼 수 있는 방법을 제안하였다. 그리고, 항목 제한 조건을 만족하는 연관 규칙 탐사시 이에 맞도록 FP-tree를 수정하였다. 알고리즘의 성능 평가를 위해 성신여자대학교 홈페이지의 웹 액세스 로그 화일로부터 사용자 트랜잭션 데이터베이스를 만들어 이를 실험 데이터?＠決볜? 사용하였다. 그 결과 제안된 방법은 항목 제한 조건을 만족하는 연관 규칙을 탐사하는데 있어 매우 효과적인 방법임을 보여주고 있다.|Data mining is to extract frequent patterns or useful information from large databases. There are many works on mining association rules, where mining association rules is one of important techniques in data mining. An association rule represents correlation between the one itemset and another itemset in a database. As a result of mining association rules, a user can get so many rules, which makes the user difficult to decide whether which rule is interesting or not. We have studied a method to solve this problem. When a user want to find association rules related to some predefined items, it is necessary to devise an algorithm which finds rules with item constraints, and the user may be very interested in the rules with items. In this paper, we have studied methods of mining association rules with item constraints which find rules having a specific item given by a user. We propose a method based on Apriori algorithm and an efficient method based on FP-growth algorithm using FP-trees. We also modify the FP-tree so that it can be adequate to find rules with item constraints. For performance analysis, a user transaction database is made from access log files on a web server of SungShin Women's University. We show that the proposed method is very effective for mining association rules with item constraints in execution time.