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

• Рязанов, Василий Владимирович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Рязанов, Василий Владимирович

Введение..........................................................4

Глава 1. Восстановление пропущенных значений в табличных данных...11

1.1 Обзор существующих подходов восстановления значений

признаков...................................................11

1.2 Локальный метод восстановления пропущенных значений.....13

1.3 Глобальный метод восстановления пропущенных значений....21

1.4 Метод восстановления пропущенных данных, основанный на серии

задач классификации.........................................25

1.5 Метод восстановления пропущенных данных, основанный на

условном сходстве объектов..................................31

Глава 2. Многоклассовая классификация на основе дихотомических подзадач.........................................................37

2.1. Обзор существующих подходов............................37

2.2. Взвешивание дихотомий и учет весов при распознавании...41

2.2.1. Использование точности дихотомии в качестве весового

коэффициента............................................41

2.2.2. Использование F-меры дихотомии в качестве весового

коэффициента............................................45

2.2.3. Взвешенная классификация на основе списков точностей... .48

2.2.4. Взвешивание дихотомий на основе максимизации

межклассового зазора...................................49

2.3. Формирование дихотомий в схеме ECOC....................51

2.3.1. Общая схема локальной оптимизации дихотомии.....51

2.3.2. Оптимизация кластерного индекса.................54

2.3.3. Оценка максимального числа исправленных ошибок при

добавлении новой дихотомии.............................59

Глава 3. Эксперименты............................................64

3.1. Исследование подходов к восстановлению пропусков.......64

3

3.1.1. Восстановление признаков на модельной задаче.....64

3.1.2. Восстановление признаков на задаче “wine”........66

3.1.3. Восстановление признаков на задаче ”home”........67

3.1.4. Восстановление признаков на задаче “image”.......68

3.1.5. Восстановление признаков на задаче “heart”.......69

3.1.6. Восстановление признаков на задаче “iris”........70

3.2. Экспериментальное исследование задач многоклассовой классификации.................................................72

3.2.1. Исследование задачи распознавания рукописных цифр.72

3.2.1. Исследование модельной задачи....................81

3.2.2. Исследование задачи диагностики двигателя........92

Заключение........................................................100

Список литературы.................................................101

4

ВВЕДЕНИЕ

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

Общая характеристика работы

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

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

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

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

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

5

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

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

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

6

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

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

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

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

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

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

7

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

Цели и задачи исследования

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

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

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

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

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

Научная новизна

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

8

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

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

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

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

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

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

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

9

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

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

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

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

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

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

5. Создание комплексов программ и практическая апробация,

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

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

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

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

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

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

10

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

11

ГЛАВА 1. ВОССТАНОВЛЕНИЕ ПРОПУЩЕННЫХ ЗНАЧЕНИЙ В ТАБЛИЧНЫХ ДАННЫХ

Для начала сформулируем постановку задачи восстановления пропущенных значений в табличных данных. Пусть дана выборка А, которую можно представить в виде таблицы w х и, где w - число объектов, а и - число признаков. Пропущенные значения в выборке будем обозначать общепринятым сокращением AW (от англ. “Not a Number”). Задача восстановления пропущенных данных состоит в том, чтобы найти значения у,, которые можно поставить на место AW в таблице так, чтобы новая выборка (или новые значения у,) оптимизировали некий критерий. Отметим, что характер самих прочерков нас не интересует. В общем случае у, могут быть любой природы (числа, текст, аудио, ... ), но в настоящей работе мы ограничимся случаем вещественных чисел, как наиболее общем и распространенном.

В работе предложено 4 различных подхода к восстановлению пропущенных данных, в ходе данной главы каждый из них будет подробно описан.

1.1. Обзор существующих подходов восстановления значений признаков

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

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

12

самых популярных решений. Существующие подходы принято делить на «marginalization» и «imputation». Некоторые исследователи выделяет третий тип [15] «projection», но в общем случае его можно рассматривать как частный случай imputation.

В случае «marginalization» или «skipping incomplete objects» неполные описания просто исключаются. В результате получают выборки полных описаний [15]. В данном случае, очевидно, много информации может быть потеряно. Практика это подтверждает: в большинстве случаев стратегия marginalization или использования простых статистик уступает в качестве более сложным методам [16].

В следующем подходе «imputation» наиболее приемлемые значения признаков оцениваются по всей выборке. Общая методология «imputation» использует среднее по выборке, медианы или случайный [15], [17]. Существует класс методов, основанных на ближайших соседях [18]. В работе [19] используется алгоритм ближайшего соседа, существуют так же подходы, основанные на k-ближайших соседей [20]. Zhang [21] предложил метод «partial imputation». Неизвестные значения оцениваются по полному описанию объекта в малой окрестности неполных описаний. В качестве плюсов данных подходов стоит отметить что методы ближайших соседей являются непараметрическими.

В работе [22], Honghai исследовал «imputation»-подход на базе метода опорных векторов [23] и провел его сравнение с заменой прочерков средними, медианами, средними последующих двух значений и методом ближайшего соседа. При этом метод опорных элементов показал наивысшую точность.

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

13

Для восстановления пропущенных значений возможно использовать статистические подходы: заполнение пропусков на основе принципа максимума правдоподобия (EM-алгоритм) [15]. Недостатком его является низкая скорость сходимости при большом числе прочерков. Delavallade и Ha [24] предложили подход, использующий энтропию для оценки неизвестных значений. Другой популярный подход называется Full information maximum likelihood (FIML, полная оценка максимального правдоподобия) [25]. Данный алгоритм работает путем оценки функции правдоподобия для каждого отдельного объекта, использует все доступные объекты - как с пропущенными значениями, так и в полном признаковом пространстве.

