PrefixSpan 알고리즘

PrefixSpan 알고리즘은 순차 패턴(SP, Sequential Pattern)을 찾는 데 사용되는 방법입니다. 순차 패턴이란 시간 순서에 따라 발생하는 일련의 이벤트나 항목들 간의 패턴을 의미합니다. 예를 들어, 고객이 온라인 쇼핑몰에서 먼저 A 제품을 사고, 나중에 B 제품을 사는 패턴을 찾는 데 사용할 수 있습니다.

PrefixSpan 알고리즘의 핵심 개념

1. 시퀀스(Sequence): 시간 순서에 따라 발생하는 사건이나 항목들의 집합입니다. 예를 들어, A -> B -> C라는 시퀀스는 어떤 사람이 A 제품을 산 후 B, 그리고 C를 샀다는 의미입니다.
2. 서브시퀀스(Subsequence): 시퀀스의 일부입니다. 예를 들어, A -> C는 A -> B -> C의 서브시퀀스입니다.
3. 빈도수(Frequency): 특정 패턴이 데이터에서 얼마나 자주 나타나는지를 의미합니다. 예를 들어, A -> B 패턴이 10번 나타났다면, 이 패턴의 빈도수는 10입니다.
4. 지지도(Support): 특정 패턴이 전체 시퀀스 중 얼마나 자주 발생하는지를 비율로 나타냅니다. 예를 들어, 100개의 시퀀스 중 A -> B가 20번 나타났다면, 지지도는 20%입니다.

PrefixSpan 알고리즘의 동작 방식

1. Prefix(접두사) 기반 확장:
   1. 이 알고리즘은 기존 시퀀스를 확장하여 더 큰 시퀀스를 만드는 방식으로 동작합니다.
   2. 예를 들어, A라는 패턴이 있으면, 이 패턴에 B나 C 같은 항목을 추가하여 A -> B, A -> C 같은 새로운 패턴을 만듭니다.
2. Prefix에 따른 세분화:
   1. 주어진 시퀀스를 접두사(prefix)에 따라 세분화합니다. 예를 들어, 시퀀스가 A -> B -> C라면, 접두사 A를 기준으로 B -> C 부분을 나누어 다룹니다.
   2. 이 과정을 통해, 각 접두사에 따라 남은 시퀀스를 분석하고, 새로운 패턴을 찾습니다.
3. 빈도 패턴 탐색:
   1. 접두사별로 남은 시퀀스를 분석하면서 자주 발생하는 패턴을 찾습니다.
   2. 각 패턴의 지지도를 계산하고, 미리 정해둔 지지도 기준값보다 낮은 패턴은 제거합니다.
4. 재귀적으로 확장:
   1. 자주 발생하는 패턴을 찾았다면, 그 패턴을 더 확장해 새로운 접두사를 만들고, 다시 빈도수를 계산하는 작업을 반복합니다. 예를 들어, A -> B라는 패턴이 있다면, 이 패턴을 확장해 A -> B -> C를 찾는 식입니다.

예시로 설명하기

예를 들어, 세 명의 고객이 다음과 같은 시퀀스를 남겼다고 가정해 봅시다:

1. 고객 1: A -> B -> C
2. 고객 2: A -> C
3. 고객 3: B -> C -> A

PrefixSpan은 먼저 단일 항목 패턴을 찾습니다: A, B, C. 그런 다음 A가 포함된 시퀀스를 찾고, A 다음에 자주 오는 패턴을 봅니다. 여기서 A -> B나 A -> C 같은 패턴이 발견되면, 이를 더 확장해 새로운 패턴을 찾는 방식으로 진행됩니다.

이렇게 PrefixSpan 알고리즘은 시간 순서에 따른 패턴을 찾는 데 매우 효과적이며, 데이터베이스에서 자주 발생하는 순차적 이벤트들을 찾아내어 활용할 수 있습니다.