1、淘寶技術部數據挖掘與計算高性能計算洪奇 明風決策樹AdaBoost多分類淘寶用戶類型判斷購買物品女男男購買化妝品多少多少根節點葉節點內部節點def tree_growth(instances): # 如果滿足終止條件，返回葉子結點 if should_stop(instances): leaf = new Node(isleaf=True) leaf.label = classify(instances) return leaf # 計算每一個split的信息增量 for split in possible_splits: infogainssplit = calculate_infogain

2、(split) # 得到具有最大信息增量的split best_split = infogains.index(max(infogains) # 按照最優split劃分樣本，遞歸構建樹 root = new Node(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) return root劃分特征每

3、一個樣本應該被分到哪個桶聚合每一個桶的統計信息計算每次分割的信息增量找到該層所有節點的最好分割逐層訓練繼續下一層終止？停止訓練是否SPARK-3022 & PR-1941FindBinsForLevel： 樣本到bin的映射 確定分隔之后，映射已經確定在開始時計算一次和社區工作重合（PR-1950）val treeInput = TreePoint.convertToTreeRDD( retaggedInput, bins, metadata)SPARK-2207 & PR-2332停止分隔的兩個參數 minInfoGain: 分隔造成的最小信息增量 minInstancesPerNode：

4、分隔出左右兒子最少的樣本數已經合并進master，1.2版本發布SPARK-3366 & PR-2595在Driver上計算每一個節點的BestSplits Driver會成為計算和通信的瓶頸分布式計算BestSplits ReduceByKey 把聚合信息Shuffle到Executor 在Executor上計算SPARK-3158 & PR-2708葉節點不需要再去尋找最優分隔： 最后一層的節點 Impurity為0的節點SPARK-3207 & PR-2780原來的實現： 抽樣之后排序，選擇分位點作為分割點 會有重復的分割點2 22 22 22 22 22 22 22 23 3分隔1分隔

5、2現在的實現： 統計每一個值的次數 選擇累加次數最接近分位次數的值作為分割點 不會有重復的分割點1 11 12 22 22 22 22 22 22 22 23 33 3（1,21,2） （2,82,8） （3,23,2）4 48 8分位次數2 210101212累計次數每一個詞的次數1 12 2分隔點val stride: Double = featureSamples.length.toDouble / (numSplits + 1)val splits = new ArrayBufferDoublevar index = 1var currentCount = valueCounts(0)

6、._2var targetCount = stridewhile (index valueCounts.length) val previousCount = currentCount currentCount += valueCounts(index)._2 val previousGap = math.abs(previousCount - targetCount) val currentGap = math.abs(currentCount - targetCount) if (previousGap currentGap) splits.append(valueCounts(index

7、 - 1)._1) targetCount += stride index += 1梯度提升樹（Gradient Boosting）AdaBoostSpark 1.2版本發布對戰預測（勝(0)、負(2)、平(1)）球隊屬球隊屬性性1 1球隊屬球隊屬性性2 2球隊屬球隊屬性性3 3球隊屬球隊屬性性4 4結果結果0.510.000.280.55610.430.00-0.02-0.00320.370.330.050.20多分類訓練器（Estimator）輸入多分類預測器（Predictor）球隊球隊屬性屬性1 1球隊球隊屬性屬性2 2球隊球隊屬性屬性3 3球隊球隊屬性屬性4 40.23-0.330.

8、17-0.660.730.00-0.07-0.33訓練結果輸入結果結果21使用One-VS-All策略，組合二分類器實現多分類訓練數據訓練器1訓練器2訓練器3訓練標簽二值化預測器1預測器2預測器3預測測試數據概率1概率1概率3選擇概率最大的為結果def fit(input: RDDLabeledPoint): MultiClasssficationModelM= val predictors = new ArrayM(numClasses) var cls = 0 while (cls val label = if (p.label = currentLabel) 1.0 else 0.0 LabeledPoint(label, p.features) ) val model: M = baseEstimator.fit(binaryInput) estimators(cls) = model cls += 1 new MultiClassificationModelM(predictors) class MultiClassificationModelM p.predictProb(x) 一次訓練多個模型設