[Перевод] Обзор методов отбора признаков08.10.2019 15:18

Правильный отбор признаков для анализа данных позволяет:

повысить качество моделей машинного обучения с учителем и без,
уменьшить время обучения и снизить требуемые вычислительные мощности,
а в случае входных данных высокой размерности позволяет ослабить «проклятие размерности».

Оценка важности признаков необходима для интерпретации результатов модели.

Мы рассмотрим существующие методы отбора признаков для задач обучения с учителем и без. Каждый метод проиллюстрирован open source-реализацией на Python, чтобы вы могли быстро протестировать предложенные алгоритмы. Однако это не полная подборка: за последние 20 лет было создано множество алгоритмов, и здесь вы найдёте самые основные из них. Для более глубокого исследования ознакомьтесь с этим обзором.

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

Методы отбора признаков обычно делят на 4 категории: фильтры, обёртки, встроенные и гибридные.

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

Существующие стратегии отбора:

Прямой отбор (Forward selection): начинаем с пустого набора признаков, а затем итеративно добавляем признаки, обеспечивающие наилучший прирост качества моделей.
Обратный отбор (Backward selection): начинаем с набора, состоящего из всех признаков, далее, на каждой итерации убираем «худший» признак.

Реализация: эти алгоритмы реализованы в пакете mlxtend, вот пример использования.
К этой группе относятся алгоритмы, которые одновременно обучают модель и отбирают признаки. Обычно это реализуют с помощью l1-регуляризатора (sparsity regularizer) или условия, которое ограничивает некоторые признаки.

SMLR (Sparse Multinomial Logistic Regression, разреженная мультиноминальная логистическая регрессия): этот алгоритм реализует l1-регуляризацию с помощью ARD (Automatic relevance determination, автоматическое определение релевантности) в рамках классической мультиноминальной логистической регрессии. Регуляризация определяет важность каждого признака и обнуляет те, которые бесполезны для прогнозирования.
Реализация: SMLR
ARD (Automatic Relevance Determination Regression, регрессия автоматического определения релевантности): модель использует байесовскую гребневую регрессию (Bayesian Ridge Regression). Она сильнее смещает веса коэффициентов в сторону нуля по сравнению, например, с методом наименьших квадратов.
ARD обнуляет вес некоторых признаков, тем самым помогая идентифицировать релевантные размерности.
Реализация: scikit-learn

Другие примеры алгоритмов регуляризации: Lasso (реализует l1-регуляризацию), гребневая регрессия (реализует l2-регуляризацию), Elastic Net (реализует l1 — и l2-регуляризацию). Если изобразить эти способы графически, то видно, что регрессия Lasso ограничивает коэффициенты площадью квадрата, гребневая регрессия очерчивает круг, а Elastic Net занимает промежуточное положение.

https://scikit-learn.org/stable/auto_examples/linear_model/plot_sgd_penalties.html

Здесь представлено исчерпывающее описание этих алгоритмов.

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

Методы с учителем

Relief: Этот метод случайным образом выбирает из датасета образцы и обновляет значимость каждого признака на основе разницы между выбранным экземпляром и двумя ближайшими к нему объектами того же и противоположного классов. Если наблюдается разница в значениях признака для двух ближайших соседей одного класса, его важность снижается, а если, наоборот, наблюдается различие между значениями признака для объектов разных классов, важность, соответственно, повышается.
$W_{i}=W_{i}-(x_{i}-nearHit_{i})^{2}+(x_{i}-nearMiss_{i})^{2}$
Вес признака уменьшается, если его значение отличается для ближайших объектов одного и того же класса больше, чем для ближайших объектов из разных классов; в противном случае вес увеличивается.
Расширенный алгоритм ReliefF использует взвешивание признаков и ищет по большему количеству ближайших соседей.
Реализация: scikit-rebate, ReliefF
Критерий Фишера (Fisher score): Обычно используется в задачах бинарной классификации. Отношение Фишера (Fisher ratio, FiR) определяется как расстояние между средними значениями признаков для каждого класса, деленное на их дисперсии:
$FiR_{i}=\frac{\left |\bar{X}_{i}^{(0)} - \bar{X}_{i}^{(1)} \right |}{\sqrt{var(X_{i})^{(0)}+var(X_{i})^{(1)}}}$
Реализация: scikit-feature, пример использования.
Критерий хи-квадрат (Chi-squared score): Проверяет, есть ли значимая разница между наблюдаемой и ожидаемой частотами двух категориальных переменных. Таким образом, проверяется нулевая гипотеза об отсутствии связи между двумя переменными.
$X^{2}=\frac{(\textrm{Observed frequency} - \textrm{Expected frequency})^2}{\textrm{Expected frequency}}$

