Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Разработка и исследование оптимизационных алгоритмов для решения задач бинарной классификации Алхасов Станислав Сергеевич

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Алхасов Станислав Сергеевич. Разработка и исследование оптимизационных алгоритмов для решения задач бинарной классификации: диссертация ... кандидата Технических наук: 05.13.17 / Алхасов Станислав Сергеевич;[Место защиты: ФГАОУ ВО «Южный федеральный университет»], 2018.- 156 с.

Содержание к диссертации

Введение

Глава 1. Применение методов интеллектуального анализа данных для классификации объектов разнородных выборок 11

1.1. Исследование методологии и стандартов интеллектуального анализа данных 11

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

1.3. Деревья решений, их особенности и применение 29

1.4. Метод k ближайших соседей, его особенности и применение 35

1.5. Метод опорных векторов, его особенности и применение 39

1.6. Искусственные нейронные сети, их особенности и применение 44

1.7. Выводы 51

Глава 2. Исследование эффективности методов бинарной классификации для анализа разнородных данных на примере класса задач прогнозирования 54

2.1. Построение классификаторов для решения задач прогнозирования 54

2.1.1. Построение логического классификатора 54

2.1.2. Построение метрического классификатора 60

2.1.3. Построение SVM-классификатора 62

2.1.4. Построение нейросетевого классификатора 68

2.2. Разработка модифицированных критериев качества бинарной классификации для задач анализа разнородных выборок 75

2.2.1. Разработка критерия качества классификации, учитывающего длительность выполнения алгоритма 75

2.2.2. Разработка критерия качества классификации, учитывающего разбалансированность исследуемой выборки 80

2.2.3. Сравнение методов бинарной классификации с помощью модифицированных критериев качества 83

2.3. Исследование набора признаков в выборке для повышения качества бинарной классификации 91

2.3.1. Первичное преобразование набора признаков анализируемой выборки 91

2.3.2. Методы снижения числа переменных в анализируемой выборке 96

2.4. Дополнительная обработка анализируемых данных 101

2.5. Выводы 105

Глава 3. Разработка модифицированного подхода, основанного на подборе оптимального классификатора посредством генетических алгоритмов 107

3.1. Постановка задачи 108

3.2. Первоначальная настройка архитектуры генетического алгоритма 112

3.3. Повышение эффективности оптимизации посредством модификации генетического алгоритма 122

3.4. Разработка комбинированного генетического алгоритма для подбора оптимальных параметров классификаторов 129

3.5. Выводы 136

Заключение 140

Литература 142

Приложение 1. Свидетельство о государственной регистрации программы для ЭВМ 153

Приложение 2. Акты о внедрении результатов диссертационной работы 154

Введение к работе

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

К настоящему моменту существует ряд работ в области класса задач бинарной классификации объектов разнородных выборок. М.А.Х. Фаркад (Farquad), А. Родан (Rodan), Хуан Бинкуан (Huang Bingquan), Т. Вафеиадис (Vafeiadis), Хуан Йин (Huang Ying), Т. Кечади (Kechadi), А. Керамати (Keramati) и ряд других авторов выполнили большой объем работы по выявлению оптимальных реализаций всех этапов интеллектуального анализа данных от подготовки исходных данных до визуализации полученных результатов применительно к прогнозированию оттока потребителей и прочим задачам подобного типа. Вместе с тем специфика бинарной классификации в целом и данной прогностической задачи в частности такова, что каждый исследователь имеют свою собственную разновидность исследуемой задачи,

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

В последнее время делаются попытки разработать более общие подходы, позволяющие расширить применимость существующих прогностических моделей. Так в исследованиях О.Е. Бухарова и Д.П. Боголюбова предложено использовать генетические алгоритмы для отбора наиболее информативных входных признаков, далее анализируемых искусственной нейронной сетью. Совместное рассмотрение искусственных нейронных сетей и генетических алгоритмов, вообще говоря, встречается во множестве работ, однако большинство из них сфокусировано на оптимизации функционала качества обучения нейросетей посредством генетических алгоритмов для решения специфических задач классификации и регрессии, когда традиционные методы оптимизации представляются менее предпочтительными. Среди таких работ следует отметить исследования В.А. Мищенко, А.А. Коробкина, Ши Хуавана (Shi Huawang), А.А. Олейника, С.А. Субботина, Ю.В. Чернухина, М.А. Беляева, Л.М.Л. де Кампоса (Campos) и др.

