My Engineer Study Story

1. K-means Clustering 이란 ? 

K-means clustering 에서 K는 데이터 집단에서 만들어지는 총 cluster수 이고 means는 각 데이터가 속한 클러스터의 중심까지의 평균 거리를 말한다. 이때 K-means clustering의 목표는 중심까지의 평균 거리를 최소화 하는 것이다.

해당 알고리즘의 구현 방법은 간단하다.

1. 각각의 데이터를 현재 가장 가까운 cluster에 배치 해준다

2. 모든 데이터의 배치가 끝난 후, 각 cluster의 centroid를 업데이트 해준다

3. 모든 데이터들을 새로 업데이트된 centroid를 기준으로 가장 가까운 곳으로 다시 재배치 해준다.

2번, 3번을 모든 데이터들이 수렴할때까지 반복해준다.

2. How to select K ? 

우리는 적절한 K를 찾기 위해 K를 다르게 하여 중심점으로 부터의 평균거리를 계산해 봐야한다.

이때, 적합한 K를 찾을 때까지 평균 거리는 급속도로 떨어질 것이다.

3. How to apply K-means Clustering in program ?

def distance(x, y):
	 return sqrt(sum(pow(int(a) - int(b), 2) for a, b in zip(x, y)))

partial_sums = {}

for i in range(10):
 	partial_sums.setdefault(i, [0 for i in range(784)] )
    
def sum_vector(A,B):
 	return [int(x)+int(y) for x,y in zip(A, B)]


for line in sys.stdin:
 	line = line.strip()
 	img = [int(item) for item in line.split(",")]
 	min_dis = distance(centroids[0] , img)
 	# print(min_dis)
 	min_idx = 0
 	for i in range(1,10):
 		dis = distance(centroids[i], img)
 		if dis < min_dis:
 			min_dis = dis
 			min_idx = i
 	partial_sums[min_idx] = sum_vector(partial_sums[min_idx], img)
 	cnt[min_idx] += 1

해당 알고리즘은 내가 짠 알고리즘인데 일단 간단하게 해당 알고리즘이 들어간 일부분만 갖고와봤다.

먼저, 해당 파일의 각 이미지(데이터)를 읽고 각 중심점과 의 최소 거리를 구한 후 최소 평균거리의 중심점을 찾아 partial_sum에 해당 img의 최소 distance를 더해준다.

for line in sys.stdin:
	 line = line.strip()
 	idx, partial = line.split("\t")
 	partial_sum, cnt = partial.split("|")
 	partial_sum = partial_sum.split(",")
 	for i in range(len(partial_sum)):
 		partial_sum[i] = int(partial_sum[i].strip())
        
 	idx = int(idx)
 	cnt = int(cnt)
    
 	if (cur_idx == idx):
 		total += cnt
 		centroids = [centroids[i] + int(partial_sum[i]) for i in range(784)]
 	else:
 		if cur_idx is not None:
 			if total > 0:
 				new_cent = [str(centroids[i]/total) for i in range(784)]
 				new_cent = ' '.join(new_cent)
 				total = str(total)
 				print("Centroid "+ str(cur_idx) + ": " + str(total) + "," + new_cent)
 				total = cnt
 				centroids = [0 for i in range(784)]
 				centroids = [centroids[i] + int(partial_sum[i]) for i in range(784)]
 
 		elif cur_idx is None:
 				total = cnt
 				centroids = [centroids[i] + int(partial_sum[i]) for i in range(784)]
                
                cur_idx = idx
                
if total > 0:
 	new_cent = [str(centroids[i]/total) for i in range(784)]
 	new_cent = ' '.join(new_cent)
 	total = str(total)
 	print("Centroid "+ str(cur_idx) + ": " + str(total) + "," + new_cent)

다음 프로그램에서는 이제 각 클러스터(idx) 마다 전에 구했던 partial들을 총합 해주고 평균을 내어 새로운 클러스터의 중심점으로 갱신해준다.

지금 이 두 프로그램이 이제 위에서 설명한 2,3번 구간이다. 이제 이 프로그램 두개를 계속해서 반복해서 실행해주면 K-means Clustering을 시행시킬 수 있다.

1. PCY Algorithm 이란 ?

PCY Algorithm은 A-Priori Algorithm과 비슷하지만 그보다 메모리 공간을 더 효율적으로 활용하는 Algorithm이라고 할 수 있다.

- Pass 1

Pass 1 에서는 각 item을 count 하여 저장하고 모든 pair를 생성해준다. 이때 생성해준 pair에 대해 hash값을 만들어 주어 해시 해시된 버킷으로 count 와 함께 bucket에 저장해줍니다. 우리는 이때 어떤 pair가 support(s)보다 높은지 낮은지만 따지면 되기때문에 pair의 구체적인 값은 알 필요가 없습니다.

