Методы и алгоритмы классификации данных на основе многомерной триангуляции Делоне тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Дорошенко Александр Юрьевич

• Дорошенко Александр Юрьевич
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Дорошенко Александр Юрьевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ И АЛГОРИТМОВ КЛАССИФИКАЦИИ ДАННЫХ

1.1. Анализ применения методов классификации

1.2. Формализованная постановка задачи

1.3. Общий подход к решению

1.4. Линейные методы классификации

1.4.1. Метод опорных векторов

1.4.2. Метод релевантных векторов

1.4.3. Однослойный персептрон

1.4.4. Дискриминантный анализ

1.4.5. Логистическая регрессия

1.5. Многослойные персептроны

1.6. Радиальные базисные сети

1.7. Гауссова модель смешения

1.8. Композиция (ансамбль) распознавателей

1.9. Логические методы

1.10. Метрические классификаторы

1.11. Наивный байесовский классификатор

1.12. Обсуждение рассмотренных методов

1.13. Идея разработанного подхода

1.14. Основные результаты

ГЛАВА 2. РАЗРАБОТКА МЕТОДОВ КЛАССИФИКАЦИИ ДАННЫХ НА

ОСНОВЕ МНОГОМЕРНОЙ ТРИАНГУЛЯЦИИ ДЕЛОНЕ

2.1. Основные понятия и определения

2.2. Метод классификации данных на основе многомерной триангуляции Делоне

2.2.1. Построение разделяющей гиперповерхности

2.2.2. Представление разделяющей гиперповерхности

2.2.3. Вычисление сегментов разделяющей гиперповерхности

2.2.4. Классификация произвольных объектов

2.2.5. Устранение «вырожденности» при определении пересечения отрезка и разделяющей гиперповерхности

2.2.6. Многоклассовая классификация

2.3. Контроль способности к обобщению

2.4. Анализ выбросов

2.5. Метод ограничивающих объемов

2.6. Основные результаты

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ КЛАССИФИКАЦИИ ДАННЫХ НА ОСНОВЕ МНОГОМЕРНОЙ ТРИАНГУЛЯЦИИ ДЕЛОНЕ

3.1. Общее описание алгоритмической модели

3.2. Об алгоритмах вычисления многомерной триангуляции Делоне

3.3. Алгоритм отбора виртуальных симплексов

3.4. Алгоритм выборки вершин граничных гиперповерхностей классов и определения смежных с ними точек

3.5. Алгоритм отсева выбросов

3.6. Алгоритм сглаживания граничных гиперповерхностей классов

3.7. Алгоритм вычисления сегментов разделяющей гиперповерхности

3.7.1. Алгоритм вычисления гиперплоскости сегмента

3.7.2. Алгоритм вычисления полупространств сегмента

3.8. Алгоритм классификации

3.9. Алгоритм определения пересечения сегмента и отрезка

3.10. Алгоритм классификации с использованием ограничивающих объемов

3.11. Основные результаты

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНОЕ СОПОСТАВИТЕЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ МЕТОДОВ И АЛГОРИТМОВ

4.1. Оценка границ применимости предложенного метода

4.1.1. Экспериментальная оценка сложности разработанного метода разделяющей гиперповерхности в зависимости от числа измерений

4.1.2. Экспериментальная оценка зависимости различных показателей разработанного классификатора от размера обучающего набора

4.1.3. Экспериментальная оценка зависимости различных показателей разработанного классификатора от количества классов

4.1.4. Об ограничениях и условиях эффективного использования разработанного метода разделяющей гиперповерхности

4.2. Исследование метода разделяющей гиперповерхности в условиях линейной разделимости исходных данных

4.3. Исследование метода разделяющей гиперповерхности в условиях линейной неразделимости исходных данных

4.4. Исследование метода сглаживания разделяющей гиперповерхности

4.5. Исследование метода отсева выбросов

103

4.6. Исследование метода классификации с использованием ограничивающих объемов

4.7. Исследование разработанного метода на реальных данных

4.8. Обсуждение полученных результатов экспериментального исследования

4.9. Основные результаты

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЯ

ВВЕДЕНИЕ

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы классификации данных на основе многомерной триангуляции Делоне»

Актуальность темы исследования

К задаче машинного обучения классификации данных (обучение с учителем) сводятся сложные прикладные задачи, число которых постоянно растет в связи с необходимостью обработки и управления обширными объемами цифровых данных, накапливаемых вследствие повсеместного применения компьютерных технологий. Имеются ввиду задачи управления бизнес-процессами, информационной безопасностью и персоналом, анализа рисков в банковской сфере, экономического прогнозирования, медицинской диагностики, формирования контекстной рекламы, фильтрации спама и многие другие. Доступность и эффективность достижений машинного обучения классификации данных для решения обозначенных проблем в совокупности со сложностью или отсутствием их решений другими известными методами приводят к популяризации и повсеместному внедрению данных технологий, что позволяет открывать новые пути получения конкурентного преимущества, оптимизации и автоматизации технологических процессов и интеллектуального труда человека, а также стимулирует развитие новых идей.

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

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

Степень разработанности темы исследования

Значительный вклад в развитие методологии машинного обучения классификации данных внесли работы многих отечественных и зарубежных ученых, среди которых в первую очередь стоит выделить публикации В.Н. Вапника и А.Ю. Червоненкиса, разработавших теорию минимизации структурного риска, а также таких известных ученых, как М.А. Айзерман, Э.М. Браверман, Л.И. Розоноэр, Ю.И. Журавлев, Ю.Э. Нестеров, C.M. Bishop, L. Breiman, N. Cesa-Bianchi, K. Crammer, C.C. Chang, A. Conconi, C. Cortes, R.A. Fisher, J.H. Friedman, C. Gentily, I. Guyon, T. Hastie, Y. LeCun, C.H. Lin, S. Marshland, W. McCulloch, R.A. Ohlsen, W. Pitts, J.R. Quinlan, F. Rozenblatt, S. Shalev-Shwartz, S. Ben-David, C.L. Stone, M.E. Tipping и др.

Целью диссертационной работы является повышение точности классификации различных наборов данных, включающих сложные линейно неразделимые пространственные конфигурации классов образов, путем разработки

новых методов и алгоритмов, основанных на использовании многомерной триангуляции Делоне. Основная идея предлагаемых методов и алгоритмов состоит в использовании многомерной триангуляции Делоне для оценки границ классов и построении, с помощью метода вычисления срединной оси, равноудаленной от них гиперповерхности, разделяющей множества объектов классов в пространстве исходных признаков.

Для достижения поставленной цели были сформулированы и решены следующие основные задачи:

1) анализ существующих методов и алгоритмов классификации данных с целью выяснения их достоинств, недостатков, характерных особенностей и ограничений;

2) разработка основного метода и алгоритма классификации данных, использующего многомерную триангуляцию Делоне. При этом решены следующие подзадачи:

- создание методов и алгоритмов процесса построения разделяющей гиперповерхности и процесса классификации;

- создание методов и алгоритмов сглаживания разделяющей гиперповерхности и отсева выбросов («артефактов») в обучающей выборке, позволяющих снизить риск переобучения;

3) разработка вспомогательного метода и алгоритма классификации данных на основе ограничивающих объемов, позволяющего снизить среднюю сложность процесса распознавания основным методом классификации без потери точности;

4) проведение экспериментальных исследований для определения эффективности предложенных методов и алгоритмов в сопоставлении с аналогами.

Объектом исследования являются методы и алгоритмы машинного обучения классификации данных.

Предмет исследования - точность классификации методами и алгоритмами классификации данных (обучение с учителем).

Научная новизна диссертационного исследования заключается:

1) в разработанном новом методе классификации данных, отличающемся использованием многомерной триангуляции Делоне для оценки границ классов и метода вычисления срединной оси для построения равноудаленной от границ классов разделяющей гиперповерхности, позволяющем расширить методологию машинного обучения классификации данных для случаев со сложными линейно неразделимыми пространственными конфигурациями распознаваемых классов без снижения показателей точности в сопоставлении с известными методами и алгоритмами;

2) в разработанных методе сглаживания разделяющей гиперповерхности, использующем метод Лапласа, и методе анализа выбросов, позволяющих повысить точность распознавания и снизить риск переобучения предложенного метода классификации на основе многомерной триангуляции Делоне;

3) в разработанном новом методе классификации данных, использующем два классификатора: на основе ограничивающих объемов и многомерной триангуляции Делоне. Последний из них применяется только при неоднозначности принятия решения первым, что позволяет достичь снижения средней сложности процесса классификации без потерь в точности распознавания.

