こんにちは、株式会社Gunosyの福島です。今回は協調フィルタリングという推薦手法について解説したいと思います。

協調フィルタリングとは

協調フィルタリングとは、口コミによる興味喚起を自動化したものといわれています。おそらく最も有名であるAmazonの「この商品を買った人はこんなものも買っています」という推薦システムもこの協調フィルタリングの応用で、アイテムベース協調フィルタリングという技術を利用しています。

協調フィルタリングはユーザのコミュニティや過去の振る舞いを利用して、ユーザの好みや興味を持つ情報を予測します。具体的には、過去の各々のユーザの購入情報やクリック情報などを利用します。

ユーザベース協調フィルタリング

もっと具体的に見てみましょう。協調フィルタリングの最も直感的な説明は、ユーザコミュニティの中で自分と購入履歴が似ているユーザを探し出し、その似ているユーザが購入しており、かつ推薦対象ユーザがまだ購入していない商品は興味を持たれたり購入されたりする可能性が高いというものです。これをユーザベース協調フィルタリングと呼びます。

では実際にこれをどう実現しているのでしょうか。今回は簡単な説明のため、ユーザの過去の購入情報のみを推薦に利用するとします（図1⁠）⁠。

このような購入履歴のデータを持っており、ユーザAに商品の推薦をしたいと考えます。このとき数式的に扱いやすくするために行列で表したのが、図2です。

購入した履歴を1、購入しなかった履歴を0としています。各行はユーザの特徴を表し、各列はアイテムの特徴を表しています。この行列はユーザ-アイテム行列と呼ばれ、協調フィルタリングではたびたび登場します。ユーザベース協調フィルタリングではこの行列を利用しユーザ間の類似度(=過去の購入行動がどれくらい似ているか)を計算し、それにもとづき提示する商品に対して優先度をつけます。ユーザAに推薦するタスクを考えます。ユーザAの場合まだ購入していない商品は2と4です。ここでの推薦タスクは「ユーザAに商品2か4どちらを提示すべきか(または提示しないか)」を確定することになります。

ユーザ間の類似度を求めるには、一般的にピアソン相関係数やコサイン類似度が用いられます。またユーザベースの協調フィルタリングには一般的にピアソン相関係数が用いられます。しかし今回は0/1のみの値ですので、jaccard係数を利用してみることにします（図3⁠）⁠。

◆相関に関連することと思いますが、Jaccard係数とは、だいたいこういうものです。という追記があれば欲しいです◆

jaccard係数を使ってユーザの類似度を求めた結果が図4です。

この jaccard相関係数は、ユーザAとユーザB、C、Dの類似度を表します。値が大きいほど類似しています。図4では、ユーザCがこの中では、一番類似していることをしめしています。

それでは購入していない商品2と4を推薦するかどうかはどう決定するのでしょうか。商品2のスコアはユーザAの平均評価値に各ユーザの類似度を考慮した重みつきの評価を加えることで計算します。簡易ではありますが今回は次のように実装してみました。

#! /usr/local/bin/python
# -*- coding:utf-8 -*-

import sys


def jaccard(v1, v2):
    """
    jacard係数を求める
    """
    v1_and_v2 = 0.
    v1_or_v2 = 0.
    for i in xrange(len(v1)):
        if v1[i] == 1 or v2[i] == 1:
            v1_or_v2 += 1
            if v1[i] == 1 and v2[i] == 1:
                v1_and_v2 += 1
    try:
        return v1_and_v2 / v1_or_v2
    except ZeroDivisionError:
        return 0.0


def calc_users_similarity(user_id, user_data, sim=jaccard):
    """
    userとuserの類似度を求める
    """
    users_similarity = {}
    for target_id in xrange(len(user_data)):
        if target_id == user_id:
            continue
        users_similarity[target_id] = sim(
            user_data[user_id], user_data[target_id])
    return users_similarity


def calc_user_average_score(user_id, user_data):
    """
    ユーザーの平均スコア
    """
    return sum(user_data[user_id]) / len(user_data[user_id])


def userbase_scoring(user_id, item_id, user_data, users_similarity):
    """
    userとitemのスコアを求める
    """
    if user_data[user_id][item_id] == 1.:
        return -1. * sys.maxint
    ave_score = calc_user_average_score(user_id, user_data)
    bunshi = 0.
    bunbo = 0.
    for target_id in xrange(len(user_data)):
        if target_id == user_id:
            continue
        bunshi += users_similarity[target_id] * (
            user_data[target_id][item_id]
            - calc_user_average_score(target_id, user_data)
        )
        bunbo += users_similarity[target_id]

    return ave_score + (bunshi/bunbo)


if __name__ == "__main__":
    user_data = [[1., 0., 1., 0.],
                 [1., 0., 0., 1.],
                 [1., 1., 1., 0.],
                 [0., 1., 0., 0.]]
    user_id = int(sys.argv[1])
    users_similarity = calc_users_similarity(user_id, user_data, sim=jaccard)
    for item_id in xrange(len(user_data[0])):
        print "item{}:".format(item_id),
        print userbase_scoring(user_id, item_id, user_data, users_similarity)

結果は図5のようになりました。(実装上ではすでに購入した商品はスコアを-sys,maxintにしています)

この結果から、ユーザAには商品2を推薦すべきという結果になりました。

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

次にアイテムベース協調フィルタリングを考えてみましょう。ユーザベースではユーザ間の類似度を計算しましたが、アイテムベース協調フィルタリングではアイテム間の類似度を計算します。先ほどの行列を縦にみると、一列一列がアイテムの特徴量を表すベクトルになります。このベクトル同士の類似度を計算することでアイテム間の類似度を計算します。類似度の計算には一般的にコサイン類似度がよいとされ用いられます。

