2016-06-10

Normalized Compression Distance - 압축 알고리즘을 통해서 유사도 비교하기

 이번에 소개할 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의 패턴에 따라서 어떤 압축 알고리즘을 사용하는 것이 정확한 비교가 되는지 결정하기 어렵다는 단점이 있다.

댓글 없음:

댓글 쓰기