Практическая значимость диссертации заключается в том, что разработанные методы и алгоритмы реализованы на программном уровне и могут составить основу для постановки научно-исследовательских и опытно-конструкторских работ (НИОКР), а также пригодны для конкретного применения в решении обозначенных задач управления и обработки неструктурированных цифровых данных, включающих сложные линейно неразделимые пространственные конфигурации распознаваемых классов. Полагается непосредственное применение в качестве автоматизированного модуля классификации данных, что подтверждается актом внедрения в проекте АО НТЦ «Поиск ИТ», а также свидетельством о государственной регистрации программы для ЭВМ. Достигнутые теоретические результаты исследования используются в учебном процессе Курского государственного университета, что подтверждается соответствующей справкой о внедрении.

Методы исследования

В процессе выполнения работы использовались методы системного анализа, распознавания образов (машинного обучения), теории алгоритмов, математического моделирования, линейной алгебры, вычислительной геометрии и теории алгоритмов. Экспериментальные исследования проводились на модельных данных и общедоступных наборах реальных данных. Для сравнения использовались эффективные программные реализации известных алгоритмов, входящие в состав свободно распространяемого программного обеспечения.

Достоверность полученных в настоящей диссертационной работе результатов подтверждается корректным использованием математического аппарата теории машинного обучения классификации данных, применением адекватных математических моделей, результатами экспериментальных исследований, актом и справкой о внедрении, положительными результатами обсуждения основных положений работы на международных научно-технических конференциях.

Реализация и внедрение

Основные практические результаты настоящей диссертационной работы внедрены в проект «Лавина» АО НТЦ «Поиск ИТ» в качестве автоматизированного модуля классификации обрабатываемых данных. Достигнутые теоретические результаты исследования используются в учебном процессе Курского государственного университета в рамках изучения магистрантами второго курса направления «Теория распознавания образов и анализ изображений». Соответствующие электронные копии акта и справки приведены в приложении 1.

Апробация результатов диссертационного исследования

Основные положения диссертации докладывались и обсуждались на I и II международной научно-технической конференции «Вопросы кибербезопасности, моделирования и обработки информации в современных социотехнических системах» «Информ-2015» (Курск - 2015) и «Информ-2016» (Курск - 2016) соответственно.

Публикации

По теме диссертации опубликовано 8 научных работ, в том числе 4 в журналах, входящих в перечень рекомендованных ВАК РФ, 2 публикации в сборниках международных конференций. В федеральном государственном бюджетном образовательном учреждении высшего образования «Курский государственный университет» получено свидетельство (.№ 2013663088 от 15 декабря 2014 г.) о государственной регистрации программы для ЭВМ.

Личный вклад

Все выносимые на защиту научные результаты получены соискателем лично либо при его непосредственном участии. В работах по теме диссертации, опубликованных в соавторстве, соискателем выполнено следующее:

- предложена общая идея метода классификации данных на основе многомерной триангуляции Делоне для двумерного пространства признаков (доля участия автора - 60%) [1];

- метод классификации на основе многомерной триангуляции Делоне расширен для произвольного пространства признаков, разработана его алгоритмическая модель и проведено практическое исследование его реализации в сравнении с существующими аналогами на модельных данных (доля участия автора - 50%) [2];

- разработан способ контроля способности к обобщению предложенного метода классификации, использующий сглаживание Лапласа, и метод анализа выбросов в обучающей выборке, созданы соответствующие алгоритмы, проведено практическое исследование программной реализации (доля участия автора - 50%)

[3];

- предложен метод ограничивающих объемов, рассматриваемый в терминологии булевой логики и алгорифмов Маркова. Рассмотрен подход к построению модели классификации с использованием двух классификаторов (доля участия автора - 50%) [4];

- описан метод ограничивающих объемов и его применение в модели классификации, использующей два классификатора. Проведено экспериментальное исследование его реализации с классификаторами, имеющими различную вычислительную сложность (доля участия автора - 60%) [5].

Основные положения, выносимые на защиту

1. Метод классификации данных на основе многомерной триангуляции Делоне, вычисляющий равноудаленную от границ классов гиперповерхность, разделяющую заданные классы в пространстве исходных признаков.

2. Методы сглаживания разделяющей гиперповерхности и анализа выбросов, позволяющие повысить точность классификации разработанным классификатором.

3. Метод классификации данных, использующий два классификатора: на основе ограничивающих объемов и многомерной триангуляции Делоне. Последний из них применяется только при неоднозначности принятия решения первым, что позволяет достичь снижения сложности процесса классификации в среднем без потерь в точности распознавания.

4. Разработанные алгоритмы, необходимые для реализации предложенных методов.

5. Результаты практического сравнительного исследования разработанной программной реализации предложенных методов и алгоритмов, подтверждающие эффективность полученных решений.

Соответствие диссертации паспорту научной специальности Область машинного обучения классификации данных связана со средствами интеллектуальной поддержки управления автономными техническими системами и системами, включенными в контуры автоматизированного управления, с обработкой и анализом баз данных разнообразного содержания больших объемов, вследствие чего представленная диссертация соответствует паспорту специальности 05.13.01 по следующим пунктам:

- п. 4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации;

- п. 5. Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации;

- п. 10. Методы и алгоритмы интеллектуальной поддержки при принятии управленческих решений в технических системах.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения, списка литературы (163 источника) и приложений, изложенных на 163 страницах, содержит 39 рисунков и 19 таблиц. В приложениях приведены копии документов о внедрении результатов настоящей диссертационной работы, свидетельство о государственной регистрации программы для ЭВМ и исходные тексты программ, реализованных согласно разработанным алгоритмам.

Во введении обоснована актуальность разрабатываемой темы исследования, сформулированы цель и задачи работы, перечислены применяемые методы исследования, рассмотрены научная новизна, практическая и теоретическая ценность полученных результатов, указано количество основных публикаций по теме исследования, а также отмечены организации, в которых внедрены основные практические и теоретические результаты диссертационной работы.

В первой главе диссертации формализуется задача классификации данных (обучение с учителем) и проводится обзор основных существующих методов и алгоритмов, предназначенных для её решения. Выделяются достоинства, недостатки, а также характерные особенности и ограничения для каждого из рассмотренных методов. Исходя из полученных результатов анализа существующей методологии классификации данных определяются основания для создания новых методов и алгоритмов. В конце главы дается краткий обзор разработанных решений.

Во второй главе приводятся основные используемые понятия и определения, дается математическое описание разработанных методов, предназначенных для решения задачи машинного обучения классификации данных. Рассматриваются вопросы построения разделяющей гиперповерхности на основе многомерной триангуляции Делоне, её сглаживания с помощью метода Лапласа,

распознавания объектов. Разбирается способ анализа выбросов в обучающем наборе. Приводится математическое описание разработанного метода классификации на основе ограничивающих объемов.

В третьей главе приводится формальное описание всех алгоритмов разработанных методов решения задачи машинного обучения классификации данных, необходимых для программной реализации.

В четвертой главе рассматриваются некоторые отдельные результаты тестирования реализации разработанных методов и алгоритмов, позволяющие составить общее представление о возможностях и практической значимости предлагаемых идей. Описываются условия проведения экспериментов, программные и аппаратные средства, с помощью которых проводилось тестирование. Указываются методы и программные реализации, используемые для проведения сравнительного анализа.

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

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ И АЛГОРИТМОВ

КЛАССИФИКАЦИИ ДАННЫХ

1.1. Анализ применения методов классификации

В данной исследовательской работе рассматриваются основные подходы к решению одной из фундаментальных проблем теории распознавания образов (машинное обучение, статистическое обучение) - обучению классификации данных. Актуальность проведения исследований и разработки новых методов и алгоритмов классификации, несмотря на широкое развитие существующей методологии, описанной, например, в работах [6-9] обусловливается разнообразием и высокой практической значимостью задач, формулируемых в указанном виде или к нему сводимых. Среди наиболее значимых примеров применения достижений исследуемой научной области можно отнести следующие:

- категоризация текстов (в том числе фильтрация спама) [10-14];

- формирование контекстной рекламы [15];

- распознавание речи [16] и текста [17,18];

- диагностика онкологических заболеваний [19];

- разработка лекарств, построение диагностических систем и систем поддержки принятия решений в медицине [20-22];

- биометрическая идентификация [23];

- приложения для бизнеса и финансов, связанные с анализом экономического состояния предприятий, оценкой их кредитоспособности и перспектив инвестирования [24-26];

- основа некоторых поисковых систем [27];

- задачи геологического прогнозирования и геостатистика [28,29];

- обнаружение стеганографических сообщений в цифровых изображениях [30-32];

- защита компьютерных информационных сетей [33];

- распознавание лиц [34,35];

- наблюдение сейсмической активности [36,37].