На текущий момент не существует стандарта «правильного» восстановления пропущенных значений признаков. В некоторых задачах лучшее поведение демонстрируют статистические методы, в некоторых задачах эффективнее исключить пропущенные объекты. Чем больше разнообразие доступных методов, тем выше шанс что один из них успешно решит задачу. В диссертационной работе предложены и описаны 4 новых подхода к восстановлению прочерков, при этом все подходы имеют разную природу: вероятностную (SNE подход, раздел 1.5), метрическую (раздел 1.2) и др. В ходе экспериментов демонстрируется, что в ряде случаев предложенные подходы превосходят по качеству существующие.

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

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

14

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

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

минимуму некой заданной изначально метрики расстояния, например

Р(х,.х,) =

р

Е(л^- л^) р, р .

Г=1

По этим соседям нашего объекта считается среднее значение признака ., которое обозначим л^)*. Так как соседи объекта и их значения могут

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

л^) = л^-1) + 0(л^-1) * -л^-1)). Параметр 0 < Э < 1, как принято в методах оптимизации, назван Элиной ^аса, а сам локальный подход имеет сходство с методами сраЭиен^носо спуска с постоянной Элиной ^аса, где вместо градиента используется вектор, направленный в сторону среднего значения. На рисунке 1.1 приведена иллюстрация шага алгоритма.

15

Рис 1.1. Схема локального шага

Алгоритм восстановления пропущенных значений может быть смнлронньш и иослеЭоб<7/иельныз4. При синхронном алгоритме после каждой итерации меняется значение всех значений, где были пропуски, а при последовательном алгоритм работает с каждым пропущенным значением по очереди.

Алгоритм локального восстановления признаков (синхронный)

Шаг 0. Для всех /, у : х = А<тА выполняем начальную инициализацию.

Инициализация может быть по среднему значению признака jr = А<тА), по медиане х = /игА/<тл(т,^ : ЛА А) или

по случайному значению jc = Аб/А). Выбор

О < ^ < 1 - параметра затухания, -числа соседей и критерия остановки.

Шаг 1. Для всех /, /: х = АяА выполняем итерационный сдвиг:

Шаг 2. Выполняем шаги 1 до тех пор, пока не сработает критерий остановки. Среди возможных критериев: максимальное число

16

итераций А, затухание изменений

У л("

7, = АоК

или

<

у 1л^^) - л^^-1)12

2—7 I ^7 77 I

7 ,.:л. = АоА

< .

Алгоритм локального восстановления признаков (последовательный)

Шаг 0. Для всех 7,7: = АоА выполняем начальную инициализацию.

Инициализация может быть по среднему значению признака

л. = ^еон(л^.: л^. АоА), по медиане у. = ^е^7он(л^.: л^. АоА) или по случайному значению л. = тон^о^(л^.: л^. АоА). Выбор 0 < 0 < 1 - параметра затухания, -числа соседей и критерия остановки.

Шаг 1. Выбирается 7,.: л. = АоА. Если таких значений нет, то завершаем

алгоритм.

Шаг 2. Для выбранного 7,.: л. = АоА выполняем итерационный сдвиг:

+ 0( Е-1)*

Шаг 3.

Выполняем шаги 2 до тех пор, пока не сработает критерий

остановки. Среди возможных критериев: максимальное число

итераций А, затухание изменений л^) - лЕч < или

После срабатывания критерия остановки

переходим на шаг 1.

Для последовательного локального алгоритма восстановления в рамках

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

Теорема 1.1. Чмслоытя нослеЭоно^ельнос^ь {л^}, / = 0,1,2... нооо^онобленныл значений н^мзноко нослеЭоно^ельны.п локольньш .ле^оЭо.п м.лее^ конечный

нреЭел.

17

Обозначим исследуемый объект х0, а значение признака х0у. Обозначим в зависимости от итерации / значение признака как хО^. Остальные объекты выборки обозначим x1,..., х^.

Обозначим метрику расстояний между объектами через

Р(х,'х.) = f

Е(х,^- х.^) f -

V=1

Рассмотрим случай эвклидовой метрики (f = 2), для

других метрик рассуждения аналогичные.

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

Vx, е X),х^ % X) ^^(х0^),х,) <^(х0^),х^). Если существует несколько одинаково близких объектов, то выбирается случайное подмножество нужного размера. Среднее значение признака по данным соседям обозначим х^)* =1 Е Ху.

х, ех(')

Распишем формулу расстояния:

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

х^ = co%s7, Vv у и х,^ = , Vx, х0, то формулу можно переписать:

^(х0^), х,) (Х0- х,у )2 + = CO%S7, Х,у = . Заметим, что = 0 .

Изобразим все объекты в координатах у, где х, (^) = х,у, х, (у) = ^,

18

Рис. 1.2. Расстояние между объектами в новых координатах

Исходя из формул, полученных выше следует что расстояние в старых координатах равно расстоянию в новых координатах j,y:/?(x^,x.)^^(x^,x.). Далее без ограничения общности будем рассматривать его как /?(х^,х.). Обратим внимание, что в новых координатах в схеме в зависимости от номера итерации может поменять только лишь значение х^. Рассмотрим возможные случаи.

Случай 1: х^ = х^. Без ограничения общности положим / = 0. В таком случае х^ = х^ = х^ + 3(х^* -х^) 3(х^* -х^) = 0х^* = х^.

