Деревья решений являются популярным методом контролируемого обучения по целому ряду причин. Преимущества деревьев решений заключаются в том, что их можно использовать как для регрессии, так и для классификации, их легко интерпретировать и они не требуют масштабирования признаков. У них есть несколько недостатков, в том числе склонность к переоснащению.

Содержание

  1. Что такое деревья решений?
  2. Геометрическая интуиция деревьев решений.
  3. Энтропия.
  4. Информационная выгода.
  5. Примесь Джини.
  6. Пример набора данных Play Tennis с деревом решений.
  7. Этапы построения дерева решений.
  8. Регрессия дерева решений.
  9. Реальные случаи дерева решений.
  10. Лучшие и худшие случаи алгоритма дерева решений.
  11. Дерево решений с Amazon Food Reviews.

Что такое деревья решений?

Деревья решений, также известные как деревья классификации и регрессии (CART), были введены Лео Брейманом для обозначения алгоритмов дерева решений. У них есть контролируемый алгоритм обучения с предопределенной целевой переменной, и они в основном используются в нелинейном принятии решений с простой линейной поверхностью принятия решений. Другими словами, они могут быть адаптированы для решения любой задачи (классификации или регрессии).

Одним из лучших и наиболее часто используемых методов обучения с учителем являются древовидные алгоритмы.Онирасширяют прогностическое моделирование с большей точностью, большей стабильностью и обеспечивают простоту интерпретации. В отличие от методов линейного моделирования, они довольно хорошо отображают нелинейные отношения. Такие методы, как деревья решений, случайный лес, повышение градиента, широко используются во всех видах задач науки о данных. Следовательно, для каждого аналитика важно изучить эти алгоритмы и применять их во время моделирования.

Геометрическая интуиция деревьев решений

На изображении ниже показана простая реализация различных узлов в дереве решений.

  • Корневой узел. Он представляет всю совокупность или выборку, которая в дальнейшем делится на два или более однородных набора.
  • Разделение. Это процесс разделения узла на два или более подузлов.
  • Узел принятия решения. Когда подузел разделяется на дополнительные подузлы, он называется узлом принятия решения.
  • Листовой (или) конечный узел: узлы, которые не разделяются, называются конечными или конечными узлами.
  • Сокращение. Когда мы удаляем подузлы узла принятия решений, этот процесс называется сокращением.
  • Ветвь (или) поддерево. Подраздел всего дерева называется ветвью (или) поддеревом.
  • Родительский и дочерний узел. Узел, который разделен на подузлы, называется родительским узлом подузлов, где подузлы являются дочерними по отношению к родительскому узлу.

Давайте теперь посмотрим, как геометрически представлены деревья решений?

Существует несколько алгоритмов, написанных для построения дерева решений, которые можно использовать в соответствии с характеристиками проблемы, которую вы пытаетесь решить. Деревья регрессии используются, когда зависимая переменная является непрерывной, а деревья классификации используются, когда зависимая переменная является категориальной.

Ниже приведено простое дерево решений набора данных IRIS. a и b – длина чашелистика и лепестка соответственно.

Мы можем попеременно думать, что деревья решений — это группа вложенных условий IF-ELSE, которые можно смоделировать как дерево, в котором решение принимается во внутреннем узле, а выходные данные получаются в конечном узле.

Геометрически мы можем думать о деревьях решений как о наборе ряда параллельных осей гиперплоскостей, которые делят пространство на количество гиперкубоидов во время вывода.

мы можем видеть, что на приведенном выше изображении границы решения параллельны оси и имеют поверхность решения для каждого конечного узла (Yi).

Простой пример дерева решений для игры в теннис выглядит так…… В любом сценарии, где обучающие данные имеют следующие черты:

  • Данные обучения имеют пару значений атрибута, как в примере, показанном выше: Ветер как атрибут имеет два возможных значения — сильный или слабый.
  • Целевая функция имеет дискретный выход. Здесь целевая функция заключается в том, стоит ли вам играть в теннис? И вывод на этот дискретный вывод: Да и Нет

Когда мы применяем алгоритм дерева решений к набору данных ……… Это выглядит так

