ID3

ID3 — это алгоритм машинного обучения, используемый для построения деревьев решений. Относится к классу методов индуктивного обучения, применяемых для задач классификации и регрессии. Алгоритм был разработан австралийским учёным Джоном Россом Куинланом в 1986 году и является одним из первых и наиболее известных алгоритмов построения деревьев решений.

История

Алгоритм ID3 (Iterative Dichotomiser 3, «итеративный дихотомизатор, версия 3») был предложен Дж. Р. Куинланом в статье «Induction of Decision Trees» (1986). Работа основывалась на более ранних исследованиях Куинлана по системам обучения на примерах, в частности на системе ID2. Основной целью разработки было создание эффективного метода для автоматического построения деревьев решений на основе обучающих данных, который мог бы работать с дискретными признаками.

До появления ID3 деревья решений строились вручную или с помощью менее формализованных методов. Алгоритм Куинлана предложил строгий математический критерий для выбора атрибутов на каждом шаге — энтропию и прирост информации (information gain), что сделало процесс построения детерминированным и воспроизводимым.

В 1993 году Куинлан представил усовершенствованную версию алгоритма — C4.5, которая устранила ряд недостатков ID3, включая проблемы с непрерывными признаками, переобучением и пропущенными значениями. Тем не менее, ID3 остаётся фундаментальным алгоритмом, изучаемым в курсах машинного обучения и искусственного интеллекта.

Основные понятия

Дерево решений

Дерево решений — это иерархическая структура, состоящая из узлов и рёбер. Каждый внутренний узел соответствует проверке значения некоторого признака (атрибута), каждое ребро — одному из возможных значений этого признака, а каждый листовой узел — классу (решению). Путь от корня к листу представляет собой набор условий, которые необходимо выполнить, чтобы отнести объект к определённому классу.

Энтропия

Энтропия — мера неопределённости (неупорядоченности) данных. В контексте ID3 энтропия набора данных S вычисляется по формуле:

\[ H(S) = -\sum_{i=1}^{n} p_i \log_2 p_i \]

где \( p_i \) — доля объектов, принадлежащих классу \( i \), в наборе S. Чем выше энтропия, тем более разнородны данные по классам.

Прирост информации

Прирост информации (information gain) — это уменьшение энтропии при разбиении набора данных по некоторому признаку A. Вычисляется как:

\[ Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v) \]

где \( S_v \) — подмножество объектов, у которых признак A принимает значение \( v \). Алгоритм ID3 на каждом шаге выбирает признак, дающий максимальный прирост информации.

Алгоритм работы

Входные данные

• Обучающая выборка — множество объектов, каждый из которых описан набором дискретных признаков и принадлежит одному из заранее заданных классов.
• Список признаков (атрибутов).

Пошаговое описание

1. Создание корневого узла, содержащего все обучающие примеры.
2. Проверка условия остановки:

• Если все примеры в узле принадлежат одному классу — узел становится листом, ему присваивается этот класс.
• Если список признаков пуст — узел становится листом, ему присваивается класс, наиболее часто встречающийся среди примеров в узле.
• Если узел не содержит примеров — создаётся лист с классом, наиболее частым в родительском узле.

1. Выбор признака:

• Для каждого признака вычисляется прирост информации.
• Выбирается признак с максимальным приростом.

1. Разбиение:

• Узел разбивается на дочерние узлы по значениям выбранного признака.
• Для каждого дочернего узла рекурсивно повторяются шаги 2–4.

Пример

Рассмотрим задачу классификации погоды для игры в теннис. Признаки: Outlook (Sunny, Overcast, Rain), Temperature (Hot, Mild, Cool), Humidity (High, Normal), Wind (Weak, Strong). Целевая переменная — Play (Yes/No). Алгоритм ID3 вычислит прирост информации для каждого признака и выберет тот, который лучше всего разделяет данные (например, Outlook). Затем процесс повторяется для каждого подмножества.

Достоинства и недостатки

Достоинства

• Простота понимания и интерпретации: результирующее дерево легко визуализируется и объясняется.
• Не требует предварительной нормализации или масштабирования данных.
• Автоматически отбирает наиболее информативные признаки.
• Работает с категориальными данными.

Недостатки

• Чувствительность к шуму: выбросы и ошибочные метки могут существенно исказить дерево.
• Переобучение: склонность строить слишком сложные деревья, идеально соответствующие обучающей выборке, но плохо обобщающие новые данные.
• Неспособность работать с непрерывными признаками: все атрибуты должны быть дискретными; непрерывные значения необходимо предварительно дискретизировать.
• Смещение в пользу признаков с большим числом значений: критерий прироста информации отдаёт предпочтение признакам, имеющим много различных значений (например, идентификатор объекта), что может приводить к неоптимальным разбиениям.
• Неустойчивость: небольшие изменения в обучающих данных могут привести к существенно отличающемуся дереву.

Модификации и развитие

C4.5

Алгоритм C4.5, разработанный тем же Куинланом, является расширением ID3. Основные улучшения:

• Поддержка непрерывных признаков (автоматическое нахождение порогов разбиения).
• Обработка пропущенных значений.
• Обрезка деревьев (pruning) для борьбы с переобучением.
• Использование нормализованного прироста информации (gain ratio) для устранения смещения в пользу многозначных признаков.

CART

Алгоритм CART (Classification and Regression Trees), предложенный Л. Брейманом и др. в 1984 году, также строит деревья решений, но использует иной критерий разбиения — индекс Джини (Gini impurity) для классификации и среднеквадратичную ошибку для регрессии. CART строит только бинарные деревья (каждый узел разбивается на два дочерних), в отличие от ID3, допускающего произвольное число ветвей.

ID3 в современных системах

Хотя ID3 редко применяется в промышленных задачах в чистом виде, он лёг в основу многих более совершенных алгоритмов и остаётся важной дидактической единицей. Реализации ID3 существуют в библиотеках scikit-learn (Python), Weka (Java) и других средах машинного обучения.

Применение

ID3 и его производные используются в различных областях:

• Медицинская диагностика: построение правил для классификации заболеваний на основе симптомов.
• Финансовый анализ: оценка кредитоспособности клиентов, выявление мошеннических транзакций.
• Техническая диагностика: определение неисправностей оборудования по показателям датчиков.
• Обработка естественного языка: классификация текстов, определение тональности.
• Игровой интеллект: моделирование принятия решений в стратегических играх.

Критика

Основная критика ID3 связана с его ограничениями по сравнению с более современными методами. Алгоритм неэффективен на больших и зашумлённых данных, требует дискретизации непрерывных признаков и подвержен переобучению. Кроме того, деревья решений в целом могут быть неустойчивыми — небольшие изменения в данных приводят к существенно иным деревьям, что снижает доверие к результатам.

Тем не менее, простота и интерпретируемость ID3 делают его полезным инструментом для начального анализа данных и обучения основам машинного обучения.

Источники

1. Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning, 1(1), 81–106.
2. Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.
3. Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and Regression Trees. Wadsworth.
4. Mitchell, T. M. (1997). Machine Learning. McGraw-Hill.
5. Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.