_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (1185318), страница 17

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

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

Агрегирующие алгоритмы этой группы различаются способами выбора отображений E(.). Рассмотрим некоторые из них. Если удается представить отображение E(.) в виде декомпозиции , то говорят о статическом выборе областей компетенции. В противном случае происходит динамический выбор алгоритма распознавания. Среди первой группы методов обычно функция F(.) имеет вид , где - соответствующая подобласть, а - некоторый показатель эффективности работы (например, доля правильных ответов) i-ого алгоритма в области D. В качестве отображения D(.) обычно используются те или иные методы кластеризации /19/. Соответствующие подобласти называются областями компетенции. В методе областей компетенции, реализованном в программном комплексе РАСПОЗНАВАНИЕ, используется кластеризация исходного признакового пространства методом k-средних. Работа метода существенно зависит от количества областей компетенции, заданного пользователем. При k=1 имеет место классификация всех объектов наилучшим из исходных алгоритмом. При слишком большом числе областей компетенции возможны многочисленные неоправданные переключения с метода на метод, приводящие к неустойчивой классификации и деградации коллективного решения. Метод областей компетенции отличается высокой скоростью распознавания и относительно небольшим временем обучения /47/.

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

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

где - дельта-окрестность объекта S. Таким образом, учитываются локальные свойства алгоритмов. Одним из вариантов такого подхода является метод Вудса. Мера локальной компетенции алгоритма в точке подсчитывается следующим образом. Для каждого алгоритма определяется номер класса, к которому он относит рассматриваемый объект. Затем производится подсчет доли правильно распознанных объектов этого класса ближайших к данному объекту. Количество ближайших объектов класса, используемых для оценки компетенции, задается пользователем. Создатели метода рекомендуют использовать для этого порядка 10 объектов.

3.10.4. Шаблоны принятия решений

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

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

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

«Шаблоны принятия решений» считается одним из наилучших методов коллективных решений и обладает устойчивыми характеристиками в большом числе экспериментов.

3.11. Средства контроля качества распознавания.

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

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

,

,

где - доля правильно распознанных объектов тестовой выборки, m – объем тестовой выборки, а - уровень значимости, с которым строится доверительный интервал . Последний показывает вероятность того, что искомая вероятность правильного распознавания произвольного объекта будет лежать внутри доверительного интервала. Чем выше уровень значимости, тем шире получается интервал. Так, при в качестве доверительного интервала будет взята вся область возможных значений вероятности, т.е. отрезок [0,1], поэтому выбор уровня значимости представляет собой компромисс между шириной интервала (т.е. ценностью данной информации) и частотой попадания в него искомой вероятности (т.е. точностью данной информации).

Выписанные выше формулы позволяют получить точные значения границ доверительного интервала в рамках принятой статистической модели. К сожалению, прямой подсчет этих вероятностей наталкивается на большие вычислительные сложности (ошибки округления, большое время работы и т.д.) и при больших объемах выборки практически невозможен. В теории вероятностей получены приближенные выражения для границ доверительного интервала при различных условиях. При достаточно больших m и , существенно отличных от нуля и единицы, можно использовать теорему Муавра-Лапласа, позволяющую приблизить биномиальное распределение нормальным. Для последнего существуют явные формулы, позволяющие определить границы доверительного интервала

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

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

,

.

Границы доверительного интервала в этом случае равны соответственно и . В программном комплексе РАСПОЗНАВАНИЕ реализованы все упомянутые выше подходы с автоматическим выбором наиболее подходящего способа подсчета границ доверительного интервала для данной задачи. Пользователь может выбрать тот или иной уровень значимости, варьируя ширину доверительного интервала.

3.12. Минимизация признакового пространства в задачах распознавания

Стандартная постановка задачи распознавания предполагает, что начальная информация о классах (обучающая информация) задается выборкой векторных признаковых описаний объектов, представляющих все классы. Во многих случаях система признаков формируется "стихийно". В ее состав включаются все показатели, влияющие на классификацию (хотя бы чисто гипотетически), и которые можно вычислить или измерить. Независимо от числа имеющихся признаков, исходная система признаков, как правило, избыточна и включает признаки, не влияющие на классификацию или дублирующие друг друга. В некоторых практических задачах распознавания затраты на вычисление части признаков могут быть значительными и конкурировать со стоимостью потерь при распознавании. Решение задач обучения при меньшем числе признаков также является более точным, а полученные решения более устойчивыми. Таким образом, решение задач минимизации признаковых пространств является важным во многих отношениях.

Рассмотрим задачу минимизации признакового пространства в следующей постановке. Пусть имеется модель алгоритмов распознавания, признаковое пространство X₁, X₂,…,X_N и критерий качества есть доля правильно распознанных объектов контрольной выборки алгоритмом A. Требуется найти такое признаковое подпространство , с минимальным n , для которого , где - некоторый минимально допустимый порог точности алгоритма распознавания A, построенного по данным обучения для данного подпространства.

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

В настоящем разделе рассматривается метод минимизации признакового пространства, ориентированный на модели частичной прецедентности /25, 26/ и основанный на кластеризации признаков с учетом их информативности и коррелированности. Рассмотрим один подход, основанный на использовании алгоритмов голосования по системам логических закономерностей /71/.

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

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