Изображение выше сообщает нам о корневом узле, поскольку прогноз пасмурный, тогда мы можем играть, если прогноз солнечный и влажность нормальная, мы можем играть в теннис, но когда влажность высокая, мы не можем играть в теннис, то же самое будет обработано.

Создание дерева решений — это всего лишь вопрос выбора того, какой атрибут следует тестировать в каждом узле дерева. Принимая во внимание, что прирост информации — это мера, которая будет использоваться для принятия решения о том, какой атрибут (или) функция должна быть проверена в каждом узле.

Прирост информации сам по себе рассчитывается с использованием меры, называемой энтропией, которую мы сначала определяем для случая бинарной проблемы принятия решений, а затем определяем для общего случая. Причина, по которой мы сначала определили энтропию для двоичной задачи принятия решений, заключается в том, что легче понять, что она пытается вычислить.

Энтропия

Том Митчелл довольно хорошо формулирует это как:

«Чтобы точно определить прирост информации, мы начнем с определения меры, обычно используемой в теории информации, называемой энтропией, которая характеризует (не)чистоту произвольного набора примеров».

Математически энтропию можно представить как:

Pj: доля выборок, принадлежащих классу C для определенного узла.

Примечание. Это определение энтропии для всех непустых классов (p≠0). Энтропия равна 0, если все образцы в узле принадлежат к одному и тому же классу.

Эта мера удовлетворяет нашим критериям из-за конструкции -p*log2(p): когда p приближается к нулю (т. е. в категории всего несколько примеров ), то log(p) становится большим отрицательным числом, но часть p доминирует в расчетах, поэтому энтропия получается почти нулевой.

Учитывая, что энтропия вычисляет беспорядок в данных, эта низкая оценка хороша, так как отражает наше желание вознаграждать категории несколькими примерами. Точно так же, если p приближается к 1 (т. е. категория содержит большинство примеров), то часть log(p) становится очень близкой к нулю, и снова «p», который доминирует в расчете, поэтому общее значение приближается к нулю.

Следовательно, мы видим, что когда категория почти или полностью пуста, или когда категория почти содержит или полностью содержит все примеры, оценка для категории становится близкой к нулю, что моделирует то, что мы хотели. Обратите внимание, что 0*ln(0) принято равным нулю по соглашению.

Графическое представление энтропии

Получение информации

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

На словах мы также можем определить получение информации следующим образом:

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

В общем случае энтропия максимальна, если все исходы равновероятны для другого, если одни исходы более вероятны, чем другие, то энтропия уменьшается.

Примесь Джини

Примесь Джини можно рассматривать как альтернативу энтропийному методу. Примесь Джини — это мера того, как часто случайно выбранный элемент из набора был бы неправильно помечен, если бы он был помечен случайным образом в соответствии с распределением меток в подмножестве.

Математически это можно представить как:

Вычисление энтропии в методе Джини происходит таким же образом, но энтропия включает в себя логарифмическое вычисление, а примесь Джини включает квадратное вычисление. Поскольку вычисление квадрата дешевле, чем логарифмическая функция, мы предпочитаем примесь Джини энтропии.

На приведенном ниже графике показано, что индекс Джини и энтропия являются очень похожими критериями примесей.

Одними из наиболее популярных алгоритмов являются ID3, C4.5 и CART. Scikit-learn использует оптимизированную версию алгоритма CART. Узнать о временной сложности можно здесь.

Давайте разберемся с примером здесь. Пожалуйста, обратитесь к набору данных для игры в теннис, который вставлен выше.

У нас есть данные за 14 дней. У нас всего два исхода:

Либо мы играли в теннис, либо не играли.

За указанные 14 дней мы играли в теннис 9 раз и 5 раз не играли.

Теперь мы увидим вероятность не играть в теннис.

А теперь энтропия исхода,

Итак, энтропия всей системы до того, как мы зададим наш первый вопрос, равна 0,940.

Теперь у нас есть четыре функции для принятия решения, а именно:

  1. Перспектива
  2. Температура
  3. Ветреный
  4. Влажность

Давайте посмотрим, что произойдет с энтропией, когда мы примем первое решение на основе Outlook.