Отдельно выделим использование методов классификации в сфере стегоанализа для выявления факта наличия скрытых сообщений. Успешность такого применения мотивирует на разработку новых, более устойчивых алгоритмов стеганографии. В частности, нами предложено использовать хаотические дискретные отображения для внедрения в некоторый контейнер (изображение) требуемой информации [38,39].

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

1.2. Формализованная постановка задачи

В общей постановке задачи машинного обучения классификации данных требуется построить (обучить) математическую модель, называемую классификатором, аппроксимирующую с приемлемой точностью зависимость между объектами (наблюдениями), описываемыми набором признаков (features), и некоторым набором значений, называемых классами, принадлежность к которым части объектов достоверно известна.

Формально требуется по заданному набору пар, называемому обучающей выборкой,

Т = {(х1,у1), ...,(хп,Уп)},Т сХхГ, (1.1)

построить алгоритм, позволяющий определять принадлежность как известных, так и неизвестных объектов к заданным классам с требуемой точностью, вида

f-.X^Y, (1.2)

где X - пространство признаков (объектов), определяемое как Декартово произведение множеств допустимых значений признаков Хг х ... х Xd, Y = [1,...,q} - множество обозначений (номеров) распознаваемых классов, называемое пространством ответов (альтернатив, исходов),

xi = ■",xi(d)>)>E X,i = 1,... ,n - признаковое описание i-го объекта,

являющееся d-мерным вектором значений признаков пространства X, yi E Y,i = 1,...,п - номер класса i-го объекта.

В зависимости от используемого подхода пространство признаков может отождествляться с некоторым метрическим (например, Евклидовым) или вероятностным пространством. В свою очередь, пространство альтернатив преимущественно для удобства задается в виде Y = {1,... ,q} для многоклассовой классификации (q > 2), а для случая распознавания двух классов, называемого бинарной классификацией, принимается Y = {-1,1} или Y = {0,1}.

Главным критерием качества модели распознавания является достижение минимума ошибок на всем распределении объектов классов. Если классификатор успешно распознает только объекты обучающей выборки, то он называется неспособным к обобщению, или иначе - «переобученным» (overfitting).

1.3. Общий подход к решению

В работах [40-42] сформулированы некоторые общие подходы к решению задачи машинного обучения классификации данных. Принцип минимизации эмпирического риска (empirical risk minimization) состоит в поиске функции среди некоторого семейства параметрических функций, при которой средняя ошибка распознавания на обучающем наборе, называемая эмпирическим риском, минимальна:

п

Remp(w)=-1^L(yi,f(xi)), (О)

¿=1

где L(u, v) - оценка ошибки классификатора, называемая функционалом потерь (loss function) или мерой несходства для ответа v при заданном и. В качестве данной меры могут использоваться различные оценки, но наиболее часто встречаются следующие: квадратичная

L(u,v) = (u-v)2, (1.4)

нуль-единичная, вида

