Классификация сo многими метками

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

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

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

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

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

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

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

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

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

Например, в маркетинге используют различную классификацию клиентов:

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

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

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

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

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

Можно выделить три вида задач классификации:

• бинарную;
• с несколькими классами (мультиклассовую);
• с несколькими метками (многометочную).

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

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

Эти два вида часто обозначают как классификация с одной меткой (single-label classification — SLC), поскольку в ней может использоваться при обучении классификатора только одна метка класса.

Классификация со многими метками (multi-label classification — MLC) относит объект к нескольким классам одновременно, которые при этом не являются взаимоисключающими.

Некоторые авторы в настоящее время рассматривают SLC как частный случай MLC. Рассмотрим общую постановку задачи классификации.

Пусть задано множество наблюдений (классифицируемых объектов) X=\left \{ x_{1}, x_{2},..., x_{n} \right \} и множество меток классов Y=\left \{ y_{1}, y_{2},..., y_{m} \right \}. При этом существует неизвестная классифицирующая функция, которая реализует отображение множества объектов в множество классов: f^{*}: X\rightarrow Y, значения которых известны на конечной обучающей выборке размером k: X^{k}=\left\{ (x_{1},y_{1}), (x_{2},y_{2}),...,(x_{k},y_{k})\right\}.

Требуется построить алгоритм (классификатор) g:X\to Y, который каждому объекту x_{i}\in X ставит в соответствие y_{i}\in Y. При этом если m=2, то имеет место бинарная классификация, а если m>2 — мультиклассовая.

Чем же постановка MLC отличается от SLC? Поскольку в этом случае обучающий набор данных будет содержать несколько полей меток классов (например, A, B и C), то для реализации отображения X\rightarrow Y потребуется уже ансамбль классифицирующих функцийF_{x}=\left\{ f_{1}^{*},f_{2}^{*},...f_{m}^{*} \right\}, размер которого равен числу меток класса. Соответственно, каждая из них потребует построения собственного классификатора, т.е. G_{x}=\left\{ g_{1},g_{2},...g_{m} \right\}.

В следующей таблице представлен пример обучающей выборки для MLC.

Вероятностная постановка SLC: \hat{y}_{j}(x_{i})=g_{j}(x_{i})=\underset{y_{j}\in Y}{argmax}\left( p(y_{j}|x_{i}) \right),

т.е. наблюдению x_{i} ставится в соответствие класс y_{j}, для которого условная вероятность p(y_{j}|x_{i}) наибольшая. При этом \sum\limits_{j=1}^{k}p(y_{j}|x_{i})=1.

Т.е. если классы являются взаимоисключающими, то сумма их вероятностей равна 1.

Вероятностная постановка MLC:

\hat{\textbf{y}}=\left[ \hat{y_{1}},\hat{y_{2}},...,\hat{y_{k}} \right]=\textbf{g(x)}=\left[ \underset{y_{1}\in Y}{argmax}(p(y_{1})|\textbf{x}),\underset{y_{2}\in Y}{argmax}(p(y_{2})|\textbf{x}),...,\underset{y_{k}\in Y}{argmax}(p(y_{k})|\textbf{x}) \right].

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

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

Метки являются независимыми если вероятность их вектора равна произведению вероятностей каждой метки в отдельности:

P(\textbf{Y})=\prod\limits_{i=1}^{n}P(y_{i}).

Рассмотрим случай двух меток, т.е. Y=\left \{ y_{1},y_{2} \right \}. Тогда если P(y_{1}|y_{2})=P(y_{1}), тогда метки являются независимыми, т.е. значение метки y_{1} не влияет на вероятность метки y_{2}. Если же y_{2} зависит от y_{1}, то P(y_{2})=P(y_{2}|y_{1})P(y_{1}).

При этом обычно P(y_{2}|y_{1})\neq P(y_{1}|y_{2}) , т.е. уровни взаимного влияния событий не равны. Следовательно, чтобы минимизировать зависимость, нужно выбрать такой их порядок, при котором их условная вероятность была наименьшей.

Данный подход позволяет повысить точность классификатора, но является достаточно затратным в вычислительном плане. Так, количество парных перестановок, которое может понадобиться, пропорционально 2^{n}. Поэтому учитывать зависимость меток в модели имеет смысл только если она сильная и значительно ухудшает результаты.

История развития и области применения MLC

Упоминания MLC в академической литературе появляются с середины 1990-х годов. При этом, по данным Google Scholar, если с 2000 по 2005 г. число упоминаний в тексте около 200, а в заголовках около 20, то с 2015 по 2020 количество публикаций с упоминанием MLC в тексте перевалило за 5000, а в заголовках — за 500. Такая динамика, несомненно, свидетельствует о высоком интересе к задаче.

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

Методы построения MLC-классификаторов

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

Tрансформация данных

На практике используют следующие методы трансформации:

• бинарной релевантности (binary relevance, BR);
• цепочки классификаторов (classifier chain, CC);
• набор мощности меток (label-powerset, LP).

Метод бинарной релевантности

В основе метода лежит преобразование задачи MLC к нескольким задачам бинарной классификации с одной меткой. При этом для каждого класса, которому может принадлежать объект, в обучающем наборе создается отдельное поле, где для примера ставится 1, если он принадлежит классу, и 0 — в противном случае.

Исходные данные будут иметь вид:

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

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

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

Метод BR имеет два основных недостатка. Первый — необходимость обучать множество классификаторов, что может привести к значительным вычислительным затратам. Второй — он не учитывает зависимость меток.

Цепочки классификаторов

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

Цепочка классификаторов

p(\textbf{Y}|\textbf{X})=p(\textbf{x})\prod\limits_{j=1}^{k}p(y_{j}|\textbf{x}, y_{1},y_{2},y_{3},y_{4}),

