ММО и поиск достоверных закономерностей в данных. Учебное пособие. Сенько (1185322), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

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

4.3 Решающие деревья и леса

4.3.1 Решающие деревья

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

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

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

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

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

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

При этом используется несколько видов индексов, включая:

- энтропийный индекс неоднородности,

- индекс Джини,

- индекс ошибочной классификации.

Энтропийный индекс неоднородности вычисляется по формуле

_,

_{где - доля объектов класса в выборке . При этом принимается, что . Наибольшее значение принимает при равенстве долей классов. Наименьшее значение достигается при принадлежности всех объектов одному классу.} Индекс Джини вычисляется по формуле

_.

Индекс ошибочной классификации вычисляется по формуле

_.

_{Нетрудно понять, что индексы (2) и (3) также достигают минимального значения при принадлежности всех объектов обучающей выборке одному классу.} Предположим, что в методе обучения используется индекс неоднородности . _{Для оценки эффективности разбиения обучающей выборки на непересекающиеся подвыборки и используется уменьшение среднего индекса неоднородности в и по отношению к . Данное уменьшение вычисляется по формуле}

_{где и являются долями и в полной обучающей выборке .}

_{На первом этапе обучения бинарного решающего дерева ищется оптимальный предикат соответствующий корневой вершине. С этой целью оптимальные разбиения строятся для каждого из признаков из набора . Выбирается признак с максимальным значением индекса . Подвыбороки и , задаваемые оптимальным предикатом для оцениваются с помощью критерия остановки. В качестве критерия остановки может быть использован простейший критерий достижения полной однородности по одному из классов. В случае, если какая-нибудь из выборок удовлетворяет критерию остановки, то соответствующая вершина дерева объявляется концевой и для неё вычисляется метка класса. В случае, если выборка не удовлетворяет критерию остановки, то формируется новая внутренняя вершина, для которой процесс построения дерева продолжается. Однако вместо обучающей выборки используется соответствующая вновь образованной внутренней вершине выборка , которая равна . Для данной выборки производятся те же самые построения, которые на начальном этапе проводились для обучающей выборки . Обучение может проводиться до тех пор, пока все вновь построенные вершины не окажутся однородными по классам. Такое дерево может быть построено всегда, когда обучающая выборка не содержит объектов с одним и тем же значениям каждого из признаков, принадлежащих разным классам. Однако абсолютная точность на обучающей выборке не всегда приводить к высокой обобщающей способности в результате эффекта переобучения.}

_{Одним из способов достижения более высокой обобщающей способности является использования критериев остановки, позволяющих остановит процесс построения дерева до того, как будет достигнута полная однородность концевых вершин.}

_{Рассмотри несколько таких критериев.}

_{1. Критерий остановки по минимальному допустимому числу объектов в выборках, соответствующих концевым вершинам.}

_{2. Критерий остановки по минимально допустимой величине индекса . Предположим, что некоторой вершине соответствует выборка , для которой найдены оптимальный признак вместе с оптимальным предикатом, задающим разбиение . Вершина считается внутренней, если индекс превысил пороговое значение и считается концевой в противном случае.}

_{3. Критерий остановки по точности на контрольной выборке. Исходная выборка данных}

_{случайным образом разбивается на обучающую выборку и контрольную выборку . Выборка используется для построения бинарного решающего дерева. Предположим, что некоторой вершине соответствует выборка , для которой найдены оптимальный признак вместе с оптимальным предикатом, задающим разбиение .}

_{На контрольной выборке производится сравнение эффективность распознающей способности деревьев и .}

_{Деревья и включает все вершины и рёбра, построенные до построения вершины . В дереве вершина считается концевой. В дереве вершина считается}

_{внутренней, а концевыми считаются вершины, соответствующие подвыборкам и .}

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

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

_{Использование критериев ранней остановки не всегда позволяет адекватно оценить необходимую глубину дерева. Слишком ранняя остановка ветвления может привести к потере информативных предикатов, которые могут быть на самом деле найдены только при достаточно большой глубине ветвления.}

В связи с этим нередко целесообразным оказывается построение сначала полного дерева, которое затем уменьшается до оптимального с точки зрения достижения максимальной обучающей способности размера путём объединения некоторых концевых вершин. Такой процесс в литературе принято называть «pruning» («подрезка»).\\

Характеристики

Список файлов книги