Исследование методов комбинирования классификаторов в рамках теории свидетельств

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Федеральное государственное автономное образовательное

учреждение высшего образования

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

«Высшая школа экономики»

Факультет компьютерных наук

Основная образовательная программа

Прикладная математика и информатика

Курсовая работа

на тему: Исследование методов комбинирования классификаторов в рамках теории свидетельств

Выполнил студент группы БПМИ143, 4 курса,

Кузнецов Кирилл Львович

Научный руководитель:

профессор, доктор физико-математических наук,

Лепский Александр Евгеньевич

Москва 2017

Введение

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

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

В процессе выполнения, для достижения этой цели необходимо решить ряд определенных задач:

- изучить основы теории свидетельств и их применение в задачах агрегирования источников информации;

- реализовать модель агрегирования классификаторов в рамках теории свидетельств;

- сравнить полученные результаты с уже существующими техниками агрегирования классификаторов, а также с результатами, полученными одиночными классификаторами;

- модифицировать реализованную модель на предмет увеличения эффективности и уровня прогнозирования в целом.

Объектом исследования ВКР является приложение теории свидетельств к решению задачи классификации.

Предметом исследования ВКР являются одиночные классификаторы и их возможные комбинации.

В работе были использованы:

- 5 одиночных классификаторов (knn, SVM, RFC, NB, LR);

- 3 стандартных метода агрегирования классификаторов в ансамбль (Plurality vote, Simple weighted, Weighted majority vote);

- 2 метрики качества работы алгоритмов (Точность, AUC-ROC);

- функционал logistic loss;

- правилакомбинирования свидетельств Демпстера и Ягера;

- процедура дисконтирования свидетельств.

В качестве источника информации (базы данных для проведения исследования) использовался UCI Machine Learning Repository.

1. Основная терминология

1.1 Теоретическая часть

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

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

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

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

Классификатор - алгоритм классификации.

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

Метрика качества - Некая мера, позволяющая получить численное значение некоторого свойства ПО или его спецификаций.

Перед переходом к самим метрикам необходимо ввести важную концепцию ошибок для описания этих метрик в терминах ошибок классификации - матрица ошибок.

	y=1	y=-1
= 1	TP (True Positive)	FP(False Positive)
= -1	FN (False Negative)	TN (True Negative)

y - истинный ответ (класс к которому принадлежит объект), - предсказание классификатора

Точность - доля правильных ответов алгоритма

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

AUC-ROC - площадь под кривой ошибок. Кривая представляет из себя линии из (0,0) до (1,1) в координатах TPR и FPR.

Является устойчивым к несбалансированным классам и может быть интерпретирован как вероятность того, что случайно выбранный positive объект будет проранжирован классификатором выше, чем случайный negative.

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

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

1.2 Обзор литературы

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

Пусть N - количество объектов обучающей выборки X = , M - количество классов в множестве C = и K - классификаторов.

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

.

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

.

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

3. «Re-scaledweightedvote». Идеей этого метода является назначить нулевой вес классификатору, выдающему N/M или меньше правильных ответов на тестовой выборке и масштабировать значение весов пропорционально. Таким образом, классификаторы с показателем точности меньше или равной 1/М в действительности исключаются из итоговой системы. Значения «важности» классификаторов в итоговой системе, по которым впоследствии, пропорционально данному значению высчитываются веса, вычисляется как:

,

где - количество ошибок допускаемых -м классификатором.

4. «Best-worst weighted vote». В данной технике производится нормировка классификаторов. Так, классификатору с максимальной точностью присваивается значение показателя важности равное 1, а худшему 0 соответственно. Для остальных классификаторов значения показателей важности распределяются линейно между двумя крайностями, описанными выше

где .

5. «Quadratic best-worst weighted vote». Аналогично предыдущему, для повышения влияния на итоговую систему классификаторов с наибольшей точностью, значения полученные предыдущим методом возводятся в квадрат

.

6. «Weightedmajorityvote». По теореме 4.1 [2], точность ансамбля максимизируется назначением весов:

где ? точность одиночного классификатора. В данном методе веса вычисляются по формуле

.

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

где ? предсказание k-го классификатора для объекта , тогда - предсказание ансамбля; ? символ Кронекера.

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

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

