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

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

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

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

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

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

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

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

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

Непрерывному признакуX j соответствует предикатвида" X j   j " , где j - некоторый пороговый параметр. Выбор одного из двух,выходящих из вершиныКатегориальномуM j  {a1j ,рёбер производится в зависимости от значения предиката.признакуXj,принимающемузначенияизмножества, arj( j) } ставится в соответствие предикат вида " X j  M j1 " , где M j1является элементом дихотомическогоодного из двух, выходящих из вершиныразбиения {M j1 , M j2 } множества M j . Выборрёбер производится в зависимостиотзначения предиката. Процесс распознавания заканчивается при достижении концевойвершины (листа).

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

При этом принимается, что 0ln(0)  0 .принимает при равенстве долей классов. Наименьшеедостигается при принадлежности всех объектов одному классу.Индекс Джини вычисляется по формулеL g ( S )  1   Pi 2 .i 1Индекс ошибочной классификации вычисляется по формуле m ( S )  1  max( Pi ) .i{1, , L}Нетрудно понять, что индексы (2) и (3) также достигают минимального значенияпри принадлежности всех объектов обучающей выборке одному классу. Предположим,что в методеобучения используется индекс неоднородности  * ( S ) . Для оценкиlэффективности разбиения обучающей выборки St на непересекающиеся подвыборки Stlrи St используется уменьшение среднего индекса неоднородности в Stпо отношению к St .

Данное уменьшение вычисляется по формуле( * , St )   * ( St )  Pl * ( Stl )  Pr * ( Str ),lrгде Pl и Pr являются долями St и St в полной обучающей выборке St .rи StНа первом этапе обучения бинарного решающего дерева ищется оптимальный предикатсоответствующий корневой вершине. С этой целью оптимальные разбиения строятся длякаждого из признаков из набора X 1 ,значением индексапредикатом для( * , St ) .X imax, X n . Выбирается признак X imax с максимальнымlПодвыбороки Stоцениваютсяс помощьюrи St , задаваемые оптимальнымкритерия остановки. В качествекритерия остановки может быть использован простейший критерий достижения полнойоднородности по одному из классов. В случае, если какая-нибудь из выборокSt*удовлетворяет критерию остановки, то соответствующая вершина дерева объявляется*концевой и для неё вычисляется метка класса.

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

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

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

В дереве Tвершинасчитается концевой. В дереве T вершинасчитаетсяlrвнутренней, а концевыми считаются вершины, соответствующие подвыборкам S и S.Распознающая способность деревьев T и Tсравнивается на контрольной выборкеSc . В том, случае если распознающая способность T превосходитспособность Tраспознающуювсе дальнейшие построения исходят из того, что вершинаявляетсяlrконцевой. В противном случае производится исследование S и S .4.Статистический критерий.

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

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

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