[R 연관규칙(Association Rule)] 순차패턴분석 (Sequence Pattern Analysis)

지난번 포스팅에서는 범주형 및 연속형 데이터에 대한 연관규칙 분석에 대하여 알아보았습니다.

 

이번 포스팅에서는 시간(time), 순서(sequence)를 고려한 순차패턴분석(sequence pattern analysis)에 대하여 소개하겠습니다.

 

먼저, 연관규칙(association rule)과 순차패턴규칙의 차이점을 '분석 주안점', '활용 데이터 항목', '흥미도/유용성 평가 척도'의 관점에서 표로 비교해보면 아래와 같습니다.

 

If A then B 형식의 데이터 속에 숨겨져있는 규칙을 찾아낸다는 면에서는 같습니다만, 순차패턴분석의 경우 "What goes AFTER what?" 과 같이 시간/순서에 따른 사건의 규칙을 찾는다는 점, 데이터셋에 Identity information (Customer Identifier, or Event ID), TimeStamp (Sequence information, or Sequence ID) 변수가 있어야 한다는 점, 그리고 Support 척도만 제공할 뿐 연관규칙에서 썼던 Confidence, Lift는 없다는 점이 연관규칙과는 다릅니다.

 

 

 

 

 

순차패턴분석에서 사용하는 데이터셋은 아래처럼 고객ID (or Event ID)별로 TimeStampe (or Sequence ID)의 시간 순서로 거래 데이터가 정리된 형태(ordered by customer ID and TimeStamp)로 되어있습니다.

 

 

 

 

 

항목집합을 순서로 나타낸 리스트를 sequence라고 하며, 

를 j번째 항목집합이라고 할 때

으로 표기합니다.

 

순차패턴분석에서 사용하는 규칙 흥미도 척도인 Support(s) = Sequence s를 포함하는 고객의 비율 입니다.

 

특정 최소 지지도(support) 이상을 가지는 sequence를 빈발 시퀀스(large sequence) 라고 합니다. 순차적 패턴 탐사 문제는 빈발 시퀀스 중에서 최대 시퀀스(maximal sequence)들을 찾는 것이라고 할 수 있습니다.

 

순차 패턴 분석 알고리즘 (Agrawal and Srikant, 1995)은 다음의 단계들로 구성되어 있습니다.

 

1) 정렬 단계 : Transaction database를 고객 sequence data로 전환한다. 2) 빈발항목집합 단계 : 고객 시퀀스의 항목집합 또는 이의 부분집합 중 최소 지지도(고객비율 사용) 이상인 것들을 빈발항목집합으로 도출한다. 편의상 각 빈발 항목집합에 일련번호를 부여한다. 3) 변환 단계 : 고객 시퀀스를 빈발항목집합을 사용한 시퀀스로 변환한다. 4) 시퀀스 단계 : 빈발 시퀀스를 도출한다. 5) 최대화 단계 : 빈발 시퀀스로부터 최대 시퀀스를 탐색한다.

 

(* 출처 : 데이터마이닝 기법과 응용, 전치혁 지음, 한나래 아카데미)

 

 

순차적 패턴 탐사 알고리즘에 대해서는 깊이 들어가지는 않겠으며, R의 arulesSequences package 사용법 중심으로 이번 포스팅을 이어가겠습니다.

 

 

1) "arulesSequences" package installation and loading

 

arulesSequences package는 M. Zaki가 개발한 cSPADE 알고리즘을 사용하여 빈발 순차 패턴을 탐색합니다. 이 알고리즘은 효율적인 격자 탐색 기법과 함께 temporal joins을 이용하며 시간 제약을 제공합니다. (Mining frequent sequential patterns with the cSPADE algorithm. This algorithm utilizes temporal joins along with efficient lattice search techniques and provides for timing constraints.  - help(arulesSequences) -)

 

##---------------------------------------- 
## sequence analysis 
##---------------------------------------- 

## 'arulesSequences' package installation, loading

install.packages("arulesSequences")

