Итерационные методы и алгоритмы решения задачи сильной отделимости

• Автор: Ершова, Арина Владимировна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Челябинск
• Количество страниц: 97 с. : ил.

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

Глава 1. Распознавание образов и фейсровские отображения

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

1.1.1. Классификация основных задач распознавания.

1.1.2. Отделимость пспсрссскающихся мио ограиииков.

1.2. Итерационные методы фсйсровского типа

1.3. Обзор методов решения задачи сильной отделимости.

1.3.1. Метод на основе операции проектирования

1.3.2. Метод опорных векторов.

1.3.3. Метод с использованием теоремы об альтернативах

1.4. Выводы по главе 1
Глава 2. Метод пссвдопроскций.
2.1. Формализация задачи сильной отделимости
2.2. Метод последовательного проектирования.
2.3. Метод на базе фсйсровских процессов
2.4. Устойчивость алгоритма 5.
2.5. Масштабируемый алгоритм 6 построения пссвдопроскций
2.6. Теорема сходимос ти
2.7. Выводы но главе 2
Глава 3. Параллельные алгоритмы решения задачи сильной отделимости
3.1. Параллельная реализация алгоритма 5
3.2. Параллельный алгоритм Зтре.
3.3. Параллельный алгоритм .
3.4. Выводы по главе 3.
Глава 4. Программный комплекс и вычислительные эксперименты
4.1. Структура программного комплекса
4.1.1. Программа генерации случайных многогранников.
4.1.2. Программа, реализующая последовательный алгоритм.
4.1.3. Программа, реализующая параллельный алгоритм i
4.1.4. Программа, реализующая параллельный алгоритм .
4.2. Вычислительные эксперименты.
4.3. Масштабируемая модельная задача .
4.4. Исследование последовательного алгоритма
4.5. Исследование параллельного алгоритма i.
4.6. Исследование алгоритма
4.7. Выводы но главе 4.
Заключение.
Литература


Алгоритмы разделения выпуклых многогранников на базе фейеров-ских отображений обладают тем преимуществом по сравнению с другими известными методами, что они применимы к нестационарным задачам, то есть к задачам, в которых исходные данные могут меняться в процессе решения задачи. Примерами таких нестационарных задач являются, например, задача о портфеле цепных бумаг, задача о спам-филы ре и задачи классификации в метеорологии. При решении шдачк о портфеле ценных бумаг [] является важным вопрос о выборе ценной бумаги из их многообразия при формировании портфеля []. Проблему выбора можно решить, условно разделив все ценные бумаги на две части: перспективные и неперспективные. Каждая ценная бумага представляется в виде многомерной точки, координаты которой - это параметрическое описание конкретной бумаги [6, ]. Эксперт строит параметризованную модель [], представляющую собой две системы неравенств. Часть коэффициентов в неравенствах являются параметрами, меняющимися во времени. В качестве примеров таких параметров можно указать средний оборот торгов, спрэд между ценами спроса и предложения и др. В результате мы приходим к нестационарной задаче сильной отделимости. Построив слой наибольшей толщины, разделяющий два многогранника, мы получаем инструмент, позволяющий автоматически разделять ценные бумаги па перспективные и неперспективные. В задаче о спам-фильтре [, ] мы должны для каждого электронного письма определить, является данное письмо «спамом», или ист. Для этого также вводится система метрик и строится параметризованная модель [. Построив слой наибольшей толщины, разделяющий два многогранника, мы получаем инструмент, позволяющий автоматически разделять письма на «хорошие» и «плохие». Когда приходит новое письмо, вычисляются характеристики этого письма и получается точка в рассматриваемом пространстве. Если данная точка попадает в «плохое» полупространство, мы делаем предположение, что это спам; если в «хорошее» - не спам. Пели точка попадает внутрь слоя, письмо доставляется пользователю с пометкой «возможно, спам». Задачи классификации эволюционирующих систем характерны и для метеорологии. Приведем несколько примеров. Одной из таких задач является задача определения морфологии и генезиса облаков и разделения их на классы, например, кучевых и слоистообразных облаков [, 1. Для этого на основе критериальных порогов, таких как температура верхней границы, альбедо, пространственная однородность и др. В радиолокационной метеорологии [, , 1 традиционным является вопрос о фазовом состоянии и форме облачных частиц - капли, ледяные кристаллы различных форм, смешанные формы, их агрегаты; и связанный с этим вопрос о тине и интенсивности выпадающих осадков - дождь, снег, мокрый снег, снежная крупа, ледяные иглы, град и др. Для решения задачи на основе данным об отражаемости, дифференциальной отражаемости, коэффициентов деполяризации и др. Построив слой наибольшей толщины, разделяющий два многогранника, мы получаем инструмент, позволяющий автоматически прогнозировать тип осадков. Задача о классификации мезомаситшбных конвективных систем по интенсивности и степени организации рассмотрена в работах [1,2]. В отличие от предыдущих задач, имеющих дело с одним или несколькими элементами поля облачности и осадков размерами от нескольких сотен метров до I -2 км, здесь рассматривается структура поля радиолокационной отражаемости всей мезомасштаб-ной системы с размерами более 0 км. Алгоритм классификации мсзомас-штабных систем [1] в своей основе подобен рассмотренным выше: в определенной стадии жизненного цикла сисіемьі выделяется наиболее интенсивные элементы, а затем по их характеру системы делятся па конвективные и слоистообразные, далее по структуре поля на линейные и нелинейные; конвективные в свою очередь подразделяются на умеренные и более мощные шторма. Для детализации набора опасных явлений, обусловленных эволюцией индивидуальной мезомасштабной системы (ливни, грозы, град, шквалы и смерчи), число неравенств может быть расширено за счет введения кинематических и эволюционных характеристик [2].