Отбор признаков (отбор переменных, отбор атрибутов, отбор предикторов, реже — генерализация) — процесс отбора подмножества значимых признаков (как зависимых, так и независимых переменных) для построения модели в машинном обучении. Отбор признаков используется по четырём причинам:
упрощение модели для повышения интерпретируемости; для сокращения времени обучения; во избежание проклятия размерности; улучшение обобщающей способности модели и борьба с переобучением.
Центральный посыл использования техники отбора признаков — наличие в данных излишних или незначимых признаков, которые могут быть удалены без существенной потери информации. («Избыточность» и «незначимость» признаков — различные понятия, поскольку один значимый признак может быть излишним при присутствии другого значимого признака, с которым он сильно коррелирует.)
Отбор признаков следует отличать от выделения признаков. Выделение признаков создаёт новые признаки, как функции от оригинальных признаков, в то время как отбор признаков возвращает подмножество признаков. Техники отбора признаков часто используются в областях, где имеется много признаков и выборки сравнительно малы (мало точек данных). Классическими местами применения отбора признаков являются анализ рукописных текстов и ДНК-микрочипы, где имеются много тысяч признаков и от десятков до сотен экземпляров выборки.
Введение Алгоритм отбора признаков можно рассматривать как комбинацию техник поиска для представления нового поднабора признаков вместе с вычислением меры, которая отражает различие подмножеств признаков. Простейшим алгоритмом является проверка каждого возможного подмножества признаков и нахождения того, который минимизирует величину ошибки. Это исчерпывающий поиск по пространству, и он является вычислительно трудным при большом количестве признаков. Выбор метрики влияет на выбор алгоритма. Метрики различаются для трёх основных категорий алгоритмов отбора признаков: обёртки, фильтры и методы вложения.
Методы обёртывания используют модель априорной оценки результата для ранжирования поднаборов признаков. Каждый новый поднабор используется для обучения модели, которая проверяется на контрольной выборке. На этой контрольной выборке считается число ошибок (показатель ошибок модели), которое даёт оценку для данного подмножества. Так как методы обёртывания осуществляют перебор всех подмножеств признаков с последующем обучением модели, они наиболее вычислительно затратны, но дают, как правило, лучший набор признаков для конкретной модели. Методы фильтров используют косвенный показатель вместо показателя ошибки для оценки поднабора признаков. Этот показатель выбирается так, чтобы его можно было легко вычислить при сохранении показателя полезности набора признаков. Обычно применяемые меры — взаимная информация, , коэффициент корреляции смешанных моментов Пирсона, алгоритм, основанный на и расстояние между классами/внутри класса или результат критериев значимости для каждой комбинации класс/признак. Фильтры обычно вычислительно менее интенсивны, чем обёртки, но они дают наборы признаков, которые не настроены на специфичный тип прогнозирующей модели. Этот недостаток настройки означает, что набор признаков, полученный из фильтра, более общий, чем набор, полученный из обёртки, что приводит к меньшей обобщающей способности модели, чем у обёртки. Однако набор признаков не содержит предположений о прогнозирующей модели, а потому более пригоден для обнаружения связей между признаками. Многие фильтры обеспечивают ранжирование признаков, не давая явно лучшего их подмножества, а точка отсечения в ранжировании выбирается с помощью перекрёстной проверки. Методы фильтров используются также как предварительные шаги обработки для методов обёртывания, что позволяет применять обёртывание для больших задач. Другим популярным подходом является алгоритм рекурсивного исключения признаков, обычно используемый вместе с методом опорных векторов для многократного построения модели и удаления незначимых признаков. Методы вложения являются обобщающей группой техник, которые осуществляют отбор признаков как часть процесса построения модели. Примером такого подхода является метод ( — метод оценивания коэффициентов линейной регрессионной модели) для построения линейной модели, такой как -регуляризация, не давая коэффициентам модели расти и обнуляя наименее значимые. Любые признаки, которые имеют ненулевые коэффициенты регрессии, «выбираются» алгоритмом LASSO. Улучшения алгоритма LASSO включают алгоритм Bolasso, который формирует выборку путём бутстрэпа, , которая комбинирует штраф алгоритма LASSO со штрафом гребневой регрессии, и метода FeaLect, который оценивает все признаки на основе комбинаторного анализа коэффициентов регрессии. Эти подходы по вычислительной сложности оказываются где-то между фильтрами и обёртками.
В традиционной статистике наиболее популярной формой отбора признаков является , которая является техникой оборачивания. Это жадный алгоритм, который добавляет лучший признак (или удаляет худший) на каждом шаге алгоритма. Главная проблема — момент остановки алгоритма. При обучении моделей это обычно делается путём перекрёстной проверки. В статистике некоторые критерии оптимизированы. Это ведёт к наследованию проблемы вложения. Исследовались и более устойчивые методы, такие как метод ветвей и границ и кусочно-линейная сеть.
Выбор поднабора Выбор поднабора оценивает поднабор признаков, как группу стабильности. Алгоритмы выбора поднабора можно разбить на «Обёртки», «Фильтры» и «Вложения». Обёртки используют алгоритм поиска для анализа пространства на возможные признаки и оценивают каждый поднабор путём прогона модели на поднаборе. Обёртки могут быть вычислительно затратны и имеют риск переобучения модели. «Фильтры» похожи на «Обёртки» по подходу к поиску, но вместо оценки модели ранжируется более простой фильтр. Техники «Вложения» встраиваются в модель и специфичны для неё.
Многие популярные подходы используют жадный поиск восхождением к вершине, который итеративно оценивает поднабор признаков как кандидата, затем модифицирует поднабор и оценивает, насколько новый поднабор лучше старого. Оценка поднабора требует использования оценочной , которая ранжирует поднаборы признаков. Исчерпывающий поиск, как правило, невыполним, так что разработчик (или оператор) определяет точку остановки, и поднабор признаков с наибольшей достигнутой оценкой, обнаруженный к этому моменту, выбирается как удовлетворительный поднабор признаков. Критерий остановки зависит от алгоритма. Возможные критерии: оценка поднабора превышает порог, программа превысила максимальное допустимое время, и так далее.
Альтернативные техники на основе поиска базируются на , который находит проекции низкой размерности данных с высокой оценкой — выбираются признаки, которые имеют наибольшие проекции в пространстве низкой размерности.
Подходы для поиска:
Исчерпывающий поиск Поиск по первому наилучшему совпадению Имитации отжига Генетический алгоритм Жадный прямой отбор Жадное обратное исключение Метод роя частиц
Распределенный поиск
Две популярные метрики фильтров для задач классификации — корреляция и взаимная информация, хотя ни одна из них не является истинной или «мерой расстояния» в математическом смысле, поскольку для них не выполняется неравенство треугольника, а потому они не представляют действительного «расстояния» — их следует, скорее, понимать как «оценку». Эти оценки вычисляются между признаками-кандидатами (или наборами признаков) и желаемой категорией. Есть, однако, истинные метрики, которые являются простыми функциями от взаимной информации.
Другие возможные метрики фильтров:
Отделимость классов Вероятность ошибки Межклассовое расстояние Вероятностное расстояние Энтропия Выбор признаков на основе непротиворечивости Выбор признаков на основе корреляции.
Критерий оптимальности Выбор критерия оптимальности сложен, так как имеется несколько целей в задаче отбора признаков. Многие критерии включают меру точности со штрафованием числом выбранных признаков (например, байесовский информационный критерий). Наиболее старыми являются и информационный критерий Акаике (, AIC). Они добавляют переменные, если t-статистика превосходит .
Другими критериями являются байесовский информационный критерий (БИК, , BIC), который использует , минимальная длина описания (, MDL), который асимптотически использует , Бонферрони / RIC, который использует , отбор признаков с максимальной зависимостью, и набор новых критериев, которые продиктованы идеей (, FDR) и которые используют нечто, близкое к . Критерий максимума энтропийной скорости может также быть использован для выбора наиболее значимого поднабора признаков.
Структурное обучение Фильтр отбора признаков является специальным случаем более общей парадигмы с названием «структурное обучение». Выбор признаков находит значимый набор признаков для конкретной целевой переменной, в то время как структурное обучение находит связи между переменными, обычно выражая эти связи в виде графа. Наиболее распространённые алгоритмы структурного обучения предполагают, что данные генерируются байесовской сетью, так что структура является ориентированной графовой моделью. Оптимальное решение задачи фильтра отбора признаков является марковским ограждением целевого узла и в байесовской сети имеется единственное марковское ограждение для каждого узла.
Механизмы отбора признаков на основе информационной теории Есть различные механизмы отбора признаков, которые используют взаимную информацию для оценки различных признаков. Они обычно используют один и тот же алгоритм:
Вычисляется взаимная информация как оценка между всеми признаками () и целевым классом () Выбирается признак с наибольшей оценкой (например, ) и добавляется в набор отобранных признаков () Вычисляется оценка, которая может быть получена из взаимной информации Выбираем признак с наибольшей оценкой и добавляем в набор отобранных признаков (например, ) Повторяем шаги 3. и 4. Пока не наберём определённое число признаков (например, )
Наиболее простой подход использует взаимную информацию в качестве «производной» оценки.
Однако, есть различные походы, которые пытаются уменьшить избыточность между признаками.
Выбор признаков на основе минимальной избыточности-максимальной релевантности Пэн, Лон и Дин предложили метод отбора признаков, который может использовать взаимную информацию, корреляцию или оценку расстояния/похожести для отбора признаков. Целью является наложение штрафа на значимость признака при избыточности, вызванной присутствием в других выбранных признаках. Значимость набора признаков для класса определяется средним значением всех значений взаимной информации между индивидуальным признаком и классом :
Избыточность всех признаков в наборе равна среднему значению всех значений взаимной информации между признаком и признаком :
Критерий минимальной избыточности-максимальной релевантности (, mRMR) является комбинацией двух мер, заданных выше и определённой как:
Предположим, что имеется полный набор из признаков. Пусть будет индикаторной функцией вхождения в множество , так что отражает присутствие, а отражает отсутствие признака в глобальном оптимальном наборе признаков. Пусть и . Формула выше может теперь быть переписана как задача оптимизации: