Об одном семействе рекуррентных алгоритмов распознавания, основанных на случайных разбиениях множества допустимых объектов

• Автор: Промахина, Ирина Михайловна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Москва
• Количество страниц: 81 c. : ил

Глава I. Семейство рекуррентных алгоритмов распознавания

§1. Описание семейства алгоритмов

§2. Предварительные результаты

§3. Сходимость алгоритмов в точке

§4. Сходимость алгоритмов почти всюду в одном частном случае

Глава II. Оценки трудоемкости алгоритмов

Глава III. Вопросы практической реализации алгоритмов

§1. Два способа реализации алгоритмов

§2. Метод случайных перестановок

§3. Решение практических задач

Литература
Приложение

Задача распознавания образов может быть сформулирована следующим образом. Пусть рассматривается множество объектов , для описания которого выбрана некоторая совокупность признаков П . Относительно множества К. известно, что оно представлено в виде объединения подмножеств К г К1 и... У К , называемых классами. Задана информация о классах К
Предъявляется объект 2 € К , имеющий описание до; по совокупности признаков Л . Требуется по известным информации
и описанию до; определить выполнение свойства 3 £ К' для каждого ^ - ;
В большинстве прикладных задач исходная информация о классах представляет собой набор описаний по совокупности признаков Л конечного числа объектов из К -••• “ Для каждого из которых точно известно, к какому
из I классов относится данный объект. Никаких других сведений о классах не имеется.
Специфичность исходной информации обусловила невозможность использования для решения задачи распознавания строгих математических методов и привела к появлению целого ряда эвристических алгоритмов, то есть алгоритмов, основанных на правдоподобных соображениях и не имеющих строгого математического обоснования. Как указано в , обширную совокупность эвристических методов решения задач распознавания можно классифицировать по принципу их формирования, так что методы, соответствующие одному принципу, образуют единое семейство, модель. Наиболее широко представленными в приложениях являются следующие модели.
Модели статистических алгоритмов распознавания. Если бы
исходные сведения о массах включали в себя информацию о плотности распределения в К точек каждого класса, то оптимальное ( в смысле минимума среднего риска) решение задачи распознавания произвольной точки ЗеК давалось бы байесовским подходом. Однако в силу неполноты априорной информации непосредственно этот подход применен быть не может. Был предложен целый ряд процедур, в которых по начальной информации о конечном числе объектов ^т) оценивались необходимые плотности вероятностей, после чего полученные оценки использовались для проведения байесовского анализа [2, 4, 16] . При этом оценивание носило как параметрический характер (когда плотности предполагались известными с точностью до параметров), так и непараметрический (метод окна Парзена, ближайших соседей, и т. д.). Поскольку, как правило, начальная информация недостаточна для получения достоверных оценок, указанные методы распознавания могут рассматриваться как эвристические.
Модели, основанные на принципе разделения [2, 13] . Алгоритмы этих моделей используются в тех случаях, когда правдоподобно предположение о том, что объекты разных классов могут быть хорошо разделены одной или несколькими поверхностями заданного вида. При этом вид поверхности задается с точностью до параметров, для определения которых используется начальная информация
Модели, основанные на принципе потенциалов £I, 157* Принцип потенциалов использует соображение о том, что влияние каждой из , Iна распознавание точек из К. максимально в непосредственной близости от 3 ^ та убывает по мере удаления от 3 • . Б этих методах решение вопроса о свойствах 3 £ КУ основывается на сравнении величин суммарного влияния на 3 точек 31}.. 3^ , принадлежащих и не принадлежащих ,

Предположим, что рп(у) и рп(у) - плотности распределений, удовлетворяющие соотношению (1.2.8) с функциями Су!и) и ^Су1и) соответственно, где Су^и) * а £^!и)-

Нетрудно проверить, что плотности и Т(у') определяют некоторые вероятностные распределения на отрезке [0. Действительно

Доказательство. Пусть &п(у) » ^п^У) и Ф„Су) обозначают функции распределений, соответствующие плотностям рп(у) » й Рп^; • Поскольку 5 урпср<4у=1(1 то для доказательства теоремы достаточно проверить выполнение неравенств
(2.1)