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

1.3.4) .Для нахождения тупиковых представительных наборов, содержащихся в некоторомэталоне S j , формируются матрицы сравнения S j со всеми эталонами других классов.Тупиковыепокрытияданныхматрицсравненияиопределяюттупиковыепредставительные наборы. Однако, если для поиска тупиковых тестов таблицы T nmlтребуется решать задачу на покрытия для матрицы из N  (m  mi ji , j 1, 2,...,lii 1)(m j  m j 1 )строк и n столбцов, то для поиска тупиковых представительных наборов объекта Si  K jзадача на покрытия решается для матрицы из (m  m j ) строк и n столбцов. Такимобразом, нахождение множества всех тупиковых представительных наборов таблицы T nmlтребует решения m задач на покрытия но «малой » размерности.

Эффективные алгоритмырешения данных задач разработаны Дюковой /22/.Вопрос обобщения алгоритмов распознавания с представительными наборами наслучаи k- значной и вещественнозначной информации информации решается аналогичнотестовому алгоритму. Множество допустимых значений некоторого признака делится наконечное число интервалов, каждому из которых приписывается целое число 0, 1, 2,…,или k-1. Таблице T nml и распознаваемым объектам ставятся в соответствие строки новыхцелочисленныхзначенийпризнаков.Далеепроцессопределениятупиковыхпредставительных наборов и распознавания полностью идентичен бинарному случаю.Другое распространение на вещественнозначные признаки связано с введениемпороговыхпараметров1 ,  2 ,...,  nпредставительного набора: набориследующеймодификациейu  {xi1 ( S ), xi2 ( S ),..., xik ( S ), }понятияназываетсяпредставительным набором для класса K j , если для любого S   T nml ,S   Kjбы одно из неравенств xt ( S )  xt ( S  )   t , t  i1 , i2 ,..., ik будет невыполненным.хотя38Заметим, что дискретизация признаков или введение пороговых параметров 1 ,  2 ,...,  nздесь могут быть индивидуальны для каждого эталона.

Главным требованием их выбораявляется отделимость рассматриваемого объекта Si  K j относительно эталонов из СK j .Отметим, что в отличие от тестового алгоритма, описанная модель с представительныминаборамидопускаетпересечениеклассов.Впоследнемслучаеоказываются«бесполезными» объекты, по которым классы пересекаются, поскольку данные объектыне содержат представительных наборов. Впрочем, существуют модификации понятияпредставительного набора, допускающие и пересечение классов.1.3.3.

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

Тестовый алгоритм и алгоритмы спредставительными наборами могут быть представлены как частные случаи более общейконструкции. Ниже будут приведены лишь некоторые основные способы выполненияданных этапов. Подробно данные вопросы рассмотрены в /25 - 27/.1. Задание системы опорных множеств алгоритма. Первым шагом определенияалгоритмов вычисления оценок (АВО) является задание множества подсистем признаков,по которым осуществляется сравнение объектов. Пусть  A - некоторая системаподмножеств множества {1,2,…,n}, называемая системой опорных множеств алгоритма A.Элементы = {i1 , i2 ,..., ik }   A называются опорными множествами алгоритма.

Ониопределяютномера признаков, покоторымсравниваютсячастиэталонныхираспознаваемых объектов. Примером выбора системы опорных множеств  A являетсямножество тупиковых тестов. Каждому подмножеству = {i1 , i2 ,..., ik } можно поставить вовзаимнооднозначноесоответствиехарактеристическийбулевскийвектор  {1 ,  2 ,..., n } , в котором  j  1, j  i1 , i2 ,..., ik , а остальные компоненты равнынулю. В силу данного соответствия    , использование данных величин будет для насравнозначным.Множество всех n-мерных булевских векторов определяет дискретный единичныйnкуб E  { :   (1 ,  2 ,..., n )} , i {0,1}, i  1,2,..., n . Число элементов куба равно2n .39Теоретические исследования свойств тупиковых тестов для случайных бинарныхтаблиц показали, что характеристические векторы «почти всех тупиковых тестов» имеютасимптотически (при неограниченном возрастании размерности таблицы обучения)приблизительно одну и ту же длину.

Это явилось одним из обоснований выбора вкачестве множества  A всевозможных подмножеств {1,2,…,n} длины k. Значение kнаходится из решения задачи обучения (оптимизации модели) или задается экспертом. Витоге, широко распространенными подходами к выбору  A являются(наряду ступиковыми тестами) следующие два:а)  A = { :   k} ;b)  A  {},   {1,2,..., n},   .Второй способ выбора системы опорных множеств, как всевозможных подсистем{1,2,…,n}, не требует нахождения подходящего значения параметра k.2.

