135844 (Автоматизированные Системы Обработки Информации), страница 7

-высокая динамичность информации;

-полиязычность;

-огромные потоки сообщений.

1. СУЩНОСТЬ И ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ РАСПОЗНАВАНИЯ ОБРАЗОВ

Цель задачи обработки – классификация объектов в заданной предметной области. В основе решения задач классификации лежит теория распознавания образов. В общем виде задача распознавания состоит в следующем.

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

Сложность решения задачи определяется:

• возможной неполнотой описания классов вследствие недостаточной априорной информации;

• ошибками измерения признаков из-за ограниченных технических возможностей устройств выделения устройств выделения признаков;

• ограниченности выделенной совокупности признаков вследствие недостаточного времени;

• в отдельных случаях невозможностью абсолютного разделения классов.

Поэтому необходимы специальные методы и средства для решения задачи распознавания.

Рассмотри основные понятия теории распознавания образов.

КЛАСС – это некоторое множество объектов или их состояний, объединенных общими свойствами.

АЛФАВИТ КЛАССОВ – полный перечень классов в заданной предметной области.

ПРИЗНАК – свойство объекта, позволяющее отличать его от других объектов в процессе распознавания.

АПРИОРНЫЙ СЛОВАРЬ ПРИЗНАКОВ – весь перечень признаков, используемый для описания объектов в алфавите классов.

РАБОЧИЙ СЛОВАРЬ ПРИЗНАКОВ –(подмножество априорного словаря) – признаки, регистрируемые доступными средствами наблюдения.

ЭТАЛОННОЕ ОПИСАНИЕ – формализованное описание объектов алфавита классов в пространстве рабочего словаря признаков.

РЕАЛИЗАЦИЯ – совокупность значений признаков распознаваемого объекта.

РЕШАЮЩЕЕ ПРАВИЛО - процедура или аналитическое выражение, позволяющее определить количественно степень сходства реализации с каждым классом алфавита и ее классифицировать.

На основе полученных частных значений степени сходства принимается решение о принадлежности реализации к одному из классов. Для этого могут использоваться различные критерии: идеального наблюдателя, Байеса, Гурвица, Севиджа и др.

1. ОСНОВНЫЕ ЗАДАЧИ ПОСТРОЕНИЯ СИСТЕМ РАСПОЗНАВАНИЯ ОБРАЗОВ

Система распознавания в общем случае является иерархичной по структуре и последовательной по технологии обработки.

Например, специальная система имеет несколько уровней обработки:

• распознавание сигналов;

• распознавание средств связи;

• распознавание источников;

• распознавание узлов связи;

• распознавание элементов группировки войск;

• распознавание состояния и характера деятельности войск.

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

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

При построении системы распознавания в общем случае приходится решать следующие основные задачи:

1. Формирование эталонного описания.

• определение алфавита классов;

• формирование словаря признаков;

• формализация признаков;

• описание классов.

1. Выбор решающего правила.

2. Разработка алгоритма управления работой системы распознавания.

Сущность задач состоит в следующем.

1. Формирование эталонного описания.

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

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

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

Вероятностные характеристики получают путем обработки статистики в ходе наблюдения за объектом или экспертным путем. Если вероятностные характеристики получить не удалось, то классы задаются способом перечисления членов класса. В этом случае статистика проявления признаков будет заложена в эталонном описании.

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

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

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

1. Выбор решающего правила.

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

При разработке систем распознавания выбираются несколько приемлемых решающих правил и оценивают их эффективность путем моделирования работы системы распознавания.

В теории распознавания известно большое количество процедур распознавания:

• вероятностные;

• детерминированные (геометрические);

• логические;

• структурные.

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

3.Разработка алгоритмов управления работой системы распознавания.

Существует несколько вариантов построения систем распознавания:

-без обучения;

-с обучением;

-с самообучением.

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

Обучающиеся распознающие системы.

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

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

Обучение в общем виде производится в несколько этапов:

-оптимизация априорной информации;

-структурная настройка(выбор решающего правила);

-параметрическая настройка.

Настройка алгоритма распознавания производится под управлением учителя путем предъявления эталонов для распознавания и оценки качества классификации.

Самообучающиеся системы.

Цель самообучения – формирование обучающей выборки до и в процессе решения задачи распознавания.

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

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

МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

1. ГЕОМЕТРИЧЕСКИЕ МЕТОДЫ.

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

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

Сущность меры близости применительно к рассматриваемому классу задач покажем на примере двух классов в 2-х мерном пространстве описаний.

Интерпретация рисунка приводит к естественному выводу о предпочтительности отнесения объекта Х к первому классу. В то же время классификация объекта Хⁱ вызывает затруднения и необходимы расчеты.

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

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

Классы могут быть представлены путем перечисления членов класса (как на рисунку: точки в кластерах) или с помощью эталонных образов (например, центральными объектами z₁ и z₂).

Заметим также, что в рассматриваемом классе задач описания объектов являются векторными.

Рассмотрим М классов. Пусть эти классы допускают их представление с помощью эталонных образов Z₁,Z₂, . . .,Z_m. Евклидово расстояние между произвольным вектором образа Х и i-м эталоном определяется следующим выражением:

_____________

D_i = || X - Z_i || = √(X - Z_i)^/ (X - Z_i) (1)

где || Х || - Евклидова норма;

х₁

х₂

Х = х₃ - вектор образа распознаваемого объекта;

:

х_n

z₁

Z = : - вектор образа эталона класса;

z_n

_{n 1}

|| Х || = [Σ X_j² ]²

^j=1

X ^/ = ( x₁ ,x₂ , . . .,x_n) - транспонированный вектор;

X ^/ Z - скалярное произведение;

_n

X^/ Z = Σ X_j^/ Z_j

^{j = 1}

Классификатор, построенный по принципу минимума расстояния, вычисляет расстояние, отделяющее классифицируемый образ Х от эталона каждого класса, и зачисляет этот образ в класс,, оказавшийся ближайшим к нему. Другими словами, образ Х приписывается к классу W_{i ,} если условие D_{i <} D_j для всех j i .

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