目次
- Voyageとは
- 近似最近傍検索とは
- HNSWアルゴリズムとは
- voyagerを使ってみる
- インストール
- データの準備
- voyagerを使ってみる
- まとめ
- 参考
Voyageとは
Voyageは、インメモリのベクトルデータに対して、高速な近似最近傍検索を行うためのライブラリです。Spotifyが開発して、オープンソースで公開されています。Spotifyでも実際に、似た音楽のレコメンドなどのために使われているそうです。
Voyageのキモは、近似最近傍検索のアルゴリズムにHNSW(Hierarchical Navigable Small Worlds)を採用し、これを独自に実装している部分にあります。このアルゴリズムによって、大きな次元の特徴ベクトルをもつ莫大なデータに対して、効率的に検索を行うことができます。
近似最近傍検索とは
近似最近傍検索（Approximate Nearest Neighbor Search）とは、高次元空間内のデータセットから与えられたクエリ点に「近似的に」最も近いデータ点を効率的に見つけるためのアルゴリズムや手法を指します。
通常の最近傍探索は、与えられたクエリ点に対して最も近い点を正確に見つけることを目的としています。一方で、データセットが非常に大きい場合や、データの次元が非常に大きい場合は計算コストが非常に高くなってしまいます。
近似最近傍検索は、最近傍探索の正確性を少し犠牲にする代わりに、計算コストを大幅に削減するためのアプローチとして考えられています。
HNSWアルゴリズムとは
HNSWアルゴリズムは、高次元のデータにおける近似最近傍検索のためのアルゴリズムおよびデータ構造です。このアルゴリズムは、巨大なデータセットでの高次元ベクトルの近似最近傍検索を高速に行うことができます。
※ ここではアルゴリズムの詳細については割愛しています。詳細を知りたい場合は、論文などを参照してください。
イメージだけを簡単に説明すると、快速･急行･各駅停車を乗り換えるようなイメージです。目的地(=クエリ点)に対して、まずは｢快速｣で行ける最も近い駅に移動します。次に、｢急行｣に乗り換えて、最も近い駅に移動します。最後に、｢各駅停車｣に乗り換えて目的地に最も近い駅に移動することで、最近傍を探索します。
voyagerを使ってみる
voyagerを使ってみます。
インストール
■python
pip install voyager
データの準備
chabsaデータセットを使用します。
はじめにデータセットを読み込みます。
■python
# データの読み込み
df = pd.read_csv('../data/interim/chabsa-sentiment-analysis.csv')
df.head()
文章をトークンに分割します。ここでの分割にはspacyのja_core_news_mdを使用しています。
■python
# 文章をトークンに分割する
import spacy
nlp = spacy.load('ja_core_news_md')
def apply_nlp(text):
doc = nlp(text)
return [token.text for token in doc]
# tokensに分かち書きされた単語が入る
df['tokens'] = df['sentence'].apply(apply_nlp)
df.head()
次に埋め込みベクトル形式に変換します。ここではfasttextを使用します。
■python
# 変換のための関数の定義
def sentence_to_vec(list_words, ft_model):
"""
文章を受け取り、ベクトル化する(ベクトルの次元数は300)
:param list_words: 単語のリスト
:param ft_model: fastTextの学習済みモデル
"""
# 単語埋め込みを格納するリスト
M = []
for w in list_words:
# 各単語に対して、単語埋め込みを取得する
M.append(ft_model.get_word_vector(w))
# ベクトルがなかった場合はゼロベクトルを返す
if len(M) == 0:
return np.zeros(300)
# 単語埋め込みのリストをNumpy配列に変換する
M = np.array(M)
# 文章の各単語埋め込みの合計を取り、それを文章ベクトルとする
v = M.sum(axis=0)
# 正規化する
return v / np.sqrt((v ** 2).sum())
# fastTextの学習済みモデルを読み込む
ft_model = fasttext.load_model("../model/cc.ja.300.bin")
# ベクトルをNumpy配列に変換する
df['vectors'] = df['tokens'].apply(sentence_to_vec, ft_model=ft_model)
df.head()
これでvectors列に埋め込みベクトルが入りました。
voyagerを使ってみる
まず、vectors列を取り出してnumpy配列形式に変換します。あわせて、データ型をfloat32に変換します。
■python
from voyager import Index, Space
# Vectorの作成
vectors = np.stack(df['vectors'].to_numpy())
vectors = vectors.astype('float32')
配列からインデックスを作成します。第一引数でSpace.Euclideanとすることで、ユークリッド距離を使用するように指定しています。第二引数では、データの次元数を指定します。
その後、add_itemsメソッドを使って、Indexにデータを格納します。
■python
# Indexの作成 index = Index(Space.Euclidean, num_dimensions=300) index.add_items(vectors)
ここまででデータセットの準備が完了しました。
実際に検索を試してみます。
■python
query = '中古車販売'
# queryをベクトル化する
query_vector = sentence_to_vec(apply_nlp(query), ft_model=ft_model)
query_vector = query_vector.astype('float32')
# queryと類似した文章を5件取得する
neighbors, _ = index.query(query_vector, k=5)
neighbors
# 元々の文章を表示してみる
for i in neighbors:
print(i, df.iloc[i]['sentence'])
25 また、輸入中古車販売は、展示販売キャンペーンの展開などにより順調に推移しました 1931 中古車販売につきましては、新車販売からの下取車の他、オークション等による外部仕入により販売車両の確保に注力しましたが、販売台数は2,003台（前期比4.5％減 24 輸入新車販売につきましては、販売体制の強化や新型車の販売促進効果などにより販売台数が伸長し堅調に推移しました 337 クレジット事業は、住宅関連、高級時計、二輪の取扱いが拡大し、輸入車、中古車及びオートリースの取扱いが好調に推移したことから取扱高が増加いたしました 2087 米国では原油安等を背景に主に中大型車販売が増加し、中国では小型車減税政策等が販売台数を押し上げました
｢中古車販売｣というqueryに関連する、データセット内の文章を検索する事ができました。
まとめ
この記事では、spotifyが公開したvoyagerという近似最近傍検索ライブラリを使ってみることができました。