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

ВВЕДЕНИЕ 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

ВВЕДЕНИЕ

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

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

Опишем подробно, как можно практически реализовать МДМ-метод.
1 шаг. В качестве начального приближения задается
𝑉0 = 〈𝑍𝑖 , 𝑍𝑖 〉 = min 〈𝑍𝑖, 𝑍𝑖〉. Устанавливаем 𝑘 = 0. Задать погрешность
𝑖∈[1:𝑠]
вычисления 𝜀.
2 шаг. Пусть найдено k-е приближение. 𝑉𝑘 ∈ 𝐿.
Через 𝑍𝑘
обозначается точка из множества 𝐻, для которой 〈𝑍𝑘
, 𝑉𝑘 〉 =
min 〈𝑍𝑖, 𝑉𝑘 〉 (если таких точек несколько, то выбрать любую из них).
𝑖∈[1:𝑠]
3 шаг. Вычисление критериальной функции для формулировки условия
остановки: 𝛿(𝑉𝑘) = 〈𝑉𝑘 − 𝑍𝑘, 𝑉𝑘〉.
Если 𝛿(𝑉𝑘) < 𝜀 то алгоритм завершает работу. Наикратчайшим расстоянием будет являться ‖𝑉𝑘‖. Иначе, осуществляется переход к следующему шагу.
4 шаг. Рассмотреть отрезок 𝑉𝑘(𝑡) = 𝑉𝑘 + 𝑡(𝑍𝑘 − 𝑉𝑘), 0 ≤ 𝑡 ≤ 1.
Пусть 𝑡𝑘, 0 ≤ 𝑡𝑘 ≤ 1, определяется соотношением
〈𝑉𝑘(𝑡𝑘), 𝑉𝑘 (𝑡𝑘)〉 = min 〈𝑉𝑘(𝑡), 𝑉𝑘(𝑡)〉.
𝑡∈[0,1]
Найти 𝑡𝑘:

−〈𝑉𝑘, 𝑍𝑘 − 𝑉𝑘〉

