В машинном обучении и статистике под многоклассовой понимают задачу классификации, в которой каждое наблюдение исходного набора данных требуется отнести более чем к двум классам. Она представляет собой наиболее общий случай классификации, с которым приходится сталкиваться в задачах анализа данных.
Классификация — одна из наиболее популярных задач интеллектуального анализа данных, поскольку она не только подходит для многих сценариев аналитической обработки, но и обладает высокой объясняющей способностью: классифицирующие правила могут быть сформулированы практически на естественном языке. Именно поэтому для решения задачи классификации разработано большое количество методов и алгоритмов, одна часть из которых относится к области математической статистики, а другая — к машинному обучению.
Можно выделить три задачи классификации:
Виды задач классификации
Каждый из этих видов задач имеет свои особенности как в плане используемых алгоритмов, так и практического применения результатов и оценки их точности. Так, если первые два вида предполагают, что любой классифицируемый объект может относиться одновременно только к одному классу, следовательно предсказывается единственное значение метки, то в третьей задаче для каждого наблюдения необходимо предсказывать сразу множество меток классов (или вектор в случае их кодирования числами).
В анализе данных чаще реализуется второй тип — задача со многими классами. При упоминании слова «классификация» именно его обычно и подразумевают. Данный вид задачи имеет наиболее общую постановку, которую при необходимости можно редуцировать к остальным двум типам.
Таким образом, при выборе вида и структуры классификационной модели для многих классов, возникает дилемма: использовать множество бинарных классификаторов или один сразу для всех классов. Преимущество первого подхода состоит в том, что бинарные классификаторы реализуют простую линейную дискриминирующую функцию. Однако простота базовой модели приводит к необходимости строить множество классификаторов: от k-1 до k(k-1)/2 .
Преимущество второго подхода заключается в том, что нужен только один классификатор, но реализующий сложную дискриминирующую функцию. Для того, чтобы делать правильный выбор при решении конкретной задачи, важно знать особенности каждого подхода. Рассмотрим их ниже.
Говоря о мультиклассовой классификации, ее рассматривают как расширение бинарной, что соответствует возможным сценариям анализа. Например, агентству недвижимости требуется предсказать, купит клиент дом или нет, что является классической бинарной задачей. Вполне разумно предположить ситуацию, когда покупатель не скажет ни да, ни нет, а попросит время на раздумье, чтобы сравнить варианты.
С точки зрения логики клиент, ушедший без покупки, тоже должен быть причислен к классу «нет». Но с точки зрения бизнес-логики это не одно и то же, поскольку клиент, попросивший время подумать, по-прежнему является потенциальным покупателем. Таким образом, мультиклассовый подход расширяет круг бизнес-решений. Если в бинарном случае по результатам можно было принять два взаимоисключающих решения (начать процедуру продажи или прекратить работу с клиентом), то при появлении третьего класса возникает еще одна задача — разработать стратегию воздействия на клиента с целью склонить его к покупке.
Пусть задан обучающий набор данных: D=(x_{i},y_{i}), i=1,...,n где n — число примеров, x_{i}— вектор признаков, y_{i} — метка класса i-го примера. Задача заключается в том, чтобы построить классификатор, который для каждого x будет правильно предсказывать y, причем не только на обучающем множестве D, но и для любых наблюдений, в него не входящих (т.е. классификатор должен обладать обобщающей способностью).
Если классификатор строится на основе машинного обучения, то в процессе итеративной настройки параметров модели происходит минимизация функции потерь (целевой функции). При статистическом подходе параметры модели выбираются так, чтобы максимизировать условную вероятность P(y|x). Т.е. в качестве предсказания классификатора выбирается метка класса y, наиболее вероятная для входного x.
В некоторых случаях получить приемлемый классификатор с многими классами не удается. Решить проблему часто можно путем трансформации сложной мультиклассовой задачи к набору бинарных. Для этого существует несколько методов.
Один против всех (One-versus-all, OvA). Иногда упоминается как один против остальных (One-versus-rest, OvR). Метод предполагает построение одного бинарного классификатора для каждого класса, при этом примеры данного класса считаются положительными, а всех других — отрицательными.
.svg )
Метод «один против всех»
Пусть D множество обучающих примеров содержит k классов.
Поскольку существует c меток, требуется построить соответствующее число классификаторов c_{1}, c_{2},..., c_{k}.
Результатом обучения по методу OvA является множество классификаторов f_{l}, где l\in \left \{1,2,...,k \right \}. Для каждого l формируется новый вектор z такой, что z_{i}=y_{i}, если y_{i}=k и z_{i}=0 в противном случае.
Конечный результат получается по принципу «победитель забирает все», т.е.
\widehat{y}=\underset{l}{argmax}f_{l}(x).
Простыми словами, новое наблюдение будет относиться к классу, бинарный классификатор для которого даст большее число «положительных» примеров.
Метод «один против всех» популярен у аналитиков данных. Тем не менее он является эвристическим и имеет ряд проблем. Например, если даже в исходной многоклассовой выборке классы сбалансированы, то каждый бинарный классификатор обучается в условиях их дисбаланса, когда отрицательных примеров намного больше, чем положительных, что приводит к снижению точности.
Один против одного (One versus One, OvO). Данный метод строит k(k-1) классификаторов, которые позволяют различить любую пару примеров, относящихся к разным классам. Алгоритм просматривает все пары примеров с разными метками классов и для каждой решает бинарную задачу f_{ij}. В каждом случае для пар (i,j) положительными являются все примеры с метками i, а отрицательными — с метками j. Решение при этом имеет вид:
\widehat{y}=\underset{x\in X}{argmax}\sum\limits_{i}^{}f_{ij}(x).
Недостаток подхода очевиден: число классификаторов растет квадратично с количеством примеров, в то время как в предыдущем методе зависимость линейная.
В методе «один против всех» строится число классификаторов, равное количеству классов k. На самом деле нет необходимости в k классификаторах, чтобы распознать k классов. Вместо этого можно использовать log_{2}k битов и сравнивать их по отдельности. Таким образом, количество классификаторов сокращается до log_{2}k.
Декомпозиция на основе корректирующих кодов является упрощенной реализацией этой схемы, поскольку неправильная метка получается даже при наличии одного некорректно определенного бита. Чтобы избежать этого, можно использовать несколько дополнительных битов. При k=8 достаточно обучить log_{2}8=3 классификатора. Но если ввести дополнительный бит и использовать 4 бита, получим:
| Метка | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 |
| 2 | 0 | 1 | 1 | 0 |
| 3 | 1 | 0 | 0 | 1 |
| 4 | 1 | 0 | 1 | 1 |
| k | 0 | 1 | 0 | 0 |
Каждая строка таблицы представляет собой код класса. Например, метка 1 имеет кодировку 0101. Тогда каждый столбец определяет задачу классификации. Например, в столбце P_{1} стоит 1, если метка равна 3 или 4 и 0 — в противном случае.
Обратите внимание, что с помощью 4-х битов можно закодировать 16 меток классов, в то время как по условию задачи требуется закодировать только 8, что дает некоторую избыточность. Если в одном из битов допущена ошибка, выбирается метка, наиболее соответствующая результатам. Это исправляет некоторые ошибки, допущенные при классификации, поэтому данная парадигма и называется декомпозицией на основе кодов коррекции ошибок.
Эта технология пришла в машинное обучение из области помехоустойчивого кодирования в радиосвязи. В основе его идеи лежит добавление при передаче в полезные данные специальным образом структурированной избыточной информации (например, контрольного числа), использование которой при приеме позволяет обнаруживать и исправлять ошибки.
В случае «один против всех» будет ровно k строк и k столбцов. В каждом столбце будет одна 1, а все остальные значения — 0.
Еще одним методом бинарной классификации, который может быть расширен для многоклассового случая, является логистическая регрессия. Как известно, ее выходом является рейтинг — величина, изменяющаяся в диапазоне от 0 до 1, которая может быть интерпретирована как вероятность принадлежности к «положительному» классу.
Интерпретация результата при классификации производится с помощью дискриминационного порога: если вероятность выше его значения, то объект относится к «положительному» классу, в противном случае — к отрицательному. Полиномиальная логистическая регрессия позволяет обобщить данный подход на случай многоклассовой классификации, когда вероятности присваиваются более чем двум классам.
В основе работы модели лежит специальная функция, известная как Softmax — обобщение логистической функции для многомерного случая. Функция преобразует вектор z размерности K в вектор той же размерности, каждый элемент которого представляет собой вещественное число в интервале \left [ 0,1 \right ], сумма которых равна 1. Элементы нового вектора интерпретируются как вероятности принадлежности объекта к соответствующему классу.
Softmax-регрессия — это алгоритм машинного обучения с учителем, используемый в задачах многоклассовой классификации. В отличие от методов OvR и OvO, которые являются адаптацией бинарной классификации к задаче со многими классами, регрессия softmax специально разрабатывалась для этих целей.
В отличие от обычной логистической регрессии, в Softmax-классификаторе используется не сигмоидальная функция s(z), а векторная функция \Psi :\mathbb{R}^{K}\rightarrow (0,1)^{K}
\Psi (z_{1},z_{2},...,z_{K})=\begin{bmatrix} \psi_{1} (z_{1},z_{2},...z_{K})\\ \psi_{2}(z_{1},z_{2},...,z_{K}) \\ .... \\ \psi _{K}(z_{1},z_{2},...,z_{K})\end{bmatrix} ,
где \psi _{k} :\mathbb{R}^{K}\rightarrow (0,1)^{K} скалярная функция вида:
\psi _{k}(z_{1},z_{2},...z_{K})=\frac{exp(z_{k})}{\sum\limits_{i=1}^{K}exp(z_{i})}.
Несложно увидеть, что благодаря нормирующим свойствам знаменателя 0<\psi _{k}(z_{1},z_{2},...z_{K})<1. Кроме того \sum\limits_{i=1}^{K}\psi (z_{1},z_{2},...,z_{K})=1 . Эти два свойства позволяют интерпретировать данную величину как вероятность i‐го класса.
Softmax-регрессия
Вектор‐столбец слева содержит выходы некоторой модели (например, нейронной сети), которая формирует их в результате поступления на ее вход классифицируемого наблюдения. Эти значения необходимо интерпретировать. Одним из вариантов — «жесткий максимум», когда реализуется принцип «победитель получает все» и все 100% вероятности отдают наибольшему значению (в нашем примере 5.1).
Этот метод является относительно грубым. Поэтому популярен подход, когда вероятности распределяются пропорционально значениям. Однако он не учитывает масштаб величин: если все значения уменьшить в 10 раз, вероятности останутся теми же. В то же время при использовании Softmax происходит выделение больших значений и подавление малых, что делает результаты классификации более выразительными.
Выше рассмотрены многоклассовые методы, которые представляют собой расширение бинарных моделей. В интеллектуальном анализе данных широко используются и модели, для которых работа более чем с двумя классами является естественной. К ним относятся нейронные сети, деревья решений, метод k-ближайших соседей и другие. Они могут работать с более чем двумя классами без каких-либо дополнительных настроек.
Применение бинарных классификаторов к решению мультиклассовых задач на основе декомпозиции остается актуальным. Это связано с тем, что модели, построенные на основе декомпозиции многоклассовой задачи на несколько бинарных, могут оказаться более точными, чем использующие один мультиклассовый классификатор.
Причины этого кроются в неоднородности границ решений между классами. Действительно, в бинарном случае каждый алгоритм классификации работает с единственной границей, как правило, линейной. В случае трех или более классов количество границ решений увеличивается, а сами они будут иметь разные характеристики. Они могут быть гладкими, изрезанными, содержать шум и т.д. Очевидно, что форма границы определяется классифицирующей функцией. При этом истинная граница решения так и остается неизвестной: классификатор дает только некоторое ее приближение.
Таким образом, в многоклассовой задаче оказывается, что один и тот же алгоритм классификации «работает» с несколькими границами решения, обладающими различными свойствами, что приводит к ухудшению качества модели. При этом чем больше классов и границ между ними, тем более выраженным является этот эффект.
Еще одной проблемой мультиклассовых моделей является то, что они имеют настройки гиперпараметров (например, для дерева решений это может быть глубина и минимально допустимое число примеров в узле и т.д.), которые делают их состоятельными только в некоторой области пространства признаков. Целью настройки гиперпараметров, как правило, является минимизация функции потерь (числа неправильно распознанных примеров, относительной ошибки распознавания и т.д.).
Область состоятельности модели
При этом форма области состоятельности модели меняется. И эти изменения могут быть неравномерными относительно границ решения, что также приводит к ухудшению различимости объектов отдельных классов. В бинарных классификаторах, где область состоятельности модели привязана к единственной границе решения, данное явление практически отсутствует.
Таким образом, решение задач мультиклассовой классификации может быть реализовано как с помощью декомпозиции на множество бинарных задач и обучения соответствующего числа бинарных моделей, либо используя единственный классификатор, способный работать более чем с двумя классами. В первом случае получаем много простых моделей, а во втором — единственную сложную модель. Правильный выбор между этими подходами обеспечивает успех решения задач мультиклассовой классификации в анализе данных.
Дополнительные материалы:
Утечка данных в машинном обучении
Предсказание рейтингов ТВ-программ: методы машинного обучения на платформе Loginom