#Installing package into ‘C:/Users/Owner/Documents/R/win-library/3.3’ 
#(as ‘lib’ is unspecified)
#also installing the dependency ‘arules’ 
#
#trying URL 'https://cran.rstudio.com/bin/windows/contrib/3.3/arules_1.4-1.zip' 
#Content type 'application/zip' length 1889108 bytes (1.8 MB) 
#downloaded 1.8 MB 
#
#trying URL 'https://cran.rstudio.com/bin/windows/contrib/3.3/arulesSequences_0.2-15.zip'
#Content type 'application/zip' length 4002231 bytes (3.8 MB) 
#downloaded 3.8 MB 
#
#package ‘arules’ successfully unpacked and MD5 sums checked 
#package ‘arulesSequences’ successfully unpacked and MD5 sums checked 
#
#The downloaded binary packages are in 
#C:\Users\Owner\AppData\Local\Temp\RtmpOOKTl5\downloaded_packages


library(arulesSequences)
#필요한 패키지를 로딩중입니다: arules 
#필요한 패키지를 로딩중입니다: Matrix 
#
#다음의 패키지를 부착합니다: 
#‘arules’ The following objects are masked from ‘package:base’: 
#abbreviate, write

 

 

 

2) transaction dataset 준비

 

순차분석 예제 데이터로는 package "arules"에 내장되어 있는 "zaki" transactions (3 variables : sequenceID, eventID, SIZE) dataset을 사용하겠습니다.

 

 

## zaki transaction Dataset > data(zaki)

str(zaki) 
#Formal class 'transactions' [package "arules"] with 3 slots 
#..@ data :Formal class 'ngCMatrix' [package "Matrix"] with 5 slots 
#.. .. ..@ i : int [1:27] 2 3 0 1 2 0 1 5 0 2 
#... .. .. ..@ p : int [1:11] 0 2 5 8 12 15 16 19 22 24 
#... .. .. ..@ Dim : int [1:2] 8 10 
#.. .. ..@ Dimnames:List of 2 
#.. .. .. ..$ : NULL 
#.. .. .. ..$ : NULL 
#.. .. ..@ factors : list() 
#..@ itemInfo :'data.frame': 8 obs. of 1 variable: 
#.. ..$ labels: chr [1:8] "A" "B" "C" "D" 
#... ..@ itemsetInfo:'data.frame': 10 obs. of 3 variables: 
#.. ..$ sequenceID: int [1:10] 1 1 1 1 2 2 3 4 4 4 
#.. ..$ eventID : int [1:10] 10 15 20 25 15 20 10 10 20 25 
#.. ..$ SIZE : int [1:10] 2 3 3 4 3 1 3 3 2 3


help(zaki)

> help(zaki) zaki R Documentation Zaki Data Set Description A small example database for sequence mining provided as an object of class transactions and as a text file. Usage data(zaki) Details The data set contains the sequential database described in the paper by M. J. Zaki for illustration of the concepts of sequence mining. sequenceID and eventID denote the sequence and event (time) identifiers of the transactions. Source M. J. Zaki. (2001). SPADE: An Efficient Algorithm for Mining Frequent Sequences. Machine Learning Journal, 42, 31–60.

 

 

## display zaki in data.frame format
as(zaki, "data.frame") 

#items sequenceID eventID SIZE 
#1 1 10 2 
#2 1 15 3 
#3 1 20 3 
#4 1 25 4 
#5 2 15 3 
#6 2 20 1 
#7 3 10 3 
#8 4 10 3 
#9 4 20 2 
#10 4 25 3

 

 

 

3) 순차패턴분석

 

cspade(dataset, parameter, control) 함수를 사용하여 순차 패턴 탐사를 진행하여보겠습니다.

 

parameter

 - support : a numeric value specifying the minimum support of a sequence (default 0.1, range [0,1]).

 - maxsize : an integer value specifying the maximum number of items of an element of a sequence (default 10, range > 0)

 - maxlen : an integer value specifying the maximum number of elements of a sequence (default 10, range > 0)

 - maxwin : an integer value specifying the maximum time difference between any two elements of a sequence (default none, range >= 0)

 

## sequential pattern analysis : cspade() 
seq_rule_1 <- cspade(zaki, 
    parameter = list(support = 0.3, maxsize = 5, maxlen = 4), 
    control= list(verbose = TRUE)) 
    
