Decision trees for uplift modeling 論文筆記

摘要

什么是uplift模型

大多數(shù)分類的目的是在給定的數(shù)據(jù)集基礎(chǔ)上獲取到一個(gè)更高的準(zhǔn)確率又官。然而，在更多的實(shí)際案例中，（是否郵寄或者治療病人時(shí)是以預(yù)測(cè)類別進(jìn)行選擇的），我們不應(yīng)該以他們的類別而進(jìn)行建模凛膏，而是應(yīng)該由我們的action行為帶來(lái)的變化概率進(jìn)行建模嗡午。之后應(yīng)該對(duì)最有利潤(rùn)的對(duì)象執(zhí)行action。這個(gè)問(wèn)題就是 $\color{red}{Uplift模型}$ 德崭、不同相應(yīng)分析、真正提升模型揖盘。在這篇文章我們針對(duì)這種問(wèn)題推出基于樹(shù)分類器眉厨。這里我們?cè)O(shè)計(jì)了心的分裂標(biāo)準(zhǔn)和剪枝方法。實(shí)驗(yàn)結(jié)果也證明了我們方法的有效性扣讼，證明了我們的方法比現(xiàn)在的uplift模型技術(shù)的更好的效果缺猛。

一、介紹和符號(hào)說(shuō)明

在大多涉及到分類的問(wèn)題中椭符，建模的目的是讓我們選擇部分顧客進(jìn)行執(zhí)行一些action動(dòng)作荔燎。一個(gè)典型的例子就是經(jīng)過(guò)一個(gè)小的實(shí)驗(yàn)后訓(xùn)練一個(gè)模型，去預(yù)測(cè)哪些客戶會(huì)在營(yíng)銷活動(dòng)結(jié)束后去購(gòu)買销钝。然后根據(jù)預(yù)測(cè)結(jié)果找到最有可能購(gòu)買的用戶有咨。然而，這個(gè)可能不是營(yíng)銷人員想要的結(jié)果蒸健，他們想要的人群是那些因?yàn)樗麄兊氖┘拥臓I(yíng)銷活動(dòng)才去購(gòu)買的人座享。

說(shuō)白了就是要減少不必要的營(yíng)銷活動(dòng)帶來(lái)的損失

這兩個(gè)目標(biāo)顯然是不對(duì)等的，某些消費(fèi)者即使沒(méi)有收到營(yíng)銷活動(dòng)他們都會(huì)去購(gòu)買的似忧。對(duì)他們執(zhí)行營(yíng)銷活動(dòng)就會(huì)造成額外的成本渣叛，更壞的情況下，過(guò)度的營(yíng)銷活動(dòng)會(huì)是得消費(fèi)者厭煩盯捌，從而影響了他們?cè)谖磥?lái)購(gòu)買的概率淳衙。事實(shí)上，在廣告屆眾所周知的是廣告營(yíng)銷活動(dòng)的確會(huì)使得一些顧客厭煩饺著，但是他們又無(wú)法識(shí)別出這些顧客箫攀。
相同的問(wèn)題在醫(yī)學(xué)界更加頻繁。在一個(gè)臨床試驗(yàn)中幼衰，隨機(jī)劃分病人靴跛，一組接受A治療，另外一組接受B或者不治療渡嚣。然后統(tǒng)計(jì)兩個(gè)組全部整體的效果差異梢睛。然而肥印，如果A只對(duì)一部分人有效（具有遺傳特性的一些人）對(duì)其他人無(wú)效，在實(shí)際中這種效果可能不會(huì)被發(fā)現(xiàn)绝葡。在某些情況下竖独，分析是在幾個(gè)子數(shù)據(jù)組中單獨(dú)進(jìn)行的，但是沒(méi)有系統(tǒng)的方法自動(dòng)檢測(cè)這些子組或者直接建立相應(yīng)差異的模型挤牛。
盡管這個(gè)問(wèn)題普遍存在且十分重要，但是這個(gè)問(wèn)題在文獻(xiàn)還是受到很少的關(guān)注种蘸，這個(gè)叫uplift模型墓赴、不同響應(yīng)模型、增量值模型或者真正提升模型航瞭。隨機(jī)選擇一部分人施加action然后進(jìn)行分析（醫(yī)學(xué)實(shí)驗(yàn)或者市場(chǎng)營(yíng)銷）诫硕，這樣的樣本稱為treatment 數(shù)據(jù)（實(shí)驗(yàn)組數(shù)據(jù)）。同時(shí)隨機(jī)選擇與treatment組不相交的一部分人不施加任何action刊侯，這部分樣本稱為control數(shù)據(jù)（對(duì)照組數(shù)據(jù)）章办，作為施加action評(píng)估結(jié)果的背景。現(xiàn)在的任務(wù)建立一個(gè)模型去預(yù)測(cè)treatment和control數(shù)據(jù)集的概率差異滨彻，而不是預(yù)測(cè)屬于某一類（例如購(gòu)買或者治好病人）的概率藕届。
如果treatment組的數(shù)據(jù)選擇是完全隨機(jī)的，這樣模型還有另外一個(gè)優(yōu)點(diǎn)：模型的效果（treatment和control的差異）是由施加的action導(dǎo)致的亭饵。樣本經(jīng)常受其他的活動(dòng)營(yíng)銷（例如競(jìng)爭(zhēng)對(duì)手的市場(chǎng)活動(dòng)）休偶，這些影響不能被直接考慮進(jìn)去。通過(guò)隨機(jī)選擇treatment和control組的數(shù)據(jù)辜羊，我們可以自動(dòng)剔除這些影響踏兜，因?yàn)檫@些影響對(duì)treatment和control作用是相等的。
盡管決策樹(shù)不在是一個(gè)熱門的研究領(lǐng)取八秃，但他仍然活躍在工業(yè)領(lǐng)域（包括所有的商業(yè)分析產(chǎn)品）碱妆，而且作為歷史上最先采用的機(jī)器學(xué)習(xí)方法，它也是uplift模型的技術(shù)首要候選昔驱。
現(xiàn)在我們描述本文的貢獻(xiàn)疹尾。雖然在歷史文獻(xiàn)中已經(jīng)描述了uplift決策樹(shù)，但是他們都是十分基礎(chǔ)舍悯，簡(jiǎn)單的使用樣本分裂標(biāo)準(zhǔn)（直接最大化樣本差異）航棱。此外，沒(méi)有特殊的剪枝方式被描述萌衬。我們提出的uplift模型是基于信息論的饮醇，不像之前的方法，它只能允許二分類問(wèn)題和二叉分裂秕豫，我們的算法可以處理多分類和多分裂朴艰。
此外观蓄，所有提出的方法都是經(jīng)過(guò)精心設(shè)計(jì)的，因此他們?cè)诜诸悊?wèn)題使用的標(biāo)準(zhǔn)分類樹(shù)的直接概況祠墅，這里我們特別指出CART和C4.5侮穿。也就是說(shuō)，當(dāng)對(duì)照組為空時(shí)毁嗦，本文的方法退化為普通的決策樹(shù)亲茅。這種方法有2個(gè)優(yōu)點(diǎn)：第一，當(dāng)沒(méi)有對(duì)照組數(shù)據(jù)時(shí)（這種經(jīng)常經(jīng)常發(fā)生在樹(shù)的層級(jí)較低時(shí)）狗准，盡管我們無(wú)法對(duì)uplift建模克锣，我們還是可以嘗試分類建模的。第二腔长，作為一個(gè)特例袭祟，這些方法被簡(jiǎn)化為眾所周知的、合理和經(jīng)過(guò)充分研究的方法捞附，這個(gè)事實(shí)正事了它背后的直覺(jué)和使用的設(shè)計(jì)原則巾乳。

