[Algorithm] What is A-Priori Algorithm?

1. A-priori Algorithm 이란 ?

발생 빈도 기반 데이터 간의 또 다른 사건의 규칙을 발견하는 Algorithm이라 할 수 있다.

 

Figure 1. Picture of A-Priori

Fig1.의 그림을 참고하여 A-Priori Algorithm을 설명하면 먼저 크게 Pass1,Pass 2과정이 있다고 생각하면 된다.

- Pass 1

이 과정에서는 Baskets(데이터)를 읽고 각각의 item들의 빈도수를 count해준다.

이때 우리가 정해놓은 Threshold(s) 값이 넘는 빈도수들의 item들을 frequent item으로 취급해준다.

 

- Pass 2

이 과정에서는 Baskets(데이터)를 다시 읽고 이번에는 Pass 1과정에서 구한 frequent pair들만 count 해준다.

 

Fig2. Example of A-priori algorithm

위 예시는 A-priori Algorithm을 이용하여 triplet set을 만드는 과정이다.

위의 방법 처럼 적용해보면 Pass1 과정을 거치면 L1 set을 구할 수 있다.

그 후 L1의 item들을 사용하여 C2 집합(frequent pair)들을 만들어 준다.

이 후 C2 집합들을 똑같이 algorithm을 적용해준후 새로운 frequent pair들(L2)만 남겨준다.

이 문제에서는 triplet을 구해야하기 때문에 L2를 이용하여 candidate triplet set(C3)를 만들어 준 후,

Algorithm을 다시 적용하여 최종 frequent triplet을 구하는 예시이다.

 

2. How to apply A-prori Algorithm ?

#1st pruning 과정
check_item ={}
s = ths * total_basket
for word in item:
	if item[word] >= s:
		check_item[word] = item[word]

#frequent pair 생성 해주기
file = open("yelp_review ","r")
freq_pairs = {}
for line in file:
	line = line.strip()
	word_list = line.split()
	word_list = list(set(word_list))
	for i in range(len(word_list)-1):
		for j in range(i+1, len(word_list)):
			if (word_list[i] in check_item) and (word_list[j] in check_item):
				pair = word_list[i] + " " + word_list[j]
				if pair in freq_pairs:
					freq_pairs[pair] += 1
				else:
					freq_pairs[pair] = 1
result = {}
for pair in freq_pairs:
	if freq_pairs[pair] > s:
		result[pair] = freq_pairs[pair]
result = sorted(result.items(), key=lambda x: x[1], reverse=True)

 

이 알고리즘 같은 경우 제가 직접 짠 A-priori 알고리즘인데 이 알고리즘으로 yelp_review 데이터에 적용해 review에 자주 쓰는 word pair들을 구할 수 있었다. 먼저 처음에는 frequent item을 만들어 주었고 해당 frequent item으로 frequent pair를 생성해 최종적인 frequent pair를 만들어주는 간단한 알고리즘이라고 생각한다.

 

Fig. result of A-priori Algorithm in yelp_reiview

해당 결과는 GCP에서 yelp review 데이터를 돌려본 결과이다. 아무래도 영어 단어들의 특징 상 묶이는 단어 pair들이 많은 것 같다. 다음에는 뭔가 더 구체적인 데이터로 특징을 찾아볼 수 있는 그런 데이터에 해당 알고리즘을 적용해 보고싶다.