Для удобства чтения вы можете прочитать эту статью в Идиоматических программистах, я размещаю там все свои новые статьи.
Деревья решений - это способ представления взаимосвязи между различными атрибутами в данном наборе данных с использованием структуры данных двоичного дерева, так что это представление можно использовать для будущих прогнозов или классификации.
Абстрактный способ понимания алгоритма дерева решений состоит в том, что он задает серию вопросов на основе набора данных для построения представления двоичного дерева. Допустим, нам нужно классифицировать изображения Apple, Orange и Banana, и у нас есть следующий набор данных.
Итак, на основе этих данных алгоритм может создать дерево решений, подобное этому.
Вначале весь набор данных хранится в корневом узле дерева, а затем на каждой итерации подмножество корневого набора данных разделяется и добавляется как дочерний.
Основная задача алгоритма дерева решений состоит в том, чтобы определить, какой атрибут должен быть выбран для отделения от родительского узла и добавления его в качестве дочернего узла (также известного как «задать вопрос») и, таким образом, обеспечить максимальную точность прогнозирования. Есть два основных показателя, которые помогают нам решить эту задачу.
- Получение информации
- Индекс Джини
Получение информации
Каждый раз, когда алгоритм должен разделить набор данных на подмножество этого набора данных, энтропия набора данных изменяется. Информационный прирост является мерой этого изменения энтропии.
Предположим, S - это набор экземпляров, A - атрибут
Энтропия
Энтропия или информационная энтропия - это мера случайности в данном фрагменте информации. Согласно Википедии, Информационная энтропия - это средняя скорость, с которой информация производится стохастическим источником данных.
Энтропия определяется как отрицательное среднее логарифмических вероятностей.
В терминах дерева решений вероятность P будет вероятностью появления элемента в подмножестве набора данных. Возьмем пример атрибута «Форма» в таблице 1.
«Форма» имеет 2 экземпляра «Круглый», из них 1 соответствует «Да» (Apple), а 1 - «Нет» (не Apple). Кроме того, «Форма» имеет 1 экземпляр «Цилиндр», который не соответствует Apple. Учитывая эту информацию, энтропия возраста будет:
Когда мы реализуем дерево решений с использованием метрики информационного прироста, для каждой итерации мы вычисляем информационный прирост для каждого атрибута в корневом узле. Посмотрим, как строится дерево решений на рис.
Наш примерный набор данных состоит из двух атрибутов объекта (форма и цвет) и трех классов (яблоко, апельсин и банан). Итак, в первой итерации мы классифицируем один из классов, скажем, Apple
Итерация 1:
На первой итерации мы предполагаем, что энтропия корневого узла равна 1, и назначаем ему весь набор данных. Затем мы вычисляем информационное усиление для каждого атрибута в нашем наборе данных (в данном случае формы и цвета). Мы уже рассчитали энтропию для формы, теперь давайте рассчитаем энтропию для цвета.
Затем мы рассчитываем информационное усиление для формы и цвета.
Мы выберем атрибут с максимальным усилением, в данном случае Color. Итак, на данный момент наше дерево выглядит так:
Итерация 2
Поскольку мы нашли листовой узел (класс) в первой итерации, мы можем перейти к представлению следующего класса, скажем, оранжевого. В противном случае мы бы продолжили работу с Apple до тех пор, пока не нашли листовой узел (который можно определить по значению получения информации, равному 1).
Теперь нам снова нужно рассчитать энтропию и информационный прирост относительно класса Orange.
По совпадению, расчет Яблока и Апельсина точно такой же. Мы должны выбрать атрибут с максимальным приростом информации. А поскольку это листовой узел, и остается классифицировать только один класс, мы будем напрямую классифицировать Banana на основе вопроса для Orange. Что-то вроде этого:
Это все для этого блога, если вы обнаружите какую-либо ошибку, не стесняйтесь комментировать ниже.
