1.5. Алгоритм распознавания, основанный на вычислении оценок (АВО)
Алгоритм распознавания АВО основан на принципе прецедентности или частичной прецедентности. Он сравнивает описания распознаваемого объекта
с матрицей
и принимает решение о том, к какому классу следует отнести этот объект. При этом решение выносится в результате вычисления степени сходства распознаваемого объекта с теми объектами, принадлежность которых к заданным классам известна. Т.е. сравнивает последнюю строку матрицы
с каждой из предшествующих строк по определенному критерию близости.
Описание алгоритма АВО
Рассмотрим основные идеи алгоритма АВО.
1) Пусть заданы стандартные описания объектов
,
и
,
,
. Требуется определить принадлежность предъявленного для распознавания объекта
к какому-либо из классов
. Если введен критерий близости некоторых частей описания
к соответствующим частям
и
, то можно сформировать обобщенный критерий близости объекта
к соответствующим объектам
. В простейшем случае обобщенный критерий определяют в виде суммы частных критериев, относящихся к отдельным частям описания.
В результате, характеристику вида
, где
и
- значения соответствующие близости
к
и
естественно считать значением функции принадлежности объекта
классу
. Величина
называется оценкой объекта
по классу
.
Описания объектов
, предъявленных для распознавания, переводятся алгоритмом распознавания в числовую матрицу оценок
. Эта процедура включает 2 этапа: сначала подсчитывается оценка
по каждой строке матрицы
, а затем эти оценки используются для получения суммарных оценок по каждому из классов
.
2) Рассмотрим процедуру построения оценок
, используемую в тесовых алгоритмах АВО. В основе тестовых алгоритмов лежит понятие “теста”.
Тестом матрицы
называется совокупность таких столбцов
, что после удаления из матрицы
всех столбцов за исключением указанных
, в полученной матрице
любые две строки, принадлежащие разным классам, будут различны.
Тест называется тупиковым, если никакая его часть не является тестом (т.е. тупиковый тест - это такой тест, что нельзя удалить из него ни одного столбца (признака), без потери способности распознавания).
Пусть
- множество всех тупиковых тестов матрицы
и
. Выделим в описании распознаваемого объекта
часть
, соответствующую признакам
и сопоставим ее со всеми частичными описаниями
объектов матрицы
, где
,
(
).
Подсчитаем число совпадений -
, которое представляет собой число строк этого класса, близких к распознаваемой строке
по тесту Т. Аналогично вычисляется оценка
по остальным тестам (для каждого класса). Величина
(9)
представляет собой оценку объекта
по классу
.
Известны разновидности тестовых алгоритмов, в которых при формировании оценок
учитываются различия в представительности (“важности”) отдельных строк матрицы
и признаков, включенных в стандартные описания.
Для этого используются числовые коэффициенты - веса признаков и веса объектов. Чаще всего эти веса задаются с помощью экспертных оценок.
Для тестовых алгоритмов была предложена следующая мера важности признаков - “информационный вес” (Дмитриев):
(10)
где
- общее число тупиковых тестов матрицы
;
- число тупиковых тестов матрицы
, содержащих признак
.
Если учитываются веса признаков
и веса объектов матрицы
-
, то каждое совпадение частичного описания
объекта
с частичными описаниями
объектов из
, соответствующее некоторому тесту Т, оцениваем величиной
(11)
В результате оценка объекта
по классу
принимает следующий вид:
(12)
3) Переход от тестовых алгоритмов к АВО связан с расширением видов подмножеств множества признаков, по которым проводится сопоставление распознаваемого объекта с объектами из
, и построением эффективной формулы вычисления оценок
для разных случаев задания подмножеств множества признаков (в АВО они называются “опорными множествами“ алгоритма распознавания). В тестовых алгоритмах в качестве опорных множеств используются множества тупиковых тестов.
В АВО рассматриваются два случая нахождения опорных множеств:
- Наличие ограничений на систему опорных множеств алгоритма.
- Отсутствие ограничений на систему опорных множеств алгоритма.
В первом случае наиболее распространенными являются системы опорных множеств, составленных из всех подмножеств множества признаков заданной длины q, q=2,...,N-1.
Рассмотрим полный набор признаков
и выделим систему подмножеств множества признаков (систему опорных множеств алгоритма)
. Удалим произвольный набор признаков из строк
и обозначим полученные строки через
.
Критерий близости позволяет оценить похожесть строк
и
. Он состоит в следующем. Пусть усеченные строки содержат q первых признаков, т.е.
=
и
=
. Строки
и
считаются похожими , если выполняются не менее чем
неравенств вида:
,
(13)
Величины
входят в качестве параметров в модель класса алгоритмов типа АВО. (Обычно
).
Рассмотрим процесс вычисления оценок по подмножеству
. Для остальных подмножеств она аналогична. В матрице
выделяются столбцы, соответствующие признакам, входящим в
(остальные столбцы выбрасываются). Проверяется близость строки
со строками
,
, а, следовательно, и принадлежность классу
(по критерию (13)).
Число строк этого класса, близких к классифицируемой строке
по выбранному критерию (13), обозначим через
. Аналогично вычисляются оценки для всех остальных классов:
.
Эти операции производятся для всех опорных множеств
и для каждого из них вычислили соответствующие оценки близости:
,
(14)
Величины
(15)
представляют собой оценки строки
для соответствующих классов по системе опорных множеств алгоритма
. На основании анализа этих величин принимается решение либо об отнесении объекта
к одному из классов
, k=1..m, либо об отказе от распознавания.
Решающее правило может принимать разные формы:
- Либо распознаваемая строка относится к классу с максимальной оценкой;
- Либо эта оценка будет превышать оценки для всех остальных классов не меньше, чем на определенную пороговую величину
;
- Либо величина отношения соответствующей оценки к сумме оценок для всех остальных классов не менее некоторого порога

Выводы
Определение класса АВО сводится к формализации следующих этапов процедуры распознавания:
- Выделяется система опорных множеств алгоритма, по которым производится анализ распознаваемых объектов
- Вводится мера близости на множестве частичных описаний объектов
- Задаются правила:
- правило вычисления оценки для пар объектов по значению степени подобия эталонного и распознаваемого объектов;
- правило формирования оценок по фиксированному опорному множеству для каждого из эталонных классов на основе оценок для пар объектов;
- правило формирования суммарной оценки для каждого из эталонных классов по всем опорным множествам;
- правило принятия решений на основе суммарных оценок, обеспечивающих отнесение распознаваемого объекта к одному из классов или отказ от классификации данного объекта
|
Если строить вычислительную процедуру по приведенному описанию алгоритма, то при большой мощности системы опорных множеств требуется значительный объем вычислений. Так при выборе в качестве системы опорных множеств всех подмножеств множества признаков мощности q число опорных множеств будет равно
, а число слагаемых в формуле, определяющей величину
, равно
.
Известны два метода, комбинация которых позволяет получить простые формулы для практически важных моделей АВО (при условии, что используются пороговые функции близости, принимающие значения 0 и 1) и
(вес опорного множества равен сумме весов входящих в него признаков)
Первый метод предложен Журавлевым (1978) использует свойство оценок для классификации по опорному множеству
,
используется оценка вида
,
где
- совокупность номеров признаков, определяющих опорное множество
,
- функция близости частичных описаний объектов
и
, принимающая значения 1 или 0 , в зависимости от числа выполненных неравенств вида
,
.