«Дерево решений» — один из наиболее важных и наиболее полезных типов структур для машинного обучения. Особенно это очень важно для контролируемого обучения, то есть обучения с классификацией помеченного набора данных, касающегося заданного поведения, и применением этих знаний к различным данным. Можно сказать, что это похоже на обучение с учителем. В отличие от неконтролируемого обучения, в этом типе вы предоставляете программе помеченные данные.
Компонент дерева решений
В дереве решений каждая ветвь представляет разные результаты. Мы можем думать об этом как о блок-схеме. Каждое решение погружает нас глубже и классифицирует наши данные.
Для каждого узла мы назначаем некоторые атрибуты и задаем несколько вопросов к этим атрибутам. Ответы на эти вопросы указывают нам пути. Таким образом, узлы — это атрибуты, а ребра — значения этих атрибутов.
Итак, в данном случае атрибут «Голоден», а вопрос «Голоден ли ты?» и каждое ребро представляет возможный ответ. С новым ответом мы достигаем нового уровня, и программа создает новый узел с новым атрибутом и рекурсивно применяет тот же метод классификации.
В конце мы можем сказать, что листья представляют результаты.
В этом случае листья являются результатом события. Если мы голодны, мы едим сейчас, если нет, то едим позже.
Итак, как вы уже поняли, основная цель в дереве решений — разделить данные, найти наиболее подходящую классификацию и повторять это до тех пор, пока все наборы данных не станут связанными друг с другом. Чтобы представить себе полное дерево решений, вот более наглядный пример;
В этом примере, во-первых, у нас есть набор данных, который содержит разные фигуры разных цветов. Сначала мы классифицируем эти данные по форме, а затем по цвету. В этом примере первая классификация сделана с учетом формы, но это может быть и цвет. Итак, вопрос в том, как программа выбирает порядок классификации? Чтобы понять это, сначала нам нужно изучить несколько концепций.
Энтропия и получение информации
Энтропия. Энтропия в духе машинного обучения измеряет однородность набора данных. Если энтропия равна 0, это означает, что все наборы данных одинаковы. Математическая формула энтропии:
В этой формуле «S» представлен для набора данных, «c» представлен для общего количества различных классификаций, «Pi» — это доля данных с классификацией.
Например, допустим, у нас есть таблица данных об ужине на улице, и в этой таблице у нас есть разные переменные. Этими переменными могут быть «Голоден ли я?», «Погода хорошая?», «Хочу ли я остаться дома?», «Хочу ли я что-нибудь заказать?» и т. д. Эти переменные приводят нас к двум различным результатам. что да или нет. Итак, у нас 2 класса. Положительное или отрицательное.
Итак, если у нас было 7 положительных результатов в нашей таблице и 4 отрицательных результата в нашей таблице, мы можем рассчитать энтропию следующим образом:
Получение информации.Получение информации определяет, насколько эффективным является атрибут для классификации данных. Повышается классификационный статус программы, прирост знаний становится больше. Мы можем думать об этой концепции так, как если бы мы углубились в наше дерево, мы хотим, чтобы наши данные были более разделены друг от друга в отношении их метки.
Мы всегда хотим максимизировать прирост информации, поэтому нам нужно, чтобы энтропия разделенных данных была как можно ниже.
Приведенная выше формула представляет собой прирост информации. T — это заданный набор, а X — это атрибут, который мы хотим рассчитать. Таким образом, ответ на предыдущий вопрос таков: когда наша программа выбирает порядок классификации, она сначала вычисляет прирост информации.
Алгоритм ID3
Итак, мы изучаем основы дерева решений и понимаем, как дерево решений разделяет данные друг с другом. Теперь мы можем увидеть, как это делает алгоритм ID3.
ID3 — это алгоритм, который генерирует дерево решений из заданного размеченного набора данных. Он используется в машинном обучении и обработке естественного языка. ID3 использует жадный подход сверху вниз, что означает, что мы строим дерево сверху вниз и на каждой итерации пытаемся выбрать наилучшую классификацию. Алгоритм ID3 заключается в поиске атрибута, который возвращает наибольший информационный прирост.
Резюме алгоритма;
- Возьмите набор данных
- Определить лучший атрибут в отношении получения информации
- Разделить S на подмножества относительно лучшего атрибута
- Создайте дерево решений, у которого корень имеет лучший атрибут
- Примените те же шаги для нового корня и его новых подмножеств. Если больше нет атрибутов для разделения, выберите самый популярный.
Этот алгоритм работает до тех пор, пока все данные не будут классифицированы/рассеяны.
Что, если два данных имеют один и тот же экземпляр или это одни и те же данные, но два разных данных? Так что, если в наших обучающих данных есть некоторый шум?
Проблема переобучения и недообучения
Проблема переобучения возникает, когда ваша программа идеально моделирует ваши тренировочные данные (в то же время она также изучает шумы), поэтому, когда она пытается классифицировать новые данные, у нее нет необходимых возможностей для их моделирования. Таким образом, мы можем сказать, что ваша программа запоминает тренировочные данные во всех деталях.
С другой стороны, недообучение — это ваша программа, которая не моделирует данные обучения и не обобщает их. Таким образом, в основном он не мог учиться на данных обучения.
Мы можем решить проблему переобучения с помощью нескольких методов;
- Перекрестная проверка: в этом методе вы разделяете данные обучения на небольшие части обучения и тестирования. Таким образом, вы можете легко настроить свою программу.
- Сокращение: вы можете уменьшить размер дерева, удалив некоторые избыточные части дерева, которые не помогают классифицировать данные. Другими словами, вы удаляете из дерева ненужные шумовые части.
Совет: попробуйте начать с простых моделей. При переходе с более простой модели будет легко определить дорогу программы. ("Бритва Оккама")
Поскольку основная проблема заключается в обучении для решения проблемы недообучения, чтобы преодолеть это, вы можете увеличить тренировочный набор, время обучения и повысить сложность своих тренировочных данных.
В этой статье я хотел кратко объяснить дерево решений и алгоритм ID3, которые я только что изучил. То, что я освещал, является очень поверхностной информацией по этим вопросам. Если вы хотите узнать больше об этих темах, я настоятельно рекомендую вам посетить источники в разделе ссылок.
использованная литература
- opendatasceince.com — Полное руководство по деревьям решений
- towardsdatascience.com — Энтропия: как деревья решений принимают решения
- Машинное обучение Udacity от Georgia Tech Course
- Машинное обучение Udacity от статьи курса Georgia Tech
- elitedatascience.com — Переобучение в машинном обучении: что это такое и как этого избежать
