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

Бинарным корневым деревом (БД) называется дерево, имеющее следующие свойства:

а) каждая вершина (кроме корневой ) имеет одну входящую дугу;

б) каждая вершина имеет имеет либо две, либо ни одной выходящей дуги.

Вершины, имеющие две выходящие дуги, называются внутренними, а остальные – терминальными или листьями.

Пусть задано N предикатов , определенных на множестве допустимых признаковых описаний {S}, именуемые признаковыми предикатами. Каждый предикат отвечает на вопрос, выполняется ли некоторое свойство на объекте S или нет. Примерами признаковых предикатов могут быть

Каждой строке таблицы обучения поставим в соответствие бинарную строку значений предикатов на описании . В результате, таблице будет соответствовать бинарная таблица бинарных «вторичных описаний» объектов обучения.

Бинарное дерево называется решающим, если выполнены следующие условия:

1. каждая внутренняя вершина помечена признаковым предикатом из ;

2. выходящие из вершин дуги помечены значениями, принимаемыми предикатами в вершине;

3. концевые вершины помечены метками классов;

4. ни в одной ветви дерева нет двух одинаковых вершин.

Пример подобного дерева для конфигурации из трех классов (рис.11) приведен на рис. 12.

Рис. 11. Конфигурация объектов трех классов. Объекты классов обозначены, соответственно, символами , , 

Рис.12. Решающее дерево для классов рис. 11

На рис.12 приведено некоторое решающее дерево, позволяющее правильно распознавать объекты трех классов, изображенных на рис.11. Вершины дерева помечены следующими предикатами: Данному решающему дереву соответствуют характеристические функции классов , , , принимающие значение 1 на объектах «своего» класса и 0 на объектах остальных классов.

Приведем еще один пример решающего дерева (рис.13), построенного непосредственно по таблице обучения: = . (1.11)

В качестве признаковых предикатов используются

Рис.13. Решающее дерево бинарной таблицы обучения (1.11)

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

Задача построения решающего дерева по обучающим данным решается неоднозначно, методам построения решающих деревьев посвящена обширная литература /16, 17, 41, и др./.

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

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

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

1.3.1. Тестовый алгоритм.

Тестовый алгоритм распознавания был опубликован в /15/ и базируется на понятии теста, введенного в 1956 году С.В.Яблонским. В классическом изложении тестовый алгоритм был предназначен для бинарных и к-значных признаков. Пусть

Определение 1. Тестом таблицы называется совокупность столбцов таких, что после удаления из всех столбцов, за исключением имеющих номера , в полученной таблице все пары строк, принадлежащих разным классам, различны. Тест называется тупиковым, если никакая его истинная часть не является тестом /59/.

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

Число совпадений с , , для каждого , , обозначим через .

Величина (1.12)

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

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

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

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

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

1.3.2. Алгоритмы распознавания с представительными наборами.

Другими алгоритмами данного вида являются алгоритмы типа “Кора” /3, 10/, в которых опорные множества связаны со значениями признаков конкретных объектов.

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