Так в работе [3] представлен также взвешенный метод комбинирования классификаторов, однако основанный на теории свидетельств.

Теория свидетельств (теория Демпстера-Шейфера или теория функций доверия) ? это математическая теория, основанная на понятии свидетельства, как совокупности некоторых подмножеств (фокальных элементов) универсального множества и частотной функции принадлежности истинной альтернативы этим подмножествам.

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

На множестве всех подмножеств рассматривается функция множеств , которую называю функцией масс или базовой вероятностью. Эта функция должна удовлетворять условиям нормировки: 1) ; 2) .

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

Если А - некоторое подмножество универсального множества, то его масса m(A) выражает долю всех соответствующих и доступных свидетельств, подтверждающих утверждение о том, что фактическое состояние (истинная альтернатива) принадлежит непосредственно А, а не какому-нибудь подмножеству А, каждое из которых имеет собственную массу.

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

.

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

.

Функция правдоподобие равна сумме масс всех множеств Bпересекающихся с рассматриваемым множеством A

.

Эти две меры соотносятся с собой отношения двойственности

.

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

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

Для двух свидетельств с функциями массm₁ и m₂ соответственно правило Демпстера формирует новую функцию масс по формулам

,

,

.

Здесь - мера конфликта между двумя наборами масс. Если , то это означает, чтосвидетельства являются абсолютно конфликтными (фокальные элементы двух свидетельств попарно не пересекаются). В этом случае правило Демпстера неприменимо.

Альтернативой правилу Демпстера является правило, разработанное Ягером. Он ввел так называемую «комбинированную вероятность» q:

Комбинированная вероятность q может использоваться для любого количества свидетелей. [5]

Основным отличием правила Ягера от Демпстера является отсутствие коэффициента конфликтности (нормализации) 1-K. Это вызвано тем, что комбинированная вероятность q от пустого множества больше либо равна 0. Причем вычисляется абсолютно также, как и коэффициент конфликтности K. После чего значение добавляется к комбинированной универсальной вероятности всего множества для получения комбинированной базовой вероятности.[5]

Таким образом вместо конфликтности, использованной в правиле Демпстера, Ягер переносит конфликтность на все множество .

Базовые вероятности других множеств определяются, как:

Комбинированные вероятности правила объединения Ягера могут быть выражены через базовые вероятности правила объединения Демпстера:

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

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

Разные классификаторы могут иметь разную «надежность», поскольку имеют разные способности и особенности к классификации. Конкретная операция дисконтирования для комбинации источников информации с разным уровнем надежности была описана Шейфером и называется методом дисконтирования [4].Она понижает массы всех фокальных элементов посредством весового коэффициента до полного игнорирования. Благодаря этому можно эффективно контролировать влияние каждого классификатора на итоговую систему (после объединения)

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

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

где .

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

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

- фрейм различения (взаим. Гипотезы - классы);

- классификаторы, обученные на обучающей выборке ;

? класс, к которому принадлежит тренировочный образ .

В работе [3] веса вычисляются на основе оптимизационной процедуры и правила объединения Депмпстера-Шейфера. Так, вектор оптимальных весов для классификаторов может быть получен путем минимизации расстояния между результатом ансамбля и действительных классов тренировочных образов, используя Jousseleme'sdistance

.

Вывод классификатора по отношению к образу представлен базовой вероятностью . Действительное значение обучающего образа характеризуется бинарным вектором . Все компоненты данного вектора равны нулю за исключением для класса . Jousseleme'sdistanceдля пары базовых вероятностей m₁и m₂ вычисляется по формуле

,

где - положительно определенная матрица , чьи компоненты являются значениями меры Жаккара

.

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

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

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

2. Реализация исследования

2.1 Использованные данные и классификаторы

Для исследования в данной работе были взяты пять концептуально разных техник классификации:

- метод k ближайших соседей (knn);

- логистическая регрессия (lr);

- случайный лес (rfc);

- машина опорных векторов (SVM);

- наивный байесовский классификатор (nb).

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

Эффективность алгоритмов и методов агрегирования классификаторов была протестирована на 10 наборах данных бинарной классификации. В качестве метрики качества были взяты точность (accuracy) и значение кривой AUC-ROC. Каждый классификатор был обучен на одинаковой обучающей выборке, а значения точности и AUC-ROCполучены на одной и той же тестовой выборке, выборки разбиты 70/30. (Размер классов примерно одинаковый на всех наборах данных, что делает точность неплохой метрикой качества в данном исследовании).

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