В работах В.М. Курейчика, В.В. Курейчика, Д. Уитли (Whitley), Ю.Р. Цоя, В.Г. Редько, Х.М. Пандей (Pandey) и др. показано, что генетические алгоритмы являются высокоэффективными, модифицируемыми и широко применимыми оптимизационными методами, моделирующими процесс биологической эволюции посредством операторов селекции, скрещивания (крос-синговера) и мутации. При этом они являются менее узкоспециализированными по сравнению со значительным числом традиционных методов оптимизации. Также в контексте рассматриваемой прогностической задачи важно то, что генетические алгоритмы не нуждаются в дифференцируемости целевой функции. Соответственно, применимость генетических алгоритмов не ограничивается их использованием для отбора входных признаков для нейронных сетей.

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

Цель и задачи исследования. Целью исследования является разработка оптимизационного алгоритма для повышения точности бинарной класси-

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

Для достижения поставленной цели требуется решить ряд задач:

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

  1. Анализ и исследование оценок эффективности прогностической модели с учетом не только точности классификации, но и длительности работы классификатора.

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

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

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

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

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

Научная новизна работы. Научная новизна работы состоит в следующем:

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

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

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

ческого алгоритма и критериев качества бинарной классификации для однозначной оценки эффективности выполнения классификации.

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

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

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

Реализация и внедрения результатов работы. Описанная в настоящей работе концепция реализована в программном продукте «Система классификаторов для прогнозирования оттока потребителей услуг телекоммуникационного предприятия», для которого получено Свидетельство о государственной регистрации программы для ЭВМ №2016662656. Дата государственной регистрации в Реестре программ для ЭВМ – 17 ноября 2016 г.

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

Апробация работы. Основные положения и результаты работы диссертационной работы докладывались и обсуждались на российских и международных научно-технических конференциях: Всероссийской научной конференции «Системы и модели в информационную эпоху» (г. Таганрог, апрель 2014 г., СМИЭ-2014); VIII Международной научной конференции «Security of Information and Networks» (г. Сочи, 8 – 10 сентября 2015 г., SIN 2015); XXIII Научной конференции «Современные информационные технологии: тенденции и перспективы развития» (г. Ростов-на-Дону, 21 – 22 апреля 2016 г., СИТО-2016); III Международной научной конференции «Information Technologies in Science, Management, Social Sphere and Medicine» (г. Томск, май 2016 г., ITSMSSM 2016); IV Международной научной конференции «Information Technologies in Science, Management, Social Sphere and Medicine» (г. Томск, декабрь 2017 г., ITSMSSM 2017).

Публикации. По теме диссертации опубликовано 10 работ, из них 5 статей в изданиях, входящих в перечни ВАК РФ, Scopus и Web of Science. Все результаты, составляющие основное содержание диссертации, и выносимые на защиту положения получены и сформулированы диссертантом самостоятельно. Большинство работ [1–4, 6–10] опубликовано в соавторстве с научным руководителем А.Н. Целых, которому принадлежит постановка задачи и разработка концепции исследования. Часть работ имеет соавтора А.А. Целых [2–5, 9], у которого диссертант получал многочисленные консультации по интеллектуальному анализу данных.

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

Деревья решений, их особенности и применение

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

Наиболее известной реализацией дерева решений является алгоритм ЮЗ (Induction of Decision Tree), основанный на принципе «разделяй и властвуй». Алгоритм производит на каждой итерации разделение выборки (подвыборки) на две части, пока в каждой подвыборке не окажутся объекты, соответствующие одному классу [33] (рис. 1.4).

Пусть все рассматриваемые объекты лежат во множестве X. Если всем объектам соответствует один класс из Y, то создается листовая вершина. В противном случае следует найти предикат с максимальной информативностью /ЗеВ v Для нахождения предиката может быть использован один из нескольких известных критериев. Самым распространенным является критерий Джини (Gini), показывающий, сколько существует пар объектов, лежащих в одном и том же классе, которые вместе идут в ту или иную вершину. Т.е. у этих пар объектов должны совпадать метки классов и значения предикатов. Данный критерий показывает насколько часто объекты, соответствующие одному и тому же классу, объединяются. l(P,X) = #{(xi,xj): Уі=ур P{xi) = p{x])}

