Модели распознавания_ основанные на различных способах обучения. Часть 2 (2015 Лекции (Сенько)), страница 3

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

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

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

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

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

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

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

При подрезке дерева может быть использован критерий целесообразности объединения двух вершин, основанный на сравнение на контрольной выборке точности распознавания до и после проведения «подрезки».

Ещё один способ оптимизации обобщающей способности деревьев основан на учёте при «подрезке» дерева до некоторой внутренней вершины одновременно увеличения точности разделения классов на обучающей выборке и увеличения сложности, которые возникают благодаря ветвлению из .

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

4.3.2 Решающие леса

В результате многочисленных экспериментов было установлено, что точность нередко значительно возрастает, если вместо отдельных решающих деревьев использовать коллективы (ансамбли) решающих деревьев, которые принято называть решающими лесами [23,24]. Коллективное решение вычисляется по результатам распознавания отдельными членами ансамбля. В методах решающих лесов в качестве членов ансамблей принято использовать решающих деревьев, которые строятся по искусственно сгенерированным обучающим выборок, статистически сходных с исходной обучающей выборкой. Получили распространение процедуры построения решающих лесов «бэггинг» и «бустинг»., основанные на различных способах генерации «искусственных» выборок из исходной обучающей выборки.

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

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

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

Существуют различные варианты реализации схемы «бустинг», зависящие от способа вычисления вероятностей, приписываемых объектам . а также способов вычисления коллективного решения. Одной из наиболее известных вариантов метода «бустинг» является метод Adaptive Boosting (AdaBoost).

4.4 Комбинаторно-логические методы, основанные на принципе частичной прецедентности

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

Выборке ставится в соответствие таблица . В строке таблицы находятся значения признаков на объекте .

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

Иными словами набор признаков считается тестом, если описания любых двух объектов из разных классов отличаются хотя бы по одному из признаков, входящих в тест.

Определение 2. Тест называется тупиковым, если никакое его отличное от подмножество (собственное подмножество) тестом не является

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

соответствующих классу : . В

случаях, когда выполняются равенства

фиксируем полное совпадение. Обозначим число полных совпадений распознаваемого объекта с объектами из через .

Оценка объекта за класс вычисляется по формуле:

,

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

Задача о поиске всевозможных тупиковых тестов сводится к известной задаче комбинаторного анализа о поиске всевозможных тупиковых покрытий элементам.

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

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