基于机器学习和模拟退火的优惠券推荐系统

赵 刚

（上海赛可出行科技服务有限公司，上海 201299）

0 引言

需求弹性反应商品需?求量对价格变动做出反应的敏感程度，营销的主要目标客户群是对价格敏感、需求弹性大的消费者，可以通过调整商品价格来促使需求弹性大的消费者进行消费。

优惠券可提升消费者的下单意愿，已成为企业常用的营销工具。优惠券的主要作用是有效提升客户交易满意度，引导消费者下单，从而提升企业的整体收益。如果企业希望达到收益最大化的目标，就应该给实际有需要的消费者发放优惠券，从而在营销成本一定的情况下，完成更多的营销转化任务。企业合理制定优惠券发放策略，使消费者享受优惠的同时，提高企业的营收和利润，从而达到双赢的目的，这是当前企业在营销环节的核心问题。

1 问题分析

1.1 优惠券特点

目前，优惠券已普遍用于服务和商品销售领域，优惠券分不同的获取方式和类型。获取方式分为2种，企业主动发放和客户自动领取。优惠券类型有折扣类、现金类以及满减类等。兼顾提高使用率和降低补贴成本是一个难题。

优惠券的本质是以企业让利的形式吸引更多消费者购买商品（降低商品消费门槛，提高商品单量）。同时，优惠券是一种隐性的商品价格歧视策略，企业针对不同的消费者需求制定相同的价格和差异化的优惠券（即在价格相同的情况下，针对不同消费者的消费能力发放不同的优惠券），既不会侵犯消费者的知情权，也不会违背公平交易的原则，这是企业追求最大利润的合理定价行为。

1.2 发放策略

传统的优惠券发放策略包括前台发放和后台发放。前台发放为运营人员制定活动，告知消费者获取优惠券的规则，让消费者通过分享、做任务以及消费等形式参与活动，如果满足活动的奖励规则，就为消费者发放优惠券。后台发放主要是将消费者分群，例如分为新消费者、老消费者以及流失消费者等，通过精准定位目标消费者的方法统一发放优惠券。后台发放主要依靠运营人员的经验和人工观察（观察用户使用优惠券的购物偏好）来对发放策略进行调整。传统的策略具有滞后性和依赖差异性的人工经验（不具有普适性）等特点，难以满足当前商业智能发展的需求。

为了解决前台发放和后台发放存在的难以制定策略的问题，该文提出智能推荐发放方法。对前台发放场景来说，可以设置合理的优惠券面额，从而达到吸引消费者的目的；对后台发放场景来说，可以通过自动计算每个消费者应发放的优惠券进行个体精准营销。

2 优惠券推荐系统

优惠券推荐系统是一个带Web用户界面的交互式系统，支持运营人员输入推荐规则，例如成本约束、人群限制、优惠券类型、金额限制以及使用条件等。优惠券推荐系统根据所设规则进行智能运算，运算的结果包括发放张数、发放人数、成本以及预期营收等。

推荐系统架构和二阶段优惠券交互图如图1所示，推荐系统架构共分为4个模块。其交互步骤如下：首先，客户消费产生新的消费数据。其次，一阶段机器学习根据消费数据进行训练，完成模型更新。再次，二阶段依赖一阶段生成的机器学习模型，在优惠券推荐时执行预测逻辑和模拟退火算法，生成最优发放结果数据。最后，根据最优发放结果为用户发放优惠券。

2.1 规则约束模块

规则约束模块可以处理运营人员的UI界面操作，还可以展示操作结果，程序将发放结果数据和规则的设置存入推荐数据库（推荐数据库一般选择关系型数据库）。

2.2 AI模型训练模块

AI模型训练模块的目标是学习消费者在购买商品时使用优惠券的概率。输入信息为消费者购买商品是否使用优惠券的数据，输出信息为1个函数，该函数通过机器学习的方法习得1个概率，该概率能够度量客户对优惠券的敏感程度。

2.3 AI模型预测模块

