라벨이 NGD인 게시물 표시

Normalized Google Distance - 구글을 통해서 유사도 비교하기

 지난번 글에서는 압축 알고리즘을 통해서 두 object의 유사도를 비교하는 방법 을 소개하였었다. 이번에 소개할 방법은 지난번 방식보다 더 재밌는 방법이다. 이번에 소개할 방법은 Normalized Google Distance(a.k.a. NGD) 라는 방법으로 이름 그대로 구글을 이용한다. 구글을 이용하기 때문에 문자적으로 의미를 가지는 키워드에 대해서만 유사도를 비교할 수 있다.  만약 두 키워드가 비슷한 의미라면, 이 두 키워드 중 하나가 나오는 문서에 다른 키워드도 등장할 확률이 높다. 이를 구글을 이용해서 측정하는 것이다. 구글에 의해 검색되는 문서 전체의 수를 N 이라고 하고, 구글에 검색해 검색결과의 수를 리턴하는 함수를 f 라고 할 때, NGD의 수식은 다음과 같다. NGD ( x , y ) = max { log f ( x ) , log f ( y ) } - log f ( x , y ) / log N - min { log f ( x ) , log f ( y ) }  비교하고 싶은 각각의 키워드를 따로따로 검색했을 때의 결과와 함께 검색했을 때의 차이를 전체 문서의 수 N 으로 정규화하는 것이다. 이때 정확한 전체 문서 수를 아는 것은 사실 불가능하다. 그래서 NGD를 이용할 때는 IDF가 매우 낮은 단어의 문서 수를 전체 문서 수로 가정한다. 보통 the 나 a 같은 단어를 사용한다.  NGD는 0에서 ∞사이의 값을 가진다. 0에 가까울수록 둘은 유사한 키워드이다. 유사하지 않은 키워드는 비교하면 큰 값이 나온다. 보통 1보다 크면 둘은 유사하지 않다고 말한다.  NGD는 일반적으로 사용할 수 없고, 문자적으로 의미를 가지는 키워드를 비교할 때만 사용할 수 있다는 점과 특정 토픽 내에서의 유사도를 비교한다거나 하는 식으로 확장할 수 없다는 단점이 있다. 하지만 구글링할 수 있는 키워드를 일반적으로 비교할 때 쉽게 구현할 수 있다는 장점이 있다.