符號(hào)

現(xiàn)在介紹一下本文使用的符號(hào)胚泌，這里與傳統(tǒng)模型不同的是我們現(xiàn)在有兩種數(shù)據(jù)集：treatment 和control悲关。雙數(shù)據(jù)集需要一個(gè)特殊的符號(hào)表示。
我們把決策樹(shù)的非葉子節(jié)點(diǎn)稱之為tests颜屠。一個(gè)test含有有限個(gè)輸出結(jié)果欧募。我們?yōu)槊恳粋€(gè)類別創(chuàng)建一個(gè)test辑舷，test的結(jié)果就是所有樣本的結(jié)果，這點(diǎn)類似于C4.5槽片。對(duì)于每個(gè)數(shù)值屬性X我們創(chuàng)建根據(jù)X<v（v是一個(gè)具體的數(shù)）劃分為多個(gè)test何缓。為每一個(gè)v創(chuàng)建一個(gè)test，v是數(shù)據(jù)中存在的屬性X的兩個(gè)連續(xù)不同值的中點(diǎn)（說(shuō)白了就是將屬性X進(jìn)行分段處理）还栓。更細(xì)講的參考決策樹(shù)的文檔碌廓。
Tests可以用符號(hào)大寫A表示（A表示具有一些屬性的樣本）。不同的類別用Y表示剩盒。Y是離散值谷婆。a表A的一個(gè)結(jié)果，y表示Y的一個(gè)結(jié)果辽聊。 $\sum_{a}$ 表示的是A的所有結(jié)果纪挎。 $\sum_{y}$ 表示的是所有類別的結(jié)果。
基于實(shí)驗(yàn)組數(shù)據(jù)的概率估計(jì)用 $P^T$ 跟匆，基于對(duì)照組的數(shù)據(jù)的概率估計(jì)用 $P^C$ 表示异袄。 $P^T(Y)$ 表示的是基于實(shí)驗(yàn)組數(shù)據(jù)的Y的概率分布情況， $P^T(y)$ 表示的當(dāng) $Y=y$ 時(shí)實(shí)驗(yàn)組的概率數(shù)據(jù)玛臂，在對(duì)照組也是類似表示烤蜕。條件概率表示也是往常的形式封孙， $P^C(Y|a)$ 表示的是在實(shí)驗(yàn)組當(dāng) $A=a$ 時(shí)的Y的分布情況。
在計(jì)算 $P^T$ 和 $P^C$ 時(shí)我們用到了拉普拉斯修正

