Введение

Процедура в машинном обучении и статистике

Выбор признаков — это процесс отбора подмножества релевантных признаков (переменных, предикторов) для использования при построении модели. Стилиометрия и анализ ДНК-микромассивов — два примера областей, где применяется выбор признаков. Его следует отличать от извлечения признаков. Методы выбора признаков используются по нескольким причинам:

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

Введение

Алгоритм выбора признаков можно рассматривать как комбинацию метода поиска для генерации новых подмножеств признаков и меры оценки, которая оценивает различные подмножества. Самый простой алгоритм — это проверка каждого возможного подмножества признаков для нахождения того, который минимизирует частоту ошибок. Это полный перебор пространства, который вычислительно невыполним для всех, кроме самых маленьких наборов признаков. Выбор метрики оценки существенно влияет на алгоритм, и именно эти метрики различают три основные категории алгоритмов выбора признаков: методы обертки, фильтры и встроенные методы. Методы обертки используют прогностическую модель для оценки подмножеств признаков. Каждое новое подмножество используется для обучения модели, которая затем тестируется на отложенной выборке. Подсчет количества ошибок, допущенных на этой отложенной выборке (частота ошибок модели), дает оценку для данного подмножества. Поскольку методы обертки обучают новую модель для каждого подмножества, они очень требовательны к вычислительным ресурсам, но обычно обеспечивают наилучший набор признаков для конкретного типа модели или типичной задачи. Фильтры используют прокси-меру вместо частоты ошибок для оценки подмножества признаков. Эта мера выбирается для быстрого вычисления, сохраняя при этом способность отражать полезность набора признаков. Распространенные меры включают взаимную информацию, меж- и внутриклассовые расстояния или результаты тестов значимости для каждой комбинации класса и признака. Фильтры обычно менее требовательны к вычислительным ресурсам, чем методы обертки, но они создают набор признаков, который не настроен на конкретный тип прогностической модели. Отсутствие такой настройки означает, что набор признаков, полученный с помощью фильтра, более общий, чем набор, полученный с помощью обертки, и обычно обеспечивает более низкую производительность прогнозирования. Однако набор признаков не содержит предположений прогностической модели и поэтому более полезен для выявления взаимосвязей между признаками. Многие фильтры предоставляют ранжирование признаков, а не явное подмножество лучших признаков, и точка отсечения в ранжировании выбирается с помощью кросс-валидации. Методы фильтрации также могут использоваться в качестве этапа предварительной обработки для методов обертки, позволяя использовать обертку для решения более крупных задач. Другой популярный подход — алгоритм рекурсивного исключения признаков, часто используемый с машинами опорных векторов для многократного построения модели и удаления признаков с низкими весами. Встроенные методы представляют собой группу методов, которые выполняют выбор признаков как часть процесса построения модели. Классическим примером является метод LASSO для построения линейной модели, который штрафует коэффициенты регрессии L1-штрафом, обнуляя многие из них. Признаки, имеющие ненулевые коэффициенты регрессии, "выбираются" алгоритмом LASSO. Улучшения LASSO включают Bolasso, который выполняет бутстрэп-выборку; Elastic Net регуляризацию, которая объединяет L1-штраф LASSO с L2-штрафом гребневой регрессии; и FeaLect, который оценивает все признаки на основе комбинаторного анализа коэффициентов регрессии. AEFS расширяет LASSO до нелинейного сценария с использованием автокодировщиков. Эти подходы обычно занимают промежуточное положение между фильтрами и методами обертки с точки зрения вычислительной сложности. В традиционном регрессионном анализе наиболее популярной формой выбора признаков является пошаговая регрессия, которая является методом обертки. Это жадный алгоритм, который добавляет лучший признак (или удаляет худший признак) на каждом шаге. Основной вопрос управления — определение момента остановки алгоритма. В машинном обучении это обычно делается с помощью кросс-валидации. В статистике оптимизируются некоторые критерии. Это приводит к присущей проблеме вложенности. Исследовались более надежные методы, такие как метод ветвей и границ и кусочно-линейная сеть.

Критерии оптимальности

Выбор критериев оптимальности затруднителен, поскольку задача отбора признаков имеет множество целей. Многие распространенные критерии включают в себя меру точности, снижаемую в зависимости от количества выбранных признаков. Примерами служат информационный критерий Акайке (AIC) и критерий Маллоуса Cp, которые предусматривают штраф в 2 единицы за каждый добавленный признак. AIC основан на теории информации и фактически выводится на основе принципа максимальной энтропии. Другие критерии включают в себя байесовский информационный критерий (BIC), использующий штраф в размере за каждый добавленный признак, минимальную длину описания (MDL), которая асимптотически использует , Bonferroni / RIC, использующие , метод отбора признаков на основе максимальной зависимости, а также множество новых критериев, основанных на частоте ложных открытий (FDR), использующих величину, близкую к . Критерий максимальной скорости энтропии также может быть использован для выбора наиболее релевантного подмножества признаков.

Структурное обучение

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

Выбор функции квадратного программирования

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

где – вектор релевантности признаков, при условии, что всего имеется n признаков, – матрица парной избыточности признаков, а – относительные веса признаков. QPFS решается методом квадратичного программирования. Недавно было показано, что QFPS имеет тенденцию отдавать предпочтение признакам с меньшей энтропией, где и

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

Совместная взаимная информация

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

Показатель использует условную взаимную информацию и взаимную информацию для оценки избыточности между уже выбранными признаками и рассматриваемым признаком.

Регулированные деревья

Признаки из дерева решений или ансамбля деревьев оказываются избыточными. Недавний метод, называемый регуляризованным деревом, может быть использован для отбора подмножества признаков. Регуляризованные деревья налагают штраф за использование переменной, схожей с переменными, выбранными на предыдущих узлах дерева для разделения текущего узла. Регуляризованные деревья требуют построения только одной модели дерева (или одной модели ансамбля деревьев) и, следовательно, являются вычислительно эффективными. Регуляризованные деревья естественным образом обрабатывают числовые и категориальные признаки, взаимодействия и нелинейности. Они инвариантны к масштабу признаков (единицам измерения) и нечувствительны к выбросам, поэтому требуют минимальной предварительной обработки данных, такой как нормализация. Регуляризованный случайный лес (RRF) является одним из типов регуляризованных деревьев. Управляемый RRF – это улучшенная версия RRF, которая использует важность признаков, полученную из обычного случайного леса.

Обзор методов метаевристики

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

Основные принципы

Методы отбора признаков обычно классифицируются на три класса в зависимости от способа сочетания алгоритма отбора и построения модели.

Метод фильтрации

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

Метод упаковки

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

Встроенный метод

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