Так как х^ х^ => => х^" = х^* х^ х^. Это означает что множество

соседей не поменялось после этой итерации, значит среднее значение признака по ним не поменялось, значит если х^ совпадало с xjo* и следовательно с х^*, то Х(<у=х^=х^*. Повторяя схему получим x^=x^\V/?>0. Такая последовательность является константой и, следовательно, сходится.

Случай 2: х^>х^\ Без ограничения общности положим / = 0. Так же заметим, что случай х^ < х^ аналогичен с точностью до замены знаков.

После замены номера итерации / = 0 получаем: х^ < х^. Докажем, что х^? < х^. Возможны 2 случая - множество ближайших соседей изменилось или нет. Рассмотрим каждый случай по отдельности.

19

Случай 2.1: X = X Множество соседей не изменилось.

+3(х^°^* - < Хо7 х^°^* < ^о0;^. Так же верно х(°)* < х^, потому что

Х01; - х^* = хо^^ + 3(х^ - хоо^ - х^* = (1 - 3)хоу + (3 -1)х^ = (1 - 3)(хо^^ - х^) > о .

Так как множество соседей не поменялось (X= X^), то и центр их не поменялся: х(.°)* = х^*.

хо^ = хо1; + 3х^* - хо1^) хо^2^ - хо^.^ = 3х(°)" - хо^.^) < о. Это и означает, что хо^ < х^1..

Случай 2.2: XX(°\ Обозначим объекты, которые появились и которые ушли из множества соседей как: X +) = X \ X X = X \ X . Докажем, что для

Vx, е XXе Xх. < х,.

Допустим 3X, е XXе Xх. > х^.. Так как X, е X),X^ е X

^2(X^),X,) <^^(хо1),X),^^(хоо),X,) >^^(хоо),X) (возведение метрики в квадрат не

меняет знак неравенства, так как она положительна)

^2(x01), X,) < ^2(x01), X^) д2+(хо1; - х. )2 < +(хо1; - х^. )2

^2(x0о),X,) > ^2(x0о),XД2 + (хо^) -х.)2 > Д2 + (хо^^ - х^.)2

Сложим 2 неравенства и сократим Д2, Д2

(хо1; - х. )2+(хо^) - х^. )2 < (хо1; - х^. )2+(хо^) - х. )2

(хо?- х.- хо?+х..)(2 хо?- х.- х..) <(хо°.^- х.- +х..)(2 хо°.^

(х..- х.)(2 хУ - х.- х..) <(х..- х.)(2 хо^^- х.- х..)

о <2( х^.- х.)(хо^)- х^1^

- х.-

х..)

Так как хо^..^ > хо^^^ х^.. > х.. Противоречие с предположением

х. > х^, значит

утверждение VX, е XXе Xх. < х^. верно.

х("'* = i X х,.=1

3"=1 X х,=* 2 X х, + X

* X, е^^ *

Из этого следует, что х^* < х^*. Это верно, потому что

X х. + ________

X, е^^ X е^о) uX(1) J

_ . _ х.

2 X е^+) X еД^ uX(1) J

X х. = 1 X х.+ ^

............. * XeX(-)

1 = * X х. +

* X eX(+)

9

20

Мощности множеств X+), Xсовпадают (так как равны мощности

lx= lx^'1 = %), а Vx, е X(+), хе Xл. < л^., следовательно 1 Е л. <1 Е л..

% х,еХ(+) % х, еХ(-)

Значит верно. Исходя из него получаем:

лу = лу + ^(л^* - л^) л0? - л0. = 0л^* - л0^) <^(л^* - л^) < 0. То что л^* - л^1; < 0

было показано ранее.

Случай 2.2 рассмотрен, это означает что верны утверждения:

) > л^/+1) л/+1) > л^/)

*^0. *^0. *^0 . *^0 .

) < л^+1) л^^+1) < л)

*^0. *^0. *^0 . — *^0.

Осталось показать, что min л. < л0. < max л., V/. Действительно, изначальная

инициализация при / = 0 попадает в данный диапазон. Далее справедливо, что min л. < л^)* < max л., V/, следовательно их взвешенно среднее л0. = (1 -0)л0. + 0л(.

лежит тоже в нужном диапазоне. Проводя данные рассуждения далее получаем

min л.. < л0/;' < max л,., V/.

, .7 0 J , .у

Так как мы рассмотрели случаи при произвольном / , то по индукции

легко показать:

л0^ = л0. л0^ = л0/;, V/ е N

л0'? < л0? л0Г^ < л0 V/ е л0'; > л0^^ л0^ > л0/;, V/ е N

Это означает, что последовательность л0у,/ = 0,1,2... монотонна и

ограничена (min л. или max л.), следовательно по теореме Вейерштрасса она

имеет предел. Теорема доказана.

Согласно теореме 1.1 для любого пропущенного значения л0. = XW числовая последовательность {л0.}, / = 0,1,2... сходится в терминах

математического предела.

21

1.3. Глобальный метод восстановления пропущенных значений

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

Список литературы диссертационного исследования кандидат наук Рязанов, Василий Владимирович, 2018 год

- — -

7

7

= ^7

л

7

4 случай. ' = ^, у = . Получаем

'1 ,'2

'17

Л

- i..

7

'1

2 - tog У

7 2 77

У - -J е "1

7 ^1 77

- -1

7

'1'2

Уе-^-Ч 7 )

0 + -------у

У е-S- -<11

7 '1

7

7 '1

7

