К-сингулярные системы точек в алгебраическом подходе к распознаванию образов

• Автор: Карпович, Павел Алексеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 80 с.

ОГЛАВЛЕНИЕ
Введение

Глава 1.Основные определения и обзор предыдущих работ

1.1.Задача распознавания образов

1.2 Алгоритмы вычисления оценок

1.3.Эффсктивные реализации АВО

1.4Ф-сингулярные системы точек

1.5.Теория матроидов

Глава 2.Эффективная реализация модели АВО

2.1.Постановка задачи и результаты

2.2.Эффективные системы опорных множеств
2.3.0-эффективные системы опорных множеств
2.4Алгоритмы распознавания свойства 0-эффективности
Глава 3.Корректность моделей АВО и &;-с.игнулярность
3.1 Алгебраический критерий fc-сингулярности
3.2.Разделение систем точек на подсистемы без 1-сингуляриости .. 49 З.ЗРазделение систем точек на подсистемы без fc-сингулярности
3.4.Разделение на подсистемы для пространства R
З.б.Эффективные критерии k-сингулярности
Список литературы

Введение
Методы теории распознавания образов широко используются для решения практических задач во многих областях науки (биология, социология, экономика и т.д.). Предполагается, что исследуемые объекты принадлежат некоторому множеству М. Данное множество может быть представлено в виде объединения конечного набора классов: М = К U ... U Ki. Задача распознавания образов (задача классификации) состоит в следующем: по конечному набору пар S — {(si,yi),..., (£п,Уп)} (щ - объект из множества М, г/i -информация о принадлежности объекта Si к классам распознавания) требуется построить алгорим А, который для произвольного допустимого объекта s множества М вычисляет значение предикатов принадлежности к классам

Для решения задач распознавания в начале 1970х годов академиком РАН Журавлевым Ю.И. была предложена модель алгоритмов вычисления оценок (АВО) [16, 19]. Благодаря своей универсальности модель предоставляет широкие возможности для описания правил классификации. Многие известные эвристические алгоритмы являются частными случаями алгоритмов вычисления оценок при специальном выборе параметров. Алгоритм в модели АВО для распознавания набора из q объектов строит числовую (q х £)-матрицу оценок близости, в которой элемент на пересечении г-й строки и j-го столбца характеризует близость г-го объекта к j-му классу. По этой матрице оценок близости осуществляется классификация объектов.
Модель АВО широко применяется иа практике, однако прямая численная реализация систем распознавания с использованием классических формул вычисления оценок близости практически невозможна. Возникающие препятствия связаны с большой вычислительной сложностью явных реализаций АВО. Множество работ посвящены именно алгоритмической оптимизации

моделей ABO [1, 1G, 19, 8, 11, 12, 9]. Многие результаты исследований в данном направлении описывают способы упрощения формул вычисления оценок близости и их эффективной алгоритмической реализации при определенном выборе параметров модели.
В дайной диссертационной работе рассматривается возможность эффективной реализации моделей АВО в зависимости от выбора системы опорных множеств - важного параметра модели. Вводится определение О-эффективной системы опорных множеств, частичный порядок на множестве классов эквивалентностей таких систем и описываются основные свойства данного порядка. Показывается, что для моделей с О-эффективными системами опорных множеств возможно упростить классические формулы вычисления оценок близости. Также исследуется задача построения алгоритма распознавания свойства О-эффективности системы опорных множеств по ее описанию. Доказывается NP-полнота этой задачи с дополнительными ограничениями.
В конце 1970х годов Журавлевым Ю.И. был предложен алгебраический подход к распознаванию образов. Одной из основных идей, используемой в алгебраическом подходе, является конструирование алгоритма, решающего задачу классификации, из некорректных (эвристических) алгоритмов при помощи корректирующих операций. Например, для модели АВО вводятся операции умножения на константу, сложения и умножения алгоритмов модели. Результирующий алгоритм распознавания ищется в виде полинома от базовых алгоритмов модели АВО. Семейство полиномов степени не более к называется алгебраическим замыканием степени к для используемой модели АВО.
Одним из центральных понятий алгебраического подхода является корректность семейств алгоритмов распознавания. Семейство алгоритмов распознавания называется корректным тогда и только тогда, когда при помощи

Ш1/12 С КВь'п+1 С КВ*’п+1 = кв*'° = КВ41’0.
Класс КВ91,92 полностью изучен и описан. В работе [8] получен критерий эффективности систем опорных множеств для функций близости из семейства В11’42. Данный критерий приведен в первой главе.
2.3. О-эффективные системы опорных множеств
В данном разделе рассмотрим подкласс О-эффективных систем опорных множеств для семейства функций В*’0. Определим и опишем структуру частичного порядка для этого класса.
Определение. Эффективную систему опорных множеств из класса КВ*’° будем называть О-эффективной, если для любого бинарного вектора ж у суммы
5]хНВ*,0(и,ї)
в любой паре различных координат одна из них равна 0.
Для любой эффективной системы опорных множеств О из класса КВ*'° можно получить 0-эффективную систему опорных множеств Пп — {іосО Є £1,п ф со}, взяв множества, которые не содержат последней координаты из Рп-
Будем называть две О-эффективные системы опорных множеств П и П эквивалентными, если выполнено хотя бы одно из условий:
1. Г2 и О, определены для множества Рп, Г2 переходит в П под действием некоторой перестановки набора признаков а, то есть а - перестановка множества Рп = {1, и
п и Є П, и = {Д...., Д}};
2. П - система для признаков Рп, Два признака с номерами п и п — 1 одновременно входят или не входят во все опорные множества системы Б!, в