ユークリッド距離
集合知プログラミングをやりたくなった
オライリー社から発売されている書籍なのですが、ユーザーの行動履歴から、嗜好を分析するというプロモーションで使われる技法を紹介しています。言語はPythonです。
どんなことをしたいかというと、amazonでよく見かける「よく一緒に購入されている商品 」「この商品を買った人はこんな商品も買っています」というアレです。
この商品を買っている人は、たぶんこの商品も買うんじゃないかという統計をとる手法を紹介しています。
やってみよう
「2.2 嗜好の収集」をやってみました。
映画の評者といくつかの映画に対する評点となるデータを用意
JSON形式のデータをつくっておく
vi recommendations.py
critics={'Lisa Rose': {'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5, 'Just My Luck': 3.0, 'Superman Returns': 3.5, 'You, Me and Dupree': 2.5, 'The Night Listener': 3.0}, '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 2.5 (r25:51908, Nov 6 2007, 16:54:01) [GCC 4.1.2 20070925 (Red Hat 4.1.2-27)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from recommendations import critics >>> 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} >>> critics['Lisa Rose']['Lady in the Water'] 2.5
というわけでこの中から似ているうユーザーを探しだすということで、ユークリッド距離を求める、という方法があるらしい。
「似ている」って何?
Tobyは「Snakes on a Plane」を4.5点、「You, Me and Dupree」を1.0点と評しています。
Mick LaSalleは「Snakes on a Plane」を4.0点、「You, Me and Dupree」を2.0点と評しています。
この2者がどれほど似ているのか、という事をユークリッド距離ではかると次のような結果になります。
% python Python 2.5 (r25:51908, Nov 6 2007, 16:54:01) [GCC 4.1.2 20070925 (Red Hat 4.1.2-27)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from math import sqrt >>> sqrt( pow(4.5-4, 2) + pow(1-2, 2) ) 1.1180339887498949
この距離が小さい人ほど嗜好が似ていると判断します。つまりAさんとBさんがこの映画を両方とも5.0と4.0と同一の点数をつけた場合は次のようになります。
>>> sqrt( pow(5.0-5.0, 2) + pow(4.0-4.0, 2) ) 0.0
上記の例では2つの映画で比較していますが、もっと多くの映画に対しても原理は同じです。
というか似ている人同士ほど高いポイントにしたいんですけど
1を足して逆数をとりましょう
>>> 1 / ( 1 + sqrt( pow(4.5-4, 2) + pow(1-2, 2) ) ) 0.47213595499957939
関数化したい
recommendations.pyに関数を足してしまいます
vi recommendations.py
JSONデータの下に以下を足す
from math import sqrt def sim_distance(prefs, person1, person2): si = {} for item in prefs[person1]: if item in prefs[person2]: si[item]=1 if len(si) == 0: return 0 sum_of_squares = sum([pow(prefs[person1][item]-prefs[person2][item],2) for item in prefs[person1] if item in prefs[person2]]) return 1 / sqrt( 1 + sum_of_squares )
実行
>>> import recommendations >>> recommendations.sim_distance(recommendations.critics,'Lisa Rose','Gene Seymour') 0.38490017945975052
感想
「はじめてのPython」にリスト内包表記(Perlでいう、grep,map)のほうが30%ほど高速なのでリスト内包表記を推奨している箇所があったと記憶しているのですが、このサンプルの表現はちょっとつらいような気がします。
でもPythonは結構勉強してて楽しい言語なので興味がある人はちょっとこの本読んでみるとよいと思います。