ММО2 (2015 Учебное пособие ММО (Сенько)), страница 3

Критерий остановки по минимальномудопустимому числу объектов в выборках,соответствующих концевым вершинам.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Хи-квадрат и другие критерии. По выборкам S и Sрассчитываетсястатистикакритерия и устанавливается соответствующее p-значение. В том случае, если полученноеp-значение оказывается меньше заранее фиксированного уровня значимости вершинасчитается внутренней. В противном случае вершинасчитается концевой.Использование критериев ранней остановки не всегда позволяет адекватно оценитьнеобходимую глубину дерева. Слишком ранняя остановка ветвления может привести кпотере информативных предикатов, которые могут быть на самом деле найдены толькопри достаточно большой глубине ветвления.В связи с этимнередкоцелесообразным оказывается построение сначала полногодерева, которое затем уменьшается до оптимального с точки зрения достижениямаксимальной обучающей способности размера путём объединения некоторых концевыхвершин.

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

Разработан целый рядэвристических критериев, которые позволяют оценить целесообразность включенияTsub . Данные критерии учитывают одновременно сложность и разделяющуюспособность.4.3.2 Решающие лесаВ результате многочисленных экспериментов было установлено, что точность нередкозначительно возрастает, если вместо отдельных решающих деревьев использоватьколлективы (ансамбли)решающих деревьев, которые принято называть решающимилесами. Коллективное решение вычисляется по результатам распознавания отдельнымичленами ансамбля.В методах решающих лесов в качестве членов ансамблей принятоиспользовать решающих деревьев, которые строятся по искусственно сгенерированнымобучающим выборок, статистически сходных с исходной обучающей выборкой.Получили распространение процедуры построения решающих лесов«бэггинг» и«бустинг»., основанные на различных способах генерации «искусственных» выборок изисходной обучающей выборки.В методе «бэггинг» (bagging) каждая искусственная случайнаявыборкой с возвращениями из исходной обучающейвыборка являетсявыборки St  {s1 ,, sm } , такжесодержащей m объектов.

Подобный способ генерации выборокназывают методом «бутрэп» (bootstrap). Название bagging является сокращённым ипроисходит от полного названия «бутстрэп агрегирование»( Bootstrap Aggregating).Отметим, что искусственная выборка состоит только из объектов исходной обучающейвыборки St . Однако некоторые объекты St могут встречаться искусственной выборке понескольку раз, а некоторые могут вообще отсутствовать.Для построения коллективногорешения может быть использован простейшеерешающее правило голосования по большинству: объект относится к тому классу, вкоторый его отнесло большинство деревьев, формирующих лес.Основной идеей метода бустинг (boosting) является пошаговое наращивание ансамблядеревьев.

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

а также способов вычисленияколлективного решения. Одной из наиболее известныхявляется метод Adaptive Boosting (AdaBoost).вариантов метода «бустинг»4.4 Комбинаторно-логические методы, основанные напринципе частичной прецедентностиМногие прикладные задачи распознавания могут быть успешно решеныметодов, основанных на принципе частичной прецедентности.с помощьюДанный принципподразумевает поиск по обучающей выборке фрагментов описаний, позволяющих сразной степенью точности разделить распознаваемые классы K1 ,объект оцениваетсяреализаций, K L . Распознаваемыйпо совокупности найденных фрагментов.

Одной из первыхпринципачастичнойпрецедентностиявляетсятестовыйалгоритм,предложенный в 1966 году. Данный алгоритм основан на понятии тупикового теста.Исходный вариант тестового алгоритма предназначен для распознаванияописываемых с помощью бинарных или категориальных признаков. Иными словами X i {a1i ,, aki (i ) } , i  1,содержит объекты из классовK1 ,ВыборкеX1,, Xn, n .

