Введение 3
Основная часть 5
1. Постановка задачи 5
2. Теоретическое описание метода решения 6
2.1. Задача сильной линейной отделимости выпуклых
многогранников 6
2.2. Измерение толщины сепаратора (псевдосепаратора) 9
2.3. Решение задачи проектирования нуля пространства на
выпуклый многогранник сведением к максиминной задаче 11
2.4. Построение классифицирующей гиперплоскости 13
3. Описание программного продукта 15
3.1. Модуль «Классификация данных» 16
3.2. Модуль «Генерация данных» 21
3.3. Модуль «Проектирование нуля пространства на выпуклый многогранник путём решения максиминной задачи 22
4. Численное экспериментирование с различными исходными данными 25
4.1. Тестовые примеры 25
4.2. Реальный набор данных 30
5. Анализ результатов численного экспериментирования и
графических интерпретаций решения 32
5.1. Анализ результатов для тестовых примеров 32
5.2. Анализ результатов для реального набора данных 35
Заключение 38
Список литературы 40
Приложение 1 41
Приложение 2 50
Приложение 3
Методы машинного обучения в настоящее время находят всё большее практическое применение во многих сферах деятельности человека, начиная с таргетинговой рекламы и заканчивая самоуправляемыми автомобилями. Развитию методов машинного обучения способствует технологические прорывы, наблюдаемые в последние годы, рост доступной вычислительной мощности, увеличение объемов данных за счет совершенствования методов их сбора и хранения.
Одной из наиболее часто решаемых на практике задач машинного обучения является задача классификации данных. Имеется конечное множество объектов, для каждого из которых известно к какому классу они относятся. Это множество называется обучающей выборкой. Также есть некоторое множество объектов, называемое тестовой выборкой, для которых неизвестна их принадлежность к тому или иному классу. Требуется построить алгоритм, с помощью которого можно произвольные объекты тестовой выборки отнести к тому или иному классу. Задачу классификации относят к разделу обучения с учителем.
Если классов два, то говорят о бинарной классификации. Среди примеров прикладных задач, решаемых в её рамках, можно выделить следующие задачи:
• медицинская диагностика,
• оценивание кредитоспособности заёмщиков,
• предсказание месторождения полезных ископаемых,
• обнаружение спама,
• информационная безопасность (определение вредоносных программ) и т.д.
Существует большое количество методов решения задачи классификации данных, в том числе бинарной: дерево решений, метод Байеса, метод опорных векторов, нейронные сети и т.д. В данной работе предлагается решить задачу бинарной классификации данных построением линейного классификатора путем решения максиминной задачи, которая предварительно сводится к минимаксной задаче. Выбор метода решения связан с тем, что при его использовании минимизируется слой неправильной классификации, в случае пересекающихся классов, т.е. когда объект может относиться одновременно к нескольким классам.
Таким образом, целью данной работы является создание программного продукта, осуществляющего бинарную классификацию данных с использованием задачи "минимакса".
Для достижения цели необходимо решить следующие задачи:
1. изучить теорию по классификации данных, сильной линейной отделимости выпуклых многогранников;
2. осуществить алгоритмическое описание бинарной классификации с использованием задачи «минимакса»;
3. выбрать среду и язык разработки программного продукта;
4. реализовать выбранный метод решения задачи классификации на основании алгоритмического описания и разработать графический интерфейс программного продукта;
5. разработать дополнительные модули импорта/экспорта данных;
6. добавить функционал построения графических интерпретаций решения для двух- и трёх - факторных наборов данных;
7. подобрать данные для численного экспериментирования;
8. провести численные эксперименты;
9. осуществить анализ полученных численных результатов и графических интерпретаций решения.
В связи с широкой применимостью задачи классификации на практике изучение и совершенствование методов её решения, а также разработка программных продуктов, решающих данную задачу как никогда актуально на сегодняшний день.
В рамках теоретического исследования удалось построить критерий линейной отделимости выпуклых многогранников, решить побочную задачу проектирования нуля пространства на выпуклый многогранник, максимизировать толщину сепаратора и минимизировать толщину псевдосепаратора, что было доказано в ходе численного экспериментирования при анализе графических интерпретаций решений, а главное, разработать алгоритм построения классифицирующей гиперплоскости.
В ходе анализа результатов численного экспериментирования были выявлены преимущества и недостатки используемого метода решения задачи бинарной классификации. Преимуществом использования выбранного метода для извлечения сложных паттернов из данных является то, что для его использования нет необходимости предварительно понимать поведение данных. Для анализа данных и извлечения паттернов методу достаточно наблюдений за данными и связями внутри них. Недостатком является, то что метод чувствителен к выбросам, т.к. классы представляются в виде выпуклой оболочкой. И возможно в случае, если бы они не учитывались можно было бы построить более точный классификатор. Также было выяснено, что толщина сепаратора (псевдосепаратора) зависит от выбора точки начального приближения, так как метод подключаемый функцией fminimax чувствителен к выбору точки начального приближения.
Для того, чтобы решить выявленные используемого метода необходимо построить механизм фильтрации значений для выявления выбросов и разработать алгоритм выбора оптимальной точки начального приближения.
В дальнейшем возможна модернизация и доработка программного продукта на предмет выявленных недостатков работы метода и разработка модуля интеграции с информационными системами.
В рамках данной работы была достигнута цель - разработан удобный программный продукт, осуществляющий решение задачи бинарной классификации с использованием задачи «минимакса», с возможностью импорта/экспорта данных и построения графических интерпретаций решения для двух- и трёх- факторных наборов данных, имеющий модуль генерации новых данных для тестовых примеров. Соответственно были решены все задачи для её достижения.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
