Pythonで距離・類似度計算時の実行時間比較

何かと計算することの多い類似度や距離をPythonで計算した場合、どのライブラリを使えば最も計算時間が短く済むのか気になったので調べました。対象によっては10万件のデータと類似度を計算して比較したりする必要があるので、計算速度の差は馬鹿にできませんね。

環境

• MacBook Pro ver 10.13.6
• メモリ 16GB 2133 MHz LPDDR3
• CPU 3.5GHz Intel Core i7
• Python 3.6.5
• numpy 1.14.5
• SciPy 1.1.0
• sklearn 0.19.1

比較内容

今回は以下の3種類の距離と類似度の実行時間について比較を行います。

• ユークリッド距離 (euclidean distance)
• マンハッタン距離 (manhattan distance)
• コサイン類似度 (cosine similarity)

比較的計算が単純なものと、割と使われる機会が多いものを選んでみました。最近使う必要があったからちょうどよかったとか、まさかそんな個人的な理由ではありますん。実はコードもほとんど使いまわした。
それぞれの距離or類似度を求める式に関しては、ここでは触れませんのであしからず。
そして、比較する計算方法は以下の4種類です。

• numpy
• SciPy
• scikit-learn (sklearn)
• math (pythonの標準実装ライブラリのみで計算)

これに関しては、適当に調べて目についたものを選びました。というかsklearnに距離計算用の関数が存在したことを初めて知りました。わざわざ距離計算でsklearnを使う機会ってあるんでしょうか。わたし、気になります。
また、今回距離を計算するのに適当に乱数でベクトルを生成しても良かったのですが、ちょうどこの前使ったから誰でも簡単に再現できるものをということでMNIST Datasetを利用しました。28px*28pxの手書き文字の画像データセットであり、60000件の学習データと10000件のテストデータが入っています。今回は1件のテストデータに対し60000件の学習データとの距離・類似度を計算する実行時間の比較を行いました。

結論：基本的にはnumpyが最強

うん、まあ、知ってた。Pythonといいつつ、コイツの中身ってCとFortranですもんね。計算量が膨大になればなるほど、他のライブラリとの差をガンガン広げてくれるでしょう。……基本的には。
若干含みのある言い方になっているのは、多対一で一気にマンハッタン距離を計算する時にだけsklearnの計算速度が上回ったからです。それどころか、多対一で計算した場合にはその他の距離計算でもnumpyに次ぐ速度を叩き出しました。
とはいえ結論は上に書いた通り、基本的にはnumpyだけを使って計算することが今回調べた限りでは最も良さげでした。時間の無い方、結論だけ知りたかった方はここまで読めば十二分です。
これ以降は、実行時間比較の方法について書いていきます。

作成プログラム

速度比較に使用したプログラムです。

ライブラリのインポート

今回使用したライブラリは以下の通りです。gzipはMNIST Datasetの画像データを開くために使用しています。

import gzip
import time
import numpy as np
from scipy.spatial import distance
import math
from sklearn.metrics.pairwise import euclidean_distances, manhattan_distances, cosine_similarity

データセットの読み込み

データセットの読み込みにはこちら参考にしました。

# 画像ファイル読み込み
def LoadImg(file_name):
    img_size = 784
    with gzip.open(file_name, 'rb') as f:
        data = np.frombuffer(f.read(), np.uint8, offset=16)
    data = data.reshape(-1, img_size)
    data = [d.astype('float64') for d in data]
    return data

file_dic={'train_img':'./gz/train-images-idx3-ubyte.gz','test_img':'./gz/t10k-images-idx3-ubyte.gz'}
train_imgs = LoadImg(file_dic['train_img'])
test_imgs = LoadImg(file_dic['test_img'])

ユークリッド距離

それぞれのライブラリを用いたユークリッド距離の計算プログラムは以下のようになりました。

# ユークリッド
def EucDist(train_imgs,test_img):
    print('EucDist')
    # numpy
    start = time.time()
    for train_img in train_imgs:
        np.linalg.norm(train_img - test_img)
    elapsed_time = time.time() - start
    print('numpy:\t\t{}'.format(elapsed_time))
    # SciPy
    start = time.time()
    for train_img in train_imgs:
        distance.euclidean(train_img,test_img)
    elapsed_time = time.time() - start
    print('SciPy:\t\t{}'.format(elapsed_time))
    # sklearn1：画像を1つずつ比較
    start = time.time()
    for train_img in train_imgs:
        euclidean_distances([train_img], [test_img])
    elapsed_time = time.time() - start
    print('sklearn-1:\t{}'.format(elapsed_time))
    # sklearn2：全学習データとテストデータを一気に比較
    start = time.time()
    euclidean_distances(train_imgs,[test_img])
    elapsed_time = time.time() - start
    print('sklearn-2:\t{}'.format(elapsed_time))
    # math
    start = time.time()
    length=len(test_img)
    for train_img in train_imgs:
        math.sqrt(sum([(train_img[i]-test_img[i]) * (train_img[i]-test_img[i]) for i in range(length)]))
    elapsed_time = time.time() - start
    print('math:\t\t{}'.format(elapsed_time))