#parameter specification: 
#support : 0.3 
#maxsize : 5 
#maxlen : 4 
#
#algorithmic control: 
#bfstype : FALSE 
#verbose : TRUE 
#summary : FALSE 
#tidLists : FALSE 
#
#preprocessing ... 1 partition(s), 0 MB [0.03s] 
#mining transactions ... 0 MB [0.03s] 
#reading sequences ... [0.04s] 
#
#total elapsed time: 0.1s
    

 

 

 

4) 순차 패턴 규칙 조회

 

summary(rule), as(rule, "data.frame") 함수를 이용해서 순차 패턴 규칙을 조회해보겠습니다.

## sequence pattern rule summary 

summary(seq_rule_1) 
#set of 18 sequences with 
#
#most frequent items: 
#A B F D (Other) 
#11 10 10 8 28 
#
#most frequent elements: 
#{A} {D} {B} {F} {B,F}(Other) 
#8 8 4 4 4 3 
#
#element (sequence) size distribution: 
#sizes 
#1 2 3 8 7 3 
#
#sequence length distribution: 
#lengths 
#1 2 3 4 
#4 8 5 1 
#
#summary of quality measures: 
#  support 
#  Min. :0.5000 
#  1st Qu.:0.5000 
#  Median :0.5000 
#  Mean :0.6528 
#  3rd Qu.:0.7500 
#  Max. :1.0000 
#
#includes transaction ID lists: FALSE 
#
#mining info: 
#data ntransactions nsequences support 
#zaki 10 4 0.3


as(seq_rule_1, "data.frame") 
#  sequence support 
#  1 <{A}> 1.00 
#  2 <{B}> 1.00 
#  3 <{D}> 0.50 
#  4 <{F}> 1.00 
#  5 <{A,F}> 0.75 
#  6 <{B,F}> 1.00 
#  7 <{D},{F}> 0.50 
#  8 <{D},{B,F}> 0.50 
#  9 <{A,B,F}> 0.75 
#  10 <{A,B}> 0.75 
#  11 <{D},{B}> 0.50 
#  12 <{B},{A}> 0.50 
#  13 <{D},{A}> 0.50 
#  14 <{F},{A}> 0.50 
#  15 <{D},{F},{A}> 0.50 
#  16 <{B,F},{A}> 0.50 
#  17 <{D},{B,F},{A}> 0.50 
#  18 <{D},{B},{A}> 0.50
  

 

 

 

5) 순차 규칙 선별 (Subsetting sequence rule)

 

순차 규칙 내 원소의 개수(element size)가 2개 이상인 규칙만 선별해보겠습니다. 

 

## making the sequence rule as a DataFrame
seq_rule_1_df <- as(seq_rule_1, "data.frame")
 
## calculate the size of the elements per each rule
seq_rule_1_size <- size(seq_rule_1)

## combine the element size with the sequence rule DataFrame
seq_rule_1_df <- cbind(seq_rule_1_df, seq_rule_1_size)
 
## subsetting the rules which have moer the 2 elements in the rule
seq_rule_1_df_size_2 <- subset(seq_rule_1_df, 
                               subset = seq_rule_1_size >= 2)
 
## checking the result
seq_rule_1_df_size_2

#          sequence support seq_rule_1_size
#7        <{D},{F}>     0.5               2
#8      <{D},{B,F}>     0.5               2
#11       <{D},{B}>     0.5               2
#12       <{B},{A}>     0.5               2
#13       <{D},{A}>     0.5               2
#14       <{F},{A}>     0.5               2
#15   <{D},{F},{A}>     0.5               3
#16     <{B,F},{A}>     0.5               2
#17 <{D},{B,F},{A}>     0.5               3
#18   <{D},{B},{A}>     0.5               3

 

* 거래 데이터 text 파일을 읽어와서 순차분석을 할 수 있는 transactions format 으로 변환하는 방법은 https://rfriend.tistory.com/193 를 참고하세요. 

 

다음번 포스팅에서는 항목의 분류/계층 체계 (taxonomy), 가상 항목(virtual item)에 대해서 알아보겠습니다.

 

이번 포스팅이 도움이 되었다면 아래의 '공감 ~♡'를 꾸욱 눌러주세요.

 

 

[ cSPADE Algorithm Reference ]

 

M. J. Zaki. (2001). SPADE: An Efficient Algorithm for Mining Frequent Sequences. Machine
Learning Journal, 42, 31–60.