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

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

Для нахождения тупиковых представительных наборов, содержащихся в некотором эталоне , формируются матрицы сравнения со всеми эталонами других классов. Тупиковые покрытия данных матриц сравнения и определяют тупиковые представительные наборы. Однако, если для поиска тупиковых тестов таблицы требуется решать задачу на покрытия для матрицы из строк и n столбцов, то для поиска тупиковых представительных наборов объекта задача на покрытия решается для матрицы из строк и n столбцов. Таким образом, нахождение множества всех тупиковых представительных наборов таблицы требует решения m задач на покрытия но «малой » размерности. Эффективные алгоритмы решения данных задач разработаны Дюковой /22/.

Вопрос обобщения алгоритмов распознавания с представительными наборами на случаи k- значной и вещественнозначной информации информации решается аналогично тестовому алгоритму. Множество допустимых значений некоторого признака делится на конечное число интервалов, каждому из которых приписывается целое число 0, 1, 2,…, или k-1. Таблице и распознаваемым объектам ставятся в соответствие строки новых целочисленных значений признаков. Далее процесс определения тупиковых представительных наборов и распознавания полностью идентичен бинарному случаю. Другое распространение на вещественнозначные признаки связано с введением пороговых параметров и следующей модификацией понятия представительного набора: набор называется представительным набором для класса , если для любого хотя бы одно из неравенств будет невыполненным.

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

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

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

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

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

Множество всех n-мерных булевских векторов определяет дискретный единичный куб , . Число элементов куба равно .

Теоретические исследования свойств тупиковых тестов для случайных бинарных таблиц показали, что характеристические векторы «почти всех тупиковых тестов» имеют асимптотически (при неограниченном возрастании размерности таблицы обучения) приблизительно одну и ту же длину. Это явилось одним из обоснований выбора в качестве множества всевозможных подмножеств {1,2,…,n} длины k. Значение k находится из решения задачи обучения (оптимизации модели) или задается экспертом. В итоге, широко распространенными подходами к выбору являются (наряду с тупиковыми тестами) следующие два:

а) = ;

b) .

Второй способ выбора системы опорных множеств, как всевозможных подсистем {1,2,…,n}, не требует нахождения подходящего значения параметра k.

2. Задание функции близости. Пусть фиксировано некоторое опорное множество  и соответствующий ему характеристический вектор . Фрагмент объекта , соответствующий всем единичным компонентам вектора , называется -частью объекта, и обозначается S. Под функцией близости будет пониматься функция от соответствующих -частей сравниваемых объектов, принимающая значение 1 («объекты близки») или 0 («объекты далеки»). Приведем примеры подобных функций.

а) =

Здесь - неотрицательные параметры, именуемые «точности измерения признаков».

b) =

Здесь  также некоторый неотрицательный параметр алгоритма.

3. Оценка близости объекта S к эталонному объекту для заданной -части. Данная числовая величина формируется на основе функции близости и, возможно, дополнительных параметров.

a) = .

b) = , где - «вес» опорного множества.

c) = . Здесь - параметры, характеризующие степень важности объекта (информативность объекта), а - веса (информативность) признаков.

4. Оценка объекта S за класс для заданной -части.

а) Функция является примером естественной оценки близости объекта к классу для заданного подмножества признаков.

5. Оценка объекта S за класс .

Данная функция задает суммарную степень близости распознаваемого объекта S к классу . Приведем обычно используемые выражения для ее вычисления.

a) .

b) , где - «вес» класса .

Например, в статистической теории распознавания аналогами параметров являются априорные вероятности классов, которые характеризуют, насколько часто встречаются объекты различных классов .

6. Решающее правило.

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

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

а) Пример простейшего решающего правила – отнесение объекта в единственный класс, за который он имеет максимальную оценку.

b) Для «осторожного» принятия решения относительно новых объектов, существенно непохожих на объекты обучающей выборки, или находящихся на границе двух и более классов, обычно достаточно введение в решающее правило двух пороговых параметров

Здесь

c) Линейное решающее правило в пространстве оценок определяется как

(1.14)

Здесь - параметры алгоритма. В решающем правиле (1.14) наличие двух или более единиц интерпретируется как «объект принадлежит нескольким классам». Когда вектор состоит из одних нулей говорят, что данный объект – выброс, он не похож ни на один из классов, т.е. близких ему аналогов ранее не наблюдалось.

Использование решающего правила означает фактически переход из признакового пространства в пространство оценок, в котором в качестве разделяющих классы функций используются гиперплоскости, проходящие через начало координат симметрично относительно новых координатных осей (случай a), пары гиперплоскостей (случай b), и наборы из l гиперплоскостей.

Варьируя в моделях вычисления оценок правила определения этапов 1-6 (часть примеров их определения приведена выше), можно получить различные модели распознающих алгоритмов типа вычисления оценок.

Если конкретные правила этапов (1-5) определены, то после последовательной подстановки выражений на этапах 2-5 могут быть получены различные общие формулы для вычисления оценок . Выбирая первые варианты реализации этапов (2-5) будет получена следующая общая формула для вычисления оценок объекта S за классы , j=1,2,…,l.