マンハッタン距離

それぞれのライブラリを用いたユークリッド距離の計算プログラムは以下のようになりました。

# マンハッタン
def ManDist(train_imgs,test_img):
    print('ManDist')
    # numpy
    start = time.time()
    for train_img in train_imgs:
        np.linalg.norm(train_img - test_img,ord=1)
    elapsed_time = time.time() - start
    print('numpy:\t\t{}'.format(elapsed_time))
    # SciPy
    start = time.time()
    for train_img in train_imgs:
        distance.cityblock(train_img,test_img)
    elapsed_time = time.time() - start
    print('SciPy:\t\t{}'.format(elapsed_time))
    # sklearn1：画像を1つずつ比較
    start = time.time()
    for train_img in train_imgs:
        manhattan_distances([train_img], [test_img])
    elapsed_time = time.time() - start
    print('sklearn-1:\t{}'.format(elapsed_time))
    # sklearn2：全学習データとテストデータを一気に比較
    start = time.time()
    manhattan_distances(train_imgs,[test_img])
    elapsed_time = time.time() - start
    print('sklearn-2:\t{}'.format(elapsed_time))
    # math
    start = time.time()
    length=len(test_img)
    for train_img in train_imgs:
        sum([abs(train_img[i]-test_img[i]) for i in range(length)])
    elapsed_time = time.time() - start
    print('math:\t\t{}'.format(elapsed_time))

コサイン類似度

それぞれのライブラリを用いたユークリッド距離の計算プログラムは以下のようになりました。ここまでくると、mathオンリーで計算した時の書き方がひどいですね……。

# コサイン
def CosSim(train_imgs,test_img):
    print('CosSim')
    # numpy
    start = time.time()
    for train_img in train_imgs:
        np.dot(train_img,test_img) / (np.linalg.norm(train_img) * np.linalg.norm(test_img))
    elapsed_time = time.time() - start
    print('numpy:\t\t{}'.format(elapsed_time))
    # SciPy
    start = time.time()
    for train_img in train_imgs:
        distance.cosine(train_img,test_img)
    elapsed_time = time.time() - start
    print('SciPy:\t\t{}'.format(elapsed_time))
    # sklearn1：画像を1つずつ比較
    start = time.time()
    for train_img in train_imgs:
        cosine_similarity([train_img], [test_img])
    elapsed_time = time.time() - start
    print('sklearn-1:\t{}'.format(elapsed_time))
    # sklearn2：全学習データとテストデータを一気に比較
    start = time.time()
    cosine_similarity(train_imgs,[test_img])
    elapsed_time = time.time() - start
    print('sklearn-2:\t{}'.format(elapsed_time))
    # math
    start = time.time()
    length=len(test_img)
    for train_img in train_imgs:
        numerator = sum([train_img[i] * test_img[i] for i in range(length)])
        denominator = math.sqrt(sum([train_img[i]**2 for i in range(length)])) * math.sqrt(sum([test_img[i]**2 for i in range(length)]))
        numerator / denominator
    elapsed_time = time.time() - start
    print('math:\t\t{}'.format(elapsed_time))

#　結果
上記の関数を用いて、それぞれ実行した結果は以下のようになりました。

# 実行
EucDist(train_imgs,test_imgs[0])
ManDist(train_imgs,test_imgs[0])
CosSim(train_imgs,test_imgs[0])

結果

EucDist
numpy:		0.32334113121032715
SciPy:		0.8891909122467041
sklearn-1:	4.2101099491119385
sklearn-2:	0.49657607078552246
math:		25.029693841934204
ManDist
numpy:		0.43810391426086426
SciPy:		0.4702122211456299
sklearn-1:	3.502877950668335
sklearn-2:	0.325991153717041
math:		15.897640943527222
CosSim
numpy:		0.4950988292694092
SciPy:		1.8947288990020752
sklearn-1:	6.854857921600342
sklearn-2:	1.0720508098602295
math:		44.23673105239868

速い、numpy速い。そしてmathおっそ……。みなさん、この手の距離・類似度計算をするときは、素直に最適化されたライブラリを用いましょうね！
はい、とまあ詳細な結果が出たところで、上の結論で書いた通り基本的にはnumpyが最強です。ただ、sklearnで画像ベクトルを一気に入れて計算した場合のsklearnの速度もなかなかのものです。使う機会があるんでしょうかとか言って本当にごめんなさい。もっと一度に計算するベクトル数が増えれば、他でも上回ったりするのでしょうか。わたし、気になります。

参考サイト

• Distance computations (scipy.spatial.distance) — SciPy v1.1.0 Reference Guide
• python - How can the Euclidean distance be calculated with NumPy? - Stack Overflow
• sklearn.metrics.pairwise.euclidean_distances — scikit-learn 0.20.1 documentation
• sklearn.metrics.pairwise.manhattan_distances — scikit-learn 0.20.1 documentation
• sklearn.metrics.pairwise.cosine_similarity — scikit-learn 0.20.1 documentation
• python - Calculate cosine similarity given 2 sentence strings - Stack Overflow