Просуммируем 4 слагаемых вместе:

ал*

= - У ?,!- У 7<- У 7-,+ 7

^'1,'2 ' 1, у 1 ' 1 7^' 1

-У 7,

7 ^'1

Л

У)-7' 7'1 '1^ / V2

7 ^'1

7.

- У A|,1 7^ . В дальнейшем данное выражение для

7 '1

производной можно упростить, пользуясь фактом что сумма вероятностей равна 1: ^У = У 7,=1.

7^' 7^'

Исходя из этого перепишем выражение в первой компоненте: У р„7и= У7ч7.У7=У7ч7s (1+7'-Лч-)

'^'1,7 ^'1 '^'1 7^'1 '^'1

35

В третьем слагаемом есть двойная сумма по всем элементам. Но можно заметить, что X () является константой, которую достаточно вычислить

один раз. Получим финальное выражение:

дС

ат,,

,1,,2

;'1

;'1

,1

л

Л

\ 7' ^1

7

= X2(7', - )(( J.1K + - Ali (1 + - А, (I + 1,l„ )) .

; ^'1

Утверждение доказано.

Легко заметить, что

линейно по числу объектов в выборке. Также

следует отметить, что вероятности достаточно вычислить лишь один раз для

всей таблицы, а в дальнейшем они не меняются.

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

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

Шаг 0. Инициализация величин с,, ст, для всех т, e X. Вычисление величин

^7,. Заполнение пропущенных данных начальными

величинами (средние, медиана или случайная). Вычисление С(0).

Выбор критерия остановки алгоритма.

Шаг 1.

Вычисление всех частных производных

аС (( У,)) ат,

и формирование

градиента VC.

36

Шаг 2. Выполнение шага в сторону антиградиента с использованием техники «момента» (англ. Momentum) для лучшей сходимости (7"'=< У,/'-1)+ 7^ + .(.) ((,J"-1) Ҷ ,у -2))

Шаг 3. Если выполнен критерий остановки, то алгоритм завершается. Иначе переходим на Шаг 1.

Обратим внимание на формулу момента на Шаге 3. Здесь 7 есть величина шага, а cr(t) - коэффициент инерции. Таким образом, вектор всегда смещается не ровно в сторону антиградиента, а немного отклоняется в сторону разницы двух предыдущих значений. В этом и заключается суть оптимизационных подходов, использующих «момент» [32], которые так же применяются в оригинальных алгоритмах SNE и t-SNE.

37

ГЛАВА 2. МНОГОКЛАССОВАЯ КЛАССИФИКАЦИЯ НА ОСНОВЕ ДИХОТОМИЧЕСКИХ ПОДЗАДАЧ

2.1. Обзор существующих подходов

Рассмотрим подробно постановку задачи многоклассовой классификации и традиционные подходы, основанные на Error-Correcting Output Codes. Дана обучающая выборка А = {x1,x2,...,xw}, x, e , , = wy-1 +1,wy-1 + 2,...,wy, w0 = 0, w^ = w, у = 1,2,...,/. Размер выборки составляет w объектов, количество классов равно /. Считаем, что объекты упорядочены по номеру класса, то есть первый класс представлен объектами с номерами , = 1..w1, второй номерами /' = w1 + 1..w2 и так далее. В целом при классификации объекты могут быть различной природы, но будем считать, что все объекты x, e в рамках рассматриваемых задач.

Задача классификации состоит в том, чтобы сопоставить произвольному объекту x e некую метку класса из уже имеющихся /. Сопоставление происходит исходя из разных эвристик и разных подходов.

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

Заметим, что многие классификаторы способны решать задачу многоклассовой классификации без дополнительных схем, сводящих задачу к серии бинарных. Например, алгоритмы -ближайших соседей [33], решающие деревья [34], алгоритмы АВО [26] могут решать задачу сразу. С другой стороны, линейные классификаторы такой способностью не обладают [25]:

38

логистическая регрессия [35], линейный дискриминант Фишера [36], метод опорных векторов [23] и др.

Самыми популярными подходами, основанные на сведении многоклассовой задачи классификации к серии бинарных классификаций являются: 1-vs-all (каждый против всех), 1-vs-1 (каждый против каждого), Error Correcting Output Codes (коды, исправляющие ошибки).

Подход 1-vs-all заключается в том, что формируется / бинарных задач классификации. В рамках ,' -й бинарной задачи классификации происходит формирование двух макроклассов: Х0 = Х,, Х1 = Х1 ... Х,-1 Х,+1 ... Х^.

,+1

На этапе обучения обучается / соответствующих бинарных классификаторов, а

на этапе классификации объекта x e X" решается / задач распознавания. На основе вектора полученных ответов cr(x) (его называют еще коЭоеьш слоео^)

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

ближе всего по расстоянию Хемминга [37].

Подход 1-VS-1 заключается в формировании (^2 1) бинарных

классификаций: Х0 = Х,, Х1 = Х7, ,' < 7;,', 7 e U. При данном подходе в каждой

бинарной задаче задействованы не все исходные классы, а лишь два, все остальные временно исключаются. На этапе обучения обучаются (^2 1)

бинарных классификаторов, а на этапе распознавания решаются эти же (^ 2 1)

задач классификации. По полученному кодовому слову cr(x) выбирается один

из исходных классов.

Подход Error-Correcting Output Codes [38] является развитием подходов 1-vs-1 и 1-vs-all. Суть подхода так же заключается в том, что исходной классификации с / классами Х7,7 = 1,2,..., / ставится в соответствие X (X не

39

более чем 2^ -1) дихотомических задач с классами А7 = Х ^А7 ^...^А? и

X/ = и и... и и X/ = ^, п X/ = 0 .

Введем для каждого класса А? бинарный вектор а, = (cr,i,cr,2,...,^,y), =1 при X, e X/ и = 0 иначе, матрица А = (с^ называется кодовой. В итоге, каждому классу А2 будет поставлен в соответствие вектор <2^ е {0,1}/= 1,2,...,A. сг^=1, если класс А? входит в первый класс / - й дихотомии, и = 0, если класс А? входит во второй класс / - й дихотомии. Этап формирования дихотомической матрицы называется коЭм/зобйнмап. Пример дихотомической матрицы изложен в таблице 2.1.

X

X

X

X

X

0 1 1

0 0 1

0 1 0

1 0 0

1 1 1

Таб. 2.1. Пример дихотомической матрицы для 5 классов

Следующий этап решения задачи классификации ЕСОС является этапом ЭекоЭм/?об<тнмя, то есть этапом принятия решения о классификации нового объекта х е А".

1. Для X решается А дихотомических задач и вычисляется вектор а(х) = (суДх),сУз(х),...,а^(х)), где аДх)/ = 1,2,...,А- результат классификации х дихотомическим алгоритмом № /.

2. Объект х относится в класс А?, согласно минимума некого критерия minr(a,o/).

40

Рассмотрим вопрос выбора критерия во втором пункте. В качестве критерия можно использовать разные метрики, такие как Евклидова, L1, L2 и прочие, но на практике чаще применяется расстояние Хемминга:

У=1

(2.1)

Соответственно классификация происходит по минимуму расстояния

Хемминга от кодового слова объекта до кодового слова класса:

x —^— X,,/': г (a(x), а,) = min г (а (x), а у)

(2.2)

В настоящее время предложено много различных модификаций традиционной схемы ECOC. Популярны троичные схемы [39] в которой матрица состоит из -1, 1 (обозначающие два макрокласса) и 0 (классы исключенные из бинарной классификации). Как естественное их развитие представлены и ^'-арные схемы кодирования [40]. Ряд исследователей исследовал вопросы разделимости столбцов и строк внутри кодовых матриц, вводя меры разделимости (diversity) для пар бинарных векторов [41], [42], [43]. Существуют способы построения дихотомической матрицы по аналогии с бинарными решающими деревьями [44].

Так как в общем случае построение оптимальной дихотомической матрицы является NP-трудной задачей, есть подходы, сводящие бинарные кодовые слова к непрерывным. Подобную технику использует многоклассовый SVM [46], хотя эксперименты не демонстрируют превосходство данного подхода по времени или качеству.

Несмотря на такое обилие модификаций ECOC до сих пор популярны 1-vs-1, 1-vs-All [45] и традиционная схема ECOC. Отметим особенности данного подхода и факторы, благоприятные для классификации.

1. Число дихотомий можно взять относительно небольшое относительно

числа классов, но удовлетворяющее неравенству 2^-1 -1 > .

2. В качестве эталонных дихотомий (Х0 и Xf1, у = 1,2,...,) надо брать такие, чтобы относительно данных двух классов было хорошее распознавание, т.е. брать дихотомии осознанно, а не случайно (см. рисунки 2.1, 2.2).

41

3. Набор эталонных дихотомий надо брать так, чтобы кодовые векторы

были максимально удалены друг от друга в совокупности для всех пар классов Л? и .

4. Задача классификации на два класса как правило решается проще, чем задача классификации на большее число классов.

5. Некоторый класс может содержать мало объектов при обучении. Это негативный фактор, если мы строим алгоритм сразу для всех классов, или индивидуально для данного класса. Но это становится несущественным, если данный класс входит в представительное объединение с другими классами. Класс может быть «плохо отделим» от других классов, но «хорошо отделим»

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

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

есть макроклассы имеют большее описание чем исходные классы.

7. Дихотомии имеют различную информативность.

На рисунках 2.1, 2.2 проиллюстрированы случаи

«естественного» и

«неестественного» формирования дихотомий.

Рис. 2.1. Создание хорошей

Рис. 2.2. Создание плохой

дихотомической задачи

дихотомической задачи

2.2. Взвешивание дихотомий и учет весов при распознавании

2.2.1. Использование точности дихотомии в качестве весового

коэффициента

42

Исходный подход ЕСОС не учитывает влияние качества дихотомии на результат классификации. Но при этом разные дихотомии могут совершать разное число ошибок во время распознавания и обучения. Тем самым, если дихотомия с номером у часто ошибается во время бинарной классификации, то ее вклад а^(х) в общее кодовое слово а(х) = (с^(х),сУз(х),...,а^(х)) для объекта X часто будет ошибочным. Ошибка в компоненте сг(х) может повлечь за собой неверную классификацию объекта х в целом.

Введем обозначение х—^X,(d),z = 0,l, которое обозначает

классификацию объекта х дихотомией d в макрокласс A? (d).

Определение 2.1. .Зероятмностмью ир<?(3йльной P(d) Эмхотиапми

d буЭап н<т?Ы(3<77йь величину

Р(х Хр (d) ] х е Хр (d))P(x e Хр (d)) + Р(х (d) ] х e (d))P(x e (d)).

