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

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

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

Аналогичным образом вводится модифицированное определение представительного набора.

Главным требованием при выборе - порогов является достижение максимальной отделимости объектов разных классов при сохранении сходства внутри классов.

Поиск тупиковых тестов и тупиковых представительных наборов при модифицированных определениях аналогичен их поиску в первоначальных вариантах методов.

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

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

Задание системы опорных множеств. Под опорными множествами модели АВО понимается наборы признаков, по которым осуществляется сравнение распознаваемых и эталонных объектов. Примером системы опорных множеств является множество тупиковых тестов. Система опорных множеств некоторого алгоритма может задаваться через систему подмножеств множества или через систему характеристических бинарных векторов.

Каждому подмножеству может быть сопоставлен бинарный вектор размерности . Пусть . Тогда сопоставляется вектор , все компоненты которого равны 0 кроме равных 1 компонент . Теоретические исследования свойств тупиковых тестов для случайных бинарных таблиц показали, что характеристические векторы для почти всех тупиковых тестов имеют асимптотически (при неограниченном возрастании размерности таблицы обучения) одну и ту же длину.

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

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

соответствует множество всех подмножеств за исключением пустого множества.

Задание функции близости. Близость между объектами по опорноным множествам задаётся аналогично тому, как задаётся близость между объектами по тупиковым тестам или представительным наборам. Пусть набор номеров соответствует характеристическому вектору .

Фрагмент описания объекта называется - частью объекта _. Под функцией близости понимается функция от соответствующих -частей сравниваемых объектов, принимающая значения 1 (объекты близки) или 0 (объекты удалены).

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

Примеры функций близости.

1. , если при произвольном , при котором , всегда выполняется неравенство . , если существует такое , что одновременно и .

2. Пусть - скалярный пороговый параметр. Функция , если выполняется неравенство . В противном случае .

Важным элементом АВО является оценка близости распознаваемого объекта к эталону по заданной - части. Данная оценка близости, которая будет обозначаться , формируется на основе введённых ранее функций близости и, возможно, дополнительных параметров. Приведём примеры функций близости различного уровня сложности:

A) ,

B) , где - параметр, характеризующий информативность опорного множества с характеристическим вектором .

С) , где - параметр, характеризующий информативность эталона , параметры характеризуют информативность отдельных признаков.

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

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

(1)

Наряду с формулой (1) используется формула

(2)

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

Прямое вычисление оценок за классы по формулам (1) и (2) в случаях, когда в качестве систем опорных множеств используются наборы с фиксированным числом признаков или всевозможные наборы признаков, оказывается практически невозможным при сколь либо высокой размерности признакового пространства из-за необходимости вычисления огромного числа значений функций близости.

Однако при равенстве весов всех признаков существуют эффективные формулы для вычисления оценок по формуле (1). Предположим, что оценки близости распознаваемого объекта к эталону по заданной - части вычисляются по формуле (A).

Тогда оценка по формуле (1) принимает вид

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

Предположим, что система опорных множеств удовлетворяет условию . Очевидно, что число опорных множеств, удовлетворяющих условию , равно . Откуда следует, что . Следовательно оценка по формуле (1) может быть записана в виде

. (3)

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

Обучение алгоритмов вычисления оценок. Для обучения алгоритмов АВО в общем случае может быть использован тот же самый подход, который используется для обучения в методе «Линейная машина». Предположим, что решается задача обучения алгоритмов

для распознавания объектов , принадлежащих классам . При правильного распознавания объекта должна выполняться система неравенств

где .

В наиболее общем из приведённых выше вариантов модели АВО обучение может быть сведено к поиску максимальной совместной подсистемы системы неравенств

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

Тестовый алгоритм был впервые предложен в работе [], где для решении задачи геологического прогнозирования.

4.5 Методы, основанные на голосовании по системам логических закономерностей

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

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

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

Математически логическая закономерность класса , которую мы будем обозначать , описывается с помощью наборов предикатов вида

, (1)

где .

Напомним, что предикатом называется утверждение, принимающее значения «ИСТИНА» или «ЛОЖЬ» в зависимости от значений входящих в них переменных. Полностью логическая закономерность задаётся конъюнкцией предикатов вида (1):

(2)

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

На этапе обучения для каждого класса строится множество логических закономерностей . Границы подбираются таким образом, чтобы равенство «ИСТИНА» выполнялось бы на максимально большом числе объектов обучающей выборки из класса и равенство «ЛОЖЬ» выполнялось бы на всех объектах обучающей выборки из класса . Наряду с полными логическими закономерностями, удовлетворяющими последним условиям, используются также частичные логические закономерности, для которых допускается попадание в них небольшой доли объектов чужих классов. Методы построения логических закономерностей подробно излагаются в работе [11], а также книге [9].

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

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

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