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

• Алхасов, Станислав Сергеевич
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Алхасов, Станислав Сергеевич

Содержание

Введение

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

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

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

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

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

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

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

1.7. Выводы

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

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

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

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

2.1.3. Построение БУМ-классификатора

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

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

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

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

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

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

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

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

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

2.5. Выводы

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

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

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

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

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

3.5. Выводы

Заключение

Литература

Приложение 1

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

Приложение 2

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

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

Введение

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

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

в высококонкурентных сферах телекоммуникаций, банкинга и страхования.

4

На примере вышеуказанной прикладной проблемы анализа данных выполнены исследования в настоящей диссертационной работе.

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

В последнее время делаются попытки разработать более общие

подходы, позволяющие расширить применимость существующих

прогностических моделей. Так в исследованиях О.Е. Бухарова и Д.П.

Боголюбова предложено использовать генетические алгоритмы для отбора

наиболее информативных входных признаков, далее анализируемых

искусственной нейронной сетью [7]. Совместное рассмотрение искусственных

нейронных сетей и генетических алгоритмов, вообще говоря, встречается во

множестве работ, однако большинство из них сфокусировано на оптимизации

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

алгоритмов для решения специфических задач классификации и регрессии,

когда традиционные методы оптимизации представляются менее

предпочтительными. Среди таких работ следует отметить исследования В.А. Мищенко, А.А. Коробкина, Ши Хуавана (Shi Huawang), А.А. Олейника, С.А. Субботина, Ю.В. Чернухина, М.А. Беляева, Л.М.Л. де Кампоса (Campos) и др. [8-14].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая значимость. Практически значимыми являются

разработанные критерии качества бинарной классификации, новая

комбинированная реализация генетического алгоритма на основе островной

модели и модели эволюции катастроф Г. де Фриза для решения

8

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

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

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

Апробация работы. Основные положения и результаты работы диссертационной работы докладывались и обсуждались на российских и международных научно-технических конференциях [23-32]:

• Всероссийской научной конференции «Системы и модели в информационную эпоху» (г. Таганрог, апрель 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).

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

Область исследования. Диссертационная работа соответствует пунктам 5 и 13 паспорта научной специальности 05.13.17 - Теоретические основы информатики.

П.5. Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях, разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений.

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

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

1. Разработанные новые критерии качества бинарной классификации -взвешенная полнота, оценка взвешенной полноты и длительности.

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

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

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

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

данных

Методы интеллектуального анализа данных позволяют решать разнообразные задачи аналитического характера во множестве отраслей, таких как телекоммуникации, Интернет-технологии, банкинг, торговля, страхование, медицина, промышленность. На сегодняшний день внедрение технологий Data Mining является одним из важнейших условий развития высокотехнологических отраслей экономики. Среди основных задач интеллектуального анализа данных в области телекоммуникаций, банковского и страхового бизнеса является прогнозирование оттока потребителей, необходимое для построения маркетинговых стратегий по удержанию потребителей.

Интеллектуальный анализ данных возник как научная отрасль в 1990-е гг. Родоначальником этого направления считается американский ученый Г.И. Пятецкий-Шапиро (G. Piatetsky-Shapiro). Прежде методы классификации, регрессии, кластеризации рассматривались в рамках прикладной статистики, однако с развитием информационных технологий, прежде всего технологий сбора и хранения данных, возникла потребность в выработке единой концепции, отражающей реальные потребности выявления скрытых, нетривиальных закономерностей из массивов данных, содержащих информацию о большом числе признаков объектов и имеющих пропуски и выбросы [33].

Методы интеллектуального анализа данных делятся на пять больших групп:

• классификация - определение класса (дискретная величина) объекта по его характеристикам.

• регрессия - определение некоторой характеристики (непрерывная величина) объекта по другим его характеристикам.

• кластеризация - разбиение объектов на некоторое число групп (кластеров).

• поиск ассоциативных правил - нахождение частых зависимостей между объектами и представление их в виде правил.

• поиск аномалий - обнаружение в выборке объектов, которые не похожи на большинство объектов.

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

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

В 2000-х гг. был разработан Межотраслевой стандарт решения задач интеллектуального анализа данных (CRISP-DM, CRoss Industry Standard Process for Data Mining) [34], который состоит из шести основных компонентов:

