D3 работает по принципу рекурсии. На каждом шаге:
- Если все примеры одного класса — создаем лист
- Иначе находим лучший признак для разделения (макс. IG)
- Разделяем данные по этому признаку
- Рекурсивно строим левое и правое поддерево
Псевдокод алгоритма ID3:
функция построить_дерево(данные, метки):
# База рекурсии
если все метки одинаковые:
вернуть Лист(метка)
если нет признаков или достигнута макс_глубина:
вернуть Лист(самая_частая_метка)
# Рекурсивный случай
лучший_признак = найти_признак_с_макс_IG(данные, метки)
узел = Узел(признак=лучший_признак)
левые_данные, левые_метки = данные где признак == 0
правые_данные, правые_метки = данные где признак == 1
узел.левый = построить_дерево(левые_данные, левые_метки)
узел.правый = построить_дерево(правые_данные, правые_метки)
вернуть узел
Важные моменты:
- База рекурсии — когда останавливаемся
- На каждом уровне выбираем лучший признак
- Каждый узел "знает" только свой вопрос
- Дерево строится от корня к листьям