Введение к работе
у:^т,- ^Актуальность темы. В данной ряботе рассмотрена модель алгоритма типа вычисления оценок1. Конкретный алгоритм А определяется БПбороМ СИСТОМН ОИОрННХ МН01ЭСТБ Од,
функции близости B(d),S,S'), весов признаков Pj.Pgi Рм » восов объектов обучающей информации 7(Sj)»7(S2)>---^7() и решающего правила. Оцоїша принадлежности объекта S классу с помором J обычно вычисляется следующим образом.Распозна-ваемпй объект сравішвается с множеством эталонных, которые принадлежат данному классу, по всем подмножествам признаков (опорным множествам) из система опорных подмножеств П, . Если близость по некоторой совокупности признаков имеет место с объектом s, , то оценка принадлежности увеличивается на произведение веса этой совокупности не вес этого объекта обучающей информации. Оценка нормируется и усредняется по числу эталонных объектов, принадлежащих классу К,.
Эффективность работы алгоритма существенно зависит от возможности вычисления оценки принадлежности данного объекта каждому из классов Kj , Kg,...', Kj . Поэтому обычно используется переход от суммирования по отдельным множествам, принадлежащим системе опорных множеств алгоритма, к сложению количеств вхождения в данные множества (при условии, что значение функции близости равно единице) для каждого признака, характеризующего объект.
Журавлев Ю.И. Об алгебраическом подходе к решению згдач распознавания и классификации.// Проблемы кибернетики. - М.: Наука, 1973 г. - Вып.33. - с.5-63.
Получены свертки для эффективного вычисления оценок в
соотрчтствущем алгоритме для некоторых систем опорных
*
множеств (для системы всех подмножеств мощности к множества признаков, для системы всех непустых подмножеств множества признаков и др.) и доказано2, что при использовании пороговой функции.близости , значение которой определяется лишь числом выполненных и невыполненных неравенств вида е, г р Ла,,Ъ.) ,J=l,... ,н, выражение для сверток принимает не более двух значений, если Ад - это множество всех непустых подмножеств m=CI,2,...,N).
В некоторых случаях известны признаки (или совокупности признаков), которые следует учитывать. Эти подмножества могут иметь ігроизвольную конфигурацию. Тогда составляется ортогональная ДЯФ характеристической функции3. Каждый интервал, соответствующий элементарной конъюнкции, рассматривается отдельно, после чего результаты суммируются. Однако, этот подход часто дает сложные формулы, ток как ортогоныльная ДНФ получается длинной. Поэтому получение эффективных сверток для новых систем опорных множеств делает возможным построение новых алгоритмов вычисления оценок.
Целью работы является исследование "и синтез новых эффективных алгоритмов вычисления оценок . для задач
^Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания и классификации.// Проблемы кибернетики. - М.: Наука, 1978 г. - Вып.33. - с.5-68.
3Гуревич И.В., Журавлев Ю.И. Минимизация булевых функций и аффективные алгоритмы распознавания. // Кибернетика. -1974г. -ИЗ. - с.16-20.
распознавания и прогнозирования.
Научная новизна. Автором получены аффективные формулы вычисления оценок для алгоритмов н которых характеристические функции опорных множеств ' являются логическими суммами хвмштгойих шаров. Для этого впервые введено понятие атомарного множества и исследованы свойства таких множеств. Результаты распространены на случай задач с неполной информацией.
Исследована задача оптимизации по радиусам хвмминговых шаров, соответствующих система опорных множеств. На основании указанных результатов сконструирован программный комплекс, реализованный на ПЭВМ PC AT/XT.
Практическая ценность. Разработанный в диссертации подход может применяться при построении эффективных формул вычисления оценок для алгоритмов с системами опорных множеств, являющихся пересечением или объединением хэмминговых шаров. Описанный алгоритм синтеза оптимального распознающего алгоритма с фиксированными центрами хамминговых шаров может эффективно использоваться для решения прикладных задач.
Публикации и апробация работы. Основные результаты диссертации докладывались на XXIV Научной конференции МФТИ (1990г.) и опубликованы в работах /1,2/.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и приложения, изложенных на 103 страницах машинописного текста, содержит 14 таблиц и 2 рисунка. Библиография включает 45 наименований.