论文地址 ：Decision Trees for Uplift Modeling

摘要

什么是uplift模型

大多数分类的目的是在给定的数据集基础上获取到一个更高的准确率。然而，在更多的实际案例中，（是否邮寄或者治疗病人时是以预测类别进行选择的）， 我们不应该以他们的类别而进行建模，而是应该由我们的action行为带来的变化概率进行建模。之后应该对最有利润的对象执行action。这个问题就是 、不同相应分析、真正提升模型。在这篇文章我们针对这种问题推出基于树分类器。这里我们设计了心的分裂标准和剪枝方法。实验结果也证明了我们方法的有效性，证明了我们的方法比现在的uplift模型技术的更好的效果。

一、介绍和符号说明

在大多涉及到分类的问题中，建模的目的是让我们选择部分顾客进行执行一些action动作。一个典型的例子就是经过一个小的实验后训练一个模型，去预测哪些客户会在营销活动结束后去购买。然后根据预测结果找到最有可能购买的用户。然而，这个可能不是营销人员想要的结果，他们想要的人群是那些因为他们的施加的营销活动才去购买的人。

说白了就是要减少不必要的营销活动带来的损失

这两个目标显然是不对等的，某些消费者即使没有收到营销活动他们都会去购买的。对他们执行营销活动就会造成额外的成本，更坏的情况下，过度的营销活动会是得消费者厌烦，从而影响了他们在未来购买的概率。事实上，在广告届众所周知的是广告营销活动的确会使得一些顾客厌烦，但是他们又无法识别出这些顾客。
相同的问题在医学界更加频繁。在一个临床试验中，随机划分病人，一组接受A治疗，另外一组接受B或者不治疗。 然后统计两个组全部整体的效果差异。然而，如果A只对一部分人有效（具有遗传特性的一些人）对其他人无效，在实际中这种效果可能不会被发现。在某些情况下，分析是在几个子数据组中单独进行的，但是没有系统的方法自动检测这些子组或者直接建立相应差异的模型。
尽管这个问题普遍存在且十分重要，但是这个问题在文献还是受到很少的关注，这个叫uplift模型、不同响应模型、增量值模型或者真正提升模型。随机选择一部分人施加action然后进行分析（医学实验或者市场营销），这样的样本称为treatment 数据（实验组数据）。同时随机选择与treatment组不相交的一部分人不施加任何action，这部分样本称为control数据（对照组数据），作为施加action评估结果的背景。现在的任务建立一个模型去预测treatment和control数据集的概率差异，而不是预测属于某一类（例如购买或者治好病人）的概率。
如果treatment组的数据选择是完全随机的，这样模型还有另外一个优点：模型的效果（treatment和control的差异）是由施加的action导致的。样本经常受其他的活动营销（例如竞争对手的市场活动），这些影响不能被直接考虑进去。通过随机选择treatment和control组的数据，我们可以自动剔除这些影响，因为这些影响对treatment和control作用是相等的。
尽管决策树不在是一个热门的研究领取，但他仍然活跃在工业领域（包括所有的商业分析产品），而且作为历史上最先采用的机器学习方法，它也是uplift模型的技术首要候选。
现在我们描述本文的贡献。虽然在历史文献中已经描述了uplift决策树，但是他们都是十分基础，简单的使用样本分裂标准（直接最大化样本差异）。此外，没有特殊的剪枝方式被描述。我们提出的uplift模型是基于信息论的，不像之前的方法，它只能允许二分类问题和二叉分裂，我们的算法可以处理多分类和多分裂。
此外，所有提出的方法都是经过精心设计的，因此他们在分类问题使用的标准分类树的直接概况，这里我们特别指出CART和C4.5。也就是说，当对照组为空时，本文的方法退化为普通的决策树。这种方法有2个优点：第一，当没有对照组数据时（这种经常经常发生在树的层级较低时），尽管我们无法对uplift建模，我们还是可以尝试分类建模的。第二，作为一个特例，这些方法被简化为众所周知的、合理和经过充分研究的方法，这个事实正事了它背后的直觉和使用的设计原则。

符号

