TalkingData基于Spark的数据挖掘工作

1、Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights ReservedTalkingData基于基于Spark的的数据挖掘工作数据挖掘工作张夏天 腾云天下科技有限公司张夏天_机器学习Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved内容TalkingData简介我们的数据挖掘工作应用广告优化随机决策树算

2、法及其Spark实现Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights ReservedTalking Data简介TalkingData移动大数据生态圈行业透视DMP数据管理平台数据交易与交换数据监测与预警基础数据服务数据能力开放企业服务Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved内容Talk

3、ingData简介我们的数据挖掘工作应用广告优化随机决策树算法及其Spark实现Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved数据挖掘在TalkingData的应用移动应用推荐广告优化用户画像游戏数据挖掘外包咨询通用推荐同步推机锋开放：移动应用通用服务接口CTR: 提升20%-50%转化率: 提升50%-100%转化成本: 降低50%人口属性移动应用兴趣标签行业兴趣标签位置信息付费预测流失预测Copyright 2014 Talkin

4、gData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved为什么选择Spark硬件资源有限人力资源有限任务繁重Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved为什么没有广泛使用MLLib内存资源有限，很多情况下无法把数据放入内存处理，因此迭代算法效率还是很低迭代依然是阿格硫斯之蹱我们只能尽可能使用需要迭代次数少，甚至不迭代的算法和

5、算法实现RDTOne Iteration LRSimHashCopyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved内容TalkingData简介我们的数据挖掘工作应用广告优化随机决策树算法及其Spark实现Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved应用广告优化针对某一应用，筛选推

6、广目标人群Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved如何做广告优化分类问题预测每个设备对目标应用的感兴趣程度算法随机决策树一次迭代LRCopyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights ReservedRDT算法简介随机决策树算法（Random Decsion Trees）Fan et al,

7、 2003融合多棵随机构建的决策树的预测结果，来进行分类/回归特点树的构建完全随机，不寻找最优分裂点和分裂值 建树的开销低建树的过程不需要使用label信息应用分类，多标签分类，回归单机开源实现： Dice Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights ReservedRDT的简单例子P(+|x)=30/50 =0.6P(+|x)=30/100=0.3(P(+|x)+P(+|x)/2 = 0.45F30.3F20.7+:100 -:120+:30-:

8、 20YYNNN F10.7F30.3+:200 -: 10+:30-: 70YYNNN Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved两种构建随机决策树的方式方式1：方式2：优点：随时剪枝缺点：需要迭代优点：不需要迭代缺点：空树占用内存很大，限制了树的深度Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All R

9、ights Reserved与决策树和随机决策森林的区别决策树随机决策森林随机决策树融合算法否是是随机程度无随机部分随机完全随机建树过程是否使用label信息使用使用不使用算法复杂度中高低计算复杂度1. 与训练样本数量线性相关2. 与所有feature的可取值数量平方相关1. 与训练样本数量线性相关2. 与feature子空间里的feature可取值数量平方相关3. 与树的数量线性相关1.与训练样本数量线性相关2. 与树的数量线性相关是否需要迭代需要需要依赖于采用哪种实现Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright

10、2014 TalkingData Ltd., All Rights Reserved为什么RDT有学习能力直观解释 Fan et al., 2003贝叶斯最优分类器解释 Fan et al., 2005;Davidson and Fan, 2006矩解释（高阶统计）Dhurandhar 2010Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights ReservedMulti-label RDT算法 Zhang et al, 2010Multi-label 学

11、习问题TreeLakeIceWinterParkL1L2L3L1L1L2L3L3L1L2L3L4ClassifierL1+L2+L3+L1-L2-L3-Classifier1Classifier2Classifier3Binary RelevanceLabel PowersetCopyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights ReservedMulti-label RDT算法F10.7F30.3YYNNN L1+:30L1-: 70L2+:50L2-:

12、50L1+:200L1-: 10L2+:40L2-: 60F30.5F20.7YYNNN L1+:30L1-: 20L2+:20L2-: 80L1+:100L1-:120L1+:200L1-: 10P(L1+|x)=30/100=0.3P(L1+|x)=30/50 =0.6P(L2+|x)=50/100=0.5P(L2+|x)=20/100=0.2(P(L1+|x)+P(L1+|x)/2 = 0.45(P(L2+|x)+P(L2+|x)/2 = 0.35Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 Talk

13、ingData Ltd., All Rights ReservedRDT算法在Spark上实现的问题两种方式都存在比较大的缺点方式1： 需要多次迭代方式2： 空树占用过多内存，限制树的深度方式3： 不显示构建树结构的随机决策树，仅在样本走到某个节点时，动态确定当前的节点的feature. 优点：无需迭代数据，内存占用小Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved如何实现不构建树的随机决策树算法一个伪随机数种子就可以确定一棵随机决策树

14、理论上：我们仅需要一个伪随机数种子，我们就可以计算出这棵树任何一个节点上的feature实践中：使用伪随机数发生器效率比较低，我们采用Hash函数Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved二叉随机决策树的实现二叉树仅针对binary数据， 每个节点只需要确定feature可以通过公式推算父节点，左右子节点的编号01237849105111261314.父节点： (p-1)/2(奇数) ， (p-2)/2（偶数） 左子节点：2*p+

15、1右子节点：2*p+2Copyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights ReservedSpark实现确定节点feature用Hash函数来确定每个节点的featuref = hash(p+s) mod M其中，p是节点编码，s是当前树的种子，M是feature数, hash函数是整数hash函数。如果在一条路径下重复出现了一个feature, 则按如下逻辑处理：while(path contains(f) f = (f+1) mod M end whi

16、leCopyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved样本在树上行走的过程f0f1f2f3f4f5f6f710100101Hash(0+s) mod 8 = 4Hash(2+s) mod 8 = 0Hash(5+s) mod 8 = 0(0+1) mod 8 = 12:f05:f05:f121345600:f4f4f0f0Conflict !f1Copyright 2014 TalkingData Ltd., All Rights Res

17、ervedCopyright 2014 TalkingData Ltd., All Rights Reserved随机决策树Spark实现MapDataDataDataDataS1S4S2S3ReduceCopyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved与MLLib算法的比较数据（对RDT算法，用SimHash转成512维binary数据）：Data#Feature#Train#TestTrain.Vol.epsilon2,000400,

18、000100,00011.3Gkdda20,216,8308,407,752510,3022.49Gkddb29,890,09519,264,097748,4014.78Gurl3,231,9612,000,000396,130344Mwebspam_tri16,609,143300,00050,00020Gwebspam_uni254300,00050,000327MCopyright 2014 TalkingData Ltd., All Rights ReservedCopyright 2014 TalkingData Ltd., All Rights Reserved与MLLib算法的比较RDT:深度: 30 树棵数：50Spark配置:excutors: 12worker: 1driver-mem: 2Gexecutor-mem:2G MLLib(1.0)算法：迭代：10次Logsitic Regression SVMDecision TreeSpark配置:excutors: 12worker: 1driver-mem: 2-6Gexecutor-mem:2-8GCopyright 2014 TalkingData Ltd., All Righ