推薦システムが、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回で試してみます。（上記の内容と同じです。）
![スクリーンショット 2020-03-23 8.58.15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/600629/38ae7d67-5671-0344-2a46-acb8009c9924.png)

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

![スクリーンショット 2020-03-23 9.01.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/600629/9cde0dbe-bf9f-5e62-f7ad-60b0b9627fba.png)

リストの最後でも、まだ、関連の高いものばかりです。
![スクリーンショット 2020-03-23 9.04.17.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/600629/9bb01617-f7cf-3952-4e03-fe8246e77f21.png)


では、3回を試してみましょう。
上位は、ほとんど変化なしです。
![スクリーンショット 2020-03-23 9.07.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/600629/27fce870-3a86-0765-f240-2d988302ac7d.png)

ただ500位あたりから、変わったものが混じり始めます。
![スクリーンショット 2020-03-23 9.58.01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/600629/db37b857-9375-04d2-192f-9e47871d1b1f.png)


次は、4回を試してみましょう。
上位は、ほとんど同じです。
![スクリーンショット 2020-03-23 9.12.29.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/600629/a1bba6ec-32e4-3d67-8091-44a4f4f10529.png)

さきほどの500位過ぎも、今回は順当な内容が並んでいます。
![スクリーンショット 2020-03-23 9.14.04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/600629/f7f5522b-6867-39cb-b814-d3e630248a8d.png)


1200位過ぎの最後の方でも、なんとなく関連の高いものが多いですね。
![スクリーンショット 2020-03-23 9.15.44.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/600629/47175ff6-ccb8-7ed7-aaf6-c78c482eb1c5.png)


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


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