Экспериментальное сравнение трех оптимизационных методов бинарной классификации данных

В наше время компьютер стал неотъемлемой частью нашей жизни. Возможности, предоставляемые компьютерами, с течением времени неуклонно растут. Большой популярностью среди молодежи и взрослых пользуются фильмы, особенно фантастика со спецэффектами, а среди детей – игры. Ни одна игра и ни один фильм не обходится без компьютерной графики. При этом нужно, чтобы наблюдаемые в фильмах и компьютерных играх явления были реалистичны, поэтому актуальной темой на сегодня является реалистичное физическое моделирование.

Векторное пространство представляет немалый интерес в науке и в исследованиях. Оно носит не только теоретический характер, но и имеет реальное применение в современном мире.

В связи с появлением гаджетов на операционных мобильных системах, таких как Android, IOS, BlackBerry OS, а также других операционных систем, связь с векторным пространством резко возросла.

Также благодаря векторному пространству, есть возможность классифицировать данные.

Именно поэтому, данная тема дипломной работы, актуальна на сегодняшний день.

В данной дипломной работе была спроектирована численная реализация МДМ-метода, метода Гильберта и адаптивного метода условного градиента, были проведены численные эксперименты, результаты которых были сравнены и проанализированы.

Проект должен быть разработан в интерактивной среде программирования Matlab R2013b. Разработанное приложение должно быть нетребовательно к ресурсам системы, просто в установке и настройке и удобно в эксплуатации.

Целью данной работы является: реализация решения задачи

проектирования нуля Евклидова пространства на выпуклый многогранник

тремя методами (методом Гильберта, МДМ-методом и адаптивным методом условного градиента).

Задачи в рамках выполнения работы:

Изучить научную и учебно-методическую литературу по теме; Численно реализовать метод МДМ в пакете Matlab;

Численно реализовать метод Гильберта в пакете Matlab;

Численно реализовать адаптивный метод условного градиента в пакете Matlab;

Реализовать пользовательский интерфейс для удобного использования методов;

Провести численные эксперименты;

Провести численные расчёты с реальной базой данных; Анализ полученных результатов.

ВВЕДЕНИЕ..................................................................................................... 4

ГЛАВА 1 ТЕОРЕТИЧЕСКОЕ ОПИСАНИЕ АЛГОРИТМОВ...................... 6

1.2 Метод Митчелла-Демьянова-Малоземова (МДМ-метод)..................... 7

1.2.1 МДМ-метод....................................................................................... 7

1.2.2 МДМ-метод практическая реализация............................................. 9

1.3 Метод Гильберта (Гильберта-Джонсона-Керти, GJK алгоритм)....... 10

1.3.1 Алгоритм GJK – метода................................................................. 10

1.3.2 Метод Гильберта практическая реализация.................................. 12

1.4 Адаптивный метод условного градиента (ACGA – метод)................. 14

1.4.1 ACGA метод.................................................................................... 14

1.4.2 ACGA метод практическая реализация......................................... 15

1.5 Задача классификации данных............................................................. 16

ГЛАВА 2 ПРАКТИЧЕСКАЯ ЧАСТЬ.......................................................... 19

2.1 Численные эксперименты.................................................................... 19

2.2 Численные эксперименты. Анализ работы методов............................ 30

2.3 Численные расчёты с реальной базой данных.................................... 57

2.4 Структурное описание программы..................................................... 63

2.4.1 Основные функции программы...................................................... 64

2.4.2 Классификации данных................................................................... 69

ЗАКЛЮЧЕНИЕ............................................................................................. 73

СПИСОК ЛИТЕРАТУРЫ............................................................................. 75

ПРИЛОЖЕНИЯ............................................................................................. 76

Приложение 1. Численные эксперименты. Параметры для ACGA метода. 76 Приложение 2. Функция dsearchn.............................................................. 86

Приложение 3. Функция нахождения решения МДМ методом............... 87

Приложение 4. Функция нахождения решения GJK методом................. 88

Приложение 5. Функция нахождения решения ACGA методом.............. 91

Приложение 6. Функция построения сепаратора, классификатора......... 93

Приложение 7. Функция нахождения разности Минковского................. 94

Приложение 8. Функция определяющая градиент функции.................... 94

Приложение 9. Функция создания графиков и определения параметров...... 94

Приложение 10. Функция добавления точки на график........................... 95

Приложение 11. Функция проставления точек классов на график с паузой96 Приложение 12. Функция проставления точек классов на график.......... 96

Приложение 13. Функция разделения данных на 2 класса...................... 97

Приложение 14. Функции для проведения численных экспериментов.... 97

Приложение 15. Функции для выгрузки данных в Excel....................... 105

Приложение 16. Код фор......................................................................... 106

1. Демьянов, В.Ф. Введение в минимакс [Текст]: / В.Ф. Демьянов, В.Н. Малоземов. Москва: Наука, 1972. – 368с.

2. E. G. Gilbert, D. W. Johnson, and S. S. Keerthi. A fast procedure for computing the distance between complex objects in three-dimensional space. In IEEE Journal of Robotics and Automation, volume 4, pages 193–203, April 1988.

https://graphics.stanford.edu/courses/cs448b-00-winter/papers/gilbert.pdf

3. E. G. Gilbert and C.-P. Foo. Computing the distance between general convex objects in three-dimensional space. In IEEE Transactions on Robotics and Automation, volume 6, pages 53–61, February 1990.

4. Методы оптимизации: Учебное пособие / А.В. Аттетков, В.С. Зарубин, А.Н. Канатников. - М.: ИЦ РИОР: НИЦ Инфра-М, 2013. - 270 с.: ил.; 60x90 1/16. - (Высшее образование: Бакалавриат). (переплет) ISBN 978-5-369-01037- 2, 700 экз.

5. C. Ericson. The gilbert-johnson-keerthi (gjk) algorithm. SIGGRAPH Presentation, 2004. Sony Computer Entertainment America.

6. Аналитическая геометрия. Часть 2. Афинные и Евклидовы пространства [Текст]: учеб. пособие. 2 семестр. – Казань: ТГГПУ, 2013. – 188с.

7. Дьяконов, В.П. MATLAB. Полный самоучитель.: учебное пособие – Москва: ДМК Пресс, 2015. – 768 с.

8. Васильев Ф.П. Численные методы решения экстремальных задач: учебник, 2-е изд., переработ. и доп. – Москва: Наука, 1988. – 552

9. Z.R. Gabidullina. Adaptive conditional gradient algorithm. In IX Moscow International Conference on Operations Research (ORM2018), pages 65 – 70, October 2018.

10. A. Гилат, MATLAB Теория и практика. Malloy Lithographers, 4-e изд., 2016, - 430 с.