1.5. Алгоритм распознавания, основанный на вычислении оценок (АВО)

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

Описание алгоритма АВО

Рассмотрим основные идеи алгоритма АВО.

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

2) Рассмотрим процедуру построения оценок, используемую в тесовых алгоритмах АВО. В основе тестовых алгоритмов лежит понятие “теста”.

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

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

Известны разновидности тестовых алгоритмов, в которых при формировании оценокучитываются различия в представительности (“важности”) отдельных строк матрицы и признаков, включенных в стандартные описания.
Для этого используются числовые коэффициенты - веса признаков и веса объектов. Чаще всего эти веса задаются с помощью экспертных оценок.
Для тестовых алгоритмов была предложена следующая мера важности признаков - “информационный вес” (Дмитриев):
(10)
где- общее число тупиковых тестов матрицы;
- число тупиковых тестов матрицы, содержащих признак.

Если учитываются веса признакови веса объектов матрицы-, то каждое совпадение частичного описанияобъектас частичными описаниямиобъектов из, соответствующее некоторому тесту Т, оцениваем величиной
(11)
В результате оценка объектапо классупринимает следующий вид:
(12)

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

В АВО рассматриваются два случая нахождения опорных множеств:

  1. Наличие ограничений на систему опорных множеств алгоритма.
  2. Отсутствие ограничений на систему опорных множеств алгоритма.
В первом случае наиболее распространенными являются системы опорных множеств, составленных из всех подмножеств множества признаков заданной длины q, q=2,...,N-1.

Рассмотрим полный набор признакови выделим систему подмножеств множества признаков (систему опорных множеств алгоритма). Удалим произвольный набор признаков из строк и обозначим полученные строки через.
Критерий близости позволяет оценить похожесть строки. Он состоит в следующем. Пусть усеченные строки содержат q первых признаков, т.е.=и=. Строкиисчитаются похожими , если выполняются не менее чемнеравенств вида:
,(13)
Величинывходят в качестве параметров в модель класса алгоритмов типа АВО. (Обычно).

Рассмотрим процесс вычисления оценок по подмножеству. Для остальных подмножеств она аналогична. В матрицевыделяются столбцы, соответствующие признакам, входящим в(остальные столбцы выбрасываются). Проверяется близость строкисо строками,, а, следовательно, и принадлежность классу (по критерию (13)).
Число строк этого класса, близких к классифицируемой строкепо выбранному критерию (13), обозначим через. Аналогично вычисляются оценки для всех остальных классов:.
Эти операции производятся для всех опорных множеств и для каждого из них вычислили соответствующие оценки близости:
,(14)
Величины
(15)
представляют собой оценки строкидля соответствующих классов по системе опорных множеств алгоритма. На основании анализа этих величин принимается решение либо об отнесении объектак одному из классов, k=1..m, либо об отказе от распознавания.

Решающее правило может принимать разные формы:
  1. Либо распознаваемая строка относится к классу с максимальной оценкой;
  2. Либо эта оценка будет превышать оценки для всех остальных классов не меньше, чем на определенную пороговую величину;
  3. Либо величина отношения соответствующей оценки к сумме оценок для всех остальных классов не менее некоторого порога

Выводы

Определение класса АВО сводится к формализации следующих этапов процедуры распознавания:
  1. Выделяется система опорных множеств алгоритма, по которым производится анализ распознаваемых объектов
  2. Вводится мера близости на множестве частичных описаний объектов
  3. Задаются правила:
  1. правило вычисления оценки для пар объектов по значению степени подобия эталонного и распознаваемого объектов;
  2. правило формирования оценок по фиксированному опорному множеству для каждого из эталонных классов на основе оценок для пар объектов;
  3. правило формирования суммарной оценки для каждого из эталонных классов по всем опорным множествам;
  4. правило принятия решений на основе суммарных оценок, обеспечивающих отнесение распознаваемого объекта к одному из классов или отказ от классификации данного объекта
Если строить вычислительную процедуру по приведенному описанию алгоритма, то при большой мощности системы опорных множеств требуется значительный объем вычислений. Так при выборе в качестве системы опорных множеств всех подмножеств множества признаков мощности q число опорных множеств будет равно, а число слагаемых в формуле, определяющей величину, равно.

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

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