_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005) (_учебник_ Журавлев Ю.И. Распознавание. Математические методы. Программная система. Практические применения (2005).pdf), страница 7

Каждый предикат отвечает на вопрос, выполняется ли некоторое свойствона объекте S или нет. Примерами признаковых предикатов могут быть1, если (1.5  x2 ( S )  3.2) & ( x5 ( S )  0)P1 ( S )  в противном случае,0,1, если 0.5 x2 ( S )  1.2 x7 ( S )  1P2 ( S )  в противном случае.0,Каждой строке Si  (ai1 , ai 2 ,...ain ) таблицы обучения Tnml  aij mn поставим в соответствиебинарную строку значений предикатов на описании Si  ( yi1 , yi 2 ,..., yiN ), yij  Pj ( Si ) .

В0  yij mNрезультате, таблице Tnml  aij mn будет соответствовать бинарная таблица TNmlбинарных «вторичных описаний» объектов обучения.Бинарное дерево называется решающим, если выполнены следующие условия:1. каждая внутренняя вершина помечена признаковым предикатом из  ;2. выходящие из вершин дуги помечены значениями, принимаемыми предикатами ввершине;3. концевые вершины помечены метками классов;4.

ни в одной ветви дерева нет двух одинаковых вершин.Пример подобного дерева для конфигурации из трех классов (рис.11) приведен на рис. 12.32x2  x1x2K3K3  x1K1K2Рис. 11. Конфигурация объектов трех классов. Объекты классов K1 , K 2 , K 3 обозначены, соответственно,символами , , y101y210y3010K3K20K3y4y21K201y2K20K31K1Рис.12. Решающее дерево для классов рис. 11На рис.12 приведено некоторое решающее дерево, позволяющее правильно распознаватьобъекты трех классов, изображенных на рис.11.

Вершины дерева помечены следующимипредикатами:y1 " x1  0" , y2 " x12  x22  1" , y3 " x1  x2 " , y4 " x2  0".Данномурешающему дереву соответствуют характеристические функции классов f1 ( S )  y1 y2 y3 y4 ,f 2 ( S )  y1 y2  y1 y2 y3  y1 y3 y4 , f 3 ( S )  y1 y2  y1 y2 y3  y1 y2 y3 y4 , принимающие значение 1 наобъектах «своего» класса и 0 на объектах остальных классов.33Приведем еще один пример решающего дерева (рис.13), построенного непосредственно 0 01 1 1   K11 1 1 01 по таблице обучения: T5.4, 2 =. 1 0 111  K 2 0 1 01 0 (1.11)В качестве признаковых предикатов используются y1  x1 , y2  x2 .y101y2010010K1K2K2K1Рис.13. Решающее дерево бинарной таблицы обучения (1.11)Здесь в качестве приближений для характеристических функций классов выбраныфункцииf1 ( S )  x1 x2  x1 x2 ,f 2 ( S )  x1 x2  x1 x2 .

В данном примере, для построениярешающего дерева использованы только два признака.Задачапостроения решающего деревапо обучающим данным решаетсянеоднозначно, методам построения решающих деревьев посвящена обширная литература/16, 17, 41, и др./.1.3. Алгоритмы распознавания, основанные на принципе частичнойпрецедентностиНастоящий класс алгоритмов выделен в отдельный раздел по несколькимпричинам. Представляя исторически логические подходы в теории распознавания, врамках данного подхода разработана также теория алгоритмов вычисления оценок,объединяющая все существующие методы распознавания и положенная в основуалгебраического подхода в теории распознавания. Теоретические основы алгоритмовчастичной прецедентности (вычисления оценок, голосования, или комбинаторнологических алгоритмов) описаны в многочисленных научных публикациях /25-27/, идругие.

В настоящем разделе описаны некоторые алгоритмы данного класса, широкоиспользуемые в практическом распознавании.Принципиальная идея данных алгоритмов основана на отнесении распознаваемогообъекта S в тот класс, в котором имеется большее число «информативных» фрагментов34эталонныхобъектов(«частичныхпрецедентов»),приблизительноравныхсоответствующим фрагментам объекта S. Вычисляются близости – «голоса» (равные 1 или0) распознаваемого объекта к эталонам некоторого класса по различным информативнымфрагментам объектов класса. Данные близости («голоса») суммируются и нормируютсяна число эталонов класса.

В результате вычисляется нормированное число голосов, илиоценка объекта S за класс  j (S ) – эвристическая степень близости объекта S к классу K j .После вычисления оценок объекта за каждый из классов, осуществляется отнесениеобъекта к одному из классов с помощью порогового решающего правила.1.3.1. Тестовый алгоритм.Тестовый алгоритм распознавания был опубликован в /15/ и базируется на понятиитеста, введенного в 1956 году С.В.Яблонским. В классическом изложении тестовыйалгоритмбылпредназначендлябинарныхик-значныхпризнаков.Пустьxi ( S )  {0,1,..., k  1}, i  1,2,..., n.Определение 1.

Тестом таблицы Tnml называется совокупность столбцов {i1 , i2 ,..., ik } таких,что после удаления из Tnml всех столбцов, за исключением имеющих номера {i1 , i2 ,..., ik } , вполученной таблице Tnk ,m ,l все пары строк, принадлежащих разным классам, различны.Тест {i1 , i2 ,..., ik } называется тупиковым, если никакая его истинная часть не являетсятестом /59/.Пустьнайденомножество{T }тупиковыхтестовтаблицыTnmlиT  {i1 , i2 ,..., ik }  {T } . Выделим в описании распознаваемого объекта S фрагмент описания(ai1 , ai2 ,..., aik ) , соответствующий признакам с номерами i1 , i2 ,..., ik .

