Алгоритмы распознавания, основанные на вычислении оценок

 

Логические алгоритмы распознавания, рассмотренные выше, в ряде случаев не позволяют получить однозначное решение о принадлежности распознаваемого объекта к определенному классу. Ю. И. Журавлевым предложен класс алгоритмов, называемый алгоритмами распознавания, основанными на вычислении оценок (АВО), который дает возможность получить однозначное решение о принадлежности объекта к определенному классу [25, 26].

Пусть множество объектов {w} подразделено на классы Ω_i, i=1, ..., m, и для описания объектов используются признаки х_j, j=1, ..., N. Все объекты описываются одним и тем же набором признаков. Каждый из признаков может принимать значения из различных множеств, например, из следующих: {0, 1}, 0 — признак не выражен, 1 —признак выражен; {0, 1, ´}, ´ —информация о признаке отсутствует; {0, 1, ..., d} —степень выраженности признака имеет различные градации; [а, b] — признак принимает значения из числового отрезка; f_i(x₁ ..., x_N) — условная плотность распределения значений признаков. Априорная информация представляется в виде таблицы, содержащей описания на языке признаков {х_1, ..., x_N] всех объектов, принадлежащих различным классам (табл. 7.1). Алгоритм распознавания сравнивает описание распознаваемого объекта с описаниями всех объектов, содержащихся в таблице, и принимает решение о том, к какому классу отнести объект. Классификация основана на вычислении степени похожести (оценки) распознаваемого объекта, на объекты, принадлежность которых к классам известна. Эта процедура включает в себя два этапа: сначала подсчитывается оценка для каждого объекта из таблицы, а затем полученные оценки используются для получения суммарных оценок по каждому из классов Ω_i.

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

Рассмотрим полный набор признаков х = {х_1, ..., x_N} и выделим систему подмножеств множества признаков (систему опорных множеств алгоритма) S₁, ..., S_l. В АВО при наличии ограничений на систему опорных множеств обычно рассматриваются либо все подмножества множества признаков фиксированной длины k, k=2,..., N— 1, либо вообще все подмножества множества признаков.

Удалим произвольный поднабор признаков из строк w₁ w₂,..., w_rm, w¢ и обозначим полученные строки Sw₁, Sw₂,..., Sw_rm, Sw¢. Правило близости, позволяющее оценить похожесть строки Sw¢, соответствующей распознаваемому объекту w¢, и строки Sw_ri-_l+v, соответствующей произвольному объекту исходной таблицы, состоит в следующем (индекс v-гo объекта класса Ω_i, представляет собой сумму порядкового номера последнего объекта предшествующего класса Ω_i-1 — r_i-1 и порядкого номера v рассматриваемого объекта в данном класе Ω_i,; естественно, 1£v£r_i-r_i-1. Пусть «усеченные» строки содержат q первых признаков, т. е. и заданы пороги e₁ ..., e_q, d.

Строки читаются похожими, если выполняется не менее чем d неравенств вида

Величины e₁ ..., e_q входят в качестве параметров в АВО.

 

Таблица 7.1

 

Рассмотрим процедуру вычисления оценок по подмножеству S₁. Для остальных подмножеств она полностью аналогична. В табл. 7.1 выделяются столбцы, соответствующие признакам, входящим в S₁ остальные столбцы вычеркиваются. Проверяется близость строки S₁w¢ со строками S₁w₁ ..., S₁ w_r1, принадлежащими объектам класса Ω_i. Число строк этого класса, близких по выбранному критерию классифицируемой строки S₁w¢, обозначается Гs₁ (w¢, Ω₁); последняя величина представляет собой оценку строки w¢ для класса Ω_i по опорному множеству S₁. Аналогичным образом вычисляются оценки для остальных классов: Гs₂(w¢, Ω₂), ..., Гs₂ (w¢, Ω_m). Применение подобной процедуры ко всем остальным опорным множествам алгоритма позволяет получить систему оценок Гs₂ (w¢, Ω₁), ..., Гs₂ (w¢, Ω_m), ..., Гs_l (w¢, Ω₁)._.., Гs_l (w¢, Ω_m). Величины

 

(7.65)

 

представляют собой оценки строки w¢ для соответствующих классов по системе опорных множеств алгоритма S_A. На основании анализа этих величин принимается решение либо об отнесении объекта w¢ к одному из классов Ω_i, i= 1,..., m, либо об отказе от его распознавания. Решающее правило может принимать различные формы, в частности распознаваемый объект может быть отнесен к классу, которому соответствует максимальная оценка, либо эта оценка будет превышать оценки всех остальных классов не меньше чем на определенную пороговую величину h₁ либо значение отношения соответствующей оценки к сумме оценок для всех остальных классов будет не менее значения порога h₂ и т. д. Параметры типа h_х и h₂ также включаются в АВО.

Пример. Заданы следующая таблица обучения и подлежащий распознаванию объект w¢:

 

 

Пусть S₁= <x₁, x₂,> S₂ = <x₃,x₄>, S₃ = <x₅,x₆>; строки будем считать близкими, если они полностью совпадают.

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

 

 

Согласно решающему правилу, реализующему принцип простого большинства голосов, объект со' относится к классу Ω_i так как Г (w¢, Ω₁)>Г(w¢, Ω₂).

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

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

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

Остановимся на аналитических формулах, обеспечивающих эффективное вычисление оценок Г_i(w¢) при различных способах задания системы опорных множеств АВО:

1. Эффективные формулы при наличии ограничений на систему опорных множеств [25]:

a) S_A совпадает с системой всех подмножеств мощности к множества {х₁ ..., x_N}:

 

