Мультиклассовая классификация - Multiclass classification

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

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

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

Общие стратегии

Существующие методы многоклассовой классификации можно разделить на (i) преобразование в двоичную систему (ii) расширение двоичной классификации и (iii) иерархическую классификацию.

Преобразование в двоичный

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

Один против остальных

Стратегия один против остальных (OvR или один против всех , OvA или один против всех , OAA) включает обучение одного классификатора для каждого класса, при этом образцы этого класса являются положительными, а все другие образцы - отрицательными. . Эта стратегия требует, чтобы базовые классификаторы производили реальную оценку достоверности своего решения, а не просто метку класса; Одни только дискретные метки классов могут привести к неоднозначности, когда несколько классов прогнозируются для одной выборки.

В псевдокоде алгоритм обучения учащегося OvR, построенного на основе учащегося $L$ двоичной классификации, выглядит следующим образом:

Входы:

$L$ , ученик (алгоритм обучения бинарных классификаторов)
образцы $X$
метки $y,$ где $y i$ ∈ {1,… $K$ } - метка для выборки $X i$

Выход:

список классификаторов $f k$ для $k$ ∈ {1,…, $K$ }

Процедура:

Для каждого k в {1,…, K }
- Создайте новый вектор меток $z,$ где $z i$ = $y i,$ если $y i = k,$ и $z i = 0 в$ противном случае
- Примените $L$ к $X$ , $z,$ чтобы получить $f k$

Принятие решений означает применение всех классификаторов к невидимой выборке $x$ и прогнозирование метки $k,$ для которой соответствующий классификатор сообщает наивысшую оценку достоверности:

{\ displaystyle {\ hat {y}} = {\ underset {k \ in \ {1 \ ldots K \}} {\ arg \! \ max}} \; f_ {k} (x)}

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

Один против одного

При редукции « один-к-одному» (OvO) обучают $K (K - 1) / 2$ бинарных классификатора для $K-$ way мультиклассовой задачи; каждый получает образцы пары классов из исходного обучающего набора и должен научиться различать эти два класса. Во время прогнозирования применяется схема голосования: все классификаторы $K (K - 1) / 2$ применяются к невидимой выборке, а класс, получивший наибольшее количество прогнозов «+1», прогнозируется комбинированным классификатором.

Как и OvR, OvO страдает двусмысленностями в том, что некоторые области его входного пространства могут получить одинаковое количество голосов.

Расширение из двоичного файла

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

Нейронные сети

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

Экстремальные обучающие машины

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

k-ближайшие соседи

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

Наивный байесовский

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

Деревья решений

Изучение дерева решений - мощный метод классификации. Дерево пытается вывести разделение обучающих данных на основе значений доступных функций для получения хорошего обобщения. Алгоритм естественным образом справляется с задачами двоичной или мультиклассовой классификации. Листовые узлы могут относиться к любому из рассматриваемых классов K.

Опорные векторные машины

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

Иерархическая классификация

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

Парадигмы обучения

На основе парадигм обучения существующие методы многоклассовой классификации можно разделить на пакетное обучение и онлайн-обучение . Алгоритмы пакетного обучения требуют, чтобы все образцы данных были доступны заранее. Он обучает модель, используя все обучающие данные, а затем предсказывает тестовую выборку, используя найденную взаимосвязь. С другой стороны, алгоритмы онлайн-обучения постепенно строят свои модели в последовательных итерациях. На итерации t онлайн-алгоритм получает выборку x _t и предсказывает ее метку ŷ _t, используя текущую модель; Затем алгоритм получает y _t , истинную метку x _t, и обновляет свою модель на основе пары образец-метка: (x _t , y _t ). Недавно была разработана новая парадигма обучения, называемая прогрессивной техникой обучения. Методика прогрессивного обучения способна не только учиться на новых образцах, но также способна изучать новые классы данных и при этом сохранять полученные знания.

Languages

In other projects