拉普拉斯修正: 原始的條件概率計(jì)算公式為 $P(x_i|c)=\frac{D_{c,x_i}}{D_c}$ 讽营，被修正后的是 $P(x_i|c)=\frac{D_{c,x_i}}{D_c+N_i}$

此外 $N^T$ 和 $N^C$ 分表表示的是實(shí)驗(yàn)組和對(duì)照組的樣本數(shù)據(jù)虎忌。 $N^T(a)$ 和 $N^C(a)$ 分別表示的是當(dāng) $A=a$ 時(shí)的數(shù)據(jù)量。最后我們令 $N=N^T+N^C$ 橱鹏， $N(a)=N^T(a)+N^C(a)$

二膜蠢、相關(guān)工作

盡管uplite模型相比之前最近受到了更高的關(guān)注，但是在文獻(xiàn)中只是模糊的說(shuō)明了一下算法莉兰，細(xì)節(jié)部分被忽略了狡蝶。下面我們介紹一下相關(guān)的研究論文。
uplift模型主要有兩種方法贮勃。最顯然的方法是建立兩個(gè)模型（two-model），一個(gè)模型訓(xùn)練treatment 苏章，另外一個(gè)模型訓(xùn)練control數(shù)據(jù)寂嘉。使用時(shí)我們將兩個(gè)模型的預(yù)測(cè)值進(jìn)行相減作為最終的結(jié)果。這里有個(gè)主要的缺點(diǎn)：我們想要的概率預(yù)測(cè)值可能與單獨(dú)每一個(gè)模型差異很大（我們想要預(yù)測(cè)是實(shí)驗(yàn)組和對(duì)照組的差異枫绅，而模型訓(xùn)練目標(biāo)只是各自的數(shù)據(jù)組內(nèi)把正負(fù)樣本分開(kāi)泉孩，并不能學(xué)到兩種組的差異情況）。在決策樹(shù)的情況下并淋，它并不一定有利于因?yàn)閍ction而導(dǎo)致的實(shí)驗(yàn)組和對(duì)照組的相應(yīng)差別分裂寓搬，而是在實(shí)驗(yàn)組和對(duì)照組各自的組內(nèi)預(yù)把預(yù)測(cè)結(jié)果分開(kāi)。
第二種方法就是訓(xùn)練一個(gè)模型县耽，試圖直接為實(shí)驗(yàn)組和對(duì)照組的差異進(jìn)行建模句喷。在文獻(xiàn)中一種決策樹(shù)的變種形式被提出，它是根據(jù)利用樹(shù)的節(jié)點(diǎn)中全部實(shí)驗(yàn)組的結(jié)果與全部對(duì)照住的結(jié)果差異進(jìn)行分裂的兔毙，就是跟下文中說(shuō)的 $\Delta\Delta P$ 類似
Hansotia和Rukstals表述了uplift模型的細(xì)節(jié)唾琼。他們描述了兩種想法，一種是基于邏輯回歸澎剥，另外一種是基于決策樹(shù)锡溯。在樹(shù)的部分描述了兩種方案，第一種是分別在實(shí)驗(yàn)組和對(duì)照組進(jìn)行建樹(shù)哑姚，用交叉驗(yàn)證的方式提高準(zhǔn)確性祭饭。第二種方法跟本文相似，建立一個(gè)樹(shù)叙量，直接訓(xùn)練實(shí)驗(yàn)組和對(duì)照組的相應(yīng)差異倡蝙。
這個(gè)算法使用的 $\Delta\Delta P$ 分裂方法，這種方法是最大話左右子樹(shù)中實(shí)驗(yàn)組與對(duì)照組的差異绞佩。假設(shè)我假設(shè)有一個(gè)數(shù)據(jù)test A有兩種輸出結(jié)果 $a_0$ 和 $a_1$ 悠咱。則這個(gè)分表標(biāo)準(zhǔn)如下：
$\Delta\Delta P(A)= | (P^T(y_0|a_0)-P^C(y_0|a_0) ) - (P^T(y_0|a_1)-P^C(y_0|a_a))|$
這里 $y_0$ 是選擇的類（這里是二分類的情況）蒸辆。這個(gè)分裂標(biāo)準(zhǔn)直接以期望差異最大化為技術(shù)，然而我們的研究是以更現(xiàn)代化的信息論為準(zhǔn)則的析既。我們?cè)趯?shí)驗(yàn)組也證明了我們的研究有更好的效果躬贡。此外 $\Delta\Delta P$ 只能適合二叉樹(shù)和二分類問(wèn)題，我們的研究適合多分裂和多分裂問(wèn)題眼坏。
在文獻(xiàn)4中拂玻，作者提出了一種用于uplift模型的決策樹(shù)建立方式。樹(shù)的建立結(jié)束是以葉子節(jié)點(diǎn)都是實(shí)驗(yàn)組或者都是對(duì)照組為標(biāo)志宰译。另外檐蚜，該算法是標(biāo)準(zhǔn)決策樹(shù)構(gòu)造過(guò)程。文獻(xiàn)12中采用了基于兩個(gè)單獨(dú)貝葉斯分類器分方式進(jìn)行邏輯回歸沿侈。
這個(gè)問(wèn)題在醫(yī)學(xué)界更為普遍闯第，實(shí)驗(yàn)組和對(duì)照組也更為也是如此。有幾種基于線性分析的方法來(lái)評(píng)估實(shí)驗(yàn)組和對(duì)照組的差異缀拭。一個(gè)例子是文獻(xiàn)中13-15中提出的嵌套均值回歸模型咳短。相關(guān)的文獻(xiàn)參考16，這些提出方法與本文的方法是不同的蛛淋，因?yàn)檫@些方法討論的是如何在有混雜因素的情況下找到判定treatment的有效性咙好，而本文的目標(biāo)是直接找到效果最好的子數(shù)據(jù)組（人群）。此外這些文獻(xiàn)中只使用線性模型褐荷，處理的問(wèn)題也是回歸而不是分類問(wèn)題勾效。
在文獻(xiàn)17中，作者設(shè)置了一個(gè)強(qiáng)大的目標(biāo)叛甫，即建立各種廣告渠道對(duì)顧客長(zhǎng)期的影響层宫。而我們的工作可以認(rèn)為是這個(gè)中的其中一部分，只研究其中一個(gè)action其监。
在文獻(xiàn)18卒密、19中action規(guī)則是選擇一個(gè)特定的action來(lái)實(shí)現(xiàn)一個(gè)特定的目標(biāo)。這與我們的方法不同棠赛，因?yàn)槲覀兪悄繕?biāo)是在特定action下哪些人群會(huì)產(chǎn)生預(yù)期的效果哮奇。
關(guān)于的模型評(píng)估會(huì)在低第四部分。

