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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

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

Определение 3.Пусть - признаковое описание объекта . Набор называется представительным набором для класса , если для произвольной строки таблицы соответствующей объекту

такое, что существует такое из множества , что .

Определение 4. Представительный набор называется тупиковым, если никакое его собственное подмножество представительным набором не является.

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

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

.

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

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

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

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

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

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