検索システムのアルゴリズム（多数データの類似度の算出）

Question

研究で推薦システムを構築しようと考えております。
その際に、5つの軸（メタデータ）が-5～5の範囲でそれぞれのデータに付与されています。
ユーザがUIにそれぞれ5つを-5～5で入力し、ボタンを押すと、データベースのデータと類似度を計算し、類似度の高いもの10件を表示する、と言ったモノを考えているのですが、
この類似度はどのように算出するべきでしょうか。

例えば、データベースのすべてのデータを変数に取り込み、入力された値と類似度を算出していくとなると、
データベースのデータが多くなればなるほどメモリが圧迫されます。
もちろん現実的には不可能です。

世の中の推薦システムはどのようにして、データを計算し、推薦しているのでしょうか。

分かりにくい文章で申し訳ありません。何かご指摘があればよろしくお願い致します。

この仕組をご存じの方がいらっしゃいましたら、ご教授願います。
よろしくお願いいたします。

Answer 1

いろいろ手法はありますよ…
ひとつ、LSH をお伝えしておきます。
3日で作る高速特定物体認識システム (7) 最近傍探索の高速化
近似近傍点探索手法 Locality Sensitive Hashing
http://d.hatena.ne.jp/gnarl/20090409/1239288337

画像処理、物体認識、レコメンド…と「距離」、「コサイン距離」等で検索すると、いろいろ見つかることと思います。

追記、データを x_i とすると、x_i は5次元のベクトルで、K = [-5, 5]^5 としたとき、x_i ∊ K なんですよね？で、入力 y ∊ K に対して argmin[x_i] d(y, x_i) を求めたいという感じではないでしょうか。
http://aidiary.hatenablog.com/entry/20091122/1258853886
http://aidiary.hatenablog.com/entry/20091212/1260624075
の例では「SURF特徴量なのでd=128」で LSH を構築しています。参考文献ではキーポイントの最近傍点が見つかっただけなので、さらに「投票」によってマッチングをさせていますが、今回の文脈ではそれは不要です。LSH 等を用いた kNN の問題では、ないのでしょうか…。

Comments

[nnahito]

ご回答有難うございます．
すいません，類似度算出方法ではなく，その算出時にどのように計算を行うかです．

現在は，全てのデータを変数に取り込んで，変数内でランキングを作成していますが，
これはデータ数が500件という小規模なのでできています．
しかし，今後，データ数が数万件以上となっていきますので，この方式では対応できないと思い質問させて頂いております．

類似度の算出は，コサイン類似度を用いており，そのプログラムはすでに実装しております．
よろしくお願いいたします．

[takotakot]

書き方が悪かったんですかね…コサイン距離ではなくて、LSH です…
kNN (k nearest neighbor) で調べてみては。