ID3 (алгоритм)

13-10-2021, 03:00

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

Алгоритм

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

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

  • Если все примеры положительны, то возвратить узел с меткой «+».
  • Если все примеры отрицательны, то возвратить узел с меткой «-».
  • Если множество признаков пустое, то возвратить узел с меткой, которая больше других встречается в значениях целевого признака в примерах.
  • Иначе:
  • A — признак, который лучше всего классифицирует примеры (с максимальной информационной выгодой).
  • Создать корень дерева решения; признаком в корне будет являться A {displaystyle A} .
  • Для каждого возможного значения A {displaystyle A} ( v i {displaystyle v_{i}} ):
  • Добавить новую ветвь дерева ниже корня с узлом со значением A = v i {displaystyle A=v_{i}}
  • Выделить подмножество E x a m p l e s ( v i ) {displaystyle Examples(v_{i})} примеров, у которых A = v i {displaystyle A=v_{i}} .
  • Если подмножество примеров пусто, то ниже этой новой ветви добавить узел с меткой, которая больше других встречается в значениях целевого признака в примерах.
  • Иначе, ниже этой новой ветви добавить поддерево, вызывая рекурсивно ID3( E x a m p l e s ( v i ) {displaystyle Examples(v_{i})} , Целевой признак, Признаки)
  • Возвратить корень.

  • Код Левенштейна
  • Адаптивный алгоритм Хаффмана
  • Алгоритм соединения хешированием
  • Согласованность данных
  • GLR-парсер

  •  

    • Яндекс.Метрика
    • Индекс цитирования