(7.66)

 

где р (w_r, w¢) — число выполненных неравенств вида

б) S_A совпадает с системой всех непустых подмножеств множества {х₁ ..., x_N}:

 

(7.67)

 

Пример. Проиллюстрируем применение формулы (7.67) на задаче, рассмотренной в предыдущем примере. Для вычисления оценок распознаваемого объекта w¢ по классам Ω₁ и Ω₂ необходимо определить величины р (w_1, w¢),..., р (w_6, w¢); как и раньше, будем полагать e₁, ..., e₆=0. В таком случае имеем: p(w_1, w¢) =4; р(w_2, w¢) = 3; р(w_3, w¢)=3; р(w_4, w¢) = 3; р(w_5, w¢) = 2; р(w_6, w¢) =5. Применение формулы (7.67) позволяет вычислить значения оценок Г₁(w¢)=(1/3) [(2⁴-1)+(2³-1)+(2³-1)]=29/3, Г₂(w¢)=1/3[(2³-1) + (2²-1)+(2⁵-1)]=41/3. Подстановка значений этих оценок в решающее правило, реализующее принцип простого большинства, приводит к отнесению объекта со' к классу П₂. Расхождение с результатом предыдущего примера определяется изменением системы опорных множеств алгоритма. Оно лишний раз свидетельствует о том, как необходимо чрезвычайно внимательно относиться к тому, по каким признакам и комбинациям признаков следует сопоставлять объекты при распознавании.

Отметим, что число непустых подмножеств множества, содержащего шесть признаков, равно 2⁶— 1 =63. Таким образом, при отсутствии формулы, элиминирующей перебор, процедуру прямого сравнения распознаваемого объекта, w¢ со строками обучающей таблицы по всем опорным множествам пришлось бы выполнить 6×63 = 378 раз.

2. Эффективные формулы при отсутствии ограничений на систему опорных множеств [26].

Практика распознавания показывает, что в некоторых случаях априори известны поднаборы признаков, которые следует учитывать при сопоставлении распознаваемого объекта с объектами обучающей таблицы. Эти подмножества признаков не всегда совпадают с частными случаями (7.66) и (7.67); они могут иметь различную длину, исключать запрещенные комбинации и т. п. В [26] аналитические формулы получены для случая произвольных опорных множеств.

Расширение области применения АВО основано на введении характеристической булевой функции системы опорных множеств алгоритма f_SA и установлении взаимно однозначного соответствия между подмножествами множества признаков и булевыми векторами длины N (вершинами N-мерного единичного куба) [26].

Пример. Заданы таблица обучения и подлежащий распознаванию объект w¢ (W=4):

 

 

Закодировав вхождение признака в опорное множество через 1, а невхождение — через 0, каждому подмножеству множества признаков <х₁, х₂, х₃, х₄> можно сопоставить бинарный вектор, или, что то же самое, вершину единичного четырехмерного куба (рис. 7.3).

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

