www.machinelearningmastery.ru

Машинное обучение, нейронные сети, искусственный интеллект
Header decor

Home
Занимательная история, выдающиеся люди, малоизвестные факты, находки, открытия, фальсификации. Присоединяйся!

Интуитивно понятное руководство по пониманию деревьев решений

Дата публикации Nov 29, 2018

Предоставлено Pixabay.com

Введение

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

Заметка: Эта статья стоит за Medium Paywall. Однако код с открытым исходным кодом, и может быть доступен из этогоссылка,

Заметка 2: Это пятый пост в сериисвет на математике машинного обучения A-Z, Вы можете найти предыдущие сообщения в блоге, связанные с письмом ниже.

A BСD E Fг* H I JКL* МNO P Q R S T U VWX Y Z

* обозначает статьи за Средним платным доступом

Почему эта статья?

Давайте сделаем шаг назад! Зачем вам читать эту статью, когда есть так много статей, объясняющих деревья решений? Следует подчеркнуть, что, в отличие от статей, которые я нашел в Интернете, эта статья не остановится на объяснении высокого уровня и не оставит читателя в покое. Напротив, я постараюсь,

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

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

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

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

Почему деревья решений?

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

мусор внутри, мусор вне!

Деревья решений велики в том смысле, что

  • Они легкоинтерпретируемыхи следует аналогичному образцу человеческого мышления. Другими словами, вы можете объяснить дерево решений как набор вопросов / бизнес-правил.
  • Предсказаниебыстро, Это набор операций сравнения, пока вы не достигнете конечного узла
  • Может быть адаптирован для решенияотсутствуют данныебез вменения данных

Пример по деревьям решений:

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

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

Пример дерева решений. Круглые узлы обозначают узлы решения, где квадратные узлы обозначают конечные узлы

Компоненты дерева решений

Позвольте мне дать вам краткий урок анатомии дерева решений. Дерево имеет узлы решений (округление), решения (ребра) и узлы листа / прогнозирования (квадрат). Сначала вы начинаете с узла принятия решений (например, Outlook), и в зависимости от ответа у вас может быть конечный узел или другой узел принятия решений (например, Windy). Дерево решений может использоваться для произвольного числа узлов решений. Однако каждая ветвь должна заканчиваться листовым узлом.

Прогнозирование с помощью дерева решений

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

Прогноз = Солнечно, Температура = Жарко, Влажность = Нормально, Ветрено = Истинно

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

Думаю, ты не играешь в гольф.

Строим дерево

Конечно, есть еще более важный вопрос, который все еще остается

Как мы можем прийти к этому дереву?

Важнее,

Как мы можем определить лучшие данные раздела функций на заданной глубине?

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

  • КОРЗИНА(Деревья классификации и регрессии) - ИспользованиеКоэффициент Джинирешить функцию раздела
  • ID3(Использует получение информации - обсуждается позже, для определения функции раздела, ине предназначен для работы с непрерывными функциями)
  • C4.5(Работает аналогично ID3, используя прирост информации для разделения данных. Однако C4.5может обрабатывать непрерывные функции, так же какможет работать с отсутствующими данными)

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

Найти замаскированного короля на улицах

(Данные и особенности)

Начиная с этого раздела, я собираюсь объяснить деревья решений историей короля TreeLand, который любил обманывать местных жителей, маскируя себя на улицах. Это раздражало, потому что всякий раз, когда кто-то непреднамеренно плохо обращался с королем, он был наказан. Люди были очень недовольны, и один мудрец (назовем его Джоном) подошел и сказал, что может решить это за 10 дней!

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

  • Выходит из замка
  • Идет медленно
  • Ест 5 или более раз в день
  • Имеет золотой зуб

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

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

  • Зеленый - если атрибут соответствует соответствующей метке
  • Красный - если атрибут не соответствует соответствующей метке
Доска Джона

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

Резюме наблюдений из выделенных таблиц

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

Получение информации: сколько информации получено путем разделения данных?

Мы уже обсуждали, что основная идея дерева состоит в том, чтобы задать вопрос (то есть проверить данные по атрибуту) и разделить данные в зависимости от ответа (например, True или False). Получение информации измеряет, насколько предсказуемыми стали данные (или насколько больше информации было получено) путем разделения данных в соответствии с ответом, предоставленным в узле принятия решений. Наденьте свои научные очки, время оформить. Информация, полученная с помощью функции F для данных Y, определяется следующим образом:

IG (Y, F) = H (Y) -H (Y | F)

гдеYцелевая переменная иFэто какая-то особенность (например, Золотой Зуб). Таким образом, чем мощнее функция, тем больше информации можно получить, разделив данные по этой функции. H (Y) - энтропия Y, а H (Y | F) - условная энтропия Y, обусловленная на F (обсуждается в ближайшее время). В коде вычисление выигрыша информации выглядит следующим образом.

Давайте теперь посмотрим, что такое энтропия и условная энтропия.

