Frequent Pattern Mining : Partition/ DHP/ Sampling/ DIC

본 개념은 Data Mining: Concepts and Techniques (Jiawei Han, ‎Jian Pei, ‎Micheline Kamber)서적을 바탕으로 합니다.

 

Data Mining: Concepts and Techniques (Jiawei Han, ‎Jian Pei, ‎Micheline Kamber) 

 

 

안녕하세요. 저번 포스팅에서는 닫힌 패턴과 최대 패턴에 관해 알아 보았습니다.

이번 포스팅에서는 빈발 패턴을 찾는 알고리즘을 조금 더 세부적으로 알아보겠습니다.

 

연관규칙 알고리즘을 효율적으로 탐색하기 위해서는 다양한 알고리즘이 적용될 수 있습니다. 효율적인 알고리즘이 왜 필요한가? 라는 질문엔 이렇게 답할 수 있겠습니다. 거래에서 나타나는 모든 항목들의 집합(item set)을 I 라고 할 때,

모든 항목들의 집합 I

모든 가능한 부분집합의 개수는 공집합을 제외하고 M 개 입니다.

그리고 모든 가능한 연관규칙의 개수는 다음과 같습니다.

가능한 부분집합의 개수나 연관규칙의 개수가 item 이 증가할 때 마다 지수적으로 증가함을 알 수 있습니다. 그렇기에 모든 경우를 다 보기에는 수행시간이 오래걸리므로 효율성이 떨어집니다. 이러한 문제점을 보안하기 위해 연관규칙의 효율적인 탐색을 위해 Partition, DHP, Sampling, DIC 가 이에 해당되는데요. 각 알고리즘의 수행 방법과 개념에 관해 알아보겠습니다.

 

#1. Partition 

Partition은 DB를 오로지 2번만 스캔한다라는 목적을 가진 알고리즘 입니다. 그렇기에 데이터를 빠르고 효율적으로 처리하는 알고리즘으로 제시 되었습니다. 기존 알고리즘의 주요 단점은 데이터 베이스에 대해서 여러 단계의 스캔을 요구한다는 것이었습니다. 즉, 디스크에 내재된 데이터 베이스의 경우 각 단계 마다 전체 데이터베이스로부터 읽기 위해서는 상당히 많은 수의 디스크 입출력을 요구합니다. 그러나 Partition은 DB로 부터 의미있는 연관성 규칙을 만들어 내기 위해 2번의 scan으로 효율적으로 수행시간을 줄일 수 있다는 장점을 가집니다. 

 

수행과정은 크게 두 단계로 나눠집니다.

 

 

1. 데이터베이스를 중복되지 않는 크기로 분할하고, 한번에 한 개의 분할만을 고려하여 그 안에서 자주 발생하는 항목집합들을 생성합니다. (Scan 1)

 

이때, 각각의 분할에서 생성된 자주 발생하는 항목집합들은 잠재적으로 자주 발생하는 항목 집합들로 통합됩니다. (Scan 2) 또한, DB안의 잠재적인 빈발을 최소 1개의 partition을 가져야 합니다. 

 

2. 각 항목에 대한 실제 지지도가 생성되고 자주 발생하는 항목 집합들이 식별됩니다. 

 

#2. DHP(Direct Hashing and Pruning)

DHP는 항목집합의 갯수가 2개인 후보들을 효율적으로 작게 구하는 방법과 이것을 기초로 전체 트랜잭션의 크기와 개수를 줄여나가는 방법을 제시하였습니다. 우선 항목집합의 갯수가 2개인 트랜잭션을 먼저 DB에서 추출하여 해쉬 테이블을 만든 후 해쉬 테이블에 있는 것과 비교하여 최소 지지도를 넘는 item set만 가지고 항목집합 갯수가 2개인 C2를 만듭니다. 따라서 DHP는 초기 단계의 두번째까지만 DB 전체를 스캔하고 이후 에는 DB 크기를 줄여가기 때문에 실행시간이 대폭 감소합니다. 그렇기에 전체적인 성능 또한 해쉬 테이블을 만드는 번거로움을 감안하더라도 Apriori를 능가합니다.

 

수행과정은 다음과 같습니다.

• Candidates : a, b, c, d, e

• Hash entries(2-itemsets) : {ab, ad, ae} , {bd, be, de} ..

• Frequent 1-itemset : a, b, d, e  (만약 10,000 개의 아이템셋이 있으면 2-itemset은 10,000의 제곱인 100,000,000 개가 된다.)

 

DHP 수행과정

 

#3. Sampling

원래의 DB에서  빈발 패턴을 가진 샘플을 추리는 알고리즘입니다. 샘플로 선정된 데이터를 SDB(Sampled DB)라고도 합니다.

하지만 문제점들이 존재합니다. 

1. SDB에서 발견된 몇몇의 빈발 패턴이 정말 빈발 패턴이 아닐 수 있습니다.

2. S (Sampled) 안에 포함되지 안되있으면 '정말 빈발 패턴' 을 놓칠 수 있습니다.

수행과정은 다음과 같습니다.

 

1. 전체 DB를 한번 Scan 합니다. 

2. 빈발 아이템 셋 집합을 검증하여 S와 SB로 분리한다. 

• S (Sampled) : {a}, {b}, {c}, {f}, {a,b}, {a,c}, {a,f}, {c,f}, {a,c,f}

• NB(Not in S, but all its subsets in S) : {b,c}, {b,f}, {d}, {e}

3. 전체 DB를 다시 Scan 합니다.

이는 놓친 빈발 패턴을 찾기 위해서입니다.

 

* reference : H.Toivonen, sampling large database for associate rules. In VLDB'96

www.math.unipd.it/~dulli/corso04/toivonen96sampling.pdf

 

#4. DIC 

DIC는 Dynamic ItemSet Count의 약자이며, 동적 항목집합 카운팅이라고도 합니다. 빈발 항목 집합들을 찾는데 있어서 카운트되는 항목 집합 들의 수를 상대적으로 적게 유지하면서 DB 스캔 횟수를 줄이는 알고리즘입니다. Apriori는 레벨 단위로 진행되면서 빈발 항목 집합들을 찾는 반면에, DIC에서는 간격을 두고 항목집합의 크기를 증가시키면서 동시에 빈발 항목 집합들을 찾습니다. 예를들면, 빈발 항목 집합들을 찾기 위해, Apriori에서 3번의 스캔이 요구된다면 DIC에서는 1.5번의 스캔 으로 빈발항목집합들을 찾을 수 있습니다.

 

DIC는 DB 시작 지점을 표시한 블록들로 분할되어 있는 경우에 사용합니다. 이 기법을 사용하면 매번 전체 DB를 스캔하기 직전에만 신규 후보 항목집합을 결정할수 있는 Apiori와 달리, 신규 후보항목집합을 임의의 시작지점에 추가할 수 있습니다.