三睛约、分裂準(zhǔn)則

決策樹(shù)算法的一個(gè)關(guān)鍵部分是對(duì)非葉子節(jié)點(diǎn)的特征選擇問(wèn)題鼎俘。接下來(lái)我們提出兩種分裂準(zhǔn)則。
我們現(xiàn)在描述一個(gè)分裂標(biāo)準(zhǔn)要滿足的幾個(gè)假設(shè)辩涝，稍后我們將證明我們的分裂標(biāo)準(zhǔn)是滿足這幾個(gè)假設(shè)的

當(dāng)且僅當(dāng)實(shí)驗(yàn)組和對(duì)照組的數(shù)據(jù)分布一致時(shí)贸伐，分裂準(zhǔn)則的值應(yīng)該是最小的。更準(zhǔn)確說(shuō)的這種情況發(fā)生在 $P^T(Y|a)=P^C(Y|a)$ 情況下怔揩。
如果在實(shí)驗(yàn)組和對(duì)照組中特征A與Y獨(dú)立捉邢，那分裂準(zhǔn)則的值應(yīng)該為0
如果對(duì)照組數(shù)據(jù)為空時(shí)脯丝，這個(gè)分裂準(zhǔn)則應(yīng)該退化為傳統(tǒng)的決策樹(shù)分裂準(zhǔn)則

假設(shè)1的目的是我們希望是在實(shí)驗(yàn)組和對(duì)照組上類別分布差異盡可能的最大化。假設(shè)2是說(shuō)伏伐，如果一個(gè)特征與Y是獨(dú)立的宠进，那這個(gè)特征不應(yīng)該用到分裂上。不過(guò)藐翎，在本文的例子中可能并不是很完美材蹬，事實(shí)上，分裂后的實(shí)驗(yàn)組和對(duì)照的數(shù)據(jù)分布可能比分裂前更加相似吝镣，因此分裂值也可以是負(fù)數(shù)堤器。在后續(xù)的定理3.2中我們會(huì)進(jìn)一步說(shuō)明這個(gè)問(wèn)題。

A. 基于分布差異的分裂標(biāo)準(zhǔn)

由于我們想最大化實(shí)驗(yàn)組和對(duì)照組的分布差異末贾，所以很自然的想到我們的分裂標(biāo)準(zhǔn)也是基于分布差異的闸溃。分布差異是指衡量?jī)煞N概率分布的差異程度。我們只要求兩個(gè)離散分布的差異是非負(fù)的拱撵，當(dāng)且僅當(dāng)兩個(gè)分布一致時(shí)值為0辉川。
我們這里使用兩種分布差異衡量方式：KL散度和歐氏距離。兩個(gè)數(shù)據(jù)分布 $Q=(q_1,....,q_n)$ 和 $P=(p_1,....p_n)$ 的差異可以表示為
$KL(P:Q)=\sum_i{p_ilog \frac{p_i}{q_i}}$ ,
$E(P:Q)=\sum_i{(p_i-q_i)^2}$ .
KL散度和歐式距離都是比較常用的方法裕膀。這里歐式距離還有一些好優(yōu)點(diǎn)。第一勇哗，它是對(duì)稱的昼扛，當(dāng)對(duì)照組存在時(shí)，這會(huì)對(duì)樹(shù)的建立有影響欲诺。但是抄谐，這里我們發(fā)現(xiàn)kl散度的不對(duì)稱性在這里也不是一個(gè)問(wèn)題，因?yàn)閷?duì)照組的數(shù)據(jù)只是實(shí)驗(yàn)組的一個(gè)比較基礎(chǔ)（就是只會(huì)用實(shí)驗(yàn)組比對(duì)照組如何如何扰法，而不是對(duì)照組比實(shí)驗(yàn)組如何如蛹含。這里我認(rèn)為是對(duì)多treatment，無(wú)對(duì)照組時(shí)塞颁，會(huì)產(chǎn)生影響浦箱，例如在訓(xùn)練過(guò)程使用 $KL(action1:action2)$ 數(shù)值和 $KL(action2:action1)$ 建立樹(shù)的結(jié)果是不相同的）。第二祠锣，歐式距離的衡量標(biāo)準(zhǔn)更穩(wěn)定酷窥，因?yàn)樵贙L散度中如果 $q_i$ 值趨于0時(shí)，會(huì)造成最終的數(shù)字很大伴网。
對(duì)于一個(gè)test A（可以理解為一個(gè)特征）下分裂標(biāo)準(zhǔn)可以表示為：
$D_{gain}(A)=D(P^T(Y):P^C(Y)|A)-D(P^T(Y):P^C(Y))$ ,
這里 $D(P^T(Y):P^C(Y)|A)$ 是條件差異蓬推。 $D$ 就是 $KL_{gain} 和E_{gain}$ 。
這個(gè)公司定義的動(dòng)機(jī)是：我們想要建立一個(gè)樹(shù)澡腾，使得實(shí)驗(yàn)組和對(duì)照組的分布盡可能的不同沸伏。公式中第一部分選擇一個(gè)特征糕珊，計(jì)算這個(gè)特征下的樹(shù)的分支中分布差異值，我們減去在父節(jié)點(diǎn)的分布差異值毅糟，從而獲得由于分裂A帶來(lái)的增益红选。這點(diǎn)類似于與決策樹(shù)中的信息增益和基尼系數(shù)。注意到留特，當(dāng)對(duì)照組數(shù)據(jù)為空時(shí)纠脾， $KL_{gain}$ 就退化為信息增益， $E_{gain}$ 就退化為Gini增益蜕青。
現(xiàn)在關(guān)鍵的問(wèn)題是對(duì)條件散度（條件差異）的定義苟蹈。這是因?yàn)閠est Ａ下的數(shù)據(jù)分布情況可能在實(shí)驗(yàn)組和對(duì)照組存在不同(例如性別特征，在實(shí)驗(yàn)組中男:女=1:4 右核，可能在對(duì)照組男:女=5:1慧脱，這樣影響了數(shù)值計(jì)算)。這里我們定義如下：
$D(P^T(Y):P^C(Y)|A) =\sum_a \frac{N(a)}{N}D(P^T(Y|a):P^C(Y|a)) \tag{1}$
這里贺喝，樣本量越多其影響就會(huì)越大菱鸥。
下面的定理表明我們的分裂準(zhǔn)備滿足我們的假設(shè)。
定理3.1 $KL_{gain}$ 和 $E_{gain}$ 特征選擇方式都是服從假設(shè)1-3的躏鱼。此外氮采，如果對(duì)照組為空時(shí)， $KL_{gain}$ 退化為信息增益染苛，當(dāng)實(shí)驗(yàn)組或者對(duì)照組為空時(shí)鹊漠， $E_{gain}$ 退化為基尼增益。
$\Delta \Delta P$ 只滿足2個(gè)假設(shè)茶行。
注意到 $KL_{gain}$ 和 $E_{gain}$ 可能是負(fù)數(shù)躯概，分裂一個(gè)節(jié)點(diǎn)時(shí)，可能會(huì)導(dǎo)致分裂后的節(jié)點(diǎn)中更加相似畔师，這就是辛普森悖論娶靡。然而，通常是劃分實(shí)驗(yàn)組和對(duì)照組數(shù)據(jù)時(shí)看锉，確保是獨(dú)立于數(shù)據(jù)的特征的（就是劃分實(shí)驗(yàn)組和對(duì)照組時(shí)完全隨機(jī)的）姿锭。
定理3.2 如果testA獨(dú)立于實(shí)驗(yàn)組和對(duì)照組的分配，即 $P^C(A)=P^T(A)$ ,則 $KL_{gain}$ 和 $E_{gain}$ 是非負(fù)的

B.正則化：對(duì)實(shí)驗(yàn)組和對(duì)照組中的大數(shù)據(jù)量的test分裂和不平衡進(jìn)行校正

為了防止對(duì)某一類數(shù)據(jù)量過(guò)大而造成模型的預(yù)測(cè)偏差伯铣，標(biāo)準(zhǔn)決策樹(shù)是將信息增益值除以信息值(就是C4.5)艾凯，在我們的場(chǎng)景下正則化會(huì)更復(fù)雜。
此外懂傀，我們要對(duì)某個(gè)特性下分裂造成的實(shí)驗(yàn)組和對(duì)照組比例失調(diào)進(jìn)行懲罰趾诗，這種分裂就違背了隨機(jī)分配的原則。