Все базы данных были взяты из каталога баз данных UCI Machine Learning Repository; признаковое пространство объектов баз данных не содержит пропусков, каждый из объектов гарантированно принадлежит одному из классов.

В рамках теории свидетельств были реализованы такие техники объединения, как:

- правило объединения Демпстера;

- правило объединения Ягера.

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

2.2 Комбинирование классификаторов в рамках теории свидетельств

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

Вывод классификатора «probas» состоит из 2-х элементов: вероятность принадлежности первому классу и второму соответственно. Множество же базовых вероятностей теории свидетельств - из 3-х (исключая пустое множество). К вероятностям принадлежности первому и второму классу добавляется универсальное множество - базовая вероятность принадлежности первому или второму классу. Таким образом уровень неуверенности классификатора (значения 1-точность) можно проигнорировать. Домножим полученные классические вероятности одиночных классификаторов на эту степень уверенности - это и будут новые базовые вероятности теории свидетельств. Поскольку сумма масс всех гипотез равна единице, то оставшаяся часть пойдет в массу всего универсального множества (игнорируемую часть), т.е. множеству принадлежности объекта либо первому, либо второму классу (в рамках данного исследования на наборах данных бинарной классификации). Рассмотрим на примере Наивного Байеса базы данных «pime» для 0-го объекта:

Рис 1. Вероятности принадлежности одному из классов объекта для Наивного Байеса (первые 10)

Вероятности принадлежности вектора обучающей выборки одному из классов (Рис. 1) домножим на точность, полученную Наивным Байесом на обучающей выборке (acc = 0.763500931099). Таким образом, получаем массы (базовые вероятности теории свидетельств):

,

,

.

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

Рис. 2 Базовые вероятности теории свидетельств принадлежности объекта классу для Наивного Байеса (первые 10)

Далее, реализуем правил объединения классификаторов в рамках теории свидетельств.

1) Правило объединения Демпстера (Приложение 1), рассмотрим на примере объединения свидетельств двух классификаторов: k ближайших соседей и Наивного Байеса на наборе данных «pime» для 0го объекта(само правило описано в первой части ВКР).



Рис. 3 Базовые вероятности (массы) kближайших соседей (слева) и наивного Байеса (справа)

Для начала вычислим нормализующий коэффициент конфликтности Kдля 0го объекта:

.

Теперь, значения новых объединенных масс:

,

,

.

Выполняя аналогичные действия по отношению к каждому объекту, получим значения новых объединенных масс:

Рис. 4 Базовые вероятности объединения масс kближайших соседей и наивного Байеса

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

3. Сравнение результатов работы алгоритмов

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

Таблица 1. Значение кривой AUC-ROCна разных алгоритмах классификации

Базы Данных/Алгоритмы классификации	TDS	NB	RFC	LR	SVM	knn	Jag
Pime	0.837	0.808	0.808	0.811	0.8105	0.789	0.836
Blood-trans	0.751	0.706	0.679	0.759	0.689	0.739	0.75
Banknote auth	1.00	0.935	0.991	0.992	0.995	0.995	1.00
Spambase	0.994	0.856	0.987	0.973	0.972	0.972	0.994
Skin segm	0.999	0.937	0.999	0.908	0.999	0.998	0.999
Phoneme	0.931	0.824	0.959	0.818	0.916	0.914	0.931
Ionosphere	0.935	0.851	0.941	0.839	0.974	0.782	0.935
Diabetes	0.743	0.728	0.725	0.709	0.726	0.684	0.741
Oil spil	0.871	0.604	0.632	0.808	0.860	0.725	0.871
Electricity	0.859	0.704	0.899	0.734	0.787	0.801	0.859

Правила объединения Демпстера и Ягера достаточно хорошо справились с задачей, показав лучший результат на 6 из 10 наборах данных, причем на оставшихся четырех не сильно отставая от лидера. Так, например, в базах данных «Phoneme», «Ionosphere» и «Electricity», не показав лучший результат, тем не менее, значения точности и AUC-ROCкривой все еще достаточно большие (в особенности в «Phoneme» и «Ionosphere»), что свидетельствует о высоком уровне способности к предсказанию.

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

Однако, превосходство правил объединениятеории свидетельств не назвать подавляющим по сравнению с одиночными классификаторами, в целом, результаты сопоставимы и различаются в несколько сотых, в добавок, на части из баз данных результаты метрик качестве являются средними («Bloodtrans», «Diabetes»). Возможно, стандартные техники объединения справятся лучше с задачей. Проведем сравнение правила объединения Демпстера со стандартными техниками объединения классификаторов, а именно: Pluralityvote, Simpleweightedvote, weightedmajorityvote на 3-х худших по значению кривой AUC-ROCбаз данных (Таблица 2).

Таблица 2. Значение кривой AUC-ROCдля разных ансамблей

Базы Данных/Ансамбли	PV	SW(без RFC)	WMV (без RFC)
Pime	0.774	0.775 (0.778)	0.773 (0.78)
Blood-trans	0.631	0.65(0.68)	0.631(0.651)
Diabetes	0.623	0.626(0.633)	0.627(0.632)

Каждый из стандартных методов объединения классификаторов уступает правилам объединения теории свидетельств в точности и значении AUC-ROCкривой. Более того оценка качества весовых методов без включения случайного леса в ансамбль выше, чем с его присутствием в итоговой системе. Это связано с тем, что определения уровня влияния того или иного классификатора основано на значение его точности на обучающей выборке. Точность RFCна обучающей выборке практически всегда равняется единице, что отнюдь не означает, что такой же результат будет достигнут на тестовой. (Для реализации Weighted Majority Vote значение точности RFCна тестовой выборке было принято за 0.99).

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

Важную роль играет эффективная комбинация классификаторов в ансамбль. Так, на примере базы данных: «Blood-trans» (Приложение 2), значение AUC-ROCкомбинации классификаторов (правилом Демпстера): SVC, LRи knn, равно 0.77, что превосходит комбинацию всех 5 классификаторов, каждого классификатора по отдельности и является лучшим на данном наборе данных.

4. Модификации модели

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

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

,

,

.

Следовательно, .

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

На примере первых двух баз данных (Рис. 5) после введения точность модели tdsувеличилась (с 0.76 до 0.79 на «pime» и с 0.746 до 0.756 на «Blood-trans»).

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

Рис 5.a. Точность ансамбля скомбинированного правилом Демпстера для разных (база данных «pime»)

Рис 5.b. Точность ансамбля скомбинированного правилом Демпстера для разных (база данных «Blood-trans»)

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

Для подбора оптимальных весов минимизируем функционал «Logisticloss» относительно весов классификаторов.

где - ответ принятый после объединения классификаторов правилом Демпстера на i-мобъекте, - истинный ответ на i-мобъекте, k - классификатор, m-базовая вероятность теории свидетельств, а l - размер выборки.

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

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

Так, на каждом из наборов данных в рамках данной работы удалось достичь лучшие значения метрик качества. Например, на базе данных «pime» значение AUC-ROCувеличилось с 0.837 до 0.871. На базе данных «Blood-trans» значение возросло до 0.801, что на 5 сотых превосходит предыдущий результат tdsи на 0.04 лучший результат среди одиночных классификаторов, также это на 0.03 больше чем объединение SVM, LRи knn (Приложение 2), притом, что в системе участвовали все 5 одиночных классификаторов. Аналогично для оставшихся 8 баз данных. Более того, количество взятых мной итераций было 10 (для каждого классификатора), следовательно, при увеличении количества итерации AUC-ROCтолько улучшится.

Заключение

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

В рамках исследовательской работы было обучено 5 алгоритмов классификации на 10 различных баз данных. Данные алгоритмы были скомбинированы в ансамбль 5 различными техниками. Реализованы правила Демпстера и Ягера и сама модель от преобразования классических вероятностей (выводов одиночных классификаторов) в базовые вероятности теории свидетельств до принятия решений о принадлежности объекта определенному классу исходя из новых значений функции масс.

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