Сравним (ai1 , ai2 ,..., aik )со всеми фрагментами (ati1 , ati2 ,..., atik ) объектов St , t  1,2,..., m, таблицы Tnml .Число совпадений (ai1 , ai2 ,..., aik ) с (ati1 , ati2 ,..., atik ) , t  m j 1  1, m j 1  2,..., m j , для каждогоj  1,2,..., l , m0  0, ml  m , обозначим через G j (T ) .Величина j ( S ) 1 G j (T )m j  m j 1 T{T }(1.12)называется оценкой S по классу K j . Имея оценки 1 (T ), 2 (T ),..., l (T ) объект S легкоклассифицируется с помощью решающих правил.

Например, он относится в тот класс, закоторый получена его максимальная оценка. В случае наличия нескольких классов смаксимальными оценками, происходит отказ от его классификации.35Если отдельное совпадение в (1.12) назвать «голосом» в пользу класса K j , то выражение(1.12) будет нормированным числом голосов за данный класс. В связи с даннойинтерпретацией, алгоритмы с подобной схемой вычисления оценок называют такжеалгоритмами голосования.Тупиковые тесты широко используются для оценки информативности (важности)признаков.

Пусть N i - число тупиковых тестов таблицы Tnml , содержащих i-й столбец , аN  {T } - общее число тупиковых тестов таблицы. Тогда вес i-го признака определяетсякакpi Ni. Чем больше вес, тем важнее признак для описания объектов. ЭтоNутверждение основывается на следующем рассуждении. Таблица Tnml является исходнымописанием классов и признаков. Тупиковый тест есть несжимаемое далее по признакамописание классов, сохраняющее разделение классов. Чем в большее число такихнеизбыточных описаний входит i-й признак, тем он важнее.Задача нахождения множества тупиковых тестов таблицы Tnmlсводится квычислению всех тупиковых покрытий строк некоторой бинарной матрицы ее столбцами.Пусть Tnml  aijmn, где aij  x j ( S i ) {0,1,..., k  1} .

Таблице T nml ставится в соответствиематрица сравнения по признакам всевозможных пар объектовC  cijN,N nгде (m  mi ji , j 1, 2,...,lii 11, aj  aj ,cij  i  i ( ,  ) ,0,aa,jjиз различных классовS  K u , S   K v , u  v ,)(m j  m j 1 ) .Столбцы ( i 1 , i 2 , . . . , i k ) образуют покрытие строк матрицыi  1,2,...,N ,j {i1 , i2 ,..., ik } :C  cijN n, еслисij  1 .

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

При решении практических задач достаточно нахождение лишь части тупиковыхтестов для вычисления оценок согласно (1.12). В случае наличия вещественнозначныхпризнаков используют обычно один из следующих двух подходов. Область определениякаждого вещественнозначного признака разбивается на k интервалов. Значение признака36из i- го интервала полагается равным i-1.

Далее задача распознавания решаетсяотносительно полученной k- значной таблицы обучения и k- значных описанийраспознаваемых объектов. Другой подход связан с введением числовых пороговыхпараметров для каждого признака. Для вещественнозначных таблиц вводится аналогтупиковых тестов, в котором требование несовпадения значений признаков заменяетсятребованием их различия не менее чем на соответствующий порог. В обоих подходах привыборе значности новой таблицы или значений пороговых параметров необходимоучитывать, что соответствующие матрицы сравнения не должны содержать нулевыхстрок, поэтому значность (или пороговые параметры) следует выбирать из требованияотделимости k- значных «образов» эталонных объектов различных классов (илиотделимости с точностью до пороговых значений).1.3.2. Алгоритмы распознавания с представительными наборами.Другими алгоритмами данного вида являются алгоритмы типа “Кора” /3, 10/, вкоторых опорные множества связаны со значениями признаков конкретных объектов.S  KПустьj,апризнакиu  {xi1 ( S ), xi2 ( S ),..., xik ( S ), }K j,еслидлялюбогоxit ( S )  xit ( S  ), t  1,2,..., k ,принимают0или1.Наборназовем представительным набором для классаS   T nml ,S   Kнезначениявыполнено.jхотябыПредставительныйодноизнаборравенствназываетсятупиковым, если любой его собственный поднабор не является представительнымнабором, т.е.

для любого его поднабора существует равный ему поднабор в каком-либодругом классе. Таким образом, тупиковый представительный набор некоторого классаKjесть несократимый фрагмент некоторого эталона данного класса, для которого нетравных ему фрагментов эталонов других классов.Пусть вычислено V j множество тупиковых представительных наборов для класса K j .Тогда степень близости распознаваемого объектаSк классу Kjпо заданномумножеству тупиковых представительных наборов V j можно оценить по формулеj ( S ) 1Vj B( S , u )(1.13) ,uV jгде B ( S , u ) равно 1, если в признаковом описании объекта S имеется фрагмент u. Далееклассификация объекта осуществляется по максимальной из вычисленных оценок, как и в37тестовом алгоритме.

Таким образом, в данном алгоритме с представительными наборамираспознаваемый объект относится в тот класс, для которого он имеет максимальную частьтупиковых представительных наборов в своем признаковом описании. Отметим, что вмодели с представительными наборами (как и для тестового алгоритма) возможны идругие способы вычисления оценок (1.13). Например, другие нормировки, весовыекоэффициенты перед B ( S , u ) , значения которых равны числу эталонов класса K j , вкоторых встречается u, или значения которых находятся в результате оптимизации моделираспознавания (см.