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

Тестовый алгоритм распознавания был опубликован в /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- значных «образов» эталонных объектов различных классов (или отделимости с точностью до пороговых значений).