Подводя итоги, можно сказать, что правило Демпстера является весьма полезным методом создания ансамбля классификаторов, превосходящий такие стандартные техники, как «Plurality Vote», «Simpleweighted», «Weightedmajorityvote». Этот метод может быть успешно применен в приложениях. Например, в соревнованиях на Kaggle, вместо обыденного бесконечного усреднения моделей в надежде улучшить эффективность алгоритма на 0.00001, при определении целесообразности выдачи кредита. Помимо исследованных задач бинарной классификации, данный метод также способен решать мультиклассовую задачу бинарной классификации не прибегая к специальным техникам решения подобного рода задач.

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

1. F. Moreno-Seco, J.M. Inesta, P.J. Ponce de Leon, L. Mico, Comparison of Classifier Fusion Methods for Classification in Pattern Recognition Tasks, D.-Y. Yeung et al. (Eds.): Springer-Verlag Berlin Heidelberg, pp.705-713, 2006

2. `Kuncheva, L.: Combining Pattern Classifiers: methods and algorithms. Wiley (2004)

3. Z. Liu, Q. Pan, J. Dezert2, A. Martin Combination of classifiers with optimal weight based on evidential reasoning// IEEE Transactions on Fuzzy Systems, 2017

4. G. Shafer, A mathematical theory of evidence, Princeton Univ. Press, 1976

5. Уткин Л.В. Анализ риска и принятие решений при неполной информации - СПб.: Наука, 2007. - 404с.

Приложение 1

Реализация правила комбинирования Демпстера для двух классификаторов

(язык программирования - Python)

deftds(masses_df_1, masses_df_2):

masses_1 = masses_df_1.values

masses_2 = masses_df_2.values

new_masses = np.zeros_like(masses_1)

n_objects = new_masses.shape[0]

for i in range(n_objects):

k = masses_1[i, 0] * masses_2[i, 1] + masses_1[i, 1] * masses_2[i, 0]

new_masses[i, 0] = (masses_1[i, 0] * masses_2[i, 0] \

+ masses_1[i, 0] * masses_2[i, 2] \

+ masses_2[i, 0] * masses_1[i, 2]) / (1 - k)

new_masses[i, 1] = (masses_1[i, 1] * masses_2[i, 1] \

+ masses_1[i, 1] * masses_2[i, 2] \

+ masses_2[i, 1] * masses_2[i, 2]) / (1 - k)

new_masses[i, 2] = masses_1[i, 2] * masses_2[i, 2] / (1 - k)

new_masses /= np.tile(new_masses.sum(axis=1), (3, 1)).T

new_masses = pd.DataFrame(new_masses, columns=masses_te_nb.columns)

return new_masses

Приложение 2

Значения AUC-ROC для разных комбинаций классификаторов и правила комбинирования Демпстера

Комбинации классификаторов /Базы данных	Blood-trans
LR, knn	0.77
LR, SVC	0.77
LR, NB	0.75
LR,RFC	0.728
knn,SVC	0.751
knn, NB	0.749
knn, RFC	0.721
SVC, NB	0.742
SVC, RFC	0.695
NB, RFC	0.715
LR, knn, SVC	0.77
LR, knn, NB	0.76
LR, knn, RFC	0.745
LR, SVC, NB	0.76
LR, SVC, RFC	0.737
LR, NB, RFC	0.741
knn, SVC, NB	0.752
knn, SVC, RFC	0.735
knn, NB, RFC	0.736
SVC, NB, RFC	0.71
LR, knn, SVC, NB	0.754
LR, knn, SVC, RFC	0.742
LR, knn, NB, RFC	0.757
LR, SVC, NB, RFC	0.738
knn, SVC, NB, RFC	0.735

Приложение 3

Реализация «дельта метода» игнорирования неочевидных данных

(язык Python)

delt_score = []

foriinnp.linspace(0, 0.3, 100):

delta = i

less_delta = np.apply_along_axis(arr=probas_te_nb.values[:,:2], axis=1, func1d=lambda x: 1 if np.abs(x[0] - x[1]) < delta else 0)

delta_masses_te_nb = masses_te_nb.copy(deep=True)

delta_masses_te_nb.iloc[:, 0] = delta_masses_te_nb.iloc[:, 0] * np.logical_not(less_delta)

delta_masses_te_nb.iloc[:, 1] = delta_masses_te_nb.iloc[:, 1] * np.logical_not(less_delta)

delta_masses_te_nb.ix[np.bool8(less_delta), 2] = 1

less_delta = np.apply_along_axis(arr=probas_te_nb.values[:,:2], axis=1, func1d=lambda x: 1 if np.abs(x[0] - x[1]) < delta else 0)

delta_masses_te_rfc = masses_te_rfc.copy(deep=True)

delta_masses_te_rfc.iloc[:, 0] = delta_masses_te_rfc.iloc[:, 0] * np.logical_not(less_delta)

delta_masses_te_rfc.iloc[:, 1] = delta_masses_te_rfc.iloc[:, 1] * np.logical_not(less_delta)

delta_masses_te_rfc.ix[np.bool8(less_delta), 2] = 1

less_delta = np.apply_along_axis(arr=probas_te_nb.values[:,:2], axis=1, func1d=lambda x: 1 if np.abs(x[0] - x[1]) < delta else 0)

delta_masses_te_knn = probas_te_knn.copy(deep=True)

delta_masses_te_knn.iloc[:, 0] = delta_masses_te_knn.iloc[:, 0] * np.logical_not(less_delta)

delta_masses_te_knn.iloc[:, 1] = delta_masses_te_knn.iloc[:, 1] * np.logical_not(less_delta)

delta_masses_te_knn.ix[np.bool8(less_delta), 2] = 1

less_delta = np.apply_along_axis(arr=probas_te_nb.values[:,:2], axis=1, func1d=lambda x: 1 if np.abs(x[0] - x[1]) < delta else 0)

delta_masses_te_svc = probas_te_svc.copy(deep=True)

delta_masses_te_svc.iloc[:, 0] = delta_masses_te_svc.iloc[:, 0] * np.logical_not(less_delta)

delta_masses_te_svc.iloc[:, 1] = delta_masses_te_svc.iloc[:, 1] * np.logical_not(less_delta)

delta_masses_te_nb.ix[np.bool8(less_delta), 2] = 1

less_delta = np.apply_along_axis(arr=probas_te_nb.values[:,:2], axis=1, func1d=lambda x: 1 if np.abs(x[0] - x[1]) < delta else 0)

delta_masses_te_lr = probas_te_lr.copy(deep=True)

delta_masses_te_lr.iloc[:, 0] = delta_masses_te_lr.iloc[:, 0] * np.logical_not(less_delta)

delta_masses_te_lr.iloc[:, 1] = delta_masses_te_lr.iloc[:, 1] * np.logical_not(less_delta)

delta_masses_te_lr.ix[np.bool8(less_delta), 2] = 1

fusio = tds(tds(tds(tds(delta_masses_te_rfc, delta_masses_te_nb), delta_masses_te_knn), delta_masses_te_lr), delta_masses_te_svc)

delt_score.append(accuracy_score(np.int64(y_te), np.int64(fusio.iloc[:, 1] > fusio.iloc[:, 0])))

Приложение 4

Итеративный подбор весов классификаторов для правила комбинирования Демпстера

(для 10 итераций, язык Python)

def tds_all(masses_df_1, masses_df_2, masses_df_3, masses_df_4, masses_df_5, alpha_1=1, alpha_2=1, alpha_3=1, alpha_4=1, alpha_5=1):

return tds(tds(tds(tds(masses_df_1, masses_df_2, alpha_1, alpha_2), masses_df_3, alpha_2=alpha_3), masses_df_4, alpha_2=alpha_4), masses_df_5, alpha_2=alpha_5)

val_scores = np.zeros((10, 10, 10, 10, 10))

for i1, alpha_1 in enumerate(np.linspace(0, 1, 10)):

for i2, alpha_2 in enumerate(np.linspace(0, 1, 10)):

for i3, alpha_3 in enumerate(np.linspace(0, 1, 10)):

for i4, alpha_4 in enumerate(np.linspace(0, 1, 10)):

for i5, alpha_5 in enumerate(np.linspace(0, 1, 10)):

tds_fusion_masses_val = tds_all(probas_val_rfc, probas_val_nb, probas_val_knn, probas_val_lr, probas_val_svc,

alpha_1, alpha_2, alpha_3, alpha_4, alpha_5)

val_scores[i1, i2, i3, i4, i5] = log_loss(y_val, tds_fusion_masses_val.iloc[:, 1].values)

np.argmin(val_scores)

Размещено на Allbest.ru

...