순차 패턴 마이닝이란?
순차 패턴 마이닝(Sequential Pattern Mining)은 데이터 안에서 자주 반복해서 나타나는 일련의 사건(event)이나 부분 수열(subsequence)을 패턴으로 발굴하는 데이터 마이닝 기법입니다. 가장 대표적인 예가 바로 "캐논 디지털 카메라를 구매한 고객은 한 달 이내에 HP 컬러 프린터를 구매한다"는 행동 패턴입니다.
왜 중요할까? 주요 활용 분야
소매 유통 업계에서는 순차 패턴을 활용해 상품 진열대 배치와 프로모션 전략을 최적화할 수 있습니다. 이 밖에도 통신 산업을 비롯한 다양한 비즈니스 분야에서 타깃 마케팅(targeted marketing), 고객 유지(user retention) 등의 업무에 폭넓게 응용되고 있습니다.
그 외에도 웹 접속 패턴 분석, 날씨 예측, 생산 공정 관리, 웹 침입 탐지 등 여러 영역에서 순차 패턴 마이닝이 활용됩니다.
핵심 용어와 기본 개념
빈발 부분 수열의 정의
각 수열이 사건(원소)들의 목록으로 구성되고, 각 사건이 아이템들의 집합으로 이루어진 수열 집합이 주어졌다고 가정해 보겠습니다. 여기에 사용자가 지정한 최소 지지도(min_sup) 임계값을 함께 주면, 순차 패턴 마이닝은 전체 수열 집합에서 최소 min_sup번 이상 등장하는 모든 빈발 부분 수열(frequent subsequences)을 찾아냅니다.
아이템, 아이템셋, 수열
모든 아이템의 집합을 I = {I1, I2, …, Ip}라고 정의합니다. 아이템셋(itemset)은 비어 있지 않은 아이템들의 집합이며, 수열(sequence)은 사건들이 시간 순서대로 나열된 것입니다. 수열 s는 {e1, e2, e3, …, el} 형태로 표현되며, 이때 e1이 e2보다 먼저 발생하고, e2는 e3보다 먼저 발생하는 식으로 순서가 유지됩니다. 각 사건 ej는 수열 s의 원소(element)라고도 부릅니다.
구매 정보에서의 사건(event)
사용자 구매 정보를 분석할 때 하나의 사건은 고객이 특정 매장에서 물건을 구매하는 한 차례의 쇼핑을 의미합니다. 이 사건은 곧 아이템셋, 즉 해당 방문에서 고객이 구매한 아이템들의 무순위(unordered) 목록입니다. 아이템셋(사건)은 (x1x2···xq)로 표기하며, 여기서 xk는 개별 아이템을 뜻합니다.
수열의 길이(length)
하나의 아이템은 수열 내 같은 사건에서는 단 한 번만 등장할 수 있지만, 서로 다른 사건들에는 여러 번 나타날 수 있습니다. 수열에 포함된 아이템 인스턴스의 총 개수를 그 수열의 길이(length)라고 하며, 길이가 l인 수열을 l-수열(l-sequence)이라고 부릅니다.
수열 데이터베이스
수열 데이터베이스(sequence database) S는 튜플 (SID, s)들의 집합입니다. 여기서 SID는 수열 식별자(sequence_ID)이고, s는 수열입니다. 예컨대 S에는 해당 매장의 모든 고객에 대한 수열이 저장됩니다. 어떤 튜플 (SID, s)가 수열 α를 포함한다는 것은 α가 s의 부분 수열(subsequence)일 때 성립합니다.
마이닝 과정의 본질과 확장 요구사항
앞서 설명한 순차 패턴 마이닝 단계는 본질적으로 사용자 쇼핑 수열 분석의 추상화(abstraction)입니다. 이러한 데이터를 대상으로 확장 가능한(scalable) 순차 패턴 마이닝 알고리즘들이 다양하게 개발되어 왔습니다.
다만 이 기본 단계만으로는 모든 응용 분야의 요구를 충족시킬 수 없습니다. 예를 들어 웹 클릭스트림(clickstream) 수열을 분석할 때는, 다음 클릭을 예측하려면 클릭 사이의 시간 간격(gap)이 매우 중요해집니다.
DNA 서열 분석에서는 DNA 서열에 기호(symbol)의 삽입(insertion), 삭제(deletion), 돌연변이(mutation)가 포함될 수 있기 때문에 근사 패턴(approximate patterns)이 더욱 유용합니다. 이처럼 다양한 요구사항은 제약 조건(constraint)의 완화 또는 적용이라는 관점에서 처리할 수 있습니다.