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

TalkingData基于Spark的

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

LRSimHash內(nèi)容TalkingData簡介我們的數(shù)據(jù)挖掘工作應(yīng)用廣告優(yōu)化隨機決策樹算法及其Spark實現(xiàn)應(yīng)用廣告優(yōu)化針對某一應(yīng)用，篩選推廣目標(biāo)人群如何做廣告優(yōu)化分類問題

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

隨機決策樹

一次迭代LRRDT算法簡介隨機決策樹算法〔RandomDecsionTrees〕[Fanetal,2003] 融合多棵隨機構(gòu)建的決策樹的預(yù)測結(jié)果，來進行分類/回歸特點 樹的構(gòu)建完全隨機，不尋找最優(yōu)分裂點和分裂值 建樹的開銷低 建樹的過程不需要使用label信息應(yīng)用 分類，多標(biāo)簽分類，回歸 單機開源實現(xiàn)：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……兩種構(gòu)建隨機決策樹的方式方式1：

方式2：

優(yōu)點：隨時剪枝缺點：需要迭代優(yōu)點：不需要迭代缺點：空樹占用內(nèi)存很大，限制了樹的深度與決策樹和隨機決策森林的區(qū)別決策樹隨機決策森林隨機決策樹融合算法否是是隨機程度無隨機部分隨機完全隨機建樹過程是否使用label信息使用使用不使用算法復(fù)雜度中高低計算復(fù)雜度1.與訓(xùn)練樣本數(shù)量線性相關(guān)2.與所有feature的可取值數(shù)量平方相關(guān)與訓(xùn)練樣本數(shù)量線性相關(guān)與feature子空間里的feature可取值數(shù)量平方相關(guān)與樹的數(shù)量線性相關(guān)1.與訓(xùn)練樣本數(shù)量線性相關(guān)2.與樹的數(shù)量線性相關(guān)是否需要迭代需要需要依賴于采用哪種實現(xiàn)為什么RDT有學(xué)習(xí)能力直觀解釋 [Fanetal.,2003]貝葉斯最優(yōu)分類器解釋 [Fanetal.,2005;DavidsonandFan,2006]矩解釋〔高階統(tǒng)計〕 [Dhurandhar2010]Multi-labelRDT算法

[Zhangetal,2010]Multi-label學(xué)習(xí)問題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上實現(xiàn)的問題兩種方式都存在比較大的缺點 方式1：需要屢次迭代 方式2：空樹占用過多內(nèi)存，限制樹的深度方式3：不顯示構(gòu)建樹結(jié)構(gòu)的隨機決策樹，僅在樣本走到某個節(jié)點時，動態(tài)確定當(dāng)前的節(jié)點的feature.優(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é)點的編號01237849105111261314. . . . . . . . . . .父節(jié)點：(p-1)/2(奇數(shù))，(p-2)/2〔偶數(shù)〕左子節(jié)點：2*p+1右子節(jié)點：2*p+2Spark實現(xiàn)—確定節(jié)點feature用Hash函數(shù)來確定每個節(jié)點的feature f=hash(p+s)modM其中，p是節(jié)點編碼，s是當(dāng)前樹的種子，M是feature數(shù),hash函數(shù)是整數(shù)hash函數(shù)。如果在一條路徑下重復(fù)出現(xiàn)了一個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實現(xiàn)Map……DataDataData…Data…S1S4S2S3Reduce與MLLib算法的比較數(shù)據(jù)〔對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ù)：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