集合知プログラミング 2章1
買って積み本になっていた集合知プログラミングを少しやってみたのでメモです。
サンプルコードはPythonで書かれていて、
http://examples.oreilly.com/9780596529321/PCI_Code.zip
からダウンロードできます。
今回やったのは以下の部分
2章 推薦を行う
2.1 協調フィルタリング
2.2 嗜好の収集
2.3 似ているユーザを探し出す
2.3.1 ユークリッド距離によるスコア
2.3.2 ピアソン相関によるスコア
2.3.3 どちらの類似性尺度を利用すべきなのか？
2.3.4 評者をランキングする
2.4 アイテムを推薦する
ユーグリット距離とピアソン相関です。
データはPythonの以下のように辞書型(ハッシュ)になっていて、データが多いときはデータベースでやるといいよと書いてあったので、今回はsqlite3でやることにしました。
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}}
sqlalchemyを使ってテーブルの作成とデータのINSERT、サンプルプログラムと同じようにユーグリット距離とピアソン相関の計算をしています。
sqlalchemyはわざわざCREATE TABLE～～のようにSQLを書かなくても自動でテーブルを作ってくれるので便利です。
#! /usr/bin/env python
#! vim: fileencoding=utf8
import os
from math import pow, sqrt
from sqlalchemy import create_engine
from sqlalchemy import Table, Column, Integer, String, ForeignKey, Float
from sqlalchemy.ext.declarative import declarative_base
from sqlalchemy.orm import relation, backref
#_Debug = True
_Debug = False
BASE_PATH = os.path.dirname(os.path.abspath(__file__))
DATA_PATH = os.path.join(BASE_PATH, 'data')
if not os.path.exists(DATA_PATH):
os.makedirs(DATA_PATH)
DB_FILE = os.path.join(DATA_PATH, 'data.db')
engine = create_engine('sqlite:///%s' % DB_FILE, echo=_Debug)
Base = declarative_base()
metadata = Base.metadata
class User(Base):
__tablename__ = "users_table"
id = Column('id', Integer, primary_key=True)
name = Column('name', String)
def __init__(self, name):
self.name = name
def __repr__(self):
return "<User<' %s'>" % self.name
class Movie(Base):
__tablename__ = "movies_table"
id = Column(Integer, primary_key=True)
name = Column(String, nullable=False)
def __init__(self, name):
self.name = name
def __repr__(self):
return "<Movie<' %s'>" % self.name
class Score(Base):
__tablename__ = "scores_table"
id = Column(Integer, primary_key=True)
user_id = Column(Integer, ForeignKey('users_table.id'))
movie_id = Column(Integer, ForeignKey('movies_table.id'))
score = Column(Float)
def __init__(self, user, movie, score):
self.user = user
self.movie = movie
self.score = score
def get_score(self):
return self.score
#return self.score /10.0
def __repr__(self):
return "<Score<' %s' ' %s' ' %s'>" % (
self.user.name,
self.movie.name,
self.score)
Score.user = relation(User, backref=backref('scores', lazy='dynamic'))
Score.movie = relation(Movie, backref=backref('scores', lazy='dynamic'))
users_table = User.__tablename__
movies_table = Movie.__tablename__
score_table = Score.__tablename__
metadata.create_all(engine)
from sqlalchemy.orm import sessionmaker
Session = sessionmaker(bind=engine)
session = Session()
def initial():
'''
初期データ挿入
'''
users_list = [
User(i) for i in [
'Lisa Rose', 'Gene Seymour', 'Michael Phillips', 'Claudia Puig', 'Mick LaSalle',
'Jack Matthews', 'Toby'
]
]
movies_list = [
Movie(i) for i in [
'Lady in the Water', 'Snakes on a Plane', 'Just My Luck', 'Superman Returns',
'You, Me and Dupree', 'The Night Listener'
]
]
for u in users_list:
session.add(u)
for m in movies_list:
session.add(m)
score_list = [
#La Sn Ju Su Yo Th
[2.5, 3.5, 3.0, 3.5, 2.5, 3.0], #Lisa
[3.0, 3.5, 1.5, 5.0, 3.5, 3.0], #Gene
[2.5, 3.0, None, 3.5, None, 4.0], #Michael
[None, 3.5, 3.0, 4.0, 2.5, 4.5], #Claudia
[3.0, 4.0, 2.0, 3.0, 2.0, 3.0], #Mick
[3.0, 4.0, None, 5.0, 3.5, 3.0], #jack
[None, 4.5, None, 4.0, 1.0, None] #Toby
]
for u_id, u in enumerate(score_list):
for m_id, m in enumerate(u):
if m:
session.add(Score(
user=users_list[u_id],
movie=movies_list[m_id],
score=m)
)
session.commit()
def hoge():
'''
ためし
'''
#Tobyさんの評価を取得
u = session.query(User).filter_by(name="Toby").first()
print u.scores.all()
#スーパーマンの映画から評価を取得してTobyさんのを表示
m = session.query(Movie).filter_by(name="Superman Returns").first()
print m.scores.filter_by(user=u).all()
#スーパーマンの映画の評価を取得
for i in m.scores.all():
print "user %s score %s" % (i.user.name, i.score)
def sim_distance(session, person1, person2):
"""
person1とperson2の距離を元にした類似性スコアを返す
"""
from sqlalchemy import or_
p1 = session.query(User).filter_by(name=person1).first()
p2 = session.query(User).filter_by(name=person2).first()
movies = [i.movie for i in session.query(Score).filter(Score.user==p1) if
i.movie in (j.movie for j in session.query(Score).\
filter(Score.user==p2))]
if movies == 0:
return 0
sum_of_squares = sum([pow(
session.query(Score).filter(Score.user==p1).filter(Score.movie==m).\
first().get_score() -
session.query(Score).filter(Score.user==p2).filter(Score.movie==m).\
first().get_score()
, 2) for m in movies])
return 1/(1+sum_of_squares)
def sim_person(session, person1, person2):
"""
person1とperson2のピアソン相関係数を返す
"""
p1 = session.query(User).filter_by(name=person1).first()
p2 = session.query(User).filter_by(name=person2).first()
movies = [i.movie for i in session.query(Score).filter(Score.user==p1) if
i.movie in (j.movie for j in session.query(Score).\
filter(Score.user==p2))]
count = len(movies)
if count == 0:
return 0
sum1 = sum([s.get_score() for s in session.query(Score).filter(Score.user==p1)
if s.movie in movies])
sum2 = sum([s.get_score() for s in session.query(Score).filter(Score.user==p2)
if s.movie in movies])
sum1sq = sum([pow(s.get_score(), 2) for s in session.query(Score).filter(Score.user==p1) if s.movie in movies])
sum2sq = sum([pow(s.get_score(), 2) for s in session.query(Score).filter(Score.user==p2) if s.movie in movies])
psum = sum([
session.query(Score).filter(Score.user==p1).filter(Score.movie==m).first().get_score() *
session.query(Score).filter(Score.user==p2).filter(Score.movie==m).first().get_score()
for m in movies])
num = psum-(sum1*sum2/count)
den = sqrt((sum1sq-pow(sum1, 2)/count)*(sum2sq-pow(sum2, 2)/count))
if den == 0:
return 0
"""
print "num %s" % num
print "den %s" % den
print "sum1 %s" % sum1
print "sum2 %s" % sum2
print "sum1sq %s" % sum1sq
print "sum2sq %s" % sum2sq
print "psum %s" % psum
"""
return num/den
def topMaches(session, person, n=5, similarity=sim_person):
scores = [(similarity(session, person, other.name), other.name)
for other in session.query(User).filter(User.name!=person)]
scores.sort()
scores.reverse()
return scores[:n]
def getRecommendations(session, person, similarity=sim_person):
from sqlalchemy.sql import exists
totals = {}
simSums = {}
for other in session.query(User).filter(User.name!=person):
sim = similarity(session, person, other.name)
#print "sim %s" % sim
if sim <= 0:
continue
for s in other.scores:
#まだ評価していなものを計算
if not session.query(Score).\
filter(Score.user==session.query(User).\
filter(User.name==person).first()).\
filter(Score.movie==s.movie).count():
totals.setdefault(s.movie, 0)
totals[s.movie] += s.get_score() * sim
simSums.setdefault(s.movie, 0)
simSums[s.movie] += sim
rankings = [(total/simSums[movie], movie.name) for movie, total in totals.iteritems()]
rankings.sort()
rankings.reverse()
return rankings
if __name__ == "__main__":
#initial() #最初にDBを作ってデータを入れる関数、最初以外はコメントアウト
#hoge()
print sim_distance(session, "Lisa Rose", "Gene Seymour")
print sim_person(session, "Lisa Rose", "Gene Seymour")
print topMaches(session, 'Toby', n=3)
print getRecommendations(session, 'Toby')
print getRecommendations(session, 'Toby', sim_distance)
これを実行すると、sqlite3に
users_table, movies_table, scores_table の3つのテーブルの作成、初期データの挿入、計算のためのSQL文が発行されます。
実行結果は以下の通りになります。
0.148148148148
0.396059017191
[(0.99124070716192991, u'Lisa Rose'), (0.92447345164190486, u'Mick LaSalle'), (0.89340514744156474, u'Claudia Puig')]
[(3.3477895267131017, u'The Night Listener'), (2.8325499182641614, u'Lady in the Water'), (2.5309807037655649, u'Just My Luck')]
[(3.5002478401415877, u'The Night Listener'), (2.7561242939959363, u'Lady in the Water'), (2.4619884860743739, u'Just My Luck')]
ところが、このプログラム、最初の方にある_DebugをTrueにして、実行しているSELECT文の数を数えると、なんと554個、、、、。
O/Rマッパーは便利だけど集計するには自分でSQL文を打った方が効率が良いです。また、上のプログラムはテーブルと密接してるので、他のテーブルには使えません。
ユーグリッド距離もピアソン相関もscores_tableのような
- 評価するモノ (例 user_id)
- 評価されるモノ (例 movie_id)
- 評価数値 (例 score)
のカラムを持つテーブルがあればいいので、
同じようなテーブルがあれば、そのまま計算できるようなプログラムを書いてみました。main関数で上で作ったデータベースを計算しています。
#! /usr/bin/env python
#! vim: fileencoding=utf8
import os
import sqlite3
from math import sqrt
import logging as logger
PATH = os.path.dirname(os.path.abspath(__file__))
DATA_PATH = os.path.join(PATH, 'data')
DB_FILE = os.path.join(DATA_PATH, 'data.db')
def sim_distance(cur, table, col1, col2, score_col, a_value, b_value):
"""
a_valueとb_valueの距離を元にした類似性スコアを返す
"""
sql = """
SELECT a.%(score_col)s AS a_score, b.%(score_col)s AS b_score
FROM %(table)s a, %(table)s b
WHERE a.%(col1)s = %(a_value)s AND a.%(col2)s = b.%(col2)s
AND b.%(col1)s = %(b_value)s""" % locals()
logger.debug(sql)
cur.execute(sql)
sum_of_sequence = count = 0
for a_s, b_s in cur:
count += 1
sum_of_sequence += pow(a_s * 1.0 - b_s * 1.0, 2)
if count == 0:
return 0
return 1 / (1 + sum_of_sequence)
def sim_person(cur, table, col1, col2, score_col, a_value, b_value):
"""
a_valueとb_valueのピアソン相関係数を返す
"""
sql = """
SELECT a.%(score_col)s AS a_score, b.%(score_col)s AS b_score
FROM %(table)s a, %(table)s b
WHERE a.%(col1)s = %(a_value)s AND a.%(col2)s = b.%(col2)s
AND b.%(col1)s = %(b_value)s""" % locals()
logger.debug(sql)
cur.execute(sql)
sum1 = sum2 = sum1sq = sum2sq = psum = count = 0
for a_s, b_s in cur:
count += 1
sum1 += a_s * 1.0
sum2 += b_s * 1.0
sum1sq += pow(a_s * 1.0, 2)
sum2sq += pow(b_s * 1.0, 2)
psum += a_s * b_s * 1.0
if count == 0:
return 0
num = psum - (sum1 * sum2 / count)
den = sqrt((sum1sq-pow(sum1, 2)/count)*(sum2sq-pow(sum2, 2)/count))
if den == 0:
return 0
"""
logger.debug("num %s" % num)
logger.debug("den %s" % den)
logger.debug("sum1 %s" % sum1)
logger.debug("sum2 %s" % sum2)
logger.debug("sum1sq %s" % sum1sq)
logger.debug("sum2sq %s" % sum2sq)
logger.debug("psum %s" % psum)
"""
return num/den
def topMaches(cur, table, col1, col2, score_col, a_value, n=5, similarity=sim_person):
"""
a_valueとそれ以外との関係性を計算してもっとも似ているもののリストを返す
"""
# a_value 以外のcol1を抽出
sql = "SELECT DISTINCT %(col1)s FROM %(table)s WHERE %(col1)s != %(a_value)s" % locals()
cur.execute(sql)
other_list = [i[0] for i in cur.fetchall()]
scores = [(similarity(cur, table, col1, col2, score_col, a_value, b_value), b_value)
for b_value in other_list]
scores.sort()
scores.reverse()
return scores[:n]
def getRecommendations(cur, table, col1, col2, score_col, a_value, n=50, similarity=sim_person):
"""
a_valueになく、他のものにある中で必要と思われるものをリストで返す
"""
totals = {}
simSums = {}
sql = "SELECT DISTINCT %(col1)s FROM %(table)s WHERE %(col1)s != %(a_value)s" % locals()
logger.debug(sql)
cur.execute(sql)
for other in (i[0] for i in cur.fetchall()):
sim = similarity(cur, table, col1, col2, score_col, a_value, other)
logger.debug("sim %s" % sim)
if sim <= 0:
continue
#a_valueになくotherにあるcol2とscoreを抽出
#MySQL4系統では副問合せを使えないのでLEFT JOINを使用
sql = """
SELECT a.%(col2)s, a.%(score_col)s FROM %(table)s a
LEFT OUTER JOIN %(table)s b ON b.%(col1)s = %(a_value)s AND a.%(col2)s = b.%(col2)s
WHERE a.%(col1)s = %(other)s AND b.%(score_col)s IS NULL""" % locals()
logger.debug(sql)
cur.execute(sql)
for c2, score in cur:
#logger.debug("%s %s" % (c2, score))
totals.setdefault(c2, 0)
totals[c2] += score * sim
simSums.setdefault(c2, 0)
simSums[c2] += sim
rankings = [(total/simSums[c2], c2) for c2, total in totals.iteritems()]
rankings.sort()
rankings.reverse()
return rankings[:n]
def main():
con = sqlite3.connect(DB_FILE)
cur = con.cursor()
args = dict(
cur=cur,
table = "scores_table",
col1 = "user_id",
col2 = "movie_id",
score_col = "score",
a_value = 1,
b_value = 2)
print sim_distance(**args)
print sim_person(**args)
print topMaches(
cur=cur,
table = "scores_table",
col1 = "user_id",
col2 = "movie_id",
score_col = "score",
a_value = 7,
n = 3)
print getRecommendations(
cur=cur,
table = "scores_table",
col1 = "user_id",
col2 = "movie_id",
score_col = "score",
a_value = 7,
n = 3)
con.close()
if __name__ == "__main__":
main()
結果は、
0.148148148148
0.396059017191
[(0.99124070716192991, 1), (0.92447345164190486, 5), (0.89340514744156474, 4)]
[(3.3477895267131017, 6), (2.8325499182641614, 1), (2.5309807037655649, 3)]
他にも手持ちのMySQLのテーブルで試しましたが上手く計算できるようです。
ただ、この計算だけだと実用的な集合知とは思えないデータが出来るので、さらに読み進めていこうと思います。
perm link: /blog/entry/collective_2_1/
