座学録

id:hikaru515 の技術ブログです

類似度のお話

まえがき

この記事は数学とコンピュータ Advent Calendarの6日目の記事です。

昨日は miurror さん、明日は junpeitsuji さんです。

本当は numpy で線形代数の話でもしようかと思ったり {\mathbb{Z}/n\mathbb{Z}} を Python で作るとかいう話をしようかと思ったんですが、ちょっと最近忙しすぎるので実装できませんでした。すみません。

以下ではプログラミング言語としてはPythonをつかいます。数式で {x} とか {y} と書いてあったらある次元のユークリッド空間の元だと思ってください。

類似度

2つのもの、あるいは複数のものが「似ている」ということを判断するにはどうすればいいでしょうか。

具体的には、「映画の好みが似ている」ことってどう測ればいいでしょう。

例えば5本の映画があったとして、その5本に1-5点で点数を振っていくとします。

映画1 映画2 映画3 映画4 映画5
A 4 3 5 1 2
B 1 1 5 1 2
C 3 4 2 5 5
D 4 4 5 2 5

このとき、Xさんという別の誰かが現れて、点数を 2, 2, 4, 1, 2 とつけた。X さんと映画の好みが近い人は AさんからDさんのうち誰でしょう?

距離

この問題はXさんの点数とAさんたちの点数の付け方の「距離」を測ればいいです。つまり、「距離」が短ければXさんと趣味が近く、「距離」が遠ければXさんと趣味が違う人だということになります。

この「距離」の測り方にはいろいろなものがあります。いくつかXさんと他の人の「距離」を計算してみましょう。

ユークリッド距離

映画5本につけられた点数をユークリッド空間 {\mathbb{R}^5} の点だと思えば、普通に最初に思い浮かべる距離はユークリッド距離でしょう。

{
\begin{equation}
d(x, y) = \sqrt{\sum_{i=1}^5(x_i - y_i)^2}
\end{equation}
}

実装すると次の関数になります。

def euclid(xs, ys):
    distance = 0
    for x, y in zip(xs, ys):
        distance += (x - y) ** 2
    return distance

A-DさんとXさんの距離を測ってみます。

from distance import euclid


def main():
    scores = {
        'A' : [4, 3, 5, 1, 2],
        'B' : [1, 1, 5, 1, 2],
        'C' : [3, 4, 2, 5, 5],
        'D' : [4, 4, 5, 2, 5],
    }
    x = [2, 2, 4, 1, 2]
    for key, score in scores.items():
        print(key, 'さん', euclid(x, score))


if __name__ == '__main__':
    main()

実行結果:

A さん 6
B さん 3
C さん 34
D さん 19

この場合、XさんはAさんやBさんとは趣向が近く、Cさんとはかなり違う趣向の持ち主のようだ、ということがわかります。

コサイン類似度

この場合は簡単すぎるのでこれでも納得感が得られますが、例えば「身長と年齢が近い」ことを測るときユークリッド距離を使うことは適切でしょうか?

身長が10cmと違うことと、年齢が10才違うことでは全く意味が違いますがユークリッド距離だと(単位を無視しているため)同じ10になってしまうます。

これは「絶対値」の影響を受けていると考えられます。そこで、絶対値を無視して「向き」だけを使って似ているかどうかを測りましょう。それがコサイン類似度です。コサイン類似度の場合は、似ているもののほうが値が大きくなります。

式で書くとこんな感じ。

{
\begin{equation}
d(x, y) = (x \cdot y)/|x||y|
\end{equation}
}

実装はこんな感じ(面倒だったので numpy を使いました)

def cosine(xs, ys):
    x = np.array(xs)
    y = np.array(ys)

    normal1 = x / np.linalg.norm(x)
    normal2 = y / np.linalg.norm(y)
    return np.dot(normal1, normal2)

内積を取ってからノルムで割るか、ノルムで割ってから内積をとるかの違いでしかないです。 ちなみに、先ほどの映画の例で類似度を計算してみると結果がユークリッド距離のときとは変わります。

A さん 0.97652701738
B さん 0.951971638233
C さん 0.773017239493
D さん 0.961154077756

ユークリッド距離のときは B A D C の順番でしたが、今回は A D B C という順番になっています。

このように、「どの距離を選ぶか」によって順位が変わります。どの距離が一番適切なのかは目的次第です*1

その他の距離

他にも距離はあります。例えばマンハッタン距離は各成分の差の和をとるものです。

{\begin{equation}d(x, y) = \sum_{i=1}^{n}|x_i - y_i|\end{equation}}

調べて見ると、他にもいろいろでてきます。例えばユークリッド内積も使えるでしょう。

類似度計算の応用

上の例で考えると、Xさんに似ているのはAさんやBさんでした。言い換えると、AさんやBさんが好きな映画をXさんも好む確率が高いと言えます。つまり、XさんにAさんやBさんが高評価をつけた映画を推薦できるわけです。

このように、Xさんと似ている趣向を持った人の購買履歴などからXさんに商品をリコメンドする仕組みのことを 協調フィルタリング と言います。Amazonなどの「この商品を買った人はこんな商品を買っています」は*2協調フィルタリングを体現している言葉です。

実際に僕もリコメンドシステムを作ったことがあります*3が、基本的には距離(類似度)を測ってソートする、という形でやっています。

まとめ

  • 2つのものの「距離」を測ることで似ているかどうかを判断できる
    • 「距離」 の定義により近いものが変わる
  • 「好み」が似ていることがわかれば、好みの近い人には推薦できる(リコメンドシステム)

僕の記事は以上です。

思っていたよりもずっと時間がとれず、どこか数学なんだという感じになってしまいましたが、最近生活が仕事に毒されていてこういうことしかかけませんでした。

何かありましたらおしらせください。

*1:このデータ、僕がてきとうに表計算ソフトに入力しただけなんですが、それでも順番が変わってしまう

*2:実装がどうなっているのかは知りませんが。

*3:本当のことをいうと僕は内容ベースフィルタリングのリコメンドシステムしか作ったことない。