빅데이터 2 week 정리 (mining massive datasets)

keyword 

자카드 유사도 -->

(ex 문서의 유사성, 표절, 미러 페이지, 출처가 같은 기사들)(ex 유사 집합 문제에서의 협업 필터링, 온라인 구매, 영화 순위) ***bag similarity 만약 특정 상품에 n개의 별을 준다면, 집합에 해당 상품을 n번 넣는다. 이후 자카드 유사도를 판단하는 과정에서 백 유사성 (Bag-similarity)를 사용한다. 교집합을 구하는 과정에선 해당 원소가 나오는 최소횟수를 구해주고, 합집합을 구할때는 나오는 전체 갯수로 구해준다.

 

 

k-shingles(슁글) -->

문서 내에서 발견되는 길이가 k인 부분문자열로 정의

(슁글의 크기는 보통 5~10)

 

 

characteristic matrix(특성 행렬) -->

행렬의 열은 집합에 해당되며, 행은 집합의 원소들에 해당됨. 

 

 

sparse matrix(희소 행렬) -->

0과 1로 구성되는 행렬(1보다 0이 많다.)

 

 

minhash(민해쉬) -->

구성하고자 하는 집합에 대한 시그니처는 수백 개의 아주 많은 계산 결과로 구성되며, 그 계산들 각각을 이루는 말임.

 

 

minhashing(민해싱) -->

특성 행렬에서 열로 표현되는 집합을 민해싱 하기 위해 행들을 치환(permutation)한다. (특정 열의 민해시 값은 변경된 순서에서 첫 번째로 1을 갖는 행의 번호임.) 민해시 함수 h는 행렬의 행(row)을 내부적으로 재정렬한다.

 

 

"""

행을 무작위로 치환하는 민해시 함수가 두 집합에 대해 같은 값을 생성할 확률은 그 두 집합의 자카드 유사도와 같다.

증명은 by-yourself!

"""

 

 

minhash-signature(민해시 시그니처)  -->

특성 행렬 M에 대하여 치환 h1, h2, h3, ..., hn으로 결정되는 민해시 함수를 호출하면 집합 S를 표현하는 열로부터 S에 대한 민해시-시그니처(minhash-signature)인 벡터 [h1(S), h2(S), ..., hn(S)]를 만들 수 있다. 이런 해시 값 리스트는 보통 하나의 열로 표현한다. 그렇기 때문에, 행렬 M으로부터 하나의 시그니처 행렬(signature-matrix)를 생성할 수 있다. #이 말은 즉슨, M의 i번째 열은 해당 열(집합)에 대한 민해시 시그니처로 대체된다는 뜻.

열 갯수는 같지만 행의 갯수는 줄어든다. 일반적으로 시그니처 행렬은 M보다 크기가 훨씬 작다.

 

Thus, instead of picking n random permutations of rows, we pick n randomly chosen hash functions h1, h2, . . . , hn on the rows. We construct the signature matrix by considering each row in their given order. Let SIG(i, c) be the element of the signature matrix for the ith hash function and column c. Initially, set SIG(i, c) to ∞ for all i and c. We handle row r by doing the following: 1. Compute h1(r), h2(r), . . . , hn(r). 2. For each column c do the following:

 

(a) If c has 0 in row r, do nothing. 

 

(b) However, if c has 1 in row r, then for each i = 1, 2, ..., n set SIG(i, c) to the smaller of the current value of SIG(i, c) and hi(r).

 

예시)

#예제의 행렬 사이즈가 작아 estimated-Jaccard similarity가 true-Jaccard similarity에 근접하다는 사실은 확인이 어렵다.

 

 

3.3절 연습문제 해설 (3.3.1 ~ 3.3.3 까지 완료 이후 진행중)

import sys
import itertools as itor
import math
import re
import numpy as np


def fig_3_2():
    """fig.3.2의 데이터를 return한다"""
    s1 = [1, 0, 0, 1, 0]
    s2 = [0, 0, 1, 0, 0]
    s3 = [0, 1, 0, 1, 1]
    s4 = [1, 0, 1, 1, 0]

    mat = [s1, s2, s3, s4]
    #data = np.array(num_rows, num_cols)
    """
    for i in num_cols:
        for j in num_rows:
            data[j, i] = mat[i][j]
    """
    return mat


def fig_3_4():
    """fig. 3.4를 return한다."""

    return fig_3_2()


def fig_3_5():
    """column-major"""

    s1 = [0, 0, 1, 0, 0, 1]
    s2 = [1, 1, 0, 0, 0, 0]
    s3 = [0, 0, 0, 1, 1, 0]
    s4 = [1, 0, 1, 0, 1, 0]

    return [s1, s2, s3, s4]