Если мы выполним разделение дерева решений на этом уровне 0 на основе перспективы, у нас будут три возможные ветви; либо будет солнечно, либо пасмурно, либо будет идти дождь.

  1. Солнечно. Согласно приведенным данным, 5 дней были солнечными. Из этих 5 дней в теннис играли 2 дня, а в теннис не играли 3 дня. При чем тут энтропия?

2. Облачно. Согласно приведенным данным, 4 дня были пасмурными, и все четыре дня играли в теннис. Позволять

3.Дождь: в приведенных данных 5 дней были дождливыми. Из этих 5 дней в теннис играли 3 дня, а в теннис не играли 2 дня. При чем тут энтропия?

Энтропия среди трех ветвей:

Каково уменьшение случайности из-за выбора мировоззрения в качестве лица, принимающего решения?

Это уменьшение случайности называется Поступлением информации. Аналогичный расчет можно сделать и для других функций.

Температура

Прирост информации = 0,029

Ветреный

Прирост информации = 0,048

Влажность

Прирост информации = 0,152

Мы видим, что снижение случайности или получение информации больше всего для Outlook. Итак, мы выбираем первого лица, принимающего решение, в качестве Outlook.

Шаги к построению дерева решений

  1. Создайте список функций, список атрибутов.

Пример: Список функций: прогноз, ветер, температура и влажность.

Атрибуты Outlook: солнечно, пасмурно и дождливо.

2. Найдите максимальный прирост информации среди всех признаков. Назначьте его корневой узел.

Outlook в нашем примере имеет три ветви: Солнечно, Пасмурно и Дождливо.

3. Удалите функцию, назначенную в корневом узле, из списка функций и снова найдите максимальное увеличение прироста информации для каждой ветви. Назначьте функцию дочерним узлом каждой ветви и удалите эту функцию из списка функций для этой ветви.

Корневой узел Sunny Branch для Outlook имеет влажность в качестве дочернего узла.

4. Повторяйте шаг 3, пока не получите ветки только с чистым листом.

В нашем примере либо да, либо нет.

Для получения дополнительной информации посетите здесь.

Критерий остановки

Если мы продолжим полностью наращивать дерево до тех пор, пока каждый конечный узел не будет соответствовать наименьшей примеси, то данные, как правило, будут переобучены.

Если разделение будет остановлено слишком рано, ошибка в обучающих данных будет недостаточно высока, и производительность пострадает из-за bais. Таким образом, предотвращение переобучения и недообучения имеет ключевое значение при моделировании дерева решений, и это можно сделать двумя способами.

  1. Установка ограничений на размер дерева
  • Предоставление минимального количества выборок для разделения узла.
  • Развертывание минимального количества образцов для терминального узла (листа).
  • Разрешение максимальной глубины дерева (глубина по вертикали).
  • Максимальное количество конечных узлов.
  • Максимальное количество функций для раскола.

2. Обрезка деревьев

обрезка– это метод машинного обучения, которыйуменьшает размер деревьев решений путем удаления разделов дерева. Это также снижает сложность окончательного классификатора и, следовательно, повышает точность прогнозирования за счет уменьшения переобучения.

Обрезка деревьев может быть выполнена двумя способами: предварительной обрезкой или последующей обрезкой.

предварительная обрезка:

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

Постобрезка:

  • Это можно сделать, сначала позволив дереву вырасти до своего полного потенциала, а затем обрезав дерево на каждом уровне после расчета точности перекрестной проверки на каждом уровне.

Где мы можем использовать деревья решений (какие проблемы)?

Деревья решений можно использовать как в задачах регрессии, так и в задачах классификации. Методы реализации сильно различаются, поскольку задачи регрессии имеют действительные числа в качестве целевых переменных, тогда как задачи классификации имеют двоичные или дискретные целевые переменные.

Регрессия

В регрессии решение о стратегическом разделении сильно влияет на точность дерева. Критерии принятия решений различаются для деревьев классификации и регрессии. Регрессия деревьев решений обычно использует среднеквадратичную ошибку (MSE), чтобы принять решение о разделении узла на два или более подузлов.