现在介绍一下本文使用的符号，这里与传统模型不同的是我们现在有两种数据集：treatment 和control。双数据集需要一个特殊的符号表示。
我们把决策树的非叶子节点称之为tests。一个test含有有限个输出结果。我们为每一个类别创建一个test，test的结果就是所有样本的结果，这点类似于C4.5。对于每个数值属性X我们创建根据X<v（v是一个具体的数）划分为多个test。为每一个v创建一个test，v是数据中存在的属性X的两个连续不同值的中点（说白了就是将属性X进行分段处理）。更细讲的参考决策树的文档。
Tests可以用符号大写A表示（A表示具有一些属性的样本）。不同的类别用Y表示。Y是离散值。a表A的一个结果，y表示Y的一个结果。表示的是A的所有结果。表示的是所有类别的结果。
基于实验组数据的概率估计用，基于对照组的数据的概率估计用表示。表示的是基于实验组数据的Y的概率分布情况，表示的当时实验组的概率数据，在对照组也是类似表示。条件概率表示也是往常的形式， 表示的是在实验组当时的Y的分布情况。
在计算 和时我们用到了拉普拉斯修正

拉普拉斯修正: 原始的条件概率计算公式为，被修正后的是

此外和分表表示的是实验组和对照组的样本数据。和分别表示的是当时的数据量。最后我们令，

二、相关工作

尽管uplite模型相比之前最近受到了更高的关注，但是在文献中只是模糊的说明了一下算法，细节部分被忽略了。下面我们介绍一下相关的研究论文。
uplift模型主要有两种方法。最显然的方法是建立两个模型（two-model），一个模型训练treatment ，另外一个模型训练control数据。使用时我们将两个模型的预测值进行相减作为最终的结果。这里有个主要的缺点：我们想要的概率预测值可能与单独每一个模型差异很大（我们想要预测是实验组和对照组的差异，而模型训练目标只是各自的数据组内把正负样本分开，并不能学到两种组的差异情况）。在决策树的情况下，它并不一定有利于因为action而导致的实验组和对照组的相应差别分裂，而是在实验组和对照组各自的组内预把预测结果分开。
第二种方法就是训练一个模型，试图直接为实验组和对照组的差异进行建模。在文献中一种决策树的变种形式被提出，它是根据利用树的节点中全部实验组的结果与全部对照住的结果差异进行分裂的，就是跟下文中说的类似
Hansotia和Rukstals表述了uplift模型的细节。他们描述了两种想法，一种是基于逻辑回归，另外一种是基于决策树。在树的部分描述了两种方案，第一种是分别在实验组和对照组进行建树，用交叉验证的方式提高准确性。第二种方法跟本文相似，建立一个树，直接训练实验组和对照组的相应差异。
这个算法使用的分裂方法，这种方法是最大话左右子树中实验组与对照组的差异。假设我假设有一个数据test A有两种输出结果和。则这个分表标准如下：

这里是选择的类（这里是二分类的情况）。这个分裂标准直接以期望差异最大化为技术，然而我们的研究是以更现代化的信息论为准则的。我们在实验组也证明了我们的研究有更好的效果。此外只能适合二叉树和二分类问题，我们的研究适合多分裂和多分裂问题。
在文献4中，作者提出了一种用于uplift模型的决策树建立方式。树的建立结束是以叶子节点都是实验组或者都是对照组为标志。另外，该算法是标准决策树构造过程。文献12中采用了基于两个单独贝叶斯分类器分方式进行逻辑回归。
这个问题在医学界更为普遍，实验组和对照组也更为也是如此。有几种基于线性分析的方法来评估实验组和对照组的差异。一个例子是文献中13-15中提出的嵌套均值回归模型。相关的文献参考16，这些提出方法与本文的方法是不同的，因为这些方法讨论的是如何在有混杂因素的情况下找到判定treatment的有效性，而本文的目标是直接找到效果最好的子数据组（人群）。此外这些文献中只使用线性模型，处理的问题也是回归而不是分类问题。
在文献17中，作者设置了一个强大的目标，即建立各种广告渠道对顾客长期的影响。而我们的工作可以认为是这个中的其中一部分，只研究其中一个action。
在文献18、19中action规则是选择一个特定的action来实现一个特定的目标。这与我们的方法不同，因为我们是目标是在特定action下哪些人群会产生预期的效果。
关于的模型评估会在低第四部分。

三、分裂准则

决策树算法的一个关键部分是对非叶子节点的特征选择问题。接下来我们提出两种分裂准则。
我们现在描述一个分裂标准要满足的几个假设，稍后我们将证明我们的分裂标准是满足这几个假设的

