GSP(Generalised Sequential Patterns)의 정의
GSP는 일반화 순차 패턴(Generalised Sequential Patterns)의 약자로, 1996년 Srikant와 Agrawal이 제안한 대표적인 순차 패턴 마이닝(sequential pattern mining) 기법입니다. GSP는 두 연구자가 이전에 발표한 연관 항목집합(itemset) 마이닝의 핵심 알고리즘인 Apriori를 순차 데이터에 맞게 확장한 것으로, 순차 패턴이 지니는 하향 폐쇄성(downward-closure) 속성을 활용하고 여러 번의 데이터베이스 스캔을 거치며 후보를 생성·검증하는(candidate generate-and-test) 방식을 채택합니다.
GSP 알고리즘의 동작 과정
1단계: 첫 번째 데이터베이스 스캔
알고리즘은 데이터베이스에 대한 첫 번째 스캔에서 최소 지지도(minimum support) 이상을 만족하는 빈발 아이템(frequent items)을 찾아냅니다. 각 빈발 아이템은 해당 아이템 하나만으로 구성된 길이 1짜리 빈발 시퀀스, 즉 1-이벤트 빈발 시퀀스를 생성합니다.
2단계: 시드 집합으로부터 후보 시퀀스 생성
이후 각 패스(pass)는 이전 단계에서 발견된 순차 패턴들의 집합, 즉 시드 집합(seed set)으로 시작됩니다. 이 시드 집합은 잠재적으로 빈발할 수 있는 새로운 패턴들, 이른바 후보 시퀀스(candidate sequences)를 만들어내는 재료가 됩니다. 각 후보 시퀀스는 그것을 생성한 시드 순차 패턴보다 정확히 하나 더 많은 아이템을 포함하며, 여기서 패턴 내 각 이벤트(event)는 하나 또는 여러 개의 아이템을 가질 수 있습니다.
3단계: 지지도 계산과 반복 종료 조건
시퀀스 내 아이템의 개수를 그 시퀀스의 길이라고 하며, 길이가 k인 시퀀스를 k-시퀀스(k-sequence)라고 정의합니다. 따라서 동일한 패스에서 생성되는 후보 시퀀스들은 모두 같은 길이를 가집니다.
Ck를 후보 k-시퀀스의 집합이라고 할 때, 데이터베이스를 한 번 스캔하면 각 후보 k-시퀀스의 지지도(support)를 계산할 수 있습니다. 이때 최소 지지도 min_sup 이상을 만족하는 Ck의 후보들이 Lk, 즉 모든 빈발 k-시퀀스의 집합을 구성합니다. 이 Lk는 다음 패스(k+1)의 시드 집합이 됩니다. 알고리즘은 어떤 패스에서도 새로운 순차 패턴이 발견되지 않거나, 더 이상 후보 시퀀스를 생성할 수 없을 때 종료됩니다.
Apriori 속성을 활용한 후보 가지치기
GSP는 Apriori 속성을 활용해 후보 집합의 크기를 효율적으로 줄입니다. 구체적으로 k번째 패스에서 어떤 시퀀스가 후보가 되려면, 그 시퀀스의 모든 길이 (k−1) 부분시퀀스(subsequence)가 (k−1)번째 패스에서 발견된 순차 패턴이어야 한다는 조건을 적용합니다. 이 가지치기(pruning) 과정을 통해 불필요한 후보를 사전에 제거함으로써 탐색 공간을 크게 축소할 수 있습니다.
이후 데이터베이스를 다시 한 번 스캔하여 각 후보 시퀀스의 지지도를 집계하고, 새로운 순차 패턴 집합 Lk를 도출합니다. 이 집합은 다음 패스의 시드가 되며, 새로운 패턴이 발견되지 않거나 후보가 생성되지 않으면 알고리즘이 종료됩니다.
수직 데이터 형식(Vertical Data Format)을 이용한 분석
Apriori 계열의 후보 생성-검증 기반 순차 패턴 마이닝 기법은 데이터베이스를 수직 데이터 형식(vertical data format)으로 변환하여 분석할 수도 있습니다. 수직 형식에서는 데이터베이스가 다음과 같은 튜플(tuple)의 집합으로 표현됩니다.
(itemset : (sequence_ID, event_ID))
여기서 이벤트 식별자(event ID)는 시퀀스 내부의 타임스탬프 역할을 합니다. 즉, 시퀀스에서 i번째 항목집합(또는 이벤트)의 event_ID는 i가 됩니다. 하나의 항목집합은 둘 이상의 시퀀스에 나타날 수 있으며, 특정 항목집합에 대해 (sequence ID, event ID) 쌍들의 전체 집합을 그 항목집합의 ID_list라고 부릅니다. 이러한 ID_list 구조를 활용하면 지지도 계산을 단순한 리스트 교집합 연산으로 처리할 수 있어 효율성이 크게 향상됩니다.