集合知プログラミング::似たユーザーを探す：：ユークリッド距離を使った方法

この前仕事で「似ているユーザー」を表示する必要があったのでその方法を共有します。

正直SQLを頑張れば、個人の情報からどうとでも似たユーザーを取得できそうですが、
今回は集合知プログラミングに載っていたユークリッド距離を用いる方法で実装しました。

最終的にSQLに落としこんでいて、バッチ処理で予めユーザー間の類似度を計算する必要もありませんでした（小規模だったので）。

ということで概念的には以下のようなイメージです。

例…身長(cm)を横軸、体重(kg)を縦軸にする。

A、B、C、Dはそれぞれユーザーを表してます。
Bさんは身長は低いけど体重が大きくて
Aさんは身長も高いし体重も大きいです。

こんな風に各要素をグラフの軸の値と見立てると
各ユーザーを2次元の空間に視覚的でわかるように
配置することができます。

もう見るとわかると思いますが、
CさんとDさんはとても距離が近く
似ているユーザーであることがわかります。

これを数式で表現してみましょう。

名前はともかく上の図の式は、
二点間の距離の公式として学生時代のどこかに出てきているかと思います。

式で表現することでより具体的になり
またプログラムで計算できる形になりました。

そしてそれぞれのユーザーごとに総当りに計算すると、

こんな感じになります。

数字的にもC-D間の距離が0.3で最小、
つまりユーザーの中で一番似ていることがわかりました。

ちなみに今回用いた式をユークリッド距離といいますが、
実際にこのまま使うと近いユーザーほど0に近づいて行きますが
遠いユーザーの場合は離れているだけ値が大きくなります
（10とか100とか、場合によってはプラス無限大まで）。

そこで今回はこのユークリッド距離の式を0〜1までの数になるように正規化します。
式は以下。

この式を使うとユーザーが似ていれば似ているほど
式の値は大きくなり１に近づき、
離れていると小さくなり０に近づきます。

これで各ユーザーごとに値を算出した後に降順でソートすることで、
似ているユーザーを似ている順に並べることができます。

あとは自分はSQLで上の数式を記述して使っています。
実行速度別に遅くなく式の計算にはそれほどコストを使っていません。

また今回は要素数は２つで２次元の空間を使って説明しましたが、
要素は無限に拡張可能です。増えただけ（）^2の項をルートの中に足していけばいいだけです。

実際こういった手法はいくつも方法が提案されていて、
ユークリッド距離の他にも、
ピアソン係数とかマンハッタン距離とかTanimoto係数とか色々あるらしいですが、
計算量で言えばこれが一番少なそうなのと、
別に精度を求めているわけではなかったのでこれを使いました。

もし似たような案件を抱えていたり、
別の方法で解決した方などいられたら
コメントください。

ではでは〜

参考書籍

僕のYak Shavingは終わらない