2010 Лекции МОТП. Записки (2010 Лекции МОТП. Записки.pdf), страница 10

выходящие из вершин дуги помечены значениями, принимаемыми предикатами ввершине;3. концевые вершины помечены метками классов;4. ни в одной ветви дерева нет двух одинаковых вершин.Пример подобного дерева для конфигурации из трех классов (рис.7) приведен на рис. 8.x2 = x1x2K3K3×× ××x1K1K2Рис. 7. Конфигурация объектов трех классов. Объекты классовсимволамиK1 , K 2 , K 3 обозначены, соответственно,× , Ο, ∆..58y101y20K3y310K21y4y20K3101K2K20K1y21K2Рис.8. Решающее дерево для классов рис.

7.На рис.8 приведено некоторое решающее дерево, позволяющее правильно распознаватьобъекты трех классов, изображенных на рис.7. Вершины дерева помечены следующими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 ∨ y1 y2 y3 y4 , f 3 ( S ) = y1 y2 ∨ y1 y2 y3 , принимающие значение 1 наобъектах «своего» класса и 0 на объектах остальных классов.Приведем еще один пример решающего дерева (рис.9), построенного непосредственно по 0 0111  ∈ K11 1101 таблице обучения: T5.4, 2 = .1 0 1 11 ∈ K 2 0 1 01 0 (9)В качестве признаковых предикатов используются y1 = x1 , y2 = x3 .y101y2K20K21K2Рис.9.

Решающее дерево бинарной таблицы обучения (9)59Здесь в качестве приближений для характеристических функций классов выбраныфункцииf1 ( S ) = y1 y2 = x1 x3 ,f 2 ( S ) = y1 ∨ y1 y2 = x1 ∨ x1 x3 .Вданномпримере,дляпостроения решающего дерева использованы только два признака.Задача построения решающего дерева по обучающим данным решается неоднозначно,методам построения решающих деревьев посвящена обширная литература /……../.1.3.Алгоритмыраспознавания,основанныенапринципечастичнойпрецедентностиНастоящий класс алгоритмов выделен в отдельный раздел по нескольким причинам.Представляя исторически логические подходы в теории распознавания, в рамках данногоподхода разработана также теория алгоритмов вычисления оценок, объединяющая всесуществующие методы распознавания и положенная в основу алгебраического подхода втеории распознавания. Теоретические основы алгоритмов частичной прецедентности(вычисления оценок, голосования, или комбинаторно-логических алгоритмов) описаны вмногочисленных научных публикациях /…./.

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

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

Впервые был опубликован в /…/ и базируется на понятии теста,введенного в 1956 году С.В.Яблонским. Приведем одну из основных модификацийалгоритма.Определение. Тестом таблицы Tnml называется совокупность столбцов {i1 , i2 ,..., ik } таких,что после удаления из Tnml всех столбцов, за исключением имеющих номера {i1 , i2 ,..., ik } , вполученной таблице Tn−k ,m ,l все пары строк, принадлежащих разным классам, различны.Тест {i1 , i2 ,..., ik } называется тупиковым, если никакая его истинная часть не являетсятестом /71/.Пусть найдено множество {T } тупиковых тестов таблицы Tnml и T = {i1 , i2 ,..., ik }∈ {T } .

Выделим в описании распознаваемого объекта S фрагмент описания (ai1 , ai2 ,..., aik ) ,соответствующий признакам с номерами i1 , i2 ,..., ik . Сравним (ai1 , ai2 ,..., aik ) со всемифрагментами (a ji1 , a ji2 ,..., a jik ) объектов S j , j = 1,2,..., m, таблицы Tnml .Число совпадений (ai1 , ai2 ,..., aik ) с (a ji1 , a ji2 ,..., a jik ) , j = mk −1 + 1, mk −1 + 2,..., mk , k = 1,2,..., l ,m0 = 0, ml = m , обозначим через Γ j (T ) .Величина Γ j ( S ) =1∑ Γj (T )m j − m j −1 T∈{T }(78)называется оценкой S по классу K j .

Имея оценки Γ1 (T ), Γ2 (T ),..., Γl (T ) объект S легкоклассифицируется с помощью решающих правил. Например, он относится в тот класс, закоторый получена его максимальная оценка. В случае наличия нескольких классов смаксимальными оценками, происходит отказ от его классификации.Если отдельное совпадение в (78) назвать «голосом» в пользу класса K j , то выражение(78) будет нормированным числом голосов за данный класс.