Также на практике может быть использован D-критерий Донского, показывающий, сколько пар объектов, лежащих в разных классах, идут в разные вершины. Иными словами, данный критерий определяет, насколько данный предикат имеет способность разделять объекты разных классов.

Помимо вышеописанных критериев широко известен также еще один критерий - энтропийный, который наиболее часто приводился в ранних описаниях алгоритма Ш3. Впоследствии был предложен критерий Джини, который в некоторых случаях оказывается эффективнее энтропийного критерия. Вместе с тем было показано, что в большинстве случаев результаты использования критерия Джини и энтропийного критерия практически не отличаются [57].

Найденный тем или иным способом предикат разделяет выборку X на две части

Х1={хєХ:р(х) = 0},

Х2={хєХ:р(х) = 1}.

Если одна из полученных подвыборок оказывается пустым множеством (Х1 = 0 или Х2=0), то создается новая листовая вершина. Метка класса в этой вершине определяется на основании того, какой класс в X преобладает. В противном случае строится новая внутренняя вершина, из которой выходят два ребра. Ребра оканчиваются дочерними вершинами, в которых описанная выше последовательность операций продолжается, пока все объекты X не окажутся в одном классе. Таким образом, представленный алгоритм имеет рекурсивный характер.

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

Недостатками ID3 можно назвать «жадность» алгоритма, поскольку ему свойственно переусложнять дерево и сильно переобучаться, низкая шумоустойчивость, чувствительность к выбору критерия информативности и составу выборки С целью устранения явления переобучения применяют несколько вариантов усечения (pruning) дерева. Предусечение (pre-pruning) является альтернативой образованию листовой вершины при X1=0 или X2=0.

Ветвление останавливается не в случае наличия пустого множества, а когда критерий информативности для всех предикатов оказывается ниже некоторого порогового значения I0. Таким образом, условие останова ветвления в некоторой вершине дерева является неравенство I(P,X) I0.

Более эффективным по сравнению с предусечением подходом является постусечение (post-pruning). В этом подходе предполагается разделение выборки на обучающую и контрольную. Обычно разбиение выборки проводят в соотношении 7:3. При постусечении в построенном ранее дереве производится замена некоторых внутренних вершин либо их дочерними вершинами (берется одна дочерняя вершина, вторая - удаляется), либо листовыми вершинами. Для этого через дерево пропускается контрольная выборка. В тех внутренних вершинах, в которые не попало ни одного контрольного объекта, происходит замена внутренней вершины на листовую. При этом метка класса присваивается на основании преобладающего класса в обучающей выборке Хв данной вершине.

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

В ряде случаев алгоритм ID3 строит дерево неоптимальной формы, начиная с корневой вершины, и усечение не позволяет повысить точность классификации. Поэтому был предложен подход, называемый заглядыванием вперед (look ahead). Суть данного метода в том, что на каждой итерации вместо определения критерия информативности строится поддерево некоторой заданной глубины для каждого предиката. В рассматриваемую вершину помещается тот предикат, который обеспечивает наилучший уровень классификации. Недостатком данного подхода является длительность его выполнения. Но вместе с тем метод обеспечивает построение более точных и простых деревьев [58].

Построение логического классификатора

Логическому классификатору, построенному на основе дерева решений ID3 свойственно расти вглубь для достижения наивысшего уровня классификации на тренировочной выборке. Такая стратегия в случае малого количества обучающих объектов или зашумленности данных может приводить к переобучению прогностической модели. Для того чтобы избежать переобучения обычно предлагаются два основных подхода. Первый – остановка роста дерева до достижения идеального разделения обучающей выборки. Второй подход – пост-усечение, лежащее в основе алгоритма C4.5. Пост-усечение является более эффективным способом предотвращения переобучения [66].