AI模型预测模块是部署AI模型训练模块生成的机器学习模型，还可以根据消费者特征和优惠券特征预测使用概率。SA模拟退火推荐模块调用AI模型预测模块预测消费者使用优惠券的概率。

2.4 SA模拟退火推荐模块

该推荐模块的目标是计算最优推荐结果，其价值的评估是在营销成本一定的情况下，使企业营收或利润最大化；或在预定营销和利润增长目标的情况下，计算所需的最低补贴成本。根据推荐结果，运营人员会使用该结果或调整规则重新计算，当该推荐结果满足企业成本要求或达成企业利润目标时，为消费者发放优惠券。

3 机器学习预测

机器学习是通过学习已知的知识来推断未知信息的方法，可以应用于经济活动的各个方面。该文的机器学习的目标是在为消费者发放优惠券或消费者领取优惠券后，由预测系统预测消费者在2周内进行消费的概率。如果消费者需求弹性大，则通过调整优惠券的面值来提高其消费概率；如果消费者需求弹性小且对价格不敏感，那么无论是否有优惠券（或者优惠券的面值大小）都不会影响他们的消费行为，此时应该不发放优惠券（或者发放面值较小的优惠券）。

3.1 特征构造

特征的数据来自消费者信息数据库、商品信息数据库以及优惠券数据库（包括发放信息和使用信息）。采用描述统计、维度聚合以及关联分析等方法构造数据特征。

数据模型的特征构造分为5类：消费者特征、商品特征、优惠券特征、消费者对商品的偏好特征以及消费者对优惠券的偏好特征。消费者特征主要包括年龄、性别、消费频率以及消费金额等；商品特征包括商品类型、商品投放优惠券次数以及商品核销优惠券次数等；优惠券特征包括面值、折扣率以及折扣类型等；消费者对商品的偏好特征包括对该商品的消费频率、下单后的支付率等；消费者对优惠券的偏好特征包括订单平均折扣率、优惠券订单比例等。

优惠券的使用预测等价为机器学习对数据的二分类问题。因此，将数据模型的标签设置为0和1，0表示2周内未使用优惠券，1表示2周内使用过优惠券，用特征加标签构成样本集。

3.2 算法训练和预测

首先，该文采用LightGBM对算法进行训练，LightGBM是一个实现GBDT算法的框架。将样本数据集划分为训练集和测试集，测试集中的数据是从样本数据集中随机抽取的，并且与训练集的数据无交叉，从而生成离线模型。

其次，采用（开源的）Java模型工具库lightgbm_predict4j对算法进行预测。因为主流的后端框架是Java语言，所以一般使用Java语言完成在线模型预测工作。在用LightGBM生成离线模型之后，使用lightgbm_predict4j加载该模型。

最后，在Java在线应用中进行预测。

3.3 算法评价

二分类一般使用AUC值作为模型的评价标准，AUC表示接受者操作特性曲线（ROC曲线）下的面积。AUC的取值范围为0.5～1.0，当AUC=0.5时，其真实性最低，无实际价值；AUC越接近1.0，其真实性越高，机器学习分类器的效果也就越好。一般训练的模型在测试集上的AUC大于0.8，即可在实际业务中应用，并能取得不错的业务效果。

3.4 筛选重要特征

二分类算法收敛后，机器学习算法可以展示各个特征对模型的重要性评分。并按重要性评分对特征进行排序，选取前n个特征重新进行模型训练，计算对应的AUC值。当找到AUC的最大值时，相应的前n个特征值为最佳的特征组合。

4 模拟退火推荐

优惠券推荐属于组合优化问题，随着问题规模的扩大，搜索空间也会增长，使求最优解变得非常困难，因此一般会采用寻找可接受满意解的方法。遗传算法（Genetic Algorithm，GA） 、模拟退火（Simulate Anneal，SA）、神经网络（Neural Network，NN）是解决这类问题的3种经典启发式算法，这类算法都是先生成初始可行解，再采用优化方法逐步得到可接受满意解。

