Взгляд на деревья и то, как они используются для разработки сложных и простых алгоритмов машинного обучения.
Следующая статья представляет собой попытку упростить понимание того, как деревья используются в машинном обучении, и сделать ее более сжатой, объединив популярные и информативные статьи и видеоролики по этому вопросу. Я использую информацию из различных статей, постов в блогах и видео, которые я не хочу заявлять как свои собственные. Итак, если вы хотите более подробно изучить темы, обсуждаемые в этой статье, я прикрепил ссылки на исходные сообщения в конце.
О каких деревьях идет речь?
Если вы хотите подробно изучить древовидные структуры данных и то, как они работают, я бы порекомендовал прочитать статью Vaidehi Joshi о деревьях и их свойствах. Тем не менее, я дам вам краткий обзор деревьев, в частности деревьев решений, и того, как они работают.
Важным свойством деревьев в целом является то, что они состоят из узлов и меньших поддеревьев (ветвей), обладающих теми же свойствами дерева, к которому они подключены, что делает рекурсию полезным инструментом для работы с ними. Это важно для их использования в машинном обучении, но мы вернемся к этому позже.
Эти свойства специфичны для деревьев и вполне соответствуют их названиям и включают в себя ребра, листовые узлы, высоту и глубину. Ребра — это соединение между узлами. Листовые узлы — это узлы, не имеющие дочерних узлов. Высота — это количество ребер от узла до корня. Глубина — это количество ребер от узла до его самого глубокого дочернего элемента. Вот изображение того, о чем я говорю.
Самое большое свойство деревьев, которое отделяет их от других структур данных на основе узлов, таких как связанные списки, стеки и очереди, заключается в том, что они могут быть пройдены нелинейным способом. Это означает, что вместо того, чтобы переходить от первого элемента в списке к следующему, пока вы не дойдете до конца, деревья могут начинаться в середине и идти либо влево, либо вправо в зависимости от того, что ищется. Это позволяет очень быстро перемещаться, если дерево создано правильно, но я перенаправлю вас обратно в Vaidehi, чтобы узнать больше о том, как это работает.
Что такое деревья решений?
Деревья решений — это особый тип дерева, который в основном используется, как вы уже догадались, для принятия решений! Хотя, чтобы быть более конкретным для ML, они используются для классификации относительно больших наборов данных, которые не слишком сильно меняются.
Хороший способ думать о дереве решений — это блок-схема. Вы следуете таблице и, как правило, получаете результат, который помогает вам принять решение.
Что особенного в деревьях решений с точки зрения машинного обучения (ML), так это то, что они создают сами себя.
Как они используются в ML?
Деревья решений в основном используются для двух типов машинного обучения; Классификация и регрессия. CART – это общий термин для них, аббревиатура от Дерево классификации и регрессии.
CART представлен в виде двоичного дерева и использует входные данные и точки разделения для создания самого себя. ML появляется, когда он вычисляет, какие входные точки и точки разделения использовать, и может быть известен как жадное разделение, лучшее разделение и т. д.
Жадное разделение
Жадное разделение — это когда вы тестируете разные точки разделения на входе, чтобы получить лучшие точки разделения для обучающих данных. Для этого нам нужна функция стоимости, которая сравнивает все возможные точки разделения и их результат и выбирает лучший из них.
Одна функция стоимости включает использование примеси Джини; вероятность того, что текущее разбиение будет ошибочным, и прирост информации; полное сведение к примесям для нахождения наилучшего разбиения данных.
Остановка создания и сокращения
К счастью, остановить создание дерева решений довольно просто, потому что мы мало в него вкладываем. По сути, поскольку мы используем рекурсию, дерево само создастся, когда закончатся данные для разделения. Мы также можем обрезать дерево, чтобы получить лучшие результаты, и это включает в себя просмотр дерева вручную и наблюдение за тем, как удаление листа влияет на результаты, и удаление их, если оно положительное, и сохранение их, если это не так.
В основе жадного разбиения лежит рекурсивное бинарное разбиение, и, как я уже говорил ранее, деревья упрощают реализацию рекурсии.
Как мы создаем дерево решений?
Чтобы показать вам, как составить дерево решений, мы будем использовать язык программирования Python.
примесь Джини
Чтобы получить примесь Джини, нам нужно рассчитать вероятность того, что заданный ввод будет угадан неправильно. Итак, скажем, у нас есть группа из трех человек, один из которых любит игры, другой занимается спортом, а последний занимается искусством, и мы сейчас ищем того, кто любит игры. Вероятность его случайной правильной классификации составляет 1/3, что делает примесь Джини равной 70%. Приведенный ниже код представляет собой функцию, которая вычисляет примесь Джини для набора данных.
Прирост информации
Прирост информации - это довольно простое уравнение, которое включает в себя среднюю нечистоту разделения данных и вычитание ее из общей нечистоты данных. Функция ниже выполняет это уравнение.
Разделение данных
Теперь, когда у нас есть способ получить примесь Джини и прирост информации, мы можем перейти к разделению данных. Для этого нам нужна функция, которая проверяет все возможные разбиения и находит наилучшее, разбивая на основе каждого значения, вычисляя примесь Джини для каждого разбиения значений, затем вычисляя прирост информации для разбиений и возвращая результат с наибольший информационный прирост.
Объединяя все это
Чтобы построить/вырастить дерево, нам потребуется рекурсивно разделить данные до тех пор, пока не останется дисперсии данных, поскольку мы делаем это, нам нужно рекурсивно создать ветвь для истинной классификации и ветвь для ложной классификации, которая также создает листовые узлы/узлы решений, которые будут решать, какой это случай, когда входные данные проходят через дерево. Это можно сделать с помощью функции ниже.
Использование дерева, которое мы создали
Теперь, когда у нас есть способ построить дерево решений, нам нужно иметь возможность делать с его помощью прогнозы.
Чтобы делать прогнозы с нашим деревом, мы рекурсивно делаем прогнозы для узлов дерева на входе. При этом мы проверяем наличие узлов решений, и если мы находим их, мы возвращаем их решение для классификации/прогнозирования.
Подведение итогов
На протяжении всей статьи мы рассмотрели, что такое деревья и деревья решений, как они используются в ML, как их создавать в python и как они делают на их основе прогнозы. Я надеюсь, что эта статья вас чем-то затруднила, но если вы все еще не понимаете, как все работает, я настоятельно рекомендую ознакомиться со статьями ниже.
Ресурсы
Если вам интересно глубже изучить некоторые идеи, о которых я говорил, ознакомьтесь с этими ресурсами, которые помогли мне написать эту статью.
- Как не попасть в тупик перед деревьями, Вайдехи Джоши
- Дерево решений, GeekForGeeks
- Деревья решений — простой способ визуализировать решение, Раджеш С. Брид
- Деревья классификации и регрессии для машинного обучения, MachineLearningMastery
- Давайте напишем классификатор дерева решений с нуля, Google Developers
