【最近傍探索簡単実装！！】Annoy のすすめ

何の記事？？

Spotify社が開発した、高速最近傍探索のライブラリである Annoy を紹介します。

レコメンドなんかによく使われる最近傍探索と簡単なレコメンドの仕組みを紹介しています。
コードは追わなくてもレコメンドの仕組みを知りたい方は是非読んでみてください。

github.com

最近傍探索

Annoy の凄さを紹介する序章として「最近傍探索って何？」って話からしたいと思います。

最近傍探索が使われている代表的な例といえば、「レコメンド」です。

それでは、このレコメンドがどのように行われているか考えていきましょう。レコメンドの王道パターンに「あなたにおすすめの商品」という決まり文句があります。

これは、EC 閲覧者と似た趣味・嗜好を持っている人を探し出し、その人が評価を高くつけたものをレコメンドするものです。

例えば、以下のような評価があったとします。（例のため３人分で）

各映画に対して「太郎、花子、一郎」の三人に 0〜1.0 で評価してもらったとします。それでは太郎に近いのは花子、一郎のどちらでしょうか？

太郎は、スターウォーズやディープインパクトなどの SF が好きなようですね。
花子は、トイストーリーやポニョといった比較的ライトなものが好みのようです。
一郎は、アルマゲドン、ディープインパクトなど SF 好きであることがわかりますね。

太郎に近い趣味・嗜好を持っているのは誰？という質問に対する結果はもちろん「一郎」になるわけです。

これは、各映画に対する評価（スコア）で見比べましたね。

今回は 3人分のデータなので、人間の力でやってもそこまで遅くもならないし、数学が得意な人であれば「コサイン類似度」で求められる。と思う方もいるかと思います。

たしかに python のライブラリなどにコサイン類似度は備わっていて求められるのですが、これが何百万、何千万といったデータ量になったら人間の力ではとても、、、それに python のライブラリを使っても時間がかかってしまいます。（ページ開いて 15分後に「あなたへのおすすめ」が出ても意味ないですよね）

そこで登場するのが、最近傍探索です。

多少精度を落とす代わりに、速度を重要視してもっとも近いものを探し出すものです。 Annoy を使えば、この最近傍探索が簡単にできてしまうというわけです！！

Annoy

それでは Annoy というライブラリの紹介をしたいと思います。

Annoy は、Spotify（音楽配信サービス）が開発した最近傍探索を高速で実行するためのライブラリです。C++での実装ですが、python で使えるようにバインディングされています。
ちなみに Annoy は「Approximate Nearest Neighbors Oh Yeah」の略だそうです。
Oh Yeah ですよ！！いけいけな会社ですね笑

ちなみに Spotify は、非常に優秀なレコメンドエンジンを開発したことで有名で一時期システム都合？で Spotify のメンテナンスが入り停止することが決まった時なんかは twitter 上で「Spotify による音楽レコメンドがないなんて生きる意味を失ったようなものだ」なんて声がツイートされていました笑

使い方

それでは実際に使ってみましょう。

まずは python から呼び出せるように pip でインストールします。

pip3 install annoy

そして使い方です。
今回は使い方に集中したいためデータは先ほどの映画の評価で行います。

import numpy as np
from annoy import AnnoyIndex

np_taro = np.array([[0.1, 0.9, 0.8, 0.2, 0.1, 0.6, 0.7, 0.9, 0.1]]) # 太郎のデータ
np_demo = np.array([[0.9, 0.1, 0.1, 0.8, 0.9, 0.1, 0.2, 0.2, 1.0], [0.2, 0.8, 0.9, 0.1, 0.1, 0.7, 0.9, 0.9, 0.2]]) # 学習データ（花子と一郎のデータ）
annoy_model = AnnoyIndex(9) # 引数(9) は、次元数。今回は映画の数

# annoy には第一引数にインデックス、第二引数にデータを格納
annoy_model.add_item(1, np_demo[0]) # 学習データを追加（花子）
annoy_model.add_item(2, np_demo[1]) # 学習データを追加（一郎）

# モデルの作成
annoy_model.build(100)

# 太郎に近いものを探す（第一引数：太郎の特徴ベクトル、第二引数：返却する数）
annoy_model.get_nns_by_vector(np_taro[0], 1)
>> [2]

さて最後の行で [2] という結果が返却されましたね。

annoy では add_item の第一引数で指定したインデックスがメインで扱われます。
get_nns_by_vector ではインデックスが返却されるため、[2] というのはインデックス２で登録したもの、つまり「一郎」が一番近いですよという結果になっています。

たしかにさっき予想した通りの結果になっていますね。

このようにして annoy に大量のデータ（大量のインデックス）を発行しても素早く近しいベクトルを持っているインデックスを返却してくれます。

最後に

さすがにこれだけでは AI と呼ぶにはふさわしくないですが、特徴ベクトルの扱い方の勉強にレコメンドはとても良い題材です。

最近傍探索のライブラリは、facebook が開発したものなど含め多く出ているのですが、annoy の良いところは pip だけで導入できることです。導入コストが低いとそれだけでやる気になりますよね。

是非試してみてくださいね