1. 当且仅当实验组和对照组的数据分布一致时，分裂准则的值应该是最小的。更准确说的这种情况发生在情况下。
2. 如果在实验组和对照组中特征A与Y独立，那分裂准则的值应该为0
3. 如果对照组数据为空时，这个分裂准则应该退化为传统的决策树分裂准则

假设1的目的是我们希望是在实验组和对照组上类别分布差异尽可能的最大化。假设2是说，如果一个特征与Y是独立的，那这个特征不应该用到分裂上。不过，在本文的例子中可能并不是很完美 ，事实上，分裂后的实验组和对照的数据分布可能比分裂前更加相似，因此分裂值也可以是负数。在后续的定理3.2中我们会进一步说明这个问题 。

A. 基于分布差异的分裂标准

由于我们想最大化实验组和对照组的分布差异，所以很自然的想到我们的分裂标准也是基于分布差异的。分布差异是指衡量两种概率分布的差异程度。我们只要求两个离散分布的差异是非负的，当且仅当两个分布一致时值为0。
我们这里使用两种分布差异衡量方式：KL散度和欧氏距离。两个数据分布 和的差异可以表示为
,
.
KL散度和欧式距离都是比较常用的方法。这里欧式距离还有一些好优点。第一，它是对称的，当对照组存在时，这会对树的建立有影响。但是，这里我们发现kl散度的不对称性在这里也不是一个问题，因为对照组的数据只是实验组的一个比较基础（就是只会用实验组比对照组如何如何，而不是对照组比实验组如何如。这里我认为是对多treatment，无对照组时，会产生影响，例如在训练过程使用数值和 建立树的结果是不相同 的）。第二，欧式距离的衡量标准更稳定，因为在KL散度中如果值趋于0时，会造成最终的数字很大。
对于一个test A（可以理解为一个特征）下分裂标准可以表示为：
,
这里是条件差异。就是。
这个公司定义的动机是：我们想要建立一个树，使得实验组和对照组的分布尽可能的不同。公式中第一部分选择一个特征，计算这个特征下的树的分支中分布差异值，我们减去在父节点的分布差异值，从而获得由于分裂A带来的增益。这点类似于与决策树中的信息增益和基尼系数。注意到，当对照组数据为空时，就退化为信息增益，就退化为Gini增益。
现在关键的问题是对条件散度（条件差异）的定义。这是因为test Ａ下的数据分布情况可能在实验组和对照组存在不同(例如性别特征，在实验组中男:女=1:4 ，可能在对照组男:女=5:1，这样影响了数值计算)。这里我们定义如下：

这里，样本量越多其影响就会越大。
下面的定理表明我们的分裂准备满足我们的假设。
定理3.1 和特征选择方式都是服从假设1-3的。此外，如果对照组为空时，退化为信息增益，当实验组或者对照组为空时，退化为基尼增益。
只满足2个假设。
注意到和可能是负数，分裂一个节点时，可能会导致分裂后的节点中更加相似，这就是辛普森悖论。 然而，通常是划分实验组和对照组数据时，确保是独立于数据的特征的（就是划分实验组和对照组时完全随机的）。
定理3.2 如果testA独立于实验组和对照组的分配，即 ,则和是非负的

B.正则化：对实验组和对照组中的大数据量的test分裂和不平衡进行校正

为了防止对某一类数据量过大而造成模型的预测偏差，标准决策树是将信息增益值除以信息值(就是C4.5)，在我们的场景下正则化会更复杂。
此外，我们要对某个特性下分裂造成的实验组和对照组比例失调进行惩罚，这种分裂就违背了随机分配的原则。

（换句话说就是，没有分裂前实验组和对照组的样本分配是随机的，但是在某一次分裂后，就可能造成一些特征更倾向于实验组或者对照组的其中一个。假如分裂前，实验组和对照组中的男：女为1:1，使用年龄作为分裂特征后，就会使得这个性别比例失调，如果此时直接用计算性别增益就会造成偏差）。

极端的情况下，某一次特征分裂后就会造成将所有的实验组数据分到一个子节点中，将所有对照组数据分到另外一个节点中。
正则化公式为：
标准:

标准：

这里 就是计算这、两个数的熵 ,也是类似情况。

