установить соответствие между набором значений приведенных признаков A,B,C

и классами W1, W2,...Wm.

Так для простоты понимания и без притязаний на медицинскую

достоверность возьмем такой пример: необходимо распознавать два

заболевания - обычная простуда и ангина (W1,W2), а в качестве логических

признаков выберем

А - повышенная температура (А=0 - нет, А=1 - да);

В - насморк (В=0 - нет, В=1 - да);

С - нарывы в горле (С=0 - нет, С=1 - да).

Тогда так называемое булево соотношение между классом W1 (обычное

простудное заболевание) и значениями признаками (а эти значения -

бинарные) выглядит так

[pic]

Здесь умножение, как вы знаете, соответствует логическому “И”, а

сложение - “ИЛИ”.

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

[pic]

Подробнее здесь мы эти вопросы не рассматриваем, так как логическим

системам в дальнейшем курсе уделим достаточное внимание.

Если распределение объектов распознавания, представляемых числовыми

значениями их признаков по областям соответствующего пространства

вероятностное, то для описания классов необходимо определить

характеристики этих распределений. А из теории вероятности известно, что

это

-функции ПРВ fi (x1,x2,....,xn), где x1.....xn - вероятностные

признаки, I - номер класса;

-P(Wi) - априорная вероятность того, что объект, случайно выбранный

из общей совокупности, окажется принадлежащим к классу Wi.

Как получить ПРВ классов системы распознавания? В распоряжении

разработчика СР - три способа:

-экспериментальное определение по статистическим данным;

-теоретический вывод;

-моделирование.

То же касается априорной вероятности класса P(Wi).

Если признаки распознавания - структурные, то описанием каж-дого

класса должен быть набор предложений (цепочек из непроизводных элементов с

правилами соединения). Каждое из предложений класса - характеристика

структурных особенностей объектов этого класса. Пример - код Фримена.

ЗАДАЧА № 5

Выбор алгоритма классификации, обеспечивающего отнесение

распознаваемого объекта или явления к соответствующему классу.

Непосредственное решение задачи распознавания на основе

использования словаря признаков и алфавита классов объектов или явлений

фактически заключается в разбиении пространства значений признаков

распознавания на области D1,D2,...,Dn, соответствующие классам

W1,W2,...,Wn (вспоминаем определение “образа”).

Указанное разбиение должно быть выполнено таким образом, чтобы

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

объектов или явлений к “чужим” классам.

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

признаков X1,X2,....,Xn (точка в n-мерном пространстве), к классу Wi, если

указанная точка лежит в соответствующей классу области признаков - Di.

Разбиение пространства признаков можно представлять как построение

разделяющих функций fi(x1,x2,....,xn) между множествами (областями)

признаков Di, принадлежащим разным классам.

Упомянутые функции должны обладать следующим свойством:

-если объект, имеющий вектор признаков [pic] фактически относится к

классу [pic], то значение разделяющей функции

[pic]

должно быть большим, чем значение ее для класса [pic]- [pic] (здесь

индекс q - означает номер класса, к которому принадлежит вектор признаков).

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

Di, соответствующим классам Wi:

[pic]

Для двух распознаваемых классов разбиение двумерного пространства

выглядит так (рис 2.2). Физически распознавание основывается на сравнении

значений той или иной меры близости распознаваемого объекта с каждым

классом. При этом если значение выбранной меры близости (сходства) L

данного объекта w с каким-либо классом Wg достигает экстремума относительно

значений ее по другим классам, то есть

[pic]

то принимается решение о принадлежности этого объекта классу Wg, то есть

w[pic]Wg.

Надеюсь понятно, что если мера близости не имеет экстремума, то мы

находимся на границе, где не можем отдать предпочтение ни одному из

классов.

X1 o o o o

xx x o o o

x o o F2(X1,X2) > F1(X1,X2)

x x x o o o o

x o o o o o

x x x x x o o o o

o

F1(X1,X2)>F2(X1,X2) x o

x x x x x x x o

o

x x x x x x

x x x x x

X2

Рис.2.2

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

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

между данным объектом w и совокупностью объектов (w1,w2,....,wn),

представляющих (описывающих) каждый класс. Так для сравнения с классом Wg

это выглядит так

[pic]

где kg - количество объектов, представляющих Wg-й класс.

При этом в качестве методов измерений расстояния между объектами

d(w,wg) могут использоваться любые методы (творческий процесс здесь не

ограничивается).

Так, если сравнивать непосредственно координаты (признаки), то

[pic]

где N - размерность признакового пространства.

Если сравнивать угловые отклонения, то рассматривая вектора,

