Лекция 8 (2012 Лекции МОТП (Сенько))

МАТЕМАТИЧЕСКИЕОСНОВЫ ТЕОРИИПРОГНОЗИРОВАНИЯЛекторСенько Олег ВалентиновичЛекция 8Решающие деревьяРешающиедеревьяпозволяющиевоспроизводятполучитьлогическиеокончательноесхемы,решениеоклассификации объекта с помощью ответов на иерархическиорганизованнуюсистемувопросов.Причёмвопрос,задаваемый на последующем иерархическом уровне, зависитот ответа, полученного на предыдущем уровне. Подобныелогические модели издавна используются в ботанике, зоологии,минералогии, медицине и других областях. Пример, решающегодерева, позволяющая грубо оценить стоимость квадратногометра жилья в предполагаемом городе приведена на рисунке1.Пример решающего дереваРис. 1Решающие деревьяСхемепринятиярешений,изображённойнарисунке1,соответствует связный ориентированный ациклический граф –ориентированное дерево.

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

Бинарные деревья удобно использовать вмоделях машинного обучения.Решающие деревьяПредположим, что бинарное деревоΤиспользуется дляраспознавания объектов, описываемых набором признаковX1,, X n . Каждой вершине дерева v ставится в соответствиепредикат, касающийся значения одного из признаков.Непрерывному признаку X j соответствует предикат вида" X j   " , гдеvj vj - некоторый пороговый параметр.Решающие деревьяКатегориальному признаку X j, принимающему значения из1M{aмножестваjj ,r, a jj } ставится в соответствиеgvcvgv{M,M"XM"предикат видаjj } - дихотомическоеjj , гдеразбиение множества M j .Выбор одного из двух, выходящих из вершины v рёберпроизводится в зависимости от значения предиката.Обучение производится по обучающей выборке St и включает всебя поиск оптимальных разбиений или поиск оптимальныхпороговых параметров..Решающие деревьяРассмотрим задачу распознавания с классами K1 ,, KL .На первом этапе обучения бинарного решающегодерева ищется оптимальный предикат соответствующийкорневой вершине.

При этом поиск производится исходяиз требования уменьшения среднего индексаlнеоднородности в выборках St ипринадлежащих дихотомическомуStr ,разбиенияобучающей выборки , задаваемому предикатом.Решающие деревьяИндекс неоднородности вычисляется для произвольной выборкиS , содержащей объекты из классов K1 ,, KL .При этом используется несколько видов индекса:a) Энтропийный индекс неоднородности вычисляется поLформуле  e ( S )   Pi ln( Pi ) , где Pi - доля объектов классаi 1K i в выборке S . При этом принимается, что 0ln(0)  0 .Наибольшее значение  e ( S ) принимает при равенстведолей классов.

Наименьшее значение  e ( S )  0 достигается припринадлежности всех объектов одному классу.Решающие деревьяб) Индекс Джини вычисляется по формулеL g ( S )  1   Pi 2i 1В) Индекс ошибочной классификации m (S )  1  max ( Pi )i 1, , LНетрудно понять, что индексы б) и в) также достигаютминимального значения при принадлежности всехобъектов обучающей выборке одному классу.Решающие деревьяУменьшение среднего индекса неоднородности в выборкахStl иStrпо отношению к обучающей выборке Stвычисляется по формуле( , St )   ( St )  Pl ( Stl )  Pr ( Str )гдеlдолиSPl и Prt иStr в выборке St .Решающие деревьяВыбирается индекс неоднородности  . Для каждого из признаковищется оптимальный предикат. Выбирается признак X imax смаксимальным значением индекса ( ) . ПодвыборокиStl иStr , задаваемые оптимальным предикатом для X imaxоцениваются с помощью критерия остановки.

В качествекритерия остановки может быть использован простейшийкритерий достижения полной однородности по одному изклассов.Решающие деревья*SВ случае, если какая-нибудь из выборок t удовлетворяеткритерию остановки, то соответствующая вершина дереваобъявляется концевой и для неё вычисляется метка класса. В*случае, если выборка St не удовлетворяет критерию остановки,то формируется новая внутренняя вершина, для которойпроцесс построения дерева продолжается.Пусть некоторой вновь образованной внутренней вершинесоответствует выборка S v . Для данной выборки производятся теже самые построения, которые на начальном этапепроводились для обучающей выборки St .Решающие деревьяОбучение может проводиться до тех пор, пока все вновьпостроенные вершины не окажутся однородными поклассам.

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

Критерий остановки по минимальному допустимомучислу объектов в выборках, соответствующих концевымвершинам.Решающие деревья2.Критерий остановки по минимальноиндекса ( , S )допустимой величине. Предположим, что некоторой вершинеv соответствует выборка S v , для которой найдены оптимальныйпризнаквместесоптимальнымпредикатом,задающимlrразбиение {Sv , Sv }. Вершина v считается внутренней, еслииндекс ( , St )превысил пороговое значение концевой в противном случае.и считаетсяРешающие деревья3.

Критерий остановки по точности на контрольной выборке.Исходная выборка данных случайным образом разбивается наобучающую выборку S и контрольную выборку S c . ВыборкаtSt используется для построения бинарного решающего дерева.Предположим, что некоторой вершине v соответствуетвыборка S v , для которой найдены оптимальный признак вместеlrс оптимальным предикатом, задающим разбиение {Sv , Sv }.На контрольной выборке S c производится сравнениеэффективность распознающей способности деревьев Τv иΤ. vРешающие деревьяΤДеревья Τv ивключает все вершины и рёбра, построенныеvдо построения вершины v .

В дереве Τv вершина v считаетсяΤконцевой. В дереве v вершина v считается внутренней, аконцевыми считаются вершины, соответствующиеподвыборкам. Распознающая способность деревьевΤv и Τv сравнивается на контрольной выборке S c . В том,случае если распознающая способность Τv превосходитΤраспознающую способностьвсе дальнейшие построенияvисходят из того, что вершина v является концевой.

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

В том случае, если полученное p-значение оказываетсяменьше заранее фиксированного уровня значимости вершина vсчитается внутренней. В противном случае вершина v считаетсяконцевой.Решающие деревьяИспользование критериев ранней остановки не всегда позволяетадекватно оценить. необходимую глубину дерева. Слишкомранняя остановка ветвления может привести к потереинформативных предикатов. В связи с этим нередкоцелесообразным оказывается построение сначала полногодерева, которое затем уменьшается до оптимального с точкизрения достижения максимальной обучающей способностиразмера путём объединения некоторых концевых вершин.Такой процесс в литературе принято называть «pruning»(«подрезка»).Решающие деревьяПри подрезке дерева может быть использован критерийцелесообразности объединения двух вершин, основанный насравнение на контрольной выборке точности распознавания дои после проведения «подрезки».Ещё один способ оптимизации обобщающей способностидеревьев основан на учёте при «подрезке» дерева до некоторойвнутренней вершины v одновременно увеличения точностиразделения классов на обучающей выборке и увеличениясложности, которые связаны ветвлением из v .Решающие деревьяПри этом прирост сложностиможет быть оценён через числолистьев в поддереве Τ решающего дерева с корневойвершиной v Следует отметить, что рост сложности являетсяштрафующим фактором, компенсирующим прирост точностиразделения на обучающей выборке с помощью включенияподдерева Τ в решающее дерево.

Разработан целый рядэвристических критериев, зависящих от точности разделения сΤвключением и без включением поддерева Τ и сложности  ,которые позволяют оценить целесообразность включения Τ..