Алгоритм ID3 — один из алгоритмов для построения дерева принятия решений. Разработан Джоном Р. Квинланом (). Впоследствии Квинлан создал усовершенствованную версию — алгоритм C4.5.
Алгоритм Взять все неиспользованные признаки и посчитать их энтропию относительно тестовых образцов Выбрать признак, для которого энтропия минимальна (а информационная выгода соответственно максимальна) Сделать узел дерева, содержащий этот признак
Алгоритм следующий:
ID3(Таблица примеров, Целевой признак, Признаки)
Если все примеры положительны, то возвратить узел с меткой «+». Если все примеры отрицательны, то возвратить узел с меткой «-». Если множество признаков пустое, то возвратить узел с меткой, которая больше других встречается в значениях целевого признака в примерах. Иначе: A — признак, который лучше всего классифицирует примеры (с максимальной информационной выгодой). Создать корень дерева решения; признаком в корне будет являться . Для каждого возможного значения (): Добавить новую ветвь дерева ниже корня с узлом со значением Выделить подмножество примеров, у которых . Если подмножество примеров пусто, то ниже этой новой ветви добавить узел с меткой, которая больше других встречается в значениях целевого признака в примерах. Иначе, ниже этой новой ветви добавить поддерево, вызывая рекурсивно ID3(, Целевой признак, Признаки) Возвратить корень.
Литература
Категория:Деревья принятия решений