Классификация с несколькими этикетками - Multi-label classification

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

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

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

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

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

• Превращение в двоичная классификация проблемы: базовый подход, называемый бинарная релевантность метод^[1] означает независимое обучение одного двоичного классификатора для каждой метки. Учитывая невидимую выборку, комбинированная модель затем предсказывает все метки для этой выборки, для которых соответствующие классификаторы предсказывают положительный результат. Хотя этот метод разделения задачи на несколько бинарных задач может внешне напоминать методы один против всех (OvA) и один против остальных (OvR) для мультиклассовая классификация, он существенно отличается от обоих, потому что один классификатор при бинарной релевантности имеет дело с одной меткой без какого-либо отношения к другим меткам. А цепочка классификаторов является альтернативным методом преобразования задачи классификации с несколькими метками в несколько задач двоичной классификации. Она отличается от бинарной релевантности тем, что метки предсказываются последовательно, а выходные данные всех предыдущих классификаторов (то есть положительные или отрицательные для конкретной метки) вводятся как признаки для последующих классификаторов.^[1] Цепочки классификаторов применялись, например, в ВИЧ прогнозирование лекарственной устойчивости.^[2][3] Байесовская сеть также был применен к классификаторам оптимального порядка в Цепочки классификаторов.^[4]
• Превращение в мультиклассовая классификация проблема: Преобразование набора меток (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 отсутствует.^[5]
• Ансамблевые методы: Набор многоклассовых классификаторов может использоваться для создания многокомпонентного классификатора ансамбля. В данном примере каждый классификатор выводит один класс (соответствующий одной метке в задаче с несколькими метками). Эти прогнозы затем объединяются методом ансамбля, обычно схемой голосования, где каждый класс, который получает необходимый процент голосов от отдельных классификаторов (часто называемый порогом дискриминации^[6]) предсказывается как присутствующая метка в выводе с несколькими метками. Однако существуют более сложные ансамблевые методы, такие как комитетные машины. Другой вариант - случайный k-labelsets (RAKEL) алгоритм, который использует несколько классификаторов LP, каждый из которых обучен на случайном подмножестве фактических меток; предсказание метки затем выполняется схемой голосования.^[7] Набор классификаторов с несколькими метками можно использовать аналогичным образом для создания классификатора ансамбля с несколькими метками. В этом случае каждый классификатор голосует один раз за каждую прогнозируемую метку, а не за одну метку.

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

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

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

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

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

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

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

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

• Интернет-упаковка (OzaBagging^[15]) -основанные методы: Наблюдение за вероятностью наличия K многих из определенных точек данных в выборке начальной загрузки приблизительно Пуассон (1) для больших наборов данных каждый экземпляр входящих данных в потоке данных может быть взвешен пропорционально распределению Пуассона (1) для имитации начальной загрузки в интерактивной настройке. Это называется онлайн-упаковкой (OzaBagging). В литературе предлагается множество методов с несколькими этикетками, в которых используется онлайн-упаковка, каждый из которых использует различные методы преобразования проблемы. EBR,^[1] ECC,^[1] EPS,^[16] E_BRT,^[17] E_BMT,^[17] ML-случайные правила^[18] являются примерами таких методов.
• ADWIN Bagging^[19]-основные методы: Методы онлайн-упаковки для MLSC иногда сочетаются с явными механизмами обнаружения смещения концепций, такими как ADWIN.^[20] (Адаптивное окно). ADWIN поддерживает окно переменного размера для обнаружения изменений в распределении данных и улучшает ансамбль, сбрасывая компоненты, которые плохо работают при дрейфе входящих данных. Как правило, буква «а» используется как нижний индекс в названии таких ансамблей, чтобы указать на использование детектора изменений ADWIN. E_аBR,^[19] E_аCC,^[19] E_аHT_PS^[19] являются примерами таких многокомпонентных ансамблей.
• GOOWE-ML^[21]-основные методы: Интерпретируя оценки релевантности каждого компонента ансамбля как векторы в пространстве меток и решая задачу наименьших квадратов в конце каждого пакета, предлагается геометрически оптимальный онлайн-взвешенный ансамбль для классификации с несколькими метками (GOOWE-ML). Ансамбль пытается минимизировать расстояние между взвешенным предсказанием его компонентов и основным вектором истинности для каждого экземпляра пакета. В отличие от онлайн-упаковки и упаковки ADWIN, в GOOWE-ML используется взвешенный схема голосования, при которой более эффективные компоненты ансамбля имеют больший вес. Ансамбль GOOWE-ML со временем увеличивается, и компонент с наименьшим весом заменяется новым компонентом, когда он заполняется в конце партии. ГОБР,^[21] GOCC,^[21] GOPS,^[21] ГОРТ^[21] являются предлагаемыми мульти-лейбльными ансамблями на основе GOOWE-ML.
• Несколько окон^[22] : Здесь модели BR, которые используют скользящее окно, заменены двумя окнами для каждой метки, одно для релевантных и одно для нерелевантных примеров. Экземпляры подвергаются передискретизации или заниженной выборке в соответствии с коэффициентом загрузки, который сохраняется между этими двумя окнами. Это позволяет обнаруживать дрейфы концепций, которые являются независимыми для каждой метки, и обрабатывать классовый дисбаланс (асимметрию в релевантных и нерелевантных примерах).

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

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

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

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

• Hamming потеря: доля неправильных этикеток в общем количестве этикеток, т.е. ${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}}$ цель, ${displaystyle z_{i,j}}$ это предсказание, и ${displaystyle operatorname {xor} (cdot )}$ это Оператор "Исключающее или" который возвращает ноль, когда цель и прогноз идентичны, и единицу в противном случае. Это функция потерь, поэтому оптимальное значение равно нулю, а его верхняя граница равна единице.
• Тесно связанные Индекс Жаккара, также называемый пересечением по объединению в настройке с несколькими метками, определяется как количество правильно спрогнозированных меток, деленное на объединение предсказанных и истинных меток, ${displaystyle {frac {|Tcap P|}{|Tcup P|}}}$, где ${displaystyle P}$ и ${displaystyle T}$ представляют собой наборы предсказанных меток и истинных меток соответственно.
• Точность, отзыв и ${displaystyle F_{1}}$ Гол: точность ${displaystyle {frac {|Tcap P|}{|P|}}}$напомнить ${displaystyle {frac {|Tcap P|}{|T|}}}$, и ${displaystyle F_{1}}$ их гармоническое среднее.^[23]
• Точное совпадение (также называемое точностью подмножества): это самый строгий показатель, указывающий процент образцов, все метки которых классифицированы правильно.

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

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

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