\hat{\textbf{y}}=\underset{\textbf{y}\in \left\{ 0,1 \right\}^{k}}{argmax}p(\textbf{y}|\textbf{x}).

Обучающие выборки для цепи из 4-х классификаторов представлены в таблицах:

Набор мощности меток

Данный метод преобразует MLC в обычную задачу классификации с несколькими классами, каждый из которых представлен как уникальный набор BR-меток. Исходная таблица будет иметь вид:

Таблица после преобразования:

Преимуществом подхода является то, что достаточно построить один классификатор. Недостаток — квадратичный рост количества классов относительно числа меток.

Перекрестное обучение

Еще одним популярным методом MLC, использующим преобразование меток, является перекрестное обучение. В нем исходная задача с несколькими метками с N классами и M наблюдениями разделяется на K обучающих наборов для задач с одной меткой. Значение K варьируется от 1, когда ни одно наблюдение не имеет более одной метки (обычная SLC), до максимального числа меток, соответствующего одному наблюдению.

Рассмотрим, например, задачу c тремя классами, в которой только два примера связаны с двумя метками каждый:

Тогда для метода перекрестного обучения требуется построить два однометочных обучающих набора:

Адаптация алгоритмов

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

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

MLC-kNN

Пусть задано наблюдение x и соответствующий ему вектор меток Y. Кроме этого определим вектор \textbf{y}_{x} каждый элемент которого принимает значение 1, если метка l\in Y и 0 в противном случае.

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

\textbf{C}_{x}(l)=\sum\limits_{a\in N(x)}\textbf{y}_{x}(l).

Таким образом, \textbf{C}_{x}(l) определяется как количество ближайших соседей x, содержащих метку l.

Введем в рассмотрение два события: H_{1}^{l}— метка l связана с наблюдением и H_{0}^{l} — l метка не связана с наблюдением. Кроме этого, введем в рассмотрение событие E\tfrac{l}{j}(j\in \left \{ 1,2,...,k \right \}) показывает, что среди k ближайших соседей классифицируемого объекта j содержат метку l. Тогда на основе счетного вектора \textbf{C}_{x}(l) и вектора \textbf{y}_{x} можно определить максимум апостериорной вероятности:

\mathbf{y}_{x}(l)=\underset{b\in (0,1)}{argmax}P(H_{b}^{l}|E_{C_{\mathbf{x}}}^{l}).

Таким образом, классификатор выбирает для объекта \textbf{x} такой вектор меток \mathbf{y}_{x}, который максимизирует апостериорную вероятность события H_{1}^{l} при определенном векторе E_{C_{\mathbf{x}}}^{l}.

Нейросетевые модели для MLC. Нейронные сети также могут быть применены для решения задачи MLC. Для этого используют обучение с учителем c адаптированной функцией ошибки. Одним из наиболее популярных подходов стал модифицированный метод обратного распространения ошибки BP-MLL (Backpropagation for Multilabel Learning).

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

E=\sum\limits_{p-1}^{m}\left [ \left ( \sum\limits_{(r,s)\in (Y_{p}\times \overline{Y}_{p})}^{} exp(c_{r}^{p}-c_{s}^{p})\right )/\left (| Y_{p}||\overline{Y}_{p} \right ) \right ]

h\left ( x_{p} \right )=\left \{ q\in Y:c_{q}(x_{p}>t(x_{p})) \right \}, c_{q}(x_{p})=c_{q}^{p},

где m — число обучающих примеров, Y_{p}\subseteq Y=\left \{ 0,1,...,Q-1 \right \} — множество меток, связанное с p-го обучающим примером, c_{q}^{p}— фактическое выходное значение q-го выходного нейрона (соответствует q-й метке), \overline{Y}_{p} — дополнение множества {Y}_{p}, содержащее метки, которые не связаны с p-го обучающим примером. h(x_{p})— множество меток, присвоенное нейросетью {Y}_{p}-му примеру.

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

Меры точности MLC-классификаторов

Заключительным этапом построения любого классификатора является оценка его точности. Очевидно, для обычных классификаторов, которые предсказывают метку единственного класса, и MLC-классификаторов, которые формируют на выходе вектор меток, ее методы будут различаться.

Для оценки точности MLC классификаторов применяются следующие методы.

Потери Хемминга (Hamming loss). Данный показатель основан на расстоянии Хемминга и определяется как относительная частота неправильных классификаций:

hloss=\frac{1}{nm}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\left [ \widehat{y}_{j}^{i}\neq y_{j}^{i} \right ],

где m — число обучающих примеров, а n — количество меток.

В таблице ниже представлен пример для определения функции потерь Хемминга.

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

0/1-потери (0/1-loss). Данный вид оценки представляет собой долю обучающих примеров, при классификации которых была допущена ошибка хотя бы для одной метки:

0/1-loss=\frac{1}{m}\sum\limits_{i=1}^{m}\left [ \widehat{\textbf{y}}_{i}\neq \textbf{y}_{i} \right ].

В данном примере 0/1-loss=\frac{1}{5}\cdot 3=0.6. Очевидно, что если во всех примерах метки распознаны верно, то показатель окажется равным 0, а если ошибочно классифицированная метка содержится во всех примерах, то 1. Несложно увидеть, что данный вид оценки эквивалентен обычной оценке ошибки классификации в случае единственной метки.

Оценка на основе потерь Хемминга применима только для MLC-классификаторов, использующих методы бинарной релевантности, в то время как 0/1-loss может применяться для цепочек классификаторов и мощности меток.

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

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

Другие материалы по теме:

Дрейф данных

Обнаружение и коррекция одномерных выбросов в данных