В связи с даннойинтерпретацией, алгоритмы с подобной схемой вычисления оценок называют такжеалгоритмами голосования.Тестовый алгоритм является удобным базисом для оценки информативности (важности)признаков. Пусть N i - число тупиковых тестов таблицы Tnml , содержащих i-й столбец , аN = {T } - общее число тупиковых тестов таблицы.

Тогда вес i-го признака определяется61какpi =Ni. Чем больше вес, тем важнее признак для описания объектов. ЭтоNутверждение основывается на следующем рассуждении. Таблица Tnml является исходнымописанием классов и признаков. Тупиковый тест есть не сжимаемое далее по признакамописание классов, сохраняющее разделение классов. Чем в большее число такихнеизбыточных описаний входит i-й признак, тем он важнее.Задача нахождения множества тупиковых тестов таблицы Tnml сводится квычислению всех тупиковых покрытий строк некоторой бинарной матрицы ее столбцами.Рассмотрим постановку данной задачи.

ПустьTnml = aijm×n, гдеaij = x j ( S i ) ∈{0,1,..., k − 1} . Таблице T nml ставится в соответствие матрица сравнения попризнакам всевозможных пар объектов из различных классовC = cijN ×n, где1, aνj ≠ aµj ,cij = i = i (ν , µ ) , Sν ∈ K u , S µ ∈ K v , u ≠ v ,0, aνj = aµj ,∑ (mN=i> ji− mi −1 )(m j − m j −1 ).i , j =1, 2 ,...,lСтолбцы (i1, i 2 ,... , i k ) образуют покрытие строк матрицы∀i = 1,2,...,N , ∃j ∈ {i1 , i2 ,..., ik } : сij = 1 .C = cijN ×n, еслиПокрытие называется тупиковым, еслипроизвольное его собственное подмножество не является покрытием.

Каждомутупиковому тесту соответствует тупиковое покрытие строк матрицы сравнения инаоборот. Нахождение всех тупиковых тестов является сложной вычислительной задачей.Тем не менее здесь существуют подходы, эффективные для таблиц средней размерности /…/. При решении практических задач достаточно нахождение лишь части тупиковыхтестовдлявычисленияоценоксогласно(78).Вслучаеналичияпризнаковвещественнозначных используют обычно один из следующих двух подходов. Областьопределения каждого вещественнозначного признака разбивается на k интервалов.Значение признака из i- го интервала полагается равным i-1. Далее задача распознаваниярешается относительно полученной k- значной таблицы обучения и k- значных описанийраспознаваемых объектов. Другой подход связан с введением числовых пороговых62параметров для каждого признака.

Для вещественнозначных таблиц вводится аналогтупиковых тестов, в котором требование несовпадения значений признаков заменяется ихразличием не менее чем на соответствующий порог. В обоих подходах при выборезначности новой таблицы или значений пороговых параметров необходимо учитывать,что соответствующие матрицы сравнения не должны содержать нулевых строк, поэтомузначность (или пороговые параметры) следует выбирать из требования отделимости kзначных «образов» эталонных объектов различных классов (или отделимости с точностьюдо пороговых значений).1.3.2. Алгоритмы распознавания с представительными наборами.Другими алгоритмами данного вида являются алгоритмы типа “Кора” /16,12/, вкоторых опорные множества связаны со значениями признаков конкретных объектов.Sν ∈ KПустьj,апризнакиu = {xi1 ( Sν ), xi2 ( Sν ),..., xik ( Sν ), }K j,еслидлялюбогопринимаютзначения0или1.Наборназовем представительным набором для классаS µ ∈ T nml ,⋅S µ ∉ Kjхотябыодноизравенствxit ( Sν ) = xit ( S µ ), t = 1,2,..., k , невыполнено.

Представительный набор называется тупиковым,если любой его собственный поднабор не является представительным набором, т.е. длялюбого его поднабора существует равный ему поднабор в каком-либо другом классе.Таким образом, тупиковый представительный набор некоторого класса Kjестьнесократимый фрагмент некоторого эталона данного класса, для которого нет равных емуфрагментов эталонов других классов.Пусть вычислено V j− множество тупиковых представительных наборов для класса K j .Тогда степень близости распознаваемого объектаS к классу K j по заданномумножеству тупиковых представительных наборов V j можно оценить по формулеΓj (S ) =1Vj∑ B( S , u )u∈V j(181),где B ( S , u ) равно 1, если в признаковом описании объекта S имеется фрагмент u.