基于GINI的分类回归树最优分割计算

Question

在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

是否有可能对此过程进行任何修改以获得速度，而代价是局部精度，但这不会导致整体精度下降？虽然这可以很容易地并行化，但是循环每个属性仍然代价高昂，选择一个单独的拆分也是很有价值的。

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

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

如果该特性是绝对的，则遵循相同的过程，但根据目标密度对二进制目标进行排序。如果你有两个以上的目标值，这就变得有点棘手了。