Погружение в деревья решений

Погружение в деревья решений

Как работают деревья решений?

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

Деревья решений

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

Классификация

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

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

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

В корневом узле мы используем «Feat 2 ≥3» в качестве условия для первого разделения нашего набора данных. Мы можем увидеть, является ли ответ ложным, мы достигаем листа, в котором есть только записи с меткой 3. Итак, метка 3 полностью отделена. Но, если ответ «Истина», мы достигаем промежуточного узла. В этом случае есть 3 записи, 2 из которых относятся к метке 2, а одна - к метке 1. Таким образом, этот результат имеет примеси, так как смешаны две метки. Применяем еще одно условие к промежуточному состоянию и получаем чисто разделенные метки. На листе 2 мы получили только запись с меткой 1, а на листе 3 у нас есть только записи с меткой 2.

Теперь могут возникнуть следующие вопросы:

1. Как мы фиксируем решающее значение в случае числовых признаков, например, «feat 2≥3»?
2. Как мы решаем, какие функции мы должны использовать для создания наших внутренних узлов условий?
3. Как решить, какую функцию использовать в первую очередь, например, в предыдущем случае у нас была функция 1 и функция 2, поэтому какую функцию мы должны использовать в качестве корневой?

Мы увидим ответы на эти вопросы по мере продвижения вперед.

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

Энтропия: дает меру примеси или случайности в данных. Это дает:

Энтропия = - P (класс 1) x Log (P (класс 1)) - P (класс 2) x Log (P (класс 2))

где P обозначает вероятность.

Если есть два класса, класс 1 и класс 2, равных чисел, т. Е. Количество записей класса 1 равно количеству записей класса 2, и мы случайным образом выбираем запись, она будет принадлежать любому классу 1. или 2 с вероятностью 50% каждый. В таких случаях энтропия будет высокой.

Если в определенном наборе данных есть все данные, принадлежащие классу 1 или 2, полученная энтропия равна 0, так как в этом случае P (class1) или P (class2) будет равно 0. Если P (class1) = 0, то P (class2) должен быть равен 1. Таким образом, очевидно, что энтропия будет высокой, если у нас есть нечистые или смешанные метки классов в наборе данных.

На приведенной выше диаграмме показано изменение вероятности меток в зависимости от энтропии. Мы можем видеть, если вероятность метки равна 0,5, энтропия максимальна.

Если в наборе данных всего 20 записей или строк, 14 из которых относятся к метке 1, а 6 из них относятся к метке 2, энтропия будет равна:

= - P (метка 1) .log (P (метка 1)) - P (метка 2) .log (P (метка 2))

= - 14 / 20.log (14/20) - 6 / 20.log (6/20)

=0.880

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

Это дает:

