ID3 (алгоритм)

Алгоритм ID3 — один из алгоритмов для построения дерева принятия решений. Разработан Джоном Р. Квинланом (англ. John R. Quinlan). Впоследствии Квинлан создал усовершенствованную версию — алгоритм C4.5.

Алгоритм

1. Взять все неиспользованные признаки и посчитать их энтропию относительно тестовых образцов
2. Выбрать признак, для которого энтропия минимальна (а информационная выгода соответственно максимальна)
3. Сделать узел дерева, содержащий этот признак

Алгоритм следующий:

ID3(Таблица примеров, Целевой признак, Признаки)

1. Если все примеры положительны, то возвратить узел с меткой «+».
2. Если все примеры отрицательны, то возвратить узел с меткой «-».
3. Если множество признаков пустое, то возвратить узел с меткой, которая больше других встречается в значениях целевого признака в примерах.
4. Иначе:
   1. A — признак, который лучше всего классифицирует примеры (с максимальной информационной выгодой).
   2. Создать корень дерева решения; признаком в корне будет являться $A$.
   3. Для каждого возможного значения $A$ ($v_i$):
      1. Добавить новую ветвь дерева ниже корня с узлом со значением $A = v_i$
      2. Выделить подмножество $Examples(v_i)$ примеров, у которых $A = v_i$.
      3. Если подмножество примеров пусто, то ниже этой новой ветви добавить узел с меткой, которая больше других встречается в значениях целевого признака в примерах.
      4. Иначе, ниже этой новой ветви добавить поддерево, вызывая рекурсивно ID3($Examples(v_i)$, Целевой признак, Признаки)
5. Возвратить корень.