시퀀스 데이터

각 요소가(순서, 값) 형태로 구성된 데이터로, A가 발생한 후에 B가 발생한 것을 분석하는 것으로 반드시 순서를 고려해야 한다.
로그 데이터 대부분이 순서가 있는 시퀀스 데이터.

• 고객 구매 기록 : 페이지 방문 순서와 구매 순서
• 고객 여정 : 여행 경로
• 웹 서핑 기록 등

지지도와 신뢰도

지지도(support)

아이템 집합이 전체 트랜잭션 데이터에서 발생한 비율

• S(A->B) = N(A,B) / n
  N(A,B):트랜잭션 데이터에서 A와 B가 동시에 출현한 횟수.
  n: 트랜잭션 데이터 크기

신뢰도(confidence)

부모 아이템 집합이 등장한 트랜잭션 데이터에서 자식 아이템 집합이 발생한 비율

• C(A->B) = N(A,B) / N(A)
  N(A,B):트랜잭션 데이터에서 A와 B가 동시에 출현한 횟수.
  N(A): 트랜잭션 데이터에서 A의 출현 횟수

윈도우 설정

A -> B -> C -> D

• 윈도우 내 크기 'L'을 설정하여 특정 이벤트가 발생했는지 확인.
  L=1, A->B는 '발생', A->C는 '미발생'
  L=2, A->B는 '발생', A->C는 '발생'

순서를 고려한 연관규칙

• A->B, B->A 일 때, 연관규칙에서는 지지도가 같으나, 순서를 고려해야 할 때 지지도는 달라지기 때문에 항목 집합으로부터 규칙을 생성할 수가 없다.
• 순서를 고려한 규칙을 지원하는 라이브러리가 없기 때문에, 규칙을 직접 찾아야(함수 작성) 한다.(DP:동적 프로그래밍)
  유니크한 요소 목록 추출 -> 빈발 단일 이벤트 추출 -> 이벤트 추가 및 지지도 계산 -> 최대 빈발 아이템 집합 탐색 -> 규칙 생성
• 신뢰도에 대한 Apriori는 성립

탐색

페이지 이동 데이터를 가지고 실습을 진행해보자.

순서가 중요하기에 고객 ID별로 방문한 순서에 따라서 데이터를 정렬하고,
방문 가능한 모든 페이지와 고객 ID별로 방문 페이지를 array형태로 변환한다.

직접 만들기 위한 함수 생성

순서를 고려한 항목 집합으로부터 규칙 생성을 지원하는 라이브러리가 없기에 직접 함수를 만들어야 한다.

1. 특정 항목 집합에서 특정 패턴이 발생했는지 윈도우 내 크기 'L'에 따른 T/F 여부를 반환해주는 함수

from itertools import product # 조합의 모든 경우의 수 

# 특정 record에 특정 pattern이 발생했는지 여부.
def contain_pattern(record, pattern, L): # 
    output = False # 미발생으로 초기화
    if set(record) & set(pattern) != set(pattern): # pattern에 포함된 모든 아이템 집합이 record에 포함된 아이템 집합에 속하지 않으면
        return False    
    else:
        # 패턴에 속한 개별 아이템에 대한 위치를 미리 구하기
        pattern_index_list = [np.where(record == item)[0] for item in pattern]
        
        ## 가능한 모든 조합에서 위치 간 거리가 L이하면 True를 반환 예시
        # record = [A, B, C, A, C, C], pattern = [A, B], L = 1
        # A의 위치: [0, 3], B의 위치: [1]
        # 가능한 모든 조합: [0, 1], [3, 1]
        # 가능한 모든 조합의 거리 차이: [1 - 0, 1 - 3] 중에 0번째 요소는 만족하므로 True
        
        for pattern_index in product(*pattern_index_list):
            distance = np.array(pattern_index)[1:] - np.array(pattern_index)[:-1] # 패턴 뒤의 값 - 앞의 값 = 거리
            if sum((distance <= L) & (distance > 0)) == (len(pattern_index) - 1): # distance는 L보다는 작거나 같아야 하고 / 거리는 음수가 아니어야 하고 최소 0보다는 커야 한다.
                output = True
                break
        
        return output

2. 1번 T/F 반환하는 함수를 통해 최대빈발하는 시퀀스 아이템을 찾는 함수

