최소지지도 이상을 갖는 항목집합을 빈발항목집합(frequent itemset)이라 한다. 트랜잭션에 나타나는 모든 항목들의 집합을 I={i1, i2, ... ,im}라 할떄, 모든 가능한 부분집합의 수는 공집합을 제외하고 M=2^m-1이다. 예를 들어, 네 원소 항목집합 I={a,b,c,d}의 모든 가능한 항목집합은 2^4-1=15 경우가 되는데, 여기서 {a}, {b}, {c}, {d}와 같이 한 항목으로 이루어진 집합을 1-항목집합, {a,b}, {a,c}, ... ,{c,d}와 같이 두 항목으로 이루어진 집합을 2-항목집합, {a,b,c}, {a,b,d}, ... ,{b,c,d}와 같이 세 항목으로 이루어진 집합을 3-항목집합이라 한다. 일반적으로 k개의 항목으로 이루어진 집합을 k-항목집합이라 한다.
원시적으로 연관규칙을 찾기 위해서는 모든 가능한 부분집합에 대해 전체 트랜잭션에 대한 지지도를 계산하여야 한다. 즉, 각각의 트랜잭션에서 모든 가능한 항목들의 부분집합이 있는지 일일히 비교하여 빈도수를 조사하고, 이 중에서 어떠한 부분집합이 빈발항목인지 알아보아야 한다. N 을 트랜잭션의 수라 하고 w를 한 트랜잭션의 최대 항목수라 할 떄, 모든 가능한 부분집합의 지지도를 계산하는 작업은 (NMw)에 비례하여 많은 비교가 필요하다. 실제 응용에서는 이러한 수치가 매우 클 수 있으므로 이러한 문제점을 줄이기 위해 다음의 두가지 접근방식에 대한 연구가 진행되어 왔다.
1.모든 가능한 항목집합의 수(M)를 줄이는 방식으로서, 선험적(apriori)인 규칙을 이용하여 지지도 계산이 불필요한 항목집합을 제거한다. 2.비교하는 수를 줄이는 방식으로서, 자료구조를 효율적으로 하여 각각의 항목집합을 각각의 트랜잭션과 일일히 비교하는 수를 줄이는 방식이다.
* 선험적 규칙(Apriori Principle)
모든 항목집합에 대한 지지도를 계산하지 않고 원하는 빈발항목집합을 찾아내는데 이용되는 선험적 규칙은 다음과 같다.
1) 한 항목집합이 빈발하다면, 이 항목집합의 모든 부분집합은 역시 빈발항목집합이다.
2) 한 항목집합이 비반발하다면, 이 항목집합을 포함하는 모든 집합은 비빈발항목집합이다.
예를 들어, 모든 항목들의 집합을 I={a,b,c,d}라 하자. 만일 {b,c,d}가 빈발항목집합이라면, 이 항목의 부분집합 {b,c}, {b,d}, {c,d}, {b}, {c}, {d}는 역시 빈발항목집합이 되는데, 이를 선험적 규칙이라 한다. 만일 {a,b}가 최소 지지도 기준을 넘지 못한 비빈발 항목집합이라면, 이 집합을 포함하는 {a,b,c}, {a,b,d}, {a,b,c,d}는 빈발항목집합이 될 수 없다. 이 사실을 이용하면 최소 지지도 기준을 넘지 못하는 항목집합들을 쉽게 가지치기 할 수 있는데, 이를 선험적 규칙을 이용한 빈발항목집합 추출 알고리즘이라 한다.
선험적 알고리즘(apriori algorithm)을 이용한 빈발항목집합의 생성은 먼저 1-항목으로 이루어진 집합(1-항목집합)에 대하여 지지도를 계산한다. 만일 1-항목집합의 지지도가 최소지지도를 넘지 못하면 모두 버린다. 최소지지도를 넘는 1-항목집합을 이용하여 불필요한 2-항목집합(2개 항목으로 이루어진 지집합)에 대한 가지치기를 하고 2-항목 빈발항목집합 후보를 생성한다. 이 빈발항목집합 후보들중에서 최소지지도 기준을 넘는 2-항목 빈발항목집합을 확정하고, 이들을 이용하여 불필요한 3-항목 집합 에 대한 가지치기를하고 3-항목 빈발항목집합 후보를 생성한다. 같은 방법을 k- 항목 빈발항목집합을 확정할때까지 반복한다.
선험적 알고리즘의 특성은 1-항목집합, 2-항목집합, ..., k-항목집합 등 각 수준별(level-wise)로 접근하는 방식이다. 각 수준에서 빈발항목집합 후보를 생성하고, 이 후보들이 지지도를 만족하는지 시험한다(generate-and-test). 알고리즘에서 Ck는 k-빈발항목집합 후보를 의미하고, Lk 는 k-빈발항목집합을 의미한다.
[그림 1] Apriori 알고리즘
k≥2인 경우, Lk를 찾는 apriori 알고리즘은 결합(join)과 가지치기(prune)의 두 과정으로 이루어진다. 관행적으로 apriori에서는 트랜잭션이나 항목집합의 항목들은 알파벳순서대로 정렬되어있다 가정한다.
1. 결합(join)단계 : Lk를 찾기 위해 L(k-1)을 자신과 결합하여 후보(candidate) k-항목집합을 생성한다. 이 후보집합을 Ck 라고 한다. 이제 l1과 l2를 항목집합 L(k-1)에 있는 항목집합이라고 하고 li[j]를 li의 j번째 항목이라고 하자. l1과 l2를 결합한 결과 항목집합은 l1[1], l1[2], ... ,l1[k-2],l1[k-1],l2[k-1]이 된다.
2. 가지치기(pruning)단계 : Ck는 모든 k-항목집합을 포함하고 있지만 그의 원소들은 빈발하거나 혹은 빈발하지 않을 수가 있기 때문에, Lk의 초집합(superset)이다. 데이터베이스를 스캔하여 Ck의 모든 후보들의 개수를 파악하면 Lk를 구할 수 있다.(즉, 최소 지지도 개수보다 큰 후보들은 정의에 의해서 Lk에 속한다고 하였다) 그러나 Ck는 상당히 클 수 있으므로 상당한 연산을 필요로 할 수가 있다.
Ck의 크기를 줄이기 위해서 apriori 성질이 다음과 같이 사용된다. "빈번하지 않은 임의의 (k-1)-항목집합은 빈발 k-항목집합의 부분집합이 될 수 없다. 그러므로 후보 k-항목집합의 임의의 (k-1)-항목집합이 L(k-1)에 없는 경우에는 이 후보 또한 빈발하지 않으므로 Ck에서 제거될 수 있다." 이러한 부분집합 검사(subset testing)는 모든 빈발 항목집합에 대한 해시 트리(hash tree)를 유지함으로써 신속히 처리될 수 있다."
[그림 2] Apriori 알고리즘의 수행 과정
* [그림 2]와 함께보는 Apriori 알고리즘 수행과정
결합단계 : 2-항목집합인 L2에서 {B, C}와 {B, E}를 이용해 {B, C, E}를 비롯한 3-항목집합 C3을 생성한다.
가지치기 단계 : C3의 구성원소들 중에서, L2상에 존재하지 않는 원소로부터 생성되는 경우가 하나라도 있으면, 후보에서 탈락시킨다. 예를들어 {B, C, E}는 그것의 부분집합 {B, C}, {B, E}, {C, E}가 모두 L-2에 속하므로 후보 집합에 해당된다. 하지만 {A, B, C}나 {A, C, E}의 경우, {A, C}나 {A, E}가 L2상에 존재하지 않으므로 후보에서 탈락된다.
============
출처 :
데이터마이닝 개념과 기법, R, SAS, MS-SQL을 활용한 데이터마이닝
댓글