Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
4
Help us understand the problem. What is going on with this article?
@voyager

レコメンドの最適化

1. レコメンド

レコメンドでは学習データをもとに機械学習などでモデルを作り、ユーザxアイテムに関して予測スコアをつけて、各ユーザに関して予測スコアが高いアイテムTOP ?を見せることが多いです。しかしこの方法では人気アイテムの予測スコアが高くなり、人気のないアイテムの予測すこが小さくなるので、人気のあるアイテムばかり広告が出て、人気のないアイテムには広告が出ないという問題があります。
広告サイトでは、人気のないアイテムに対してもある程度のCVを得るため広告を出す必要がある場合が多いです。

2. 最適化

アイテム単位で広告するユーザ数に制限を入れることにより解消することができます。
例えば人気アイテムには広告を出す最大ユーザ数を設定し、人気のアイテムには広告を出す最小ユーザ数を設定すれば良いです。

3.例

ユーザ数 30、アイテム数 20とします。
各ユーザに関して5件アイテムをレコメンドすると考えます。

ただしすべてのアイテムに関して10人以下しか広告を出さず
アイテム0,1,2は人気アイテムなので3人以下しか広告を出さず
アイテム18,19は人気のないアイテムなので9人以上広告を出すとします。

以下
$ scores_{ui} $: ユーザu,アイテムiの予測スコアとします。

上記の条件を数式にすると

変数

$ choices_{ui} $ : ユーザuにアイテムiの広告を出すかどうか(1 or 0)

目的関数

$ \sum_{u} \sum_{i} scores_{ui} * choices_{ui} $
を最大化する。

制約条件

  1. $\sum_{i} choices_{ui} <= 5 (\forall u)$
  2. $\sum_{u} choices_{ui} <= 10 (\forall i)$
  3. $\sum_{u} choices_{ui} <= 3 (i=0,1)$
  4. $\sum_{u} choices_{ui} >= 9 (i=18,19)$

となり線形計画法で解けます。

pulpで実数すると

USER =30
ITEM = 20
Users = list(range(0,USER))
Items = list(range(0,ITEM))

prob = pulp.LpProblem("test",pulp.LpMaximize)

# 変数の宣言
choices = pulp.LpVariable.dicts("Choice",(Users,Items) , 0, 1, pulp.LpInteger)

# 目的関数
prob += pulp.lpSum([scores[u][i] * choices[u][i] for u in Users for i in Items ])

# 制約条件
#1. $\sum_{i} choice_{ui} <= 5 (\forall u)$
for u in Users:
    prob += pulp.lpSum([choices[u][i] for i in Items]) <=5

#2. $\sum_{u} choice_{ui} <= 10 (\forall i)$
for i in Items:
    prob += pulp.lpSum([choices[u][i] for u in Users]) <= 10

#3. $\sum_{u} choice_{ui} <= 3 (i=0,1)$
for i in [0,1]:
    prob += pulp.lpSum([choices[u][i] for u in Users]) <= 3

#4. $\sum_{u} choice_{ui} >= 9 (i=18,19)$
for i in [18,19]:
    prob += pulp.lpSum([choices[u][i] for u in Users]) >= 9

status = prob.solve()

で解けます。

今scoresを下記のようにアイテム1,2は人気アイテムなのでスコアを増やして、スコア18,19は人気のないアイテムなのでスコアを減らします。

np.random.seed(10)
scores = np.random.rand(USER, ITEM)
scores[:,0] += 0.3
scores[:,1] += 0.3
scores[:,18] -= 0.3
scores[:,19] -= 0.3
scores = np.clip(scores, 0, 1)

サンプルソースは
https://github.com/tohmae/pulp_sample/blob/master/score_optimize.py
にあります。

上記のスコアで最適化を実行した場合、制約条件2,3,4がない場合は

Item0 Item1 Item2 Item3 Item4 Item5 Item6 Item7 Item8 Item9 Item10 Item11 Item12 Item13 Item14 Item15 Item16 Item17 Item18 Item19
User0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0
User1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0
User2 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0
User3 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0
User4 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0
User5 1 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0
User6 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1
User7 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
User8 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0
User9 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0
User10 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0
User11 0 1 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0
User12 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0
User13 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0
User14 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
User15 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0
User16 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0
User17 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0
User18 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0
User19 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
User20 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0
User21 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0
User22 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0
User23 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0
User24 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0
User25 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0
User26 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
User27 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0
User28 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0
User29 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0

制約条件2,3,4を入れた場合は

Item0 Item1 Item2 Item3 Item4 Item5 Item6 Item7 Item8 Item9 Item10 Item11 Item12 Item13 Item14 Item15 Item16 Item17 Item18 Item19
User0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1
User1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1
User2 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0
User3 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0
User4 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0
User5 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0
User6 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1
User7 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 0 0
User8 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0
User9 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0
User10 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0
User11 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1
User12 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0
User13 0 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0
User14 0 0 1 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
User15 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0
User16 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1
User17 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0
User18 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1
User19 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
User20 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0
User21 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1
User22 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0
User23 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0
User24 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0
User25 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0
User26 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1
User27 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0
User28 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 0
User29 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1

となり制約条件2,3,4を入れた方がアイテム1,2の広告数が減って、アイテム18,19の広告数が増えることがわかります。

線形計画法でレコメンドの最適化ができました。

4
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
voyager

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
4
Help us understand the problem. What is going on with this article?