Была поставлена задача изучить влияние ограничения максимальной глубины d дерева C4.5 на качество классификации. Был рассмотрен диапазон глубины d = 1…750 с шагом 20 (рис. 2.1). В качестве анализируемых признаков были взяты переменные, приведенные к диапазону [0; 1] по методу minmax-нормализации. Кроме того, известно [67], что в случае логических методов классификации, к которым относятся деревья решений, приведение данных к нормализованному виду не существенно.

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

Достаточно стабильный уровень всех метрик в широком диапазоне d от 50 до 750, а также близость соответствующим значениям метрик для дерева неограниченной глубины свидетельствует о том, что значение глубины дерева в условиях данной задачи примерно равно 50. Поэтому был проведен идентичный эксперимент в диапазоне значений глубины [1; 50] с шагом, равным единице.

Из рис. 2.2, уточняющего предыдущий график, можно более точно сделать вывод о примерном значении реальной глубины дерева, приблизительно равной 20. Уменьшение этой глубины приводит к противоположным последствиям для полноты и точности (precision), а также правильности (accuracy). Точность (precision) на интервале глубины [2; 15] существенно превосходит точность (precision), достигаемую деревом неограниченной глубины. При d = 6 точность (precision) максимальна и равна 88,22%, что более чем на 20% выше значения той же метрики для дерева неограниченной глубины (см. табл. 2.1). Более высокие значения также наблюдается в этом диапазоне глубины и для доли верных распознаваний (accuracy).

Напротив, для полноты, являющейся наиболее важной метрикой по условиям задачи, наблюдается падение значений. Максимум, достигнутый при величине максимальной глубины, равной 33, близок значению полноты дерева неограниченной глубины, которое реально имеет глубину, равную примерно 20. Таким образом, этот максимум является только лишь выбросом и не несет смысла. Отсюда, можно сделать вывод, что в контексте данной задачи предпочтительнее использовать дерево неограниченной глубины. Ограничение глубины в диапазоне [4; 15] имеет смысл только в случае, если основными метрикой является доля верных распознаваний (accuracy), точность (precision) или F-мера.

Из графика, представленного на рис. 2.3 следует, что ограничение минимального числа объектов в терминальных вершинах имеет смысл в том случае, если ключевой метрикой качества классификации является точность (precision). Максимум точности (precision) достигается при минимальном числе объектов, равном шести. Это соответствует приблизительно 89%. Напротив, полнота в этом случае принимает более низкие значения, чем при отсутствии ограничения на число объектов в листовой вершине. Отсюда можно сделать вывод, что в условиях задачи прогнозирования оттока потребителей не имеет смысла ограничивать минимальное число объектов в листовых вершинах.

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

Из рис.2.4 следует, что ограничение максимального числа листовых вершин вплоть до семи дает выигрыш в росте качества классификации в случае оценивания его метрикой точности (precision). Однако в условиях прогнозирования оттока потребителей, когда ключевой метрикой является полнота, варьирование максимального числа листов преимуществ не дает. Напротив, при значениях 22 и менее наблюдается падение значений полноты. Таким образом, в рассматриваемой ситуации ограничивать число терминальных вершин не следует.

Сравнение методов бинарной классификации с помощью модифицированных критериев качества

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

полнота //;

взвешенная полнота // = kju;

