Лекция 8. Решающие деревья (2014 Лекции (Сенько))

Лекция 8Решающие деревьяЛектор – Сенько Олег ВалентиновичКурс «Математические основы теории прогнозирования»4-й курс, III потокСенько Олег Валентинович ()МОТП, лекция 21 / 15Содержание лекции1Решающие деревьяСенько Олег Валентинович ()МОТП, лекция 22 / 15Решающие деревьяРешающие деревья воспроизводят логические схемы, позволяющиеполучить окончательное решение о классификации объекта спомощью ответов на иерархически организованную систему вопросов.Причём вопрос, задаваемый на последующем иерархическом уровне,зависит от ответа, полученного на предыдущем уровне. Подобныелогические модели издавна используются в ботанике, зоологии,минералогии, медицине и других областях.

Пример, решающегодерева, позволяющая грубо оценить стоимость квадратного метражилья в предполагаемом городе приведена на рисунке 1. Схемепринятия решений, изображённой на рисунке 1, соответствует связныйориентированный ациклический граф – ориентированное дерево.Дерево включает в себя корневую вершину, инцидентную тольковыходящим рёбрами, внутренние вершины, инцидентную одномувходящему ребру и нескольким выходящим, и листья – концевыевершины, инцидентные только одному входящему ребру..Сенько Олег Валентинович ()МОТП, лекция 23 / 15Решающие деревьяРис.1Сенько Олег Валентинович ()МОТП, лекция 24 / 15Решающие деревьяКаждой из вершин дерева за исключением листьев соответствуетнекоторый вопрос, подразумевающий несколько вариантов ответов,соответствующих выходящим рёбрам.

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

Предположим,что бинарное дерево T используется для распознавания объектов,описываемых набором признаков X1 , . . . , Xn .Каждой вершине ν дерева T ставится в соответствие предикат,касающийся значения одного из признаков. Непрерывному признакуXj соответствует предикат вида ”Xj ≥ δjν ”, где δjν - некоторыйпороговый параметр.Сенько Олег Валентинович ()МОТП, лекция 25 / 15Решающие деревья. ОбучениеКатегориальному признаку Xj 0 , принимающему значения из00множества Mj 0 = {aj1 , . . . , ajr(j 0 ) } ставится в соответствие предикатν1вида ”Xj 0 ∈ Mjν10 ” , где Mj 0 является элементом дихотомическогоν2разбиения {Mjν10 , Mj 0 } множества Mj 0 . Выбор одного из двух,выходящих из вершины ν рёбер производится в зависимости отзначения предиката.Процесс распознавания заканчивается при достижении концевойвершины (листа).

Объект относится классу согласно метке,поставленной в соответсттвие данному листу.Обучение решающих деревьев Рассмотрим задачу распознавания склассами K1 , . . . , KL . Обучение производится по обучающей выборкеSet и включает в себя поиск оптимальных пороговых параметров илиоптимальных дихотомических разбиений для признаков X1 , . .

. , Xn .При этом поиск производится исходя из требования снижениясреднего индекса неоднородности в выборках, порождаемых искомымдихотомическим разбиением обучающей выборки Set .Сенько Олег Валентинович ()МОТП, лекция 26 / 15Решающие деревьяИндекс неоднородности вычисляется для произвольной выборки Se ,содержащей объекты из классов K1 , .

. . , KL . При этом используетсянесколько видов индексов, включая:энтропийный индекс неоднородности,индекс Джини,индекс ошибочной классификации.Энтропийный индекс неоднородности вычисляется по формулеe =−γe (S)LXPi ln Pi ,(1)i=1e При этом принимается,где Pi - доля объектов класса Ki в выборке S.e принимает при равенствечто 0 ln(0) = 0. Наибольшее значение γe (S)eдолей классов. Наименьшее значение γe (S) достигается припринадлежности всех объектов одному классу.Сенько Олег Валентинович ()МОТП, лекция 27 / 15Решающие деревья.

ОбучениеИндекс Джини вычисляется по формулеe =1−γg (S)LXPi2 .(2)i=1Индекс ошибочной классификации вычисляется по формулеe = 1 − max (Pi ).γm (S)1,...,L(3)Нетрудно понять, что индексы (2) и (3) также достигаютминимального значения при принадлежности всех объектовобучающей выборке одному классу.Предположим, что в методе обучения используется индекснеоднородности γ∗ . Для оценки эффективности разбиения обучающейвыборки Set на непересекающиеся подвыборки Setl и Setr используетсяуменьшение среднего индекса неоднородности в Setl и Setr по отношениюк SetСенько Олег Валентинович ()МОТП, лекция 28 / 15Решающие деревья. ОбучениеДанное уменьшение вычисляется по формуле∆(γ∗ , Set ) = γ∗ (Set ) − Pl γ∗ (Setl ) − Pr γ∗ (Setr ),где Pl и Pr являются долями Setl и Setr в выборке Set .

На первом этапеобучения бинарного решающего дерева ищется оптимальный предикатсоответствующий корневой вершине. С этой целью оптимальныеразбиения строятся для каждого из признаков из набора X1 , . . . , Xn .Выбирается признак Ximax с максимальным значением индекса∆(γ∗ , Set ). Подвыбороки Setl и Setr , задаваемые оптимальнымпредикатом для Ximax оцениваются с помощью критерия остановки. Вкачестве критерия остановки может быть использован простейшийкритерий достижения полной однородности по одному из классов. Вслучае, если какая-нибудь из выборок Set∗ удовлетворяет критериюостановки, то соответствующая вершина дерева объявляется концевойи для неё вычисляется метка класса.

