Классификация по нескольким этикеткам

редактировать

Не путать с мультиклассовой классификацией.

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

Формально, классификация с несколькими метками - это проблема поиска модели, которая отображает входные данные x в двоичные векторы y (присваивая значение 0 или 1 для каждого элемента (метки) в y).

СОДЕРЖАНИЕ

1 Методы трансформации задачи
2 Адаптированные алгоритмы
3 парадигмы обучения
4 Классификация потоков с несколькими метками
5 Статистика и показатели оценки
6 Реализации и наборы данных
7 См. Также
8 ссылки
9 Дальнейшее чтение

Методы трансформации проблемы

Для классификации с несколькими метками существует несколько методов преобразования проблем, которые можно условно разбить на:

Преобразование в проблемы бинарной классификации : базовый подход, называемый методом бинарной релевантности, сводится к независимому обучению одного бинарного классификатора для каждой метки. Учитывая невидимую выборку, комбинированная модель затем предсказывает все метки для этой выборки, для которых соответствующие классификаторы предсказывают положительный результат. Хотя этот метод разделения задачи на несколько бинарных задач может внешне напоминать методы один против всех (OvA) и один против остальных (OvR) для мультиклассовой классификации, он существенно отличается от обоих, поскольку один классификатор под бинарной релевантностью имеет дело с одной меткой, без какого-либо отношения к другим меткам. Классификатор цепь представляет собой альтернативный способ для преобразования задачи классификации с множеством меток на несколько двоичных задачи классификации. Она отличается от бинарной релевантности тем, что метки предсказываются последовательно, а выходные данные всех предыдущих классификаторов (т. Е. Положительные или отрицательные для конкретной метки) вводятся в качестве признаков для последующих классификаторов. Цепочки классификаторов применялись, например, для прогнозирования лекарственной устойчивости ВИЧ. Байесовская сеть также применяется для оптимального упорядочивания классификаторов в цепочках классификаторов.
Преобразование в задачу мультиклассовой классификации : преобразование набора меток (LP) создает один двоичный классификатор для каждой комбинации меток, присутствующей в обучающем наборе. Например, если возможные метки для примера были A, B и C, представление Powerset меток для этой проблемы представляет собой задачу классификации нескольких классов с классами [0 0 0], [1 0 0], [0 1 0 ], [0 0 1], [1 1 0], [1 0 1], [0 1 1]. [1 1 1], где, например, [1 0 1] обозначает пример, в котором метки A и C присутствуют, а метка B отсутствует.
Методы ансамбля : для создания классификатора ансамбля с несколькими метками можно использовать набор мультиклассовых классификаторов. В данном примере каждый классификатор выводит один класс (соответствующий одной метке в задаче с несколькими метками). Эти прогнозы затем объединяются методом ансамбля, обычно схемой голосования, где каждый класс, который получает необходимый процент голосов от отдельных классификаторов (часто называемый порогом дискриминации), прогнозируется как текущая метка в выводе с несколькими метками. Однако существуют более сложные ансамблевые методы, такие как комитетные машины. Другой вариант -алгоритмслучайных k- меток (RAKEL), который использует несколько классификаторов LP, каждый из которых обучен на случайном подмножестве фактических меток; предсказание метки затем выполняется схемой голосования. Набор классификаторов с несколькими метками можно использовать аналогичным образом для создания классификатора ансамбля с несколькими метками. В этом случае каждый классификатор голосует один раз за каждую прогнозируемую метку, а не за одну метку.

Адаптированные алгоритмы

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

k-ближайшие соседи : алгоритм ML-kNN расширяет классификатор k-NN до данных с несколькими метками.
деревья решений : Clare - это адаптированный алгоритм C4.5 для классификации по нескольким меткам; модификация включает в себя вычисления энтропии. Усовершенствованный MMDT MMC, MMDT и SSC может классифицировать данные с несколькими метками на основе многозначных атрибутов без преобразования атрибутов в однозначные. Их также называют многозначными и многозначными методами классификации дерева решений.
методы ядра для векторного вывода
нейронные сети : BP-MLL - это адаптация популярного алгоритма обратного распространения для обучения с несколькими метками.

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

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

