Введение к работе
Актуальность темы. В последние десятилетия интенсивно развивается теория и разрабатываются новые методы распознавания образов, дисциплины, предметом изучения которой являются способы решения трудноформализуемых и противоречивых задач классификации, оптимизации и принятия решения, которые часто возникают при моделировании сложных систем в экономике, медицине, технике и т.д. Процедуры распознавания активно используются при проектировании экспертных систем в различных областях знания. Отдельным важным приложением теории и методов распознавания является анализ и понимание изображений.
Задачей распознавания или классификации, согласно Ю.Н.Журавлеву1, называется следующая задача. Пусть задано множество М объектов, называемое допустимым, и задано неизвестное покрытие множества М множествами К\,...,Кт С М, (Jy=i Kj — М> называемыми классами (образами). Обычно предполагается, что KjDKj = 0 для любых і ф j. Информация о множествах Л'і,..., Л'т задана не полностью, обычно известны конечные Щ С Kj. В общем случае задается некоторая информация /o(A'i, , Кт). Задача состоит в том, чтобы для произвольного объекта S Є М, заданного описанием 1(S), определить значения предикатов:
Pj(S) = i. J' SeKj! (jeNm). JK ' \ 0, иначе
Далее, не уменьшая общности, будем полагать га = 2.
Исторически сложилось несколько подходов к постановке и решению задач распознавания, такие как, например, вероятностный, представленный работами В.Н.Вапника,А.Я.Червоненкиса и др., алгебраический — работами Ю.И.Журавлева, Ю.А.Зуева, К.В.Рудакова и других авторов. В каждом случае приведенное выше общее определение задачи распознавания тем или иным способом конкретизируется. Автор в своей работе придерживался подхода, сформированного работами Вл.Д.Мазурова и И.И.Еремина, основанного на применении фундаментальных результатов теории линейных неравенств, полученных С.Н.Черниковым, Фань-Дзи, Д.Гейлом и др.
'Журавлев Ю.К. Об алгебраическом подходе к решению задач распознавания или классификации// Проблемы кибернетики, вып.33.-1978.-С.5-68.
Согласно работе2, задачей дискриминантного анализа называется следующий частный случай задачи распознавания. Пусть мно-
жество М С Rn, М = A'iU^2' заданы конечные подмножества А С Л'ь В С Л'а и класс функций F С {Rn -* Я}. Требуется найти функцию f Є F, такую что
/(а) > 0 (а Є А), f(b) < О (6 Є В).
Если такая функция найдена, то полагается К\ ={їЄ М\ f(x) > 0} и А'г = {а; Є Af| /(ж) < 0). Поставленная задача часто может быть сведена к задаче поиска решения подходящей системы неравенств (в частности, линейных, если F — класс аффинных функций). К сожалению, как правило, эта система несовместна, поэтому для решения исходной задачи требуется то или иное обобщение понятия решения системы неравенств.
Одним из требуемых обобщений является понятие комитета, впервые введенное в работе3 для системы строгих однородных линейных неравенств. Вместо одной точки xq Є Rn, удовлетворяющей всем неравенствам несовместной системы, предлагалось искать конечную последовательность (ас1,.. ,,хд) (хг Є Я") точек, называемую комитетом исследуемой системы, такую что каждому неравенству удовлетворяют более половины ее членов. В работах Вл.Д.Мазурова, Л.И.Тягунова, Д.Н.Гайнаноъа и других авторов понятие комитета получило широкое развитие. Были доказаны теоремы существования комитетов и обобщающих их конструкций для различных классов систем неравенств и получены верхние оценки числа членов комитетов с минимально возможным числом членов (называемых минимальными), разрешающих заданную систему неравенств. На основе понятия комитета системы неравенств введено понятие разделяющего комитета, являющегося обобщением понятия решения задачи дискриминантного анализа. Полученный таким образом метод формирования алгоритмов распознавания, называемых комитетными, исследовался в работах Н.Г.Белецкого, Ю.А.Зуева, В.В.Рязанова и других авторов.
2 Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. Наука. Москва. 1990.
г Ablow C.ilf, Kaylor D.J Inconsistent homogenous linear inequalities// Bull.Amer.Math.Soc.-1965.-v.71.№5.
Целью настоящей: работы является исследование комбинаторных свойств минимального комитета системы линейных неравенств для уточнения оценки числа его членов и построения эффективных алгоритмов нахождения комитета указанной системы с числом членов, более близким к минимальному, чем у известного алгоритма проектирования на плоскость.
Методика исследования предполагает использование фактов теории комитетов, выпуклого анализа, теории линейных неравенств и теории графов.
Научная новизна. В работе введено понятие гиперграфа МСП произвольной системы включений, обобщающее известное понятие графа МСП и исследованы некоторые его свойства. В частности, показано, что разрешимость произвольной системы включений комитетом с наперед заданным числом членов эквивалентна наличию в гиперграфе ее МСП подгиперграфа специального вида; гиперграф МСП системы линейных однородных неравенств на плоскости обладает своего рода экстремальным свойством по отношению к числу членов минимального комитета указанной системы.
Полученные результаты позволили классифицировать минимальные комитеты произвольных систем включений с 3 и 5 членами и указать способ построения такой классификации для произвольного числа членов.
За счет более полного учета параметров задачи, получена более точная чем в4 верхняя оценка числа членов минимального комитета системы линейных неравенств. При доказательстве использовалась методика, предложенная в этой работе.
На основе указанных результатов предложен метод нахождения комитета системы линейных неравенств с числом членов, не большим, а в ряде нетривиальных случаев строго меньшим, чем в алгоритме проектирования на плоскость, и превосходящим его по вычислительной сложности не более, чем на 0(т3), где га — число неравенств исследуемой системы.
Кроме того предложен конечношаговый алгоритм нахождения
4 Мазуров Вл.Д. О построении комитета системы выпуклых неравенств // Кибернетика.-№2.-19<37.-С.56-59.
оценки числа шагов известного метода линейной коррекции для нахождения решений МСП системы линейных неравенств.
Практическая ценность. Полученные в работе новые методы могут быть положены в основу конкретных эффективных алгоритмов распознавания, которые предполагается использовать при проектировании программного продукта " КВАЗАР+" в рамках проекта ГНТП "Перспективные информационные технологии" (05.05.1190).
Апробация работы. Основные результаты диссертации докладывались на Конференции с международным участием "Математические методы распознавания образов" (г.Пущино, 1995), 27 Школе-конфереции молодых ученых (г.Екатеринбург, 1996), обсуждались на семинарах отдела проблем распознавания и методов комбинаторного анализа ВЦ РАН и отдела математического программирования ИММ УрО РАН.
Публикации. По теме диссертации автором опубликовано четыре работы.
Структз'ра и объем диссертации. Диссертация состоит из введения, трех глав, объединяющих 10 параграфов, заключения и списка литературы. Объем работы 101 страница, 18 рисунков на 18 страницах. Список литературы включает 74 наименования.