ズッキーニのプログラミング実験場

プログラミング + アカデミック + 何か面白いこと。 記載されているものは基本的に私が所属する団体とは関係がありません。

   Mar 26

協調フィルタリング

by zuqqhi2 at 2015年3月26日
Pocket

協調フィルタリング とは

協調フィルタリング には様々なやり方があるが、
一般的には大人数の集団の中からレコメンド対象と好みが似た集団を見つけ出し、
その集団の行動リストの中から適切な行動を推薦するというものである。

嗜好データ

嗜好データを構造化するにはいろいろな方法があるが、
簡単にするには商品を購入したを1、していない0にしたり、
見た映画には1から5の評価を付けさせ、見ていない映画には0にしたりするなどがある。

ECサイト 映画
商品を購入した 1 映画を見た 1.0 – 5.0
商品を購入していない 0 映画を見ていない 0

人とその人の映画の評価(1.0-5.0の範囲)をpythonのディクショナリでハードコーディングしたものは
このようになる。

これを利用するには以下の様なコードを書けば良い。

#!/usr/bin/python

from database import critics

# Read evaluation
print critics['Lisa Rose']['Lady in the Water']

# Set value
critics['Toby']['Snakes on a Plane'] = 5.0
print critics['Toby']

嗜好の似ている集団を検索する

リコメンド対象とそれ以外の人がどれだけ似ているかを調べるためには類似性スコアを算出するとよい。
このスコアを算出するには様々な方法がある。
ここでは、以下の2つの方法を説明する。

  • ユークリッド距離
  • ピアソン相関

ユークリッド距離

お互いに同じ2つの映画(ターミネーターとスターウォーズ)を見て評価をしている場合、
以下のように2次元グラフ上にプロットしてその距離を計算する方法である。
この距離が短いほうが2人の好みが似ていると考える。
euclid
3つ以上ある場合はz,wなど変数を増やして同様の計算式を使用すればよい。

先ほどのデータを利用して任意の2人の評価者の好みを計算するプログラムは以下のようになる。

#!/usr/bin/python

from database import critics
from math import sqrt

#
# Calculate similarity between person1, person2
# using euclid distance
#
def sim_distance(prefs, person1, person2):
    # Get the list item evaluated by twosome
    items = [1 for item in prefs[person1] if item in prefs[person2]]

    # Nothing items
    if len(items) == 0: return 0

    # Calculate euclid distance
    distance = sum([pow(prefs[person1][item]-prefs[person2][item],2)
        for item in prefs[person1] if item in prefs[person2]])

    return 1.0/(1.0 + distance)

# main
if __name__ == '__main__':
    print sim_distance(critics, 'Lisa Rose', 'Gene Seymour')

ピアソン相関

ユークリッド距離はデータの大きさが整理されていないときにはうまく動作しない。
例えば、人同士の類似性スコアを計算しようとしてその人達の身長と年齢をデータとして比べようとすると、
身長のほうが年齢よりも値が大きくなるため身長の差が年齢の差よりも結果に大きな影響を与えてしまう。

ピアソン相関係数を用いるとその問題はなくなる。
ピアソン相関では2つのデータ群の関係性を見る。
片一方のデータ群が変化した時にもう一方のデータ群も同じように変化をするならば相関が高い、すなわち類似していると見るのである。

これを計算するには次のように考える。
データの変化をよく表す直線と平均の差データと平均の差割合を計算すると。
図で言うと、緑色の線がデータの変化を良く表す直線と平均の差で、
青色の線がデータと平均の差である。
ちなみに、各データは映画の評価、x,y軸が評価者になる。
piason
各データが青色の直線(データの変化をよく表す直線)上に乗っていれば、
両方の評価者の評価は近く、直線よりも遠ければ評価も遠いことが感覚的にわかるだろう。

各データが青色の直線上に乗っているとは、
2つの差の割合を計算することで計算できる。書くデータが直線上に完全に乗っていれば、
両方の差の値は同じになるはずであるから、1となる。
完全に離れてしまえば0となる。

