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