公式中的第一项负责惩罚不平衡的分裂。严重依赖于组分配的特征将会更大的惩罚（就是A下的实验组和对照组越失调，惩罚越大）。注意的值可能接近无穷大。然而，只有当实验组和对照组的中的数据充足时惩罚才有意义。当实验组和对照组的数据比例严重失调时，第一项的数值就接近于0了。
公司中的第二项和第三项是惩罚了具有大量数据的结果，使用熵或者gini衡量这个。
这里我们发现一个问题，尽管当信息增益比较小时，如果正则化系数比较叫，那么最终这个特征也可能获得更高的优先分裂的权利。当在正则化时，加上就会得到一个更好的结果。
在考虑正则化后，我们最终的分裂标准如下

C.树的应用

一旦树建立好之后，叶子节点包含实验组和对照组的数据分布。我们对每一个叶子标注了预期的利润，这里我们就可以根据叶子节点来进行对一个样本的预测了。
每一个具有一个利润,这里针对实验组我们设置一个固定的成本。和表示的是在叶子节点上的数据情况。如果一个对象在叶子节点中是被施加了action，那么期望收益问。如果一个对象在叶子节点没有被施加action，那么期望收益为。所以在叶子节点中如果施加了action的收益为：

只有当这个数值大于0时，我们才会对这个对象施加action。

D.剪枝

决策树的剪枝是对模型的泛化能力有决定性的作用。这里我们采用了最简单但有效的方法，其基础就是利用单独的验证集。对于分类问题，通过徐连接在树建立完成后，从低向上检查使用用叶子节点替换子树（后剪枝操作），但是这种方法在uplift上是无效的，因为从叶子节点获取的总期望收益和在子树的根节点上获得的利润相同。
因此，我们这里实行另外一个改进的方法，即“最大化类型概率差”，它可以认为是对uplift案例的分类精度的概况。这个想法是观察实验组和对照组概率在叶子节点和根节点的差别，总的来说，如果叶子节点的差异不大于根节点的差异，则进行修剪。在每一个节点中，我们只看在训练集中差异最大的类别，并记住差异的符号（正负号），之后只有当训练集和验证集中符号相同时才有助于提高模型的准确性。
更准确的讲，在训练集上简历树时，对于每个节点t，我们记录使得值最大类别 ,还要记住这个值的符号（正负号）。在剪枝阶段时，假设我们在检查一个跟节点和它的叶子节点。我们记录下来和,并在验证集上计算：
,

这里表示的是验证集中落入叶子的样本数量（包括实验组和对照组），第一个公式表示的是未剪枝下的最大类别概率差，第二个公式表示的如果剪枝后的最大化类别概率差。当时进行剪枝操作。

四、实验评估

这里我们对比了四种模型（DoubleTree、 、、）。为了使得 可做比较，我们这边进行对其修改：

其中、是A的结果值（就是特征A的不同取值）

A.uplift评估方式

在传统的分裂模型中，会预先留出一些数据，用来评估模型的效果。但是方法不能直接应用在uplift上，现在我们有两种数据集：treatment 和contral数据。使用模型可以对实验组的数据进行打分，这个分数可以用来计算收益和绘制提升曲线。然而，要考虑到增加的收益，我们需要考虑对照组的数据行为。但这不是一个容易的事，因为在实验组中没有记录这个人对应的对照组的数据（一个人也不可能同时受到teatment和contral）。
为了选择出对应的对照数据，我们需要对对照组也用相同的模型进行打分。按预测值排序排序中取p分位数的人施加action获取的利润可以通过实验组中p分位数的利润值减去对照总p分位数的利润。这种方法并不是最理想的，因为你无法保证在两个数据集中相同的分位数中的人具有一样的特征。但是这种方法实践效果中比较有效。
注意，当实验组和对照组的数据不同时，应该通过加权计算对照组的利润，以弥补差异。
从相同的角度来看，就是用相同的模型对实验组和对照组预测，绘制两条单独的lift曲线，然后减去对照组的曲线，这就是uplift curve。为了方便比较数值，我们计算uplift curve曲线下的面积 ，这里就是的定义。

B.数据准备

C.实验结果

uplife的效果图片

五、总结

这篇文章一种uplift的决策树构造方法。为此设计了两种树的分裂方法和一种剪枝方式。并通过实验证明方法的优越性。

这篇文章是uplift树模型中比较老的一篇，文中详细介绍了树在构造中如何节点分裂，如果解决实验组和对照组的样本比例不平衡问题（正则化的方法），已经如何利用验证集进行剪枝操作。