Энтропия и условная энтропия

Энтропия измеряет, сколько бит требуется для преобразования данных. Таким образом, чем более предсказуемы ваши данные, тем меньше требуется нужных битов. Напротив, чем менее предсказуемы ваши данные, тем больше бит вам нужно. Это записано следующим образом:

где (y в Y) обозначает уникальные результаты в Y (например, является King = True или False в нашем примере). Вы можете реализовать это в Python довольно легко.

Энтропия с точки зрения непрофессионала

Давайте разберемся в энтропии более интуитивно. Скажем, король решил никогда не обманывать местных жителей, а Джон решил собрать данные, чтобы решить эту проблему. У него была бы нулевая энтропия. Зачем? Потому что метка предсказуема на 100% (то есть всегда 0). Но, по нашим данным, энтропия находится на самом высоком уровне (т. Е. 1), потому что существует равная вероятность того, что человек будет королем или нет.

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

Разница разных значений энтропии

Условная энтропия с точки зрения непрофессионала

Это создает основу для того, чтобы объяснить, что такое условная энтропия (т.е. H (Y | F) Представьте, что теперь, для каждого назначения данных, Джон говорит, был ли у человека Золотой Зуб или нет. Затем, в зависимости от значения признака (то есть F), Лиза должна предсказать, был ли это король или нет. Если вы посмотрите на таблицу ниже, данные теперь более предсказуемы, чем отсутствие каких-либо функций.

С доски Джона

Таким образом, то, что делает получение информации, это то, что

он измеряет разницу в предсказуемости до и после предоставления информации о функцииF,

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

IG (Y, F) = H (Y) -H (Y | F)

Тем временем в TreeLand ...

(Строим дерево)

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

Дерево с надписью «Замок»

Он счастлив с левой стороны. Он считает, что «классификация 4/6 - это не плохо». Учитывая, что у него всего 10 точек данных, мы немного ослабим его. Но результаты с правой стороны плохие (т. Е. 50% верно или 50% неверно). Ему нужно улучшить результаты, поэтому он идет вперед и пытается разделить остаток слева, используя функцию, которая дает максимальный прирост информации, который оказывается «Золотой Зуб»И получает следующее.

Дерево с функциями «Замок» и «Золотой Зуб»

Итак, поехали! Джон нашел секретный соус! Это на самом деле, какАлгоритм ID3работает. Более формально у вас будет следующий псевдокод.

Peseudocode

Наиболее важной функцией в этом коде будетbuild_treeкоторый на самом деле будет выглядеть так (доступно вкод).

Граждане Триленда могут снова расслабиться ...

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

Дерево выросло слишком много ...

(Переоснащение и регуляризация)

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

Новое дерево решений

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

Давайте вернемся и исправим ошибки Джона

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

  • Убедиться, что каждый листовой узел имеет хотя быNточки данных
  • Убедиться, что глубина дерева не превышаетd
  • Убедиться, что прирост информации превышает пороговое значение для разделения

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

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

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

Итак, после пересмотра этих методов и применения их к модели, Джон придумал следующую модель, которая более объяснима.

Упорядоченное дерево

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

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

Работа с непрерывными значениями

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

  • Дискретизируйте непрерывный элемент путем объединения диапазона непрерывного элемента в равные ячейки
  • Используйте «минимальное энтропийное разбиение[2] чтобы найти раскол в непрерывной функции

Минимальное энтропийное разбиение

Минимальное энтропийное разбиение (MEP) работает следующим образом.

  • Сначала вы назначаете набор точек среза в зависимости от диапазона, в котором распространяются данные (например, диапазон среза в точках с одинаковым разбросом)
  • Затем для каждой точки разреза вычислите взвешенную сумму энтропии метки Y
  • Выберите точку среза, которая дает минимальную энтропию

Заворачивать

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

Сначала мы кратко обсудили функциональность дерева решений, используя в качестве примера игрушечный набор данных о погоде. Затем мы подскочили к более оживленной проблеме, которая заключалась в том, чтобы определить, действительно ли раздражающий Король TreeLand наводит ужас на улицы. Мы увидели, как Джон использовал сбор информации для идентификации функций, которые могут помочь идентифицировать короля, и впоследствии построил дерево, используя эти функции. После этого мы увидели, как возникали такие проблемы, как «переоснащение», когда набор данных становился больше. Мы также обсудили, как можно избежать переоснащения, используя различные методы регуляризации (например, ограничение максимальной глубины дерева). Наконец, мы завершили приключение в TreeLand и быстро ознакомились с тем, как можно обрабатывать непрерывные функции в деревьях решений.

Код для этой статьи доступенВот,

Ссылка

[1]Конспект лекций из КМУ

[2]Многоинтервальная дискретизация непрерывнозначных атрибутов для обучения классификации

Видео с канала Google Developers Youtube
Видео из Стэнфорда

Оригинальная статья

Footer decor

© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map