多様性を含めたEコマースサイトのアイテムリスト最適化

商品販売・宿泊施設予約・音楽や動画配信サイトのように、課金システムを持つEコマースサイトは、私たちにとって身近なものとなりました。これらのサイトを見ると、様々なアイテムが掲載されています。掲載されるアイテムをどのように決定するか、どのような配置で並べるかは、Eコマースサイトの売り上げに直結する重要な問題です。単純に売上数などの人気順で並べてしまうと、類似性の高いアイテムが連続して配置されることが多く、特定の趣味趣向に偏る可能性があります。そこでNishimura et al., 2019では、類似度の高い項目が隣り合って配置されることに対するペナルティなどを用い、項目リスト問題を二次割り当て問題として定式化しました。そしてそれを量子アニーリングで解き、アイテムの人気度と多様性を考慮したアイテムリストを作成するのに成功しました。今回はこの問題を題材にして、JijModelingによる数理モデル実装と、JijZeptSolverでの求解をしてみましょう。

数理モデル

ウェブサイトのどの位置にどのアイテムを掲載するかを考えましょう。 掲載されるアイテムの集合を\(I\)、アイテムが掲載される位置の集合を\(J\)と定義します。 アイテム\(i\)を\(j\)番目の位置に配置するとき\(x_{i, j} = 1\)、それ以外の場合には\(x_{i, j} = 0\)となるようなバイナリ変数を用います。

各アイテムはどこか一箇所に掲載されなければならない

\[ \sum_{j \in J} x_{ij} = 1 \qquad (\forall i) \tag{1} \]

一つの場所には一つのアイテムしか掲載できない

\[ \sum_{i \in I} x_{ij} = 1 \qquad (\forall j) \tag{2} \]

目的関数

アイテム\(i\)を\(j\)番目の位置に配置したときに予想される人気や売上を\(s_{ij}\)のように書きます。すると

\[ \max \quad \sum_{i \in I} \sum_{j \in J} s_{ij} x_{ij} \tag{3} \]

が、最大化したいものです。 しかし上述したように、この目的関数だけでは同じ趣向のアイテムばかりが掲載されることになり、最適な配置とは考えられない解を得ます。 よって、目的関数に以下のような項を導入しましょう。

\[ D(\mathbf{x}) = - \sum_{i \in I} \sum_{i' \in I} \sum_{j \in J} \sum_{j' \in J} f_{ii'} d_{jj'} x_{ij} x_{i'j'} \tag{4} \]

ここで\(f_{ii’}\)はアイテム\(i\)とアイテム\(i’\)の類似度を表します。 そして\(d_{jj’}\)は、\(j\)番目と\(j’\)番目の配置が隣り合うとき1、そうでないとき0となるような関数です。 これにより、隣り合う位置に類似度が大きいアイテムが並ぶような解は、目的関数の値が小さくなります。 以上の議論から、この最適化問題で最大化したい関数は

\[ \max \quad \sum_{i \in I} \sum_{j \in J} s_{ij} x_{ij}- w \sum_{i \in I} \sum_{i' \in I} \sum_{j \in J} \sum_{j' \in J} f_{ii'} d_{jj'} x_{ij} x_{i'j'} \tag{5} \]

のように定式化されます。 第二項の係数\(w\)は、第二項の重みを調整するためのものです。

問題分割

大きな問題の場合、実行可能解が求まらないことや、仮に求まったとしても最適解から遠い場合があります。 そこで、まずは(3)式を目的関数とした最適化問題を解きます。 その後、アイテムリストの中でも上位に表示されるアイテムに対し、(5)式を用いた最適化問題を解きます。 これにより、閲覧頻度の高い上位のアイテムを効果的に決定することができます。

実装しましょう

ここからは、実際にJijModelingとJijZeptSolverを用いて、この問題を解くスクリプトを実装しましょう。

変数の定義

まずは(3)式を目的関数とした最適化問題を解くために必要な変数を定義しましょう。

import jijmodeling as jm

# make problem
problem = jm.Problem('E-commerce', sense=jm.ProblemSense.MAXIMIZE)

# define variables
I = problem.Natural('I')
J = problem.Natural('J')
s = problem.Float('s', shape=(I, J))
x = problem.BinaryVar('x', shape=(I, J))

Iはアイテムの集合、Jはアイテムを掲載する場所の集合、sは売り上げ予想を表す行列、xは最適化に用いるバイナリ変数です。また、今回の最適化問題は最大化問題なので、 jm.Problem(..., sense=jm.ProblemSense.MAXIMIZE) を設定する点に注意してください。

数理モデルの実装

続いて、(1), (2)式の制約と、(3)式の目的関数で表される数理モデルを実装しましょう。