0, если 𝑡 < 0
𝑡 =
‖𝑍𝑘̅ − 𝑉��
‖2 𝑡𝑘 = {𝑡, если 𝑡 ∈ [0,1]
1, если 𝑡 > 1

5 шаг. Положим 𝑉𝑘+1 = 𝑉𝑘 (𝑡𝑘).
...

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

Прежде чем рассмотреть GJK – метод приведем используемые обозначения.
𝜗(𝐻) – ближайшая точка к началу координат из выпуклого многогранника
𝜗(𝐻) = min{‖𝑥‖ ∶ 𝑥 ∈ 𝐻} (8)
Так как H – выпуклый многогранник, то 𝜗(𝐻) – единственна.
Симплекс 𝑀 – подмножество точек, составляющих выпуклый многогранник, образующее 𝑛 + 1 точками. Для двухмерного пространства симплекс – треугольник, трехмерного – тетраэдр.
𝑙 – количество точек, составляющих симплекс.
𝐿(𝑀) – выпуклая оболочка симплекса.
ℎ𝐻(𝑝) – опорная функция. Это функция, которая для выпуклого тела возвращает экстремальную точку в направлении 𝑝.
ℎ𝐻(𝑝) = 𝑚𝑎𝑥{𝑥 ∗ 𝑝 ∶ 𝑥 ∈ 𝐻 } (9)

Рис. 2 Нахождения решения с
помощью опорной функции

𝑠𝐻(𝑝) – любое решение (1). ℎ𝐻(𝑝) = 𝑠𝐻(𝑝) ∗ 𝑝, 𝑠𝐻(𝑝) ∈ 𝐻
Алгоритм определения 𝜗(𝐻), где 𝐻 ∈ 𝑅𝑛.
Генерируются последовательности симплексов 𝐿(𝑀𝑘) (выпуклые оболочки), содержащихся в 𝐻, таких, что их 𝜗(𝐿(𝑀𝑘)) → 𝜗(𝐻).
В каждой итерации алгоритма нужно вычислять, 𝜗(𝐿(𝑀𝑘)).
...

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

В этом разделе приведена практическая реализация GJK – метода.
1 шаг. Генерируется выпуклое множество 𝐻 ∈ 𝑅𝑛. Установить некое множество 𝑀0 = {𝑍1, … , 𝑍𝑙} , состоящее из точек, принадлежащих 𝐻, где размер множества 𝑙 = 𝑛 + 1. Установить k=0 (номер итерации). Задать погрешность вычисления 𝜀.
2 шаг. Определить 𝜗𝑘 = 𝜗(𝐿(𝑀𝑘))
Для каждого отрезка, составленного из множества 𝑀𝑘 находится 𝜗 и
записывается в множество K (количество элементов множества равно 𝑙∗(1+𝑙)),
2
таким образом:
Для каждого 𝑍𝑖 ∈ 𝑀𝑘, 𝑍𝑗 ∈ 𝑀𝑘, так что 𝑍𝑖 ≠ 𝑍𝑗 :
−〈𝑍𝑖, 𝑍𝑗 − 𝑍𝑖〉
0, если 𝑡 < 0
𝑡 =
‖𝑍𝑗 − 𝑍𝑖‖
2 𝑡 = {𝑡, если 𝑡 ∈ [0,1] 1, если 𝑡 > 1
𝜗 = 𝑍𝑖 + 𝑡(𝑍𝑗 − 𝑍𝑖), 0 ≤ 𝑡 ≤ 1.
Из полученного множества K находится точка с минимальным расстоянием до начала координат:
𝜗∗ = min{‖𝜗‖ ∶ 𝜗 ∈ 𝐾}
Из множества M исключается найденная точка 𝐾 = 𝐾\𝜗∗.
...

Приложение 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.4.2 ACGA метод практическая реализация
В этом разделе приводится практическая реализация ACGA – метода.
1 шаг. В качестве начального приближения задается
𝑥0 = 〈𝑍𝑖 , 𝑍𝑖 〉 = min 〈𝑍𝑖, 𝑍𝑖〉. 𝑥0 ∈ 𝐿, 𝛽 ∈ (0; 1), 𝜀0 > 0, 0 < 𝜎0 ≤ 1,
𝑖∈[1:𝑠]

0 < 𝛼 ≤ 𝛼0
Устанавливается 𝑘 = 0.
2 шаг. Выбрать точку 𝑦𝑘, 𝑘 = 0,1,2, … таким образом, чтобы удовлетворялись условия 0 < 𝜎 ≤ 𝜎𝑘 ≤ 1 и 0 < 𝛼 ≤ 𝛼0 , это означает:
〈𝑔(𝑥𝑘), 𝑦𝑘 − 𝑥𝑘 〉 ≤ max {𝜎𝑘 min〈𝑔(𝑥𝑘), 𝑥 − 𝑥𝑘 〉, −𝛼𝑘}
𝑥∈𝐿
Проверка критерия остановки
Если 〈𝑔(𝑥𝑘), 𝑦𝑘 − 𝑥𝑘 〉 = 0, алгоритм завершает работу. Кратчайшим расстоянием является ‖𝑥𝑘‖.
Иначе вычисляется 𝑡𝑘 = |𝑔(𝑥𝑘), 𝑦𝑘 − 𝑥𝑘|
И вычисляется 𝑠𝑘:
𝑦𝑘 − 𝑥𝑘, если 〈𝑔(𝑥𝑘), 𝑦𝑘 − 𝑥𝑘 〉 + 𝜀𝑘 ∗ ‖𝑦𝑘 − 𝑥𝑘‖𝜈 ≤ 0
𝑠𝑘 = {
𝑡𝑘(𝑦𝑘 − 𝑥𝑘)
𝜀𝑘 ∗ ‖𝑦𝑘 − 𝑥𝑘‖𝜗
, в противном случае
3 шаг. Пусть 𝑖̂𝑘 – наименьший индекс 𝑖 ∈ 𝐽(𝑖̂), для которого выполняется условие выбора итерационного размера шага для 𝑥 = 𝑥𝑘, 𝑠 = 𝑠𝑘, 𝜀 = 𝜀𝑘.
Вычисляется 𝜂 = (1 − 𝛽)1⁄𝜈−1.
...

1.5 Задача классификации данных
Пусть дано два множества 𝑍, 𝑃.
𝑐𝑜𝑛𝑣(𝐷) – наименьшее выпуклое множество, содержащее множество 𝐷.
𝐿 = 𝑐𝑜𝑛𝑣{𝑧𝑖}𝑖=̅1̅̅:̅𝑙
𝑀 = 𝑐𝑜𝑛𝑣{𝑝𝑗}𝑗=̅1̅̅:̅𝑚̅̅
Линией уровня функции 𝑓(𝑥) называется геометрическое место точек, удовлетворяющее уравнению 𝑓(𝑥) = 𝑐𝑜𝑛𝑠𝑡.
Уравнение гиперплоскости: 𝜋(с, 𝛾) = {𝑥 ∈ 𝑅𝑛 ∶ 〈𝑐, 𝑥〉 = 𝛾}
𝑐 – нормаль опорной гиперплоскости, которая отделяет 0 от гиперплоскости.
𝛾 – сдвиг.
𝜋(с, 𝛾𝐿) – называется опорной к классу L, если 𝛾𝐿 = min〈𝑐, 𝑧𝑖〉
𝑖=̅1̅̅:̅𝑙
𝜋(с, 𝛾𝑀) – называется опорной к классу M, если 𝛾𝑀 = min 〈𝑐, 𝑝𝑗〉
𝑗=̅1̅̅:̅𝑚̅̅
𝑓(𝑥) = 〈𝑐, 𝑥〉 − 𝛾∗, называется линейным классификатором, где 𝛾∗
определяется как 𝛾∗ = 𝛾𝐿+𝛾𝑀.
2
Принцип классификации
Пусть 𝑧̅ точка, которую нужно классифицировать (отнести к первому, либо ко второму классу).
Если 𝑓(𝑧 Если 𝑓(𝑧 Если 𝑓(𝑧
> 0, то 𝑧̅ ∈ 𝐿.
< 0, то 𝑧̅ ∈ 𝑀.
= 0, то отнести, либо к первому, либо ко второму классу, либо
не отнести ни к одному.
...

Приложение 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
ВВЕДЕНИЕ

В наше время компьютер стал неотъемлемой частью нашей жизни.
...

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

Численные эксперименты были проведены для решения следующих вопросов:
Как лучше выбирать точку начального приближения на 0 шаге? Из всего множества, полученного разностью Минковского или из точек из оболочки, точки которой получены из разности Минковского.
...

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 с.