あるデータともう１つのデータがどれだけ似通っているかを計算する方法はたくさんある。
http://wikiwiki.jp/cattail/?%CE%E0%BB%F7%C5%D9%A4%C8%B5%F7%CE%A5
その中でもユークリッド距離、ピアソンの積率相関係数、Jaccard係数をpythonで実装する。
集合知プログラミング第2章参考。
https://www.oreilly.co.jp/books/9784873113647/
ユークリッド距離
中学や高校の数学でならうような一般的な距離。２次元か３次元なら図で表せるしイメージもできるが、それ以上の次元はイメージできない。けどやっていることは基本的に3次以下と同じ。
(a_1, a_2, a_3, ... a_i), (b_1, b_2, b_3, ... b_i)
みたいな2つのデータがあったとき、ab間のユークリッド距離dは
d = \sqrt{(a_1 - b_1)^2 + (a_2 -b_2)^2 + (a_3 -b_3)^2 + ...+(a_i-b_i)^2}
このままだと距離が返ってくるが、0から1までの値で似ていれば似ているほど1に近くなる、みたいな類似度として分かりやすい値が欲しい。0での除算エラーを防ぐためにこのdに1を足して逆数をとるとそのような値を取ることが出来る。
1/(1 + d)
これをpythonで実装したのが以下。
import math
def sim_distance(prefs, person1, person2):
# person1とperson2が共に評価してるもののリスト
si = {}
for item in prefs[person1]:
if item in prefs[person2]:
si[item] = 1
# person1とperson2がどちらも評価してるものが無ければ類似性は0
if len(si) == 0 :
return 0
# 各項目ごとの差の平方
squares = [(prefs[person1][item] - prefs[person2][item]) ** 2 for item in si]
sum_of_sqrt = math.sqrt(sum(squares))
return 1/(1 + sum_of_sqrt)
以下のデータを使って類似度を求めてみる。
critcsはいくつかの映画と、その映画に対する各人の5点満点の評価を格納している。
critics = {
'Lisa Rose': {
'Lady in the Water': 2.5,
'Snakes on a Plane': 3.5,
'Just My Luck': 3.0,
'Superman Returns': 3.5,
'The Night Listener': 3.0,
'You, Me and Dupree': 2.5,
},
'Gene Seymour': {
'Lady in the Water': 3.0,
'Snakes on a Plane': 3.5,
'Just My Luck': 1.5,
'Superman Returns': 5.0,
'The Night Listener': 3.0,
'You, Me and Dupree': 3.5,
},
'Michael Phillips': {
'Lady in the Water': 2.5,
'Snakes on a Plane': 3.0,
'Superman Returns': 3.5,
'The Night Listener': 4.0,
},
'Claudia Puig': {
'Snakes on a Plane': 3.5,
'Just My Luck': 3.0,
'The Night Listener': 4.5,
'Superman Returns': 4.0,
'You, Me and Dupree': 2.5,
},
'Mick LaSalle': {
'Lady in the Water': 3.0,
'Snakes on a Plane': 4.0,
'Just My Luck': 2.0,
'Superman Returns': 3.0,
'The Night Listener': 3.0,
'You, Me and Dupree': 2.0,
},
'Jack Matthews': {
'Lady in the Water': 3.0,
'Snakes on a Plane': 4.0,
'The Night Listener': 3.0,
'Superman Returns': 5.0,
'You, Me and Dupree': 3.5,
},
'Toby': {
'Snakes on a Plane': 4.5,
'You, Me and Dupree': 1.0,
'Superman Returns': 4.0,
}
}
$ python
Python 3.5.1 (default, Nov 7 2016, 22:30:16)
[GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.42.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import recommendation
>>> recommendation.sim_distance(critics, 'Lisa Rose', 'Gene Seymour')
0.29429805508554946
ピアソンの積率相関係数
データが正規化されていない場合、単純にユークリッド距離を求めても微妙な結果しか出ない。例えば映画の評価で、AさんとBさんの好みが似通っている場合。この場合であればAさんとBさんの類似度は高くなって欲しい。映画X,Y,Zに対する二人の評価が以下のようだったとする。
| 映画X | 映画Y | 映画Z | |
|---|---|---|---|
| Aさん | 3 | 1.5 | 3.5 |
| Bさん | 4 | 2 | 5 |
好みは似通っているっぽいものの、Aさんはどちらかというと辛口評価、Bさんは甘口な評価。これを上のsim_distanceで計算すると類似度は0.348。評価点にバイアスというか下駄をはかせているような場合だと、いくら好みが似通っていてもユークリッド距離ではカバーしきれない。
こういうときに使うのがピアソンの積率相関係数。データ間の単純な距離ではなく、相関関係を数値化する。
\frac{ \sum_{i=1}^{n} (X_i - \bar{X})(Y_i - \bar{Y}) } { \sqrt{ \sum_{i=1}^{n} (X_i - \bar{X})^2} \sqrt{ \sum_{i=1}^{n} (Y_i - \bar{Y})^2} }
上付きバーは平均値。式を見ただけだと何してるのかよくわからないけど、分子は共分散、分母はそれぞれのデータの標準偏差を求めている。コサイン類似度の計算としても考えられるっぽい？（よく理解できてない…）
参考: http://mathtrain.jp/correlation
http://aoki2.si.gunma-u.ac.jp/lecture/Soukan/pearson.html
http://d.hatena.ne.jp/sleepy_yoshi/20110325/p1
これをpythonで実装
def sim_pearson(prefs, person1, person2):
si = {}
for item in prefs[person1]:
if item in prefs[person2]:
si[item] = 1
n = len(si)
if n == 0: return 0
mean1 = sum([prefs[person1][item] for item in si]) / n
mean2 = sum([prefs[person2][item] for item in si]) / n
variance1 = math.sqrt(sum([((prefs[person1][item] - mean1) ** 2) for item in si]))
variance2 = math.sqrt(sum([((prefs[person2][item] - mean2) ** 2) for item in si]))
covariance = sum([(prefs[person1][item] - mean1)*(prefs[person2][item] - mean2) for item in si])
if variance1 * variance2 == 0: return 0
return covariance / (variance1 * variance2)
>>> data = {'Asan': {'X': 3.0,'Y': 1.5,'Z': 3.5,},'Bsan': {'X': 4.0,'Y': 2.0,'Z': 5.0,}}
>>> recommendation.sim_pearson(data, 'Asan', 'Bsan')
0.9958705948858225
ユークリッド距離よりもかなり高い数値が出てきた。
じゃあピアソンの積率相関係数が最強じゃん、と思ったけど、散布図上で直線的な関係じゃないとうまく捉えられなかったり、比較データが正規分布してないといけなかったり、外れ値があるとそれに引きずられたりしてしまうみたいで、ある程度条件を揃えないといけない。
別のpython実装
集合知プログラミングの中では、同じピアソンの積率相関係数を求める関数を以下のような感じで実装してた。
def sim_pearson(prefs, p1, p2):
'''
Returns the Pearson correlation coefficient for p1 and p2.
'''
# Get the list of mutually rated items
si = {}
for item in prefs[p1]:
if item in prefs[p2]:
si[item] = 1
# If they are no ratings in common, return 0
if len(si) == 0:
return 0
# Sum calculations
n = len(si)
# Sums of all the preferences
sum1 = sum([prefs[p1][it] for it in si])
sum2 = sum([prefs[p2][it] for it in si])
# Sums of the squares
sum1Sq = sum([pow(prefs[p1][it], 2) for it in si])
sum2Sq = sum([pow(prefs[p2][it], 2) for it in si])
# Sum of the products
pSum = sum([prefs[p1][it] * prefs[p2][it] for it in si])
# Calculate r (Pearson score)
num = pSum - sum1 * sum2 / n
den = sqrt((sum1Sq - pow(sum1, 2) / n) * (sum2Sq - pow(sum2, 2) / n))
if den == 0:
return 0
r = num / den
return r
この本に載ってるこのコードを見た時、上の数式をどう式変形するとこういう実装になるのかが理解できなかったので、数式見たまんまをさきほどのように実装した。scipyにある scipy.stats.pearsonr で検算したところ、自分が実装したコードも、このコードも返ってくる値は同じだった。どっちの実装でもいいんだろうけど、どう式変形すると下の集合知プログラミングに載っていたようなコードになるのかは分からない… ご存じの方いたら教えてください。
Jaccard係数
集合と集合の類似度を計算する。
J( A, B ) = \frac { \mid A \cap B \mid } { \mid A \cup B \mid } = \frac { \mid A \cap B \mid } { |A| + |B| - \mid A \cap B \mid }
文章と文章の類似度を計算したい時に使う。文章Aに使われている単語と文章Bに使われている単語を抜き出して、その単語の和集合と共通部分から値を求める。
こういう場合であれば共通して使われている単語が多いほど類似度は高くなる。
def sim_jaccard(prefs, a, b):
si = {}
for item in prefs[a]:
if item in prefs[b]:
si[item] = 1
n = len(si)
if n == 0:
return 0
len_a = len(prefs[a])
len_b = len(prefs[b])
return n / (len_a + len_b - n)
>>> data = {'machine-learning': ['DNN', 'python', 'chainer', 'scikit-learn'], 'python-waf': ['python', 'django', 'flask', 'pyenv']}
>>> recommendation.sim_pearson(data, 'machine-learning', 'python-waf')
0.14285714285714285