close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
РЯЗАНОВ ВАСИЛИЙ ВЛАДИМИРОВИЧ
РЕШЕНИЕ ЗАДАЧ ВОССТАНОВЛЕНИЯ ПРОПУЩЕННЫХ
ЗНАЧЕНИЙ ПРИЗНАКОВ И МНОГОКЛАССОВОЙ
КЛАССИФИКАЦИИ
Специальность 05.13.18 – Математическое моделирование,
численные методы и комплексы программ
Автореферат
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва – 2018
Работа выполнена на кафедре информатики и вычислительной математики
Московского физико-технического института
(государственного университета)
Научный руководитель:
Петров Игорь Борисович,
доктор физико-математических наук,
профессор, член-корреспондент РАН
Официальные оппоненты:
Сенько Олег Валентинович,
доктор физико-математических наук,
Федеральный исследовательский центр
«Информатика и управление» РАН,
Вычислительный центр имени А.А.
Дородницына РАН, отдел методов
классификации и анализа данных,
ведущий научный сотрудник
Бирюков Андрей Сергеевич,
кандидат физико-математических наук,
АО «Лаборатория Касперского», отдел
разработки продукта для защиты
критической инфраструктуры,
руководитель отдела
Ведущая организация:
Федеральное государственное бюджетное
образовательное учреждение высшего
образования «Московский педагогический
государственный университет»
Защита состоится «_____»_____________________ 2018 года в _______
часов на заседании диссертационного совета Д 212.156.05, созданного на базе
Московского физико-технического института (государственного университета),
по адресу: 141700, Московская обл., г. Долгопрудный, Институтский пер., 9,
МФТИ, аудитория 903 КПМ.
С диссертацией можно ознакомиться в библиотеке Московского физикотехнического института (государственного университета) и на сайте МФТИ
http://www.mipt.ru.
Автореферат разослан
«______» _____________________________2018 г.
Ученый секретарь
диссертационного совета Д 212.156.05
кандидат физико-математических наук
Федько Ольга Сергеевна
2
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
В рамках диссертационной работы рассматриваются проблемы решения
задачи восстановления пропущенных значений признаков и задачи многоклассовой классификации. На основе системы прецедентов формулируются и исследуются алгоритмы заполнения пропусков, алгоритмы формирования дихотомической кодовой матрицы и алгоритмы распознавания объекта на основе
сравнения кодовых слов.
Актуальность темы исследования. При решении прикладных задач
классификации, регрессии и кластеризации часто встречаются случаи, когда
какие-либо значения в исходной табличной выборке неизвестны. Такие ситуации приводят к проблемам при классификации: некоторые алгоритмы классификации не предполагают наличие пропусков в таблице, другие могут показать
худшее качество, чем на таблице полных описаний. Таким образом, задача восстановления пропусков позволяет решить проблемы отказа некоторых классификаторов от работы и способна повысить точность классификации.
Существующие подходы12 принято делить на «marginalization» (исключение объектов или признаков с пропусками) и «imputation» (восстановление значений). Некоторые исследователи выделяют отдельную группу «projection»
(или «imputation by regression»). Алгоритмы восстановления включают в себя
множество методов разной природы, начиная с замены средним/медианой и заканчивая алгоритмами восстановления с использованием SVM, ближайших соседей или EM-алгоритм.
Так как точность решения задачи классификации напрямую зависит от
данных, с которыми работает классификатор, то неточное восстановление пропусков приведет к ухудшению точности классификации или отказу. Таким образом, проблема восстановления прочерков является актуальной.
Задача классификации называется многоклассовой, если число классов
превышает 2. При решении задачи на 3 и более классов, может возникнуть
необходимость в сведении ее к серии задач классификаций на 2 класса. Такие
ситуации возникают, если природа классификатора не позволяет разделять более двух классов одновременно. Например, линейные методы широко распространены из-за своей простоты и наглядности (логистическая регрессия, метод
опорных векторов и др.), но линейная гиперплоскость разделяет пространство
лишь на два подпространства. Классификаторы, способные напрямую решать
многоклассовые задачи (нейронные сети, градиентный бустинг и др.), без группировки классов тоже могут показать низкую точность в случае несбалансированной представленности классов и при некоторых особенностях их простран-
1
R.J.A. Little, D.B. Rubin. Statistical Analysis with Missing Data // Journal of Educational Statistics. 1991. Vol. 16, N. 2. P. 150-155.
2
E. Zloba. Statistical methods of reproducing of missing data // Computer Modelling
& New Technologies. 2002. Vol. 6, N.1. P. 51-61.
3
ственного расположения. В таких случаях вместо многоклассовой классификации решают несколько задач бинарной классификации.
Подходы, которые сводят многоклассовую классификацию к бинарной,
устроены по следующей схеме: во время обучения несколько раз повторяется
процедура группировки всех классов в два макрокласса и процедура обучения
бинарного классификатора на двух макроклассах. Такие группировки называются дихотомиями. Во время классификации нового объекта происходит классификация его каждым из бинарных классификаторов, и полученный вектор
предсказаний сравнивается с кодовыми словами классов в дихотомической
матрице. На текущий момент распространены подходы 1-vs-1 (каждый против
каждого), 1-vs-all (один против всех) или ECOC3 (error-correcting output codes).
В случае 1-vs-1 каждая дихотомическая задача разделяет только два исходных класса, не затрагивая при этом все остальные, в случае 1-vs-all в бинарных задачах отделяется один класс от всех других поочередно. Схема ECOC
формирует серию произвольных дихотомических задач, соблюдая требования
различности кодовых слов классов. ECOC является самой гибкой схемой из
данных трех и широко применяется при решении задач классификации линейными и другими методами. Поэтому, развитие ЕСОС с целью улучшения точности распознавания является актуальной задачей.
Сформулированные выше проблемы пропущенных значений признаков и
многоклассовой классификации являются распространенными проблемами при
решении задач классификации и требуют наличия большого числа разнообразных точных подходов, чтобы на этапе обучения исследователь мог подобрать
наиболее подходящий по метрикам алгоритм.
Степень разработанности темы исследования. В настоящий момент
задачи многоклассовой классификации и восстановления пропущенных значений признаков являются недостаточно разработанными. Самыми распространенными способами решения пропущенных значений на практике являются замена средним/медианой и удаление объектов/признаков с пропусками. Такие
подходы являются быстрыми, но по точности восстановления уступают более
сложным методам. Существуют подходы, основанные на k-ближайших соседях,
алгоритмах SVM, бинарных решающих деревьях и других классификаторах. В
некоторых задачах такие подходы показывают хорошую точность восстановления, но не гарантируют успешный результат и быструю работу.
В качестве другого способа восстановления используют различные статистические подходы: EM-алгоритм, Full information maximum likelihood (FIML,
полная оценка максимального правдоподобия) и другие. Данные подходы показывают неплохие результаты на больших выборках.
Для более точного решения многоклассовой задачи в настоящее время
разработаны различные модификации схемы ECOC: тройное кодирование, кла3
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.
4
стеризация плохо разделимых классов, исследуются схемы, повышающие разделимость кодовых слов классов и дихотомий. Но, в большинстве прикладных
пакетов и задач, как правило, выбирается самая традиционная схема ECOC.
Несмотря на большое количество уже существующих подходов и интерес
исследователей к данным темам, нельзя утверждать, что существует единый
стандарт восстановления пропущенных значений и схемы ECOC. В зависимости от числа объектов, признаков, пропусков и других параметров задачи лучшие результаты показывают те или иные методы, поэтому разработка новых
конкурентных алгоритмов позволяет расширить перечень доступных методов и
выбрать наилучший.
Цели и задачи исследования. В рамках работы над диссертацией ставились цели создания и обоснования методов моделирования различной природы
пропущенных значений в табличных данных и разработка модифицированных
вычислительных методов классификации на основе схемы с использованием
дихотомических подзадач. В качестве развития методов исследования математических моделей многоклассовой классификации ставилась задача создания
алгоритмов и численных методов формирования дихотомической кодовой матрицы и задача предложения и обоснования новых функций сравнения кодовых
слов и декодирования объекта с целью максимизации точности классификации.
Основные задачи исследования:
1. Создание и исследование математических методов моделирования
пропущенных значений признаков.
2. Разработка алгоритмов и вычислительных методов построения дихотомий в методе моделирования многоклассовой классификации
(ЕСОС) и их оценки.
3. Создание, обоснование и разработка комплексов программ для алгоритмов классификации объектов по имеющейся кодовой матрице с использованием дихотомий.
Научная новизна. Автором разработаны новые методы математического
моделирования пропущенных значений признаков: локальный, глобальный,
СЗК и SNE алгоритмы восстановления. Получена теорема о сходимости локального метода, показывающая применимость критериев остановки. Для глобального и SNE методов получены выражения для градиентов, которые являются эффективными по числу операций относительно подсчета функционала.
В работе предложены способы оценки дихотомий и вычислительные методы по точности, F-мере, спискам точностей, на основе данных оценок введены функции сравнения кодовых слов на этапе декодирования. Предложен алгоритм оптимизации дихотомий с весами и показана его способность осуществлять отбор дихотомий.
Предложена и исследована процедура добавления дихотомий в кодовую
матрицу. Создан вычислительный метод поиска локальным алгоритмом по
фиксированному критерию оценки. Предложено использование кластеризаци5
онных индексов для быстрого поиска начального приближения, доказана теорема об их быстром пересчете. Получена оценка максимального числа исправленных ошибок при добавлении новой дихотомии, показана NP-трудность
нахождения оптимальной по числу исправленных ошибок дихотомии. Созданы
и апробированы комплексы программ.
Теоретическая значимость. Полученные в работе алгоритмы восстановления пропущенных значений, методы построения дихотомической матрицы и
декодирования объекта являются новыми. Для локального алгоритма доказана
теорема о сходимости, для SNE и глобального алгоритмов получены быстрые
выражения для градиентов. Исследован вопрос добавления новой дихотомии,
получена оценка для максимального числа исправленных ошибок и показана
NP-трудность задачи поиска дихотомии, максимизирующей данный критерий.
Практическая значимость. Предложенные алгоритмы применимы на
практике, что показывают эксперименты по восстановлению прочерков и по
многоклассовой классификации на ряде практических и модельных задач.
Методология и методы исследования. Теоретические результаты выведены с применением методов математического моделирования, вычислительной математики, оптимизации, теории линейной алгебры, дискретной математики, теории вероятностей, теории распознавания и теории множеств. Расчеты проведены
на основании предложенных комплексов программ, разработанных с применением современных технологий программирования.
Положения, выносимые на защиту.
1. Методы математического моделирования пропущенных значений признаков: локальный, глобальный, основанный на серии задач классификаций (СЗК) и на условном сходстве объектов (SNE). Теорема о сходимости локального метода и выражения для градиентов глобального
и SNE методов.
2. Численный метод нахождения весов дихотомий для лучшей отделимости кодовых слов классов. Показана ее способность осуществлять отбор дихотомий.
3. Вычислительный метод локального поиска оптимальной по критерию
дихотомии. Предложены различные функции качества и исследовано
их поведение, доказана теорема о пересчете кластеризационных индексов при локальном шаге.
4. Оценка максимального числа исправленных ошибок при добавлении
новой дихотомии в методе моделирования многоклассовой классификации (ЕСОС). Показана NP-трудность поиска оптимальной по числу
исправленных ошибок дихотомии.
5. Создание комплексов программ и практическая апробация, подтверждающая применимость предложенных методов восстановления при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 наименование.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность диссертационной работы, сформулированы цели и задачи исследования, аргументирована научная новизна исследований, представлены результаты и положения, выносимые на защиту,
приведена краткая структура диссертации по главам.
В первой главе предложены и исследованы алгоритмы восстановления
пропущенных значений признаков. Исследуются методы, основанные на метрической близости объектов – глобальный и локальный, метод последовательного решения серии задач классификаций (далее СЗК-метод или СЗК-алгоритм)
и метод условного сходства объектов (далее SNE-метод, сокращение от англ.
stochastic neighbor embedding)
Подходы, предложенные в данной главе можно в общем случае применять как в задачах классификации, так и в задачах кластеризации или регрес7
сии. Рассматриваются табличные данные, т.е. данные, которые можно представить в виде таблицы m × n , где m - число объектов, а n - число признаков. Пропущенные значения в выборке будем обозначать как NaN (от англ. “Not a Number”). Краткий обзор существующих подходов к восстановлению пропущенных
значений приведен в разделе 1.1.
В разделе 1.2 вводится локальный подход, основанный на следующей
последовательности итераций xij(t ) = xij(t −1) + θ ( xij(t −1) * − xij(t −1) ) , ∀xij = NaN , xij(t ) = xij( t −1) ,
∀xij ≠ NaN , где t -номер итерации, xij – произвольный неизвестный элемент таблицы обучения, 0 < θ ≤ 1 , начальная точка последовательности итераций выбирается случайно из множества допустимых значений признаков, xij( t ) * – среднее
по k ∈ ` соседям i -го объекта. Здесь θ , k - параметры подхода. Итерационная
схема может быть синхронной, при которой значения xij(t ) = xij(t −1) + θ ( xij(t −1) * − xij(t −1) ) на
каждой итерации t меняются одновременно для всех xij = NaN или последовательной, при которой сначала фиксируется xij = NaN , а затем проводится итерационная процедура xij(t ) = xij(t −1) + θ ( xij(t −1) * − xij(t −1) ) . В работе показана сходимость последовательной процедуры восстановления.
Теорема 1.1. Числовая последовательность { xij(t ) } , t = 0,1, 2... восстановленных значений признака последовательным локальным методом имеет конечный предел.
Данная теорема доказывается путем доказательства монотонности и
ограниченности восстановленных значений и сведения ее к теореме Вейерштрасса о пределе числовой последовательности.
В другом метрическом подходе (глобальном, раздел 1.3) рассматривается
функционал, основанный на всевозможных парах объектов. Суть алгоритма заключается в том, что рассматриваются всевозможные пары объектов и рассматривается несколько метрик между ними. Если у объекта отсутствует значение признака, то данное значение полагается переменной, которая ищется в
ходе оптимизации. Рассматриваемые метрики между парами объектов: метрика
в подпространстве полных описаний (подпространстве, где известны признаки
обоих объектов), в подпространстве, где известен хотя бы один признак и во
всем пространстве.
Для каждого объекта xi вводятся следующие множества. Ωi0 = {t : xit ≠ NaN } ,
Ω1i = {t : xit = NaN } – множества признаков, в которых объект xi имеет определенное значение или имеет неизвестное(пропущенное) значение соответственно.
Через yij далее будем обозначать неизвестные значения xij = NaN . На основе
множеств Ωi0 и Ωi0 определим следующие пересечения для пар объектов xi , x j :
1
0
00
0
0
11
1
1
Ωij01 = Ωi0 ∩ Ω1j , Ω10
ij = Ω i ∩ Ω j , Ω ij = Ω i ∩ Ω j , Ω ij = Ωi ∩ Ω j .
Метрика в подпространстве полных описаний выглядит так:
1

2
+
2
ρ (xi , x j ) =  ∑ ( xit − x jt ) 
 t∈Ω00

 ij

8
Метрики в подпространствах, где известен хотя бы один признак и в полном пространстве, выглядят следующим образом соответственно:
1

2
ρ ++ (xi , x j ) =  ∑ ( xit − x jt )2 + ∑ ( xit − y jt ) 2 + ∑ ( yit − x jt ) 2 
 t∈Ω00

t∈Ω01
t∈Ω10
ij
ij
 ij

1

2
2
2
2
2
ρ (xi , x j ) =  ∑ ( xit − x jt ) + ∑ ( xit − y jt ) + ∑ ( yit − x jt ) + ∑ ( yit − y jt ) 
 t∈Ω00

t∈Ω01
t∈Ω10
t∈Ω11
ij
ij
ij
 ij

Предложены следующие функционалы метрической близости
F1 ( yij ) =
m
∑
i1 ,i2 =1
i1 > i2
( ρ (xi1 , xi2 ) − ki1+i2 ρ + (xi1 , x i2 )) 2 , F2 ( yij ) =
m
∑ ( ρ (x
i1 ,i2 =1
i1 >i2
i1
, xi2 ) − ki++
ρ ++ (xi1 , xi2 )) 2
1i2
Утверждение 1.1. Частные производные функционалов F1 ( yij ) и F2 ( yij )
по произвольному yij выглядят следующим образом:
∂F1 ( yij )
∂yij
∂F2 ( yij )
∂yij
=2
( ρ (xi1 , xi ) − ki1+i ρ + (xi1 , xi ))
∑
i1 ≠ i
ρ ( xi1 , xi ) > 0
=2
ρ ( xi , xi )
( yij − xi1 j ) ,
1
 ( yij − xi1 j )
( yij − xi1 j )+ 
++ ++
++
ρ
x
x
−
ρ
x
x
−
(
(
,
)
k
(
,
))
k


∑
i1
i
i1i
i1
i
ρ (xi1 , xi ) i1i ρ ++ (xi1 , xi ) 
i1 ≠ i

ρ ( x ,x ) >0
i1
i
 yij − xi1 j , xi1 j ≠ NaN
где ( yij − xi j ) + = 
1

0, иначе
Метод восстановления признаков, основанный на применении серии задач классификаций (раздел 1.4.), состоит в следующем. Пусть неизвестно какое-то значение xij , а множество допустимых значений j –го признака вычисляется по таблице обучения и для каждого j оно упорядочено по возрастанию
a = a1 < a2 < ... < aN = b . Тогда мы должны распознать значение xij . Алгоритм распознавания состоит в последовательном решении не более [ log 2 N ] + 1 дихотомических задач по обучающим выборкам, полученным из исходной таблицы обучения путем ее последовательного деления по числам a1 , a2 ,..., aN .
Теорема 1.2. Γ j (x) =
2
C kd ( xt , x ,xτ ) , где
∑
K j ( K j − 1) xt ,xτ ∈K j ,t >τ
d ( x , x, x ) = {β : ( x ≤ x ≤ x ) ∨ ( x ≤ x ≤ x )}, β = 1, 2,..., n ,
t
tβ
tβ
τ
β
τβ
τβ
β
K - описание j - го класса.
j
Теорема 1.2 позволяет использовать неметрическую функцию близости
1, ( xt β ≤ xβ ≤ xτβ ) ∨ ( xτβ ≤ xβ ≤ xt β ), ∀β ∈ Ω,
в модели вычисления оцеBΩ (xt , x, xτ ) = 
иначе.
0,
нок4 и эффективное вычисление оценок за классы.
4
Журавлев Ю.И., Никифоров В.В. Алгоритмы распознавания, основанные на
вычислении оценок // Кибернетика. 1971. №3. С. 1-11.
9
В разделе 1.5 предложен алгоритм восстановления пропущенных данных
на основе условного сходства объектов. Данный метод имеет общие методы с
алгоритмами SNE5 и t-SNE, используемых в задаче понижения размерности.
Рассматриваются векторы xi , x i , i = 1, m в подпространстве полных описаний признаков ( Ω ) и во всем пространстве соответственно ( Ω ). Для объектов x i из пространства полных признаков Ω неизвестные значения xij = NaN полагаются переменными yij и ищутся в процессе оптимизации.
Определение 1.1. Условным сходством (conditional similarity) для любой
− xi − x j
пары объектов xi , x j ∈ Ω называется величина p j|i = e
2σ i2
2
∑e
− xi − x k
2σ i2
2
.
k ≠i
Рассматриваются условные сходства p j|i и p j|i между всеми различными
парами объектов из пространств Ω и Ω . Величины σ i , σ i в них можно задавать
константами или искать, оптимизируя энтропию распределения по эффективному числу соседей.
На основе условных близостей объектов вводит и затем минимизируется
дивергенция Кульбака-Лейблера:
p j|i
C = ∑ KL( Pi || Pi ) =∑∑ p j|i log
p j|i
i
i
j
Для того, чтобы минимизировать данный функционал, необходимо найти
частые производные
∂C
.
∂xi1 ,i2
Утверждение 1.2. Частные производные дивергенции Кульбака-Лейблера
представимы в виде:
∂C
= ∑ dii1i2
∂xi1 ,i2 i ≠i1
d
i
i1i2
=
(( p
∂ xi − xi1
i1 |i
2
∂xi1i2
)
(
+ pi|i1 − p i1|i (1 + pi|i ) − p i|i1 1 + pi1|i1
(
) ) , где
)
= 2 xi1i2 − xii2 .
Утверждение позволяет находить частные производные за линейное время, несмотря на то, что функционал имеет квадратичную зависимость от числа
объектов, тем самым быстрее оптимизируя функцию.
Имея функцию и вектор градиента, осуществляется оптимизация методом
градиентного спуска с использованием «момента»:
yij
(t )
= yij
( t −1)
+η
∂C ( yij )
∂yij
+ α (t )
(y
( t −1)
ij
− yij
( t − 2)
)
Во второй главе рассматривается проблема многоклассовой классификации. Раздел 2.1 вводит основные обозначения и понятия, а также приводит об5
G.E. Hinton and S.T. Roweis. Stochastic Neighbor Embedding. In Advances in
Neural Information. Processing Systems, volume 15, pages 833–840, Cambridge,
MA, USA, 2002. The MIT Press
10
зор существующих методов работы с данной задачей. Рассмотрим задачу классификации при числе классов большем 2. Дана обучающая выборка
X = {x1 , x 2 ,..., xm } , xi ∈ K j , i = m j −1 + 1, m j −1 + 2,..., m j , m0 = 0 , ml = m , j = 1, 2,..., l . Считаем,
что x, xi ∈ R n . Суть подхода ЕСОС состоит в следующем. Исходной задаче классификации с l классами K j , j = 1, 2,..., l ставится в соответствие N ( N не более
2l −1 − 1 )
дихотомических задач с классами
K 0j = K i ∪ K i ∪ ... ∪ K i
и
j
j
j
j
j
K 1 = Kσ ∪ Kσ ∪ ... ∪ Kσ . K 0 ∪ K 1 = X , K 0 ∩ K 1 = ∅ . Введем для каждого класса K i
1
1
2
π
ρ
2
бинарный вектор α i = (α i1 , α i 2 ,..., α ik ) , α ij = 1 при Ki ∈ K1j и α ij = 0 иначе. В таком
случае матрица Α = (α ji )l× N называется кодовой. В итоге, каждому классу K j
будет поставлен в соответствие вектор α j = (α j1 , α j 2 ,..., α jN ) , α jt ∈ {0,1}, t = 1, 2,..., N .
α jt = 1 , если класс K j входит в первый класс t − й дихотомии, и α jt = 0 , если
класс K j входит в нулевой класс t − й дихотомии. Этап формирования дихотомической матрицы называется кодированием. Тогда задача классификации x
может быть решена следующим образом. Следующие этапы называются также
задачей декодирования.
1. Для x решается N дихотомических задач и вычисляется вектор
α (x) = (α1 (x), α 2 (x),..., α N (x)) , где α t (x), t = 1, 2,..., N - результат классификации x дихотомическим алгоритмом № t .
2. Объект x относится в класс Ki , согласно минимума некого критерия
r (α, α i ) = min r (α, α j ) . В качестве критерия можно использовать разные
j
метрики, такие как Евклидова, L2 и прочие, но на практике чаще применяется расстояние Хемминга:
N
r (α (x), α j ) = ∑ α t (x) − α jt
(2.1)
t =1
Принятие решение о классификации происходит по формуле
A
x 
→ K i , i : r (α (x), α i ) = min r (α (x), α j )
j
(2.2)
Отметим особенности данного подхода и факторы, благоприятные для
классификации.
1. В качестве эталонных дихотомий ( K 1j и K 0j , j = 1, 2,..., N ) надо брать такие, чтобы относительно данных двух классов было хорошее распознавание, т.е. брать дихотомии осознанно, а не случайно (см. рисунки
2.1, 2.2).
2. Набор эталонных дихотомий надо брать так, чтобы векторы α j , α k
были максимально удалены друг от друга в совокупности для всех пар
классов K j и K k .
3. Задача классификации на два класса решается проще, чем задача классификации на большее число классов.
4. Некоторый класс может содержать мало объектов при обучении. Это
негативный фактор, если мы строим алгоритм сразу для всех классов,
11
или индивидуально для данного класса. Но это становится несущественным, если данный класс входит в представительное объединение
с другими классами. Класс может быть «плохо отделим» от других
классов, но «хорошо отделим» совместно с другими классами.
5. В дихотомической задаче макроклассы имеют большую мощность чем
исходные классы в многоклассовой задаче.
6. Дихотомии имеют различную информативность.
На рисунках 2.1, 2.2 проиллюстрированы случаи «естественного» и «неестественного» формирования дихотомий.
Рис. 2.1. Создание хорошей дихотомической задачи
Рис. 2.2. Создание плохой дихотомической задачи
В разделе 2.2 диссертационной работы предложен ряд способов оценки
дихотомий и на основе их созданы функции сравнения кодовых слов нового
объекта и кодовых слов классов в дихотомической матрице.
В подразделах 2.2.1 и 2.2.2 вводятся понятия точности и F-меры дихотомии и на основе их предлагаются модифицированные функции сравнения кодовых слов:
N
r (α (x), α j ) = ∑ rjt , где
t =1
N
r (α (x), α j ) = ∑ rjt , где
t =1
1 − pt , α (x)t = α jt ,
rjt = 
иначе
 pt ,
1 − Ft , α (x)t = α jt
rjt = 
иначе
 Ft ,
(2.3)
(2.5)
Здесь pi , Fi - точность и F-мера бинарного классификатора, соответствующего i дихотомии бинарного классификатора. Для принятия решения о принадлежности объекта классу используется так же формула (2.2).
Подраздел 2.2.3 вводит определение матрицы списков точностей и функцию расстояния между кодовыми словами, которая учитывает не скалярную
точностью дихотомии, а точность в зависимости от исходного макрокласса.
12
Определение 2.6. Матрица W называется матрицей списков точно K true

стей, если W =  ji  , где K j -мощность (количество объектов) класса K j ,
 K j lxN
di
а K true
= x : x 
→ K ai ij , x ∈ K j , K j ⊂ K ai ij .
ji
di
K true
= x : x 
→ K ai ij , x ∈ K j , K j ⊂ K ai ij
ji
есть количество объектов класса K j ,
которые были отнесены в верный бинарный класс ( K ai ) i -й дихотомией на этаij
пе обучения. aij есть компонент кодовой матрицы дихотомий, который равен 0,
если K j ⊂ K 0i , и равен 1, если K j ⊂ K 1i .
Функция расстояния меняется следующим образом:
N
r (α (x), α j ) = ∑ rjt , где
t =1
1 − W jt , α (x)t = α jt
rjt = 
иначе
 W jt ,
(2.7)
В разделе 2.2.4 предложен и обоснован метод добавления весов дихотомиям и модификации функции расстояния Хемминга (2.1) с учетом данных весов (2.10).
N
r (α (x), α j ) = ∑ α (x)t − α jt wt
t =1
Вводится оптимизационная задача, называемая оптимизацией дихотомий
с весами (ОДВ).
N
∑ αυ
j =1
N
∑w
j =1
j
j
− α µ j w j ≥ y; ∀υ , µ ;υ > µ ;υ , µ = 1,..., l
(2.9)
= N , wj ≥ 0
y → max
Цель данной задачи найти такой вектор весов w ∈ \ n , чтобы минимальное
расстояние между кодовыми словами разных классов было максимально согласно функции близости. На практике ОДВ позволяет не только максимизировать зазор между классами, но и отбирать дихотомии путем обнуления весов в
ходе оптимизации.
Раздел 2.3 посвящен изучению задачи формирования кодовой матрицы. В
разделе 2.3.1 описывается процедура локальной оптимизации дихотомии d по
произвольному критерию Q ( d ) . Обозначим класс допустимых дихотомий через
Θ . Локальный алгоритм состоит в поиске начального приближения d (0) ∈ Θ
(кластеризационными критериями или случайного). На итерации t строится
множество допустимых дихотомий D(t ) , каждая из которых отличается от дихотомии d(t ) в одной компоненте и принадлежит классу Θ . Если
∃d ∈ D(t ) : Q ( d ) = max Q ( d i(t ) ) ≥ Q ( d (t ) ) , то эта дихотомия становится d (t +1) , иначе алdi( t ) ∈D( t )
горитм поиска дихотомии завершается.
Раздел 2.3.2 посвящен важному вопросу выбора начального приближения
в локальном алгоритме. В качестве начального приближения исследован под13
ход, заключающийся в задании случайной дихотомии и последующей быстрой
оптимизации кластеризационными критериями Ball-Hall6 и Trace_W7.
Определение 2.8. Индексом Ball-Hall называется величина
C=
1
∑ ni
i∈I1
∑
x∈Κ1
2
x − µ1 +
1
∑ ni
i∈I 2
∑
x∈Κ 2
x − µ2
2
=
1
1
J (Κ 1 ) +
J (Κ 2 )
∑ ni
∑ ni
i∈I1
i∈I 2
Определение 2.9. Индексом Trace_W называется величина
C=
∑
x∈Κ1
2
x − µ1 +
∑
x∈Κ 2
2
x − µ2
= J (Κ 1 ) + J (Κ 2 )
Получена теорема о быстром пересчете данных критериев при использовании локального алгоритма.
Теорема 2.1. Пусть внутренний дисперсионный критерий при разбиении
на два множества Κ1 , Κ 2 равен:
C=
1
∑ ni
i∈I1
∑
x∈Κ1
2
x − µ1 +
1
∑ ni
i∈I 2
∑
x∈Κ 2
x − µ2
2
=
1
1
J (Κ 1 ) +
J (Κ 2 ) ,
∑ ni
∑ ni
i∈I1
i∈I 2
и Κ1 → Κ = Κ1 ∪ Kν , Κ 2 → Κ = Κ 2 \ Kν , тогда верно:
*
1
J (Κ 1* ) = J (Κ 1 ) +
J (Κ *2 ) = J (Κ 2 ) −
и C* =
*
2
∑
x∈Kν
∑
x∈Kν
x − µ1
2
−
nν 2 mν − µ1
x − µ2 −
,
∑ n + nν
i∈I1
2
2
i
nν 2 mν − µ 2
2
∑ n − nν
i∈I 2
i
1
1
J (Κ *1 ) +
J (Κ * 2 )
∑ ni + nν
∑ ni − nν
i∈I1
i∈I 2
Следствие из данной теоремы позволяет быстро пересчитывать индексы
Ball-Hall и Trace_W. Скорость пересчета обусловлена тем, что не нужно полностью считать индексы заново, а достаточно посчитать небольшую поправку,
трудоемкость которой пропорциональна размеру класса Kν , перешедшему из
одного макрокласса в другой.
В следующем разделе 2.3.3 получена оценка максимального числа исправленных ошибок при добавлении новой дихотомии в существующей ансамбль. Она выражается через матрицу неточностей ансамбля из N дихотомий
C ( Cij -число отнесений объектов класса K i в класс K j ) и матрицу перекрытия
D.
6
Qinpei ZhaoMantao XuPasi Fränti. Sum-of-Square Based Cluster Validity Index
and Significance Analysis // International Conference on Adaptive and Natural Computing Algorithms. ICANNGA 2009. Pp. 313-322.
7
Clustering Indices Bernard Desgraupes University Paris Ouest Lab Modal’X //
https://cran.r-project.org/web/packages/clusterCrit/index.html
14
Определение 2.10. Величина q (d) =
∑
i , j:di ≠ d j
Cij называется числом неточ-
ностей вектора d .
Определение 2.11. Матрицей перекрытия D бинарного дихотомическо1, d i ≠ d j
го вектора d будем называть матрицу вида: Dij = 
.
0, di = d j
В работе показано, что q (d) =
∑
i , j:di ≠ d j
Cij = C,D есть оценка сверху макси-
мального числа объектов, для которых новая дихотомия может исправить оценку. Ставится задача поиска дихотомии d max : q (d max ) = maxl q (d) , максимизируd∈{0,1}
ющей данную оценку и показывается, что задача нахождения такого вектора
является NP-трудной.
В третьей главе приводятся результаты практической апробации предложенных моделей. В разделе 3.1 для моделирования и исследования алгоритмов восстановления пропущенных данных из первой главы используется следующая схема. Берется табличная выборка и α % случайных признаков для
каждого объекта заменяется на NaN. После этого данные пропущенные значения восстанавливаются различными методами и сравниваются по точности
классификации на восстановленной выборке.
Исследовалась модельная задача, которая представляла из себя смеси
нормальных распределений с 10 независимыми признаками. Все распределения
сгруппированы в 2 класса через одного. Результаты визуализации полученной
выборки видно на рисунке 3.1.
Рис. 3.1. Начальная выборка
Результаты экспериментов представлены в таблице 3.1. Сравнивались
подходы восстановления пропущенных значений средним, локальный алгоритм
и серия задач классификаций. Задачи классификации решались алгоритмами
ближайших соседей (KNN), бинарных решающих деревьев (BT) и линейной
машиной (LM).
метод\α
KNN
10
сред. лок.
90.0 100
20
СЗК. сред. лок.
94.0 100
100
30
СЗК. сред. лок.
82.0 97.0
100
15
40
СЗК. сред. лок.
70.5 98.0
100
СЗК.
99.5
BT
LM
94.0
72.5
метод\α
50
сред. лок.
67.5 97.0
90.0 94.0
58.5 86.5
KNN
BT
LM
99.0
98.0
92.5
86.5
93.0
50.5
98.5
97.0
60
СЗК. сред. лок.
97.0 64.5 90.5
89.5 84.5 88.5
85.0 47.0 80.0
88.0
81.0
91.5
52.5
97.5
95.0
70
СЗК. сред. лок.
84.5 66.5 87.0
88.0 79.0 78.0
74.0 44.0 64.0
94.0
81.0
84.5
51.5
97.0
94.5
80
СЗК. сред. лок.
66.5 63.5 78.0
83.0 80.0 71.0
64.0 55.5 66.5
Taб. 3.1. Точность распознавания при различных α
90.0
85.5
СЗК.
72.8
73.5
70.0
В работе исследовалось восстановления пропущенных значений на примере классической выборки машинного обучения “iris”, посвященной задаче
классификации сортов Ириса. Визуализация задачи представлена на рисунке
3.6.
Рис. 3.6. Визуализация в задаче IRIS
В данной задаче выбирались 2 признака, в которые добавлялись α% прочерков и затем восстанавливались заменой средним и всеми предложенными
подходами. Результаты представлены в таблице 3.6.
метод\α
0
LogReg
SVM
2 признака, α =80
сред.
лок.
глоб.
96
87.3
86.7
89.3
96.6
94.0
90.6
92.6
СЗК.
2 признака, α =90
SNE
сред.
лок.
глоб.
СЗК.
SNE
88.6
92.0
88.0
85.3
87.3
88.6
92
83.3
94.0
94.0
91.3
94.0
94.0
94.6
16
BT
96.6
90.6
92.6
93.3
94.0
92.6
94.0
91.3
93.3
92.6
93.3
Таб. 3.6 Точность распознавания при различных α
Эксперименты по восстановлению пропущенных значений разными алгоритмами демонстрируют что при небольшом числе прочерков предпочтительнее предложенные подходы, а при большом статистические (замена средним).
Алгоритмы многоклассовой классификации исследовались на трех реальных и модельных выборках, одна из которых представлена в виде нормально
распределенных 16-ти классов и двумя признаками. Расположение объектов
проиллюстрировано на рисунке 3.17. Исследовалась точность классификации в
зависимости способа построения дихотомической матрицы (случайная матрица, локальный поиск с использованием F-меры в качестве функции качества,
отбор дихотомий с помощью ОДВ) и зависимость точности классификации в
зависимости от функции декодирования (по F-мере, по точности, по спискам
точностей, расстояние Хемминга).
Рис. 3.17. Визуализация модельной задачи
Точность классификации в зависимости от способа сравнения кодовых
слов изображена на рисунке 3.19. Эксперименты проведены при разном числе
дихотомий при случайном построении кодовой матрицы.
17
Рис. 3.19. Точность в зависимости от числа дихотомий (логистическая регрессия)
На рисунке 3.30 изображена зависимости точности классификации от
числа дихотомий в матрице при разных способах построения кодовой матрицы.
Рис. 3.30. Точность классификации в зависимости от способа построения
матрицы (классификатор – SVM, расстояние Хемминга взвешенно по спискам
точности)
Эксперименты по многоклассовой классификации демонстрируют следующие результаты: подход ОДВ существенно сокращает число дихотомий в
матрице, наилучшие результаты показывают функции декодирования, взвешенные по F-мере или спискам точностей, наилучшие результаты при построении кодовой матрицы дает локальный поиск по F-мере.
В заключении сформулированы основные результаты диссертационной
работы.
18
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
1. Предложены методы математического моделирования пропущенных
значений признаков: локальный, глобальный, основанный на серии задач классификаций(СЗК) и на условном сходстве объектов(SNE). Доказаны теорема о сходимости локального метода и выражения для градиентов SNE и глобального методов.
2. Разработан численный метод оптимизации дихотомий с весами, показана его способность осуществлять отбор дихотомий.
3. Предложены различные функции качества дихотомий, обосновано их
использование в качестве критерия при локальном методе. Обоснован
вычислительный метод оптимизации дихотомий, доказана теорема о
пересчете кластеризационных индексов при локальном шаге.
4. Исследован метод моделирования многоклассовой классификации
(ЕСОС), оценено сверху максимальное число исправленных ошибок
при добавлении новой дихотомии, доказана NP-трудность добавления
дихотомии, оптимальной по числу исправленных ошибок.
5. Создан комплекс программ и проведены эксперименты, подтверждающие применимость предложенных алгоритмов на реальных практических (модель двигателя, распознавание цифр, диагностика сердечных заболеваний и др.) и модельных задачах.
Результаты, полученные в работе, показывают перспективность данной
темы для дальнейшего исследования.
Публикации соискателя по теме диссертации:
1. Рязанов В. В. О восстановлении пропущенных значений в таблицах
данных // Труды 55-й научной конференции МФТИ. Управление и
прикладная математика. Т. 2 (19–25 ноября 2012). – М. : МФТИ, 2012.
– С. 116.
2. Рязанов В. В. О решении задач классификации с большим числом
классов // Труды 56-й научной конференции МФТИ. Управление и
прикладная математика. Т. 2 (25–30 ноября 2013). – М. : МФТИ, 2013.
– С. 152–153.
3. Рязанов В. В. Об одном способе оптимизации метода ЕСОС при решении задач классификации // Труды 58-й научной конференции МФТИ.
Секция информатики. (23–28 ноября 2015). – М. : МФТИ, 2015. – 2 с.–
Режим доступа: http://conf58.mipt.ru/static/reports_pdf/553.pdf . – (Дата
обращения 01.09.2018)
4. Рязанов В. В. Об оптимизации билинейных форм в задачах классификации // Труды 59-й научной конференции МФТИ. Секция информатики. (21–26 ноября 2016). – М. : МФТИ, 2016. – 2 с. – Режим доступа:
http://conf59.mipt.ru/static/reports_pdf/2754.pdf. – (Дата обращения
01.09.2018)
5. Рязанов В. В. О распознавании пропущенных значений признаков при
решении задач классификации // Труды 60-й Всероссийской научной
19
конференции МФТИ. Прикладная математика и информатика. (20–26
ноября 2017). – М. : МФТИ, 2017. – С. 70–71.
6. Ryazanov Vladimir V., Ryazanov Vasily V. Classification of Incomplete
Data // Information Models & Analyses, 2013, Vol. 2, N. 3, P. 203–211.
7. Dokukin A. A., Ryazanov V. V., Shut O. V. Multilevel models for solution
of multiclass recognition problems // Pattern Recognition and Image Analysis, July 2016, Vol. 26, N. 3, P. 461–473.
8. Ryazanov V. V. Optimisation of multiclass supervised classification based
on using output codes with error-correcting // Pattern Recognition and Image Analysis, April 2016, Vol. 26, N. 2, P. 262–265.
9. Ryazanov V. V. An approach for training data reduction using bilinear form
optimization // Information Content and Processing, 2016, Vol. 3, N. 4, P.
357–367.
10.Рязанов В. В. Поиск информативных подмножеств признаков и объектов в задачах распознавания по прецедентам // Информационное обеспечение математических моделей: сб. науч. тр. –М. :МФТИ, 2017, С.
91–100.
11. Журавлев Ю.И., Рязанов В.В. О решении задач распознавания по прецедентам при большом числе классов // Доклады Академии наук, 2017,
T. 476, № 5. С. 489–491.
12. Yu. I. Zhuravlev, V. V. Ryazanov. Solution of Instance-Based Recognition
Problems with a Large Number of Classes // Doklady Mathematics, 2017,
Vol. 96, N. 2, P. 488–490.
13. I.B. Petrov, V.V. Ryazanov. Missing data imputation based on stochastic
neighbor embedding // Proceedings of the International Conference on Pattern Recognition and Artificial Intelligence. 2018. Monreal, Canada. P.
698–701. – Режим доступа: https://users.encs.concordia.ca/~icprai18/
ICPRAI%202018%20Proceedings.pdf. – (Дата обращения 01.09.2018)
20
РЯЗАНОВ ВАСИЛИЙ ВЛАДИМИРОВИЧ
РЕШЕНИЕ ЗАДАЧ ВОССТАНОВЛЕНИЯ ПРОПУЩЕННЫХ
ЗНАЧЕНИЙ ПРИЗНАКОВ И МНОГОКЛАССОВОЙ
КЛАССИФИКАЦИИ
Автореферат
Подписано в печать 11.10.2018. Формат 60 × 84 1/16. Усл. печ. л. 1. Тираж 100
экз. Заказ № 412.
Федеральное государственное автономное образовательное учреждение высшего образования
«Московский физико-технический институт (государственный университет)»
Отдел оперативной полиграфии «Физтех-полиграф»
21
Документ
Категория
Без категории
Просмотров
8
Размер файла
6 996 Кб
Теги
решение, восстановлен, пропущенную, признаков, многоклассовому, классификация, задачи, значение
1/--страниц
Пожаловаться на содержимое документа