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

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

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

Существующие подходы¹² принято делить на «marginalization» (исключение объектов или признаков с пропусками) и «imputation» (восстановление значений). Некоторые исследователи выделяют отдельную группу «projection» (или «imputation by regression»). Алгоритмы восстановления включают в себя множество методов разной природы, начиная с замены средним/медианой и заканчивая алгоритмами восстановления с использованием SVM, ближайших соседей или EM-алгоритм.

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

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

¹ R.J.A. Little, D.B. Rubin. Statistical Analysis with Missing Data // Journal of Edu
cational Statistics. 1991. Vol. 16, N. 2. P. 150-155.

² E. Zloba. Statistical methods of reproducing of missing data // Computer Modelling
& New Technologies. 2002. Vol. 6, N.1. P. 51-61.

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

Подходы, которые сводят многоклассовую классификацию к бинарной, устроены по следующей схеме: во время обучения несколько раз повторяется процедура группировки всех классов в два макрокласса и процедура обучения бинарного классификатора на двух макроклассах. Такие группировки называются дихотомиями. Во время классификации нового объекта происходит классификация его каждым из бинарных классификаторов, и полученный вектор предсказаний сравнивается с кодовыми словами классов в дихотомической матрице. На текущий момент распространены подходы 1-vs-1 (каждый против каждого), 1-vs-all (один против всех) или ECOC³ (error-correcting output codes).

В случае 1-vs-1 каждая дихотомическая задача разделяет только два исходных класса, не затрагивая при этом все остальные, в случае 1-vs-all в бинарных задачах отделяется один класс от всех других поочередно. Схема ECOC формирует серию произвольных дихотомических задач, соблюдая требования различности кодовых слов классов. ECOC является самой гибкой схемой из данных трех и широко применяется при решении задач классификации линейными и другими методами. Поэтому, развитие ЕСОС с целью улучшения точности распознавания является актуальной задачей.

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

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

В качестве другого способа восстановления используют различные статистические подходы: EM-алгоритм, Full information maximum likelihood (FIML, полная оценка максимального правдоподобия) и другие. Данные подходы показывают неплохие результаты на больших выборках.

Для более точного решения многоклассовой задачи в настоящее время разработаны различные модификации схемы ECOC: тройное кодирование, кла-

³ Thomas G. Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. // Journal of Artificial Intelligence Research. August 1994. Vol. 2, Issue 1. Pp. 263-286.

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

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

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

Основные задачи исследования:

1. Создание и исследование математических методов моделирования пропущенных значений признаков.

2. Разработка алгоритмов и вычислительных методов построения дихотомий в методе моделирования многоклассовой классификации (ЕСОС) и их оценки.

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

Научная новизна. Автором разработаны новые методы математического моделирования пропущенных значений признаков: локальный, глобальный, СЗК и SNE алгоритмы восстановления. Получена теорема о сходимости локального метода, показывающая применимость критериев остановки. Для глобального и SNE методов получены выражения для градиентов, которые являются эффективными по числу операций относительно подсчета функционала.

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

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

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

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

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

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

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

4. Методы математического моделирования пропущенных значений признаков: локальный, глобальный, основанный на серии задач классификаций (СЗК) и на условном сходстве объектов (SNE). Теорема о сходимости локального метода и выражения для градиентов глобального и SNE методов.

5. Численный метод нахождения весов дихотомий для лучшей отделимости кодовых слов классов. Показана ее способность осуществлять отбор дихотомий.

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

7. Оценка максимального числа исправленных ошибок при добавлении новой дихотомии в методе моделирования многоклассовой классификации (ЕСОС). Показана NP-трудность поиска оптимальной по числу исправленных ошибок дихотомии.

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

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

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

55-я, 56-я, 58-я, 59-я, 60-я научные конференции МФТИ, Москва, 2012-2017гг.;

Международная конференция OGRW-9, Koblenz, 2014;

Международная конференция CFDM, Varna, 2015;

Cпециальная секция международной конференции ICPRAI, Montreal, 2018.

Публикации. Результаты исследования опубликована в 13 научных работах, три из которых [7, 8, 11] - в рецензируемых изданиях, включённых ВАК РФ в список изданий, рекомендуемых для опубликования основных научных результатов диссертаций, а [12] является переводной версией [11], также опубликованной в рецензируемом журнале. Результаты, представленные в рамках диссертационной работы, являются обобщением результатов, полученных автором лично или при его активном участии. Личный вклад соискателя в работах, выполненных в соавторстве совпадает с положениями, выносимыми на защиту. Также лично соискателем написан весь программный код и проведены все эксперименты.

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