# set constraint 1: onehot constraint for items
problem += problem.Constraint('onehot-items', lambda i: jm.sum(J, lambda j: x[i, j])==1, domain=I)
# set constraint 2: onehot constraint for position
problem += problem.Constraint('onehot-positions', lambda j: jm.sum(I, lambda i: x[i, j])==1, domain=J)
# set objective function 1: maximize the sales
problem += jm.sum(jm.product(I, J), lambda i, j: s[i, j] * x[i, j])

ここまでで出来上がった数理モデルを確認してみましょう。

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{E-commerce}\\\displaystyle \max &\displaystyle \sum _{i=0}^{I-1}{\sum _{j=0}^{J-1}{{s}_{i,j}\cdot {x}_{i,j}}}\\&\\\text{s.t.}&\\&\begin{aligned} \text{onehot-items}&\quad \displaystyle \sum _{j=0}^{J-1}{{x}_{i,j}}=1\quad \forall i\;\text{s.t.}\;i\in \left\{0,\ldots ,I-1\right\}\\\text{onehot-positions}&\quad \displaystyle \sum _{i=0}^{I-1}{{x}_{i,j}}=1\quad \forall j\;\text{s.t.}\;j\in \left\{0,\ldots ,J-1\right\}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[I\times J;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}I&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\J&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\s&\in \mathop{\mathrm{Array}}\left[I\times J;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\\end{alignedat}\end{array} \end{split}\]

インスタンスデータ作成

次に、I, J, s に対応するインスタンスデータを作成します。 ここではアイテム数を10、そしてアイテムを掲載する場所の数も10とします。 また、売り上げ予想行列sはランダムとします。

import numpy as np

# set the number of items
inst_I = 10
inst_J = 10
inst_s = np.random.rand(inst_I, inst_J)
instance_data = {'I': inst_I, 'J': inst_J, 's': inst_s}

JijZeptSolverで解く

JijZeptSolverを用いて、先程実装した問題を解いてみましょう。

import jijzept_solver

instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)

解のチェック

計算結果をチェックしてみましょう。

df = solution.decision_variables_df
x_indices = np.array(df[df["value"]==1]["subscripts"].to_list())
# initialize binary array
pre_binaries = np.zeros([inst_I, inst_J], dtype=int)
# input solution into array
pre_binaries[x_indices[:, 0], x_indices[:, 1]] = 1
# format solution for visualization
pre_zip_sort = sorted(zip(np.where(np.array(pre_binaries))[1], np.where(np.array(pre_binaries))[0]))
for pos, item in pre_zip_sort:
    print('{}: item {}'.format(pos, item))

0: item 6
1: item 7
2: item 2
3: item 8
4: item 1
5: item 4
6: item 3
7: item 0
8: item 9
9: item 5

問題の分割: ペナルティ項と変数固定の活用

次は、上位のアイテムに対してアイテム類似度を考慮した目的関数(5)式で、最適化問題を解きましょう。 そのために新しく変数を定義します。

# set variables for sub-problem
f = problem.Float('f', shape=(I, J))
d = problem.Float('d', shape=(I, J))
fixed_IJ = problem.Natural('fixed_IJ', ndim=2)
num_fixed_IJ = problem.DependentVar("num_fixed_IJ", fixed_IJ.len_at(0))
w = problem.Float('w')

fixed_IJは次の最適化問題では解かない（すなわち、下位に表示されているアイテムとその位置に対応する）変数の添字の集合を表します。 これは二次元配列として表現され、例えば\(x_{5, 6} = 1, x_{7, 8} =1\)のように固定する場合にはfixed_{IJ} = [[5, 6], [7, 8]]のようになります。 fはアイテム類似度を表す行列、dは配置が隣り合うかどうかを表す行列です。 次に、アイテムの類似度を最小化するための項を追加しましょう。

# set penalty term 2: minimize similarity
problem += - w * jm.sum(jm.product(I, J, I, J), lambda i, j, k, l: f[i, k] * d[j, l] * x[i, j] * x[k, l])

最後に、下位に表示されているアイテムとその位置を固定する制約条件を追加しましょう。

# set fixed variables
problem += problem.Constraint('fix', lambda v: x[fixed_IJ[v][0], fixed_IJ[v][1]]==1, domain=num_fixed_IJ)

Constraintを用いることで、変数固定を自明な制約として記述することができます。
では、新たに追加された項と制約条件を表示してみましょう。

problem

\[\begin{split}\begin{array}{rl} \text{Problem}\colon &\text{E-commerce}\\\displaystyle \max &\displaystyle \sum _{i=0}^{I-1}{\sum _{j=0}^{J-1}{{s}_{i,j}\cdot {x}_{i,j}}}+\left(-w\right)\cdot \left(\sum _{i=0}^{I-1}{\sum _{j=0}^{J-1}{\sum _{k=0}^{I-1}{\sum _{l=0}^{J-1}{{f}_{i,k}\cdot {d}_{j,l}\cdot {x}_{i,j}\cdot {x}_{k,l}}}}}\right)\\&\\\text{s.t.}&\\&\begin{aligned} \text{fix}&\quad \displaystyle {x}_{{{fixed\_{}IJ}_{v}}_{0},{{fixed\_{}IJ}_{v}}_{1}}=1\quad \forall v\;\text{s.t.}\;v\in \left\{0,\ldots ,num\_{}fixed\_{}IJ-1\right\}\\\text{onehot-items}&\quad \displaystyle \sum _{j=0}^{J-1}{{x}_{i,j}}=1\quad \forall i\;\text{s.t.}\;i\in \left\{0,\ldots ,I-1\right\}\\\text{onehot-positions}&\quad \displaystyle \sum _{i=0}^{I-1}{{x}_{i,j}}=1\quad \forall j\;\text{s.t.}\;j\in \left\{0,\ldots ,J-1\right\}\end{aligned} \\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[I\times J;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}d&\in \mathop{\mathrm{Array}}\left[I\times J;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\f&\in \mathop{\mathrm{Array}}\left[I\times J;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\fixed\_{}IJ&\in \mathop{\mathrm{Array}}\left[(-)\times (-);\mathbb{N}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{N}\\I&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\J&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\s&\in \mathop{\mathrm{Array}}\left[I\times J;\mathbb{R}\right]&\quad &2\text{-dimensional array of placeholders with elements in }\mathbb{R}\\w&\in \mathbb{R}&\quad &\text{A scalar placeholder in }\mathbb{R}\\\end{alignedat}\\&\\&\text{Dependent Variables:}\\&\qquad \begin{alignedat}{2}num\_{}fixed\_{}IJ&=\mathop{\mathtt{len\_{}at}}\left(fixed\_{}IJ,0\right)&\quad &\in \mathbb{N}\\\end{alignedat}\end{array} \end{split}\]

数理モデルの実装が完了したところで、アイテム類似度と変数固定のためのインスタンスを作成しましょう。

# set instance for similarity term
inst_f = np.random.rand(inst_I, inst_I)
triu = np.tri(inst_J, k=1) - np.tri(inst_J, k=0)
inst_d = triu + triu.T
# set instance for fixed variables
reopt_N = 5
item_indices = x_indices[:, 0]
position_indices = x_indices[:, 1]
fixed_indices = np.where(np.array(position_indices)>=reopt_N)
fixed_items = np.array(item_indices)[fixed_indices]
fixed_positions = np.array(position_indices)[fixed_indices]
inst_fixed_IJ = np.array([[x, y] for x, y in zip(fixed_items, fixed_positions)])
# set weight fo the penalty
inst_w = 1.0

instance_data = {'I': inst_I, 'J': inst_J, 's': inst_s, 'f': inst_f, 'd': inst_d, 'fixed_IJ': inst_fixed_IJ, 'w': inst_w}

それでは、類似度に関するペナルティと変数固定を考慮した数理モデルを、JijZeptSolverで最適化計算しましょう。

instance = problem.eval(instance_data)
solution = jijzept_solver.solve(instance, solve_limit_sec=1.0)

再び、得られた解をチェックしてみましょう。

df = solution.decision_variables_df
x_indices = np.array(df[df["value"]==1]["subscripts"].to_list())
# initialize binary array
post_binaries = np.zeros([inst_I, inst_J], dtype=int)
# input solution into array
post_binaries[x_indices[:, 0], x_indices[:, 1]] = 1
# format solution for visualization
post_zip_sort= sorted(zip(np.where(np.array(post_binaries))[1], np.where(np.array(post_binaries))[0]))
for i, j in post_zip_sort:
    print('{}: item {}'.format(i, j))

0: item 7
1: item 6
2: item 2
3: item 1
4: item 8
5: item 4
6: item 3
7: item 0
8: item 9
9: item 5

2つの結果を比較してみましょう。

items = ["Item {}".format(i) for i in np.where(pre_binaries==1)[0]]
pre_order = np.where(pre_binaries==1)[1]
post_order = np.where(post_binaries==1)[1]

グラフ描画のために、次のようなクラスを定義しましょう。

from typing import Optional
import matplotlib.pyplot as plt

class Slope:
    """Class for a slope chart"""
    def __init__(self,
        figsize: tuple[float, float] = (6,4),
        dpi: int = 150,
        layout: str = 'tight',
        show: bool =True,
        **kwagrs):

        self.fig = plt.figure(figsize=figsize, dpi=dpi, layout=layout, **kwagrs)
        self.show = show

        self._xstart: float = 0.2
        self._xend: float = 0.8
        self._suffix: str = ''
        self._highlight: dict = {}
        
    def __enter__(self):
        return(self)

    def __exit__(self, exc_type, exc_value, exc_traceback):
        plt.show() if self.show else None
        
    def highlight(self, add_highlight: dict) -> None:
        """Set highlight dict
        
        e.g.
            {'Group A': 'orange', 'Group B': 'blue'}
        
        """
        self._highlight.update(add_highlight)
        
    def config(self, xstart: float =0, xend: float =0, suffix: str ='') -> None:
        """Config some parameters
        
            Args:
                xstart (float): x start point, which can take 0.0〜1.0        
                xend (float): x end point, which can take 0.0〜1.0
                suffix (str): Suffix for the numbers of chart e.g. '%'
        
            Return:
                None
                
        """
        self._xstart = xstart if xstart else self._xstart
        self._xend = xend if xend else self._xend
        self._suffix = suffix if suffix else self._suffix
    
    def plot(self, time0: list[float], time1: list[float], 
             names: list[float], xticks: Optional[tuple[str,str]] = None, 
             title: str ='', subtitle: str ='', ):
        """Plot a slope chart
        
        Args:
            time0 (list[float]): Values of start period
            time1 (list[float]): Values of end period
            names (list[str]): Names of each items
            xticks (tuple[str, str]): xticks, default to 'Before' and 'After'
            title (str): Title of the chart
            subtitle (str): Subtitle of the chart, it might be x labels
        
        Return:
            None
        
        """
        
        xticks = xticks if xticks else ('Before', 'After')
        
        xmin, xmax = 0, 4
        xstart = xmax * self._xstart
        xend = xmax * self._xend
        ymax = max(*time0, *time1)
        ymin = min(*time0, *time1)
        ytop = ymax * 1.2
        ybottom = ymin - (ymax * 0.2)
        yticks_position = ymin - (ymax * 0.1)
        
        text_args = {'verticalalignment':'center', 'fontdict':{'size':10}}
        
        for t0, t1, name in zip(time0, time1, names):
            color = self._highlight.get(name, 'gray') if self._highlight else None
            
            left_text = f'{name} {str(round(t0))}{self._suffix}'
            right_text = f'{str(round(t1))}{self._suffix}'
            
            plt.plot([xstart, xend], [t0, t1], lw=2, color=color, marker='o', markersize=5)
            plt.text(xstart-0.1, t0, left_text, horizontalalignment='right', **text_args)
            plt.text(xend+0.1, t1, right_text, horizontalalignment='left', **text_args)
        
        plt.xlim(xmin, xmax)
        plt.ylim(ytop, ybottom)
    
        plt.text(0, ytop, title, horizontalalignment='left', fontdict={'size':15})
        plt.text(0, ytop*0.95, subtitle, horizontalalignment='left', fontdict={'size':10})
        
        plt.text(xstart, yticks_position, xticks[0], horizontalalignment='center', **text_args)
        plt.text(xend, yticks_position, xticks[1], horizontalalignment='center', **text_args)
        plt.axis('off')
        
        
def slope(
    figsize=(6,4),
    dpi: int = 150,
    layout: str = 'tight',
    show: bool =True,
    **kwargs
    ):
    """Context manager for a slope chart"""
    
    slp = Slope(figsize=figsize, dpi=dpi, layout=layout, show=show, **kwargs)

    return slp

最後に、比較のためのグラフを表示しましょう。

# compute similarity for the first
A = np.dot(instance_data['f'], pre_binaries)
B = np.dot(pre_binaries, instance_data['d'])
AB = A * B
pre_similarity = np.sum(AB)

# compute similarity for the second
A = np.dot(instance_data['f'], post_binaries)
B = np.dot(post_binaries, instance_data['d'])
AB = A * B
post_similarity = np.sum(AB)

pre_string = "Similarity: {:.2g}".format(pre_similarity)
post_string = "Similarity: {:.2g}".format(post_similarity)
with slope() as slp:
    slp.plot(pre_order, post_order, items, (pre_string, post_string))

最初の最適化結果と比較すると、下位部分は変数固定により変化はありません。 しかし、上位部分は類似度を考慮したことで、順番に変動が見られます。

参考文献

• Nishimura et al., 2019, "Item Listing Optimization for E-Commerce Websites Based on Diversity"