자카드 유사도의 변형과 활용, 상세 설명

자카드 유사도(Jaccard similarity)는 두 집합의 유사도를 측정할 때 사용하는 방법 중 하나입니다.

 

2가지 사례만 들어보겠습니다.

 

뉴스를 언론에서 자체적으로 만들어낼 수도 있지만, 연합뉴스가 취재한 뉴스를 사와서 조금 수정한 뒤 배포하는 경우도 있습니다. 그러면 다양한 언론사에서 수집한 뉴스 데이터라도 비슷하거나 똑같은 뉴스가 있을 수 있는 것이죠. 만약 구글 뉴스처럼 사용자에게 뉴스를 제공하는 일을 한다면 문서 간 유사도를 파악해 비슷한 뉴스는 걸러내서 서비스해야 합니다.

 

다른 사례는 두 고객 간의 유사도를 파악하는 일입니다. 넷플릭스처럼 고객이 좋아할 만한 영화를 알고리즘으로 추천하는 일을 할 때, 고객 간 유사도를 사용할 수 있습니다. 나와 취향이 유사한 사람이 좋아한 영화는 내가 봐도 좋은 평점을 내릴 확률이 높습니다.

 

위 두 경우 모두에서 자카드 유사도를 이용할 수 있습니다.

 

자카드 유사도의 정의

두 집합 간의 자카드 유사도는 (교집합의 크기 / 합집합의 크기)로 정의됩니다.

 

예를 들어 abxxo와 abxx라는 두 개의 문자열이 있습니다. 두 문자열에 포함된 공통의 문자는 abx로 3개이고, 합집합의 크기는 abxo로 4입니다. 따라서 abxxo와 abxx 간의 자카드 유사도는 3/4인 것입니다.

 

 

이를 코드로 보면 아래와 같습니다.

s1 = 'abxxo'
s2 = 'abxx'

def jaccard_similarity(s1, s2):
    s1 = set(s1) 
    s2 = set(s2)
    return len(s1 & s2) / len(s1 | s2)

jaccard_similarity(s1, s2)

이 방식을 문서 간 유사도에 적용하기 위해서는 문서를 단어의 집합으로 표현해줘야 합니다. 그리고 두 문서에 공통으로 등장하는 단어를 두 문서에 등장하는 모든 단어 집합의 크기로 나누어줍니다.

 

이처럼 자카드 유사도는 집합 간 유사도를 측정하기 때문에, 문서에 등장한 단어의 배열 순서는 고려하지 못하게 됩니다. 만약 이게 문제가 된다면, 문서를 단어 집합으로 표현하는 대신 다른 방법을 이용할 수도 있습니다. 예를 들어 I love you를 {I, love, you}로 나누어주기보다는, {I ,  l, lo, ov, ve,  y, yo, ou}로 나타내는 것입니다. 2개 문자씩 짝지어주었지 깨문에 2-shingles라고 하는데, 문서를 k-shingles로 표현하면 단어 순서의 영향이 줄어들 것입니다.

 

Jaccard similarity for bags

그런데 자카드 유사도는 abxxo와 abxx에 공통으로 2번씩 등장하는 x의 존재를 다른 문자들과 똑같이 취급합니다. 그래서 abxxo와 abx 간의 자카드 유사도는 abxx와 같은 3/4입니다. 이 점을 고려해, 두 문자열에서 겹치는 문자에 대해서도 고려하는 게 Jaccard similarity for bags입니다.

 

bags는 가방이라는 뜻입니다. 가방에 들어 있는 물건은 안에서 뒤섞여 순서가 없지만, 같은 종류의 물건이 2개가 있을 수 있는 것에 비유한 것입니다.

 

위에서 x가 2번 겹친다는 점을 고려하면 abxxo와 abxx 간의 자카드 유사도는 분자가 4, 분모가 5로 4/5가 됩니다. 또는 분모 계산은 그냥 두 문자열의 길이를 단순히 합한 것으로 정의해, 4/9라고 할 수도 있습니다. 후자의 경우는 유사도의 최댓값이 1/2이 되므로 4/9 정도의 유사도면 높은 값입니다.

 

그런데 문서 간 유사도를 측정할 때는 같은 단어가 중복되는 게 그리 이슈는 아닙니다. 어떤 문서에 금리, 부동산, 불황, 코스피 등의 단어가 등장했다면, '금리'가 몇 번 등장했든 그 문서는 경제와 관련이 있을 것입니다.

 

한편 영화 평점 데이터로 사용자 간 유사도를 판별하는 문제를 보겠습니다. 두 사용자가 본 영화들의 집합으로 자카드 유사도를 계산할 경우, 평점이 반영되지 않습니다. 평점까지 고려한 유사도를 계산하기 위한 한 가지 옵션이 Jaccard similarity for bags를 이용하는 것입니다. 예를 들어 한 명이 5점 평점을 매겼고, 다른 한 명은 3점 평점을 매긴 영화가 있다면, 그 영화는 교집합 계산에서 3으로 계산합니다.

 

대량 문서에 대한 자카드 유사도 연산

위의 코드는 두 개의 문자열(또는 문서) 간의 자카드 유사도를 구할 때 사용할 수 있지만, 대규모 문서끼리의 유사도를 구할 때는 다른 방식을 이용하는 게 좋습니다. 

 

이를 위해 문서를 행렬로 나타냅니다.

 

	단어1	단어2	단어3	단어4
문서1	0	1	1	0
문서2	1	1	0	0
문서3	0	1	1	1

 

문서1에 단어2와 단어3이 등장한다는 것을 위의 방식으로 표현해준 것입니다. 여기서 문서1과 문서2에 등장하는 단어의 교집합의 크기는 문서1과 문서2 벡터의 점곱(dot product)과 같습니다. 한편 합집합은 두 벡터에 등장하는 1을 모두 더해준 뒤 교집합의 크기만큼 빼주면 됩니다.

 

이를 코드로 표현하면 아래와 같습니다.

def jaccard_similarity(docs1, docs2):
    # docs1, docs2: 단어가 출현하는 부분이 1이고 나머지는 0인 문서-단어 행렬
    intersections = np.dot(docs1, docs2.T)
    wordsums = docs1.sum(axis=1, keepdims=True) + docs2.T.sum(axis=0, keepdims=True)
    unions = wordsums - intersection
    return intersections / unions

위에서 docs1과 docs2는 자카드 유사도를 구하고자 하는 두 그룹의 문서들의 행렬 표현입니다. 위 함수의 output은 유사도 행렬(similarity matrix)입니다. 유사도 행렬의 [i, j]번째 원소 값은 docs1의 i번째 문서와 docs2의 j번째 문서 간의 유사도를 나타냅니다.

 

확률적으로 자카드 유사도 구하기

그런데 행렬곱으로 연산하더라도 넷플릭스처럼 대규모 데이터에서 모든 사용자 간의 유사도를 구해야 하는 일에는 다른 방법이 필요합니다. 자카드 유사도를 근사적으로 구하는 방식입니다. 확률적으로 자카드 유사도를 근사하는 방법이 있습니다.  

 

예를 들어 아래와 같은 두 문서 간의 자카드 유사도는 1/3입니다.

	단어1	단어2	단어3	단어4
문서1	0	1	1	0
문서2	1	1	0	0

위 행렬을 열(column)별로 보면 3가지 경우가 있습니다. 

 

• X: 문서1과 문서2가 모두 1인 경우
• Y: 문서1과 문서2 둘 중 하나만 1인 경우 
• Z: 둘 다 0인 경우

 

여기서 X는 (공집합)을 의미하고 Y는 (합집합 - 공집합)을 의미합니다. 따라서 X인 경우의 수를 x, Y인 경우의 수를 y라고 하면, 문서1과 문서2의 자카드 유사도는 x/(x+y)가 됩니다. 

 

이제 위의 행렬에서 임의(random)로 하나의 열을 추출한다고 하겠습니다. Z인 경우가 없다고 가정한다면, 그 열이 X일 확률은 문서1과 문서2의 자카드 유사도와 일치합니다. 이 점을 이용하면 위 행렬의 모든 열을 조사할 필요 없이, 일부 열만 랜덤으로 추출해서 X인 경우를 조사하면, 큰 수의 법칙에 따라 실제 자카드 유사도를 합리적으로 추론할 수 있습니다.

 

대규모 데이터에서의 자카드 유사도를 활용에 관한 상세한 내용은 책 Mining of Massive Datasets을 보시기를 추천드립니다.