电子商务中基于Q学习的动态交叉销售方法，本文主要内容关键词为：电子商务论文,方法论文,动态论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
修订日期：2007-11-20
中图分类号：TP311 文献标识码：A 文章编号：1007-9807(2008)03-0106-08
0 引言
交叉销售研究领域的代表人物Kamakura认为：“客户与经销商的接触点越多，那么他的转移成本就越高，因此，交叉销售是一种培养稳固的顾客关系的重要工具。”[1]交叉销售是电子商务企业的一种重要营销手段，美国E-Tailing Group市场调查公司的研究表明，全球100家最大的在线零售企业中有62家企业采用各种形式的交叉销售策略[2]。
在传统的商务模式下，受获取信息能力以及计算能力的限制，营销人员无法在交易过程中实时制定优化的交叉销售商务条款，只能根据对未来市场需求的预测将交叉销售的商务条款事先制定出来，这些商务条款在一段时期里具有相对稳定性，不会随客户个体的特殊需求而动态改变。近年来，Amazon.com、Travel-related.com等电子商务企业利用电子商务系统的实时信息处理能力，实施了一种商务条款可以随客户的交易进程而实时制订的交叉销售策略[2]，在实际运行中，这些商务条款是由智能代理而非营销人员来制定和实施。宾夕法尼亚大学的Netessine等人将这一类交叉销售定义为“动态交叉销售”，而将传统的需要事先确定商务条款的交叉销售定义为“静态交叉销售”[2]。根据Netessine等人的定义，动态交叉销售是指：当买方提出对一种商品的购买请求时，经销方能够主动建议买方再同时购买另外一些商品，并对由这些商品组成的消费套餐提供一个折扣价格[2]。由于动态交叉销售的决策是伴随客户的交易进程而实时制定的，因此，实时决策能力是实施动态交叉销售的关键因素。
目前，有关交叉销售的研究成果大多集中于交叉销售机会的识别问题上，而对策略优化问题的研究非常少[3]。交叉销售的策略优化问题是指：在营销资源有限的条件下，如何优化交叉销售的商务条款，从而为企业带来最大收益。对此，Netessine等人在提出动态交叉销售这一概念的同时，重点探讨了动态交叉销售策略的优化模型[2]。在他们所提出的随机动态规划模型中，策略的优化需要同时考虑价格折扣水平、价格折扣对客户购物行为的影响以及商品库存资源三者之间的互动关系。尽管Netessine等人从库存资源限制的角度给出了科学的策略优化模型，但是，求解随机动态规划模型需要巨大的计算花销。为了保证决策的实时性要求，Netessine等人在求解过程中引入了启发式信息。然而，启发式信息带有很大的经验色彩，一般只有在所允许的计算时间里不可能找到最优解时，才使用这一策略。因此，Netessine等人的求解策略是在牺牲最优解的前提下，获得实时求解的能力。另外，Netessine等人认为，适合与目标商品进行交叉销售的商品候选集合并不是很大，但他们没有给出如何确定这一集合的方法，而只是假设这一集合为已知。Lerzan等人对银行呼叫中心的动态交叉销售问题进行了专门研究[4]，他们将动态交叉销售的策略优化问题映射为马尔可夫决策模型，模型考虑了通讯能力限制条件下如何优化动态交叉销售的实施，从而使企业获得最大收益。在他们的模型中，系统的状态仅仅用电话占线数量和空闲电话数量这两个变量来描述，因此系统的状态空间很小，方便了模型的求解。银行呼叫中心业务的这一特殊性与本文研究的问题有很大差距，因此，Lerzan的方法不能用来解决本文所要研究的问题。自从2004年动态交叉销售的概念被提出以来，有关这一领域的专门研究还很少。除上述两篇文献外，本文仅仅检索到2005年发表的一篇类似的短文，该文献针对旅行社的动态捆绑销售问题进行了分析[5]，但该文献仅仅从概念上对动态捆绑销售进行了介绍，没有给出具体的实施办法。通过对上述文献内容的分析，本文发现电子商务环境下实施动态交叉销售的现有理论研究成果中还没有一种特别有效的计算方法，能够既保证决策的实时性又能同时保证获得最优解。
电子商务零售行业中实施动态交叉销售的难度在于，在确定商品组合和价格折扣水平时必须参考商品的库存水平。例如，尽管某商品组合在一定的价格折扣水平下对买方具有很大的吸引力，但如果这些商品库存水平非常低，正处于供不应求的状态，那么，该商品以非折扣价单独出售可能会给经销商带来更大的收益。因此，各种商品的库存状态是动态交叉销售策略优化的依据。但是，在电子商务零售业中，商品的种类往往很多，库存系统的状态空间非常巨大[6]。例如，假设有N种不同的商品，每种商品的最大库存量为M，用x[，i]表示第i种商品的库存量，用向量(x[，1]，x[，2]，…，x[，N])[T]来描述库存状态，那么，系统可能出现的状态数量为N[M]。此外，在动态交叉销售决策中，系统不仅要参考商品的库存状态，还要参考客户首先提出了什么购买申请(即事件)，这样才能做出科学的决策。可能出现的事件与产品库存共同组成了一个巨大的状态空间，在此状态空间下的马尔可夫决策问题是个大规模马氏决策问题[6]。一些文献对大规模复杂随机系统的决策问题进行了研究，这些文献大多采用状态集结的方法，但是，状态集结的策略需根据具体问题的特点而不同，目前还没有通用的状态集结策略[6]。
动态规划是解马尔可夫决策问题的常用方法，但动态规划方法求解模型的计算量很大，在线计算不能满足决策实时性要求。最近，机器学习理论以及随机动态规划等领域若干思想的集成产生了一种新的方法学——强化学习，也称神经动态规划，这种方法为求解马尔可夫决策问题提供了一种新的策略。Q-学习算法是一种基于仿真的强化学习算法，是由Watkins[7]针对折扣型马尔可夫决策问题提出的。Q-学习过程可以在仿真环境下离线进行，其训练结果是一张LOOK UP表。当有决策需要时，系统只需查询LOOK UP表就可以立刻采取决策，而无需在线计算，因此，Q-学习方法能够满足决策的实时性要求。传统的Q-学习方法是对状态空间进行盲目地搜索，通过无数次迭代计算来获得稳定收敛的LOOK UP表。当状态空间非常巨大时，就很难获得稳定收敛的LOOK UP表[8.9]。
由于动态交叉销售决策中所面临的商品库存状态空间非常巨大，因此，采用传统Q-学习方法求解动态交叉销售问题的计算花销十分巨大。但实际上，大多数商品之间并不适合交叉销售，适合与某一特定商品组合为消费套餐的商品选项并不是很多。商务智能中的一种重要知识——关联规则，反映的是各种商品在销售中的关联关系，利用这种知识可以发现哪些商品可以和目标商品进行捆绑销售，哪些商品不能够与目标商品组成消费套餐。为此，本文首先提出一种事件驱动的马氏决策模型来描述动态交叉销售的决策过程，并进而提出一种知识驱动的Q-学习方法来求解该模型。根据本文提出的算法，关联规则被植入Q-学习过程，在Q-学习的每次迭代计算中，算法不是盲目地选择决策，而是在关联规则指导下，以较高的概率选择比较优良的决策，从而加快学习的收敛速度。仿真试验的结果表明，本文提出的方法具有较高的效率和精度。
1 动态交叉销售的事件驱动型马氏决策过程模型
本文研究这样一类动态交叉销售问题：1)商品按单件出售，对同一种商品，买方每次只买一件商品；2)卖方每次只选择一种商品与买方的第一选择组成消费套餐。
动态交叉销售的决策问题是一类特殊的马氏决策过程问题。普通型马氏决策过程(MDP)没有考虑系统中出现的事件对系统状态和决策的影响，而动态交叉销售中的每个决策除了要考虑各种商品的库存状态，还要考虑消费者首先提出购买的是什么商品。因此，可以将动态交叉销售的决策过程描述为一个由五元组
有限离散时间序列t：假设某营销活动周期的时间长度为T，将时间T划分为足够多的N个子时间段，保证每个时间段里最多只有一位买方到达。令t(t=1，2，…，N)表示某个时间段的序列号。
在时间点t，系统状态可能发生如下转移：
2 基于聚类分析确定交叉销售的商品集
从动态交叉销售的MDP模型可以看出，系统的状态空间十分巨大。事实上，许多商品之间根本没有交叉销售的可能，可以通过确定适合交叉销售的商品集合来降低问题中状态空间的规模。利用数据挖掘技术可以从历史交易数据中发现哪些商品有可能被客户同时购买，那么，这些商品就可以聚集在同一个簇中进行交叉销售。本文利用文献[12]提出的ROCK算法对整个商品集合进行聚类。在传统的聚类算法中，优化的标准是使每一个点到簇中心点的欧几里德距离之和最小，与此不同，ROCK算法是以交易记录之间联结(link)量作为簇划分的标准而非采用距离，这与本文问题的要求十分一致。算法的逻辑大体如下所述：
由于ROCK算法的优化标准是使同一个簇中的交易之间的link尽可能大，因此，同一个簇中的商品项具有较高的关联度，适合交叉销售。本文不给出ROCK算法的详细过程，读者可参考文献[12]。利用ROCK算法可以获得规模很小的适合交叉销售的商品集合。
3 知识驱动型Q-学习算法
尽管利用ROCK算法可以找出一个规模不大的彼此间关联密切的商品集合进行交叉销售，但是在这个商品集合中，有些商品之间的关联度大，有些个别商品之间的关联度很小，甚至是负关联的。利用数据挖掘技术可以从历史数据中发现商品之间的关联关系，本文利用这些知识来指导Q-学习过程，从而提高学习的效率。
3.1 Q-学习基本原理
传统的Q-学习的训练结果是由(s，d，Q(s，d))三元组组成的LOOK UP表。在实际应用中，当出现某状态s时，系统只需要查询LOOK UP表，选择Q(s，d)最大的决策。Q-学习方法的实现如下：
经过多次迭代计算，Q(s，d)将趋于收敛。
3.2 关联规则
利用数据挖掘技术可以从交易数据中挖掘出如下两类关联规则[13.14]：
1)正关联规则：正关联规则是型如：X
Y(c％，s％)的蕴涵式，规则中X，Y为商品项集，且X∩Y=
，c％表示规则的信任度，是指在购买了商品集X的交易中有c％的交易还包含商品集Y，s％表示规则的支持度，即总交易数中有s％的交易同时购买了商品集X和Y的商品。如果X和Y中分别只有一个商品项i和j，那么，这样的关联规则被称为简单正关联规则，记为ij(c％，s％)，其含义是：如果买方购买商品i，他还很有可能买商品j。
2)负关联规则：型为X
Y(c％，s％)是负关联规则的一种常见形式，它反映的是如果买方购买某些商品后，他很有可能不再买另一些商品。如果规则XY中X和Y分别只包含一个商品项，那么，这样的负关联规则被称为简单负关联规则，记为ij(c％，s％)。
令
％与
％分别表示信任度与支持度的阈值，如果某规则的信任度c％和支持度s％分别大于％和％，那么该规则成立。
3.3 知识驱动的Q-学习算法
利用Q-学习算法求解动态交叉销售问题时，其训练结果是由(s，e，d，Q(s，e，d))四元组组成的LOOK-UP表。在进行动态交叉销售决策时，智能代理只需浏览该表，选择当前库存状态s和事件e所对应的一个Q(s，e，d)值最大的决策d，每项决策由两项子决策d′和d〞组成。子决策d′=(i，j)表示系统挑选出商品j(j≠i)与事件e中的商品i捆绑为一个消费套餐，子决策d〞=
，表示系统给该消费套餐的折扣率为。
图1 Q-学习过程
Fig.1 Process of Q-learning
本文将关联规则植入Q-学习过程，在每次迭代中，不是盲目地选择决策，而是在关联规则指导下，以较高的概率选择比较优良的决策，其计算过程如图1所示。在图-1中，业务环境信息包括目前的库存状态
，以及发生的事件
。系统将LOOKUP表中与环境信息相关的各种决策的Q值以及规则前提为商品i的简单关联规则提交给控制模块。控制模块按下述方法调整各种决策的Q值效用度，根据各种决策的Q值效用度来形成各种决策的选择概率。
为了定量衡量某一决策的Q值对选择决策时的指导效用，本文用μ(，，d[，t])表示决策的Q值效用度，其计算方法如公式(9)所示，公式中
设有简单正关联规则为ij，为了与负关联规则的信任度相区别，用
％表示正关联规则的信任度，负关联规则的信任度记为
％。信任度表示规则的正确率，或规则的效用。公式(10)是利用正关联规则对决策的Q值效用度的修正。
在Q-学习的训练过程中，有多种决策探索方法，但最为常用的是Boltzmann提出的Softmax分布探索[15]。根据Softmax探索策略，在迭代计算中决策d[，t]被选中的概率为
(14)
公式(14)中τ为“温度”系数，τ越小，系统越倾向于选择Q值效用度大的决策，τ越大，系统越趋向于以平均的概率选择各种候选决策。系统将以公式(14)计算出的概率随机挑选一个决策，一旦一个决策被选中，那么就执行该决策，并根据获得的即时报酬和LOOK UP表中的信息，利用下面的公式在LOOK UP表中修改该决策的Q值。
根据上述原理，本文设计了一个知识驱动的Q-学习算法K-Q-learning，算法描述如下：
1 随机初始化LOOK UP表中各个决策的Q值
2 repeat
a)令商品集合C为交叉销售所考虑的所有商品
b)令t=1
c)repeat
【if发生某事件，即买方提出购买某商品i，且有i∈C
(1)观察当前的库存状态s，从LOOK UP表中找出状态s和事件所对应的所有决策，形成决策集合H，如果H中某决策所选择的捆绑商品已经不在商品集合C中，那么，将该决策从H中删除。
(2)从知识库中找出所有以商品i为前提的简单正关联规则和简单负关联规则
(3)根据公式(13)，利用关联规则对决策集合H中的各个决策的Q值效用度进行修正
(4)利用公式(14)形成集合H中的各个决策被选择的概率
(5)根据集合H中的各个决策被选择的概率随机选择一个决策
(6)执行该决策，计算该决策的即时收益，并观察新状态
(7)根据公式(15)在LOOK UP中修改该决策的Q值
(8)更新库存状态，如果某商品的库存量降为0，那么将该商品从商品集合C中删除】
t=t+1
当t=N时结束本轮循环】
d)当Q值收敛或达到规定的循环次数，结束循环】
4 仿真实验
4.1 实验目的
大量的文献已经证明零售商品之间存在各种关联关系，关联规则的挖掘技术已经日臻成熟。本文实验的目的不是验证商品间的关联关系，而是验证K-Q-学习算法的收敛效率，实验的另一个目的是验证动态交叉销售策略的收益能力。在实验中，需要对同一个商品集合，假设存在不同数量的关联规则的情况下，比较算法的收敛能力以及动态交叉销售策略的收益能利，从而分析本文提出的方法在什么情况下是适用的。
4.2 实验设计
为了分析K-Q-learning算法在动态交叉销售中的应用效果，本文设计了一个交易数据生成器，并将预设的关联规则存放在知识库中。在实验中规定有5种商品，每种商品的库存量为10件。在每个时间点t，交易事件发生器根据λ[，i]，F(p[，i])和
等随机参数随机生成一笔交易，同时进行K-Q-learning算法的一次迭代运算。在实验过程中，先规定商品之间存在的关联关系，即那些商品之间存在关联、关联的强度等，然后再依据上述参数生成交易数据。为了比较关联规则数量不同时算法的计算能力，本文规定了不同数量的关联规则，并分别生成不同的交易数据。针对不同的数据集，算法的计算的效率和动态交叉销售的收益能力分别如图2a和图2b所示。
为保证所模拟的交易过程体现出商品之间的关联关系，规定：
4)为避免因为价格折扣率过低(例如低于成本)引起消费者行为理性发生逆转，从而破坏关联规则所体现的购买行为模式，本文规定商品的折扣价格不能低于成本，尽管有时零售商会以低于成本的价格出售商品，但这种策略仅仅适用于特殊的紧急情况，不是本文考虑的范围。
4.3 实验结果分析
从图2a中可以发现，随着规则数量的提高，算法的计算效率明显提高。图2b对比了正关联规则和负关联规则数量不同时动态交叉销售的收益与不实行交叉销售策略的收益，从图2b会发现，正关联规则越多，动态交叉销售的收益越明显，在只有负关联规则而没有正关联规则的特殊情况下，动态交叉销售的收益与不实行动态交叉销售时的收益几乎相同。这一仿真试验的结果说明，动态交叉销售并非适用于任何商品集合，而是适用于那些彼此间存在正关联关系的商品集合。
5 结论
本文提出用Q-学习方法来解决电子商务环境下动态交叉销售中实时决策问题，针对动态交叉销售的马氏决策模型中的巨量状态空间问题，本文提出用关联规则理论来指导Q-学习的训练过程，从而保证获得稳定收敛的LOOK UP表。实验结果表明，本文提出的方法适用于那些商品间存在广泛的关联关系的商品集合。