Расчет информационного выигрыша в дереве решений

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

Как использовать: Набор для обучения вводится в виде csv списка, в качестве разделителя используется точка с запятой. Первая строка считается метками характеристик и класса объекта (сначала характеристики, потом класс). Данные по умолчанию взяты из известного примера дерева решений играть или нет в теннис на улице. Объекты принадлежат к двум классам: "Играть" и "Не играть", в качестве характеристик используются "Осадки", "Температура", "Влажность" и "Ветер".

Расчет информационного выигрыша

Осадки;Температура;Влажность;Ветер;Класс Солнечно;Жарко;Высокая;Нет;Не играть Солнечно;Жарко;Высокая;Да;Не играть Переменная облачность;Жарко;Высокая;Нет;Играть Пасмурно;Умеренно;Высокая;Нет;Играть Пасмурно;Прохладно;Нормальная;Нет;Играть Пасмурно;Прохладно;Нормальная;Да;Не играть Переменная облачность;Прохладно;Нормальная;Да;Играть Солнечно;Умеренно;Высокая;Нет;Не играть Солнечно;Прохладно;Нормальная;Нет;Играть Пасмурно;Умеренно;Нормальная;Нет;Играть Солнечно;Умеренно;Нормальная;Да;Играть Переменная облачность;Умеренно;Высокая;Да;Играть Переменная облачность;Жарко;Нормальная;Нет;Играть Пасмурно;Умеренно;Высокая;Да;Не играть

Набор для обучения

Точность вычисления

Знаков после запятой: 3

Рассчитать

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

Загрузить 

 Ссылка  Сохранить  Виджет

Информационный выигрыш и деревья решений

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

Чтобы было понятнее, разберем пример с данными по умолчанию.

Классифицируемые объекты обладают следующими свойствами (атрибутами):

• Осадки: Солнечно/Переменная облачность/Пасмурно
• Влажность: Высокая/Нормальная
• Ветер: Да/Нет
• Температура: Жарка/Умеренно/Прохладно

Классы объектов: Играем/Не играем

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

Возникает вопрос - как измерить количество информации, которое даст нам проверка значения конкретного атрибута объекта? Один из подходов - это проверка уменьшения энтропии, и именно это рассчитывает метрика информационный выигрыш (information gain).

Вернемся к примеру. В нашем наборе для обучения есть пять объектов класса "Не играем" и девять объектов класса "Играем". Используя известную формулу энтропии Шеннона, находим текущую энтропию:

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

Если значение атрибута "Ветер" равно "Да", у нас остается 6 примеров. Три из них принадлежат классу "Играем" и три - классу "Не играем". Их энтропия, таким образом, равна

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

Если значение атрибута "Ветер" равно "Нет", у нас остается 8 примеров. Шесть из них принадлежат классу "Играем" и два - классу "Не играем". Энтропия этого множества равна

Это конечно лучше чем исходное значение в 0.94 бита энтропии. То есть, если нам повезло и атрибут равен "Нет", мы получим разбиение с меньшей энтропией.

Чтобы оценить уменьшении энтропии в-общем, нам надо усреднить значение с весами равными вероятности получить "Да" и "Нет". Так как изначально у нас было шесть примеров со значением "Да" и восемь - со значением "Нет", среднее значение энтропии после разбиения по атрибуту "Ветер" будет

Начав с энтропии 0.94 и проведя разбиение по атрибуту "Ветер", мы получили энтропию 0.892. Информационный выигрыш, как уменьшении энтропии после проверки атрибута "Ветер" составит

Общая формула для расчета информационного выигрыша для атрибута a выглядит следующим образом

,

где
- набор обучающих примеров, каждый в форме , где значение атрибута (свойства, характеристики) конкретного примера и - класс объекта (целевая функция),
- энтропия T при условии проверки атрибута a (условная энтропия)

Формула для условной энтропии:

где
- такое подмножество множества обучающих примеров T, где у каждого примера значение атрибута a равно v.

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

Последнее замечание для тех, у кого возник вопрос "Зачем, зачем это всё? Почему бы просто не использовать оператор if для каждой комбинации атрибутов?". Вы конечно, можете так сделать, но надо понимать, что даже для такого небольшого примера число комбинаций равно 3*2*2*3=36. Мы, в свою очередь, можем построить дерево решений, используя только 14 из них для обучения алгоритма. И что самое замечательное, наш алгоритм, наше построенное дерево решений, может прекрасно классифицировать все оставшиеся 22 комбинации без нас. В этом весь смысл машинного обучения.