模拟退火算法是单体启发式算法，其优点是易于对复杂问题进行建模，且总是有可能找到全局最优解。下面以消费者的平均期望优惠券使用率表示目标订单数或目标营收的近似值，为用户发放单一面值的优惠券，以说明模拟退火在优惠券推荐中的应用方法（其他规则和场景与其类似）。

4.1 数学模型

消费者的预测使用概率如公式（1）所示。

式中：x为消费者特征数据；g（x）为对消费者的补贴成本，即对消费者发放优惠券的面值；p（x）为x在g（x）情况下的预测使用概率；f为第一阶段的机器学习预测求解的概率函数（根据消费者过去的消费数据）。

消费者的发放成本如公式（2）所示。

式中：x为消费者特征数据；h（x）为x的发放成本。

目标优化函数如公式（3）所示。

图1 推荐系统架构和二阶段优惠券交互图

式中：L为总发送成本。

设消费者数量为n，消费者x标记为x～x，将优惠券发放问题转化为求解g（x）的问题，使目标优化函数L取得最小值。

4.2 约束条件

设定最优化问题的约束条件，所有消费者的预测使用概率均值约束如公式（4）所示。如果未接受新解，则对未接受次数d累加1。接受概率σ如公式（6）所示。5） 如果满足终止条件，则输出当前解，将其作为最优解， 计算结束， 终止条件定义如公式（7）所示。6） 退火内循环1轮结束，温度降温后转第2步。温度更新方法如公式（8）所示。

式中：α为本次发放目标期望平均使用率约束因子；p 为计算的所有消费者的预测使用概率实际值；n为消费者数量。

单个消费者的补贴约束如公式（5）所示。

式中：β为单个消费者补贴上限；g（x）为对消费者x的补贴成本，g（x）取值为离散整数值，取值范围为[0，β]。

4.3 求解过程

对g（x）的求解过程如下：1） 算法初始化。执行智能发放优惠券模拟退火算法的流程如图2所示。设初始化温度t，每个温度t下的迭代次数为m，温度的衰减系数为u[u∈（0，1）]，初始解s为每个消费者最大补贴金额β，根据公式（1）～公式（3）计算初始化目标函数值L。2） 当k=1，…，m时，重复执行第3步～第5步。m为关键参数，表示马尔科夫链长度（此处是对m现实含义的进一步解释。从算法角度看，m为温度t下的迭代次数；从现实含义来看，m为马尔科夫链长度），其数字越大，模拟退火算法搜索就越充分，越有可能找到全局最优解，但会增加算法的搜索时间。3） 根据随机选择操作对当前解进行变换，得到的新解为s'，具体过程为随机选择消费者x，对g（x）进行随机变换（增加或减少），该变换需要满足公式（4）、公式（5）所定义的约束条件。4） 计算目标函数变化量。如果变化量小于0，就说明新解比原有解更好（接受新解）；否则基于Metropolis准则，用概率σ接受新解。在接受新解后，设置未接受次数d=0；

式中：K为玻尔兹曼常数，K=1.380649×10；t为当前温度；ΔL为目标函数变化量，ΔL=L-L（L为新解的目标值）；σ为接受概率。

图2 模拟退火推荐算法流程图

式中：d为未接受新解的连续次数，如果连续d次未接受新解，则默认已收敛；β为单个消费者补贴上限；n为消费者数量。

式中：u为温度衰减系数；t为当前温度。

5 结语

智能营销在经济领域中占据越来越重要的地位，优惠券是一种有效的营销方法。为了解决智能营销问题，该文建立了优惠券推荐系统，该系统采用机器学习和模拟退火算法解决优惠券发放最优化问题。该推荐系统的特点是可设置各种补贴目标，例如补贴上限、消费者使用率以及目标订单数等，由推荐系统自动完成对每个消费者个性补贴的计算工作。 同时，该算法能估算总营销成本以及营销成果的可提升空间。如果运营人员评估营销成本高于预算，还可以重新调整约束规则，再次进行计算。该算法具有按需补贴、预算可控以及个性补贴等优势，可以降低企业营销的难度和成本。