Критерий независимости хи-квадрат.
Чтобы корректно применять критерий хи-квадрат для проверки связи между разными признаками из датасета и целевой переменной, необходимо соблюсти условия: переменные должны быть категориальными, независимыми и должны иметь ожидаемую частоту больше 5. Последнее условие гарантирует, что CDF (cumulative density function) статистического критерия (test statistic) может быть аппроксимирован с помощью распределения хи-квадрат. Подробнее рассказано здесь.
Реализация: sklearn, scipy
CFS (Correlation-based feature selection, отбор признаков на основе корреляции): Обоснование этого метода можно сформулировать так:
Признаки релевантны, если их значения систематически меняются в зависимости от принадлежности к той или иной категории.

Таким образом, хорошее подмножество признаков содержит такие признаки, которые высоко коррелируют с целевой переменной, и при этом не коррелируют друг с другом. Оценка подмножества из k признаков вычисляется так:
$Merit_{S_{k}}=\frac{kr_{cf}}{\sqrt{k+k(k-1)\bar{r}_{ff}}}$
Здесь $r_{cf}$ — это среднее значение всех корреляций между признаком и классом, а $\bar{r}_{ff}$ — среднее значение всех корреляций между признаками. Критерий CFS определяется так:
$CFS = \underset{S_{k}}{max}\left [ \frac{r_{cf_{1}}+r_{cf_{2}}+\cdots +r_{cf_{k}}}{\sqrt{k + 2(r_{f_{1}f_{2}}+\cdots +r_{f_{i}f_{j}}+\cdots +r_{f_{k}f_{1}})}} \right ]$
Реализация: scikit-feature, пример использования.
FCBF (Fast correlation-based filter, быстрый фильтр на основе корреляции): Этот метод работает быстрее и эффективнее, чем ReliefF и CFS, и поэтому чаще используется для входных данных высокой размерности. По сути, этот типичный подход, учитывающий релевантность и избыточность, в рамках которого сначала для всех признаков вычисляются Symmetrical Uncertainty (взаимная информация между X и Y I (X, Y), деленная на сумму их энтропий), затем признаки сортируются по этому критерию, а потом удаляются избыточные.
Реализация: skfeature, https://github.com/shiralkarprashant/FCBF

Методы без учителя

Дисперсия: было показано, что оценка дисперсии признака может быть эффективным способом отбора признаков. Как правило признаки с почти нулевой дисперсией не являются значимыми, и их можно удалить.
Реализациия: Variance Threshold
Средняя абсолютная разность: Вычисляем среднюю абсолютную разность между значениями признака и его средним значением (реализация).
$MAD_{i}=\frac{1}{n}\sum_{j=1}^{n}\left | X_{ij} - \bar{X}_{i}\right |$
Более высокие значения, как правило, имеют более высокую предсказательную силу.
Соотношение дисперсий: Среднее арифметическое, деленное на среднее геометрическое. Более высокая дисперсия соответствует более релевантным признакам (реализация).
$AM_{i}=\bar{X_{i}}=\frac{1}{n}\sum_{j=1}^{n}X_{ij}$
$GM_{i}=(\prod_{j=1}^{n} X_{ij})$
Поскольку $AM_{i} \geqslant GM_{i}$ , если и только если соблюдается равенство $X_{i1}=X_{i2}=\cdots =X_{in}$ , тогда:
$R_{i}=\frac{AM_{i}}{GM_{i}}\in \left [1, +\infty \right )$
Критерий Лапласа (Laplacian Score): В его основе лежит наблюдение, что данные из одного класса часто расположены ближе друг к другу, поэтому можно оценить важность признака по его способности отражать эту близость. Метод состоит из встраивания данных в граф ближайших соседей с помощью измерения произвольного расстояния с последующим вычислением матрицы весов. Затем для каждого признака вычисляем критерий Лапласа и получаем такое свойство, что наименьшие значения соответствуют самым важным размерностям. Однако на практике при отборе подмножества признаков обычно применяется другой алгоритм кластеризации (метод k-средних), с помощью которого выбирается самая эффективная группа.
Реализация: scikit-feature
Критерий Лапласа в сочетании с энтропией на основе расстояния: в основе алгоритма лежит критерий Лапласа, где кластеризация методом k-средних заменяется на энтропию. Алгоритм демонстрирует более высокую стабильность на датасетах высокой размерности (реализация).
MCFS (Multi-Cluster Feature selection, многокластерный отбор признаков): для измерения корреляции между разными признаками выполняется спектральный анализ. Для кластеризации данных и оценки признаков используются собственные вектора оператора Лапласа (graph Laplacian). Их вычисление описывается в этой работе.
Реализация: https://github.com/danilkolikov/fsfc
Алгоритмы LFSBSS (Localised feature selection, отбор локализованных признаков), взвешенные k-средние (weighted k-means), SPEC и Apriori рассмотрены здесь и реализованы в этом пакете.

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

Полный список других алгоритмов отбора признаков, о которых я не упомянул, был реализован в пакете scikit-feature.

Определять релевантные признаки можно также с помощью PLS (Partial least squares, частично наименьшие квадраты), как рассказывается в этой статье, или с помощью методов линейного уменьшения размерности, как показано здесь.