Прирост информации = энтропия (ы) - [(средневзвешенное значение) x (энтропия каждой функции)

Итак, как это на самом деле работает?

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

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

Например, для функции 1,

Мы можем увидеть, если выберем условие «Feature 1 == 2», мы сможем успешно отделить метку 2 от набора данных в чистом виде.

Теперь энтропия (E (s)) = - 4/10 * журнал (4/10) - 6/10 * журнал (6/10) = 0,97

Для функции 1:

E (feature_1 == 1) = - 3/4 * журнал (3/4) - 1/4 * журнал (1/4) = 0,81

E (feature_1 == 2) = - 3 / 3log (3/3) = - 1log1 = 0

E (feature_1 == 3) = - 2/3 * журнал (2/3) - 1/3 * журнал (1/3) = 0,91

Для Признака 1 средневзвешенное значение =

4/10*0.81+3/10*0+3/10*0.91=0.597

Информационное усиление = 0,97–0,597 = 0,313

Опять же, давайте сделаем то же самое для функции 2:

Для функции 2:

Для функции 2:

E (feature_2 == 1) = - 2/3 * журнал (2/3) - 1/3 * журнал (1/3) = 0,91

E (feature_2 == 2) = - 2/3 * журнал (2/3) - 1/3 * журнал (1/3) = 0,91

E (feature_2 == 3) = - 3/4 * журнал (3/4) - 1/4 * журнал (1/4) = 0,81

Для Признака 2 средневзвешенное значение =

3/10*0.91+3/10*0.91+4/10*0.81=0.87

Таким образом, информационная выгода для признака 2 = 0,97–0,87 = 0,1.

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

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

Это дает:

Примесь Джини = 1 - (Вероятность «Класса 1») ² - (Вероятность «Класса 2») ²

Посмотрим, как он работает,

Скажем, это наше распределение по набору данных из 100 записей. Условие, примененное к функции 1, дает вышеуказанный вывод.

Примесь Джини листа 1: 1– (35/43) ² - (8/43) ² = 0,302

Примесь Джини листа 2: 1 - (15/57) ² - (42/57) ² = 0,38

Теперь общая примесь Джини для Признака 1:

Средневзвешенное значение примеси Джини:

=43/100* 0.30+ 57/100*38=0.34

Аналогичным образом мы рассчитываем индекс примеси Джини и для других характеристик.

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

Примесь Джини: 1- (1 / (0 + 1) ²) - (0 / (0 + 1) ²) = 0

Итак, мы можем видеть, что для чистого распределения индекс примеси Джини равен 0.

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

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

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

Скажем, мы получили средние значения, как показано выше. Итак, avg_1 = (val_1 + val_2) / 2. Затем мы подбираем средние значения в условии, чтобы проверить, какое из них обеспечивает минимальный индекс примеси Джини или которое обеспечивает максимальный информационный выигрыш, в зависимости от используемых нами методов. Среднее значение служит пороговым значением в нашем условии, сформированном для характеристики.

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

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

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

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

Регресс

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

Давайте рассмотрим два условия:

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

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

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

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

Допустим, у нас есть набор функций, состоящий из трех функций: Feature 1, Feature 2 и Feature 3.

Давайте рассмотрим приведенное выше изображение как наше распределение для признака 1. По оси Y указаны значения, по которым нам нужно сопоставить регрессию, а по оси X - значения признаков. Итак, мы рассматриваем значения, показанные на диаграмме как Val 1, Val 2 и т. Д., Как значения отсечения для формирования условия для Feature 1. Эти значения являются не чем иным, как средним значением значений Feature 1 двух соответствующих точек. Теперь посмотрим, как продвигаются вычисления.

Теперь рассмотрим приведенные выше диаграммы. Диаграммы не в масштабе, поэтому avg_2 не равно avg_4. Когда мы рассматриваем val_1 как пороговое значение для функции 1, мы берем средние значения всех значений Y для точек слева от линии как avg_1, и аналогично мы берем средние значения всех точек для справа от строки как avg_2. Таким образом, для любого значения, для которого свойство условия 1 ›val_1 имеет значение True, дерево предоставляет avg_2 в качестве прогноза и наоборот.

Затем мы возьмем квадраты ошибок для всех точек. Таким образом, для любой точки справа от линии квадрат ошибки точки равен (фактическое значение - прогнозируемое значение (т. Е. Avg_2)) ², и аналогично для любой точки слева квадрат ошибки точки равен (фактическое значение - прогнозируемое значение (т.е. avg_1)) ². Итак, мы находим квадратичную ошибку для всех точек и суммируем их. Это называется суммой квадратов ошибок. Скажем, для значения 1 сумма квадратов ошибки равна S_1.

Точно так же для значения 4 вычисляется сумма квадратов ошибок, чтобы сказать S_4. Мы можем заметить, что S_4 будет намного меньше, чем S_1. Итак, мы находим сумму квадратов ошибок для всех значений, которые мы рассматривали, как отсечку для создания условия. Если мы построим их, мы получим график, как показано ниже.

На приведенной выше диаграмме мы видим, что val_4 для Feature 1 обеспечивает минимальную сумму квадратов ошибок для точки. Итак, теперь мы увидели, как определяется значение отсечения для определенного значения.

Теперь, если у нас есть несколько функций, как решить, какую функцию мы должны использовать для создания узла. Для этого мы создаем кандидатов. Например, скажем, для функции 1 val_4 дает минимальную сумму квадратичной ошибки. Таким образом, он называется кандидатом на функцию 1. Точно так же мы находим кандидатов для функции 2 и функции 3. Скажем, SSR, соответствующий кандидату функции 2, - это S_2_3, а SSR - кандидату функции 3 - S_3_5. Мы сравним S_4, S_2_3 и S_3_5 и выберем минимум. Характеристика, соответствующая минимуму, будет использоваться для создания решающего узла.

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

Обрезка

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

На приведенной выше диаграмме показано, как работает концепция обрезки.

В основном есть два типа обрезки:

1. Предварительная обрезка
2. Пост обрезка

В Pre-pruning мы устанавливаем такие параметры, как «min_samples», «max_depth» и «max_leaves» во время создания дерева. Все параметры нуждаются в настройке гиперпараметров и определяются с помощью методов перекрестной проверки и поиска по сетке. Он ограничивает дерево определенной глубиной или определенным количеством листьев.

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

Заключение

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

В этой статье мы увидели, как деревья решений работают с использованием принципов CART.

Надеюсь это поможет.