talkingdata基于spark的數(shù)據(jù)挖掘工作

1、TalkingData基于Spark的數(shù)據(jù)挖掘工作,張夏天 騰云天下科技有限公司@張夏天_機器學習,內(nèi)容,TalkingData簡介我們的數(shù)據(jù)挖掘工作應用廣告優(yōu)化隨機決策樹算法及其Spark實現(xiàn),Talking Data簡介,TalkingData移動大數(shù)據(jù)生態(tài)圈,行業(yè)透視,DMP數(shù)據(jù)管理平臺,數(shù)據(jù)交易與交換,數(shù)據(jù)監(jiān)測與預警,基礎數(shù)據(jù)服務,數(shù)據(jù)能力開放,企業(yè)服務,內(nèi)容,TalkingData簡介我們的數(shù)據(jù)挖掘工作

2、應用廣告優(yōu)化隨機決策樹算法及其Spark實現(xiàn),數(shù)據(jù)挖掘在TalkingData的應用,移動應用推薦,廣告優(yōu)化,用戶畫像,游戲數(shù)據(jù)挖掘,,外包咨詢,,通用推薦,同步推,機鋒,開放：移動應用通用服務接口,CTR: 提升20%-50%轉(zhuǎn)化率: 提升50%-100%轉(zhuǎn)化成本: 降低50%,,人口屬性,,移動應用興趣標簽,,行業(yè)興趣標簽,,位置信息,,付費預測,,流失預測,為什么選擇Spark,硬件資源有限,人力資源有限,任務

3、繁重,,,為什么沒有廣泛使用MLLib,內(nèi)存資源有限，很多情況下無法把數(shù)據(jù)放入內(nèi)存處理，因此迭代算法效率還是很低迭代依然是阿格硫斯之蹱我們只能盡可能使用需要迭代次數(shù)少，甚至不迭代的算法和算法實現(xiàn),RDT,One Iteration LR,SimHash,內(nèi)容,TalkingData簡介我們的數(shù)據(jù)挖掘工作應用廣告優(yōu)化隨機決策樹算法及其Spark實現(xiàn),應用廣告優(yōu)化,針對某一應用，篩選推廣目標人群,,,,,,,如何做廣告優(yōu)化

4、,分類問題預測每個設備對目標應用的感興趣程度算法隨機決策樹一次迭代LR,RDT算法簡介,隨機決策樹算法（Random Decsion Trees）[Fan et al, 2003]融合多棵隨機構(gòu)建的決策樹的預測結(jié)果，來進行分類/回歸特點樹的構(gòu)建完全隨機，不尋找最優(yōu)分裂點和分裂值 建樹的開銷低建樹的過程不需要使用label信息應用分類，多標簽分類，回歸單機開源實現(xiàn)： Dice

5、 www.dice4dm.com,RDT的簡單例子,P’(+|x)=30/50 =0.6,P(+|x)=30/100=0.3,,,(P(+|x)+P’(+|x))/2 = 0.45,兩種構(gòu)建隨機決策樹的方式,方式1：,方式2：,,,,,,,,,,,,,,,,,,,,優(yōu)點：隨時剪枝缺點：需要迭代,優(yōu)點：不需要迭代缺點：空樹占用內(nèi)存很大，限制了樹的深度,與決策樹和隨機決策森林的區(qū)別,為什么RDT有學習能力,直觀解釋 [Fan

6、et al., 2003]貝葉斯最優(yōu)分類器解釋 [Fan et al., 2005;Davidson and Fan, 2006]矩解釋（高階統(tǒng)計）[Dhurandhar 2010],Multi-label RDT算法 [Zhang et al, 2010],Multi-label 學習問題,Multi-label RDT算法,P(L1+|x)=30/100=0.3,P’(L1+|x)=30/50 =0.6,P(L

7、2+|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,RDT算法在Spark上實現(xiàn)的問題,兩種方式都存在比較大的缺點方式1： 需要多次迭代方式2： 空樹占用過多內(nèi)存，限制樹的深度,,,方式3： 不顯示構(gòu)建樹結(jié)構(gòu)的隨機決策樹，僅在樣本走到某個節(jié)點時，動態(tài)確定當前的節(jié)點的feature.

8、優(yōu)點：無需迭代數(shù)據(jù)，內(nèi)存占用小,如何實現(xiàn)不構(gòu)建樹的隨機決策樹算法,一個偽隨機數(shù)種子就可以確定一棵隨機決策樹理論上：我們僅需要一個偽隨機數(shù)種子，我們就可以計算出這棵樹任何一個節(jié)點上的feature實踐中：使用偽隨機數(shù)發(fā)生器效率比較低，我們采用Hash函數(shù),二叉隨機決策樹的實現(xiàn),二叉樹僅針對binary數(shù)據(jù)， 每個節(jié)點只需要確定feature可以通過公式推算父節(jié)點，左右子節(jié)點的編號,父節(jié)點： (p-1)/2(奇數(shù)) ，

9、(p-2)/2（偶數(shù)） 左子節(jié)點：2*p+1右子節(jié)點：2*p+2,Spark實現(xiàn)—確定節(jié)點feature,用Hash函數(shù)來確定每個節(jié)點的featuref = hash(p+s) mod M其中，p是節(jié)點編碼，s是當前樹的種子，M是feature數(shù), hash函數(shù)是整數(shù)hash函數(shù)。如果在一條路徑下重復出現(xiàn)了一個feature, 則按如下邏輯處理：while(path contains(f)) f = (

10、f+1) mod M end while,樣本在樹上行走的過程,,,,,,,,Hash(0+s) mod 8 = 4,Hash(2+s) mod 8 = 0,Hash(5+s) mod 8 = 0,(0+1) mod 8 = 1,,,,,2:f0,,5:f0,5:f1,,2,1,3,4,5,6,0,0:f4,f4,f0,f0,Conflict !,f1,隨機決策樹Spark實現(xiàn),Map,Data,Data,Data,Data,

11、S1,S4,S2,S3,,,,,,,,,,,,,,,,,Reduce,與MLLib算法的比較,數(shù)據(jù)（對RDT算法，用SimHash轉(zhuǎn)成512維binary數(shù)據(jù)）：,與MLLib算法的比較,RDT:深度: 30 樹棵數(shù)：50Spark配置:excutors: 12worker: 1driver-mem: 2Gexecutor-mem:2G,MLLib(1.0)算法：迭代：10次Logsitic Re