[Data mining] Itemset mining - GSP algorithm, Apriori algorithm
[ Motivation ]
Sequence data를 다룰 일이 있어서, Markov chain를 사용하던 와중에 "sequence pattern matching"에 대해서 찾아보게 되었다. Sequence Pattern Matching는 크게 String mining과 itemset mining로 나뉠 수 있다. 이 중에, itemset mining에 관심이 생겼고, 그에 대표적인 알고리즘인 GSP와 Apriori에 대해서 찾아보았다.
[ Itemset Mining ]
(Frequent) Itemset mining이란, 주어진 sequence에서 가장 빈번하게 발생되는 item들의 set을 (= itemset) 구하는 것을 의미합니다.
-> 우리가 흔히 말하는 pattern matching에서 pattern을 여기서는 itemset (즉, set of items) 을 뜻한다.
[ Application ]
Itemset Mining은 market basket analysis와 같이 마케팅 분야에 자주 사용이 된다. 당연하지만, Bioinformatics와 같은 다른 분야에서도 사용이 되는 분석 방식이다.
-> 단순하게 생각하면, "이 정도면 자주 발생한다~"라는 조건을 만들고 그 조건에 부합하는 itemset을 찾는 것이다 : 누구나 sequence에 대해서 분석을 하려고 할 때, 가장 쉽게 떠올릴 수 있는 패턴 일 것이다.
예시.
슈퍼마켓에서 장을 보는 순서라는 데이터가 있다고 하자.
사람 A : 과자 - 고기 - 채소 - 쌈장 - 아이스크림
사람 B : 고기 - 채소 - 계란 - 껌
사람 C : 아이스크림 - 고기 - 쌈장 - 채소 - 맥주
....
위의 데이터에서, 우리는 "고기를 사면 같이 먹을 채소를 사는구나~" 라는 내용을 알 수 있습니다. ( 더 나아가서 쌈장도 구매를 하는구나~ ) 즉, 우리는 "고기", "채소", "과자", ... 등과 같은 item의 모임인 itemset 중에 {"고기", "채소"} 라는 빈번하게 발생하는 itemset ( frequent item set )을 찾았으며, 이를 이용하여 고기를 장바구니에 담은 사람에게 채소 페이지를 추천하는 알고리즘을 제공할 수 있습니다.
[ Apriori Algorithm ]
Apriori Algorithm은 transaction이 존재하는 database/dataset에서 사용하기 위해 고안된 알고리즘이다. 여기서 transaction이란, 데이터베이스(DB)에서 사용하는 기술적인 용어보다는 기록이라고 생각하면 편합니다.
예로 들어,
- DNA 염기서열은 기록이라기 보다는 그냥 단순한 A,T,C,G,U 의 조합이기 때문에 transaction이 없는 데이터 입니다.
(당연히 모여서 의미를 이루기는 하지만, 어떤 이벤트의 기록이라고 보기는 힘들죠.)
- 방금 전 예로 들었던 장 본 데이터는, "구매를 한 이벤트에 대한 기록"이기 때문에 transaction이 있는 데이터입니다.
Apriori 알고리즘은 bottom-up 방식을 사용합니다. 무슨 말이냐면, item을 하나만 포함하는 set부터 차례대로 길이/크기를 늘려가면서 주어진 조건에 부합하는 가장 긴 set을 찾는 방식을 사용합니다. ( set의 길이가 길다 = set의 cardinality가 높다 )
Pseudu code는 아래와 같습니다.
-> 위에서 언급했었던 대로, "얼마나 많이 발생해야 빈번한가?"을 나타내는 값입니다. 예로 들어서, 이 값이 3으로 설정이 되었다면, 3번 이상은 나와야 빈번하게 발생한 itemset이라고 판단하게 됩니다.
알고리즘 자체는 간단합니다.
- 길이가 n-1인 가능한 item들의 조합을 구하고, 그것들의 frequency를 구한 뒤, threshold 이상인 값들을 추출한 것을 L(n-1)라고 합니다.
- L(n-1)의 원소들의 조합으로 길이가 n인 itemset을 생성합니다.
- threshold보다 적게 발생한 set은 제거합니다.
- ... : 이 과정을 L(k)의 원소가 없을 때까지 반복합니다.
이 때, 중요한 점은 L(n-1)에서 L(n)를 생성할 때에, 기존에 threshold보다 적게 발생한 sequence를 보유한 sequence는 자동적으로 제외합니다. ( 당연히, L(k)에서 threshold 이상 발생하였다면, 그 전에도 threshold 이상 발생했을 것입니다 )
예시.( 출처 : Wikipedia )
위와 같은 itemset들이 있고, threshold가 3이라고 생각해보겠습니다.
길이가 1인 set 들을 추출하고, 그 값들에 대한 frequency를 구해보면 왼쪽처럼 나옵니다.
위의 itemset에서 {1, 2, 3, 4} , {1, 2, 4}, {1, 2} 에 1이 들어가 있기 때문에, 1의 frequency는 3입니다.
이 때, threshold가 3이지만 모든 값이 모두 3회 이상 발생하였기 때문에 제거해야 하는 set은 없습니다.
위에서 구한 길이가 1인 set들의 원소를 조합해서, 길이가 2인 set을 생성하고, 각각의 frequency를 구한 결과입니다.
마찬가지로, 길이가 1인 set의 frequency를 구할 때처럼, {1, 2}가 포함되어 있는 itemset은 {1, 2, 3, 4}, {1, 2, 4}만 존재하기 때문에 frequency는 2입니다.
이번에는, threshold인 3보다 낮은 frequency를 갖는 set이 발생하였습니다. 이 set들은 제거하고 다음 단계로 넘어갑니다.
바로 전 단계에서 구한 길이가 2인 set들 중 threshold 이상으로 발생한 set에는 {1, 2}, {2, 3}, {2, 4}, {3, 4}가 있습니다. 이 set의 원소들을 조합하여 길이가 3인 set을 생성하면, {1, 2, 3}, {1. 2. 4}, {2, 3, 4} 가 있지만, 이미 {1, 3}, {1, 4}를 포함하는 set이라면 threshold보다 낮게 발생을 하기 때문에, {2, 3, 4}만 조사를 하면 됩니다.
길이가 3인 set 중에, frequency가 threshold를 넘어가는 set이 없기 때문에 여기서 알고리즘은 종료가 됩니다.
[ GSP ] - WIP