TalkingData基于Spark的数据挖掘工作

TalkingData基于Spark的

数据挖掘工作张夏天腾云天下科技@张夏天_机器学习内容TalkingData简介我们的数据挖掘工作应用广告优化随机决策树算法及其Spark实现TalkingData简介TalkingData移动大数据生态圈行业透视DMP数据管理平台数据交易与交换数据监测与预警根底数据效劳数据能力开放企业效劳内容TalkingData简介我们的数据挖掘工作应用广告优化随机决策树算法及其Spark实现数据挖掘在TalkingData的应用移动应用推荐广告优化用户画像游戏数据挖掘外包咨询通用推荐同步推机锋开放：移动应用通用效劳接口CTR:提升20%-50%转化率:提升50%-100%转化本钱:降低50%人口属性移动应用兴趣标签行业兴趣标签位置信息付费预测流失预测为什么选择Spark硬件资源有限人力资源有限任务繁重为什么没有广泛使用MLLib内存资源有限，很多情况下无法把数据放入内存处理，因此迭代算法效率还是很低迭代依然是阿格硫斯之蹱我们只能尽可能使用需要迭代次数少，甚至不迭代的算法和算法实现RDTOneIteration

LRSimHash内容TalkingData简介我们的数据挖掘工作应用广告优化随机决策树算法及其Spark实现应用广告优化针对某一应用，筛选推广目标人群如何做广告优化分类问题

预测每个设备对目标应用的感兴趣程度算法

随机决策树

一次迭代LRRDT算法简介随机决策树算法〔RandomDecsionTrees〕[Fanetal,2003] 融合多棵随机构建的决策树的预测结果，来进行分类/回归特点 树的构建完全随机，不寻找最优分裂点和分裂值 建树的开销低 建树的过程不需要使用label信息应用 分类，多标签分类，回归 单机开源实现：RDT的简单例子P’(+|x)=30/50=0.6P(+|x)=30/100=0.3(P(+|x)+P’(+|x))/2=0.45F3>0.3F2<0.6F1>0.7+:100-:120+:30-:20YYNNN……F1<0.5F2>0.7F3>0.3+:200-:10+:30-:70YYNNN……两种构建随机决策树的方式方式1：

方式2：

优点：随时剪枝缺点：需要迭代优点：不需要迭代缺点：空树占用内存很大，限制了树的深度与决策树和随机决策森林的区别决策树随机决策森林随机决策树融合算法否是是随机程度无随机部分随机完全随机建树过程是否使用label信息使用使用不使用算法复杂度中高低计算复杂度1.与训练样本数量线性相关2.与所有feature的可取值数量平方相关与训练样本数量线性相关与feature子空间里的feature可取值数量平方相关与树的数量线性相关1.与训练样本数量线性相关2.与树的数量线性相关是否需要迭代需要需要依赖于采用哪种实现为什么RDT有学习能力直观解释 [Fanetal.,2003]贝叶斯最优分类器解释 [Fanetal.,2005;DavidsonandFan,2006]矩解释〔高阶统计〕 [Dhurandhar2010]Multi-labelRDT算法

[Zhangetal,2010]Multi-label学习问题TreeLakeIceWinterParkL1L2L3L1L1L2L3L3L1L2L3L4ClassifierL1+L2+L3+L1-L2-L3-Classifier1Classifier2Classifier3BinaryRelevanceLabelPowersetMulti-labelRDT算法F1<0.5F2>0.7F3>0.3YYNNN……L1+:30L1-:70L2+:50L2-:50L1+:200L1-:10L2+:40L2-:60F3>0.5F2<0.7F1>0.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.35RDT算法在Spark上实现的问题两种方式都存在比较大的缺点 方式1：需要屡次迭代 方式2：空树占用过多内存，限制树的深度方式3：不显示构建树结构的随机决策树，仅在样本走到某个节点时，动态确定当前的节点的feature.优点：无需迭代数据，内存占用小

如何实现不构建树的随机决策树算法一个伪随机数种子就可以确定一棵随机决策树理论上：我们仅需要一个伪随机数种子，我们就可以计算出这棵树任何一个节点上的feature实践中：使用伪随机数发生器效率比较低，我们采用Hash函数二叉随机决策树的实现二叉树仅针对binary数据，每个节点只需要确定feature可以通过公式推算父节点，左右子节点的编号01237849105111261314. . . . . . . . . . .父节点：(p-1)/2(奇数)，(p-2)/2〔偶数〕左子节点：2*p+1右子节点：2*p+2Spark实现—确定节点feature用Hash函数来确定每个节点的feature f=hash(p+s)modM其中，p是节点编码，s是当前树的种子，M是feature数,hash函数是整数hash函数。如果在一条路径下重复出现了一个feature,那么按如下逻辑处理： while(pathcontains(f))f=(f+1)modMendwhile样本在树上行走的过程f0f1f2f3f4f5f6f710100101Hash(0+s)mod8=4Hash(2+s)mod8=0Hash(5+s)mod8=0(0+1)mod8=12:f05:f05:f121345600:f4f4f0f0Conflict!f1随机决策树Spark实现Map……DataDataData…Data…S1S4S2S3Reduce与MLLib算法的比较数据〔对RDT算法，用SimHash转成512维binary数据〕：Data#Feature#Train#TestTrain.Vol.epsilon2,000400,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,000327M与MLLib算法的比较RDT:

深度:30

树棵数：50Spark配置:excutors:12worker:1driver-mem:2Gexecutor-mem:2G

MLLib(1.0)算法：

迭代：10次

LogsiticRegression SVM DecisionTreeSpark配置:excutors:12worker:1driver-mem:2-6Gexecutor-mem:2-8G与MLLib算法的比较DataRDTLRSVMDTAUCTrainingTime(s)AUCTrainingTime(s)AUCTrainingTime(s)AUCTrainingTime(s)epsilon.718341.757958.666079.74833990kdda.6542436.59061276.60201557--kddb.6437842.60132187.60012638