レコメンドエンジン『Cicindela』を試す：第4回

しばらく間が空いてしまいました。

前回までで、ログ収集→計算→レコメンドの動作は一通り再現したので、
今回はそこで利用したフィルタのロジックを見てみます。

まず、どんなフィルタリングロジックを適用するかは
/home/cicindela/lib/Cicindela/Config/_common.pm
で設定します。

現在はこのようになっています。

'pick' => {
        datasource =>  [ 'dbi:mysql:cicindela;host=127.0.0.1', 'root', '' ],
        filters => [
            [ 'PicksExtractor', { interval => '20 year', extract_heavy_user_set => 1 } ],
            'InverseUserFrequency',
            'ItemSimilarities',
        ],
        recommender => 'ItemSimilarities',
        refresh_interval => 1,
    },

赤字の所が今回関連する所です。
フィルタオプションは配列で先に定義されたモジュールから順に実行されるようです。
この設定の場合は

　PicksExtractor（計算サンプルとして利用するデータを取得）
　　↓
　InverseUserFrequency（計算に使うiuf値を定義）
　　↓
　ItemSimilarities（アイテムごとの関連度を計算する）

とモジュールが動作します。

またモジュールにオプションを指定する場合は

[ 'PicksExtractor', { interval => '20 year', extract_heavy_user_set => 1 } ]

このように配列内でハッシュで定義します。

これで設定方法はOK。
次に今回使った各フィルタ内部を見てみます。

まず最初にPicksExtractorは
収集したログデータから計算に利用するサンプルデータを取得します。
※ただしこのフィルタはログデータが選択したか/していないかの2択で取得している場合で利用します。

サンプル取得のロジックはいくつかパターンがあり、設定で変更ができます。

use_simple_set
　最新のログからサンプルを取得するロジック
use_heavy_user_set
　ヘビーユーザ（threshold_min～threshold_max）からのみサンプルを取得するロジック
extract_recent_set
　一定期間内（interval以降）のログで選択者数の多い中（threshold1以上）から
　サンプルを取得するロジック
extract_older_set
　一定期間外（interval以前）のログで選択者数の多い中（threshold2以上）から
　サンプルを取得するロジック

上記いずれかのロジックを使って計算に利用するサンプルを取得し、out_tableで指定したテーブルに保存します。
デフォルトではextract_recent_setとextract_older_setが複合で利用されます。

※PicksExtractorに関連したオプションは下記の通りです

in_table
　サンプルの抽出に利用するテーブル名の指定（デフォルト："picks"）
out_table
　抽出結果を保存するテーブル名の指定（デフォルト："extracted_picks"）
threshold_min
　use_heavy_user_setを利用した際、1ユーザあたりのログ数最小値（デフォルト：5）
threshold_max
　use_heavy_user_setを利用した際、1ユーザあたりのログ数最大値（デフォルト：50）
limit
　use_simple_setまたはuse_heavy_user_setでの、
　計算に利用するログのサンプル数上限（デフォルト：500000）
interval
　計算に利用するログの指定期限（デフォルト："3 month")
threshold1
　extract_recent_setでの、1アイテムあたりのログ数最小値（デフォルト：3）
threshold2
　extract_older_setでの、1アイテムあたりのログ数最小値（デフォルト：5）
limit1
　extract_recent_setでの、サンプル取得数上限（デフォルト：250000）
limit2
　extract_older_setでの、サンプル取得数上限（デフォルト：250000）

InverseUserFrequencyは生成したサンプルのテーブルから、
アイテム毎のユーザ数を集計し、inverse user frequency値を計算して保存します。
これはスコアリング時にユーザの多いデータにスコアが偏るのを補正するために使うようです。

iuf値計算のロジックを見てみると、

select a.item_id, log(b.total / a.cnt) / log([log_base]) from
  (select item_id, count(*) cnt from [in_table] group by item_id) a,
  (select count(distinct user_id) total from [in_table]) b

となっていて、

　log(ユーザIDの重複を排除したアイテム数 / アイテム毎のユーザ数 / log(log_baseで指定した係数))

というロジックで出た値がアイテム毎にiuf値として保存されます。

※InverseUserFrequencyに関連したオプションは下記の通りです

in_table
　計算に利用するサンプルを保存したテーブルの指定（デフォルト："extracted_picks'"）
out_table
　iuf値を保存するテーブルの指定（デフォルト："iuf"）
log_base
　iuf値の計算に利用する係数（デフォルト：2）

最後のItemSimilaritiesはレコメンドを計算し、レコメンドに用いるテーブルに登録するフィルタです。
※ただしこれもログデータが選択したか/していないかの2択の場合のみ利用します。

計算部分のロジックを見やすい形にしてみるとこんな感じになります。

# 取得したサンプルからitem_idを取得
my $sth = $self->sql("select distinct item_id from [in_table]");
$sth->execute or db_error;

# iufの利用設定（利用しない場合はコメントアウトにする）
my $_iuf_commentout = [use_iuf] ? '' : '--';

# アイテムIDごとにスコア計算
while (my ($item_id) = $sth->fetchrow_array) {
 $self->sql("
insert into [out_table] (item_id1, item_id2, score)
select $item_id, items.item_id,
    (log(items.count) / log([log_base]))
$_iuf_commentout  * coalesce(iuf.iuf, 1)
    score
  from
  (select r2.item_id item_id, count(*) count
    from [in_table] r1, [in_table] r2
    where r1.item_id = $item_id
      and r2.user_id = r1.user_id
      and r2.item_id != $item_id
    group by r2.item_id
    having count >= [threshold]
  ) items
$_iuf_commentout left outer join [in_table_iuf] iuf on items.item_id = iuf.item_id
  order by [order_by]
  limit [limit]
")->execute() or db_error;
}

SQLのコメントアウトを上手くiufのフラグとして利用しています。
ロジックの詳細をかいつまむと、

select r2.item_id item_id, count(*) count
    from [in_table] r1, [in_table] r2
    where r1.item_id = $item_id
      and r2.user_id = r1.user_id
      and r2.item_id != $item_id
    group by r2.item_id
    having count >= [threshold]

サンプルデータを保存したテーブルよりアイテムごとにユーザの関連数を計算し、
閾値以上のデータを抽出するようになっています。
そしてこの取得データを利用して計算しています。

select $item_id, items.item_id,
(log(items.count) / log([log_base]))
$_iuf_commentout * coalesce(iuf.iuf, 1)
   score
  from 【取得データ】 items
$_iuf_commentout left outer join [in_table_iuf] iuf on items.item_id = iuf.item_id
   order by [order_by]
    limit [limit]

赤字がスコアの計算式になります。
use_iuf=1の場合はアイテム毎にiuf値と外部結合してスコアに利用しているようです。
そしてその結果をorder_byで指定した条件によりソートして、limit件数分取得したのものをテーブルに保存します。
ただしここでのテーブルは計算中のバッファみたいなもので、計算終了後は後ろに"_online"がついたテーブルに移行されます。

※ItemSimilaritiesに関連したオプションは下記の通りです

in_table
　計算に利用するサンプルを保存したテーブルの指定（デフォルト："extracted_picks"）
out_table
　計算結果を保存するテーブルの指定（デフォルト："item_similarities"）
in_table_iuf
　iuf値を保存しているテーブルの指定（デフォルト："iuf"）
threshold
　サンプルから抽出する条件の閾値（デフォルト：3）
limit
　計算結果の取得最大数（デフォルト：30）
use_counts
　現在未使用？（デフォルト：1）
use_iuf
　iufの利用フラグ（デフォルト：1）
order_by
　計算結果のソート条件（デフォルト："items.count desc, score desc"）

ざっくりと今回のフィルタリングを紐解いて見るとこんな感じになります。