В случае, если выборка Set∗ неудовлетворяет критерию остановки, то формируется новая внутренняявершина, для которой процесс построения дерева продолжается.Сенько Олег Валентинович ()МОТП, лекция 29 / 15Решающие деревья. ОбучениеОднако вместо обучающей выборки Set используется соответствующаявновь образованной внутренней вершине ν выборка Seν , которая равнаSet∗ .

Для данной выборки производятся те же самые построения,которые на начальном этапе проводились для обучающей выборки Set .Обучение может проводиться до тех пор, пока все вновь построенныевершины не окажутся однородными по классам. Такое дерево можетбыть построено всегда, когда обучающая выборка не содержитобъектов с одним и тем же значениям каждого из признаков,принадлежащих разным классам. Однако абсолютная точность наобучающей выборке не всегда приводить к высокой обобщающейспособности в результате эффекта переобучения.Одним из способов достижения более высокой обобщающейспособности является использования критериев остановки,позволяющих остановит процесс построения дерева до того, как будетдостигнута полная однородность концевых вершин.Сенько Олег Валентинович ()МОТП, лекция 210 / 15Решающие деревья.

Обучение.Рассмотри несколько таких критериев.1. Критерий остановки по минимальному допустимому числу объектовв выборках, соответствующих концевым вершинам.2. Критерий остановки по минимально допустимой величине индексаe . Предположим, что некоторой вершине ν соответствует∆(γ∗ , S)выборка Seν , для которой найдены оптимальный признак вместе соптимальным предикатом, задающим разбиение {Seνl , Seνr } . Вершина νe превысил пороговоесчитается внутренней, если индекс ∆(γ∗ , S)значение τ и считается концевой в противном случае.3.Критерий остановки по точности на контрольной выборке.

Исходнаявыборка данных случайным образом разбивается на обучающуювыборку Set и контрольную выборку Sec . Выборка Set используется дляпостроения бинарного решающего дерева. Предположим, чтонекоторой вершине ν соответствует выборка Seν , для которой найденыоптимальный признак вместе с оптимальным предикатом, задающимразбиение {Seνl , Seνr }.Сенько Олег Валентинович ()МОТП, лекция 211 / 15Решающие деревья. ОбучениеНа контрольной выборке Sec производится сравнение эффективностьраспознающей способности деревьев Tν и T++ν .++Деревья Tν и Tν включает все вершины и рёбра, построенные допостроения вершины ν . В дереве Tν вершина ν считается концевой. Вдереве T++вершина ν считается внутренней, а концевыми считаютсяνвершины, соответствующие подвыборкам Seνl и Seνr .

Распознающаяспособность деревьев Tν и T++сравнивается на контрольной выборкеνeSc . В том, случае если распознающая способность T++превосходитνраспознающую способность Tν все дальнейшие построения исходят изтого, что вершина ν является концевой. В противном случаепроизводится исследование Seνl и Seνr .4. Статистический критерий.

Заранее фиксируется пороговый уровеньзначимости (P<0.05,p<0.01 или p<0.001). Предположим, что намтребуется оценить, является ли концевой вершина , для которойнайдены оптимальный признак вместе с оптимальным предикатом,задающим разбиение {Seνl , Seνr }.Сенько Олег Валентинович ()МОТП, лекция 212 / 15Решающие деревья. ОбучениеИсследуется статистическая достоверность различий междусодержанием объектов распознаваемых классов в подвыборках Seνl иSeνr . Для этих целей может быть использованы известныестатистический критерий: Хи-квадрат и другие критерии. По выборкамSeνl и Seνr рассчитывается статистика критерия и устанавливаетсясоответствующее p-значение. В том случае, если полученноеp-значение оказывается меньше заранее фиксированного уровнязначимости вершина ν считается внутренней.

В противном случаевершина ν считается концевой.Использование критериев ранней остановки не всегда позволяетадекватно оценить необходимую глубину дерева. Слишком ранняяостановка ветвления может привести к потере информативныхпредикатов, которые могут быть на самом деле найдены только придостаточно большой глубине ветвления.Сенько Олег Валентинович ()МОТП, лекция 213 / 15Решающие деревья. ПодрезкаВ связи с этим нередко целесообразным оказывается построениесначала полного дерева, которое затем уменьшается до оптимальногос точки зрения достижения максимальной обучающей способностиразмера путём объединения некоторых концевых вершин. Такойпроцесс в литературе принято называть «pruning» («подрезка»).При подрезке дерева может быть использован критерийцелесообразности объединения двух вершин, основанный на сравнениена контрольной выборке точности распознавания до и послепроведения «подрезки».Ещё один способ оптимизации обобщающей способности деревьевоснован на учёте при «подрезке» дерева до некоторой внутреннейвершины ν одновременно увеличения точности разделения классов наобучающей выборке и увеличения сложности, которые возникаютблагодаря ветвлению из ν.Сенько Олег Валентинович ()МОТП, лекция 214 / 15Решающие деревьяПри этом прирост сложности, связанный с ветвлением из вершины ν,может быть оценён через число листьев в поддереве Tsubполногоνрешающего дерева с корневой вершиной ν.

Следует отметить, чторост сложности является штрафующим фактором, компенсирующимприрост точности разделения на обучающей выборке с помощьювключения поддерева Tsubв решающее дерево. Разработан целый рядνэвристических критериев, которые позволяют оценитьцелесообразность включения Tsubν . Данные критерии учитываютодновременно сложность и разделяющую способность.Сенько Олег Валентинович ()МОТП, лекция 215 / 15.