1. Понимание предметной области (Business Understanding);

2. Понимание данных (Data Understanding);

3. Предобработка данных (Data Preparation);

4. Построение модели (Modeling);

5. Оценка (Evaluation);

6. Внедрение в производственные процессы (Deployment).

12

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

На второй стадии исследователь должен изучить структуру данных, оценить качество данных, в первом приближении постараться выделить характерные подмножества в выгруженном наборе данных. Если данные получены из нескольких источников, то следует разработать подход по их интеграции в единый массив. В простейшем случае эта операция выполняется по идентификатору каждой записи (каждого объекта, каждого анализируемого потребителя в случае задачи прогнозирования оттока [1, 3, 35, 36], кредитного скоринга [37-39] и т.д.). Для ключевых признаков рассматриваемых объектов следует провести простой статистический анализ и выявить характерные распределения параметров. Обычно желательным является распределение, близкое нормальному.

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

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

распределение, которое впоследствии используется для заполнения имеющихся пропусков.

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

^Х 25 ~ Х75 ~ Х25^); Х 75 ^ 1,5( Х75 _ Х25

где х25 и х75 - первый и третий квартили соответственно.

Полученный после удаления/замены пропусков и выбросов массив данных далее обычно следует нормировать. Это важно в случае построения моделей, основанных на метрических и линейных классификаторах, а также искусственных нейронных сетях. Существует два основных подхода, которые, как правило, обеспечивают сходный уровень качества классификации [40]: • minmax-нормализация

* X - Ш1П Х

* 11 1 Х* - 1

• 7-нормализация

1]

шах х - шт х.

* Х1] М-х* = —-

1

где м - среднее арифметическое для значений признака I, - среднее арифметическое для значений признака ¡.

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

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

применять методы понижения размерности данных, среди которых наиболее известен метод главных компонент [25].

Четвертый этап стандарта CRISP-DM - моделирование. Он предполагает выбор методики моделирования и решение нескольких взаимосвязанных дополнительных задач. На этом этапе для получения результата, близкого к оптимальному, следует выполнить два условия. Первое из них - определить способ разделения исходного массива данных на обучающую и тестовую выборки. Второе условие - обоснованный подбор метода (или группы методов) интеллектуального анализа данных, наилучшим образом подходящего для конкретной задачи. Выбор метода часто является нетривиальной задачей, часто имеются лишь эмпирические рекомендации. В настоящей диссертационной работе подбор метода предлагается осуществлять с использованием кластерного анализа и генетических алгоритмов.

Этап оценки в стандарте CRISP-DM предполагает, прежде всего, подбор метрики оценки качества связан с пониманием предметной области и может существенно варьироваться в зависимости от конкретных особенностей поставленной перед аналитиком задачи. Наиболее часто используемые метрики оценки качества будут рассмотрены далее в настоящей работе.

Последний (шестой) этап CRISP-DM - внедрение в производственную

деятельности, в частности, в виде интеллектуальных систем управления

взаимоотношениями с клиентами (Customer Relationship Management, CRM-

системы) в случае решения различных задач прогнозирования оттока

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

бинарной классификации клиентов [1, 41-48]. Важное место здесь

принадлежит применению различных методов визуализации полученных

результатов. В случае если размерность представляемых данных выше

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

многомерных данных, как лица Чернова (Chernoff faces), параллельные

координаты, график Эндрюса (Andrews plot). Третий подход представляет

15

наибольший интерес, поскольку позволяет наглядно для конечного пользователя показать точку х = {х^ х2;...; в многомерном пространстве в виде кривой, заданной рядом Фурье [49, 50].

Х-1

fx{t) = —f= + х2 sin t + х3 cost + х4 sin21 + x5 cos2t + x6 sin3¿ +... V 2

Наиболее очевидной характеристикой оценки качества классификации является отношение числа правильных ответов T к общему числу ответов (T + F), где F - число неправильных ответов, называемое в англоязычной литературе как accuracy (В настоящей работе этот термин переведен как правильность, тогда как точностью [precision] называется другая, обычно более важная характеристика) [51].

Accuracy = —T— T+ F

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

Самым известным примером, показывающим несовершенство данного критерия качества, является задача медицинской диагностики. Пусть имеется 950 здоровых пациентов (класс «-1») и 50 больных (класс «1»). Даже если классификатором оказывается константа, всегда равная нулю (класс «-1»), правильность (accuracy) будет очень высокой (95%). Иными словами, в данном случае ни один больной пациент из 50 верно не диагностирован, при том, что правильность (accuracy) равна 95% [34]. В задаче прогнозирования оттока клиентов наблюдается та же самая ситуация, когда верное распознавание объектов минорного класса гораздо важнее верного распознавания объектов более многочисленного класса.

Более формально правильность (accuracy) может быть представлена как

1 1

Accuracy = - ^ \a ( xt ) = y ],

