Энтропия: Как деревья решений принимают решения

Простая логика и математика, лежащие в основе очень эффективного алгоритма машинного обучения.

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

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

Что такое энтропия? В самых простых терминах энтропия — это не что иное, как мера беспорядка. (Можно думать о ней и как о мере порядка. Мне нравится беспорядок, потому что он звучит круче.)

Математическая формула для энтропии выглядит следующим образом —

Энтропия. Иногда также обозначается с помощью буквы ‘H’.

Где ‘Pi’ — это просто частотная вероятность элемента/класса ‘i’ в наших данных. Для простоты предположим, что у нас есть только два класса: положительный и отрицательный. Поэтому ‘i’ здесь можно было бы назвать как +, так и (-). Так, если бы в нашем наборе данных было 100 точек данных, 30 из которых принадлежат классу положительных, а 70 — классу отрицательных, то ‘P+’ было бы 3/10, а ‘P-‘ — 7/10. Довольно просто.
Если бы я вычислил энтропию моих классов в данном примере по формуле, приведенной выше. Вот что бы я получил.

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

По оси x измеряется доля точек данных, принадлежащих к положительному классу в каждом пузырьке, а по оси y — их соответствующие энтропии. Сразу видна перевернутая форма графика ‘U’. Энтропия минимальна в крайних точках, когда в пузырьке либо нет положительных экземпляров, либо есть только положительные экземпляры. То есть, когда пузырек чистый, беспорядок равен 0. Энтропия максимальна посередине, когда пузырек равномерно распределен между положительными и отрицательными значениями.

Какое значение имеет, что энтропия измеряется с помощью логарифма с основанием 2 или почему энтропия измеряется в диапазоне от 0 до 1, а не в каком-то другом диапазоне? Просто метрика. Не важно, как она появилась. Важно знать, как ее прочитать и что она нам говорит, что мы только что сделали выше. Энтропия — это мера беспорядка или неопределённости, и цель машинного обучения и специалистов по данным в целом — уменьшить неопределённость.

Теперь мы знаем, как измерить беспорядок. Далее нам нужна метрика для измерения сокращения этого беспорядка в нашей целевой переменной/классе с учетом дополнительной информации( особенностей/независимых переменных) о ней. Вот тут-то и появляется метрика Information Gain. Математически ее можно записать как:

Мы просто вычитаем энтропию Y, полученную по X, из энтропии только по Y, чтобы вычислить уменьшение неопределенности по Y, полученную по дополнительной информации X о Y. Это называется «Information Gain (Получение информации)». Чем больше уменьшение неопределенности, тем больше информации о Y получено из X.

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

Пример: таблица скоринга

Здесь наша целевая переменная — это Liability (Ответственность), которая может принимать два значения «Normal» (Нормальный) и «High» (Высокий), и у нас есть только одна фича — Credit Rating (Кредитный рейтинг), которая может принимать значения «Excellent» (Отлично), «Good» (Хорошо) и «Poor» (Плохо). Всего есть 14 наблюдений. 7 из них относятся к классу «Normal Liability»(Нормальная ответственность) и 7 — к классу «High Liability»(Высокая ответственность). Таким образом, имеем максимальную неопределённость.

Подводя итог по верхней строке, мы видим, что есть 4 наблюдения, которые имеют значение Excellent(отлично) для фичи кредитного рейтинга . Наблюдаем, что 3 из них принадлежат к классу нормальной ответственности и только 1 — к классу высокой ответственности. Аналогичным образом можно вычислить такие значения для других значений Рейтинга кредитоспособности из таблицы непредвиденных обстоятельств.

Для этой иллюстрации, я буду использовать эту таблицу, чтобы вычислить энтропию нашей целевой переменной самостоятельно, а затем вычислить энтропию нашей целевой переменной с учетом дополнительной информации об объекте, из фичи кредитного рейтинга. Это позволит мне рассчитать, сколько дополнительной информации предоставляет «Кредитный рейтинг» для моей целевой переменной «Ответственность».
Давайте приступим.

Энтропия нашей целевой переменной равна 1, причем при максимальном беспорядке, возникающем из-за равномерного деления на классы «Нормальный» и «Высокий». Наш следующий шаг — вычислить энтропию целевой переменной «Ответственность» с учетом дополнительной информации о кредитной оценке. Для этого мы рассчитаем энтропию для Liability(ответственности) для каждого значения кредитной оценки и сложим их, используя средневзвешенное значение доли наблюдений, которые попадают в каждую величину. Причины, по которым мы используем средневзвешенную величину, станут более понятными, когда мы обсудим это в контексте деревьев принятия решений.

Мы получили энтропию для нашей целевой переменной с учетом функции «Кредитный рейтинг». Теперь мы можем вычислить Information Gain для Liability используя Credit Rating, чтобы увидеть, насколько информативна эта фича.

Знание кредитного рейтинга помогло нам уменьшить неопределенность в отношении целевой переменной » Liability» (Ответственность)! Разве это не то, что должна делать хорошая фича? Предоставлять нам информацию о нашей целевой переменной? Это именно то, как и почему деревья принятия решений используют энтропию и получение информации, чтобы определить, на какой фиче разделить свои ветви, чтобы ближе предсказать целевую переменную с каждым делением, а также, чтобы определить, когда остановить деление дерева! (в дополнение к гиперпараметрам, таким как максимальная глубина, конечно). Давайте посмотрим на это в действии с другим примером с использованием деревьев решений.

Пример: Решающие деревья

Рассмотрим пример, когда мы строим дерево решений, чтобы предсказать, приведет ли предоставленный человеку кредит к списанию или нет. Наше население состоит из 30 человек. 16 относятся к классу списания, а остальные 14 — к классу не списания. У нас есть две особенности, а именно » Balance «, который может принимать два значения -> «< 50K» или «>50K» и » Residence «, который может принимать три значения -> «OWN», «RENT» или «OTHER». Я покажу вам, как алгоритм дерева решений решит, какой признак разделить сначала и какой признак дает больше информации, или снизит неопределенность в нашей целевой переменной с помощью концепций «Энтропия» и » Information Gain».

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

Разделение на функцию , «Баланс» приводит к увеличению information gain 0.37 по нашей целевой переменной. Давайте сделаем то же самое для признака, «Residence».

Information gain для фичи Balance почти в 3 раза больше, чем для Residence! Если вы вернетесь и посмотрите на схемы, то увидите, что дочерние узлы от расщепления на Balance выглядят более чистыми, чем на Residence. Однако левый узел для residence также очень чистый, но именно здесь в игру вступают средневзвешенные значения. Несмотря на то, что этот узел очень чистый, он имеет наименьшее количество суммарных наблюдений, и результат вносит небольшую часть его чистоты, когда мы вычисляем общую энтропию от деления на Balance. Это важно, потому что мы ищем общую информативность функции и не хотим, чтобы наши результаты были искажены редким значением фичи.

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

Вот так! Теперь вы знаете, что такое энтропия и information gain, и как они вычисляются. Вы понимаете, как дерево решений либо само по себе, либо в древовидном ансамбле решает, на каком порядке лучше всего разделить функции, и решает, когда остановиться, когда тренироваться по заданным данным. Если каждый из вас должен объяснить кому-то хитросплетения того, как работает дерево решений, надеюсь, вы не сделаете этого слишком плохо.
Надеюсь, что вы смогли получить какую-нибудь ценность из этой заметки. Если есть что-то, что я пропустил или что-то было неточным, или если у вас есть абсолютно любые отзывы, пожалуйста, дайте мне знать в комментариях. Я был бы очень признателен. Спасибо.

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *