В реализации ID3, в какой момент рекурсия в алгоритме должна быть остановлена ​​

Question

В реализации ID3, в этот момент рекурсия в алгоритме должна быть остановлена.

Answer 1

Ну, вы продолжаете разделять (формируете два новых узла из существующего), пока выполняется критерий расщепления.

Критерий расщепления, как правило, отрицательное значение разницы между родительским узлом данных Gain, иначе энтропии, (или дисперсии если переменная является дискретным, а не категоричное) и средневзвешенную И.Г. из мнимые дочерних узлы средневзвешенной информации Gain:

if weighted_mean(IG_child1, IG_child2) < IG_parent : 
    createNodes(IG_child1, IG_child2) 
else : 
    continue 

Так что это тривиальный ответ, но, скорее всего, более сложное намерение за ваш вопрос, который, если вы не возражаете, я буду повторно горе rd слегка как следует ли вам продолжать создавать узлы, пока выполняется критерий расщепления?

Как вы, возможно, только что узнали, если вы кодирование алгоритма ID3, применяя критерий расщепления без ограничения часто вызывают над облегающими (то есть дерево, которое вы строить из обучающих данных Безразлично «Хорошо обобщить, потому что он не отличал шум от подлинной модели»).

Так что это, скорее всего, ответ на ваш вопрос: методы к узлу расщепления «» (сдерживают и, следовательно, иметь дело с более облегающие проблемы) все попадают в одну из двух категории-- сверху вниз или нижней up. Пример сверху вниз: установить некоторый порог (например, если взвешенное среднее дочерних узлов меньше, чем на 5% ниже, то не разделить)?

Пример снизу вверх: pruning. Обрезка означает, что алгоритм расщепляется до тех пор, пока критерий расщепления будет удовлетворен, а затем после его прекращения, начните с нижнего слоя узлов и «нерасщепите» любые узлы, в которых разность IG между дочерними узлами и родителем меньше, чем некоторые порог.

Эти два подхода не имеют такого же эффекта, и на самом деле обрезка является превосходной техникой. Причина: если вы применяете порог разделения сверху вниз, тогда, конечно, будет предотвращено некоторое разделение; однако, если бы это было разрешено, следующий раскол (один или оба из двух дочерних узлов в внуках) мог быть действительным расколом (т. е. выше порога), но этот раскол никогда не произойдет. Разумеется, обрезка объясняет это.

Answer 2

Филиал останавливается, когда нет примеров для классификации или нет атрибутов, которые можно классифицировать. algorithm description on Wikipedia довольно легко следовать, и там есть множество ссылок на примеры и дискуссии.