논문정리_Frequent item set mining(Christian Borgelt∗)

MLA

Grahne, Gösta, and Jianfei Zhu. "Fast algorithms for frequent itemset mining using fp-trees." IEEE transactions on knowledge and data engineering 17.10 (2005): 1347-1362.

개인적인 목적으로 읽으면서 조금씩 정리해가려고 합니다. 논문은 구글 스콜라에서 검색하실 수 있습니다. 이 논문은 frequent item set mining에 대한 survey 논문이라고 볼 수 있는데요. 논문에서는 개념 정의와 기본적인 개념 그리고 핵심적인 업무에 대해 쓰여있습니다. 여러 개의 소제목으로 이루어져 있는데, 필요한 것부터 하나씩 읽어나가면서 정리해가려고 합니다.

Introduction

Apriori, Eclat, FP-Growth(Frequent Pattern Growth), LCM(Liner time Closed item set Miner)

Basic notion

Frequent item set mining의 기본 개념은 market basket analysis에서 시작되었다.

슈퍼 혹은 인터넷에서 사람들이 함께 구매하는 물품을 알아내서 소비패턴을 파악하는 일에서부터 시작한 것이다.

파악한 규칙을 판매에 적용하기 위함이다. 슈퍼에서는 함께 상품을 진열하거나, 웹에서는 삼품을 추천하거나 같은 페이지에 노출시키는 일을 한다.

Problem Definition

기본적으로 frequent item set mining을 문제를 정의하는 방법을 설명한다.

1. item base라고 부르고, n개의 물건이라고 생각할 수 있다.(집합)

2. transactions, m개의 거래 목록이다.(vector)

3. 현실에서 n개의 물건과 m개의 거래 목록이 있다고 가정해보자. 실제로는 n개의 물건 리스트를 제공하기 어렵다. 물품의 개수가 너무 많기 때문이다. 따라서 모든 거래 목록을 종합해서 물건의 리스트를 구 할 수 있다.

4. m개의 transactions 중에 I를 포함하는 t의 집합

5. m개의 transactions 중에 I를 포함하는 t의 집합의 갯수

6. (m개의 transactions 중에 I를 포함하는 t의 집합의 개수)/(m은 transaction의 개수)

frequent item set mining에서 1~6 가지를 가지고 문제를 정의할 수 있다. 최종적으로 frequent item set mining의 목적은 모든 item set들을 찾아내어서 함께 짝지을 수 있는 것으로 정의하는 것이다. 예를 들어서 슈퍼에서 frequent item set mining 한다고 가정하면 일정 횟수 이상 함께 구매되는 물품을 찾아내는 것이다.

FIGURE1은 최소 기준을 3회 이상이라고 정하였을 때의 frequent item set mining의 예이다.

Search space and support properties

이 챕터는 위의 세 가지 항목으로 설명할 수 있다. 1~3번까지 이해하기 전에, antimonotone의 개념을 알아야지 이해가 쉽다.

http://blog.naver.com/sindong14/220661432606

Anti-monotone property

antimonotone의 개념은 위의 블로그의 글을 참고했다.

논문의 내용으로 설명하면, 현실에서는 item base의 수가 너무 많아서 모든 항목을 이용해서 조합(item set)을 만들기가 어렵다. 따라서 효율성을 높이기 위해서 사용하는 방법이 antimonotone의 개념이다. 1번을 보면 item set I가 있을 때, I가 포함되는 J가 있다. 그리고 가장 상위에는 B(=item base)가 존재한다. 위와 같은 가정에서 I와 J의 개수를 구한다고 했을 때 I의 수가 J 보다 많다.

이것을 antimonotone과 함께 간단하게 설명하면, antimonotone은 데이터 마이닝을 할 경우에 선행되는 조합이 조건을 만족하지 못하고 유의미하지 않으면 그 이후의 조합도 의미가 없다고 말할 수 있다. 1번의 개념을 적용하면 2번에서 I가 최소 조건보다 작은 수라면, J 역시 최소 조건 보다 작다는 것이다. 그리고 마지막으로 3번은 I가 최소 조건의 만족하는 F의 원소라면, I에 포함되는 J도 역시 F의 원소라고 할 수 있다.

정리하면, item base의 개수가 너무 많아서, 모든 조합을 구하는 것이 불가능하고 frequent item set을 찾을 수 없을 때 1~3번의 규칙을 가지고 효율적으로 유의미한 조합을 찾겠다는 의미다.

Closed and Maximal Item Sets and Generators

ITEM SET ENUMERATION

Organizing the Search

Breadth-First/Levelwise Search

Depth-First Search

Order of the Subproblems

Order of the Items

DATABASE REPRESENTATIONS

Horizontal Representation

Vertical Representation

Hybrid Representations

ADVANCED TECHNIQUES

Reducing the Transaction Database

Perfect Extension Pruning

Few Items

Conditional Item Reordering

Generating the Output

Closed and Maximal Item Set Filtering

INTERSECTING TRANSACTIONS

EXTENSIONS

Association Rules

Cover Similarity

Item Set Ranking and Selection

Fault-Tolerant Item Sets

SUMMARY