Классификация потоков с несколькими метками

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

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

Методы на основе Online Bagging (OzaBagging): наблюдение за вероятностью наличия K многих из определенных точек данных в выборке начальной загрузки приблизительно равно Пуассону (1) для больших наборов данных, каждый экземпляр входящих данных в потоке данных может быть взвешен пропорционально Пуассону ( 1) распространение для имитации начальной загрузки в режиме онлайн. Это называется онлайн-бэггингом (OzaBagging). В литературе предлагается множество методов с несколькими этикетками, использующих онлайн-упаковку, каждый из которых использует разные методы преобразования проблемы. EBR, ECC, EPS, E B RT, E B MT, ML-Random Rules являются примерами таких методов.
Методы ADWIN на основе бэггинга: методы онлайн-бэггинга для MLSC иногда комбинируются с явными механизмами обнаружения смещения концепций, такими как ADWIN (адаптивное окно). ADWIN поддерживает окно переменного размера для обнаружения изменений в распределении данных и улучшает ансамбль, сбрасывая компоненты, которые плохо работают при дрейфе входящих данных. Как правило, буква «а» используется в качестве нижнего индекса в названии таких ансамблей, чтобы указать на использование детектора изменений ADWIN. E a BR, E a CC, E a HT PS являются примерами таких многокомпонентных ансамблей.
Методы на основе GOOWE-ML: интерпретация оценок релевантности каждого компонента ансамбля как векторов в пространстве меток и решение задачи наименьших квадратов в конце каждого пакета, геометрически оптимальный онлайн-взвешенный ансамбль для классификации по нескольким меткам (GOOWE -ML) предлагается. Ансамбль пытается минимизировать расстояние между взвешенным предсказанием его компонентов и основным истинным вектором для каждого экземпляра пакета. В отличие от Online Bagging и ADWIN Bagging, GOOWE-ML использует схему взвешенного голосования, при которой более эффективные компоненты ансамбля имеют больший вес. Набор GOOWE-ML со временем растет, и компонент с наименьшим весом заменяется новым компонентом, когда он заполняется в конце партии. GOBR, GOCC, GOPS, GORT - это предлагаемые мульти-лейбл-ансамбли на основе GOOWE-ML.
Несколько окон : здесь модели BR, в которых используется скользящее окно, заменяются двумя окнами для каждой метки, одно для релевантных и одно для нерелевантных примеров. Экземпляры подвергаются избыточной или недостаточной выборке в соответствии с коэффициентом загрузки, который сохраняется между этими двумя окнами. Это позволяет обнаруживать дрейфы концепций, которые являются независимыми для каждой метки, и обрабатывать классовый дисбаланс (асимметрию в релевантных и нерелевантных примерах).

Статистика и показатели оценки

Учитывая, что это набор меток для выборки данных (не путайте его с одним горячим вектором; это просто набор всех меток, принадлежащих этому образцу), степень, в которой набор данных является мульти-меткой, может быть отраженным в двух статистических данных: ${\ displaystyle Y_ {i}}$ $Y_ {i}$ ${\ displaystyle i ^ {th}}$ $я ^ {th}$