2つの差の割合であるから以下の計算式で計算できる。
回帰直線の部分を計算して計算式に代入することで以下の計算式の右端の式が得られる。
回帰直線の導き方は話題が異なるので省略する。
correration

ソースコードは以下のようになる。

#!/usr/bin/python

from database import critics
from math import sqrt

#
# Calculate pearson correlation between p1 and p2
#
def sim_pearson(prefs,p1,p2):
    # Get item list
    items = {}
    for item in prefs[p1]:
        if item in prefs[p2]:
            items[item]=1
    n = len(items)

    # return 0 when items are nothing
    if n == 0: return 0

    # calculate p's variance
    ave1 = sum([prefs[p1][it] for it in items])/float(n)
    var1 = sqrt(sum([pow(prefs[p1][it]-ave1,2) for it in items]))

    ave2 = sum([prefs[p2][it] for it in items])/float(n)
    var2 = sqrt(sum([pow(prefs[p2][it]-ave1,2) for it in items]))

    # calculate covariance
    cov = sum([(prefs[p1][it]-ave1)*(prefs[p2][it]-ave2) for it in items])

    # calculate similarity
    if var1*var2 == 0: return 0
    return cov/(var1*var2)

if __name__ == '__main__':
    print sim_pearson(critics, 'Lisa Rose', 'Gene Seymour')

嗜好の似た評価者によるアイテムの推薦

最も似た嗜好を持つ評価者を特定し、
その人が高い評価を与えている映画を推薦するのが最も簡単な方法であるが、
その人がリコメンド対象が好きな映画を見ていないために精度の高い推薦ができない可能性がある。

それを解決するために嗜好の近さを重みとして、それを評価値に掛けた値を合計することで精度を高めることができる。
ソースコードにすると以下のようになる。

#!/usr/bin/python

from database import critics
from pearson import sim_pearson
from euclid import sim_distance

#
# Calculate weighed mean, and recommend
#
def getRecommendations(prefs,person,similarity=sim_pearson):
    totals = {}
    simSums = {}
    for other in prefs:
        if other == person: continue
        sim = similarity(prefs, person, other)

        # ignore similarity is less than 0
        if sim <= 0: continue

        for item in prefs[other]:
            if item not in prefs[person] or prefs[person][item] == 0:
                totals.setdefault(item,0)
                totals[item] += prefs[other][item] * sim
                # similarity
                simSums.setdefault(item,0)
                simSums[item] += sim

    # make normalized list
    rankings = [(total/simSums[item],item) for item,total in totals.items()]

    rankings.sort()
    rankings.reverse()
    return rankings


if __name__ == '__main__':
    print getRecommendations(critics, 'Toby')

最後の方でtotal/simSums[item]とあるが、
これはたくさんの評価者に見られている映画の評価値が高くなってしまうという問題を防ぐために正規化をしている。

似ているアイテムを出す

criticsのキーと値を入れ替えると、
どの映画が誰に評価されているかというデータになる。
この状態で今までやってきた関数を動かすと、アイテム同士の近さを見ることができる。
criticsを入れ替えてアイテム同士の近さを出力するプログラムを書いてみる。
すると以下のようになる。

#!/usr/bin/python

from database import critics
from pearson import sim_pearson
from euclid import sim_distance

#
# Transform key and value
#
def transformPrefs(prefs):
    result = {}
    for person in prefs:
        for item in prefs[person]:
            result.setdefault(item,{})
            result[item][person]=prefs[person][item]

    return result

#
# Make ranking
#
def topMatches(prefs,person,n=5,similarity=sim_pearson):
    scores=[(similarity(prefs,person,other),other) for other in prefs if other!=person]
    scores.sort()
    scores.reverse()
    return scores[0:n]

if __name__ == '__main__':
    movies = transformPrefs(critics)
    print topMatches(movies, 'Superman Returns')

アイテムベースフィルタリング

