Дерево классификации и регрессии - оптимальный расчет расщепления с помощью 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

Можно ли внести какие-либо изменения в эту процедуру для увеличения скорости за счет локальной точности, но это не приведет к снижению общей точности ?Несмотря на то, что это можно легко распараллелить, обходить каждый атрибут по-прежнему дорого, и стоит выбрать одно разбиение.

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 целевых значений.