推薦システムが、BDレコーダーを買ったら直後に、別のBDレコーダーを薦めてくる問題、を考える

皆さんは、オンラインで、1つあれば十分な類の商品（例えば、BDレコーダー）を購入した直後に、そのサイトから、同じような、別のモデルの商品を、繰り返し薦められて、うんざりした経験はありませんか？
いわゆる、BDレコーダーを買ったら直後に、別のBDレコーダーを薦めてくる問題（通称：BDレコーダー問題）です。（ウソです。そんな言葉ありません。。。）

先日、推薦システムや協調フィルタリングの話をしている時に、この議題が出て、「類似の商品を薦めるのではなく、併売の可能性が高い商品を薦めるには、どうすればいいんだろう？」としばらく考えていましたが、少しして、自分がアホなことで悩んでいたことに気がつきました。

結論から言うと、単純に過去の併売の履歴を集計して、数量が大きいもの（＝併売の可能性が高いもの）から推薦すればいいわけです。
分かりやすくするために、実際のデータセットを使ってお話ししましょう。
今回使用するデータセットは、下記URlの groceries.csv です。これは、ある食料・雑貨店での、購入履歴をまとめたもので、Rの機械学習用のサンプルデータセットです。（ちなみに、私はPython派です。）
https://github.com/stedy/Machine-Learning-with-R-datasets/blob/master/groceries.csv

csvの中身は、下記のような感じです。

1	citrus fruit,semi-finished bread,margarine,ready soups
2	tropical fruit,yogurt,coffee
3	whole milk
4	pip fruit,yogurt,cream cheese ,meat spreads
5	other vegetables,whole milk,condensed milk,long life bakery product
6	whole milk,butter,yogurt,rice,abrasive cleaner
7	rolls/buns
8	other vegetables,UHT-milk,rolls/buns,bottled beer,liquor (appetizer)
9	pot plants
10	whole milk,cereals
11	tropical fruit,other vegetables,white bread,bottled water,chocolate
12	citrus fruit,tropical fruit,whole milk,butter,curd,yogurt,flour,bottled water,dishes

１行目は、citrus fruit,semi-finished bread,margarine,ready soups の4商品が一緒に購入されたことを表しており、２行目では、tropical fruit,yogurt,coffee 3商品が一緒に購入されたことを表わしているといった感じです。

このデータのすべての各アイテムに対し、一緒に購入された（併売された）商品を集計します。

まずは、上記のcsvを読み込んで、ユニークなアイテム数を求めます。
（csv のすべての行をまとめたリストにして、set()を実施すれば簡単に、求まります。 https://note.nkmk.me/python-list-unique-duplicate/
注：後々の処理のために、商品名の中に含まれるスペースを他の文字に変換しておきましょう。）
このcsvには、171種類の商品があることが分かります。

次に、171種類の商品に対し、併売された数量を求めます。
具体的に説明します。

分かりやすくするために、csvが下記のようだったと仮定します。

1	citrus fruit,yogurt,margarine,ready soups,cream cheese
2	citrus fruit,yogurt,coffee, whole milk
3	whole milk,coffee,cream cheese

① １行目のcitrus fruitの、１行目内の併売数量を求めると下記のようになります。

|yogurt|ready soups|cream cheese|whole milk|
|---|---|---|---|---|
|1|1|1|1|

② 2行目のcitrus fruitの、１行目内の併売数量を求めると下記のようになります。

yogurt	margarine	whole milk	coffee
1	1	1	1

③ 上記の①と②を足し合わせると下記のようになります。

yogurt	ready soups	cream cheese	whole milk	margarine	coffee
2	1	1	2	1	1

これを、すべての行とすべてのアイテムに対し、繰り返し実施します。
すると、縦横それぞれがユニークアイテム数である171のマトリックスが出来上がります。

