순차 패턴 분석 기초

 

 

순차 패턴 분석

• 순차 패턴 분석

시간과 순서를 고려한 연관분석이다. 연관 분석은 항목 간 발생 순서는 중요하지 않지만, 순차 패턴 분석에서는 항목 간 발생 순서가 중요한 요소다. 동 분석에 활용하는 데이터는 (1) 트랜잭션 데이터 셋, (2) Identity 정보, (3) Timestamp이며, 오직 Support 값을 활용하여 유용성을 평가한다. 예를 들면, 고객이 버튼 A à B à C 순서로 선택한 지지도가 최소 지지도 이상이면 해당 순차 패턴은 빈발 패턴이므로 중요하게 고려되어야 한다.

• GSP (apriori-based sequential pattern mining)

첫 DB 스캔 시 length 1의 sequence candidates를 구성하고, 최소 지지도 미만의 후보들을 제외한다. 두 번째 스캔 시 length 2의 sequence candidates를 구성하고, 마찬가지로 최소 지지도 미만의 후보들을 제외한다. 이 과정을 반복하며 모든 후보들을 얻는다. (apriori와 동일 à 엄청 느리다.)

• cSPADE (aprori 알고리즘 기반)

(1) Sequence ID (SID), Event ID (EID)를 순서대로 정렬하여, 각 Sequence의 Event 별 item 항목을 담은 Vertical table을 만든다. (2) Vertical table을 참고하여, length 1의 sequence부터 순차적 SID-EID 패턴을 찾는다. (3) length 2, 3, … 순으로 각 패턴을 만족하는 SID-EIDs 패턴을 찾는다(연속일 필요는 없음).

• PrefixSpan (pattern-growth 알고리즘 기반)

(1) Length 1 패턴을 찾고, 각 패턴의 projected DB를 만든다. (2) Length 1 패턴의 각 projected DB에서 Length 2 패턴의 projected DB를 만든다. (3) 이 과정을 반복해 나가며 분석을 진행한다. 단계가 지날수록 candidates의 생성 비율이 줄어들고, iteration마다 DB Scan이 필요한 GSP보다 성능이 우수하다.