В scikit-learn Пакет Python реализует некоторые алгоритмы и показатели с несколькими метками.

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

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

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

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

• Мультиклассовая классификация
• Множественное обучение
• Структурированный прогноз
• время жизни корреляции

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

1. Джесси Рид, Бернхард Пфарингер, Джефф Холмс, Эйбе Франк. Цепочки классификаторов для классификации по нескольким меткам. Журнал машинного обучения. Springer. Vol. 85 (3), (2011).
2. Heider, D; Senge, R; Ченг, Вт; Hüllermeier, E (2013). «Классификация по нескольким меткам для использования информации о перекрестной устойчивости в прогнозировании лекарственной устойчивости ВИЧ-1». Биоинформатика. 29 (16): 1946–52. Дои:10.1093 / биоинформатика / btt331. PMID  23793752.
3. Riemenschneider, M; Senge, R; Neumann, U; Hüllermeier, E; Хайдер, Д. (2016). «Использование информации о перекрестной резистентности протеазы ВИЧ-1 и обратной транскриптазы для улучшенного прогнозирования лекарственной устойчивости посредством классификации с несколькими метками». BioData Mining. 9: 10. Дои:10.1186 / s13040-016-0089-1. ЧВК  4772363. PMID  26933450.
4. Суфан, Осман; Ба-Алави, Вой; Афиф, Моатаз; Эссак, Магбубах; Калнис, Панос; Баич, Владимир Б. (10.11.2016). «DRABAL: новый метод для анализа больших высокопроизводительных скрининговых тестов с использованием байесовского активного обучения». Журнал химинформатики. 8: 64. Дои:10.1186 / s13321-016-0177-8. ISSN  1758-2946. ЧВК  5105261. PMID  27895719.
5. Сполаор, Ньютон; Черман, Эвертон Альварес; Монар, Мария Каролина; Ли, Хуэй Диана (март 2013 г.). «Сравнение методов выбора характеристик с несколькими метками с использованием подхода преобразования проблемы». Электронные заметки по теоретической информатике. 292: 135–151. Дои:10.1016 / j.entcs.2013.02.010. ISSN  1571-0661.
6. «Порог дискриминации - документация Yellowbrick 0.9». www.scikit-yb.org. Получено 2018-11-29.
7. Цумакас, Григориос; Влахавас, Иоаннис (2007). Случайный k-labelsets: метод ансамбля для классификации по нескольким меткам. (PDF). ECML. Архивировано из оригинал (PDF) в 2014-07-29. Получено 2014-07-26.
8. Zhang, M.L .; Чжоу, З.Х. (2007). «ML-KNN: ленивый подход к обучению с несколькими метками». Распознавание образов. 40 (7): 2038–2048. CiteSeerX  10.1.1.538.9597. Дои:10.1016 / j.patcog.2006.12.019.
9. Маджаров, Горгджи; Кочев, Драги; Горгжевикдж, Деян; Джероски, Сашо (2012). «Обширное экспериментальное сравнение методов многокомпонентного обучения». Распознавание образов. 45 (9): 3084–3104. Дои:10.1016 / j.patcog.2012.03.004.
10. Чен, Йен-Лян; Сюй, Чанг-Линь; Чжоу, Ши-чжи (2003). «Построение многозначного и многозначного дерева решений». Экспертные системы с приложениями. 25 (2): 199–209. Дои:10.1016 / S0957-4174 (03) 00047-2.
11. Чжоу, Шихчи; Сюй, Чан-Лин (01.05.2005). «MMDT: многозначный и многозначный древовидный классификатор решений для интеллектуального анализа данных». Экспертные системы с приложениями. 28 (4): 799–812. Дои:10.1016 / j.eswa.2004.12.035.
12. Ли, Хун; Го, Юэ-цзянь; Ву, Мин; Ли, Пинг; Сян, Яо (01.12.2010). «Совместите разложение многозначных атрибутов с обучением по нескольким меткам». Экспертные системы с приложениями. 37 (12): 8721–8728. Дои:10.1016 / j.eswa.2010.06.044.
13. Zhang, M.L .; Чжоу, З.Х. (2006). Многометровые нейронные сети с приложениями к функциональной геномике и категоризации текста (PDF). IEEE Transactions по разработке знаний и данных. 18. С. 1338–1351.
14. Аггарвал, Чару С., изд. (2007). Потоки данных. Достижения в системах баз данных. 31. Дои:10.1007/978-0-387-47534-9. ISBN  978-0-387-28759-1.
15. Оза, Никундж (2005). «Интернет-упаковка и разгон». Международная конференция IEEE по системам, человеку и кибернетике. HDL:2060/20050239012.
16. Читай, Джесси; Пфарингер, Бернхард; Холмс, Джефф (2008-12-15). Классификация по нескольким меткам с использованием ансамблей сокращенных наборов. Компьютерное общество IEEE. С. 995–1000. Дои:10.1109 / ICDM.2008.74. HDL:10289/8077. ISBN  9780769535029. S2CID  16059274.
17. Осойник, Аляг; Панов, PanăźE; DźEroski, Sašo (2017-06-01). «Классификация по нескольким меткам с помощью многоцелевой регрессии для потоков данных». Машинное обучение. 106 (6): 745–770. Дои:10.1007 / s10994-016-5613-5. ISSN  0885-6125.
18. Соуза, Рикардо; Гама, Жоао (24 января 2018 г.). «Многопозиционная классификация высокоскоростных потоков данных с использованием правил адаптивной модели и случайных правил». Прогресс в искусственном интеллекте. 7 (3): 177–187. Дои:10.1007 / s13748-018-0142-z. ISSN  2192-6352. S2CID  32376722.
19. Читай, Джесси; Бифет, Альберт; Холмс, Джефф; Пфарингер, Бернхард (21 февраля 2012 г.). «Масштабируемая и эффективная классификация по нескольким меткам для развивающихся потоков данных». Машинное обучение. 88 (1–2): 243–272. Дои:10.1007 / s10994-012-5279-6. ISSN  0885-6125.
20. Бифет, Альберт; Гавальда, Рикар (2007-04-26), "Обучение на основе изменяющихся во времени данных с помощью адаптивного управления окнами", Материалы Международной конференции SIAM 2007 по интеллектуальному анализу данных, Общество промышленной и прикладной математики, стр. 443–448, CiteSeerX  10.1.1.215.8387, Дои:10.1137/1.9781611972771.42, ISBN  9780898716306
21. Бююкчакир, Аликан; Бонаб, Хамед; Джан, Фазли (17.10.2018). Новый комплексный онлайн-ансамбль для классификации потоков с несколькими метками. ACM. С. 1063–1072. arXiv:1809.09994. Дои:10.1145/3269206.3271774. ISBN  9781450360142. S2CID  52843253.
22. Ксиуфис, Элефтериос Спиромитрос; Спилиопулу, Майра; Цумакас, Григориос; Влахавас, Иоаннис (16.07.2011). Работа с дрейфом концепций и несбалансированностью классов при классификации потоков с несколькими метками. AAAI Press. С. 1583–1588. Дои:10.5591 / 978-1-57735-516-8 / IJCAI11-266. ISBN  9781577355144.
23. Годболе, Шантану; Сараваги, Сунита (2004). Дискриминационные методы для классификации с несколькими метками (PDF). Достижения в области обнаружения знаний и интеллектуального анализа данных. С. 22–30.
24. Сечидис, Константинос; Цумакас, Григориос; Влахавас, Иоаннис (2011). О стратификации данных с несколькими метками (PDF). ECML PKDD. С. 145–158.
25. Филипп Пробст, Набережная Ау, Джузеппе Казаликкио, Клеменс Штахль, Бернд Бишль. Классификация по нескольким меткам с пакетом R mlr. The R Journal (2017) 9: 1, страницы 352-369.

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

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