Time Weight Collaborative Filtering - ut_ymgc @ サーベイ

ABSTRACT

協調フィルタリング(CF)は主要な推薦アルゴリズムであるが、時間を考慮できていない。すなわち、ユーザがアイテムに対していつ評価を行ったかを考慮していない。ユーザの興味は時間を追って変化していくと考えられるため、時間軸を考慮しないのはおかしい。本稿では、古い評価には小さな重みを与えることで時間軸を考慮した協調フィルタリングを提案する。提案する手法は、クラスタリングを用いて異なるアイテムを区別する。それぞれのクラスタに対してユーザの興味を追っていき、その評価行動に基づいてdecay factorを取り入れる。実施した実験によると計算のオーダを上げることなく精度の向上を実現した。

INTRODUCTION

• CFはユーザベースとアイテムベースがあるが、アイテムベースの方がスケーラビリティや精度が優れている
• ユーザの興味は時間を追って変化するため、新しい評価の重みを大きくするべき。
• 時間を考慮する簡単なやり方としてウィンドウサイズを設けるものがある
  • しかし、新しいデータのみを用いるこの手法ではデータが疎であるという問題をより強くしてしまう。
• 本稿では、それぞれのアイテムに対して適切な時間重みを与える
  • あるユーザはすぐに興味が変わってしまうが、別のユーザはゆっくりと変わっていく
  • 同一のユーザであっても異なるアイテムに対しては違った時間的変化を見せる
  • 提案手法では、ユーザは類似するアイテムに対しては類似する時間的変化を見せると仮定する
  • アイテムをクラスタリングし、それぞれのクラスタに対してのユーザの評価行動を分析し、それぞれのユーザに特化したdecay factorを与える。

RELATED WORK

• コンセプトドリフトに関する研究がいくつかあるけど、本手法はそれに似ている。
  • ユーザの興味はコンセプトドリフトみたいに変わっていくから、古いデータをそのまま使っていてはいけない

TIME WEIGHT ALGORITHMS

• 本手法の主なアイデア
  • それぞれのアイテムに対して適切な時間的重みを与える
  • より新しい評価データにはより大きな重みを与える

Item-based Collaborative Filtering Algorithms

• アイテムベースの協調フィルタリングは二つのフェーズに分かれる

1. 1. 類似度計算: 類似度を計算する主要な方法が三つある
      1. コサイン類似度
      2. ピアソン相関係数
      3. 条件付き確率に基づく類似度: 条件付き確率に基づくアイテムiとjの類似度は、アイテムiを買ったユーザのうち何人がアイテムjを買うかという確率
   2. 嗜好の推定: あるアイテムに対するユーザの評価の予測は、ユーザが既に評価したアイテム集合に対する評価値を、予測するアイテムとの類似度で平均したもの。

Time Function

• 関数f(t)を定義
  • 嗜好の推定の式の各評価値にf(t)をかける（式5）
  • f(t)の形として指数関数を採用する
    • ユーザの最近の評価を重視するという観点から、指数関数はシグモイド関数よりこの問題に適している
• パラメータとしてT0を考える
  • T0日経過すると関数f(t)の値が半減する
  • 興味が頻繁に変わるユーザに対してはT0を小さく設定
  • 興味があまり変わらないユーザに対してはT0を大きく設定

Learning Parameters

• ユーザの嗜好を精度よく予測できるパラメータT0を推定する
• しかし、ユーザの嗜好は多岐にわたる
  • 同一のユーザでさえも異なるタイプのアイテムに対しては異なる行動をする
  • あるタイプのアイテムに対する興味は頻繁に変わるが、別のタイプのアイテムに対する興味はあまり変わらないなど
• 全てのユーザと全てのアイテムに対してそれぞれパラメータを割り振るのは良くない
  • 類似するユーザは類似するアイテムに対して類似する嗜好を示す
  • 同一のユーザは類似するアイテムに対して類似する時間的変化を見せる
• 本手法では、それぞれのユーザ、それぞれのアイテムクラスタに対してT0を割り当てる
  • Kmeansを用いてユーザの嗜好データを基にアイテムをクラスタリングする
  • それぞれのアイテムクラスタに対してleave-one-out法を用いてT0を推定する
    • あるアイテムクラスタにおいて、一つをテスト用に抜き出し、抜き出したアイテムに対するユーザの評価を推定し、実際の評価との差を取る。これを全てのアイテムについて行い、MAEを取る。MAEが最小となるようなT0を学習する。

Building the Model

• アルゴリズム参照（読めば分かる）

EXPERIMENTS

• 二つ実験する
  • T0が手法の精度にどれくらい寄与するか
  • 既存のCF（アイテムベース）と提案手法との比較
    • どちらもピアソン相関係数を用いる

Experiment Design

• EachMovieとGroupLensのデータセットを用いる
• 学習サイズをユーザ数30, 60, 200と変化させる
• All but one
  • それぞれのユーザの一番新しく評価したアイテムのみをテストに用いる
• Given k
  • それぞれのユーザからk個の評価を用いて学習し、残りをテストに用いる
• 近傍は３０に設定

Experiment(1): impact of parameter T0

• T0を10, 20, 50, 100, 200と変化させる
  • （ユーザごと、アイテムクラスタごとにT0を設定するんじゃなかった？）
  • 異なるユーザに同じT0を与えるのは好ましくない、提案手法では異なるT0を与える
    • （なぜかこれに関する実験結果はない）
• 結果によるとT0は精度に大きく影響を与える（そうは見えない）

Experiment(2): comparison to the classic item-based algorithm

• どちらのデータセットに対しても、どの大きさの学習サイズに対しても、どのテスト手法（all but one, given k)に対しても提案手法の方が精度良かった。

Complexity Analysis

• アイテム間の類似度計算（オフライン処理）にはかなりの計算量がかかる
  • 提案手法も同じで、かなりの計算量がかかっている
• それに加えて提案手法はT0を計算する分だけより計算量がかかる
  • しかし、T0を計算する部分は類似度計算よりも計算量が少ないため、無視できることがある
• 評価の予測（オンライン処理）の計算量は提案手法も従来手法も同じ

CONCLUSION AND FUTURE WORK

時間の重みを付けた協調フィルタリングを提案。最近の評価は昔の評価よりもユーザの嗜好をより反映している。あるユーザがあるアイテムクラスタに対してどのように興味が変わっていくかを学習する（T0をそれぞれのユーザ、それぞれのアイテムクラスタに対して割り当てる)。実験結果によると提案手法は従来手法を上回る精度を実現した。
今後はストリームデータに対するＣＦを検討する