あれ、これ何か見覚えがありますよね？
そうです、これは、協調フィルタリングでやることとかなり似たことをやっています。
ただし、この後の処理は、協調フィルタリングより、はるかに単純です。

出来上がったマトリックスは、併売された各アイテムの合計数量を表しています。

citrus fruitであれば、下記の通りです。

併売されたアイテム名	合計数量
canned_fruit	11
prosecco	3
frozen_fish	16
sweet_spreads	10
canned_vegetables	21
...	...
cooking_chocolate	4
long_life_bakery_product	41
dish_cleaner	16
snack_products	3
ham	28

これを降順でソートしてあげれば、下記のように併売可能性の高いアイテムのリストが出来上がります。

併売されたアイテム名	合計数量
whole_milk	300
other_vegetables	284
yogurt	213
tropical_fruit	196
root_vegetables	174
...	...
bags	0
toilet_cleaner	0
citrus_fruit	0
whisky	0
make_up_remover	0

そうなんです。
簡単なんです。
ただの集計なんです。
機械学習なんて、いらないんです。

考えてみれば、当たり前の話で、類似したアイテムを求めるというのは、何をもって類似しているとするのかや、コールドスタート問題、様々なデータを使っての対象アイテムの特徴ベクトル化といったややこしい問題がいろいろあります。だからこそ、協調フィルタリングは画期的だったわけです。

ただ、ここで終わっては面白くないので、もう少し続けます。

これを、wikipediaのクリック・ストリーム・データセットにも適用してみます。
データセットは、下記URLにても公開されています。
https://meta.wikimedia.org/wiki/Research:Wikipedia_clickstream
https://dumps.wikimedia.org/other/clickstream/

このデータセットは、wikipwdiaの各ページ（記事）へのアクセスがあった際に、そのアクセスがどこからやってきたものかを集計したもので、アクセス元ページとアクセス先ページという1対1の関係に対し（その経路での）アクセス数が記載してあります。
これを、余計なものを排除し、wikipwdiaの各ページから、次にどのwikipwdiaのページに行くのかを表したものと捉えて、次に行くページの予測に使います。（wikipwdiaへのアクセスの大部分が検索エンジンなどの外部サイトからの流入出であることを考えると、実際には、結果の信憑性には、だいぶ疑問が残りますが。。。）

データセットのサイズが大きすぎるので、今回は、2019年1月のデータのみを使います。
（総レコード数は、2,113,911行で、Nanを削除して、2,113,885行です。）

データセットを読み込んで、外部サイトからのアクセスを削除すると、下記のような感じになります。
（外部サイトからのアクセスを削除すると、145,967行になります。ほとんどが外部からのアクセスでした。。。）

アクセス元	対象ページ	アクセスタイプ	数量
CMLL	CMLL世界ライトヘビー級王座	link	119
Fate/EXTRA	ジャバウォック	link	18
SAYURI	第78回アカデミー賞	link	18
CH	標数	link	11
DIVE!!	財木琢磨	link	15
Rising_Reysol	CAN_DO_レイソル	link	16
Amazon.com	シニア・バイス・プレジデント	link	92
3D	ニンテンドー3DS	link	10
Wii	ニンテンドー3DS	link	10

（アクセスタイプのlinkは、wikipedia内での、ページ遷移を表しています。）

先ほどと同じように、対象ページのユニークな（重複を排除した）アイテムリストを作成します。
今回のデータセットでは、90,355個になります。
つまり、求めるマトリックスは、90,355*90,355になります。
（普通にやると、一瞬でメモリが吹っ飛ぶので、scipy.sparseを使うようにして下さい。）

さて、では内容を見てみましょう。
（2019年1月だけのデータなので、（内部からの）アクセスがないページも多数あります。そのため、アクセスがあるページのみを取り上げています。）

対象サイト	Amazon.com
トップ1	ジェフ・ベゾス
トップ2	Amazon.co.jp
トップ3	ECサイト
トップ4	日本
トップ5	GAFA