Предположим, мы делаем двоичное дерево, алгоритм сначала выберет значение и разделит данные на два подмножества. Для каждого подмножества он будет рассчитывать MSE отдельно. Дерево выбирает значение с наименьшим значением MSE.

Давайте более подробно рассмотрим, как выполняется разделение для регрессора деревьев решений. Первым шагом к созданию дерева является создание первого бинарного решения. Как вы собираетесь это делать?

  • Нам нужно выбрать переменную и значение для разделения таким образом, чтобы две группы максимально отличались друг от друга.
  • Для каждой переменной, для каждого возможного значения возможного значения этой переменной посмотрите, лучше ли оно.
  • Как определить, что лучше? Возьмите средневзвешенное значение двух новых узлов (mse*num_samples).

Подводя итог, мы имеем:

  • Одно число, которое представляет, насколько хорошим является разделение, является средневзвешенным значением среднеквадратичных ошибок двух групп, которые создают.
  • Способ найти наилучшее разделение, которое состоит в том, чтобы попробовать каждую переменную и попробовать все возможные значения этой переменной и посмотреть, какая переменная и какое значение дает нам разделение с лучшим результатом.

Это весь процесс создания регрессора дерева решений, который остановится, когда будет выполнено некоторое условие остановки (определяемое гиперпараметрами):

  • Когда вы достигаете запрошенного лимита (например, max_depth)
  • Когда в ваших листовых узлах есть только одна вещь (дальнейшее разделение невозможно, MSE для поезда будет нулевым, но будет соответствовать любому другому набору - не полезная модель)

Простая схема показана ниже.

Разделение числовых признаков

Разделение числовых признаков может быть выполнено путем сортировки признаков в порядке возрастания и использования каждого значения в качестве пороговой точки, а также вычисления прироста информации для каждого значения в качестве порога. Наконец, если это полученное значение равно порогу, который дает максимальное значение прироста информации, то ура..!

Масштабирование функций.Масштабирование функций (или) стандартизация столбцов не требуется для выполнения в деревьях решений. Потому что дерево решений — это не метод, основанный на расстоянии, как SVM.

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

Несбалансированный набор данных. Несбалансированный классоказывает вредное влияние на структуру дерева, поэтому его можно избежать, используя повышающую или понижающую дискретизацию в зависимости от набор данных.

Мультиклассовая классификация: дерево решений. Естественно, он выполняет мультиклассовую классификацию. Мы также можем использовать один метод v/s Rest.

Поверхность решения: поверхность решения представляет собой гиперкубоид, параллельный оси.

Матрица подобия.Дерево решений нуждается в функциях явно и не работает в матрицах сходства.

Большая размерность.Помимо искаженных классов, высокая размерность также может отрицательно сказаться на структуре дерева, если размерность очень высока, что означает у нас есть много функций, а это означает, что поиск критерия разделения на каждом узле займет много времени.

Влияние выбросов.Выбросы также влияют на структуру дерева, поскольку с увеличением глубины увеличивается вероятность появления выбросов в дереве.

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

Лучшие и худшие случаи алгоритма дерева решений

  1. Деревья решений по своей сути могут выполнять мультиклассовую классификацию.
  2. Они обеспечивают наибольшую интерпретируемость модели, потому что представляют собой просто ряд условий if-else.
  3. Они могут обрабатывать как числовые, так и категориальные данные.
  4. Нелинейные отношения между функциями не влияют на производительность деревьев решений.
  5. Небольшое изменение в наборе данных может сделать древовидную структуру нестабильной, что может привести к дисперсии.
  6. Изучающие деревья решений создаютнедообучаемые деревья, если некоторые классы несбалансированы. Поэтому рекомендуется сбалансировать набор данных перед подгонкой под дерево решений.

Дерево решений с обзорами продуктов питания Amazon

Давайте применим алгоритм дерева решений к реальному набору данных Amazon Fine Food Review Analysis от Kaggle.

Сначала мы хотим узнать, что такое анализ Amazon Fine Food Review?

