🗊Презентация Деревья принятия решения

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

Data Mining └ Деревья решений └ Введение Дерево решений – представленный в виде связного ациклического графа план, при помощи которого оценивается значение целевого атрибута объекта по набору значений независимых атрибутов.

Data Mining └ Деревья решений └ Введение Если зависимая переменная принимает дискретные значения – решает задачу классификации. Если непрерывные – задачу регрессии (численного прогнозирования). Впервые предложены в конце 50х годов прошлого века. При проходе от корня к листьям дерева определяется значение зависимой переменной. Внутренний узел представляет разбиение множества возможных значений той или иной независимой переменной. Атрибуты, соответствующие внутренним узлам дерева – атрибуты расщепления (прогнозирующие атрибуты). Каждая ветвь от внутреннего узла отмечается предикатом расщепления. Информация об атрибутах и предикатах расщепления в узле – критерий расщепления.

Data Mining └ Деревья решений └ Введение

Data Mining └ Деревья решений └ Преимущества и недостатки Преимущества деревьев решений: Просты в понимании и интерпретации. Не требуют подготовки данных. Используют модель «белого ящика». Позволяют оценить модель при помощи статистических тестов. Дают возможность извлекать из базы данных правила на естественном языке. Позволяют создавать классификационные модели в тех областях, где аналитику достаточно сложно формализовать знания. Алгоритм конструирования дерева решений не требует от пользователя выбора входных атрибутов. Быстро обучаются.

Data Mining └ Деревья решений └ Преимущества и недостатки Недостатки деревьев решений Проблема получения оптимального дерева решений бывает NP-полной. Могут появиться слишком сложные конструкции, которые при этом недостаточно полно представляют данные. Существуют концепты, которые сложно понять из модели, так как модель описывает их сложным путем. Для данных, которые включают категориальные переменные с большим набором уровней, больший информационный вес присваивается тем атрибутам, которые имеют большее количество уровней.

Data Mining └ Деревья решений └ Построение Выбираем целевой атрибут Выбираем критерий расщепления Разделяем обучающую выборку Исключаем атрибут расщепления из выборки Для всех полученных подвыборок переходим на шаг 2

Data Mining └ Деревья решений └ Критерий прироста информации Ансамбль – множество сообщений, каждому из которых соответствует вероятность посылки. Пусть X = {x1, x2, …, xn} – наш ансамбль. Соответственно имеем p(x1) = p1 , p(x2) = p2, …, p(xn) = pn. Если x1, x2, …, xn независимы и некоторый xi обязательно отправляется, то . Мера средней неопределённости ансамбля до посылки сообщения – информационная энтропия ансамбля.

Data Mining └ Деревья решений └ Критерий прироста информации Информационная энтропия: Мера неопределённости выбора сообщения из ансамбля Численно равна среднему количеству бит, необходимых для однозначной кодировки всех сообщений ансамбля Условная энтропия: для ансамблей, в которых известна вероятность появления одного сообщения после другого, или для описания потерь в канале с помехами

Data Mining └ Деревья решений └ Критерий прироста информации Взаимная энтропия двух ансамблей:

Data Mining └ Деревья решений └ Критерий прироста информации Энтропия: Неотрицательна: H(X)≥0 Ограничена сверху: Для независимых A и B справедливо: H(AB) = H(A)+H(B)

Data Mining └ Деревья решений └ Критерий прироста информации Взаимная информация (information gain): I(Y|X) = H(Y) – H(Y|X) – мера неопределённости, снятой посылкой сообщения из ансамбля. В случае с конструированием деревьев решений целесообразно использовать её в качестве критерия выбора новых атрибутов расщепления.

Data Mining └ Деревья решений └ Критерий прироста информации При наличии непрерывных атрибутов надо бы поискать пороговые значения, которые надо выставлять в узлах. Для этого тоже можно хорошо приспособить энтропию и information gain. Надо определить, какие значения непрерывных атрибутов дадут наибольший прирост. Пороговая энтропия:

Data Mining └ Деревья решений └ Алгоритм построения На старте имеем таблицу примеров и набор атрибутов с заранее определённым целевым. Если все примеры принадлежат одному классу, возвратим соответствующий лист. Если множество атрибутов пусто, вернуть наиболее часто встречающийся в таблице примеров класс. Найти атрибут с наибольшим приростом информации (а для количественных атрибутов также найти оптимальный порог). Создать узел дерева для найденного атрибута: Поместить атрибут в узел Для всех возможных значений атрибута добавить новую ветвь дерева с соответствующим предикатом и рекурсивно вызвать алгоритм для разделённой по атрибуту обучающей выборки Завершить, если атрибуты закончились Все элементы таблицы примеров имеют одно значение целевого атрибута