レコメンドエンジン(協調フィルタリング)をPHP+Redisで実装

PHPで使えるレコメンドエンジンはいくつか存在しますが、ドキュメント不足だったり、非推奨な関数が使われていたりで満足いくものではありませんでした。

ですので、自分で実装することにしました。

※2016/08/25追記 ライブラリ化しました！
https://github.com/YuzuruS/redis-recommend

packagistに登録もしてあるので、composerを使って簡単にインストールできます。

composer.json

{
    "require": {
       "yuzuru-s/redis-recommend": "1.0.*"
    }
}

協調フィルタリング型レコメンドとは？

今回実装する協調フィルタリング型レコメンドとは、Amazonにあるコレ↓です。

たとえば以下のデータがあったとします。

名前	本1	本2	本3
Aさん	1	1	1
Bさん	1	1	-

Aさんが本1、本2、本3を閲覧しました。
Bさんが本1、本2を閲覧しました。

AさんBさんともに本1,本2を閲覧しているので、Cさんが本1を閲覧した時に、本2をレコメンドする。という仕組みです。

上記は数が少ないので見た目で分かりますが、実際のサービスは商品の数が圧倒的に多いので、類似度を計算して高い順からレコメンドします。

Jaccard(ジャッカード)指数

類似度の計算ではJaccard(ジャッカード)指数を使うのが一般的なようです。

AとBそれぞれを集合とすると、Jaccard(ジャッカード)指数は以下のように定義できます。

Jaccard(A,B) = \frac{|A∩B|}{|A∪B|}

この計算式を使って下記のデータを計算すると

• 本1と本2を両方購入した人はEさん1名 (A∩B)
• 本1もしくは本2を購入した人はA,B,C,D,Eの5名 (A∪B)

以上より本1と本2の類似度は0.2になります。

名前	Aさん	Bさん	Cさん	Dさん	Eさん	Fさん	Gさん
本1	1	-	1	-	1	-	-
本2	-	1	-	1	1	-	-

PHP+Redisによる実装

Redisには取り出しやすい便利な型SortedSetがあるのでそれを類似度の保存に使います。

商品閲覧を記録

addViewer.php

/**
 * $item_id => 商品ID
 * $user_id => ユーザーID
 */ 
$Redis->lRem('Viewer:Item:' . $item_id, $user_id);
$Redis->lPush('Viewer:Item:' . $item_id, $user_id);
$Redis->lTrim('Viewer:Item:' . $item_id, 0, 999); // 1000個以降削除 記録する商品や顧客数が増えると計算量が爆発して死ぬので。

Jaccard(ジャッカード)指数を計算

calc.php

/**
 * $item_ids => 商品IDの配列 [1,2,3,4,5]のような配列
 */

foreach ($item_ids as $item_id1) {
	$base = $Redis->lRange('Viewer:Item:' . $item_id1, 0, 999);
	if (count($base) === 0) {
		continue;
	}
	foreach ($item_ids as $item_id2) {
		if ($item_id1 === $item_id2) {
			continue;
		}
		$target = $Redis->lRange('Viewer:Item:' . $item_id2, 0, 999);
		if (count($target) === 0) {
			continue;
		}

		# ジャッカード指数を計算
		$join = floatval(count(array_unique(array_merge($base, $target))));
		$intersect = floatval(count(array_intersect($base, $target)));
		if ($intersect == 0 || $join == 0) {
			continue;
		}
		$jaccard = $intersect / $join;

		$Redis->zAdd('Jaccard:Item:' . $item_id1, $jaccard, $item_id2);
	}
}

レコメンド商品idの取得

getRecommend.php

$Redis->zRevRange('Jaccard:Item:' . $item_id, 0, -1);

参考記事