（換句話說(shuō)就是，沒(méi)有分裂前實(shí)驗(yàn)組和對(duì)照組的樣本分配是隨機(jī)的恃泪，但是在某一次分裂后郑兴，就可能造成一些特征更傾向于實(shí)驗(yàn)組或者對(duì)照組的其中一個(gè)。假如分裂前贝乎，實(shí)驗(yàn)組和對(duì)照組中的男：女為1:1情连，使用年齡作為分裂特征后，就會(huì)使得這個(gè)性別比例失調(diào)览效，如果此時(shí)直接用計(jì)算性別增益就會(huì)造成偏差）却舀。

極端的情況下，某一次特征分裂后就會(huì)造成將所有的實(shí)驗(yàn)組數(shù)據(jù)分到一個(gè)子節(jié)點(diǎn)中锤灿，將所有對(duì)照組數(shù)據(jù)分到另外一個(gè)節(jié)點(diǎn)中挽拔。
正則化公式為：
$KL_{gain}$ 標(biāo)準(zhǔn):
$I(A)=H(\frac{N^T}{N},\frac{N^C}{N})KL(P^T(A):P^C(A)) + \frac{N^T}{N}H(P^T(A)) + \frac{N^C}{N}H(P^C(A))+\frac{1}{2}$
$E_{gain}$ 標(biāo)準(zhǔn)：
$J(A)=Gini(\frac{N^T}{N},\frac{N^C}{N})E(P^T(A):P^C(A)) + \frac{N^T}{N}Gini(P^T(A)) + \frac{N^C}{N}Gini(P^C(A))+\frac{1}{2}$

這里 $H(\frac{N^T}{N},\frac{N^C}{N})$ 就是計(jì)算這 $\frac{N^T}{N}$ 、 $\frac{N^C}{N}$ 兩個(gè)數(shù)的熵 , $Gini(\frac{N^T}{N},\frac{N^C}{N})$ 也是類似情況但校。

公式中的第一項(xiàng)負(fù)責(zé)懲罰不平衡的分裂螃诅。嚴(yán)重依賴于組分配的特征將會(huì)更大的懲罰（就是A下的實(shí)驗(yàn)組和對(duì)照組越失調(diào)，懲罰越大）状囱。注意 $I(A)$ 的值可能接近無(wú)窮大术裸。然而，只有當(dāng)實(shí)驗(yàn)組和對(duì)照組的中的數(shù)據(jù)充足時(shí)懲罰才有意義亭枷。當(dāng)實(shí)驗(yàn)組和對(duì)照組的數(shù)據(jù)比例嚴(yán)重失調(diào)時(shí)袭艺，第一項(xiàng)的數(shù)值就接近于0了。
公司中的第二項(xiàng)和第三項(xiàng)是懲罰了具有大量數(shù)據(jù)的結(jié)果叨粘，使用熵或者gini衡量這個(gè)猾编。
這里我們發(fā)現(xiàn)一個(gè)問(wèn)題，盡管當(dāng)信息增益比較小時(shí)宣鄙，如果正則化系數(shù)比較叫袍镀，那么最終這個(gè)特征也可能獲得更高的優(yōu)先分裂的權(quán)利默蚌。當(dāng)在正則化時(shí)冻晤，加上 $\frac{1}{2}$ 就會(huì)得到一個(gè)更好的結(jié)果。
在考慮正則化后绸吸，我們最終的分裂標(biāo)準(zhǔn)如下
$\color{red}{ \frac{KL_{gain}(A)}{I(A)} ,\frac{E_{gain}(A)}{J(A)} }$

C.樹(shù)的應(yīng)用

一旦樹(shù)建立好之后鼻弧，葉子節(jié)點(diǎn)包含實(shí)驗(yàn)組和對(duì)照組的數(shù)據(jù)分布。我們對(duì)每一個(gè)葉子標(biāo)注了預(yù)期的利潤(rùn)锦茁，這里我們就可以根據(jù)葉子節(jié)點(diǎn)來(lái)進(jìn)行對(duì)一個(gè)樣本的預(yù)測(cè)了攘轩。
每一個(gè) $y$ 具有一個(gè)利潤(rùn) $v_y$ ,這里針對(duì)實(shí)驗(yàn)組我們?cè)O(shè)置一個(gè)固定的成本 $c$ 。 $P^T(Y|l)$ 和 $P^C(Y|l)$ 表示的是在葉子節(jié)點(diǎn) $l$ 上的數(shù)據(jù)情況码俩。如果一個(gè)對(duì)象在葉子節(jié)點(diǎn)中是被施加了action度帮，那么期望收益問(wèn) $-c+\sum_yP^T(y|l)v_y$ 。如果一個(gè)對(duì)象在葉子節(jié)點(diǎn)沒(méi)有被施加action，那么期望收益為 $\sum_yP^C(y|l)v_y$ 笨篷。所以在葉子節(jié)點(diǎn)中如果施加了action的收益為：
$-c+\sum_yv_y(P^T(y|l)-P^C(y|l)) \tag{2}$
只有當(dāng)這個(gè)數(shù)值大于0時(shí)瞳秽，我們才會(huì)對(duì)這個(gè)對(duì)象施加action。

D.剪枝