Приведем пример следующей дихотомической задачи (таблица 2.2). Пусть дихотомии d] и d^ имеют вероятности правильной классификации P(dJ = P(d2) = l, то есть классификаторы, которые соответствуют данной дихотомии никогда не ошибаются. Пусть P(dg) = 0.5. Разбиение исходных классов данными дихотомиями проиллюстрировано на картинке ниже.

0 0 1

1 0 1

0 0 0

1 0 0

0 1 0

Таб. 2.2. Пример дихотомической матрицы для 5 классов

43

Исходя из того, что E(d3) = 0.5 следует, что для половины объектов x е X1 кодовое слово a(x) = (^1(x),^2(x),...,^^(x)) будет неверным а(х) = (0,0,0) вместо верного кодового слова a(x) = (0,0,1) для класса X1, значит согласно минимуму расстояния Хемминга данные объекты будут классифицированы в класс Х3 (и наоборот половина объектов x е Х3 будут классифицированы в класс X1). Аналогичные рассуждения верны и для пары классов X2, X4.

Введем схему, которая позволит косвенно учитывать влияние вероятности правильной классификации дихотомии во время декодирования. Пусть дана дихотомия d с вероятностью правильной классификации X(d). Если x ——- X1 (d), то с вероятностью P(d) x е X1 и с вероятностью 1 - P(d) x е Xf0. Аналогично для случая x —- X0 (d).

Модифицируем вклад данной дихотомии в формулу для расстояния Хемминга: если (x) ^җ,^ для класса x е X,, то в формулу для расстояния Хемминга добавим не 1, а X(d), так как дихотомия могла и ошибиться. Если

сҗ (x) = сҗ то добавим 1 - X(d) вместо 0.

Таким образом, итоговая формула для модифицированного расстояния

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

г(а(x), а) = V , где

У=1

^1 - р,, Җ^), = ,

р,, иначе

(2.3)

Для краткости здесь и далее будем использовать обозначение: р, = X(d,).

Соответственно классификация происходит по минимуму модифицированного расстояния Хемминга аналогично случаю (2.2).

x ——— X, д': г (a(x), а,) = min г (а (x), а 7) = min "V г, (2.4)

7 7'

В самом худшем случае, когда р, = 0.5 вклад дихотомии будет одинаков при любом предсказанном ответе, то есть данная дихотомия никак не будет

44

влиять на принятие решения на многоклассовом уровне. При решении практических задач вероятность P(d,) оценивается по точности дихотомии.

Определение 2.2. j* > j7,7 = 1,2,...,X. Задача классмфмка^мм е

ЕСОС назыеае^ся ираемльном, еслм мз j*7 > j7,7 = 1,2,...,X слеЭуе^ P* > P, аЭе P*, P - ^очнос^м расиознаеанмя иосле м Эо ои^м^мза^мм.

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

Рассмотрим случай когда / = 4 и дихотомическая матрица выглядит следующим образом (таблица 2.3).

dl d2 d3 d4

K1 1 0 0 0

K2 0 1 0 0

K3 0 0 1 0

K4 0 0 0 1

Таб. 2.3. Пример дихотомической задачи на 4 класса

Пусть априорные вероятности классов Р( Х,) = 0.25,i = 1..4. Пусть каждая дихотомия всегда тождественно предсказывает 0, из этого получаем ее качество:

V/ Р*7 = Р(т ——Х0 ] т e 0)Р(0) + Р(т ——1 ] т e 1)Р(1 ) = 0.75

45

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

/

Р* = XР(-------Х, ] т e Х, )(Х, ) = 0.25

,=1

Пусть теперь дихотомии разбивают классы так же, но работают по-другому, а именно: Р(т ———Х0] т e 7^0) = 0.5, Р(т ———7^1] т e Т^1 ) = 1, 7 = 1..4. Для данного примера после подсчета вероятностей имеем: V7 — Р = Р(т ——— Х0] т e ^0)Р(Х0) + Р(т ——— ^1] т e ХТ1)Р(Х) = 0.625, но /

Р = XР(т-------Х, ] т e Х, )Р(Х, )^ 0.46.

,=1

Получается: j,7' = 1..4, но P* > P, что демонстрирует что данный

случай является примером неправильной задачи.

2.2.2. Использование F-меры дихотомии в качестве весового коэффициента

Зачастую такой показатель как accuracy (который может использоваться как аппроксимация вероятности классификатора) является не лучшим критерием «качества» работы распознавания. Достаточно рассмотреть пример с сильно несбалансированными классами: пусть априорная вероятность класса Х0 равна 95%, а класса Х1 - 5%. Пусть обучен классификатор, который предсказывает все объекты по максимуму априорной вероятности, то есть в класс Х0. Accuracy для такого алгоритма будет равна 0.95, что считается довольно высокой величиной. Но в то же время практической пользы от алгоритма абсолютно не будет, так как он не производит никакую работу по разделению объектов двух классов. Тем самым возникает вопрос о развитии критерия «качества» дихотомии.

46

Вместо точности можно рассмотреть другие существующие метрики бинарной классификации. К популярным относятся '-Х X' [60], X/?gX//s.s, /V?-X XРгесА/ои, Аеса//, Ғ-Ўиера [61]. Рассмотрим вкратце каждую из них.

Первые 3 метрики (Roc-Auc, LogLoss, PR-Auc) работают из предположения, что классификатор предсказывает вероятности (оценки), а не номера классов. В текущей постановке метода ЕСОС рассматриваются классификаторы, которые предсказывают номера классов, поэтому опустим данные метрики из рассмотрения.

