2020년의 첫 글 및 한국에서 쓰는 첫 글 ㅎㅎ 너무 오래 쉬었다. 대구에서 집 밖에 전혀 나갈 수가 없기 때문에.. 하나의 스팀 게임을 일주일 동안 75시간 플레이한 끝에 드디어 키보드를 잡았다. 앞으로 한 달 동안 뭘 해야할지 심각하게 고민이다... 일 시켜 주세요...
* 이 포스팅은 Sequence Mining에 대한 기본적인 이해가 있다는 가정하에 진행된다.
Sequence Mining이란, 아이템들의 ordering을 분석하여 이를 다양한 방법으로 활용하는 것을 말한다. Sequence mining을 통해 어떤 sequence가 어떤 빈도로 출현했는지, 다음 아이템은 무엇일지 예측하는 것 등이 가능하다. 하지만 우리가 가지고 있는 모든 아이템셋들에 대해서 빈도를 하나하나 찾아보는 것은 굉장히 비효율적인 일일 것이다. 이러한 비효율성을 해결하기 위해 order를 고려하지 않는 association rule에서는 Apriori Algorithm을 활용하였다. 이번 포스팅에서는, sequence mining에서 아이템셋의 support를 효율적으로 구할 수 있도록 하는 알고리즘인 ApriroiAll algorithm에 대해 알아볼 것이다.
Motivation
AprioriAll algorithm의 motivation도 Apriori algorithm의 그것과 같다. 예를 들어, 우리가 <포카칩, 초코파이, 꼬북칩> 순서로 과자를 산 사람의 수를 알고 싶다고 하자. 이 때, 이 사람의 수는 <포카칩, 초코파이> 순서로 과자를 산 사람의 수보다 많을 수 있을까? 그럴 수 없을 것이다. <포카칩, 초코파이>의 순서를 지켜 구매했다고 하더라도 그 다음에 꼬북칩을 사지 않은 사람이 존재할 것이기 때문이다.
이를 Association rule로 적용시켜보자. 만약 sequence A가 sequence B의 subsequence라면, A의 support는 B의 support보다 크거나 같을 것이다. 이를 식으로 표현하면 다음과 같다.
그러므로 B의 support가 우리가 설정해 놓은 minimum support 값보다 크다면, A의 support 또한 minimum support 값보다 클 것이다. 이를 식으로 표현하면 다음과 같다.
그러므로 만약 우리가 A가 B의 subsequence인 것을 알고 B의 support가 조건을 만족한다는 것을 확인한다면, A의 support도 따라서 조건을 만족할 것이다. AprioriAll Algorithm은 이 아이디어를 기본으로 한다.
AprioriAll Algorithm
이제 본격적인 AprioriAll Algorithm에 대해 설명할 차례이다. 언제나 그렇듯이, 예시와 함께 설명하도록 하겠다. 다음과 같은 데이터가 있다고 하자. 우리의 minimum support는 2이다.
이 데이터셋을 이해하는 것은 어렵지 않을 것이다. 각 row(행)는 각 고객을 말하고, {} 안에 묶여 있는 것은 한 번에 구매한 물건들을 말한다.
1. minimum support를 만족하는 길이가 1인 sequence를 구한다.
우선, minimum support를 만족하는 길이가 1인 sequence를 구한다. 모든 길이가 1인 sequence들의 support(빈도) 값을 구하면 다음과 같다.
이들 중에는 minimum support를 만족하지 않는 후보가 없기 때문에 제거할 것이 없다. 이를 우리는 L_1 (Large 1-sequence)라고 부른다.
2. 길이 k를 늘려가면서 C_k, L_k를 찾아나간다.
이제 L_1을 바탕으로 C_2를 찾을 차례이다. C_2는 L_1에서 두 개의 sequence를 합하여 만든 모든 sequence 후보들이다. 이들 중 support 값이 minimum support를 만족하는 것들은 다음과 같다. 이들을 우리는 L_2라고 부른다.
이렇게 숫자를 늘려가면서 모든 L_k sequence들을 구한다. 이 때, C_k는 L_k-1에서 앞의 k-2개가 똑같은 두 개의 sequence를 합함으로써 만들어진다. 예를 들어서, 위에서 구한 L_2를 바탕으로 C_3을 구한다고 하자. 그러면 우리는 앞의 1개가 똑같은 두 개의 sequence를 합해서, <1 2 3>, <1 2 4>, <1 2 5>, <1 3 2>, ..., <3 5 4>로 구성된 C_3을 구할 수 있다. 이 C_3으로부터 다시 minimum support를 만족하는 L_3을 구하는 것이다. L_3은 다음과 같다.
이 L_3으로 부터 얻은 C_4는 <1 2 3 4>, <1 2 4 3>, <1 3 4 5>, <1 3 5 4>가 된다. 이 중 minimum support를 만족하는 sequence는 <1 2 3 4>이다. 이것이 L_4가 된다.
더 이상 만들 수 있는 C_5가 없기 때문에, C와 L을 찾는 것은 종료된다. 그리고 찾은 모든 L에 속하는 sequence들은 minimum support를 만족하는 sequence가 된다.
이번 포스팅에서는 sequence mining에서 minimum support 조건을 만족하는 itemset을 찾는 방법인 AprioriAll algorithm에 대해 알아보았다. 이를 통해 sequence mining에서의 효율적인 association rule 적용이 가능할 것이다.
Refernces
R. Agrawal and R. Srikant. Mining sequential patterns. Proceedings of the Eleventh International Conference on Data Engineering, 1995.
최근댓글