TalkingData基于Spark的数据挖掘工作PPT课件

TalkingData基于Spark的数据挖掘工作 张夏天腾云天下科技有限公司 张夏天 机器学习 内容 TalkingData简介我们的数据挖掘工作应用广告优化随机决策树算法及其Spark实现 2 TalkingData简介 TalkingData移动大数据生态圈 行业透视 DMP数据管理平台 数据交易与交换 数据监测与预警 基础数据服务 数据能力开放 企业服务 3 内容 TalkingData简介我们的数据挖掘工作应用广告优化随机决策树算法及其Spark实现 4 数据挖掘在TalkingData的应用 移动应用推荐 广告优化 用户画像 游戏数据挖掘 外包咨询 通用推荐 同步推 机锋 开放 移动应用通用服务接口 CTR 提升20 50 转化率 提升50 100 转化成本 降低50 人口属性 移动应用兴趣标签 行业兴趣标签 位置信息 付费预测 流失预测 5 为什么选择Spark 硬件资源有限 人力资源有限 任务繁重 6 为什么没有广泛使用MLLib 内存资源有限 很多情况下无法把数据放入内存处理 因此迭代算法效率还是很低迭代依然是阿格硫斯之蹱我们只能尽可能使用需要迭代次数少 甚至不迭代的算法和算法实现 RDT OneIterationLR SimHash 7 内容 TalkingData简介我们的数据挖掘工作应用广告优化随机决策树算法及其Spark实现 8 应用广告优化 针对某一应用 筛选推广目标人群 9 如何做广告优化 分类问题预测每个设备对目标应用的感兴趣程度算法随机决策树一次迭代LR 10 RDT算法简介 随机决策树算法 RandomDecsionTrees Fanetal 2003 融合多棵随机构建的决策树的预测结果 来进行分类 回归特点树的构建完全随机 不寻找最优分裂点和分裂值建树的开销低建树的过程不需要使用label信息应用分类 多标签分类 回归单机开源实现 D 11 RDT的简单例子 P x 30 50 0 6 P x 30 100 0 3 P x P x 2 0 45 12 两种构建随机决策树的方式 方式1 方式2 优点 随时剪枝缺点 需要迭代 优点 不需要迭代缺点 空树占用内存很大 限制了树的深度 13 与决策树和随机决策森林的区别 14 为什么RDT有学习能力 直观解释 Fanetal 2003 贝叶斯最优分类器解释 Fanetal 2005 DavidsonandFan 2006 矩解释 高阶统计 Dhurandhar2010 15 Multi labelRDT算法 Zhangetal 2010 Multi label学习问题 16 Multi labelRDT算法 P L1 x 30 100 0 3 P L1 x 30 50 0 6 P L2 x 50 100 0 5 P L2 x 20 100 0 2 P L1 x P L1 x 2 0 45 P L2 x P L2 x 2 0 35 17 RDT算法在Spark上实现的问题 两种方式都存在比较大的缺点方式1 需要多次迭代方式2 空树占用过多内存 限制树的深度 方式3 不显示构建树结构的随机决策树 仅在样本走到某个节点时 动态确定当前的节点的feature 优点 无需迭代数据 内存占用小 18 如何实现不构建树的随机决策树算法 一个伪随机数种子就可以确定一棵随机决策树理论上 我们仅需要一个伪随机数种子 我们就可以计算出这棵树任何一个节点上的feature实践中 使用伪随机数发生器效率比较低 我们采用Hash函数 19 二叉随机决策树的实现 二叉树仅针对binary数据 每个节点只需要确定feature可以通过公式推算父节点 左右子节点的编号 父节点 p 1 2 奇数 p 2 2 偶数 左子节点 2 p 1右子节点 2 p 2 20 Spark实现 确定节点feature 用Hash函数来确定每个节点的featuref hash p s modM其中 p是节点编码 s是当前树的种子 M是feature数 hash函数是整数hash函数 如果在一条路径下重复出现了一个feature 则按如下逻辑处理 while pathcontains f f f 1 modMendwhile 21 样本在树上行走的过程 Hash 0 s mod8 4 Hash 2 s mod8 0 Hash 5 s mod8 0 0 1 mod8 1 2 f0 5 f0 5 f1 2 1 3 4 5 6 0 0 f4 f4 f0 f0 Conflict f1 22 随机决策树Spark实现 Map Data Data Data Data S1 S4 S2 S3 Reduce 23 与MLLib算法的比较 数据 对RDT算法 用SimHash转成512维binary数据 24 与MLLib算法的比较 RDT 深度 30树棵数 50Spark配置 excutors 12worker 1driver mem 2Gexecutor mem 2G MLLib 1 0 算法 迭代 10次LogsiticRegressionSVMDecisionTreeSpark配置 excutors 12work