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. Возвратить корень.


Литература[править | править вики-текст]

  • Паклин Н.Б., Орешков В.И. Глава 9. // Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд.. — СПб: Питер, 2013. — С. 444-459. — ISBN 978-5-459-00717-6