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

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

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

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

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

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

6、et al., 2003]貝葉斯最優(yōu)分類器解釋 [Fan et al., 2005;Davidson and Fan, 2006]矩解釋（高階統(tǒng)計(jì)）[Dhurandhar 2010],Multi-label RDT算法 [Zhang et al, 2010],Multi-label 學(xué)習(xí)問(wèn)題,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上實(shí)現(xiàn)的問(wèn)題,兩種方式都存在比較大的缺點(diǎn)方式1： 需要多次迭代方式2： 空樹(shù)占用過(guò)多內(nèi)存，限制樹(shù)的深度,,,方式3： 不顯示構(gòu)建樹(shù)結(jié)構(gòu)的隨機(jī)決策樹(shù)，僅在樣本走到某個(gè)節(jié)點(diǎn)時(shí)，動(dòng)態(tài)確定當(dāng)前的節(jié)點(diǎn)的feature.

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

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

10、f+1) mod M end while,樣本在樹(shù)上行走的過(guò)程,,,,,,,,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,隨機(jī)決策樹(shù)Spark實(shí)現(xiàn),Map,Data,Data,Data,Data,

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