슭의 개발 블로그

지난번 글에서는 압축 알고리즘을 통해서 두 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는 일반적으로 사용할 수 없고, 문자적으로 의미를 가지는 키워드를 비교할 때만 사용할 수 있다는 점과 특정 토픽 내에서의 유사도를 비교한다거나 하는 식으로 확장할 수 없다는 단점이 있다. 하지만 구글링할 수 있는 키워드를 일반적으로 비교할 때 쉽게 구현할 수 있다는 장점이 있다.

이번에 소개할 Normalized Compression Distance (a.k.a. NCD) 는 압축 알고리즘을 이용해서 두 object의 유사도를 측정하는 참신하고 재밌는 방법을 소개할 것이다. 이 방법은 간단하면서도 의외로 효과적이면서 기발한 방법이다. compression 알고리즘은 보통 효율적인 압축을 위해서 자주 등장하는 sequence일수록 더 짧은 길이로 압축하도록 노력한다. 따라서 같은 길이의 sequence가 더 짧은 길이로 압축됐다면, 이 sequence에는 반복되는 sub-sequence가 많이 있다는 말이 된다. NCD는 compression의 이러한 성질을 이용한다. 입력받은 sequence를 compression 한 길이를 리턴하는 함수를 Z 라고 할때 NCD의 수식은 다음과 같다. NCD ( x , y ) = [ Z ( x + y ) - min { Z ( x ) , Z ( y ) } ] / max { Z ( x ) , Z ( y ) } 즉, 비교할 두 sequence를 합친 sequence를 압축한 길이가 sequence를 따로따로 압축한 길이에 비해서 얼마나 더 짧아졌는가를 보여주는 것이다. 압축 알고리즘은 일반적으로 Z ( x + y ) 가 Z ( x ) + Z ( y ) 보다 작아서 NCD는 0에서 1 사이의 정규화된 값을 가진다. NCD가 1에 가까울수록 둘 사이에는 공통점이 없는 것이고, 0에 가까우면 둘은 매우 비슷한 패턴을 가지고 있는 것이다. NDC는 두 object를 binary sequence로 변환할 수 있는 경우에만 사용 가능하다는 문제가 있지만, 컴퓨터로 계산하는 대부분의 경우 binary sequence로 변환할 수 있으므로 큰 문제는 되지 않는다. NCD의 재밌는 점은 어떤 압축 알고리즘이든지 사용할 수 있다는 것이다. 덕분에 gzip, bzip, 7z 등 이미 존재하는 다양한 압축 알고리즘을 이용할 수 있어서 구현이 쉽지만, 비교할 object의 패턴에 따라...