Пусть (вершина 6), ,(вершина 14).

В таком случае

В [26] показано, что в тех случаях, когда множество единиц fs_A образует в единичном Af-мерном кубе интервал или сумму непересекающихся интервалов, также существуют аналитические формулы для вычисления оценок. Напомним, что подмножество вершин единичного N-мерного куба называется интервалом, если оно соответствует некоторой элементарной конъюнкции. Очевидно, что все грани, ребра и вершины единичного N-мерного куба являются интервалами.

Система опорных множеств организована следующим образом (соответствующий интервал представлен ребром, соединяющим вершины 6 и 14): в нее включены все признаки, входящие в ДНФ характеристической функции без отрицания (х₂ и х₃), не включены признаки, входящие в ДНФ с отрицанием (х₄), а по остальным признакам (х₁) происходит полная вариация, т. е. рассматриваются подмножества, как включающие, так и не включающие эти признаки (x_l, x₂, х₃ и х₂, х₃).

Эффективная аналитическая формула для вычисления оценок в случаях, когда характеристической функции системы опорных множеств соответствует интервал, имеет вид

 

(7.68)

 

В (7.68) учитывается вклад только тех строк таблицы обучения («эффективных»), постоянная часть которых (в нашем случае <x₂,x₃> близка постоянной части w¢; р* (w¢_r„ w¢) — число выполненных неравенств вида |a_j-b_j|£e_j,- на варьируемой части (здесь <x₁>).

 

 

Рис. 7.3

 

Таким образом, при условии e₁ ..., e₆=0 и, учитывая, что эффективны в Ω₁ строки w₁ и w₃, в Ω₂ — строки w₄ и w₆, р* (w¢₂, w¢)= = 0,р*( w¢₃, w¢) = 1, р*( w¢₄, w¢)=0, р*( w¢₆, w¢)=1, имеем: Г₁(w¢)-= (1/3)(2⁰ + 2¹)=1;Г₂=(w¢) = (1/3)(2⁰+2¹)=1.

Полученный результат означает, что при указанном выборе системы опорных множеств строка w¢ не классифицируется.

Если характеристической функции соответствует сумма непересекающихся интервалов (представляется ортогональной ДНФ), как, например, в случаях S_A = {S₁, S₂, S₃, S₄, S₅}, S₁ = <x₂, x₃> (вершина б), S₂ = <x_1, x₂, x₃> (вершина 14), S₃ = <x_1, x₃, x₄> (вершина 11), S₄=<x_1, x₃> (вершина 10), S₅ = <x₁, x₂, x₄> (вершина 13), то при вычислении оценок (7.68) применяется к каждому интервалу отдельно и результаты суммируются.

В [26] показано, что сложность формулы вычисления оценок в АВО при произвольной S_A пропорциональна сложности ДНФ, представляющей характеристическую функцию системы опорных множеств алгоритма. Это означает, что построение простой формулы для вычисления оценок Г_i(w¢) связано с задачей минимизации булевых функций в классе ДНФ [36], а точнее — с задачей построения кратчайшей ортогональной ДНФ или ДНФ, в которой каждый интервал имеет небольшое число пересечений с соседними. В общем случае задача такого синтеза неразрешима и потому следует пользоваться приближенными алгоритмами, обеспечивающими получение «достаточно простых» ортогональных ДНФ или ДНФ с небольшим числом взаимных пересечений интервалов [26].

Таким образом, если для вычисления расстояний r_j(a_j, b_j) существует эффективный алгоритм и число операций при одном таком вычислении не превосходит некоторой величины Q, то число операций при вычислении всех величин Г_i(w¢),i=1, ..., m не превосходит 2QNm.

Число операций при распознавании одного объекта в фиксированном алгоритме А пропорционально «площади» таблицы Т_N,m с коэффициентом пропорциональности, не превосходящим 2Q.

Сведение задачи построения экстремальных алгоритмов типа АВО к отысканию экстремумов функции многих переменных было обосновано Ю. И. Журавлевым. Для проведения оптимизации могут быть применены методы переборного типа (при небольшом числе параметров), градиентного типа или случайного поиска.

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