def shape(col_major):
    num_rows, num_cols = len(col_major[0]), len(col_major)
    return num_rows, num_cols


def jaccard_sim_naive(char_mat):
    """
    true Jaccard similarity
    characteristic matrix의 jaccard similarity를
    계산하기 위한 가장
    naive method이다
    """
    _, set_num = shape(char_mat) #num cols(열의 숫자를)
    sim_mat = np.zeros((set_num, set_num))
    for i, s1 in enumerate(char_mat):
        print(i, s1)
        for j, s2 in enumerate(char_mat):

            if i == j:
                sim_mat[i, j] = 1
            else:
                num_X, num_Y = 0, 0
                #type X 와 type Y row의 수를 계산
                for v1, v2 in zip(s1, s2):
                    if v1 == v2 == 1:
                        num_X += 1
                    elif v1 != v2:
                        num_Y += 1
                sim_mat[i, j] = float(num_X) / float(num_X + num_Y)
    return sim_mat


def minhash_naive(char_mat):
    num_rows = len(char_mat[0])
    set_num = len(char_mat)
    sim_mat = np.zeros((set_num, set_num))
    total_num = math.factorial(num_rows)
    for i, s1 in enumerate(char_mat):
        for j, s2 in enumerate(char_mat):
            same_hash_num = 0
            for perm in itor.permutations(range(num_rows)):
                for idx in perm:
                    if s1[idx] == s2[idx] == 1:
                        #permutation that make the two col
                        same_hash_num += 1
                        break
                    elif s1[idx] != s2[idx]:
                        break
            sim_mat[i, j] = float(same_hash_num) / float(total_num)
    return sim_mat


def calc_sig_math(char_mat, hash_funcs, elements = None):
    """signature matrix를 characteristic matrix로 부터 계산한다."""
    num_rows, num_cols = len(char_mat[0]), len(char_mat)
    num_hf = len(hash_funcs)
    sig_mat = np.zeros((num_hf, num_cols))

    elements = elements or range(num_rows)

    for i in range(num_hf):
        for j in range(num_cols):
            sig_mat[i, j] = sys.maxsize

    for k in range(num_rows):
        for i, hf in enumerate(hash_funcs):
            hash_value = hf(elements[k])
            for j, cols in enumerate(char_mat):
                if cols[k] == 1:
                    sig_mat[i, j] = min(sig_mat[i, j], hash_value)

    return sig_mat

def jaccard_sim(sig_mat):

    num_rows, num_cols = sig_mat.shape

    sim_mat = np.zeros((num_cols, num_cols))

    for i in range(num_cols):
        for j in range(num_cols):
            if i == j:
                sim_mat[i, j] = 0
            else:
                same_hash_num = 0
                for k in range(num_rows):
                    if sig_mat[k, i] == sig_mat[k, j]:
                        same_hash_num += 1
                sim_mat[i, j] = float(same_hash_num) / float(num_rows)

    return sim_mat


def exercise_3_3_1():
    chart_mat = fig_3_2()

    def a():
        print(jaccard_sim_naive(chart_mat))

    def b():
        print(minhash_naive(chart_mat))

    a()
    b()

def exercise_3_3_2():
    def h1(x):
        return (x + 1) % 5

    def h2(x):
        return (3*x + 1) % 5

    def h3(x):
        return (2*x + 4) % 5

    def h4(x):
        return (3*x - 1) % 5
    print(calc_sig_math(fig_3_4(), [h1, h2, h3, h4]))

def exercise_3_3_3():
    chart_mat = fig_3_5()

    hash_funcs = [lambda x: (2*x+1)%6, lambda x: (3*x+2)%6, lambda x: (5*x+2)%6]
    #print(hash_funcs)
    def a():
        print(calc_sig_math(chart_mat, hash_funcs))

    def b():
        for hf in hash_funcs:
            res = []
            for i in range(6):
                res.append(str(hf(i)))
            print(', '.join(res))
    def c():
        print("True jaccard similarity:")
        print(jaccard_sim_naive(chart_mat))
        print("\nEstimated jaccard similarity:")
        print(jaccard_sim(calc_sig_math(chart_mat, hash_funcs)))
    a()
    b()
    c()



def exec_exercises(_globals):
    prog = re.compile('exercise_.*')
    for func_name in _globals:
        m = prog.match(func_name)
        if m:
            _globals[m.group(0)]()


exec_exercises(globals())