対象サイト	Amazon.co.jp
トップ1	Amazon.com
トップ2	ジャスパー・チャン
トップ3	長谷川純一
トップ4	ECサイト
トップ5	合同会社
（＊勉強不足の私には、「んっ、変な名前が紛れ込んでるが、コード間違えたか？」と思いましたが、正しい内容でした。。。）

対象サイト	Nintendo_Switch
トップ1	Nintendo_Switchのゲームタイトル一覧
トップ2	ゲーム機
トップ3	Wii_U
トップ4	ニンテンドー3D
トップ5	大乱闘スマッシュブラザーズ_SPECIAL

対象サイト	GODZILLA
トップ1	GODZILLA_ゴジラ
トップ2	ゴジラ_ザ・シリーズ
トップ3	ローランド・エメリッヒ
トップ4	ゴジラ
トップ5	マシュー・ブロデリック

対象サイト	Microsoft_PowerPoint
トップ1	プレゼンテーションソフトウェア
トップ2	Microsoft_Office
トップ3	IOS_(アップル)
トップ4	MacOS
トップ5	マイクロソフト

対象サイト	Intel_Core_2
トップ1	Intel_Core_i7
トップ2	LGA775
トップ3	Nehalemマイクロアーキテクチャ
トップ4	Pentium_Dual-Core
トップ5	Intel_Celeron

どれも、「でしょうね」というような内容です。。。

今回は、もう少し遊んでみます。
元のデータセットでは、アクセス元のページとアクセス先ページという１対１のデータですが、これを連続してページ遷移が行われたと仮定して、はじめのアクセス元ページから、数回のページ遷移（wikipedia内）で、どこに辿り着く可能性が高いのか（もしくは、どこからやってきたか）を求めてみます。

（補足）
手順1. 対象アイテムをアクセス元ページとして、アクセス先ページをリストアップし、アクセス数を加算する。
（列名が対象アイテムで、行名がアクセス先ページの各セルに、アクセス数を加算する。）
手順2. 上記手順1のアクセス先ページすべてをアクセス元ページとして、手順1と同じ作業を実施する。
（ただし、加算するセルの列名は、手順1のアクセス先ページ（＝手順2のアクセス元ページ）ではなく、手順1のアクセス元ページ（対象アイテム）とする。）
手順3. 手順2を任意の回数繰り返す。
（※列名と行名や、アクセス元ページとアクセス先ページはやりたい内容によって入れ替えます。）

今回の検証では、アクセス数の加算は、手順1、手順2、手順3のどこでも同じように行なっていますが、手順1ではアクセス数1、手順2ではアクセス数0.5、手順3ではアクセス数*0.25のように係数を付加してもいいかと思います。

では、検証です。

まずは、1回で試してみます。（上記の内容と同じです。）

では、2回です。
上位には、順当なアイテムが並んでいます。

リストの最後でも、まだ、関連の高いものばかりです。

では、3回を試してみましょう。
上位は、ほとんど変化なしです。

ただ500位あたりから、変わったものが混じり始めます。

次は、4回を試してみましょう。
上位は、ほとんど同じです。

さきほどの500位過ぎも、今回は順当な内容が並んでいます。

1200位過ぎの最後の方でも、なんとなく関連の高いものが多いですね。

総論

購買履歴やクリックストリームは、対象アイテム（ページ）の前後の履歴を集計することで、類似性が高いものに限らず、関連の高いものを探し出すことができる。ただし（協調フィルタリングだけのときほどではなくても）、「BDレコーダーを買った直後の別のBDレコーダー」のようなものも含まれるので、協調フィルタリングやコンテンツベース推薦などと併用しながら、特手のカテゴリーのアイテム（電化製品など）については、類似性が高すぎるものは推薦から外すや、同じ製品カテゴリーのものは推薦から外すなどの個別の対策が必要だろうと思います。

最後まで、お読み頂き、有り難うございました。