TalkingData基于Spark的數(shù)據(jù)挖掘工作

TalkingData基于Spark的

數(shù)據(jù)挖掘工作張夏天騰云天下科技@張夏天_機(jī)器學(xué)習(xí)內(nèi)容TalkingData簡(jiǎn)介我們的數(shù)據(jù)挖掘工作應(yīng)用廣告優(yōu)化隨機(jī)決策樹(shù)算法及其Spark實(shí)現(xiàn)TalkingData簡(jiǎn)介T(mén)alkingData移動(dòng)大數(shù)據(jù)生態(tài)圈行業(yè)透視DMP數(shù)據(jù)管理平臺(tái)數(shù)據(jù)交易與交換數(shù)據(jù)監(jiān)測(cè)與預(yù)警根底數(shù)據(jù)效勞數(shù)據(jù)能力開(kāi)放企業(yè)效勞內(nèi)容TalkingData簡(jiǎn)介我們的數(shù)據(jù)挖掘工作應(yīng)用廣告優(yōu)化隨機(jī)決策樹(shù)算法及其Spark實(shí)現(xiàn)數(shù)據(jù)挖掘在TalkingData的應(yīng)用移動(dòng)應(yīng)用推薦廣告優(yōu)化用戶(hù)畫(huà)像游戲數(shù)據(jù)挖掘外包咨詢(xún)通用推薦同步推機(jī)鋒開(kāi)放：移動(dòng)應(yīng)用通用效勞接口CTR:提升20%-50%轉(zhuǎn)化率:提升50%-100%轉(zhuǎn)化本錢(qián):降低50%人口屬性移動(dòng)應(yīng)用興趣標(biāo)簽行業(yè)興趣標(biāo)簽位置信息付費(fèi)預(yù)測(cè)流失預(yù)測(cè)為什么選擇Spark硬件資源有限人力資源有限任務(wù)繁重為什么沒(méi)有廣泛使用MLLib內(nèi)存資源有限，很多情況下無(wú)法把數(shù)據(jù)放入內(nèi)存處理，因此迭代算法效率還是很低迭代依然是阿格硫斯之蹱我們只能盡可能使用需要迭代次數(shù)少，甚至不迭代的算法和算法實(shí)現(xiàn)RDTOneIteration

LRSimHash內(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)化分類(lèi)問(wèn)題

預(yù)測(cè)每個(gè)設(shè)備對(duì)目標(biāo)應(yīng)用的感興趣程度算法

隨機(jī)決策樹(shù)

一次迭代LRRDT算法簡(jiǎn)介隨機(jī)決策樹(shù)算法〔RandomDecsionTrees〕[Fanetal,2003] 融合多棵隨機(jī)構(gòu)建的決策樹(shù)的預(yù)測(cè)結(jié)果，來(lái)進(jìn)行分類(lèi)/回歸特點(diǎn) 樹(shù)的構(gòu)建完全隨機(jī)，不尋找最優(yōu)分裂點(diǎn)和分裂值 建樹(shù)的開(kāi)銷(xiāo)低 建樹(shù)的過(guò)程不需要使用label信息應(yīng)用 分類(lèi)，多標(biāo)簽分類(lèi)，回歸 單機(jī)開(kāi)源實(shí)現(xiàn)：RDT的簡(jiǎn)單例子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……兩種構(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ū)別決策樹(shù)隨機(jī)決策森林隨機(jī)決策樹(shù)融合算法否是是隨機(jī)程度無(wú)隨機(jī)部分隨機(jī)完全隨機(jī)建樹(shù)過(guò)程是否使用label信息使用使用不使用算法復(fù)雜度中高低計(jì)算復(fù)雜度1.與訓(xùn)練樣本數(shù)量線(xiàn)性相關(guān)2.與所有feature的可取值數(shù)量平方相關(guān)與訓(xùn)練樣本數(shù)量線(xiàn)性相關(guān)與feature子空間里的feature可取值數(shù)量平方相關(guān)與樹(shù)的數(shù)量線(xiàn)性相關(guān)1.與訓(xùn)練樣本數(shù)量線(xiàn)性相關(guān)2.與樹(shù)的數(shù)量線(xiàn)性相關(guān)是否需要迭代需要需要依賴(lài)于采用哪種實(shí)現(xiàn)為什么RDT有學(xué)習(xí)能力直觀解釋 [Fanetal.,2003]貝葉斯最優(yōu)分類(lèi)器解釋 [Fanetal.,2005;DavidsonandFan,2006]矩解釋〔高階統(tǒng)計(jì)〕 [Dhurandhar2010]Multi-labelRDT算法

[Zhangetal,2010]Multi-label學(xué)習(xí)問(wèn)題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上實(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.優(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)01237849105111261314. . . . . . . . . . .父節(jié)點(diǎn)：(p-1)/2(奇數(shù))，(p-2)/2〔偶數(shù)〕左子節(jié)點(diǎn)：2*p+1右子節(jié)點(diǎn)：2*p+2Spark實(shí)現(xiàn)—確定節(jié)點(diǎn)feature用Hash函數(shù)來(lái)確定每個(gè)節(jié)點(diǎn)的feature f=hash(p+s)modM其中，p是節(jié)點(diǎn)編碼，s是當(dāng)前樹(shù)的種子，M是feature數(shù),hash函數(shù)是整數(shù)hash函數(shù)。如果在一條路徑下重復(fù)出現(xiàn)了一個(gè)feature,那么按如下邏輯處理： while(pathcontains(f))f=(f+1)modMendwhile樣本在樹(shù)上行走的過(guò)程f0f1f2f3f4f5f6f710100101Hash(0+s)mod8=4Hash(2+s)mod8=0Hash(5+s)mod8=0(0+1)mod8=12:f05:f05:f121345600:f4f4f0f0Conflict!f1隨機(jī)決策樹(shù)Spark實(shí)現(xiàn)Map……DataDataData…Data…S1S4S2S3Reduce與MLLib算法的比較數(shù)據(jù)〔對(duì)RDT算法，用SimHash轉(zhuǎn)成512維binary數(shù)據(jù)〕：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

樹(shù)棵數(shù)：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