Деревья принятия решений
 Скачать 98 Kb.
|
Деревья принятия решенийДерево решений – представленный в виде связного ациклического графа план, при помощи которого оценивается значение целевого атрибута объекта по набору значений независимых атрибутов. Определение Если зависимая переменная принимает дискретные значения – решает задачу классификации. Если непрерывные – задачу регрессии (численного прогнозирования). Впервые предложены в конце 50х годов прошлого века. При проходе от корня к листьям дерева определяется значение зависимой переменной. Внутренний узел представляет разбиение множества возможных значений той или иной независимой переменной. Атрибуты, соответствующие внутренним узлам дерева – атрибуты расщепления (прогнозирующие атрибуты). Каждая ветвь от внутреннего узла отмечается предикатом расщепления. Информация об атрибутах и предикатах расщепления в узле – критерий расщепления. Деревья решений Пример дерева и исходных данных Преимущества деревьев решений: Просты в понимании и интерпретации. Не требуют подготовки данных. Используют модель «белого ящика». Позволяют оценить модель при помощи статистических тестов. Дают возможность извлекать из базы данных правила на естественном языке. Позволяют создавать классификационные модели в тех областях, где аналитику достаточно сложно формализовать знания. Алгоритм конструирования дерева решений не требует от пользователя выбора входных атрибутов. Быстро обучаются. Преимущества и недостатки Недостатки деревьев решений Проблема получения оптимального дерева решений бывает NP-полной. Могут появиться слишком сложные конструкции, которые при этом недостаточно полно представляют данные. Существуют концепты, которые сложно понять из модели, так как модель описывает их сложным путем. Для данных, которые включают категориальные переменные с большим набором уровней, больший информационный вес присваивается тем атрибутам, которые имеют большее количество уровней. Преимущества и недостатки Data Mining └ Деревья решений └ ПостроениеВыбираем целевой атрибут Выбираем критерий расщепления Разделяем обучающую выборку Исключаем атрибут расщепления из выборки Для всех полученных подвыборок переходим на шаг 2 Общий алгоритм построения Ансамбль – множество сообщений, каждому из которых соответствует вероятность посылки. Пусть X = {x1, x2, …, xn} – наш ансамбль. Соответственно имеем p(x1) = p1 , p(x2) = p2, …, p(xn) = pn. Если x1, x2, …, xn независимы и некоторый xi обязательно отправляется, то . Мера средней неопределённости ансамбля до посылки сообщения – информационная энтропия ансамбля. Информационная энтропия Информационная энтропия: Мера неопределённости выбора сообщения из ансамбля Численно равна среднему количеству бит, необходимых для однозначной кодировки всех сообщений ансамбля Условная энтропия: для ансамблей, в которых известна вероятность появления одного сообщения после другого, или для описания потерь в канале с помехами Информационная энтропия Взаимная энтропия двух ансамблей: Взаимная энтропия Энтропия: Неотрицательна: H(X)≥0 Ограничена сверху: Для независимых A и B справедливо: H(AB) = H(A)+H(B) Некоторые свойства энтропии Взаимная информация (information gain): I(Y|X) = H(Y) – H(Y|X) – мера неопределённости, снятой посылкой сообщения из ансамбля. В случае с конструированием деревьев решений целесообразно использовать её в качестве критерия выбора новых атрибутов расщепления. Взаимная информация При наличии непрерывных атрибутов надо бы поискать пороговые значения, которые надо выставлять в узлах. Для этого тоже можно хорошо приспособить энтропию и information gain. Надо определить, какие значения непрерывных атрибутов дадут наибольший прирост. Пороговая энтропия: Пороговая энтропия Data Mining └ Деревья решений └ Алгоритм построенияНа старте имеем таблицу примеров и набор атрибутов с заранее определённым целевым. Если все примеры принадлежат одному классу, возвратим соответствующий лист. Если множество атрибутов пусто, вернуть наиболее часто встречающийся в таблице примеров класс. Найти атрибут с наибольшим приростом информации (а для количественных атрибутов также найти оптимальный порог). Создать узел дерева для найденного атрибута:
Для всех возможных значений атрибута добавить новую ветвь дерева с соответствующим предикатом и рекурсивно вызвать алгоритм для разделённой по атрибуту обучающей выборки Завершить, если атрибуты закончились Все элементы таблицы примеров имеют одно значение целевого атрибута Алгоритм ID3 |