두 단어의 '유사도'를 측정하기 (resemblance)

   구글이나 네이버에서 검색을 할 때, 영어 단어를 '정확히' 입력하지 않았을 경우, '비슷한' 단어로 검색할 것을 추천하는 것을 본 경험이 있을 것이다. 그와 같이, 두 단어가 정확히 같은 것인가를 판단하는 것이 아니라, 대충 비슷한 것인가를 판단할 수 있는 방법을 살펴 보자. 즉, '비슷한 정도'를 수치화 할 수 있는 방법을 살펴 보자.

   기본적인 아이디어는 단어를 잘게 자른 조각(그것을 shingle 이라 하자)들을 모은 후, 그 조각들이 많이 비슷하면 비슷할수록 두 단어가 비슷하다는 것이다. 예를 들어 보자. adenophorae radix  와  adenophora 를 비교하는 모습을 살펴 보자. 논의의 편의를 위하여 shingle 의 길이를 2 개로 제한하자.

adenophorae radix --> ad
adenophorae radix --> de
adenophorae radix --> en
adenophorae radix --> op
...
adenophorae radix --> di
adenophorae radix --> ix

따라서 adenophorae radix 의 shingle 은 { 'ad', 'de', 'en', ..., 'ix' } 가 된다. 같은 식으로 adenophora 에 대한 shingle도 구할 수 있다. 주어진 단어에 대한 shingle 의 집합을 S라 하자. 즉,

S('adenophorae radix', 2) = { 'ad', 'de', 'en', ..., 'ix' },
S('adenophora', 2) = { 'ad', ..., 'ra' }

가 된다. 쉽게 생각을 해보자. 위와 같이 shingle 을 정의한 상태에서, 두 단어가 '비슷하다'면? 즉, 두 집합이 비슷하다면? 그렇다면 두 집합을 교집합 시킨 것과 합집합 시킨 것이 유사할 것이다. 즉 두 집합 A 와 B에 대하여

n( A ∩ B ) ≒ n( A ∪ B )

일 것이다. 다시 표현하면,

n( A ∩ B ) ÷ n( A ∪ B ) ≒ 1.0

일 것이다. 따라서, 위의 경우에 대하여, resemblance R 을,

R(A,B) = n( A ∩ B ) ÷ n( A ∪ B )    --------------------------------- (1)

로 정의하면, 우리가 생각하는 것을 수학적으로 적절히 표현할 수 있게 된다. 극단적인 경우, R(A,A) = 1.0 인 것이다. 위 식을 C++ 코드로 간단히 표현해 보자.

std::set<std::string> get_shingle(const std::string& str, int size)

{

        std::set<std::string> shingle;

        int length = (int)(str.size());

        int max_pos = length - size;

        int i = 0;

        for(i = 0; i<=max_pos; i++){

                shingle.insert(str.substr(i, size));

        }

        return shingle;

}

 

bool get_resemblance(

const std::string& str1,

const std::string& str2,

double *r, double *c1, double *c2)

{

        std::set<std::string> s1 = get_shingle(str1, 2);

        std::set<std::string> s2 = get_shingle(str2, 2);

        if(s1.empty() == true || s2.empty() == true) return false;

        std::set<std::string> com;

        std::set<std::string> all;

        std::set_intersection(s1.begin(), s1.end(),

s2.begin(), s2.end(),

std::inserter(com, com.begin()));

        std::set_union(s1.begin(), s1.end(),

s2.begin(), s2.end(),

std::inserter(all, all.begin()));

 

 

        double com_size = (double)(com.size());

        double union_size = (double)(all.size());

 

        *r = com_size/union_size;

        *c1 = com_size/s1.size();

        *c2 = com_size/s2.size();

 

        return true;

}

(최대한 명시적 코드를 작성하기 위해 성능은 거의 고려하지 않음)

get_shingle 함수는 주어진 단어를 주어진 길이로 자른 조각 집합을 반환해 준다. get_resemblance 함수는 위의 식에 따라 계산한 값들을 반환한다. containment, 즉, 한 단어가 다른 단어에 '포함'되어 있는가 역시 '비슷한' 단어가 포함되어 있는가로 생각해 볼 수 있고, 쉽게 계산할 수 있다. get_resemblance 함수는 containment 까지 반환한다. 위 코드로 adenophorae radix 와 adenophora 의 resemblace 와 containment 를 구해 보면,

resemblance : 0.642857
containment of 'adenophora' in 'adenophorae radix' : 1.0
containment of 'adenophorae radix' in 'adenophora' : 0.642857

가 나온다. 어느 정도 합당한 값으로 보인다.

---

위의 알고리즘은 Syntactic Clustering of the Web(pdf임)에서 소개된 것으로, 인터넷에서 두 '문서'의 유사도를 계산하기 위하여 제안된 것이다. 위처럼 결과적으로 방법은 간단해도 그것은 어느 정도 수학적으로 뒷받침된다. 본 문서에서는, 두 문서의 유사도를 계산할 때, shingle 을 섞은 후^[각주:1] s 개를 선택해서 위의 식(1)처럼 계산하거나, m 번째 요소를 선택해서 식(1)처럼 계산하면 resemblance 에 대한 unbiased estimator 가 된다는 것이다. 또, shingle 은 자갈, 작은 돌, 로 해석할 수 있겠는데, 문서들을 단어들로 나눠서 단어들이 얼마나 비슷하게 본다는 개념에서 단어들을 '자갈'이라고 표현한 것이다. 하여튼 이와 같은 알고리즘을, 단어의 유사도를 찾기 위하여 나는 위처럼 다소 간단히 적용해 보았다. 음... 저 알고리즘을 적용해야 할 데이터가 결국은 사람이 눈으로 다시 한 번 확인을 해야만 하는 것이라서 대충 구현해도 되기 때문에...

1. 원래 문서에 permutation 으로 표현된 π 라는 operator 를 적용하는 것이 곧 배열을 무작위로 섞는 것을 의미한다. [본문으로]