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

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

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

В связи с появлением гаджетов на операционных мобильных системах, таких как 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