시퀀스 데이터 마이닝 Sequential Data Mining

[참고자료] 사용자 행동 데이터의 시퀀스 패턴 마이닝 기술 동향(임지연, 2020)

1. 시퀀스 데이터란?

시퀀스 데이터 = 특정 기간동안 대상의 행동을 나타내는 “선후 관계”가 있는 항목들의 집합
- action (or event)의 집합 : action 1, action 2, action 3 .. 같이 구성되어 전체를 이루며, 이들 원소간에서는 중복이 허용되지 않는다. 단 하나의 원소에는 여러 시퀀스에 포함될 수 있다
- “시간”축이 존재
- action 간의 “순서”가 존재
- 시퀀스의 길이 = 시퀀스를 구성하는 항목의 개수
ex ) sequence = < a(ce)(bd)(bcde)f(dg) > 의 시퀀스의 길이는 12이며, 서로 다른 7개의 항목(abcdefg)으로 이루어져있고, 6개의 원소(a, ce, .. , dg)로 이루어져있다
-사례 : 마케팅) 쇼핑 순서에 따른 물건 배치, 웹) 사용자 서비스 이용 데이터

2. 시퀀스 패턴 마이닝 정의

1) 개념 정의
시퀀스 패턴 p가 주어졌을 때, 패턴 p의 지지도support값 = 데이터베이스에 존재하는 패턴 p를 포함한 시퀀스의 개수
빈발 패턴/빈발 시퀀스 패턴 = 지지도 임계치 min_support 이상의 값을 지지도로 가지는 패턴
1-patter = 길이가 1인 패턴

2) 목적
(1) 최소 지지도 이상의 완전한 패턴 집합 탐색
(2) DB탐색 횟수를 최소화하는 효율적이고 확장 가능한 방식
(3) 연구자가 설정한 제한 조건을 반영

3. 시퀀스 패턴 마이닝 알고리즘

1) apriori 기반 시퀀스 패턴 마이닝 : 빈도 기반 방식 ~ Generalize Sequential Pattern (GSP)
(특징) 가장 오래 됐다
(단점) 모든 빈발 시퀀스 패턴을 탐색하다보니 시간이 많이 걸린다

2) 깊이 탐색 기반 시퀀스 패턴 마이닝 : pattern growth based method ~ FreeSpan
(특징) 부분 집합에서 빈발 패턴 탐색, 효율적
(단점) (min_sup값 이상이면 다 결과로 도출하다보니) 비슷해 보이는 수많은 시퀀스가 나온다

3) 제약식 기반 시퀀스 패턴 마이닝 : 제약 기반 방식
- constraint 제약식의 유형
(1) 항목(item) : 항목의 부분집합이 포함되어야 하거나 포함되어서는 안 되는 조건
(2) 시퀀스 길이 : 패턴의 길이를 체크 - 특정 항목이 등장하는 개수 or 트랜잭션 개수
(3) 슈퍼 패턴 : 특정한 패턴을 적어도 하나 이상을 부분집합으로 가짐
(4) 합계 : 항목(item)의 합계(평균, 최소, 최대, 표준편차 등)에 대한 제약
(5) 정규식
(6) 지속 기간 : 시퀀스(or 항목item)의 지속 기간 ~ time-stamp가 있어야 한다
(7) 간격

17 18 19 20 21 텍스늡 ㅜㄴ류 22 트렌드

4. 더 공부할 부분

(1) 선후 관계를 고려한 빈도 기반의 분석 방법
(2) Markov Chain 등의 확률 기반 예측 방법

(3) Data Preparation for Mining World Wide Web Browing Patterns, 1999
(4) Discovering Internet marketing Intelligence through online analytical web usage mining, 1998
(5) Using sequential and non-sequential patterns in predictive web usage mining tasks, 2002
(6) Analysis of Navigation behaviour in web sites integrating multiple information systems, 2000

(7) 텍스트 분류, Sequential patterns for text categorization, 2006
(8) Sequencial pattern mining for structure-based XML document classification, 2005