Задание функции близости. Пусть фиксировано некоторое опорное множество  исоответствующий ему характеристический вектор . Фрагментобъектаxi1 ( S ), xi2 ( S ),...xik ( S )S  ( x1 ( S ), x2 ( S ),...xn ( S ) , соответствующий всем единичным компонентамвектора , называется -частью объекта, и обозначается S.

Под функцией близостиB ( S i , S j ) будет пониматься функция от соответствующих -частей сравниваемыхобъектов, принимающая значение 1 («объекты близки») или 0 («объекты далеки»).Приведем примеры подобных функций.1, | xi ( S )  xi ( S ) |  i , i : i  1,   ,B(S,S)а)    = иначе.0,Здесь( 1 ,  2 , . . . ,  n )- неотрицательные параметры, именуемые «точности измеренияпризнаков».1,b) B ( S , S  ) = 0,i| xi ( S )  xi ( S  ) |  ,иначе.Здесь  также некоторый неотрицательный параметр алгоритма.3. Оценка близости объекта S к эталонному объекту S i для заданной -части. Даннаячисловаявеличинаформируетсядополнительных параметров.a) ( Si , S ) = B ( Si , S ) .наосновефункцииблизостии,возможно,40b)c) ( Si , S ) = w B ( Si , S ) , где w ( Si , S ) =  i ( p )Bj: j 1jSiстепень важности объекта- «вес» опорного множества.( Si , S ) .Здесьi- параметры, характеризующие(информативность объекта), аp1 , p 2 ,...

p n- веса(информативность) признаков.4. Оценка объекта S за класса) Функция  j ( S ) Kjдля заданной -части.1  (Si , S ) является примером естественной оценки(m j  m j 1 ) Si K jблизости объекта к классу для заданного подмножества признаков.5. Оценка объекта S за классKj .Данная функция задает суммарную степень близости распознаваемого объекта S к классуK j . Приведем обычно используемые выражения для ее вычисления.a)  j ( S )  Ab)  j ( S )  v jj(S ) . Aj( S ) , гдеvj- «вес» классаKj .Например, в статистической теории распознавания аналогами параметровvjявляютсяаприорные вероятности классов, которые характеризуют, насколько часто встречаютсяобъекты различных классов .6. Решающее правило.Решающее правило есть правило (алгоритм, оператор), относящее объект повектору оценок (1 ( S ), 2 ( S ),..., l ( S )) в один из классов, или вырабатывающее дляобъекта «отказ от распознавания».

Отказ является более предпочтительным вариантомрешения в случаях, когда оценки объекта малы за все классы (объект являетсяпринципиально новым, аналоги которого отсутствуют в обучающей выборке), или онимеет две или более близкие максимальные оценки за различные классы (объект лежит награнице классов).В формальной постановке, решающее правило r вычисляет для распознаваемогообъектаSповекторуоценок( S )  (1 ( S ), 2 ( S ),..., l ( S ))вектор41r (( S ))  (1A ( S ), 2A ( S ),..., lA ( S )), i ( S )  {0,1, }, i  1,2,..., l.Интерпретация обозначенийприведена ранее в (1.1).а) Пример простейшего решающего правила – отнесение объекта в единственный класс,за который он имеет максимальную оценку.1,  j ( S )  i ( S ), i  1,2,..., l , i  j,иначе.0, jA ( S )  b) Для «осторожного» принятия решения относительно новых объектов, существеннонепохожих на объекты обучающей выборки, или находящихся на границе двух и болееклассов, обычно достаточно введение в решающее правило двух пороговых параметровj ( S )  i ( S )  1 , i  1,2,..., l , i  j,1,l jA ( S )  j ( S )   2  i ( S ),i 10,иначе.Здесь 1 ,  2  0.c) Линейное решающее правило в пространстве R l оценок определяется какlii(S)c 1,j j1,j 1lAi i ( S )  , c1    ij  j ( S )  c2i ,j 1lii0,(S)c,jj2j 1Здесь1 ,  2 ,  ij , c1i , c2i(1.14)- параметры алгоритма.

В решающем правиле (1.14) наличиедвух или более единиц интерпретируется как «объект принадлежит нескольким классам».Когда вектор (1A ( S ), 2A ( S ),..., lA ( S )) состоит из одних нулей говорят, что данный объект– выброс, он не похож ни на один из классов, т.е. близких ему аналогов ранее ненаблюдалось.Использование решающего правила означает фактически переход из признаковогопространства в пространство оценок, в котором в качестве разделяющих классы функцийиспользуются гиперплоскости, проходящие через начало координат симметрично42относительно новых координатных осей (случай a), пары гиперплоскостей (случай b), инаборы из l гиперплоскостей.Варьируя в моделях вычисления оценок правила определения этапов 1-6 (частьпримеров их определения приведена выше), можно получить различные моделираспознающих алгоритмов типа вычисления оценок.Если конкретные правила этапов (1-5) определены, то после последовательнойподстановки выражений на этапах 2-5 могут быть получены различные общие формулыдля вычисления оценок  j (S ) .