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

в 12:00, , рубрики: Алгоритмы, Блог компании Инфосистемы Джет, машинное обучение, отбор признаков

Обзор методов отбора признаков - 1

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

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

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

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

Модели с учителем и без

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

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

Обёртки

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

Обзор методов отбора признаков - 2

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

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

Реализация: эти алгоритмы реализованы в пакете mlxtend, вот пример использования.

  • RFE (Recursive feature elimination, рекурсивное удаление признаков): «жадный» алгоритм поиска, который отбирает признаки с помощью рекурсивного определения всё более маленьких наборов признаков. Он ранжирует признаки по очерёдности их удаления.

    Реализация: scikit-learn

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

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

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

    Реализация: SMLR

  • ARD (Automatic Relevance Determination Regression, регрессия автоматического определения релевантности): модель использует байесовскую гребневую регрессию (Bayesian Ridge Regression). Она сильнее смещает веса коэффициентов в сторону нуля по сравнению, например, с методом наименьших квадратов.

    Обзор методов отбора признаков - 3

    ARD обнуляет вес некоторых признаков, тем самым помогая идентифицировать релевантные размерности.

    Реализация: scikit-learn

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

Обзор методов отбора признаков - 4
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, частично наименьшие квадраты), как рассказывается в этой статье, или с помощью методов линейного уменьшения размерности, как показано здесь.

Перевели «Инфосистемы Джет»

Автор: JetHabr

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js