Рассмотрим бинарный классификатор, работающий на классы (Negative) и A) (Positive). Если объект v е А), и классификатор предсказал для него класс А),, то такая ситуация называется True-Negative (истинноотрицательный). Аналогично True-Positive (истинно-положительный) для класса X). Изобразим это наглядно в виде картинки на рисунке 2.3:

X С х е

X!—

X!—

True Positive False Positive

Faise Negative True Negative

Рис. 2.3. Схема бинарных предсказаний

Обозначим количество Positve объектов через X),, Negative как Х\., True-

Positive, True-Negative, False-Positive, False-Negative как Л^,Л^,Л^,Л^у соответственно. Верны равенства: X), = Х'.^, + Х).,., Х\„. = Х).у, +

47

Определение 2.3. ^еса// (Тгме-Розч'бте РаУе, млм иолно^а? ес^ь селмчмна

Лтр

^о ес^ь соо^но^енме серно иребсказанныл объек^ос класса X1 к обрежу

чмслу объек^ос класса X1.

Определение 2.4. Ркес/'з/'оа (млм ^очнос^ь) ес^ь соо^но^енме

ЛТР

Л^р + Лрр

^о

ес^ь соо^но^енме серно иребсказанныл объек^ос класса X1, к обрежу чмслу

объек^ос, которые былм иребсказаны к классу X (как серно, ^ак м о^мбочно?

кеса// * ркес/'з/'оа

Определение 2.5. т-жера ес^ь селмчмна 2------------------------

кеса// + ркес/'з/'оа

Метрики Recall и Precision хороши в специфических задачах (где нужно минимизировать конкретно ошибки 1-го или 2-го рода), но существуют ситуации, где хороший Recall или хороший Precision не гарантируют хорошую работу бинарного классификатора.

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

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

классификации по расстоянию Хемминга.

Л

к(а(x), а) = V к,, где

У=1

1 р, ^(x), =

, иначе

(2.5)

Л

x —^— X,, ,: к (а(х), а,) = min к (а (x), а7) = min "V к (2.6)

7 7 1=1

Для краткости здесь и далее будем использовать обозначение F-меры дихотомии: Д = Р (d,).

48

2.2.3. Взвешенная классификация на основе списков точностей

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

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

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

Определение 2.6. ^а^рм^а W назыеае^ся ла^рм^ем симское ^очнос^ем, еслм

W = (

аЭе XJ-ло^нос^ь (колмчес^ео объек^ое) класса X., а

- >

hV

Xr =x: x

] = ]x: x d' >TX, x e X., X. Xесть количество объектов класса X., которые были отнесены в верный бинарный класс (X) '-й дихотомией на этапе обучения. а. есть компонент кодовой матрицы дихотомий, который равен 0, если X. X0, и равен 1, если X. 7X,'.

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

Процедура декодирования выглядит в данном случае следующим образом:

г(а(xX а.) = , где

у=1

1 , ^(x), =

ЙЙ,, иначе

(2.7)

49

X

x ——— Х,,,': r(a(x),a,) = min r(a(x),a,) = min X (2.8)

7 7

2.2.4. Взвешивание дихотомий на основе максимизации межклассового зазора

Описанный выше подход ориентируется на качественную работу бинарных классификаторов, соответствующих дихотомическим задачам, но не учитывает информацию о том, какие классы были вместе сгруппированы дихотомией. Данный вопрос не менее важен, чем хорошо обученный классификатор. Большинство исследований (например [46], [47]) говорят о том, что хороший набор дихотомий должен удовлетворять следующим свойствам: дихотомии должны быть различны, кодовые слова должны быть различными. Но требование простой лишь различности кодовых слов является необходимым для того, чтобы в принципе решать задачу классификации, но не всегда достаточным для успешной точности. Кодовые слова для разных классов должны быть максимально удалены друг от друга, чтобы минимизировать ошибку в выборке класса, в случае отклонения от истины по расстоянию Хемминга [46]. Иными словами, если мы используем метрический критерий r (a,, a 7), необходимо максимизировать min r (a,, a 7) по всем парам классов ,', у'. Таким образом необходимо, чтобы минимальное расстояние между двумя различными кодовыми словами классов было максимальным.

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

Определение 2.7. Дзее^енньш расстоянием ^ешшинза шежЭу еед^орашм

X

х,y e {0,1}" с еесашм w e R" назыеае^ся еелмчмна XIту -

У=1

50

Опишем способ нахождения вектора весов. Введем параметры w,,,' = 1,2,..., X, характеризующие веса и параметр у e , характеризующий минимальный зазор между всеми возможными парами классов. Необходимо найти такой вектор весов w, чтобы параметр у был максимальным.

Задача оптимизации будет выглядеть следующем образом:

X

Xl%- - У;V^;^>^;^ = 1,...,/

7=1

X

X w7 = X, w7 > 0 (2.9)

7=1

у — max

Отметим, что данная задача является задачей линейного программирования. После решения задачи (2.9) решающее правило будет выглядеть следующим образом:

X

Г(a(XX a7 ) = Xl^(Х)? -^7'7^7

У=1

х

X

Х,,,': r(a(x), a,) = min r(a(x),a 7) = min X^(x)^

7 7 ti

(2.10)

(2.11)

На практике задача (2.9) решает еще одну проблему - отбор дихотомий.

Практические эксперименты показывают, что, как правило, большая часть

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

Более подробно эксперименты, демонстрирующие поиск весов и отбор на основании их дихотомий приведены в Главе 3.

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

51

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

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

следующий вид:

г(а(x), а7) = V , где

У=1

1 - р,, ^(x), = ^7,

р,, иначе

x ——X,, ,: г (а(х), а,) = min г (а (x), а 7) = min V гҗ

7 7 1=1

(2.12)

(2.13)

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

X> у;v^,= 1,...,/ j =1

X w7 = , w7 > 0 (2.14)

7=1

у max

где

^1 - Р,, ^,У = ^7,,

р,, иначе

г

,7,

В дальнейшем при классификации применяется модифицированное

решающее правило

x ——X,,,: г (а(х), а,) = min г (а (x), а 7) = min "V r7,w, (2.15)

7 7 1=1

2.3. Формирование дихотомий в схеме ECOC

2.3.1. Общая схема локальной оптимизации дихотомии

52

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

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

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

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

Опишем схему, позволяющую найти дихотомию удовлетворяющую тому или иному критерию. В их качестве можно рассматривать критерии, изложенные в разделе 2.2: вероятность, F-мера, списки точностей, а также

53

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

Алгоритм построения дихотомии с использованием локального критерия

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

Шаг 1. Рассмотрим итерацию под номером , (, > 0). Имеем текущую дихотомию d(у), подсчитанное значение 0 (d(;)). Рассматриваются векторы d(,) = (<^(,), <^2У),...,1 - б^,..., ^),' = 1../, для которых расстояние Хемминга до вектора d(у) составляет 1 (то есть отличающиеся ровно в ' -й компоненте). Рассматриваются только те векторы d(у), для которых выполнены такие же условия как для начальной точки и условие уникальности: дихотомия d(у) не встречалась при текущем запуске алгоритма. Обозначим допустимое множество индексов ', в которых можно сделать такие изменение через 0 с {1,2,...,/}. Вычисляются значения 0(d(;)) по