оценка полноты и длительности (ОПД) со = /(//, t);

оценка взвешенной полноты и длительности (ОВПД) со = f(ju , г1).

В табл. 2.7 представлены значения этих метрик применительно к четырем анализируемым методам бинарной классификации с параметрами, оптимальными в рамках данной задачи при пороговых значениях полноты и времени, равных //0 = 80% и t0 =100 с соответственно.

Из табл. 2.7 видно, что показывающие высокие значения полноты методы решающих деревьев (70,77%), нейронных сетей (72,69%) и опорных векторов (85,09%) существенно различаются по структуре выходных данных. Дерево решений и ИНС имеют малое число ложноположительных распознаваний, допустимость наличия которых заложена самой формулой этой метрики (1.1). Однако слишком большая доля таких распознаваний приводит к константной классификации, что лишает ее какого-либо практического смысла. Этот недостаток решается только формулированием более совершенной, обобщенной метрики качества классификации. Наличие единственной усовершенствованной метрики важно в случае автоматизации анализа качества классификации в прогностической системе, содержащей набор разных классификаторов.

Аналогичное свойство можно отметить и в случае метода k ближайших соседей. Классификация по одному ближайшему соседу вопреки более высокому значению полноты действительно оказывается менее предпочтительной, как и было отмечено в разделе 1.4. На рис. 2.15 в качестве примера совместно приведены четыре рассматриваемые метрики, характеризующие качество бинарной классификации методом kNN с нечетным числом ближайших соседей в диапазоне [1; 11].

Ранее в разделе 2.1.3 были рассмотрена возможность построения прогностической модели на основе метода опорных векторов (SVM). Был сделан вывод о недостаточности использования полноты в случае автоматизированного полного перебора всех комбинаций параметров классификатора. В качестве наилучшего результата в предыдущих экспериментах был выбран SVM-классификатор с полиномиальным ядром (p = 3), регуляризационной константой C = 100 и коэффициентом у = 100, имеющий полноту 85,00%, долю верных распознаваний (accuracy) 39,88% и точность (precision) 18,05%.

Располагая модифицированными метриками качества классификации, можно заново провести полный перебор параметров (см. табл. 2.4) SVM-классификатора. Методика проведения эксперимента остается неизменной за исключением того, что оптимизирующим критерием при полном переборе в данном случае является взвешенная полнота jJ.

Полученные результаты кардинально отличаются от приведенных в табл. 2.4. Наилучшим вариантом в табл. 2.8 следует признать №5 не только потому, что взвешенная полнота здесь максимальна (41,72%), но и потому что взвешивающий коэффициент к = JU/ju здесь принимает очевидным образом наибольшее значение, что позволяет считать полученное разделение на два класса наиболее качественным. Правильность (accuracy) здесь равна 89,64%, что является основанием подозревать полученный классификатор в вырожденности (в том, что все объекты распознаны как относящиеся к классу «-1»), поскольку полученное значение близко к величине доли объектов класса «-1» (лояльных потребителей) в обучающей выборке. Тем не менее, несмотря на высокую правильность (accuracy), классификатор не является вырожденным, поскольку имеет высокую полноту (47,52%), тогда как это возможно в случае примерно половины истинно положительных распознаваний, что невозможно при константном классе «-1». Отсюда следует, что классификатор верно распознает лишь половину нелояльных потребителей (класс «1»), но при доле таких потребителей, равной менее 15%, такую классификацию следует считать умеренно эффективной. Параметр C при полном переборе варьировался в логарифмическом масштабе. Коэффициент рассматривался с шагом 20. Поэтому для более точного определения оптимального вида SVM-классификатора следует провести более точную оценку качества классификации при ограниченном наборе параметров: ядро – радиальное базисное (RBF), C = 100…1000, = 80…160.

Для уточнения оптимальных значений C и был снова произведен полный перебор классификаторов SVM-RBF с параметрами C = 100…1000, = 80…160. Был учтен приближенный характер границ данных параметров (в случае регулиризующей константы учитывался порядок числа, а не его мантисса), в результате чего диапазоны C и были сужены до интервалов 50…70 и 130…160 соответственно. Проведенный полный перебор не дает возможности наглядно оценить наблюдаемые при изменении C и тенденции, поэтому построены графики (рис. 2.16–2.17) для оценки влияния данных параметров на качество классификации.

Из рис. 2.16 следует, что точность (precision) с ростом константы С падает, тогда как полнота растет. При этом видно, что взвешенная полнота достигает максимуму при С = 55, после чего убывает, в отличие от полноты. В сочетании с нисходящим трендом правильности (accuracy) это свидетельствует о усилении тенденции подгонки выходных значений под класс «1», что впоследствии приведет к вырождению классификатора в константый. Таким образом, можно порекомендовать использовать значение константы, равное С = 55.

Первоначальная настройка архитектуры генетического алгоритма

В предыдущем разделе были упомянуты основные функции, применяемые для тестирования сходимости генетических алгоритмов и ряда иных методов оптимизации. Самый известный набор таких функций носит название набора де Йонга (De Jong), который впервые был предложен в диссертации К. де Йонга [86]. Однако позже сам де Йонг стал противником активного применения данного набора тестовых функций при определении параметров генетических алгоритмов в связи с тем, что точное подстраивание алгоритма под эти отдельно взятые функции может не отражать всей специфики функции приспособленности (fitness function), которую должен быть способен оптимизировать разрабатываемый генетический алгоритм. Случай точного настраивания алгоритма оказывается аналогичным ситуации переобучения (overfitting) алгоритмов классификации и регрессии. Поэтому, исходя из вышесказанного, можно предложить предварительное оценивание оптимизирующей способности разрабатываемого генетического алгоритма, возможности преодоления локальных экстремумов и плато. Для этих целей из современного набора тестовых функций [81, 87] были специально отобраны ниже представленные функции, используемые для решения задач минимизации.

Однако оптимизация прогностической системы предполагает противоположное, потому что желательным является наиболее высокое значение метрики качества классификации. Поэтому тестовую функцию следует преобразовать к решению задачи максимизации. В случае использования турнирной селекции для преобразования достаточно формулы tp(xt) = -f(xt)

Если же используется стохастическая однородная или пропорциональная селекция, то к следует прибавить достаточно большое положительное число [88].

В качестве первой, самой простой тестовой функции следует рассмотреть сферическую функцию (sphere function), имеющую один минимум в точке /(0; 0;...; 0) = 0 и называемую в случае двух независимых переменных параболоидом вращения (рис. 3.3). Для решения подобного рода задач она впервые была предложена И. Рохенбергом. В наборе де Йонга для нее, как и для некоторых иных тестовых функций, наложено стандартное ограничение области определения [-5,12; 5,12] для всех независимых переменных.

После сферической функции, очевидным образом имеющей один экстремум, следует рассмотреть более сложные тестовые функции. Самой известной и часто используемой тестовой функцией с множеством локальных экстремумов является функция Растригина. Она была предложена Л.А. Растригиным как функция двух независимых переменных и впоследствии обобщена Х. Мюленбайном (Muhlenbein), М. Шомишем (Schomisch) и И. Борном (Born). Эта функция является невыпуклой нелинейной мультимодальной, имеет большое число равномерно распределенных локальных минимумов и один глобальный минимум /(0;0;...;0) = 0 (рис. 3.4).

В общем случае, если каждая особь хг популяции содержит к генов (параметров), функция принимает вид

Последняя из рассматриваемых тестовых функций - функция Розенброка (рис. 3.6) - используется для тестирования минимизационных задач. Ее характерная особенность - протяженный овраг в области минимума. Между двумя «крыльями» графика находится плато, которое препятствует достижению глобального минимума, расположенного в точке на одной стороне графика функции, тогда как преждевременная сходимость часто происходит на другой стороне. Для случая у независимых переменных функция описывается формулой

Описанные выше тестовые функции были использованы для тестирования разрабатываемого генетического алгоритма. Операторы мутации и кроссинговера являются неотъемлемой частью большинства разработанных генетических алгоритмов. Таким образом, генетический алгоритм в процессе своей работы реализует две стратегии, каждая из которых более предпочтительна для одних тестовых функций и, напротив, менее предпочтительна для других. Эти стратегии – исследование и использование (exploration and exploitation). Исследование базируется на операторе мутации и позволяет находить ранее неизвестные участки пространства поиска. Использование основывается на операторе скрещивания и позволяет улучшать ранее полученные результаты. Таким образом, в процессе мутаций преодолеваются локальные экстремумы, тогда как кроссинговер помогает достичь «дна» глобального экстремума с высокой точностью [82]. С целью учесть обе эти тенденции в разрабатываемом генетическом алгоритме в первом приближении использованы высокие значения вероятностей скрещивания и мутации [92–95].

Из вышесказанного можно предположить, что в случае функции Розенброка высокая вероятность кроссинговера особей в популяции может стать причиной «застревания» алгоритма на плато, тогда как в случае функций Растригина и Экли повышенная склонность особей к мутированию может привести к невозможности за конечное число итерации достичь глобального оптимума при заданном уровне точности. Соответственно требуется промежуточный вариант архитектуры генетического алгоритма, который будет учитывать все основные возможные характеристики оптимизируемой функции [96].

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

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