ВВЕДЕНИЕ 3
1. АНАЛИТИЧЕСКИЙ ОБЗОР 6
1.1. Описание предметной области 6
1.2. Литературный обзор 7
2. ПОЛИЭДРАЛЬНАЯ ОПТИМИЗАЦИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ
КЛАССИФИКАЦИИ 14
2.1. Описание базы данных 14
2.2. Полиэдральная оптимизация 18
2.2.1. Основные понятия и теоремы 18
2.2.2. Универсальное измерение толщины сепаратора или псевдосепаратора 23
3. ПОСТАНОВКА ЗАДАЧИ КЛАССИФИКАЦИИ БАНКНОТ 26
4. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ, С ПОМОЩЬЮ
КОТОРОГО РЕШАЕТСЯ ЗАДАЧА КЛАССИФИКАЦИИ БАНКНОТ 29
4.1 Описание приложения 29
4.2 Проведение численных экспериментов 33
4.3 Анализ проделанной работы 37
ЗАКЛЮЧЕНИЕ 38
СПИСОК ЛИТЕРАТУРЫ 39
ПРИЛОЖЕНИЕ 1 41
ПРИЛОЖЕНИЕ 2
Современное общество трудно представить без различных технических устройств, новомодных гаджетов, смартфонов, а так же без автоматизации различных услуг и действий, которых людям приходится выполнять изо дня в день. Появление всего этого делает жизнь человека проще и комфортнее, позволяя сосредоточится на более важных делах, не задумываясь о мелочах. Речь идет об автоматической оплате счетов и штрафов, совершении онлайн покупок, возможности безналичной и автоматической оплаты операций купли - продажи.
Данная работа посвящена тому, как обеспечить подлинность денежных купюр при повсеместном росте популярности безналичного расчета, использования банковских карт и автоматической оплаты с помощью телефонов, часов и интернет приложений. Ведь с развитием информационных технологий, автоматической обработки информации происходит прогресс не только среди технических устройств, облегчающих нашу жизнь, но и среди устройств, с помощью которых можно заниматься мошеннической деятельностью, например, подделкой денежных купюр.
Актуальность данной темы очевидна, поскольку частое использование безналичного расчета притупляет внимание некоторых людей в отношении наличных денег, чем могут воспользоваться злоумышленники. Актуальность темы подтверждает и то, что стали появляться денежные купюры нового образца номиналом 200 и 2000 рублей, а так же выпуск в оборот ограниченных серий купюр, посвященных различным мероприятиям (олимпиада, чемпионат мира), подлинность которых зачастую может вызывать сомнения. И если в крупных городах и мегаполисах люди способны отличить подделку от настоящих денег или прибегнуть к помощи специалистов или специальных устройств, то в менее развитых городах и областях, как правило, это затруднительно.
Основной целью данной работы является построение классификатора для решения задачи определения подлинности банкнот с помощью полиэдральной оптимизации. Данный подход основан на том, чтобы каждый анализируемый объект - банкноту рассматривать как точку в n - мерном пространстве, при этом объекты, принадлежащие одному классу, представляют собой выпуклый многогранник. Тогда задача классификации банкнот примет вид задачи линейной отделимости двух выпуклых многогранников.
Для реализации поставленной цели были рассмотрены следующие задачи:
1. Проблема проектирования нуля пространства на выпуклый многогранник и решить её, путем сведения к задаче максимина;
2. Задача построения «разности Минковского» для двух выпуклых многогранников;
3. Построение сепаратора максимальной толщины, в случае отделимости многогранников и псевдосепаратора наименьшей толщины, в случае неотделимости многогранников;
4. Установить правило отнесения новых данных к тому или иному многограннику;
Результатом работы стал программный комплекс, который по входным данным - характеристикам банкнот, позволяет определить, является ли банкнота подлинной или нет.
В первой главе данной работы рассмотрены подходы и методы к задаче классификации банкнот отечественными и зарубежными исследователями, выявлены преимущества и недостатки данных подходов, рассмотрены полученные результаты.
Вторая глава посвящена теории полиэдральной оптимизации и описанию входных данных для задачи классификации. Здесь кратко описаны методы, используемые для извлечения характеристик банкнот, изложены основные
определения и теоремы полиэдральной оптимизации.
В третьей главе расписана математическая модель для задачи классификации банкнот.
Четвертая глава посвящена описанию полученного приложения и описанию проведенных численных экспериментов, доказывающих эффективность построенного классификатора.
В заключительной части работы подведены итоги, проведен анализ полученных результатов.
Разработанное приложение достигает поставленной цели: по входным данным - характеристикам банкнот, строит классификатор и идентифицирует новую купюру как подлинную или же фальшивую.
Построение классификатора осуществлялось на основе вышеизложенной теоретической базы. Приложение, получая на вход базу данных с характеристиками различных банкнот и число признаков, по которым необходимо провести классификацию, строит сепаратор, в случае отделимости двух классов, или псевдосепаратор, в противном случае, который и позволяет провести классификацию.
При создании приложения были выполнены следующие задачи:
1. Изучена проблема проектирования нуля пространства на выпуклый многогранник и её решение, путем сведения к задаче максимина;
2. Изучена задача построения «разности Минковского» для двух выпуклых многогранников;
3. Реализовано построение сепаратора максимальной толщины, в случае отделимости многогранников и псевдосепаратора наименьшей толщины, в случае неотделимости многогранников;
4. Установлено правило отнесения новых данных к тому или иному многограннику;
Проведенные численные эксперименты подтвердили правильность построения классификатора и эффективность применения теории полиэдральной оптимизации к задачам классификации. Приложение может выступать в качестве инструмента эксперта для проверки денежных купюр на различных предприятиях и организациях.