def find_maximum_frequent_sequence_item(item_set, sequence_data, min_support = 0.01, L = 1):
    queue = [] # 탐색할 대상을 넣을
    maximum_frequent_sequence_item = [] # 최대빈발패턴을 담을 리스트
    
    # 유니크한 아이템 집합에 대해, min_support가 넘는 아이템들만 queue에 추가시킴
    for item in item_set: # 방문 페이지
        occurence = sequence_data.apply(contain_pattern, pattern = [item], L = L).sum() # sequence_data: 고객 ID별 방문 페이지 ndarray / [item] 각 시퀀스 -> 시퀀스가 몇 번 등장했는지 횟수 반환
        if occurence / len(sequence_data) >= min_support: # min_support : 시퀀스의 등장 비율(기준=1%)
            queue.append([item])

    while queue:
        current_pattern = queue.pop()
        check_maximum_frequent = True # 모든 자식 집합이 min_support를 넘기지 않으면 True를 유지

        for item in item_set:
            occurence = sequence_data.apply(contain_pattern, pattern = current_pattern + [item], L = L).sum() # current_pattern에 item을 추가하였을 때 최대빈발패턴의 여부 확인하기 위한
            if occurence / len(sequence_data) >= min_support: # min_support를 넘는 패턴을 queue에 추가 / 추가하였을 때 여전히 min_support보다 높은 값을 가지는 최대빈발패턴이라면 item을 추가하기 전의 occurence는 최대빈발패턴이 아니게 된다.
                check_maximum_frequent = False 
                queue.append(current_pattern + [item]) # 기존의 패턴을 'pop'하였기에 제외시키고, 기존 패턴에 item을 추가하여 'append'시킨다. / 계속 item을 추가하여 최종 최대빈발패턴이 나올 때까지 while문을 동작시킨다.
        
        if check_maximum_frequent and len(current_pattern) > 1: # 기존의 패턴이 최대빈발패턴 이라면 / 패턴의 길이가 단 하나의 아이템이라면 패턴이라고 보기 어렵다.
            maximum_frequent_sequence_item.append(current_pattern) # 'pop'으로 꺼낸 패턴이 최종적으로 최대빈발패턴이라면 maximum_frequent_sequence_item 'append'한다.
    
    return maximum_frequent_sequence_item

3. 2번 함수에서 반환하는 최대빈발패턴 시퀀스 아이템을 통해 시퀀스의 빈발패턴을 찾는 함수

def generate_association_rules(maximum_frequent_sequence_item, sequence_data, min_support = 0.01, min_confidence = 0.5, L = 1):
    # 결과 초기화
    result = {"부모":[], "자식":[], "지지도":[], "신뢰도":[]} # DataFrame 형식으로 만들기 쉽다.
        
    for sequence_item in maximum_frequent_sequence_item:
        # A -> B에서 A, B를 모두 포함하는 가짓 수 co_occurence 계산
        co_occurence = sequence_data.apply(contain_pattern, pattern = sequence_item, L = L).sum()
        support = co_occurence / len(sequence_data) # 지지도
        if co_occurence > min_support: # co_occurence가 최소 지지도보다 높은 것들만
            for i in range(len(sequence_item)-1, 0, -1): # 한 아이템 집합에 대해, 부모의 크기를 1씩 줄여나가는 방식으로 부모와 자식 설정
                antecedent = sequence_item[:i] # i 앞의 아이템 = 부모 집합
                consequent = sequence_item[i:] # i 뒤의 아이템 = 자식 집합
                antecedent_occurence = sequence_data.apply(contain_pattern, pattern = antecedent, L = L).sum() # 부모 집합의 발생 비율만 
                
                confidence = co_occurence / antecedent_occurence # 신뢰도
                if confidence > min_confidence: # 최소 신뢰도보다 높다면
                    result['부모'].append(antecedent)
                    result['자식'].append(consequent)
                    result['지지도'].append(support)
                    result['신뢰도'].append(confidence)
            
    return pd.DataFrame(result)

이 함수들을 사용하여 순서를 고려한 연관규칙을 찾아보자.

#1 : page_set과 page_sequence_per_order을 가지고 최대빈발패턴 아이템 반환
maximum_frequent_sequence_item = find_maximum_frequent_sequence_item(page_set, page_sequence_per_order, min_support = 0.02, L = 1)

#2 : 결과값
result = generate_association_rules(maximum_frequent_sequence_item, page_sequence_per_order, min_support = 0.01, min_confidence = 0, L = 1)

그 결과값을 보자.
부모 페이지를 방문하고 다음 순서로 자식 페이지가 등장하는 지지도와 신뢰도를 반환하는 것을 볼 수 있다.