Введение 4
1. Теоретическая часть 6
1.1 Постановка задачи 6
1.2 Теоретическое описание метода решения 6
1.2.1 Задача сильной линейной отделимости выпуклых многогранников 7
1.2.2 Измерение толщины сепаратора (псевдосепаратора) 10
1.2.3 Решение задачи проектирования нуля Евклидова пространства на выпуклый многогранник сведением к задаче максимина 12
1.2.4 Решение задачи проектирования нуля Евклидова пространства на выпуклый многогранник сведением к линейной задаче о дополнительности 14
1.2.5 Построение классифицирующей гиперплоскости 22
2. Практическая часть 23
2.1 Описание программного продукта 23
минимакса» 24
2.1.2 Модуль «Классификация данных с использованием линейной задачи о
дополнительности» 33
2.1.3 Модуль «Проектирование нуля Евклидова пространства на выпуклый
многогранник с использованием задачи минимакса» 34
2.1.4 Модуль «Проектирование нуля Евклидова пространства на выпуклый
многогранник с использованием линейной задачи о дополнительности» 38
2.1.5 Модули для генерации данных 40
2.2 Проведение численных экспериментов и анализ полученных результатов...43
2.2.1 Тестовые эксперименты 43
2.2.2 Эксперименты с реальными наборами данных 63
Заключение 72
Список использованной литературы 74
Приложения
В настоящее время сложно переоценить актуальность машинного обучения, которое день ото дня находит все большее практическое применение во множестве сфер деятельности человека. Буквально на каждом своём шагу современный человек так или иначе сталкивается с машинным обучением: распознавание речи, рукописного ввода, образов, медицинская и техническая диагностика, кредитный скоринг, ранжирование в
информационном поиске, обнаружение спама - это лишь малая часть его приложений.
Задача классификации является одной из классических задач, решаемых с помощью машинного обучения. Классификация - это системное распределение изучаемых предметов, явлений, процессов по родам, видам, типам, по каким-либо существенным признакам для удобства их исследования; группировка исходных понятий и расположение их в определённом порядке, отражающем степень этого сходства [14]. Таким образом, под классификацией будем понимать отнесение объектов (зависимых переменных) к одному из заранее известных классов. Классификация относится к стратегии обучения с учителем (supervised learning), которое также называют контролируемым или управляемым обучением. В данной работе речь пойдёт о решении задачи бинарной классификации, то есть когда классов для распределения всего два.
Для решения задачи бинарной классификации существует большое количество методов: метод Байеса, метод опорных векторов, дерево решений и др. Далее будет предложено решение данной задачи путём построения линейного классификатора с использованием задач минимакса и линейной задачи о дополнительности.
Целью данной работы является создание программного продукта, осуществляющего бинарную классификацию данных посредством решения задач минимакса и линейной задачи о дополнительности. Для достижения этой цели необходимо решить следующие задачи:
1. Изучить постановку задачи бинарной классификации;
2. Изучить постановку задачи линейной отделимости политопов;
3. Изучить использование задачи линейной отделимости политопов при решении задачи бинарной классификации;
4. Изучить постановку и методы решения задачи минимакса;
5. Изучить постановку и методы решения линейной задачи о дополнительности;
6. Численно реализовать алгоритм решения задачи линейной
отделимости политопов посредством задач минимакса и линейной задачи о дополнительности и, как следствие решения задачи бинарной
классификации;
7. Разработать графический интерфейс для программного продукта;
8. Подобрать реальные данные для проведения числовых экспериментов;
9. Провести числовые эксперименты с реальными данными;
10. Осуществить анализ полученных результатов.
Данная работа состоит из двух больших разделов: теоретическая часть и практическая часть. В свою очередь теоретическая часть включает в себя постановку основной задачи, описание метода решения данной задачи с применением задачи линейного разделения множеств, определения толщины сепаратора (псевдосепаратора), описание методов решения задачи проектирования нуля евклидова пространства на выпуклый многогранник путём сведения к задаче минимакса и линейной задаче о дополнительности. Практическая же часть описывает каждый модуль получившегося в результате программного продукта, численные эксперименты, проводимые с ним, а также последующий анализ полученных нами результатов.
В рамках выполнения данной работы были изучены и численно реализованы алгоритмы решения задачи бинарной классификации посредством задач минимакса и линейной задачи о дополнительности, а также алгоритм решения линейной задачи о дополнительности; разработано программное приложение в среде Matlab, позволяющее отыскивать не только решение задачи бинарной классификации, но и решение задачи проектирования нуля Евклидова пространства на выпуклый многогранник; разработан графический интерфейс для полученного приложения в среде GUIDE пакета Matlab; проведены численные эксперименты как на тестовых, так и на реальных данных, а полученные результаты были проанализированы.
В ходе теоретического исследования удалось сформулировать критерий линейной отделимости выпуклых многогранников, отыскать решение вспомогательной задачи проектирования нуля пространства на выпуклый многогранник, определить условия максимизации толщины сепаратора и минимизации толщины псевдосепаратора, что было продемонстрировано в ходе численного экспериментирования при разборе графических интерпретаций решений, а главное, разработать алгоритм построения классифицирующей гиперплоскости.
В практической же части исследования мы демонстрируем интерфейс и результаты работы полученного продукта и описываем каждый из его модулей, а затем проводим численные эксперименты и анализируем результаты.
В ходе анализа результатов мы убедились в том, что алгоритм решения задачи классификации посредством задачи минимакса является более предпочтительным нежели с помощью линейной задачи о дополнительности. Использование функции позволяет построение псевдосепаратора, что предполагает возможность классификации даже в случае неотделимости обучающих множеств. Однако стоит упомянуть, что данный метод является чувствительным к выбору начальной точки приближения и в зависимости от её выбора может давать совершенно различные результаты. Оба метода своим недостатком имеют чувствительность к выбросам, так как основаны на построении выпуклой оболочки множеств. Поэтому при предварительном анализе данных следует более тщательно подойти к процессу исключения выбросов, что впоследствии может дать более точные результаты классификации.
Таким образом, цель работы достигнута и нами разработан программный продукт, осуществляющий бинарную классификацию данных с использованием теорем об отделимости.
В дальнейшем возможна оптимизация алгоритмов, лежащих в основе программы, и модификация программного продукта с целью устранения недостатков, уменьшения времени работы программы и повышения эргономичности продукта.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
