Normalized compression distanceとNormalized Google distance

 文章間の類似度を測るおもしろい指標を発見したので、メモ。

Normalized compression distance

１つ目はNormalized compression distance（NCD）。日本語でいうと正規化圧縮距離。

アイデアを簡単にいうと以下のとおり。

文章xと文章yがある。

Z(d)をドキュメントdを圧縮したときのサイズ（圧縮アルゴリズムはgzip, gzip2など）とする。

もしxとyの関連性が高ければ、Z(x + y)と、Z(x)およびZ(y)間の差は小さくなるはずである。

以下Pythonで書いたサンプルコード。
共通する単語を多く含むものが関連性が高いと判断される。

# -*- coding: utf-8 -*-

import zlib

"""Normalized compression distance

See the page below for more details:
https://en.wikipedia.org/wiki/Normalized_compression_distance#Normalized_compression_distance

"""
def ncd(x,y):
    if x == y:
        return 0
    z_x = len(zlib.compress(x))
    z_y = len(zlib.compress(y))
    z_xy = len(zlib.compress(x + y))    
    return float(z_xy - min(z_x, z_y)) / max(z_x, z_y)

if __name__ == '__main__':
    query = 'Hello, world!'
    results = ['Hello, Python world!', 
               'Goodbye, Python world!', 
               'world record']

    for r in results:
        print r, ncd(query, r)

Normalized Google distance

2つ目はNormalized Google distance（NGD）。日本語でいうと正規化Google距離。

Googleじゃなくてもクエリに対する結果ページの総数を返してくれる検索エンジンであれば何でもよい。
似たような方法を昔自分で試したことがあるが、既知の手法だったらしい。

アイデアを簡単にいうと以下のとおり。

文章xと文章yがある。

F(q)をクエリqに対する検索結果件数とする。

文章xと文章yの関連性が高ければ、F(x + y)と、F(x)およびF(y)間の差は小さくなるはずである。

NGDは、NCDと違って、セマンティックな類似度を測定することが出来る。

以下Pythonで書いたサンプルコード。

きちんとbig apple = new york、SVM = support vector machineという関連性を距離に反映出来ている！！
以下のサンプルではクエリにマッチした検索結果はAPIで取ってきているが、APIには使用回数制限があるため注意。

# -*- coding: utf-8 -*-

import urllib
import json
from math import log

"""Normalized Google distance

See the page below for more details:
https://en.wikipedia.org/wiki/Normalized_compression_distance#Normalized_Google_distance

"""

def gcnt(q):
    url = 'https://ajax.googleapis.com/ajax/services/search/web?v=1.0&q=%s' % urllib.quote(q)
    res = urllib.urlopen(url)
    json_res = json.loads(res.read())
    return json_res['responseData']['cursor']['estimatedResultCount']

def ngd(x,y):
    if x == y:
        return 0
    f_x = log(float(gcnt(x)))
    f_y = log(float(gcnt(y)))
    f_xy = log(float(gcnt(x + y)))
    N = 50 * 1e9   # total number of indexed pages
    return (max(f_x, f_y) - f_xy) / (log(N) - min(f_x, f_y))

if __name__ == '__main__':
    # ex1) Which city is associated with "big apple?"
    query = 'big apple'
    results = ['Tokyo', 
               'London', 
               'Paris', 
               'New York']
    for r in results:
        print r, ngd(query, r)

    # ex2) Which is related with "SVM?"
    query = 'SVM'
    results = ['Random Forest', 
               'Gradient Boosting', 
               'Artificial Neural Network', 
               'Support Vector Machine']
    for r in results:
        print r, ngd(query, r)