決策樹(shù)的剪枝是對(duì)模型的泛化能力有決定性的作用率翅。這里我們采用了最簡(jiǎn)單但有效的方法练俐，其基礎(chǔ)就是利用單獨(dú)的驗(yàn)證集。對(duì)于分類問(wèn)題冕臭，通過(guò)徐連接在樹(shù)建立完成后腺晾，從低向上檢查使用用葉子節(jié)點(diǎn)替換子樹(shù)（后剪枝操作），但是這種方法在uplift上是無(wú)效的辜贵，因?yàn)閺娜~子節(jié)點(diǎn)獲取的總期望收益和在子樹(shù)的根節(jié)點(diǎn)上獲得的利潤(rùn)相同悯蝉。
因此，我們這里實(shí)行另外一個(gè)改進(jìn)的方法念颈，即“最大化類型概率差”泉粉，它可以認(rèn)為是對(duì)uplift案例的分類精度的概況。這個(gè)想法是觀察實(shí)驗(yàn)組和對(duì)照組概率在葉子節(jié)點(diǎn)和根節(jié)點(diǎn)的差別榴芳，總的來(lái)說(shuō)嗡靡，如果葉子節(jié)點(diǎn)的差異不大于根節(jié)點(diǎn)的差異，則進(jìn)行修剪窟感。在每一個(gè)節(jié)點(diǎn)中讨彼，我們只看在訓(xùn)練集中差異最大的類別，并記住差異的符號(hào)（正負(fù)號(hào)）柿祈，之后只有當(dāng)訓(xùn)練集和驗(yàn)證集中符號(hào)相同時(shí)才有助于提高模型的準(zhǔn)確性哈误。
更準(zhǔn)確的講，在訓(xùn)練集上簡(jiǎn)歷樹(shù)時(shí)躏嚎，對(duì)于每個(gè)節(jié)點(diǎn)t蜜自，我們記錄使得 $|P^T(y^*|t)-P^C(y^*|t)|$ 值最大類別 $y^*$ ,還要記住這個(gè)值的符號(hào)（正負(fù)號(hào)） $s(t)=sgn(P^T(y^*|t)-P^C(y^*|t))$ 。在剪枝階段時(shí)卢佣，假設(shè)我們?cè)跈z查一個(gè)跟節(jié)點(diǎn) $r$ 和它的葉子節(jié)點(diǎn) $l_1,....,l_k$ 重荠。我們記錄下來(lái) $s$ 和 $y^*$ ,并在驗(yàn)證集上計(jì)算：
$d_1(r)= \sum_{i=1}^{k} \frac{N(l_i)}{N(r)}s(l_i)( P^T(y^*(l_i)|l_i) -P^C(y^*(l_i)|l_i) )$ ,
$d_2(r)=s(r)(P^T(y^*(r)|r) -P^C(y^*(r)|r) )$
這里 $N(l_i)$ 表示的是驗(yàn)證集中落入葉子 $l_i$ 的樣本數(shù)量（包括實(shí)驗(yàn)組和對(duì)照組），第一個(gè)公式表示的是未剪枝下的最大類別概率差虚茶，第二個(gè)公式表示的如果剪枝后的最大化類別概率差戈鲁。當(dāng) $d_1(r) \leq d_2(r)$ 時(shí)進(jìn)行剪枝操作。

四嘹叫、實(shí)驗(yàn)評(píng)估

這里我們對(duì)比了四種模型（DoubleTree婆殿、 $\Delta \Delta P$ 、 $E_{gain}$ 罩扇、 $KL_{gain}$ ）婆芦。為了使得 $\Delta \Delta P$ 可做比較，我們這邊進(jìn)行對(duì)其修改：
$\Delta \Delta P(A) = {max}_{a,a'}[(P^T(y_0|a) -P^C(y_0|a) ) -(P^T(y_0|a') -P^C(y_0|a') )]$
其中 $a$ 、 $a'$ 是A的結(jié)果值（就是特征A的不同取值）

A.uplift評(píng)估方式

在傳統(tǒng)的分裂模型中消约，會(huì)預(yù)先留出一些數(shù)據(jù)癌压，用來(lái)評(píng)估模型的效果。但是方法不能直接應(yīng)用在uplift上荆陆，現(xiàn)在我們有兩種數(shù)據(jù)集：treatment 和contral數(shù)據(jù)滩届。使用模型可以對(duì)實(shí)驗(yàn)組的數(shù)據(jù)進(jìn)行打分，這個(gè)分?jǐn)?shù)可以用來(lái)計(jì)算收益和繪制提升曲線被啼。然而帜消，要考慮到增加的收益，我們需要考慮對(duì)照組的數(shù)據(jù)行為浓体。但這不是一個(gè)容易的事泡挺，因?yàn)樵趯?shí)驗(yàn)組中沒(méi)有記錄這個(gè)人對(duì)應(yīng)的對(duì)照組的數(shù)據(jù)（一個(gè)人也不可能同時(shí)受到teatment和contral）。
為了選擇出對(duì)應(yīng)的對(duì)照數(shù)據(jù)命浴，我們需要對(duì)對(duì)照組也用相同的模型進(jìn)行打分娄猫。按預(yù)測(cè)值排序排序中取p分位數(shù)的人施加action獲取的利潤(rùn)可以通過(guò)實(shí)驗(yàn)組中p分位數(shù)的利潤(rùn)值減去對(duì)照總p分位數(shù)的利潤(rùn)。這種方法并不是最理想的生闲，因?yàn)槟銦o(wú)法保證在兩個(gè)數(shù)據(jù)集中相同的分位數(shù)中的人具有一樣的特征媳溺。但是這種方法實(shí)踐效果中比較有效。
注意碍讯，當(dāng)實(shí)驗(yàn)組和對(duì)照組的數(shù)據(jù)不同時(shí)悬蔽，應(yīng)該通過(guò)加權(quán)計(jì)算對(duì)照組的利潤(rùn)，以彌補(bǔ)差異捉兴。
從相同的角度來(lái)看蝎困，就是用相同的模型對(duì)實(shí)驗(yàn)組和對(duì)照組預(yù)測(cè)，繪制兩條單獨(dú)的lift曲線倍啥，然后減去對(duì)照組的曲線禾乘，這就是uplift curve。為了方便比較數(shù)值虽缕，我們計(jì)算uplift curve曲線下的面積始藕，這里就是 $\color{red}{areas\ under\ uplift\ curves(AUUC)}$ 的定義。

