Aprior 알고리즘

Apriori 알고리즘의 개요

-어떤 Item 집합의 존재가 다른 Item 집합의 존재를 암시하는 것을 의미하며 다음과 같이 표시한다.

(Item set A) => (Item set B ) ( if A then B : 만일 A 가 일어나면 B 가 일어난다. ) 

     - 함께 구매하는 상품의 조합이나 서비스 패턴 발견하는데 이용

     - 특정 제품 또는 사건들이 동시에 발생 하는 패턴을 파악하는데 이용

ex) 가정 용품 판매 기간 동안 같이 판매해야 하는 상품의 패턴 발견 

- 데이터들에 대한 발생 빈도를 기반으로 각 데이터 간의 연관관계를 밝히기 위한 방법

- 구현이 간단하고 성능 또한 만족할 만한 수준을 보여주는 알고리즘으로 패턴 분석을 위해 자주 이용되는 알고리즘

- Apriori는 K번째 항목집합이 K+1번째 항목집합을 발견하기 위해 사용되는 레벨단위로 진행되는 반복 접근법을 사용

- 예를 들어서 A->B일때 0.75의 확률을 가진다고해서, B->A일확률일 0.75라는 것을 보장해주지는 못한다. 따라서 한 트랜잭션에 대해서 A가 나오고 B가 나오는 예와 B가 나오고 A가 나오는 것에 대한 확률은 input데이터를 따로 정렬해서 구해야한다.

- 여기서 사용할 set()은 순서가 없는 집합형 자료형이므로 순서는 신경쓰지 않아야한다.

Apriori알고리즘 적용예시

교차 판매 ( Cross Selling )

상품 진열 ( Inventory Display )

부정탐지(fraud detection)

- 상당히 높은 신뢰도를 갖는 규칙에 대해 특정 고객이 그 규칙이 적용이 않되다면 수상할 수 있음

Category Design

- 상품의 배치문제, 패키지 상품의 구성, 쿠폰 발행, 카탈로그의 구성, 신상품의 카테고리 선정

Apriori 알고리즘 설명

- Database로부터 후보 항목 집합(Candidate Itemset)을 생성하고, 

이를 데이터베이스 트랜잭션과 비교하여 빈발 항목 집합(Large Itemset)을 찾아내는 과정, 

더 이상의 빈발 k-항목 집합이 없을 때까지 반복하는 과정을 거친 후 최종 빈발 항목 집합을 생성함

- 빈발 항목 집합들(Large Item Sets)을 찾기 위해서 미리 결정된 최소 지지도(Minimum Support) 이상의 트랜잭션 지지도를 가지는 항목 집합들의 모든 집합들을 빈발 항목 집합들이라고 하며 그 외 모든 항목 집합들은 작은 항목 집합들(Small Itemsets)이라 함.

- 데이터베이스로부터 연관 규칙을 생성하기 위하여 빈발 항목 집합을 이용. 

지지도(Support)와 신뢰도(Confidence)는 다음의 식을 통해 계산

여기서 지지도란, 전체 건수중에 몇 개 이상 포함되어있는 항목들이 무엇인지 찾아내기 위한 척도이며, 신뢰도란, 지지도를 가진 건수가 전체 항목중에 몇개나 있는지를 볼 수 있는 것이라고 생각하면 쉽다. Apriori알고리즘 구현 여기서는 최소지지도가 2이상인 빈발항목을 구하는 코드이다. import itertools # set자료형 사용이 핵심! # Apriori알고리즘 자체가 순서가 없다. 데이터는 편의대로 정렬해놓은것!(180811) class Apriori: def __init__(self,input, min_support): self.min_support = min_support self.origin_set = input self.distinct_list = self.distinct_input(input) self.distinct_set = list(map(set,self.distinct_list)) #DataSet을 중복없이 나열하는 함수 #return { } def distinct_input(self, input): # { }은 set에 사용하는 기호지만 인수없이쓰면 dict로 인식한다 # 따라서 set()을 사용한다. data_set = set() for idx in list(input): data_set.update(idx) return list(data_set) #빈도수를 구하는 함수 #원본데이터에서 경우의수를 구한데이터를 가지고 빈도수를 구한다. #param n경우의수 step수 / data distinct_list #return [] def get_freq(self,n): freq_dic = dict() case_list = self.number_of_case_n(n, self.distinct_list) for j in list(self.origin_set) : for i in list(case_list) : if(j.issuperset(i)): if freq_dic.get(i, 0) == 0 : freq_dic[i] = 1 else : freq_dic[i] += 1 return freq_dic #param : freq_dic def rm_minsup(self, freq_dic): cp_freq_dic = freq_dic.copy() sum_val = len(cp_freq_dic.keys()) for i in list(cp_freq_dic.items()): if i[1] < self.min_support: del cp_freq_dic[i[0]] return list(cp_freq_dic) #DataSet의 모든 경우의수를 구하는 함수 #return [] def number_of_case_n(self, n, data): n_list = list() for subset in itertools.combinations(data, n): n_list.append(subset) return list(map(frozenset, n_list)) def start(self): i = 1 step_result = None while True: step_result = list(map(set, self.rm_minsup(self.get_freq(i)))) self.distinct_list = self.distinct_input(step_result) print(step_result) print(i) if len(step_result) <= 1: break if i >= 100: break i += 1 conf = [ a for a in self.origin_set if a.issuperset(step_result[0])] #최소지지도 : 전체 건수중에 3개 이상 포함되어있는 항목들이 무엇인지 => {2,5} print(self.min_support / len(self.origin_set)) #신뢰도 : 전체 건수중에 포함되어있는 항목중에 2,5가 포함되어있는 건은 몇건인지 => 3건 print(len(conf) / len(self.origin_set)) if __name__== "__main__": min_support = 2 ##4장의 영수증 내역의 리스트 모음이라고 생각하자. input = [{'A', 'C', 'D'}, {'B', 'C', 'E'}, {'A', 'B', 'C', 'E'}, {'B', 'E'}] apriori = Apriori(input,min_support) apriori.start()  결과: [{'E'}, {'D'}, {'A'}, {'B'}, {'C'}]  #최초 중복을 제거한 데이터 [{'A'}, {'C'}, {'E'}, {'B'}] # 최소 지지도이하 1차 제거후 1 [{'A', 'C'}, {'E', 'C'}, {'E', 'B'}, {'B', 'C'}] # 최소 지지도 이하 2차 제거후 2 [{'E', 'B', 'C'}] # 최소지지도 이하 3차 제거후 3 0.5 #최소지지도 0.5 #신뢰도

지지도 기반의 탐색을 하고 싶으면 데이터 셋의 각 경우를 구해서 모두 issubset해서 지지도를 구해서 확인하면 된다.

신뢰도 기반의 탐색을 하고 싶으면 주어진 데이터 셋의 각 경우를 구해서 모두 issubset해서 지지도를 구하고 이 지지도를 기반으로 신뢰도를 구하면 된다.

[참고]

http://www.jidum.com/jidums/view.do?jidumId=1099

http://hamait.tistory.com/743?category=132470

http://contents.kocw.net/KOCW/document/2014/Chungbuk/choisanghyun/12.pdf