Пусть обучающая выборкаSt, K L . При этом общее число объектов равно m .St ставится в соответствие таблицаTnml . В строке jнаходятся значения признаков X 1 ,, X n на объекте s j .Определение 1. Тестом таблицыTnml{i1 ,объектов,таблицы Tnmlназывается такая совокупность столбцов, ir } , что для произвольной пары строк s*и s , соответствующих объектам изразных классов, существует такой столбец i из множества {i1 ,, ir }, что значения напересечении i со строками s и s различны.*Иными словами набор признаков считается тестом, если описания любых двух объектовиз разных классов отличаются хотя бы по одному из признаков, входящих в тест.Определение 2. Тест T  {i1 ,от, ir } называется тупиковым, если никакое его отличноеT подмножество (собственное подмножество) тестом не являетсяНа этапе обучения ищется множестводля таблицы Tnml .всевозможных тупиковых тестовПредположим что нам требуется распознать объектвекторным описанием( x*1 ,, x*n ) .T ( St )s*сВыделим в векторном описании фрагмент( xi1 ,, xir ) , соответствующий тесту Tсравнивается с множеством фрагментов строк{( xTji1 ,соответствующих классу K l :из множества T ( St ) .

Фрагмент ( xi1 ,( xTji1 ,, xTjir )таблицы, xTjir ) | s j  Kl } ( xi1 ,случаях, когда выполняются равенства xTji1  x*i1 ,Tnml, xir ),, xir ) . В, xTjir  x*irфиксируем полное совпадение. Обозначим число полных совпадений распознаваемого объектаs* с объектами K l из St через Gl (T , s* ) .Оценка объекта s*за класс K lвычисляется по формуле: l ( s* ) гдеml - число объектовобъекта1mlT T ( St )Gl (T, s* ) ,обучающей выборки из класса K l .

Классификацияможет производится с помощью по вектору оценок[ 1 ( s* ),,  L ( s* )]с помощью стандартного решающего правила, т.е. объект относится в тот класс, оценказа который максимальнаЗадача о поиске всевозможных тупиковых тестов сводится к известной задачекомбинаторного анализа о поиске всевозможных тупиковых покрытий элементам.Нахождение всех тупиковых тестов является сложной комбинаторной задачей. Однакоэффективные алгоритмы поиска разработаны для некоторых типов таблиц. При решениипрактических задач эффективен подход , основанный на вычислении только частитупиковых тестов.Другим известным классом алгоритмов распознавания , основанным на принципечастичной прецедентности, являются алгоритмы типа КОРА.

В отличие от тестовогоалгоритма, где в качестве информативных элементов используются несжимаемые наборыпризнаков – тупиковые тесты, в алгоритмах типа КОРА в качестве информативныхэлементов используются несжимаемые фрагменты описаний эталонных объектовобучающей выборки.Определение 3.Пусть ( xv1 ,Набор( xvj1 ,, xvn ) - признаковое описание объекта, xvjr ), если для произвольной строкиsv  Kl .называется представительным набором для классаKlтаблицыTnmlсоответствующей объектуKlsu  Ki такое, что существует такое j из множества { j1 ,, jr } , что xvj  xuj .Определение 4.

Представительный набор называется тупиковым, если никакое егособственное подмножество представительным набором не является.На этапе обучения для каждого из классовмножествоK1 ,, KLпо таблицеTnmlищетсявсевозможных тупиковых представительных наборов. Обозначим черезVl - множество всевозможных представительных наборов для класса K l . Предположим,что нам требуется распознать объектv  ( xui1 ,с описаниемs*( x*1 ,, xuir ) - представительный набор.

Функция ( s* , v)( s* , v)( x*i1  xvi1 ,, x*ir  xvir ) ,Оценка s*за класс K l вычисляется по формулеиl ( s* ) , x*n ) . Пустьравна 1, еслиравна 0 в противном случае.1 (s* , u) .| Vi | uViПервоначальные варианты тестового алгоритма и алгоритма типа КОРА былиразработаны для бинарных или категориальных переменных. Они не могут бытьнапрямую использованы в задачах с признаками, принимающими значения из интерваловвещественной оси.Для того, чтобы обеспечить возможность работы с подобнойинформацией могут быть использованы два подхода.а) Первый подход основан на разбиении области возможных значений каждоговещественнозначного признака на k связных подмножеств (интервалов, полуинтервалов,отрезков).