- Pass 2

이후 Pass 2에서는 오직 frequent bucket에만 있는 pair만 count 해준다. 즉, 버킷이 s이하로 카운트 되면 그 버킷은 frequent한 pair가 아니다라고 할 수 있다. 그러므로 pair 가 {i, j}라 한다면 두가지 조건을 만족 하게되는데 첫번째는 두 item 모두 frequent item 이고 두번째는 pair {i , j}가 frequent bucket에 hash 되어 있다는 것이다. 

이렇게 원래 4-byte의 정수가 bits로 대체되었기 때문에(A-Priori와 다르게) 기존의 공간의 1/32만 차지하게되어서 메모리 효율이 훨씬 좋아집니다. Pass 2에서는 triples(item, item, count)를 사용해야만 하는데 그렇기 때문에 frequent pair가 많다면 비효율적이게 됩니다. 그래서 PCY는 pair의 2/3이상 줄여주어야만 A-priori보다 효율적으로 쓸 수 있게됩니다.

1. SON Algorithm이란 ? 

SON Algorithm은 baskets을 작은 chunk로 나누어 모든 frequent itemset을 찾는 것을 도와주는 Algorithm이다. 이때 이 Algorithm은 distributed/ parallel computing에 적합해 MapReduce를 활용하여 쓰이기 좋은 구조이다. 그래서 이 알고리즘을 두 MapReduce job으로 설명해 볼 것이다.

1st MapReduce

먼저 1st MapReduce job의 목표는 Candidate itemsets을 생성하는 것이 목표이다.

Mapper for Job 1

    - A-priori Algorithm을 chunk에 적용해 s(support) 값을 넘는지 check하기

    - 각 chunk에서 frequent itemsets을 만들어 (F, c) 형태로 output하기 (F => key (itemset) c => value (count) )

Reducer for Job 1

    - 2nd MapReduce에서 활용할 candidate itemset을 output하기

    - 이때 받아온 (F, c) 형태에서 count 값은 버리고 오직 itemset인 F만 output

2nd MapReduce

2nd MapReduce job의 목표는 true frequent itemsets을 찾는 것이 목표이다.

Mapper for Job 2

    -  1st MapReduce에서 만든 candidate itemset을 이용하여 각 chunk의 frequency count하기

Reducer for Job 2

    - Mapper of job 2에서 생성한 output들을 종합하여 count를 집계하기

    - 그후 support(s) 값보다 작은 값들은 제외시켜 output하기

2. How to use SON Algorithm ?

1st Mapper

for line in sys.stdin:
    line = line.strip()
    word_list = line.split(' ')
    total_basket += 1
    word_list = list(set(word_list))
    basket_list.append(word_list)
    for word in word_list:
        if word in item:
            item[word] += 1
        else:
            item[word] = 1

s = ths * total_basket

for word, cnt in item.items():
    if cnt >= s:
        check_item[word] = cnt

check_pairs = {}

for basket in basket_list:
    for i in range(len(basket)-1):
        for j in range(i+1, len(basket)):
            if (basket[i] in check_item) and (basket[j] in check_item):
                if (basket[i] <= basket[j]):
                    pair = basket[i] + " " + basket[j]
                else : pair = basket[j] + " " + basket[i]
                if pair in check_pairs:
                    check_pairs[pair] += 1
                else:
                    check_pairs[pair] = 1

for pair, cnt in check_pairs.items():
    if (cnt >= s):
        print("%s\t%s" %(pair, cnt))

1st Reducer

cur_pair = None
for line in sys.stdin:
    line = line.strip()
    pair, count = line.split('\t')
    if pair != cur_pair:
        if cur_pair is not None:
            print ("%s" % (cur_pair))
        cur_pair = pair

print("%s" % (cur_pair))

2nd Mapper

check_pairs = {}
file = open("pair_list", "r")
for line in file:
    pair = line.strip()
    check_pairs[pair] = 0

for line1 in sys.stdin:
    line1 = line1.strip()
    word_list = line1.split(' ')
    word_list = list(set(word_list))
    #print(word_list)
    for i in range(len(word_list) - 1):
        for j in range(i+1, len(word_list)):
            if (word_list[i] <= word_list[j]):
                pair = word_list[i] + " " + word_list[j]
            else : pair = word_list[j] + " " + word_list[i]
            #print(pair)
            if pair in check_pairs:
                check_pairs[pair] +=1
                

for pair, cnt in check_pairs.items():
    print("%s\t%s" % (pair, cnt))

2nd Reducer