Мощность метки - это среднее количество меток на один пример в наборе: где - общее количество выборок данных; ${\ displaystyle {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} | Y_ {i} |}$ ${\ frac {1} {N}} \ sum _ {{i = 1}} ^ {N} | Y_ {i} |$ ${\ displaystyle N}$ $N$
Плотность этикеток - это количество этикеток в образце, деленное на общее количество этикеток, усредненное по выборкам: где - общее количество доступных классов (которое является максимальным количеством элементов, которые могут составлять). ${\ displaystyle {\ frac {1} {N}} \ sum _ {i = 1} ^ {N} {\ frac {| Y_ {i} |} {| L |}}}$ ${\ frac {1} {N}} \ sum _ {{i = 1}} ^ {N} {\ frac {| Y_ {i} |} {| L |}}$ ${\ Displaystyle L = \ bigcup _ {я = 1} ^ {N} Y_ {я}}$ $L = \ bigcup _ {{i = 1}} ^ {N} Y_ {i}$ ${\ displaystyle Y_ {i}}$ $Y_ {i}$

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

Потеря Хэмминга : доля ошибочных меток в общем количестве меток, т. Е. Где - цель, является предсказанием и является оператором «Исключающий или», который возвращает ноль, когда цель и предсказание идентичны, и единицу в противном случае. Это функция потерь, поэтому оптимальное значение равно нулю, а его верхняя граница равна единице. ${\ displaystyle {\ frac {1} {| N | \ cdot | L |}} \ sum _ {i = 1} ^ {| N |} \ sum _ {j = 1} ^ {| L |} \ operatorname {xor} (y_ {i, j}, z_ {i, j})}$ ${\ displaystyle {\ frac {1} {| N | \ cdot | L |}} \ sum _ {i = 1} ^ {| N |} \ sum _ {j = 1} ^ {| L |} \ operatorname {xor} (y_ {i, j}, z_ {i, j})}$ ${\ displaystyle y_ {i, j}}$ $y_ {i, j}$ ${\ displaystyle z_ {я, j}}$ $z _ {{i, j}}$ ${\ Displaystyle \ OperatorName {xor} (\ cdot)}$ ${\ Displaystyle \ OperatorName {xor} (\ cdot)}$
Тесно связанный индекс Жаккара, также называемый пересечением по объединению в настройке с несколькими метками, определяется как количество правильно предсказанных меток, деленное на объединение предсказанных и истинных меток, где и представляют собой наборы предсказанных меток и истинных меток соответственно. ${\ displaystyle {\ frac {| T \ cap P |} {| T \ cup P |}}}$ ${\ frac {| T \ cap P |} {| T \ cup P |}}$ ${\ displaystyle P}$ $п$ ${\ displaystyle T}$ $Т$
Точность, отзыв и оценка : точность есть, отзыв есть и есть их гармоническое среднее. ${\ displaystyle F_ {1}}$ $F_ {1}$ ${\ displaystyle {\ frac {| T \ cap P |} {| P |}}}$ ${\ frac {| T \ cap P |} {| P |}}$ ${\ displaystyle {\ frac {| T \ cap P |} {| T |}}}$ ${\ frac {| T \ cap P |} {| T |}}$ ${\ displaystyle F_ {1}}$ $F_ {1}$
Точное совпадение (также называемое точностью подмножества): это самый строгий показатель, указывающий процент образцов, все метки которых классифицированы правильно.

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

Реализации и наборы данных

Java-реализации алгоритмов с несколькими метками доступны в программных пакетах Mulan и Meka, оба основаны на Weka.

Scikit учиться Python пакет реализует некоторые мульти-этикетки алгоритмы и метрики.

Scikit-multilearn пакет Python специально обслуживает классификации мульти-меток. Он обеспечивает многокомпонентную реализацию нескольких хорошо известных методов, включая SVM, kNN и многие другие. Пакет построен на основе экосистемы scikit-learn.

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

Список часто используемых наборов данных с несколькими метками доступен на веб-сайте Mulan.

Смотрите также

использованная литература

дальнейшее чтение

Маджаров, Горгджи; Кочев, Драги; Горгжевикдж, Деян; Джероски, Сашо (2012). «Обширное экспериментальное сравнение методов многокомпонентного обучения». Распознавание образов. 45 (9): 3084–3104. DOI : 10.1016 / j.patcog.2012.03.004.