質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.64%

Python COS類似度計算の高速化

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 3,560

KK-31

score 22

数列同士のCOS類似度を計算する際の高速化について、質問させていただきます。

 質問内容

  1. 行列Aに対して、rand2で定義したデータとのコサイン類似度を求めた、配列cos_listを得たい場合、
    現在は、cos_simを内包表記で呼び出すことで、計算していますが、何らかの方法でここを高速化できないでしょうか?
     
import numpy as np
import time
def cos_sim(v1, v2): 
    return np.dot(v1, v2) / (np.linalg.norm(v1) * np.linalg.norm(v2))

print("データ生成中...")
rand1 = [ np.random.rand() for i in range(5000)] #5000個の乱数データを作成する。 #[0.43839043,0.8423294420,0.2342…]
rand2 =  [ np.random.rand() for i in range(5000)] #類似度を検索する対象となる乱数データ  #[0.139043,0.9442446246420,0.231342…]
A = np.array([rand1 for j in range(10000)],dtype=np.float32)  #[[0.43839043,0.8423294420,0.2342…],[0.43839043,0.8423294420,0.2342…],[0.43839043,0.8423294420,0.2342…], …]
print("データ準備完了")
start = time.time() #時間計測用変数

###------ーーーここを高速化したい。------ーーー
cos_list =[ cos_sim(rand2,a) for a in A] #コサイン類似度リスト #[0.73141,0.73141,0.73141, ...]
###------ーーー------ーーー------ーーーー
#※あくまで例なのでデータは、Aの各データをrand1で固定しているので、10000個の同じコサイン類似度リストが求まります。

print("完了時間:{0}".format(time.time() - start) + "[sec]") #>> 完了時間:2.42

以上、ご教授のほどよろしくお願い致します。

実行環境:Python3.X
CPU:仮想v6コア(AWS)

 考えたこと

何となく、早やくなりそうだけど、やり方がわからないのですが、
イメージ的にこんな事がやりたい気がしています。
(一回1:1の関係でリスト化して、numpyで一気に全体に対してCOS類似度を求める?)

# target_list = [ cos_sim(rand2,a) for a in A] 
target_list = [[rand2,a] for a in A] 
#とりあえず、rand2の列とaの列を1:1の関係でリストに定義して、ここからnumpyの機能でCOS類似度を一気に求められないでしょうか・・・
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

こんな感じでどうでしょうか。

import numpy as np
import time
def cos_sim(v1, v2): 
    return np.dot(v1, v2) / (np.linalg.norm(v1) * np.linalg.norm(v2))

print("データ生成中...")
rand1 = [ np.random.rand() for i in range(500)]
rand2 =  [ np.random.rand() for i in range(500)]
A = np.array([rand1 for j in range(1000)], dtype=np.float32)
print("データ準備完了")

# original
start = time.time() 
cos_list =[cos_sim(rand2,a) for a in A] 
print("完了時間:{0}".format(time.time() - start) + "[sec]")

# rand1とrand2をnumpy配列に
rand1 = np.array(rand1)
rand2 = np.array(rand2)
start = time.time() 
cos_list2 =[cos_sim(rand2,a) for a in A] 
assert np.allclose(cos_list, cos_list2), "error1"
print("完了時間:{0}".format(time.time() - start) + "[sec]")

# 先にスケーリングすることにする
def cos_sim2(v1, v2):
    return np.dot(v1, v2)

A = np.array([rand1 for j in range(1000)], dtype=np.float32)

start = time.time()
rand2 /= np.linalg.norm(rand2)
A /= np.linalg.norm(A, axis=1).reshape(-1, 1) 
cos_list3 =[cos_sim2(rand2,a) for a in A] 
assert np.allclose(cos_list, cos_list3), "error2"
print("完了時間:{0}".format(time.time() - start) + "[sec]")

""" =>
データ生成中...
データ準備完了
完了時間:0.059908390045166016[sec]
完了時間:0.021083831787109375[sec]
完了時間:0.003892183303833008[sec]
"""

先にスケーリングすると1桁速くなりますね(たぶんスケーリング時間込みでも)。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/11/28 08:23

    大変参考になりました。
    ありがとうございます。

    キャンセル

0

import timeit
import numpy as np

# 入力データ
A = np.random.rand(10000, 5000)
b = np.random.rand(5000)

# 質問欄のやり方
def cos_sim(v1, v2): 
    return np.dot(v1, v2) / (np.linalg.norm(v1) * np.linalg.norm(v2))

# Vectorized Computation
def cos_sim2(v1, v2):
    return np.inner(A, b) / (np.linalg.norm(v1, axis=1) * np.linalg.norm(v2))

# 質問欄の書き方
loop = 10
secs = timeit.timeit('[cos_sim(b, a) for a in A]', globals=globals(), number=loop)
print(secs / loop)

# Vectorized Computation
secs = timeit.timeit('cos_sim2(A, b)', globals=globals(), number=loop)
print(secs / loop)
0.1224646340124309  # 質問欄のやりかた
0.09451284902170301  # 一度に計算するやり方

numpy を使えば、基本的に for ループを使う必要性はないはずです。

一度の呼び出しで計算するやり方を記載しました。(配列の各要素ではなく、配列全体に一気に演算を適用する計算方法を vectrized computation といいます。)

約1.3倍ほど早くなりました。これ以上の劇的な高速化は難しいかもしれません。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/11/28 08:24

    大変参考になりました。こんな書き方があるんですね・・・。
    ありがとうございます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.64%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る