составляющими которых являются признаки распознаваемого объекта w и класса

wg, будем иметь:

[pic]

где ||Xw|| и ||Xwg|| - нормы соответствующих векторов.

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

можно учитывать и их веса Vj (устанавливать степень доверия или

важности). Тогда рассмотренное среднеквадратическое расстояние принимает

следующий вид:

[pic]

В алгоритмах распознавания, использующих вероятностные признаки, в

качестве меры близости используется риск, связанный с решением о

принадлежности объекта к классу Wi, где i - номер класса. (i=1,2,..,m.).

Описания классов, как мы недавно рассмотрели

[pic]

В рассматриваемом случае к исходным данным для расчета меры близости

относится платежная матрица вида:

[pic]

Здесь на главной диагонали - потери при правильных решениях. Обычно

принимают Сii=0 или Cii<0.

По обеим сторонам от главной диагонали - потери при ошибочных

решениях. В каждой системе эти потери свои, свойственные только ей.

Однако назначение их - творчество разработчика системы распознавания.

Если вектор признаков распознаваемого объекта w - [pic], то риск,

связанный с принятием решения о принадлежности этого объекта к классу Wg,

когда на самом деле он может принадлежать классам W1,W2,...,Wm, наиболее

целесообразно определять как среднее значение потерь

С1g, C2g,...,Cmg ,

то есть, потерь, стоящих в g-ом столбце платежной матрицы.

Тогда этот средний риск можно записать как определение МОЖ

[pic]

Здесь P(Wi/Xw) - апостериорная вероятность того, что w[pic]Wi.

Для исходных данных, а именно описаний классов эта вероятность

легко может быть определена в соответствии с теоремой гипотез или по

формуле Байеса

[pic]

Вероятности и плотности, входящие в формулу - ни что иное как

характеристики описания классов в вероятностной системе.

Для алгоритмов, основанных на логических признаках, понятие “мера

близости” не имеет смысла. Вспомним упрощенный пример, рассмотренный нами

для логических признаков заболеваний (простой простуды и ангины).

Имея значения признаков А,B,C, достаточно подставить их в булевы

соотношения между классами и признаками, чтобы сразу получить результат

как истинность или ложность булевой функции описания того или иного класса.

Действительно, пусть признаки приняли следующие значения:

-Повышенная температура: A=1

-Насморк: B=0

-Нарывы в горле: C=1

Тогда подстановка их в булевы соотношения даст следующий результат:

[pic]

[pic]

То есть, истинным является второе соотношение, соответствующее

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

Для алгоритмов, основанных на структурных (лингвистических)

признаках, понятие “меры близости” более специфично.

С учетом того, что каждый класс описывается совокупностью предложений,

характеризующих структурные особенности объектов соответствующих

классов, распознавание неизвестного объекта осуществляется

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

предложений в составе описания какого-либо класса.

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

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

описания каждого класса.

Рассмотрев задачу №5 , мы фактически завершили рассмотрение круга

задач создания СР. В то же время уже отмечалось, что создание СР

осуществляется последовательными приближениями по мере получения

дополнительной информации. В этом ряду последовательных приближений

главную роль играют признаки распознавания. От эффективности их набора

зависит, эффективность системы в целом. В процессе совершенствования

системы указанный набор пополняется, неэффективные признаки исключаются.

Поэтому одной из задач создания СР должна быть и задача перехода от

априорного словаря признаков к рабочему. То же касается и априорного

алфавита классов.

ЗАДАЧА № 6

Определение рабочего алфавита классов и рабочего словаря признаков

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

Настоящая задача на уровне разработки, прошедшей этапы решения задач 1

- 5, по крайней мере уже может быть поставлена, так как в результате

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

приближения (априорный алфавит классов и априорный словарь признаков,

выбран алгоритм распознавания).

Суть стоящей задачи - разработка такого (рабочего) алфавита классов

и такого (рабочего) словаря признаков, которые обеспечили бы максимальное

значение показателя эффективности распознавания. То есть, из априорного

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

ограничениях на их получение (измерение) доставить максимум вероятности

правильной классификации объектов (явлений) и (или) минимальные вероятности

ошибочных классификаций создаваемой системой. Такой выбор не может не

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

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

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

моделирования. Об этом мы говорили при создании априорного словаря

признаков. К этому мы вернемся при специальном рассмотрении вопросов

моделирования систем распознавания.

Что же касается приемов, обеспечивающих отбор в процессе оптимизации

систем распознавания, то они являются также предметом отдельного

рассмотрения.

Т е м а 3

Классификация систем распознавания

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19