Этот набор данных состоит из обзоров изысканных продуктов от Amazon. Данные охватывают период более 10 лет, включая все ~500 000 обзоров до октября 2012 года. Обзоры включают информацию о продуктах и ​​пользователях, рейтинги и обзоры в текстовом виде. У нас также есть обзоры из всех других категорий Amazon.

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

Источник: https://www.kaggle.com/snap/amazon-fine-food-reviews

Набор данных Amazon Fine Food Reviews состоит из обзоров изысканных продуктов от Amazon.

Количество отзывов: 568 454
Количество пользователей: 256 059
Количество товаров: 74 258
Период времени: октябрь 1999 г. — октябрь 2012 г.
Количество атрибутов/столбцов в данных: 10

Информация об атрибутах:

  1. Id
  2. ProductId — уникальный идентификатор товара.
  3. UserId — уникальный идентификатор пользователя
  4. Имя профиля
  5. HelpfulnessNumerator — количество пользователей, которым отзыв был полезен.
  6. HelpfulnessDenominator — количество пользователей, которые указали, считают ли отзыв полезным или нет.
  7. Score — оценка от 1 до 5
  8. Time — временная метка обзора.
  9. Резюме — Краткое изложение обзора
  10. Текст — Текст обзора

Цель

Учитывая отзыв, определите, является ли он положительным (рейтинг 4 или 5) или отрицательным (рейтинг 1 или 2).

Предварительная обработка данных

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

Чтобы узнать полный обзор набора данных обзора продуктов питания Amazon и характеристик, посетите мою предыдущую ссылку в блоге здесь.

Сплит Train-Test

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

Если у вас есть один набор данных, вам нужно сначала разделить его с помощью функции Sklearn train_test_split.

Обозначение текста с помощью Bag of Words

Настройка гиперпараметров

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

мы уже определили функцию Grid_search, когда мы ее вызываем, она даст результат.

После того, как мы найдем лучшие параметры с помощью CV поиска в сетке, мы хотим проверить производительность с помощью тестовых данных, в этом случае мы используем AUC в качестве показателя производительности.

мы уже определили функцию для проверки тестовых данных, когда мы ее вызовем, она даст результат.

Показатели эффективности

Показатели производительности используются для измерения поведения, деятельности и эффективности бизнеса. Это должно быть в форме данных, которые измеряют требуемые данные в пределах диапазона, позволяя сформировать основу, поддерживающую достижение общих бизнес-целей.

Чтобы узнать подробную информацию о показателях производительности, используемых в машинном обучении, посетите мою предыдущую ссылку в блогездесь.

мы уже определили функцию для показателей производительности, когда мы ее вызываем, она даст результат.

Важность функции на BOW

Топ-20 важных функций

Визуализация Graphviz дерева решений BOW Features

Точно так же мы построили модель дерева решений с функциями TFIDF, AvgWord2Vec, TFIDF_AvgWord2Vec. Чтобы понять полный код, перейдите по моей ссылке GitHub.

Выводы

Для записи сотрясений в таблицу мы использовали библиотеку Python PrettyTable.

The pretty table — это простая библиотека Python, предназначенная для быстрого и простого представления табличных данных в визуально привлекательных таблицах.

Наблюдения

  1. По сравнению со всеми другими представлениями функций, функции Bag of words с глубиной 50 и min_split 500 получают самые высокие оценки AUC 80,65% на тестовых данных.

2. Оптимальные значения Depth и Min_split из Grid_search_CV различаются от модели к модели.

Чтобы узнать полный обзор набора данных обзора продуктов питания Amazon и характеристик, посетите мою предыдущую ссылку в блоге здесь.

Чтобы узнать подробную информацию о показателях производительности, используемых в машинном обучении, посетите мою предыдущую ссылку в блогездесь.

Чтобы понять полный код, перейдите по моей ссылке GitHub.

использованная литература

  • Прикладной ИИ
  • Википедия
  • Курсера
  • Лагерь данных

Спасибо за чтение и ваше терпение. Надеюсь, вам понравился пост, дайте мне знать, если в моем посте есть ошибки. Давайте обсудим в комментариях, если вы нашли что-то не так в посте или у вас есть что добавить…

Счастливого обучения!!