l i=i

где l - общее число объектов в выборке, y - вектор-строка целевых значений объектов,

a ( x ) - вектор-строка предсказанных классификатором значений объектов,

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

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

• верные срабатывания (TP, т.е. true positive);

• ложные срабатывания (FP, т.е. false positive);

• ложные пропуски (FN, т.е. false negative);

• верные пропуски (TN, т.е. true negative).

Эти четыре типа значений образуют матрицу ошибок (confusion matrix).

y = 1 y = 0

a ( x ) = 1 f TP FP ^ a ( x ) = 0 [ FN TN,

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

Точность (precision) - метрика качества, показывающая, какая доля объектов выделенных классификатором как положительные, действительно является положительными.

Precision = —TP— TP+ FP

Полнота (recall) - метрика качества, которая показывает, какая часть

положительных объектов выделена классификатором.

17

TP

Recall =--(1.1)

TP+ FN

Точность (precision) и полнота характеризуют разные стороны классификации. Чем выше точность (precision), тем меньше ложных срабатываний (FP). Чем выше полнота, тем меньше ложных пропусков (FN). Приоритет той или иной метрики зависит от специфики решаемой задачи. К.В. Воронцов в [34] приводит следующие примеры.

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

Пример 2. Поиск вражеских самолетов для автоматического уничтожения системами ПВО. Здесь важнее точность (precision), потому что нельзя допустить уничтожения собственных самолетов.

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

Простейший вариант - арифметическое среднее - обычно не считается лучшим способом обобщения метрик.

Average = 1 (Precision + Recall)

Другой способ обобщения - минимум.

Minimum = min (Precision, Recall)

Наиболее распространенной обобщающей метрикой является гармоническое среднее, или F-мера (F-measure), также известная как мера Ван Ризбергена, которая представляет собой, по сути, сглаженный минимум.

Precision • Recall

F = 2 •■

Precision + Recall

F-мера задает равный приоритет для точности (precision) и полноты. Она

Заключение диссертации по теме «Теоретические основы информатики», Алхасов, Станислав Сергеевич

Заключение

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

В ходе выполнения данной работы получены следующие основные результаты и сделаны определенные выводы:

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

2. Разработаны новые критерии качества бинарной классификации -взвешенная полнота и оценка взвешенной полноты и длительности (ОВПД). Первая (статическая) из них служит в качестве оценки влияния числа ложных распознаваний минорного класса (нелояльных потребителей в случае прогнозирования оттока) и общей разбалансированности анализируемой выборки. Вторая (динамическая) учитывает время выполнения вычислений с использованием того или иного классификатора.

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

4. Разработан комбинированный генетический алгоритм, сочетающий

катастрофическую и островную модели со специализацией генетических

140

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

5. В качестве результата использования разработанного генетического алгоритма, построенного на основе островной модели со специализацией островов и модели эволюции катастроф, получен набор параметров классификатора и анализируемых данных, соответствующих наиболее высокому качеству прогнозирования. Таким образом, архитектура классификатора в случае анализа лояльности потребителей телекоммуникационных услуг оказывается следующей: искусственная нейронная сеть обратного распространения ошибки с 28 и 16 нейронами в скрытых слоях, гиперболическим тангенсом в качестве активационной функции, скоростью обучения и импульсом, равными 0,79 и 0,002 соответственно. Данные при этом нормализуются по формуле шттах-нормализации и перемешиваются. Число блоков перекрестной проверки (кросс-валидации) устанавливается равным шести. Также выявляется оптимальное сочетание анализируемых признаков, количество которых ограничивается девятью.

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

Литература

1. Farquad M.A.H., Ravi V., Bapi Raju S. Churn prediction using comprehensible support vector machine: An analytical CRM application // Applied Soft Computing. - № 19. - 2014. - P. 31-40.

2. Rodan A., Fayyoumi A., Faris H., Alsakran J., Al-Kadi O. Negative Correlation Learning for Customer Churn Prediction: A Comparison Study // The Scientific World Journal. - Volume 2015. - 2015. - P. 1-7.

3. Huang B., Kechadi M.T., Buckley B. Customer churn prediction in telecommunications // Expert Systems with Applications. - № 39. - 2012. -P. 1414-1425.

4. Vafeiadis T., Diamantaras K.I., Sarigiannidis G., Chatzisavvas K.Ch. A comparison of machine learning techniques for customer churn prediction // Simulation Modelling Practice and Theory. - № 55. - 2015. - P. 1-9.

5. Huang Y., Kechadi T. An effective hybrid learning system for telecommunication churn prediction // Expert Systems with Applications. -№ 40. - 2013. - P. 5635-5647.

6. Keramati A., Jafari-Marandi R., Aliannejadi M., Ahmadian I., Mozaffari M., Abbasi U. Improved churn prediction in telecommunication industry using data mining techniques // Applied Soft Computing. - № 24. - 2014. - P. 9941012.

7. Bukharov O.E., Bogolyubov D.P. Development of a decision support system based on neural networks and a genetic algorithm // Expert Systems with Applications. - № 42. - 2015. - P. 6177-6183.

8. Мищенко В.А., Коробкин А.А. Использование генетических алгоритмов в обучении нейронных сетей // Современные проблемы науки и образования. - № 6. - 2011. - С. 116-119.

9. Shi H. Evolving Artificial Neural Networks Using GA and Momentum // 2nd International Symposium on Electronic Commerce and Security. - 2009. - P. 475-478.

10.Oliinyk A.A., Subbotin S.A. Neural network synthesis based on evolutionary optimization // Системш доошження та шформацшш технологи. - № 1. -2015. - P. 77-86.

11.Чернухин Ю.В., Беляев М.А. Особенности использования генетических алгоритмов при обучении перцептронов // Известия ТРТУ. - № 4 (22). -2001. - С. 134-140.

12.Божич В.И., Гладков Л.А., Курейчик В.М., Шницер Ю.Л. Разработка системных принципов построения эволюционных инструментальных средств формирования и обучения нейронных сетей // Известия ТРТУ. -№ 4 (22). - 2001. - С. 182-186.

13.Campos L.M.L. de, Oliveira R.C.L. de, Roisenberg M. Optimization of neural networks through grammatical evolution and a genetic algorithm // Expert Systems with Applications. - № 56. - 2016. - P. 368-384.

14.Хритоненко Д.И., Семенкин Е.С. Применение самонастраивающегося алгоритма генетического программирования для решения задач классификации // Актуальные проблемы авиации и космонавтики. - № 8, том 1. - 2012. - С. 322-323.

15.Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. - М.: ФИЗМАТЛИТ, 2012. - 260 с.

16. Бионические информационные системы и их практические применения / Под ред. Л.А. Зинченко, В.М. Курейчика, В.Г. Редько. - М.: ФИЗМАТЛИТ, 2011. - 288 с.

17.Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. - 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

18.Научная сессия МИФИ-2007. IX Всероссийская научно-техническая конференция «Нейроинформатика-2007»: Лекции по нейроинформатике. Часть 2. - М.: МИФИ, 2007. - 148 с.

19.Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы / Пер. с польск. - М.: Горячая линия - Телеком, 2006. - 452 с.

20.Whitley D. A genetic algorithm tutorial // Statistics and Computing. - Volume 4, Issue 2. - 1994. - P. 65-85.

21.Pandey H.M., Chaudhary A., Mehrotra D. A comparative review of approaches to premature convergence in GA // Applied Soft Computing. - №2 24. - 2014. - P. 1047-1077.

22.Алхасов С.С., Целых А.Н., Целых А.А. Свидетельство о государственной регистрации программы для ЭВМ №2016662656 от 17 ноября 2016 г. «Система классификаторов для прогнозирования оттока потребителей услуг телекоммуникационного предприятия».

23.Alkhasov S.S., Tselykh A.N., Tselykh A.A. An Integrated ANN-GA Approach to Data Classification // Proceedings of the 2016 Conference on Information Technologies in Science, Management, Social Sphere and Medicine (ITSMSSM 2016). - 2016. - P. 172-176.

24.Алхасов С.С., Целых А.Н. Принципы построения прогностической системы для моделирования оттока клиентов // Материалы Всероссийской научной конференции «Системы и модели в информационную эпоху». Часть 1. - Таганрог: Изд-во ТТИ ЮФУ, 2014. - С. 4-6.

25.Алхасов С.С., Целых А.Н. Основные подходы к построению информационной системы для моделирования оттока клиентов услуг связи // Известия ЮФУ. Технические науки. - № 2 (163). - 2015. - С. 106-115.

26.Алхасов С.С., Целых А.Н., Целых А.А. Классификация на основе модифицированной структуры искусственных нейронных сетей посредством генетических алгоритмов // Известия ЮФУ. Технические науки. - № 10 (183). - 2016. - С. 111-121.

27.Алхасов С.С., Целых А.Н., Попкова Е.А. Решение задач классификации с использованием MATLAB и Microsoft Azure // Современные информационные технологии и: тенденции и перспективы развития: Материалы XXIII научной конференции (Южный федеральный университет). - Ростов н/Д.: Изд-во ЮФУ, 2016. - С. 38-43.

28.Алхасов С.С., Целых А.Н., Целых А.А. Применение генетических алгоритмов со стохастической функцией приспособленности для оптимизации структуры нейронных сетей // Современные информационные технологии и: тенденции и перспективы развития: Материалы XXIII научной конференции (Южный федеральный университет). - Ростов н/Д.: Изд-во ЮФУ, 2016. - С. 44-46.

29.Алхасов С.С., Целых А.Н. Построение генетического алгоритма для использования в нейросетевом классификаторе // Современные информационные технологии и: тенденции и перспективы развития: Материалы XXIII научной конференции (Южный федеральный университет). - Ростов н/Д.: Изд-во ЮФУ, 2016. - С. 35-37.

30.Алхасов С.С., Целых А.Н. Основные элементы блока предварительной обработки результатов измерений в прикладных задачах анализа данных // Альманах современной науки и образования. - № 3 (105). - 2016. - С. 11-13.

31.Alkhasov S.S., Tselykh A.N., Tselykh A.A. Application of cluster analysis for the assessment of the share of fraud victims among bank card holders // Proceedings of the 8th International Conference on Security of Information and Networks (September 08-10, 2015, Sochi, Russia). - 2015. - P. 103-106.

32.Alkhasov S.S., Tselykh A.A. Combined Optimization and Modified Performance Metrics for Automated Model and Parameter Selection in Telecom Customer Churn Prediction // Proceedings of the IV Conference on Information Technologies in Science, Management, Social Sphere and Medicine (ITSMSSM 2017). - 2017. - P. 196-200.

33.Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP. - 2-е изд., перераб. и доп. - СПб.: БХВ-Петербург, 2007. - 384 с.

34.Воронцов К.В. Машинное обучение [Электронный ресурс]: видеолекции курса / Школа анализа данных «Яндекса». - Режим доступа: https://yandexdataschool.ru/edu-process/courses/machine-learning (дата обращения: 16.12.2016).

35.Просянкина-Жарова Т.И., Терентьев А.Н. Исследование привлечения сбережения населения для активизации инвестиционной деятельности на основе использования модели прогнозирования оттока депозитов физических лиц // Фундаментальные исследования. - № 11-3. - 2013. -С. 507-511.

36.Юсупова Н.И., Ахметова Ю.В., Богданова Д.Р. Классификация клиентов на основе нечеткой классификации // Вестник Уфимского государственного авиационного технического университета. - № 5 (58), том 17. - 2013. - С. 93-100.

37.Бабина Н.В. Скоринг как метод оценки кредитного риска потребительского кредитования // Сервис plus. - № 3. - 2007. - С. 30-36.

38. Андреева Г. Скоринг как метод оценки кредитного риска [Электронный ресурс]. - Режим доступа: http://www.cfin.ru/finanalysis/ banks/scoring.shtml (дата обращения: 16.12.2016).

39. Модели кредитного и поведенческого скоринга [Электронный ресурс]. - Режим доступа: http://www.uran.donetsk.ua/~masters/2006/kita/ shepeleva/library/metod%20scoring.pdf (дата обращения: 16.12.2016).

40.Jain A., Nandakumar K., Ross A. Score normalization in multimodal biometric systems // Pattern Recognition. - № 38. - 2005. - P. 2270-2285.

41.Кошман А.С. CRM (Customer Relationship Management) - система управления взаимоотношениями с клиентами // Вестник Московского государственного областного университета. Серия: Экономика. - № 4. -2010. - С. 132-136.

42.Арустамов Э., Токмин К. Управление и планирование деятельности телекоммуникационных компаний в период финансового кризиса // РИСК: Ресурсы, Информация, Снабжение, Конкуренция». - №2 2. - 2010.

- С. 35-37.

43.Галямов А.Ф., Тархов С.В. Управление взаимодействием с клиентами коммерческой организации на основе методов сегментации и кластеризации клиентской базы // Вестник Уфимского государственного авиационного технического университета. - № 4 (65), том 18. - 2014. -С. 149-156.

44.Райхельд Ф.Ф., Тил Т. Эффект лояльности: движущие силы экономического роста, прибыли и непреходящей ценности / Пер. с англ.

- М.: Издательский дом "Вильямс", 2005. - 384 с.

45.Данильченко О. Клиентская аналитика: практики исследований удовлетворенности, расширенные возможности прогнозирования и моделирования [Электронный ресурс]. - Режим доступа: http://www.ibm.com/ru/events/presentations/swc2013/SPSS.pdf (дата обращения: 16.12.2016).

46.Исаев С. ACRM для грузоперевозок на примере железнодорожного транспорта / CRM SAS Russia [Электронный ресурс]. - Режим доступа: http://www.sas.com/content/dam/SAS/ru_ru/doc/Events/Presentation/Uvelic henie_dohodnosti_v_krizis_18_03_2015/1_Gruzoperevozki.pdf (дата обращения: 16.12.2016).

47. Технологии и инструменты повышения эффективности бизнеса телеком-операторов: опыт, методология и предложение компании «ИТС» / ООО «Информационные Технологии и Сервисы» [Электронный ресурс]. - Режим доступа: http://www.itands.ru/site? resource=bi_telecom.pdf (дата обращения: 16.12.2016).

48.Палкин Н.Б., Орешков В.И. Бизнес-аналитика: от данных к знаниям: Учебное пособие. - 2-е изд., испр. - СПб.: Питер, 2013. - 704 с.

49.Визуализация многомерных данных с помощью диаграмм Эндрюса [Электронный ресурс]. - Режим доступа: https://habrahabr.ru/post/ 248623/ (дата обращения: 16.12.2016).

50.Andrews plot [Электронный ресурс]. - Режим доступа: http://www. mathworks.com/help/stats/andrewsplot.html (дата обращения: 16.12.2016).

51.Cichosz P. Data Mining Algorithms: Explained Using R. - NY: Wiley, 2015. - 720 p.

52.Оценка классификатора (точность, полнота, F-мера) [Электронный ресурс]. - Режим доступа: http://bazhenov.me/blog/2012/07/21/ classification-performance-evaluation.html (дата обращения: 16.12.2016).

53.Performance Measures for Machine Learning [Электронный ресурс]. -Режим доступа: http://www.cs.cornell.edu/courses/cs578/2003fa/ performance_measures.pdf (дата обращения: 16.12.2016).

54.Вейнберг Р.Р. Интеллектуальный анализ данных и систем управления бизнес-правилами в телекоммуникациях: Монография. - М.: НИЦ ИНФРА-М, 2016. - 173 с.

55. Соколов Е.А. Семинары по выбору моделей [Электронный ресурс]. -Режим доступа: http://www.machinelearning.ru/wiki/images/1/1c/Sem06_ metrics.pdf (дата обращения: 16.12.2016).

56.Воронцов К.В. Лекции по методу опорных векторов [Электронный ресурс]. - Режим доступа: http://www.ccas.ru/voron/download/SVM.pdf (дата обращения: 16.12.2016).

57.Raileanu L.E., Stoffel K. Theoretical Comparison between the Gini Index and Information Gain Criteria // Annals of Mathematics and Artificial Intelligence. - Volume 41, Issue 1. - 2004. - P. 77-93.

58.Makhabel B. Learning Data Mining with R. - Birmingham: Packt Publishing, 2015. - 314 p.

59.Коэльо Л.П., Ричарт В. Построение систем машинного обучения на языке Python / Пер. с англ. - М.: ДМК Пресс, 2016. - 302 с.

60.Кохонен Т. Самоорганизующиеся карты / пер. 3-го англ. изд. - 2-е изд. -М.: БИНОМ. Лаборатория знаний, 2014. - 655 с.

61.Лепский А.Е., Броневич А.Г. Математические методы распознавания образов: Курс лекций. - Таганрог: Изд-во ТТИ ЮФУ, 2009. - 155 с.

62.Методы оптимизации / Р. Габасов, Ф.М. Кириллова, В.В. Альсевич и др.

- Мн.: Издательство «Четыре четверти», 2011. - 472 с.

63.Ясницкий Л.Н. Введение в искусственный интеллект. - 2-е изд., испр. -М.: Издательский центр «Академия», 2008. - 176 с.

64.Хайкин С. Нейронные сети: полный курс - 2-е изд., испр. / Пер. с англ.

- М.: ООО "И.Д. Вильямс", 2006. - 1104 с.

65.Осовский С. Нейронные сети для обработки информации / Пер. с польск.

- М.: Финансы и статистика, 2002. - 344 с.

66.Mitchell T.M. Machine Learning. - NY: McGraw-Hill Science/Engineering/ Math, 1997. - 432 p.

67.Луньков А.Д., Харламов А.В. Интеллектуальный анализ данных. Часть I / Саратовский государственный университет им. Н.Г. Чернышевского [Электронный ресурс]. - Режим доступа: http://elibrary.sgu.ru/uch_lit/ 1141.pdf (дата обращения: 16.12.2016).

68.Круглов В.В., Борисов В. В. Искусственные нейронные сети. Теория и практика. - 2-е изд., стереотип. - М.: Горячая линия-Телеком, 2002. -382 с.

69.Круглов В.В., Дли М.И., Голунов Р.Ю. Нечеткая логика и искусственные нейронные сети. - М.: ФИЗМАТЛИТ, 2001. - 201 с.

70.Нейроинформатика / А.Н. Горбань, В.Л. Дунин-Барковский, А.Н. Кирдин и др. - Новосибирск: Наука. Сибирское предприятие РАН, 1998.

- 296 с.

71.Classification, Clustering, and Data Mining Applications / D. Banks, L. House, F.R. McMorris, P. Arabie, W. Gaul (Eds.). - Springer Verlag: Berlin, Heidelberg, NY, 2004. - 658 p.

72.Яхъяева Г. Основы теории нейронных сетей [Электронный ресурс]. -Режим доступа: http://www.intuit.ru/studies/courses/88/88/info (дата обращения: 16.12.2016).

73.Refaat M. Data Preparation for Data Mining Using SAS. - San Francisco: Morgan Kaufmann, 2007. - 424 p.

74.Терещенко О.В., Курилович Н.В., Князева Е.И. Многомерный статистический анализ в социальных науках: учеб. пособие. - Мн.: БГУ, 2012. - 239 с.

75.Layton R. Learning Data Mining with Python. - Birmingham: Packt Publishing, 2015. - 344 p.

76.Moeyersoms J., Martens D. Including high-cardinality attributes in predictive models: A case study in churn prediction in the energy sector // Decision Support Systems. - № 72. - 2015. - P. 72-81.

77.Воронцов К.В. Лекции по методам оценивания и выбора моделей [Электронный ресурс]. - Режим доступа: http://www.ccas.ru/voron/ download/Modeling.pdf (дата обращения: 16.12.2016).

78.Нейчев Р.Г., Катруца А.М., Стрижов В.В. Выбор оптимального набора признаков из мультикоррелирующего множества в задаче прогнозирования [Электронный ресурс]. - Режим доступа: http://conf58. mipt.ru/static/reports_pdf/191.pdf (дата обращения: 16.12.2016).

79.Загоруйко Н.Г. Прикладные методы анализа данных и знаний. -Новосибирск: ИМ СО РАН, 1999. -270 с.

80.DEAP 1.1.0 documentation. Regroup typical EC benchmarks functions to import easily and benchmark examples [Электронный ресурс]. - Режим доступа: http://deap.readthedocs.io/en/master/api/benchmarks.html (дата обращения: 16.12.2016).

81.Virtual Library of Simulation Experiments. Test Functions and Datasets [Электронный ресурс]. - Режим доступа: http://www.sfu.ca/~ssurjano/ optimization.html (дата обращения: 16.12.2016).

82. Эволюционные методы моделирования и оптимизации сложных систем: конспект лекций / Е.С. Семенкин, М.Н. Жукова. В.Г. Жуков и др. -Красноярск: СФУ, 2007. - 209 с.

83.Скобцов Ю., Сперанский Д. Эволюционные вычисления [Электронный ресурс]. - Режим доступа: http://www.intuit.ru/studies/courses/14227/ 1284/info (дата обращения: 16.12.2016).

84.Mitchell M. An Introduction to Genetic Algorithms / 5th ed. - Cambridge MA, London: MIT Press, 1999. - 158 p.

85.The practical handbook of genetic algorithms, applications / edited by Lance D. Chambers. - 2nd ed. - Boca Raton: Chapman & Hall/CRC, 2001. - 544 p.

86.De Jong K.A. An analysis of the behavior of a class of genetic adaptive systems: Ph.D. thesis. - Ann Arbor: University of Michigan, 1975. - 256 p.

87. Воронов В. Методы конструирования тестовых функций [Электронный ресурс]. - Режим доступа: https://habrahabr.ru/post/349660/ (дата обращения: 24.02.2018).

88.Luke S. Essentials of Metaheuristics [Электронный ресурс]. - Режим доступа: https://cs.gmu.edu/~sean/book/metaheuristics/Essentials.pdf (дата обращения: 16.12.2016).

89.Test Functions Index [Электронный ресурс]. - Режим доступа: http:// infinity77.net/global_optimization/test_functions.html (дата обращения: 16.12.2016).

90.Мочалин А.Е. Бинарно-вещественное кодирование решений в генетических алгоритмах // Технологический аудит и резервы производства. - № 2 (23), том 3. - 2015. - С. 41-45.

91.Yang X.-S. Test Problems in Optimization [Электронный ресурс]. - Режим доступа: https://arxiv.org/pdf/1008.0549.pdf (дата обращения: 16.12.2016).

92.DEAP 1.1.0 documentation. Evolutionary Tools [Электронный ресурс]. -Режим доступа: http://deap.readthedocs.io/en/master/api/tools.html (дата обращения: 16.12.2016).

93.De Rainville F.-M., Fortin F.-A., Gardner M.-A., Parizeau M., Gagné C. DEAP - Enabling Nimbler Evolutions // SIGEVOlution. - Volume 6, Issue 2. - 2014. - P. 17-26. 94.Ivic S., Crnkovic B., Skific J., Cavrak M. Python u racunarskom inzenjerstvu. Numericke metode, priprema, obrada i vizualizacija podataka. - Rijeka: Sveuciliste u Rijeci, 2014. - 197 s.

95.Jacobson L., Kanber B. Genetic algorithms in Java Bacics. - NY: Apress, 2015. - 154 p.

96.Бураков М.В. Генетический алгоритм: теория и практика: учеб. пособие. - СПб.: ГУАП, 2008. - 164 с.

97.Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие / Под ред. Ю.Ю. Тарасевича. - Астрахань: Издательский дом «Астраханский университет», 2007. - 87 с.

98. Scikit Learn 019.1. Tuning the hyper-parameters of an estimator [Электронный ресурс]. - Режим доступа: http://scikit-learn.org/stable/modules/grid_search.html (дата обращения: 24.02.2018).

99.Гладков Л.А., Курейчик В.В., Курейчик В.М., Сороколетов П.В. Биоинспирированные методы в оптимизации. - М.: ФИЗМАТЛИТ, 2009. - 384 с.