B.數(shù)據(jù)準(zhǔn)備

C.實(shí)驗(yàn)結(jié)果

uplife的效果圖片

五彼宠、總結(jié)

這篇文章一種uplift的決策樹(shù)構(gòu)造方法鳄虱。為此設(shè)計(jì)了兩種樹(shù)的分裂方法和一種剪枝方式弟塞。并通過(guò)實(shí)驗(yàn)證明方法的優(yōu)越性凭峡。

這篇文章是uplift樹(shù)模型中比較老的一篇，文中詳細(xì)介紹了樹(shù)在構(gòu)造中如何節(jié)點(diǎn)分裂决记，如果解決實(shí)驗(yàn)組和對(duì)照組的樣本比例不平衡問(wèn)題（正則化的方法）摧冀，已經(jīng)如何利用驗(yàn)證集進(jìn)行剪枝操作。

最后編輯于：2020.04.19 21:58:08

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

禁止轉(zhuǎn)載，如需轉(zhuǎn)載請(qǐng)通過(guò)簡(jiǎn)信或評(píng)論聯(lián)系作者索昂。

人面猴
序言：七十年代末建车，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子椒惨，更是在濱河造成了極大的恐慌缤至，老刑警劉巖，帶你破解...
沈念sama閱讀 211,376評(píng)論 6贊 491
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件康谆，死亡現(xiàn)場(chǎng)離奇詭異领斥，居然都是意外死亡，警方通過(guò)查閱死者的電腦和手機(jī)沃暗，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,126評(píng)論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門月洛，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人孽锥，你說(shuō)我怎么就攤上這事嚼黔。” “怎么了惜辑？”我有些...
開(kāi)封第一講書人閱讀 156,966評(píng)論 0贊 347
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵唬涧，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我盛撑，道長(zhǎng)爵卒，這世上最難降的妖魔是什么？我笑而不...
開(kāi)封第一講書人閱讀 56,432評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任撵彻，我火速辦了婚禮钓株，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘陌僵。我一直安慰自己轴合，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 65,519評(píng)論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布碗短。她就那樣靜靜地躺著受葛，像睡著了一般。火紅的嫁衣襯著肌膚如雪偎谁。梳的紋絲不亂的頭發(fā)上总滩，一...
開(kāi)封第一講書人閱讀 49,792評(píng)論 1贊 290
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音巡雨，去河邊找鬼闰渔。笑死，一個(gè)胖子當(dāng)著我的面吹牛铐望，可吹牛的內(nèi)容都是我干的冈涧。我是一名探鬼主播茂附，決...
沈念sama閱讀 38,933評(píng)論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼督弓！你這毒婦竟也來(lái)了营曼？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書人閱讀 37,701評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤愚隧，失蹤者是張志新（化名）和其女友劉穎蒂阱，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體狂塘，經(jīng)...
沈念sama閱讀 44,143評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡蒜危，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,488評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了睹耐。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片辐赞。...
茶點(diǎn)故事閱讀 38,626評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖硝训，靈堂內(nèi)的尸體忽然破棺而出响委，到底是詐尸還是另有隱情，我是刑警寧澤窖梁，帶...
沈念sama閱讀 34,292評(píng)論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布赘风，位于F島的核電站，受9級(jí)特大地震影響纵刘，放射性物質(zhì)發(fā)生泄漏邀窃。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,896評(píng)論 3贊 313
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一假哎、第九天我趴在偏房一處隱蔽的房頂上張望瞬捕。院中可真熱鬧，春花似錦舵抹、人聲如沸肪虎。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 30,742評(píng)論 0贊 21
一樁弒父案惧蛹，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)扇救。三九已至，卻和暖如春香嗓，著一層夾襖步出監(jiān)牢的瞬間迅腔，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書人閱讀 31,977評(píng)論 1贊 265
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工靠娱，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留沧烈，地道東北人。一個(gè)月前我還...
沈念sama閱讀 46,324評(píng)論 2贊 360
代替公主和親
正文我出身青樓饱岸，卻偏偏與公主長(zhǎng)得像掺出，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子苫费，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,494評(píng)論 2贊 348