これまでのユーザベースの推薦とは異なり、
ここではアイテムベースのフィルタリングについて説明する。
アイテムベースのフィルタリングでは、
アイテム同士の類似度は人同士の類似度ほど頻繁に変化しないという性質を利用して、
計算の頻度を下げ精度を上げることができる。

アイテムベースフィルタリングを使用するには以下のような手順で計算すればよい。

  1. アイテム同士の類似度を値として持つデータセットを作成する(ユーザが増えて安定してきたら計算回数を減らすことができる)
  2. リコメンド対象が評価したアイテムリストを作成する
  3. 似ているアイテムを探し、類似度で重み付けする

これをプログラムで実現すると以下のようになる。

#!/usr/bin/python

from database import critics
from itemsim import transformPrefs,topMatches
from euclid import sim_distance

#
# calculate similarity between item and item
#
def calculateSimilarItems(prefs,n=10):
    result = {}

    itemPrefs = transformPrefs(prefs)
    c = 0
    for item in itemPrefs:
        c += 1
        if c % 100 == 0: print "%d / %d" % (c,len(itemPrefs))
        scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
        result[item]=scores
    return result

#
# Recommend on a item bases
#
def getRecommendedItems(prefs, itemMatch, user):
    userRatings = prefs[user]
    scores = {}
    totalSim = {}

    for (item,rating) in userRatings.items():
        for (similarity,item2) in itemMatch[item]:
            if item2 in userRatings: continue

            scores.setdefault(item2,0)
            scores[item2] += similarity*rating

            totalSim.setdefault(item2,0)
            totalSim[item2] += similarity

    rankings = [(score/totalSim[item],item) for item,score in scores.items()]
    rankings.sort()
    rankings.reverse()
    return rankings


if __name__ == '__main__':
    itemsim = calculateSimilarItems(critics)
    print getRecommendedItems(critics,itemsim,'Toby')

アイテムベースのフィルタリングは、一般的に、疎なデータセットに対して
ユーザベースフィルタリングより性能が優れていることが知られている。

リファレンス

この記事は以下の本を元に知人に解説するために説明の仕方を変えて記述したものである。
なお、1章と2章は公開されている。

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

Related Posts

  • mahout2015年6月17日 Mahout で 協調フィルタリング  Mahoutを使って協調フィルタリングをやってみる。 Mahoutを使うことで基本的に一切の予備知識無しで、機械学習技術を利用することができる。 本記事では、Mahoutのインストール方法から紹介するが、Hadoopはすでにインストール済みとする。 環境 […]
  • 2013年7月13日 [Haskell]画像処理 水平方向のエッジ やりたいこと 水平方向の微分で水平方向のエッジ画像を出力する。 プログラム プログラムはこんな感じ。 結果 入力画像 出力画像 Target Output horizontal edge image. Program […]
  • 2013年7月11日 [Haskell]反転画像の生成 やりたいこと 前回まででPGM形式の画像の出力、読み込みができるようになったから、 今度は画像処理をやってみる。 今回は一番簡単な、反転画像を作る。 プログラム だいたいこんな感じ。 […]
  • [OpenCV][Ruby]Webページのデザイン崩れ確認の自動化2016年12月12日 [OpenCV][Ruby]Webページのデザイン崩れ確認の自動化 はじめに この記事は、OpenCV Advent Calendar […]
  • 2013年6月8日 [Processing]カメラの利用方法 概要 Processing カメラ ProcessingでARプログラムを作成するためにカメラを利用するプログラムを作ってみる。 ソースコード 以下がそのソースコード。 Processingだとものすごく簡単にかけるから便利! […]
  • 2012年11月10日 [玄箱Pro][初期化]自分がハマったところのメモ Q:シリアルコンソールを接続しても何も表示されない。 A:多くの場合接触不良が原因であるため、玄箱proとシリアルコンソールの接続部分を左右とか上下に動かしてみる。 Q:シリアルコンソールで接続したけど文字化けして読めないし入力もできない。 A:ボーレ […]
Pocket

You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.