cur_pair = None
total = 0
ths = 0.01
total_basket = 4984636
s = ths * total_basket

for line in sys.stdin:
    line = line.strip()
    pair, cnt = line.split("\t")
    if pair != cur_pair:
        if cur_pair is not None:
            if total >= s:
                print("%s\t%s" % (cur_pair, total))
        cur_pair = pair
        total = int(cnt)
    else: total += int(cnt)

print("%s\t%s" % (cur_pair, total))

1. A-priori Algorithm 이란 ?

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

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 해준다.

위 예시는 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를 만들어주는 간단한 알고리즘이라고 생각한다.

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

1. RFP 란 ?

Rabin Finger Printing 알고리즘은 긴 문자열을 해싱하는 데에 사용하는 대표적인 알고리즘이다.

이 알고리즘은 일반적인 Chunking 알고리즘이지만 최신기술은 아니다. 그래서 Chunking 알고리즘에서 수행능력이 높은 면은 아니지만 가장 기본적인 알고리즘 중 하나이다. 

d 의 경우 fingerprint 값의 가능한 범위를 나타낸다. 이 값은 257로 설정하는 것이 좋은데 그 이유는 만약 256으로 할경우 값의 충돌이 나타날 수 있기 때문이다.

q의 경우 값이 클 수록 fingerprint value가 겹치지 않기에 이것 또한 값이 클 수록 좋다.

m의 경우 Window size로 가장 작은 chunk size를 나타낸다.

2. RFP on deduplication

먼저 m=4이기 때문에 첫번째 RFP를 구하면 공식을 이용하여 12가 된다. 이때 mask와 AND operation을 적용할 경우 0이 아니기 때문에 chunk가 만들어질 수 없다.

다음 RFP를 계산하면 0이 되기 때문에 mask 와 AND operation을 적용할 경우 0이 되기 때문에 3까지가 anchor point가 되어 첫번째 chunk가 생성된다.

이러한 식으로 계속해서 chunk를 만들어가면 RFP 알고리즘을 적용한 variable size의 chunk를 만들 수 있다.

3. What if the input contains many runs of zeros?

만약 file이 0이 많이 구성된 파일일 경우 무수한 chunk를 생성할 거기에 chunk size를 variable하게 할 경우 비효율 적일 수 있다. 그래서 오히려 fixed size로 하는 것이 더 효율적일 수 있다. 만약 chunk 숫자를 줄이고 싶을 경우 0이 아닌 다른 숫자가 나올 때 anchor point를 만들어 준다면 chunk 숫자를 조금 더 효율적으로 만들 수 도 있다.

1. Dijkstra's Algorithm 이란?

Dijkstra Algorithm 은 동적 프로그래밍을활용한 대표적인 최단 경로 탐색 Algorithm입니다. 이 알고리즘으로 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있습니다. Dijkstra Algorithm은 sequential algorithm이기에 MapReduce에 바로 적용하는 것은 불가능합니다. 왜냐하면 MapReduce에서는 데이터를 서로 주고받는 구조가 매우 힘들기 때문입니다. 그렇기에 MapReduce에서는 Brute-force 방식을 활용하여 모든 nodes를 다시 재 방문하여 구하는 식으로 사용하여 Dijkstra Algorithm을 MapReduce에 적용할 수 있습니다.

Figure 2 같은 경우 Dijkstra algorithm을 Parallel BFS를 이용하여 MapReduce로 구현하였을 때의 psuedo 코드 이다. Map phase에서는 각 노드와 neighbor node와의 distance를 Emit 하고 Reduce phase에서는 그 중 min distance를 찾아 distance를 update 한 후 start node와 neighbor node 구조체를 emit 해준다. 

2. My Review

평소에 Dijkstra 알고리즘 자체는 코딩 문제를 풀면서 많이 접근한 적이 많은 친숙한 알고리즘이여서 쉽게 다가갈 수 있었다. 하지만 아무래도 여기서는 MapReduce에 Dijkstra 알고리즘을 적용해야 했어서 기존에 알고있던 방식으로는 사용할 수 없어서 조금 까다로웠다. MapReduce에서는 Parallel BFS를 활용하여 Dijkstra 알고리즘을 사용할 수 있었고 처음에는 까다로웠지만 전반적인 프로그램의 구조를 이해한 후에는 굉장히 유용한 구조임을 깨달을 수 있었다.

1. Page rank 란?

Page rank란 페이지의 중요도를 웹페이지 간 연결 관계에 기반을 두고 측정한 지표이다. 

