集合知プログラミング 2章1

  • January 18, 2010 23:06

買って積み本になっていた集合知プログラミングを少しやってみたのでメモです。

集合知プログラミング
Toby Segaran
オライリージャパン
売り上げランキング: 15874

サンプルコードは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文が発行されます。

http://static.flickr.com/4027/4284307397_0d8a367c05.jpg http://static.flickr.com/4014/4285050820_6952b4d93d.jpg http://static.flickr.com/4036/4284307333_1aa87a073d.jpg

実行結果は以下の通りになります。

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)

のカラムを持つテーブルがあればいいので、

http://static.flickr.com/4036/4284307333_1aa87a073d.jpg

同じようなテーブルがあれば、そのまま計算できるようなプログラムを書いてみました。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のテーブルで試しましたが上手く計算できるようです。

ただ、この計算だけだと実用的な集合知とは思えないデータが出来るので、さらに読み進めていこうと思います。