Итак, вы продолжаете разделение (формируете два новых узла из существующего), пока выполняется критерий разделения.
Критерием расщепления обычно является отрицательное значение для разницы между родительским узлом Информационный прирост , он же энтропия , (или дисперсия , если переменная дискретная а не категориальные) и средневзвешенная IG предполагаемых дочерних узлов средневзвешенная информационный прирост :
if weighted_mean(IG_child1, IG_child2) < IG_parent :
createNodes(IG_child1, IG_child2)
else :
continue
Так что это тривиальный ответ, но, вероятно, за вашим вопросом стоит более изощренное намерение, которое, если вы не возражаете, я слегка перефразирую как , если вы продолжите создавать узлы пока критерий расщепления удовлетворен?
Как вы, возможно, только что узнали, если кодируете алгоритм ID3, применение критерия расщепления без ограничений часто вызывает перегонку (т. Е. Дерево, которое вы построили из обучающих данных. плохо обобщается, потому что не отличает шум от подлинных образцов).
Так что, скорее всего, это ответ на ваш вопрос: методы «ограничения» разбиения узла (и, следовательно, решения проблемы перебора) все попадают в одну из двух категорий - сверху вниз или снизу вверх . Пример сверху вниз: установить некоторый порог (например, если средневзвешенное значение дочерних узлов меньше, чем на 5% ниже, то не делить)?
Пример снизу вверх: обрезка . Сокращение означает позволить алгоритму разделяться до тех пор, пока критерий разделения удовлетворяется, а затем после его остановки начинать с нижнего уровня узлов и «расщеплять» любые узлы, в которых разница IG между дочерними узлами и родительским узлом меньше, чем некоторые. порог.
Эти два подхода не имеют одинакового эффекта, и на самом деле обрезка является превосходной техникой. Причина: если вы применяете порог разделения сверху вниз, то, конечно, некоторое разделение будет предотвращено; однако, если бы это было разрешено, следующее разделение (один или оба дочерних узла на внуков) могло бы быть допустимым разделением (т. е. выше порогового значения), но такое разделение никогда бы не произошло. Обрезка конечно объясняет это.