特徴量の選択

前述の例では購入か購入していないかの2値を利用し、推薦システムを構築しました。しかし実際にはサービス上での行動はさまざまであり、それらをうまく用いることでうまくモデルを記述し、推薦精度を上げることができます。モデルに対してどのような特徴を利用するかを特徴選択といい、非常に重要な作業となります。

ユーザの行動は購入履歴以外にも、クリックしたかどうか、カートに入れたかどうか、Likeしたかどうか、アイテムに対するratingなどがあるでしょう。古典的な協調フィルタリングではこのratingがよく使われたりします。

また、アイテムの内容(商品のタイトル、商品説明の文書、出演している俳優やカテゴリなどのメタデータ)を用いることで精度が改善されたという事例が多くあります。

どのような特徴を選択するかはそのモデルの精度を決める重要な要素になります。そのため推薦システムで何を実現したいのか、それはサービス上の行動で考えたときどのような行動に現れるのかなどのドメイン知識は非常に重要です。一方で近年ではこの特徴選択も自動的に学習させるdeep learningといった手法が注目を集めています。実際にGoogleの画像検索のメインエンジンはこのdeep learningを利用しているようです。deep learningは直接的に協調フィルタリングに関連するわけではありませんが、この分野は今後大きく研究が進む可能性があるので注視していく必要があるでしょう。

協調フィルタリングの課題

さて、次は協調フィルタリングの課題をみてみましょう。協調フィルタリングの代表的な課題としてこれらのものがあります。

• データのスパース性
• コールドスタート問題
• スケーリング
• 同一性
• Shilling Attack
• ノイズ処理
• プライバシー保護

とくにデータのスパース性やコールドスタート問題、スケーリングの問題などは協調フィルタリングの大きな課題としられており、その解決に多くの研究がなされてきました。スパース性とは行列のスパース性のことです。通常のサイトではユーザ数に対してはるかに巨大な商品数があります。通常ユーザはその中で非常に少数なアイテムしか購入しません。そのためユーザアイテム行列が非常に疎(スパース)なものとなります。協調フィルタリングシステムではユーザ同士がアイテム購入のかぶりなどを利用しユーザ間(もしくはアイテム間)の類似度を計算します。このため行列がスパースかつ巨大になると推薦精度がおちてしまったり、計算量が増加し推薦速度が落ちたりします。

また近年、協調フィルタリングの商用化がすすむことによって重要性が増し、いわゆるハッキング的な攻撃にさらされることになりました。協調フィルタリングのアルゴリズムの特性をつくプロファイル・インジェクションという攻撃や、購入情報などを抜こうとする攻撃などがあります。プロファイル・インジェクションに対しては、アルゴリズムの堅牢性を高めたり、もしくは異常なプロファイルを探知するスパムフィルタリングなどで対処します。購入情報のハッキングなどに対しては、そもそも情報が流出してもデータの難読化をはかり、利用できないようにすれば良いという考え方があります。こういった手法を研究するプライバシー保護データマイニングという分野も存在します。シンプルな手法としてユーザの評価値にランダムノイズ(たとえばガウスノイズ)を加えて中央のサーバに保持するといった方法があります。個々の評価値は難読化されていますが、全体で見ると正しい推薦結果が出せるといった方法です。

コールドスタート問題

ところで、コールドスタート問題とは何でしょう。なかなかイメージしにくいと思うので詳しく説明します。先ほどの商品群に新たに新製品の商品5が追加されたとします（図6⁠）⁠。

商品5は新製品なので、当然誰も購入していません。ですので協調フィルタリングでは商品5は推薦できません。このように新製品や新規ユーザなどまだ行動履歴が十分にない対象に対して推薦を行うことが難しい(もしくはできない)ことをコールドスタート問題といいます。

コールドスタート問題への対策もいろいろ研究されています。たとえば前回で紹介した内容ベースフィルタリングと組み合わせハイブリッドなモデルによって解決するといった方法もその1つです。Gunosyではコールドスタート問題に対して、TwitterやFacebookの行動履歴を用いる、登録時にアンケートに答えてもらうといったことで対策しています。

今後、推薦エンジンの応用が広まるにしたがい、コールドスタートをいかに乗り越えるかは非常に重要な過大になると筆者は考えています。

メモリベースとモデルベース

協調フィルタリングにはユーザの行動データをすべてメモリに乗せて扱うメモリベースと、データをオフライン処理した後に推薦を行うモデルベースのアプローチがあります。メモリベースでの推薦は容易に構築でき、また非常に効果も高いですが、前述に挙げたような課題があります。そういった課題を解決するためにモデルベースの手法が利用されます。たとえば、データの次元を削減することや機械学習的な手法であらかじめ学習させておくといったアプローチがあります。たとえばSVD（特異値分解）で次元削減を行うことで行列の疎性やスケーリング、ノイズ除去といったことができます。またuserをクラスタリングし、ユーザクラスタとアイテムの行列を用いるclustering Collaborate Filteringといったものもあります。クラスタリングはいわゆる教師なし学習と呼ばれる機械学習の手法です。近年ではnetfrix prizeで注目を集めたmatrix factorizationを利用するモデルが流行っているようです。また内容ベースフィルタリングやルールベースのモデルと組み合わせるハイブリッドなモデルも効果をあげています。ハイブリッドモデルに関しては次回で詳しく解説します。

モデルベースの推薦では、モデルを構築するのに大量の計算資源を必要としますが、いったんモデルを構築し終えると、メモリベースよりも高速に、また特定の状況（データがスパースなときなど）ではメモリベースよりも高い精度を誇ります。

次回は、推薦システムを構築するのに必要なデータの獲得について解説します。