文字間の距離をいろいろ試せるライブラリ

　最近参加したKaggleのコンテストでTF-IDFのcosine similarityやBM25というテキスト間の距離概念を知った。他にもテキスト間の距離が存在していて、PythonのDistanceというライブラリを使うと簡単に計算できる。

このライブラリの便利なところは、”文字”ではなく”単語”を構成要素として距離を測れるところ。

例えば、
hoge fuga foo bar
hige foge hoo car

のハミング距離を”文字”単位で測ると4（文字数で正規化して0.235）で、結構近いなーとなるが、
単語単位で見ると4（単語数で正規化して1.000）で遠いことになる。
テキスト処理の場合はBOWのように単語単位で処理する場合が多いと思うので、これは嬉しい。

　Distanceで計算できる距離には、

• hamming distance
• levenshtein distance
• Jaccard distance
• Sorensen distance

などがある。

　ちょっと遊んでみたのでコードを載せておく。

wikipediaからSVM, RF, ANNの説明文を持ってきて、"support vector machines"との距離を測ってみた。本来なら、lowercase変換/stopwords除去/stemmingなどの前処理を行うべきだが、今回はお試し実装なので省略した。

import re
import distance

if __name__ == '__main__':

    query = 'support vector machines'
    text = [
        'In machine learning, support vector machines (SVMs, also support vector networks[1]) \
        are supervised learning models with associated learning algorithms that analyze data \
        and recognize patterns, used for classification and regression analysis.',
        
        'Random forests are an ensemble learning method for classification, regression and \
        other tasks, that operate by constructing a multitude of decision trees at training \
        time and outputting the class that is the mode of the classes (classification) or \
        mean prediction (regression) of the individual trees.',
        
        'In machine learning and cognitive science, artificial neural networks (ANNs) are \
        a family of statistical learning models inspired by biological neural networks \
        (the central nervous systems of animals, in particular the brain) and are used to \
        estimate or approximate functions that can depend on a large number of inputs and \
        are generally unknown.'
    ]

    q = re.split('\W+', query)
    for i, t in enumerate(text):
        w = re.split('\W+', t)
        w = filter(len, w)
        
        print "text_%d: %f %f %f %f" % (i+1, distance.nlevenshtein(q, w, method=1), \
                distance.nlevenshtein(q, w, method=2), distance.sorensen(q, w), distance.jaccard(q, w))

以下結果。text_1がSVMの説明である可能性が高そうと予測できる。

text_1: 0.906250 0.906250 0.800000 0.888889
text_2: 1.000000 1.000000 1.000000 1.000000
text_3: 1.000000 1.000000 1.000000 1.000000