L(u,v) = {0' U = V , (1.5)

11, U Ф v

кусочно-линейная (hinge loss)

L(u, v) = max(0,1 — uv), (i 6)

логистическая

L(u,v) = log(1 + e~uv). (1.7)

Получаемый таким образом классификатор не всегда сходится к лучшему решению и может оказаться неспособным к обобщению для распознавания неизвестных объектов, поскольку зависит от заданного обучающего набора (1.1).

В сформулированном позже принципе минимизации структурного риска (structural risk minimization) [41,42], предложено контролировать способность классификатора к обобщению, решая задачу поиска минимума по двум противоречивым критериям - по средней ошибке на обучающей выборке и её сложности, характеризующейся размерностью Вапника-Червоненкиса (VC-размерность, комбинаторная размерность) [42,43], В наиболее простом определении VC-размерность описывает максимальное число векторов, на которых классификатор может быть обучен без ошибок. Так, для линейных моделей VC-размерность равна d + 1, где d - размерность пространства, что, например, для двумерного пространства означает, что линейным функционалом возможно без ошибок разделить любые три точки. Контроль VC-размерности в большинстве случаев осуществляется добавлением к функционалу (1.3) регуляризирующего оператора ^(w), определяющего дополнительный критерий качества решения (гладкость функции, максимизация «отступа» («интервала уверенности»), минимум параметра функции):

п

R(w) = ^L(yiJ(xi,w))+Y^(w), Y>0- (18)

¿=i

Сама такая задача называется некорректно поставленной или плохо обусловленной (ill-posedproblem), а её решение - регуляризацией [44].

1.4. Линейные методы классификации

Наиболее хорошо изученными и разработанными являются линейные методы классификации, согласно которым обучаются линейная модель вида

f(x) = sign ^^ w(l) x(l) + b^ = sign(w • х + b), (19)

где w(1\ ..., w(d) называются весовыми коэффициентами, b - смещение или порог, а как w • х обозначено скалярное произведение векторов w и х. Иногда для удобства добавляется еще одно измерение, где х(0) = 1 и = Ь, тогда формула (1.9) записывается в более компактном виде f(x) = sign(£f=0 w(l) x(l)) = sign(w • х).

Основным преимуществом алгоритмов данной группы является устойчивость к переобучению, связанная с простотой модели. Применимость линейных методов классификации ограничена условием линейной разделимости классифицируемых объектов, что во многих случаях может быть достигнуто переходом с использованием некоторого нелинейного отображения ф: XD ^ XR к пространству вторичных признаков XR большей размерности, называемому спрямляющим (см. рис. 1). Более того, явного использования отображения можно избежать, выразив задачу обучения классификатора через функцию ядра K(u,v), вычисляющую скалярное произведение векторов и и v в спрямляющем пространстве (см. [45]):

K(u,v) = ф(и) • ф(у). (1.10)

Данная идея называется ядровым переходом («kernel trick») и впервые была сформулирована для метода опорных векторов, рассматриваемого далее, а позже обобщена и для многих других подходов.

Рисунок 1. Применение ядра скалярного произведения для нелинейного разделения классов с использованием линейных методов.

Наиболее популярными из используемых функций ядра [6], являются радиальная базисная функция (Radial Basis Function, RBF) ([46,47]) (1.11), полиномиальная (1.12) и сигмоидальная (1.13):

K(u,v) = exp(—y(u — v)2), (111)

K(u,v) = (1 + u^vy, (1.12)

K(u,v) = tanh(ku^v — S). (1.13)

Все описываемые далее линейные модели могут быть использованы с применением ядер.

1.4.1. Метод опорных векторов

Метод опорных векторов (support vector machine, SVM) предложен В.Н. Вапником в работах [40-43,45,48] как аппроксимирующая реализация принципа минимизации структурного риска, и в большинстве случаев получаемый классификатор превосходит другие по качеству классификации. В основе метода лежит идея построения оптимальной разделяющей гиперплоскости, обладающей максимальным отступом (margin) до ближайших объектов классов (см. рис. 2), в связи с чем метод также называют методом максимального отступа.

Рисунок 2. Оптимальная гиперплоскость для двух классов

Список литературы диссертационного исследования кандидат наук Дорошенко Александр Юрьевич, 2018 год

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Дорошенко, А.Ю. О методе построения разделяющей поверхности для решения задач классификации / А.Ю. Дорошенко, В.М. Довгаль, В.В. Гордиенко // Вопросы кибербезопасности, моделирования и обработки информации в современных социотехнических системах: сб. науч. тр. II Междунар. науч.-техн. конф. - Курск, 2016. - С. 135-138.

2. Довгаль, В.М. Об алгоритме построения разделяющей гиперповерхности для решения задачи классификации при линейной неразделимости классов образов / В.М. Довгаль, А.Ю. Дорошенко. // Auditorium. Электронный научный журнал Курского государственного университета. - 2016. - № 4(12). - URL: http://auditorium.kursksu.ru/pdf/012-013.pdf (дата обращения: 19.01.2018).

3. Дорошенко, А.Ю. Об одном подходе к решению проблемы переобучения классификатора / А.Ю. Дорошенко, В.М. Довгаль // Auditorium. Электронный научный журнал Курского государственного университета. 2017. - №1(13). - URL: http://auditorium.kursksu.ru/pdf/013-009.pdf (дата обращения: 19.01.2018).

4. Дорошенко, А.Ю. Способ создания форм представления исходных данных для структурного распознавания образов / А.Ю. Дорошенко, В.М. Довгаль, В.В. Гордиенко // Вопросы кибербезопасности, моделирования и обработки информации в современных социотехнических системах: сб. науч. тр. Междунар. науч.-техн. конф. - Курск, 2015. - С. 36-38.

5. Дорошенко, А.Ю. К вопросу об эффективной организации систем классификации данных [Электронный ресурс] / А.Ю. Дорошенко, В.М. Довгаль // Auditorium. Электронный научный журнал Курского государственного университета. - 2016. - № 4(12). - URL: http://auditorium.kursksu.ru/pdf/012-014.pdf (дата обращения: 19.01.2018).

6. Marshland S. Machine learning: An Algorithm Perspective / S. Marshland // Chapman and Hall/CRC. - 1st ed. - 2011. - 406 p.

7. Хайкин, С. Нейронные сети: полный курс / С. Хайкин. - Москва: Издат. дом «Вильямс», 2006. - 1104 с.

8. Shalev-Shwartz, S. Understanding Machine Learning: From Theory to Algorithms / S. Shalev-Shwartz, S. Ben-David. - 1st ed. - Cambridge University Press, 2014. - 410 p.

9. Hastie, T. The Elements of Statistical Learning. Data Mining, Inference, and Prediction / T. Hastie, R. Tibshirani, J. Friedman // Springer Series in Statistics. - 2rd ed. -2009. - 745 p.

10. Guzella, T.S. A review of machine learning approaches to Spam filtering / T.S. Guzella, W.M. Caminhas // Expert Systems with Applications. - 2009. - Vol. 36. -№ 7. - P. 10206-10222.

11. Delany, S.J. SMS spam filtering: Methods and data / S.J. Delany, M. Buckley, D. Greene // Expert Systems with Applications. - 2012. - Vol. 39. - № 10. - P. 98999908.

12. Almomani, A. A survey of phishing email filtering techniques / A. Almomani [et al.] // IEEE Communications Surveys and Tutorials. - 2013. - Vol. 15. - № 4. - P. 20702090.

13. Joachims, T. Text categorization with Support Vector Machines: Learning with many relevant features / T. Joachims // Machine Learning: ECML-98. - Springer Berlin Heidelberg, 1998. - P. 137-142.

14. Павлов, А.С. Метод обнаружения поискового спама, порожденного с помощью цепей Маркова / А.С. Павлов, Б.В. Добров // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: тр. XI Всерос. науч. конф. - 2009. - C. 311-317.

15. Perlich, C. Machine learning for targeted display advertising: Transfer learning in action / C. Perlich [et al.] // Machine Learning. - 2014. - Vol. 95. - № 1. - P. 103-127.

16. Deng, L. New types of deep neural network learning for speech recognition and related applications: an overview / L. Deng, G. Hinton, B. Kingsbury // IEEE International Conference on Acoustics, Speech and Signal Processing. - IEEE, 2013. -P. 8599-8603.

17. Plamondon, R. On-line and off-line handwriting recognition: A comprehensive survey / R. Plamondon, S.N. Srihari // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2000. - Vol. 22. - № 1. - P. 63-84.

18. Parvez, M.T. Offline arabic handwritten text recognition / M.T. Parvez, S.A. Mahmoud // ACM Computing Surveys. - 2013. - Vol. 45. - № 2. - P. 1-35.

19. Kourou, K. Machine learning applications in cancer prognosis and prediction / K. Kourou [et al.] // Computational and Structural Biotechnology Journal. - 2015. - Vol. 13.

- P. 8-17.

20. Lavecchia, A. Machine-learning approaches in drug discovery: Methods and applications / A. Lavecchia // Drug Discovery Today. - 2015. - Vol. 20. - № 3. - P. 318331.

21. Murphy, R.F. An active role for machine learning in drug development / R.F. Murphy // Nature Chemical Biology. - 2011. - Vol. 7. - № 6. - P. 327-330.

22. Gawehn, E. Deep Learning in Drug Discovery / E. Gawehn, J.A. Hiss, G. Schneider // Molecular Informatics. - 2016. - Vol. 35. - № 1. - P. 3-14.

23. Banerjee, S.P. Biometric Authentication and Identification Using Keystroke Dynamics: A Survey / S.P. Banerjee, D. Woodard // Journal of Pattern Recognition Research. - 2012. - Vol. 7. - № 1. - P. 116-139.

24. Lessmann, S. Benchmarking state-of-the-art classification algorithms for credit scoring: An update of research / S. Lessmann [et al.] // European Journal of Operational Research. - 2015. - Vol. 247. - № 1. - P. 124-136.

25. Cheng, C. A comparison of ensemble methods in financial market prediction / C. Cheng, W. Xu, J. Wang // Proceedings of the 2012 5th International Joint Conference on Computational Sciences and Optimization, CSO 2012. - IEEE, 2012. - P. 755-759.

26. Shynkevich, Y. Stock price prediction based on stock-specific and sub-industry-specific news articles / Y. Shynkevich [et al.] // International Joint Conference on Neural Networks (IJCNN). - IEEE, 2015. - P. 1-8.

27. McCallum, A. A Machine Learning Approach to Building Domain-Specific Search Engines / A. McCallum [et al.] // International Joint Conference on Artificial Intelligence.

- Stockholm, Sweden, 1999. - Vol. 16. - P. 662-667.

28. Белозеров, Б.В. Использование метода ближайших соседей при восстановлении обстановки осадконакопления / Б.В. Белозеров [et al.] // Машинное обучение и анализ данных. - 2014. - Vol. 1. - № 9. - С. 1319-1329.

29. Kanevski, M. Machine Learning Algorithms for GeoSpatial Data. Applications and Software Tools / M. Kanevski, A. Pozdnoukhov, V. Timonin // iEMSs. - Barcelona, Spain, 2008. - P. 320-327.

30. Qian, Y. Deep learning for steganalysis via convolutional neural networks / Y. Qian [et al.] // Media Watermarking, Security, and Forensics 2015 / eds. A.M. Alattar, N.D. Memon, C.D. Heitzenrater. - SPIE, 2015. - P. 94090J-94090J10.

31. Kodovsky, J. Ensemble classifiers for steganalysis of digital media / J. Kodovsky, J. Fridrich, V. Holub // IEEE Transactions on Information Forensics and Security. - 2012.

- Vol. 7. - № 2. - P. 432-444.

32. Lyu, S. Detecting hidden messages using higher-order statistics and support vector machines / S. Lyu, H. Farid // Information Hiding. - Springer Berlin Heidelberg, 2003. -Vol. 2578. - P. 340-354.

33. Mukkamala, S. Intrusion Detection Systems using Adaptive Regression Splines / S. Mukkamala [et al.] // Enterprise Informations Systems VI. - Springer-Verlag, 2005. -P. 211-218.

34. Muralidharan, R. Object Recognition Using K-Nearest Neighbor Supported By Eigen Value Generated From the Features of an Image / R. Muralidharan // International Journal of Innovative Research in Computer and Communication Engineering. - 2014. -Vol. 2. - № 8. - P. 5521-5528.

35. Ding, C. A Comprehensive Survey on Pose-Invariant Face Recognition / C. Ding, D. Tao // Transactions on Intelligent Systems and Technology. - 2015. - Vol. 7. - № 3.

- P. 1-42.

36. Goh, A.T.C. Seismic Liquefaction Potential Assessed by Neural Networks / A.T.C. Goh // Journal of Geotechnical Engineering. - 1994. - Vol. 120. - № 9. - P. 1467-1480.

37. Samui, P. Seismic liquefaction potential assessment by using Relevance Vector Machine / P. Samui // Earthquake Engineering and Engineering Vibration. - 2007. -Vol. 6. - № 4. - P. 331-336.

38. Бредихин, Р.В. Метод транспортировки текстовых сообщений в изображениях с использованием дискретных отображений / Р.В. Бредихин, В.М. Довгаль, А.Ю. Дорошенко, В.С. Фастов // Известия Юго-Западного

государственного университета. Научный рецензируемый журнал. - 2011. - № 5-1(38). - С. 58-60.

39. Довгаль, В.М. Способ стеганографии на основе дискретного отображения Хенона / В.М. Довгаль, В.В. Гордиенко, С.Ю. Гора, А.Ю. Дорошенко // Auditorium. Электронный научный журнал Курского государственного университета. - 2014. -№ 1 - Режим доступа: http://auditorium.kursksu.ru/pdf/001-009.pdf (дата обращения: 19.01.2018).

40. Вапник, В.Н. Теория распознавания образов (статистические проблемы обучения) / В.Н. Вапник, А.Я. Червоненкис. - Москва: Наука, 1974. - 416 с.

41. Vapnik, V.N. Statistical Learning Theory / V.N. Vapnik // Wiley. - 1998. - 760 p.

42. Vapnik, V.N. The Nature of Statistical Learning Theory / V.N. Vapnik // SpringerVerlag. - New York, 1995. - 314 p.

43. Вапник, В.Н. Восстановление зависимостей по эмпирическим данным / В.Н. Вапник. - Москва: Наука, 1979. - 448 с.

44. Тихонов, А.Н. Методы решения некорректных задач / А.Н. Тихонов, В.Я. Арсенин. - Москва: Наука, 1979. - 285 p.

45. Boser, B.E. A training algorithm for optimal margin classifiers / B.E. Boser, I.M. Guyon, V.N. Vapnik // Proceedings of the fifth annual workshop on Computational learning theory - COLT '92. - ACM Press, 1992. - P. 144-152.

46. Айзерман, М.А. Теоретические основы метода потенциальных функций в задаче об обучении автоматов распределению входных ситуаций на классы / М.А. Айзерман, Э.М. Браверман, Л.И. Розоноэр // Автоматика и телемеханика. - 1964. -Т. 25. - № 6. - С. 917-936.

47. Powell, M.J.D. The theory of radial basis function approximation in 1990 / M.J.D. Powell // Advances in Numerical Analysis. - Oxford: Clarendon Press, 1992. - Vol. 2. -P. 105-210.

48. Cortes, C. Support-Vector Networks / C. Cortes, V.N. Vapnik // Machine Learning. - 1995. - Vol. 20. - № 3. - P. 273-297.

49. Tipping, M.E. The relevance vector machine / M.E. Tipping // Advances in Neural Information Processing Systems 12. - 2000. - Vol. 12. - P. 652-658.

50. Bishop, C.M. Variational relevance vector machines / C.M. Bishop, M.E. Tipping // Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence. -2000. - № 1. - P. 46-53.

51. Tipping, M.E. Sparse Bayesian learning and the relevance vector machine / M.E. Tipping // The Journal of Machine Learning Research. - 2001. - Vol. 1. - P. 211244.

52. Rozenblatt, F. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms / F. Rozenblatt. - Washington: Spartan Books, 1962. - 616 p.

53. Kivinen, J. Online Learning of Linear Classifiers / J. Kivinen // Advanced Lectures on Machine Learning. - Springer Berlin Heidelberg, 2003. - P. 235-257.

54. Hoi, S.C.H. LIBOL: A Library for Online Learning Algorithms / S.C.H. Hoi, J. Wang, P. Zhao // Journal of Machine Learning Research. - 2014. - Vol. 15. - № 1. -P. 495-499.

55. Gentile, C. A New Approximate Maximal Margin Classification Algorithm / C. Gentile // The Journal of Machine Learning Research. - 2001. - Vol. 2. - P. 213-242.

56. Li, Y. The relaxed online maximum margin algorithm / Y. Li, P.M. Long // Machine Learning. - 2002. - Vol. 46. - № 1-3. - P. 361-387.

57. Crammer, K. Online Passive-Aggressive Algorithms / K. Crammer [et al.] // Journal of Machine Learning Research. - 2006. - Vol. 7. - P. 551-585.

58. Cesa-Bianchi, N. A Second-Order Perceptron Algorithm / N. Cesa-Bianchi, A. Conconi, C. Gentile // SIAM Journal on Computing. - 2005. - Vol. 34. - № 3. -P. 640-668.

59. Dredze, M. Confidence-weighted linear classification / M. Dredze, K. Crammer, F. Pereira // Proceedings of the 25th international conference on Machine learning -ICML '08. - ACM Press, 2008. - P. 264-271.

60. Wang, J. Soft Confidence-Weighted Learning / J. Wang, P. Zhao, S.C.H. Hoi // ACM Transactions on Intelligent Systems and Technology. - 2016. - Vol. 8. - № 1. -P. 1-32.

61. Rao, C. The Utilization of Multiple Measurements in Problems of Biological Classification / C. Rao // Journal of the Royal Statistical Society. Series B (Methodological). - 1948. - Vol. 10. - P. 159-203.

62. Baudat, G. Generalized Discriminant Analysis Using a Kernel Approach / G. Baudat, F. Anouar // Neural Computation. - 2000. - Vol. 12. - № 10. - P. 2385-2404.

63. Friedman, J.H. Regularized discriminant analysis / J.H. Friedman // Journal of the American Statistical Association. - 1989. - Vol. 84. - № 405. - P. 165-175.

64. Fisher, R.A. the Use of Multiple Measurements in Taxonomic Problems / R.A. Fisher // Annals of Eugenics. - 1936. - Vol. 7. - № 2. - P. 179-188.

65. Welling, M. Fisher Linear Discriminant Analysis / M. Welling // Science. - 2009. - Vol. 1. - № 2. - P. 1-3.

66. Mika, S. Fisher discriminant analysis with kernels / S. Mika [et al.] // Neural Networks for Signal Processing IX: Proceedings of the 1999 IEEE Signal Processing Society Workshop (Cat. No.98TH8468). - IEEE. - P. 41-48.

67. Cai, D. Locality sensitive discriminant analysis / D. Cai [et al.] // IJCAI International Joint Conference on Artificial Intelligence. - 2007. - P. 708-713.

68. Yan, S. Graph embedding and extensions: A general framework for dimensionality reduction / S. Yan [et al.] // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 2007. - Vol. 29. - № 1. - P. 40-51.

69. Grogan, T.R. A simulation based method for assessing the statistical significance of logistic regression models after common variable selection procedures / T.R. Grogan, D.A. Elashoff // Communications in Statistics: Simulation and Computation. - 2017. -Vol. 46. - № 9. - P. 1-14.

70. Lyles, R.H. An efficient design strategy for logistic regression using outcome- and covariate-dependent pooling of biospecimens prior to assay / R.H. Lyles [et al.] // Biometrics. - 2016. - Vol. 72. - № 3. - P. 965-975.

71. Hosmer, D.W. Applied Logistic Regression / D.W. Hosmer, S. Lemeshow, R.X. Sturdivant. - 3rd ed. - John Wiley & Sons, Inc., 2013. - 528 p.

72. Lin, C.-J. Trust region Newton methods for large-scale logistic regression /

C.-J. Lin, R.C. Weng, S.S. Keerthi // Proceedings of the 24th international conference on Machine learning - ICML '07. - ACM Press, 2007. - P. 561-568.

73. McCulloch, W.S. A logical calculus of the ideas immanent in nervous activity / W.S. McCulloch, W. Pitts // The Bulletin of Mathematical Biophysics. - 1943. - Vol. 5. - № 4. - P. 115-133.

74. Metropolis, N. Equation of State Calculations by Fast Computing Machines / N. Metropolis [et al.] // The Journal of Chemical Physics. - 1953. - Vol. 21. - № 6. -P. 1087-1092.

75. Bottou, L. Stochastic Learning / L. Bottou // Advanced Lectures on Machine Learning. - Springer Berlin Heidelberg, 2004. - P. 146-168.

76. Widrow, B. Adaptive switching circuits / B. Widrow, M. Hoff. // 1960 IRE WESCON Convention Record. - IRE, 1960. - 96-104 p.

77. Rumelhart, D.E. Learning Internal Representations by Error Propagation /

D.E. Rumelhart, G.E. Hinton, R.J. Williams // Readings in Cognitive Science: A Perspective from Psychology and Artificial Intelligence. - Elsevier, 2013. - P. 399-421.

78. LeCun, Y.A. Efficient backprop / Y.A. LeCun [et al.] // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - 2012. - Vol. 7700 LECTU. - P. 9-48.

79. Holland, J.H. Adaption in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence / J.H. Holland. -Cambridge: MIT Press, 1992. - 232 p.

80. Lecun, Y. Deep learning / Y. Lecun, Y. Bengio, G. Hinton // Nature. - 2015. -Vol. 521. - № 7553. - P. 436-444.

81. Schmidhuber, J. Deep Learning in neural networks: An overview / J. Schmidhuber // Neural Networks. - 2015. - Vol. 61. - P. 85-117.

82. Deng, L. Deep Learning: Methods and Applications / L. Deng, D. Yu // Foundations and Trends® in Signal Processing. - 2014. - Vol. 7. - № 3-4. - P. 197-387.

83. Duchi, J. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization / J. Duchi, E. Hazan, Y. Singer // Journal of Machine Learning Research. -2011. - Vol. 12. - P. 2121-2159.

84. Kingma, D.P. Adam: a Method for Stochastic Optimization / D.P. Kingma, J.L. Ba // International Conference on Learning Representations 2015. - 2015. - P. 1-15.

85. Nesterov, Y. Gradient methods for minimizing composite functions / Y. Nesterov // Mathematical Programming. - 2013. - Vol. 140. - № 1. - P. 125-161.

86. Kalteh, A.M. Review of the self-organizing map (SOM) approach in water resources: Analysis, modelling and application / A.M. Kalteh, P. Hjorth, R. Berndtsson // Environmental Modelling & Software. - 2008. - Vol. 23. - № 7. - P. 835-845.

87. Kohonen, T. Self-Organizing Maps. Vol. 30 / T. Kohonen. - 2001. - 501 p.

88. Liu, Y. A Review of Self-Organizing Map Applications in Meteorology and Oceanography / Y. Liu, R.H. Weisberg // Self Organizing Maps - Applications and Novel Algorithm Design. - 2011. - 253-272 p.

89. Barreto, G. Time series prediction with the self-organizing map: A review / G. Barreto // Perspectives of NeuralSymbolic Integration. - 2007. - P. 135-158.

90. Kohonen, T. Learning vector quantization / T. Kohonen // The Handbook of Brain Theory and Neural Networks. - MIT Press, 1995. - P. 537-540.

91. Nova, D. A review of learning vector quantization classifiers / D. Nova, P.A. Estevez // Neural Computing and Applications. - 2014. - Vol. 25. - № 3-4. -P. 511-524.

92. Powell, M.J.D. Radial basis functions for multivariable interpolation: a review / M.J.D. Powell // Algorithms for approximation. - 1987. - P. 143-167.

93. Poggio, T. Networks for Approximation and Learning / T. Poggio, F. Girosi // Proceedings of the IEEE. - 1990. - Vol. 78. - № 9. - P. 1481-1497.

94. Park, J. Universal Approximation Using Radial-Basis-Function Networks / J. Park, I.W. Sandberg // Neural Computation. - 1991. - Vol. 3. - № 2. - P. 246-257.

95. Light, W.A. Ridge functions, sigmoidal functions and neural networks / W.A. Light // Approximation Theory. - 1993. - Vol. VII. - P. 163-206.

96. Broomhead, D.S. Multivariable Functional Interpolation and Adaptive Networks / D.S. Broomhead, D. Lowe // Complex Systems. - 1988. - Vol. 2. - P. 321-355.

97. Yee, P.V. Regularized Radial Basis Function Networks: Theory and Applications to Probability Estimation, Classification and Time Series Prediction: Ph.D. Thesis / P.V. Yee. - McMaster University, Hamilton, Ontario, 1998.

98. Titterington, D.M. Statistical Analysis of Finite Mixture Distributions / D.M. Titterington, A.F.M. Smith, U.E. Makov. - New Yourk: JSTOR, 1985. - 243 p.

99. Torres-Carrasquillo, P.A. Approaches to Language Identification using Gaussian Mixture Models and Shifted Delta Cepstral Features / P.A. Torres-Carrasquillo [et al.] // International Conference on Spoken Language Processing. - 2002. - Vol. 2002. - P. 8992.

100. Torres-Carrasquillo, P.A. Language identification using Gaussian mixture model tokenization / P.A. Torres-Carrasquillo, D.A. Reynolds, J.R. Deller // IEEE International Conference on Acoustics Speech and Signal Processing. - Orlando, Fl., USA, 2002. -Vol. 1. - P. 757-760.

101. Dempster, A.P. Maximum Likelihood from Incomplete Data via the EM Algorithm / A.P. Dempster, N.M. Laird, D.B. Rubin // Journal of the Royal Statistical Society. Series B. - 1977. - Vol. 39. - № 1. - P. 1-38.

102. McLachlan, G.J. The EM Algorithm and Extensions: Second Edition / G.J. McLachlan, T. Krishnan. - John Wiley & Sons, Inc., 2007. - 369 p.

103. Kotsiantis, S.B. Bagging and boosting variants for handling classifications problems: A survey / S.B. Kotsiantis // Knowledge Engineering Review. - 2014. -Vol. 29. - № 1. - P. 78-100.

104. Wang, J.C. Bagging non-differentiable estimatiors in comples surveys / J.C. Wang, J.D. Opsomer, H. Wang // Survey Methodology. - 2014. - Vol. 40. - № 2. - P. 189-209.

105. Bühlmann, P. Boosting Algorithms: Regularization, Prediction and Model Fitting / P. Bühlmann, T. Hothorn // Statistical Science. - 2007. - Vol. 22. - № 4. - P. 477-505.

106. Appel, R. Quickly Boosting Decision Trees. Pruning Underachieving Features Early / R. Appel, T. Fuchs, P. Dollar, P. Perona // Proceedings of the 30th International Conference on Machine Learning (ICML-13). - 2013. - Vol. 28. - P. 594-602.

107. Breiman, L. Random forests / L. Breiman // Machine Learning. - 2001. - Vol. 45.

- № 1. - P. 5-32.

108. Freund, Y. Large margin classification using the perceptron algorithm / Y. Freund, R.E. Schapire // Machine Learning. - ACM Press, 1999. - Vol. 37. - P. 277-296.

109. Rokach, L. Decision Trees / L. Rokach, O. Maimon // In The Data Mining and Knowledge Discovery Handbook. Springer. - Springer-Verlag, 2005. - P. 165-192.

110. Breiman, L. Classification and Regression Trees. Vol. 19 / L. Breiman [et al.]. -Monterey: Wadsworth, Inc., 1984. - 368 p.

111. Rutkowski, L. The CART decision tree for mining data streams / L. Rutkowski [et al.] // Information Sciences. - 2014. - Vol. 266. - P. 1-15.

112. Quinlan, J. C4.5: programs for machine learning. Vol. 240 / J. Quinlan. // Morgan Kaufmann Publishers Inc. - San Francisco, 1993. - 302 p.

113. Yildiz, O.T. Parallel univariate decision trees / O.T. Yildiz, O. Dikmen // Pattern Recognition Letters. - 2007. - Vol. 28. - № 7. - P. 825-832.

114. Kass, G. V. An Exploratory Technique for Investigating Large Quantities of Categorical Data / G.V. Kass // Applied Statistics. - 1980. - Vol. 29. - № 2. - P. 119.

115. Berry, M.J.A. Data mining techniques: for marketing, sales, and customer relationship management / M.J.A. Berry, G.S. Linoff. - Wiley, 2011. - 888 p.

116. Loh, W.-Y. Split Selection Methods for Classification Trees / W.-Y. Loh, Y.-S. Shih // Statistica Sinica. - 1997. - Vol. 7. - № 4. - P. 815-840.

117. Rutkowski, L. Decision trees for mining data streams based on the mcdiarmid's bound / L. Rutkowski [et al.] // IEEE Transactions on Knowledge and Data Engineering.

- 2013. - Vol. 25. - № 6. - P. 1272-1279.

118. Bringmann, B. Pattern-based classification: a unifying perspective / B. Bringmann, S. Nijssen, A. Zimmermann // Proceedings of ECML-PKDD workshop on from local patterns to global models. - 2009. - P. 36-50.

119. Fürnkranz, J. A Brief Overview of Rule Learning / J. Fürnkranz, T. Kliegr // Rule Technologies: Foundations, Tools, and Applications / J. Fürnkranz, T. Kliegr. - Springer International Publishing, 2015. - Vol. 9202. - P. 54-69.

120. Agrawal, R. Mining association rules between sets of items in large databases / R. Agrawal, T. Imielinski, A. Swami // ACM SIGMOD Record. - ACM Press, 1993. -Vol. 22. - P. 207-216.

121. Webb, G.I. OPUS: an efficient admissible algorithm for unordered search / G.I. Webb // Journal of artificial Intelligence Research. - 1995. - Vol. 3. - P. 431-465.

122. Clark, P. Rule induction with CN2: Some recent improvements / P. Clark, R. Boswell // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Springer-Verlag, 1991. -Vol. 482. - P. 151-163.

123. Abudawood, T. Evaluation measures for multi-class subgroup discovery / T. Abudawood, P. Flach // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Springer Berlin Heidelberg, 2009. - Vol. 5781. - P. 35-50.

124. Cohen, W.W. A simple, fast, and effective rule learner / W.W. Cohen, Y. Singer // Proceedings of the National Conference on Artificial Intelligence. - 1999. - P. 335-342.

125. Ture, M. Comparing classification techniques for predicting essential hypertension / M. Ture [et al.] // Expert Systems with Applications. - 2005. - Vol. 29. - № 3. - P. 583588.

126. Kotsiantis, S.B. Supervised Machine Learning: A Review of Classification Techniques / S.B. Kotsiantis // Informatica. - 2007. - Vol. 31. - P. 249-268.

127. Аркадьев, А.Г. Обучение машины классификации объектов / А.Г. Аркадьев, Э.М. Браверман. - Москва: Наука, 1971. - 192 с.

128. Fix, E. Discriminatory Analysis. Nonparametric discrimination consistency properties / E. Fix, J.L. Hodges // International Statistical Review. - Vol. 57. - № 3. -1989. - P. 238-247.

129. Cover, T.M. Nearest Neighbor Pattern Classification / T.M. Cover, P.E. Hart // IEEE Transactions on Information Theory. - 1967. - Vol. 13. - № 1. - P. 21-27.

130. Weinberger, K.Q. Distance Metric Learning for Large Margin Nearest Neighbor Classification / K.Q. Weinberger, L.K. Saul // The Journal of Machine Learning Research. - 2009. - Vol. 10. - P. 207-244.

131. Kohavi, R. A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection / R. Kohavi // Appears in the International Joint Conference on Articial Intelligence (IJCAI). - 1995. - P. 1-7.

132. Krstajic, D. Cross-validation pitfalls when selecting and assessing regression and classification models / D. Krstajic [et al.] // Journal of Cheminformatics. - 2014. - Vol. 6. - № 1. - P. 1-15.

133. Dudani, S.A. The Distance-Weighted k-Nearest-Neighbor Rule / S.A. Dudani // IEEE Transactions on Systems, Man and Cybernetics. - 1976. - Vol. SMC-6. - № 4. -P. 325-327.

134. Parzen, E. On Estimation of a Probability Density Function and Mode / E. Parzen // The Annals of Mathematical Statistics. - 1962. - Vol. 33. - № 3. - P. 1065-1076.

135. Rish, I. An empirical study of the naive Bayes classifier / I. Rish // Empirical methods in artificial intelligence workshop, IJCAI. - Sicily, Italy, 2001. - P. 41-46.

136. Liu, B. Scalable sentiment classification for Big Data analysis using Naive Bayes Classifier / B. Liu [et al.] // 2013 IEEE International Conference on Big Data. - IEEE, 2013. - P. 99-104.

137. Дорошенко, А.Ю. О подходе к решению задачи классификации данных на основе построения разделяющей гиперповерхности / А.Ю. Дорошенко // Вестник БГТУ им. В.Г. Шухова. - 2017. - № 8. - P. 174-179.

138. Дорошенко, А.Ю. Алгоритм формирования классов для структурного распознавания образов с помощью нормального алгорифма Маркова / А.Ю. Дорошенко // Auditorium. Электронный научный журнал Курского государственного университета. - 2014. - № 4. - URL: http://auditorium.kursksu.ru/pdf/004-014.pdf (дата обращения: 19.01.2018).

139. Дорошенко, А.Ю. Об одном подходе к решению задач различения и отождествления кортежей признаков / А.Ю. Дорошенко // Auditorium. Электронный научный журнал Курского государственного университета. - 2015. -№3(7). - URL: http://auditorium.kursksu.ru/pdf/007-010.pdf (дата обращения: 19.01.2018).

140. Препарата, Ф. Вычислительная геометрия: Введение: пер. с англ. / Ф. Препарата, М. Шеймос. - Москва: Мир, 1989. - 478 с.

141. Ласло, М. Вычислительная геометрия и компьютерная графика на C++: пер. с англ. / М. Ласло. - Москва: БИНОМ, 1989. - 304 с.

142. Blum, H. A transformation for extracting new descriptors of shape / H. Blum // Symposium on Models for the Perception of Speech and Visual Form. - Cambridge, 1964. - P. 362-380.

143. Barber, C.B. The quickhull algorithm for convex hulls / C.B. Barber, D.P. Dobkin, H. Huhdanpaa // ACM Transactions on Mathematical Software. - 1996. - Vol. 22. - №2 4.

- p. 469-483.

144. Chazelle, B. An optimal convex hull algorithm in any fixed dimension / B. Chazelle // Discrete & Computational Geometry. - 1993. - Vol. 10. - № 1. - P. 377409.

145. Wang, D. Online support vector machine based on convex hull vertices selection / D. Wang [et al.] // IEEE Transactions on Neural Networks and Learning Systems. - 2013.

- Vol. 24. - № 4. - P. 593-609.

146. Ruano, A. A randomized approximation convex hull algorithm for high dimensions / A. Ruano, H.R. Khosravani, P.M. Ferreira // IFAC-PapersOnLine. - 2015. - Vol. 28. -№ 10. - P. 123-128.

147. Делоне, Б.Н. Sur la sphere vide / Б.Н. Делоне // Изв. АН СССР. - 1934. - Т. 6.

- С. 793-800.

148. Kimmel, R. Skeletonization via Distance Maps and Level Sets / R. Kimmel [et al.] // Computer Vision and Image Understanding. - 1995. - Vol. 62. - № 3. - P. 382-391.

149. Zou, J.J. A new skeletonization algorithm based on constrained Delaunay triangulation / J.J. Zou, H.H. Chang, H. Yan // ISSPA 1999 - Proceedings of the 5th International Symposium on Signal Processing and Its Applications. - Queensland Univ. Technol, 1999. - Vol. 2. - P. 927-930.

150. Buell, W.R. Mesh Generation—A Survey / W.R. Buell, B.A. Bush // Journal of Engineering for Industry. - 1973. - Vol. 95. - № 1. - P. 332-338.

151. Vollmer, J. Improved Laplacian Smoothing of Noisy Surface Meshes / J. Vollmer, R. Mencl, H. Muller // Computer Graphics Forum. - 1999. - Vol. 18. - № 3. - P. 131— 138.

152. Kobbelt, L. Interactive multi-resolution modeling on arbitrary meshes / L. Kobbelt [et al.] // Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH '98. - ACM Press, 1998. - P. 105-114.

153. Bansal, R. Outlier Detection: Applications and techniques in Data Mining / R. Bansal, N. Gaur, S.N. Singh // 2016 6th International Conference - Cloud System and Big Data Engineering (Confluence). - IEEE, 2016. - P. 373-377.

154. Singh, K. Outlier Detection: Applications And Techniques. / K. Singh, S. Upadhyaya // International Journal of Computer Science Issues. - 2012. - Vol. 9. -№ 1. - P. 307-323.

155. Захаров, А.А. Алгоритм определения пересечений полигональных объектов с использованием ориентируемых ограничивающих объемов / А.А. Захаров, С.С. Садыков // Вычислительные методы и программирование. - 2003. - Т. 4. -№ 2. - С. 195-200.

156. Cohen, J.D. I-Collide: an interactive and exact collision detection / J.D. Cohen [et al.] // Proceedings of the 1995 symposium on Interactive 3D graphics - SI3D '95. - ACM Press, 1995. - P. 189-196.

157. Bergen, G.v.d. Efficient Collision Detection of Complex Deformable Models using AABB Trees / G.v.d. Bergen // Journal of Graphics Tools. - 1997. - Vol. 2. - № 4. -P. 1-13.

158. Hall, M. The WEKA data mining software / M. Hall [et al.] // ACM SIGKDD Explorations Newsletter. - 2009. - Vol. 11. - № 1. - P. 10-18.

159. Chang, C.-C. LIBSVM: a library for support vector machines / C.-C. Chang, C.-J. Lin // ACM Transactions on Intelligent Systems and Technology. - 2011. - Vol. 2. - № 3. - P. 1-27.

160. Seidel, R. The upper bound theorem for polytopes: an easy proof of its asymptotic version / R. Seidel // Computational Geometry: Theory and Applications. - 1995. -Vol. 5. - № 2. - P. 115-116.

161. Bhargava, N. Decision Tree Analysis on J48 Algorithm for Data Mining / N. Bhargava [et al.] // International Journal of Advanced Research in Computer Science and Software Engineering. - 2013. - Vol. 3. - № 6. - P. 1114-1119.

162. Bellman, R. Dynamic Programming. Vol. 70 / R. Bellman. - 1957. - 342 p.

163. Lichman, M. UCI Machine Learning Repository / M. Lichman. - Irvine, CA: University of California, 2013. - URL: http://archive.ics.uci.edu/ml (дата обращения: 19.01.2018).

ПРИЛОЖЕНИЯ

Приложение №1 Копии документов о внедрении результатов диссертации

УТВЕРЖДАЮ Проректор по

и сследовательско й международным «Курский университет»

СПРАВКА

об использовании в учебном процессе результатов кандидатской диссертации Дорошенко Александра Юрьевича «Методы и инструментальные средства построения разделяющей гиперповерхности на основе многомерной триангуляции Делоне для решения задачи машинного обучения

классификации данных», представленной к защите по специальности 05.13.01 - Системный анализ, управление и обработка информации

Рассмотренные в диссертации средства решения отдельных проблем машинного обучения классификации данных, а именно:

- метол разделяющей гиперповерхности на основе многомерной триангуляции Делоне;

- алгоритм сглаживания разделяющей гиперповерхности, как способ решения проблемы переобучения;

- алгоритм отсева выбросов в исходной выборке;

- метод классификации с использованием ограничивающих объемов используются в учебном процессе Курского государственного университета при

изучении магистрами второго курса направления «Теория распознавания образов и анализ изображений» при прохождении производственных практик и выполнении курсовых и дипломных работ.

Заведующий кафедрой программного обеспечения и администрирования информационных систем

Е.А. Бабкин

Приложение №2 Копия свидетельства о регистрации программы для ЭВМ

Приложение №«3

Исходный код программы, реализующей предложенный подход HypersurfaceClassifier (Реализации классификатора на основе метода разделяющей гиперповерхности):

package hypersurface;

import j ava.io.IOException; import java.util.Collection; import j ava.util.Vector;

import multidimensional.LineSegment; import multidimensional.Maths; import multidimensional.Plane; import multidimensional.Point; import multidimensional.Polygon; import multidimensional.Surface; import classifiers.Abstract Classifier; import dataset.MtDataset;

import dataset.MtPattern;

/**

*

public class HypersurfaceClassifier implements AbstractClassifier {

// separated hyper plane private Surface[] mtSurfaces;

// reference to one object every classes private MtPattern[] references;

// number of using features private int numFeatures;

// number of classes to recognition private int numClasses;

// hold algorithms for smoothing and outlier analysis

private HypersurfaceClassifier modifier; /**

* constructor - initialize recognition system: build separating hyper plane

*

* @param a

* @param b

* @throws IOException */

public HypersurfaceClassifier (int numOfFeatures, int numOfClasses) { this.numFeatures = numOfFeatures; this.numClasses = numOfClasses;

this.mtSurfaces = new Surface[numOfClasses - 1];

this.references = new MtPattern[numOfClasses - 1];

this.modi fier = new HupersurfaceModi fier(numOfFeatures) ;

}

/**

* This function set parameters for hypersurface smoothing

*

* @param smoothCoef

* - ratio of smoothing

* @param smoothlterations

* - number of smoothing iterations

*/

public void addSmooth(float smoothCoef, int smoothlterations) { this.modi fier.addSmooth(smoothCoef, smoothlterations) ;

}

/**

* This function set outlier analysis parameter:

* minimum number of adjacent neighbors from non outlier point

*

* @param minNumNeighbors

* - integer value higher then С

*/

public void addOutlierAnalysis(int mi nNumNeighbors) {

this.modi fier.addOutlierAnalysi s(minNumNeighbors) ;

}

/**

* Even-odd method for classi fy some point

*

* @param what

* @return

*/

©Override

public int classify(Point what) {

for (int i = 0; i < this.mtSurfaces.length; i++) { if (this.references[i].equals(what)) {

return this.references[i].getClassName();

}

boolean isEvenResult = this.mtSurfaces[i

.isEvenNumberOflntersections(new LineSegment(what.clone(), this.references[i].clone()));

if (isEvenResult) {

return this.references[i].getClassName();

}

}

// point belongs to last class return this.numClasses - 1;

}

/**

* Reset all parameters to default

*/

©Override

public void reset(int numOfFeatures, int numOfClasses) { this.numFeatures = numOfFeatures; this.numClasses = numOfClasses;

this.mtSurfaces = new Surface[numOfClasses - 1]; this.references = new MtPattern[numOfClasses];

}

* @return all surfaces */

public Surface[] getSurfaces() { return this.mtSurfaces;

}

/**

* this general learn function for decision hypersurface classifier

*

* @param - trainingSet

* @throws IOException */

public void learn(MtDataset trainingSet) {

// find all virtual simplices Collection<Simplex> virtualSimplices; try {

virtualSimplices = this

.buildVirtualSimplices(trainingSet);

// smooth or/and outlier analysis

if (this.modi fier.apply(virtualSimplices, trainingSet) ) { this.modi fier.addOutlierAnalysis(0);

virtualSimplices = this.buildVirtualSimplices(trainingSet);

// this.smoothModi fier.apply(virtualSimplice s, trainingSet) ;

}

} catch (IOException e) {

e.printStackTrace(); return;

}

for (int considerClas sName = 0; considerClassName < this.numClasses - 1; considerClassName++) {

// parse triangles with vertices i class and another classes Vector<Simplex> considerSimplices = this

.parseConsiderVirtualSimplices(considerClassName, virtualSimplices);

if (this.references[considerClassName] == null) {

Simplex someSimplex = considerSimplices.get(0);

for (int i = 0; i < someSimplex.getNumOfVertices(); i++) {

if (someSimplex.getVertex(i) .get ClassName() == considerClassName) { this.references[considerClassName] = someSimplex .getVertex(i);

}

}

}

this.mtSurfaces[considerClassName] = this.buildSurface( considerClassName, considerSimplices);

}

System.out.println("Surfaces are build: "

+ this.mtSurfaces[0].getNumOfSegments());

}

/**

* this general function create hypersurface separates considerClassName

*

* @param simplices

* - all virtual simplices regard of considerClassName

* @return one surface */

protected Surface buildSurface(int considerClas sName, Collection<Simplex> simplices) { Surface surface = new Surface(this.numFeatures);

for (Simplex simplex : simplices) {

// find points of plane of surface segment

Point[] vertices = this.findSegmentVertices(considerClassName, simplex);

// calculate segment

Polygon segment = this.buildSegment(considerClassName, simplex, vertices);

// build segment surface.addSegment(segment);

}

return surface;

}

*

* @param considerClassName

* @param simplex

* @param vertices

* @return

*/

protected Polygon buildSegment(int considerClas sName, Simplex simplex, Point[] vertices) {

Plane plane = new Plane(this.numFeatures, vertices,

Plane.POINTS_DEFINITION);

// find all edges of surface segment

Vector<HalfSpace> edges = this.makeSegmentEdges(considerClassName, simplex);

return new Polygon(this.numFeatures, plane, edges,

Maths.average(vertices));

}

/**

* select all segment faces that contains consider class point

*

* @param considerClassName

* - separated class

* @param simplex

* - some virtual simplex

* @return Vector of HalfSpace objects

*/

protected Vector<HalfSpace> makeSegmentEdges(int considerClassName, Simplex simplex) {

Vector<HalfSpace> edges = new Vector<HalfSpace>();

Simplex[] faces = simplex.getFaces(); for (int f = 0; f < faces.length; f++) {

considerClassName;

Simplex face = faces[f] ; boolean isEdge = false; // handle all face's edges

for (int v = 1; v < face.getNumOfVertices(); v++) { MtPattern a = (MtPattern) face.getVertex(v); MtPattern b = (MtPattern) face.getVertex(v - 1);

if ((a.getClassName() == considerClassName || b.getClassName()

&& (a.getClassName() != b.getClassName())) { isEdge = true; break;

}

}

if (isEdge) {

Plane edgeBoundingPlane = new Plane(this.numFeat ures,

face.getVertices(), Plane.POINTS_DEFINITION); // inside part of segment in direct of "f" point edgeBoundingPlane.orientate(simplex.getVert ex(f), true) ; / / System.out.println(edge) ;

edges.add(new HalfSpace(edgeBoundingPlane, true));

}

}

return edges;

* function make one surface segment plane : fi nd d point s (d - number o f

* dimensions) and calculate plane

*

* @param simplex

* - some virtual simplex

* @return MtPlane object */

protected Point[] findSegmentVertices(int considerClassName, Simplex simplex) {

Point vertices[] = new Point[this.numFeatures]; int p = 0;

boolean isFirst = true;

for (int i = 0; i < simplex.getNumOfVertices(); i++) { Mt Pattern a = simplex.getVertex(i);

if (a.getClassName() != considerClassNameI continue;

for (int j = 0; j < simplex.getNumOfVertices(); j++) { if (i == j)

continue;

MtPattern b = simplex.getVertex(j);

if (a.getClassName() != b.getClassName()) { vertices[p++] = a.add(b).scale(.5f); if ( ! isFirst) break;

}

}

isFirst = false;

}

return (p > 0) ? vertices : null;

}

/**

* this function selects virtual simplices contains "considerClassName"

* point between own vertices.

*

* @param simplices

* - array of simplexes vertices indexes

* @param trainingSet

* - vertices of Delaunay triangulation

* @return - collection of dirty simplexes

*/

private Vector<Simplex> parseConsiderVirtualSimplices(

int considerClassName, Collection<Simplex> simplices) { Vector<Simplex> considerSimplices = new Vector<Simplex>();

for (Simplex simplex : simplices) {

if (simplex.containsClass(considerClassName)) { considerSimplices.add(simplex);

}

}

return considerSimplices;

}

/**

* this functions find only virtual simplices between all Delaunay

* simplices,

* and create Simplex objects

*

* @param simplices

* - array of simplices indices