Шаг 2. Если max 0 (d(;)) > 0 (d(у)), то делаем итерационное изменение дихотомии: d(,+1) = d(^,'0 = argmax0(d(У)) и переходим на Шаг 1. А Если таких максимумов несколько, то выбирается случайный.

Шаг 3. Если max 0 (d(;) )< 0 (d(у)) или = 0, то алгоритм завершается, а d(;) становится искомой дихотомией.

54

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

2.3.2. Оптимизация кластерного индекса

Для оптимизации дихотомических алгоритмов возможна также и оптимизация внутренних кластеризационных критериев [49], [50] (их так же называют индексами). При решении задачи кластеризации возникает необходимость оценить качество ее работы. Так как кластеризация представляет из себя обучение без учителя (англ. unsupervised learning) это означает, что у объектов отсутствуют какие-либо метки классов. Данный факт существенно усложняет процесс построения метрики, но, несмотря на это, существует различные критерии оценки кластерного разбиения.

Теперь вернемся к рассмотрению задачи нахождения новой дихотомии. При добавлении новой дихотомии должны быть выполнены некоторые обязательные требования: дихотомия не должна состоять из одних 0 или одних 1, дихотомия или ее инверсия не должна быть совпадать с другой дихотомией. На этом необходимые требования заканчиваются и в остальном можно выбирать новую дихотомию свободно. Уже при числе классов / = 12 число дихотомий существенно возрастает: Л = 2/-1 -1 = 2047 и для быстрого поиска новых разбиений необходимо иметь возможность заранее оценивать разделяющий потенциал дихотомии.

Разделение дихотомии исходных классов на 2 макрокласса можно рассматривать как результат кластеризации на 2 кластера. Но, в отличие от кластеризации, дихотомия всегда содержит один из исходных классов целиком

55

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

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

и, = ]X,] - мощность, т.е. количество объектов, класса X..

m. = — X x -вектор, равный среднему арифметическому всех объектов класса и, xeX

X,. Определения даны для всех , = 1,2,...,.

I1 = {,}: X, e X^ 12 = {,}: X, е Х2, то есть I1,12 обозначают индексы

принадлежности классов к макроклассам X^ Х2. I1 12 = 0, I1 12 = {1,2,...,/}.

р 7 — Xи,m, ,у = 1,2 - средний вектор макрокласса.

XН ,eI,

,eI 7

В задаче поиска оценивания дихотомии на основе кластеризационных

критериев исследовались следующие индексы:

Определение 2.8. ХнЭексо.л ХбХ-НбХ /^7 у н^зые^е^ся (зелмчмнл

Определение 2.9. ХнЭексо.л /4Р/ н^зые^е^ся еелмчмнй

С = XIlx - PJI2 + X llx - Р^12 = (К1) + (К2)

xeK] xeK 2

Данные индексы можно использовать как метрику качества дихотомии, например, при методе локального поиска, описанного в разделе 2.3.1. Но сложность вычисления индекса Ball-Hall или Trace_W пропорциональна размеру всей выборке. В случае локального шага, где изменяется

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

56

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

Теорема 2.1. Лус^ь ену^ренний Эисиерсионный критерий ири разбиении ил Эел ^но^ес^ел К1, К 2 рллен:

и К1 К* = К1 А.,К2 К2 = К2 \ А., тогда верно:

У (К*) = У (К1) + X] ]х - ^1

хеА.

2 "Л mr- ^1

X + "г

;е!1

"г"]]mr - 2

X - "г

.е12

Доказательство.

и с ==---------------У (К *1) +

X ".+ ".

.е!1

1 *

-У(К 2)

г

X".-"

.е12

Пусть кластер А. из К2

переходит

в множество К1, т.е. К1* = К1 А.,

X ".m

К 2* = К 2\ А.. Тогда ^* =

".

X". ^1 (X".+".- "У)+".m.

1