java - 分类和回归树 - 用 GINI 进行最优分割计算

Question

我一直在关注本指南cart算法与我的java实现，想知道是否有更快的方法来选择最佳分割。

指南建议采取以下步骤:

       for each feature:
          for each value of the feature:
             make a split
             remember GINI score if a split is less than previous min GINI

是否可以对此过程进行任何修改，以牺牲局部精度为代价来提高速度，但不会导致总体精度下降？虽然这可以很容易地并行化，但循环每个属性的成本仍然很高，并且选择单个拆分是有值(value)的。

Answer 1

是的，这可以加快:

For each feature
    Sort data by feature
    Calculate cumulative counts of different values of target
    Calculate reverse cumulative counts of different values of target
    At each feature value
         Calculate gini value based on cumulative counts
         Keep the maximum

如果特征采用一组有限的值，则可以进一步优化。您可以聚合数据并使用聚合数据进行拆分计算，而不是对数据进行排序。

如果特征是分类特征，则遵循相同的过程，但按二元目标的目标密度对特征进行排序。如果您有超过 2 个目标值，这会变得有点棘手。