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

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

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

По выборкам 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из множества T ( St ) .

Фрагмент ( xi1 ,сравнивается с множеством фрагментов строк{( xTji1 ,соответствующих классу K l :( xTji1 ,, xTjir )таблицы, xTjir ) | s j  Kl } ( xi1 ,случаях, когда выполняются равенства xTji1  x*i1 ,Tnml, xir ),, xir ) . В, xTjir  x*irфиксируем полное совпадение. Обозначим число полных совпадений распознаваемого объектаs*с объектамиKlизОценка объекта s*StGl (T , 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 ,по таблице, KLTnmlвсевозможных тупиковых представительных наборов. ОбозначимVl - множество всевозможных представительных наборов для класса K l .Предположим, что нам требуется распознать объект s*. Пусть1, еслиv  ( xui1 ,( x*i1  xvi1 ,Оценка s*с описанием, xuir ) - представительный набор. Функция ( s* , v), x*ir  xvir ) ,( s* , v)и( x*1 ,, x*n )равнаравна 0 в противном случае.за класс K l вычисляется по формулеl ( s* ) 1 (s* , u) .| Vi | uViПервоначальные варианты тестового алгоритма и алгоритма типа КОРА былиразработаны для бинарных или категориальных переменных.

Они не могут бытьнапрямую использованы в задачах с признаками, принимающими значения из интерваловвещественной оси.Для того, чтобы обеспечить возможность работы с подобнойинформацией могут быть использованы два подхода.а) Первый подход основан на разбиении области возможных значений каждоговещественнозначного признака на k связных подмножеств (интервалов, полуинтервалов,отрезков). Значению признака, принадлежащего элементу j разбиения присваиваетсясамо значение j .Разбиение оптимизируется с целью достижения максимальногоразделения классов. Выбирается такое число элементов разбиения k , при которомдостигается максимальная точность распознавания.Другой подход основан на модификации понятий теста и представительного набора сиспользованием пороговых параметровX1,1 , ,  n ,которые задаются для признаков, Xn .Определение 5. Тестом таблицыназывается такая совокупность столбцовTnml{i1 , , ir } , что для произвольной пары строк s*и s , соответствующих объектам изразных классов, существует такой столбец i из множества{i1 ,, ir } , что абсолютнаявеличина разницы значений, стоящихпревышает  i* .*на пересечении i состроками sиsАналогичным образом вводится модифицированное определение представительногонабора.Главным требованием при выборе- порогов является достижение максимальнойотделимости объектов разных классов при сохранении сходства внутри классов.Поиск тупиковых тестов и тупиковых представительных наборов при модифицированныхопределениях аналогичен их поиску в первоначальных вариантах методов.Тестовый алгоритм и алгоритм с представительными наборами являются частью болееобщей конструкции, основанной на принципе частичной прецедентности и носящейназвание алгоритмов вычисления оценок.Существует много вариантов моделей данного типа.

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

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