Figure1 은 웹페이지들을 노드로 취급하고 화살표가 가르키는 방향은 해당 웹페이지에서 가르키는 쪽의 웹페이지 쪽으로 접근이 가능하다는 것을 표시하는 것이다. 또한 노드 안의 숫자는 각 웹페이지의 page rank를 의미한다. 또한 Page rank의 값이 클수록 해당 웹페이지의 중요도가 크다는 것을 의미한다. 

2. Page rank 알고리즘

Figure2. 같은 경우 Pagerank를 MapReduce로 구현하였을 때의 pseudo 코드 이다. Map phase에서는 각 노드의 PageRank 값을 계산하여 node id와 Pagerank value를 Emit해준다. 그 후, Reduce phase에서 각 node id에 포함된 모든 Pagerank를 합산하여 새로운 pagerank를 구하여 Emit해준다.

Figure 3에서는 MapReduce를 2번 Iteration 한 것을 보여주는 그림이다. 첫번째 그림을 가볍게 설명해보면 Pagerank를 5개의 node에 공평하게 0.2로 나누고, edge의 화살표에 따라 해당 노드의 pagerank value를 분배해줍니다. 그후 Reduce phase에서 edge(화살표)에 있는 값을 aggregate 한 후 다음 Iteration에 Emit 해주는 방법입니다.

3. My Review

이번 알고리즘은 뭔가 실제로도 사용했던 알고리즘을 실제 데이터를 갖고 사용해봐서 좋은 기회였다고 생각한다. 특히 이 알고리즘은 굉장히 단순하지만 각 Iteration마다 체계적이여서 각 phase가 납득이 잘 가는 알고리즘이였다. 하지만 현재 구글 검색엔진에는 사용되지 않는데 그 이유는 들어가는 간선은 있지만 나가는 간선은 없는 정점 집합인 Spider Trap에 의한 문제와 Dead End에 의한 문제로 Pagerank 그 자체를 사용해서 현재 검색엔진을 사용하고 있지는 않다고 한다.

1. N-gram 이란?

N-gram 이란 간단하게 말해서 입력한 문자열을 N개의 기준 단위로 분리하는 방법이다.

예를 들어, "Here is a dog" 라는 문장을 단어 단위의 3-gram으로 만든다면,

"Here is a", "is a dog"로 만들 수 있다. 이렇게 할 경우 각 키워드에 따른 빈도(Relative Frequency)를 분석 할 수 있고, 검색어 엔진에서 키워드를 뽑아내거나 음성 인식에서도 쓰일 수 있다고 한다.

2. N-gram 알고리즘

   2-1. N-gram 실행 전 문자열 다듬기

String line = value.toString().replaceAll("[^A-Za-z]"," ");

나 같은 경우 자바에서 N-gram 알고리즘을 사용했었기에 이렇게 정규표현식과 replaceAll 함수를 사용 하여 문자를 다듬어 주었다. 이때, 알파벳이 아닌것들을 모두 공백으로 만들어 주었다.

   2-2. N-gram 단어 단위로 만들기

String word_list ="";

// Doing N-grams according to each word
                for(i = 0; i <= num_itr - N ; i++){
                    if(words[i] != null){
                        String key_word = words[i];
                        HashMap<String, Integer> map = new HashMap<String, Integer>();
                        if (input_map.containsKey(key_word)){
                            map = input_map.get(key_word);
                        }
                        //Make N-gram words
                        for (j = i + 1 ; j < i + N; j++){
                            word_list = word_list + " " + words[j]; //concat words
                        }
                        if (map.containsKey(word_list)){
                            map.put(word_list, (int) map.get(word_list) + 1);
                        }else {
                            map.put(word_list, 1);
                        }
                        input_map.put(key_word, map);
                        word_list = "";
                    }
                }

나 같은 경우 Java의 Hash map을 사용하여 N-gram 기준 keyword와 뒤에 따라오는 word_list로 구분해주었고, keyword에 따라 word_list를 생성해 N-gram 단어를 생성했다. 그 후, Hashmap에 있는지 없는지 여부를 확인해 그 단어를 count 해주었다.

3. My Review

맨 처음에 N-gram 알고리즘을 공부했을 때는 그냥 단순히 알고리즘 중 하나인줄 알았는데 이렇게 블로그를 쓰면서 조사를 해보니깐 N-gram 알고리즘은 Language Model에서 사용되는 기본적인 기술 중 하나라는 것을 알았다.

또한 N-gram 기반으로 담은 단어를 확률로도 예측 할 수 있는 것이 굉장히 과학적이라고 느껴졌다.

하지만 N-gram에도 정확도 문제가 있다.

예를 들어, N-gram 언어 모델은 이전의 N개의 단어만 고려하기 때문에, 앞 문장의 맥락을 놓치는 경우가 발생 할 수 있기 때문에 정확도가 떨어질 수 있다고 한다.