MLLib在淘宝的使用和改进

MLlib在淘宝的应用和改进淘宝技术部数据挖掘与计算——高性能计算洪奇明风MLlib在淘宝分类&回归朴素贝叶斯决策树线性模型协同过滤ALS聚类KMeans关联规则FPGrowth降维优化特征提取L-BFGS梯度下降基本统计相关性分层抽样假设检验SVDPCATF-IDFWord2VecStandardScalerNormalizer主要内容决策树多分类决策树基本算法应用场景——用户识别购买频率女男男购买化妆品高低多少根节点叶节点内部节点deftree_growth(instances):

#如果满足终止条件，返回叶子结点

ifshould_stop(instances):leaf=newNode(isleaf=True)leaf.label=classify(instances)

returnleaf

#计算每一个split的信息增量

forsplitinpossible_splits:infogains[split]=calculate_infogain(split)

#得到具有最大信息增量的splitbest_split=infogains.index(max(infogains))

#按照最优split划分样本，递归构建树root=newNode(isLeaf=False)

for(split_outcome,split_sublists)in

split_instances(instances,best_split):child=tree_growth(split_sublists)root.add_child(split_outcome,split_sublists)

returnroot决策树的构建决策树在Spark的实现划分特征每一个样本应该被分到哪个桶聚合每一个桶的统计信息计算每次分割的信息增量找到该层所有节点的最好分割逐层训练继续下一层终止？停止训练是否1342划分特征：连续特征的分割点SPARK-3207&PR-2780原来的实现：抽样之后排序，选择分位点作为分割点会有重复的分割点222222223分隔1分隔21划分特征：连续特征的分割点现在的实现：统计每一个值的次数选择累加次数最接近分位次数的值作为分割点不会有重复的分割点112222222233（1,2）（2,8）（3,2）48分位次数21012累计次数每一个词的次数12分隔点1划分特征：连续特征的分割点valstride:Double=featureSamples.length.toDouble/

(numSplits+1)valsplits=newArrayBuffer[Double]varindex=1varcurrentCount=valueCounts(0)._2vartargetCount=stridewhile(index<valueCounts.length){

valpreviousCount=currentCountcurrentCount+=valueCounts(index)._2

valpreviousGap=math.abs(previousCount-targetCount)

valcurrentGap=math.abs(currentCount-targetCount)

if(previousGap<currentGap){splits.append(valueCounts(index-1)._1)targetCount+=stride

}index+=1}1样本分桶：一次FindBinsForLevelSPARK-3022&PR-1941FindBinsForLevel：样本到bin的映射确定分隔之后，映射已经确定在开始时计算一次和社区工作重合（PR-1950）valtreeInput=TreePoint.convertToTreeRDD(

retaggedInput,bins,metadata)2决策树在Spark的实现划分特征每一个样本应该被分到哪个桶聚合每一个桶的统计信息计算每次分割的信息增量找到该层所有节点的最好分割逐层训练继续下一层终止？停止训练是否1342样本分桶：一次FindBinsForLevelSPARK-3022&PR-1941FindBinsForLevel：样本到bin的映射确定分隔之后，映射已经确定在开始时计算一次和社区工作重合（PR-1950）valtreeInput=TreePoint.convertToTreeRDD(

retaggedInput,bins,metadata)2信息增益：并行计算BestSplitsSPARK-3366&PR-2595原先实现在Driver上计算每一个节点的BestSplitsDriver会成为计算和通信的瓶颈分布式计算BestSplitsReduceByKey把聚合信息Shuffle到Executor在Executor上进行计算3决策树在Spark的实现划分特征每一个样本应该被分到哪个桶聚合每一个桶的统计信息计算每次分割的信息增量找到该层所有节点的最好分割逐层训练继续下一层终止？停止训练是否1342信息增益：并行计算BestSplitsSPARK-3366&PR-2595原先实现在Driver上计算每一个节点的BestSplitsDriver会成为计算和通信的瓶颈分布式计算BestSplitsReduceByKey把聚合信息Shuffle到Executor在Executor上进行计算3最好分割：前向剪枝SPARK-2207&PR-2332停止分隔的两个参数minInfoGain:分隔造成的最小信息增量minInstancesPerNode：分隔出左右儿子最少的样本数已经合并进master，1.2版本发布4决策树在Spark的实现划分特征每一个样本应该被分到哪个桶聚合每一个桶的统计信息计算每次分割的信息增量找到该层所有节点的最好分割逐层训练继续下一层终止？停止训练是否1342最好分割：前向剪枝SPARK-2207&PR-2332停止分隔的两个参数minInfoGain:分隔造成的最小信息增量minInstancesPerNode：分隔出左右儿子最少的样本数已经合并进master，1.2版本发布4最好分割：避免叶结点的计算SPARK-3158&PR-2708叶节点不需要再去寻找最优分隔：最后一层的节点Impurity为0的节点4决策树在Spark的实现划分特征每一个样本应该被分到哪个桶聚合每一个桶的统计信息计算每次分割的信息增量找到该层所有节点的最好分割逐层训练继续下一层终止？停止训练是否1342最好分割：避免叶结点的计算SPARK-3158&PR-2708叶节点不需要再去寻找最优分隔：最后一层的节点Impurity为0的节点4决策树的展望梯度提升树（GradientBoosting）AdaBoostSpark1.2版本多分类

多分类应用场景对战预测（胜(0)、负(2)、平(1)）球队属性1球队属性2球队属性3结果0.000.280.55610.00-0.02-0.00320.330.050.20…………多分类训练器（Estimator）输入多分类预测器（Predictor）球队属性1球队属性2球队属性30.23-0.33-0.660.730.00-0.33………训练结果输入结果21…多分类的实现使用One-VS-All策略，组合二分类器实现多分类训练数据训练器1训练器2训练器3…训练标签二值化预测器1预测器2预测器3…预测测试数据概率1概率1概率3…选择概率最大的为结果多分类器的实现-训练deffit(input:RDD[LabeledPoint]):MultiClasssficationModel[M]={

valpredictors=newArray[M](numClasses)

varcls=0

while(cls<numClasses){

valcurrentLabel=cls

valbinaryInput=input.map(p=>{

vallabel=if(p.label==currentLabel)1.0else0.0

LabeledPoint(label,p.features)

})

valmodel:M=baseEstimator.fit(binaryInput)estimators(cls)=model

cls+=1

}

newMultiClassificationModel[M](predictors)

}多分类器的实现-预测classMultiClassificationModel[M<:ClassificationWithProbModel]

(valbasePredictors:Array[M])extendsSerializable{defpredict(x:Vector):Int={

valprobs=predictProb(x)probs.zipWithIndex.maxBy(_._1)._2

}defpredictProb(x:Vector):Array[Double]={

basePredictor