Данная статья предназначена для статистиков, инженеров машинного обучения и специалистов, которые интересуются вопросами обнаружения зависимостей в наборах данных. Также материал, изложенный в статье, может быть интересен широкому кругу читателей, неравнодушных к data mining. В материале не будут затронуты вопросы feature engineering и, в частности, применения таких методов как анализ главных компонент.

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

В первой части данной статьи мы сделаем обзор некоторых методов отбора признаков и рассмотрим теоретические моменты в этом процессе. Данный раздел является скорее систематизацией наших взглядов.

Во второй части статьи на примере искусственного набора данных мы поэкспериментируем с отбором информативных признаков и сделаем сравнение результатов.

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

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

В конце статьи будут сведены результаты экспериментов и сделана ссылка на полный код R на Git.

Часть 1. Способы и методы отбора информативных признаков.

Давайте рассмотрим общий подход к классификации методов ОИП, обратившись к Вики:

Алгоритмы отбора информативных признаков могут быть представлены следующими группами: Wrappers (оберточные), Filters (фильтровочные) и Embedded (встроенные в машины). (Я оставлю без точного перевода эти термины в виду размытости их звучания для русскоязычного сообщества — прим. мое.)

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

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

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

Примеры.

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

Фильтровочным алгоритмом ОИП можно назвать перебор входных переменных, дополняемый проведением статистического теста на зависимость между отобранными переменными и выходом. Если наши входы и выход категориальны, то возможно провести тест хи-квадрат на независимость между входом (или комбинированным набором входов) и выходом с оценкой p-value и, как следствие, бинарным выводом о значимости или незначимости отобранного набора признаков. Другими примерами фильтровочных алгоритмов можно считать:

• линейную корреляцию входа и выхода;
• статистический тест на разницу в средних в случае категориальных входов и непрерывного выхода;
• F-критерий (дисперсионный анализ).

Встроенным алгоритмом ОИП является, например, значения p-values, соответствующие коэффициентам линейной регрессии. В данном случае p-value позволяет также сделать бинарный вывод о значимом отличиии коэффициента от нуля. Если отмасштабировать все входы модели, то модули весов можно трактовать как показатели важности. Также можно использовать R^2 модели — меру объяснения дисперсии процесса смоделированными значениями. Еще одним примером может служить функция оценки важности входных переменных, встроенная в random forest. Кроме того, можно использовать модули весов, соответствующие входам в искуственной нейронной сети. Этим список не исчерпывается.

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

Теперь, когда мы немного ориентируемся в основных группах методов ОИП, предлагаю обратить внимание на то, какими методами осуществляется именно перебор поднаборов входных переменных. Снова обратимся к странице Вики:

Подходы к перебору включают:

• Полный перебор
• Первый лучший кандидат
• Имитация отжига
• Генетический алгоритм
• Жадный поиск на включение
• Жадный поиск на исключение
• Particle swarm optimization
• Targeted projection pursuit
• Scatter Search
• Variable Neighborhood Search

Поиск поднабора предикторов — это дискретная задача, так как на выходе мы получаем вектор целых чисел, обозначающих индексы входов, вида:

входы: 1 2 3 4 5 6… 1000
отбор: 0 0 1 1 1 0… 1

Мы вернемся к этой особенности позднее и проиллюстрируем, к чему она ведет практически.

От того, как будет настроен поиск поднабора входных признаков, сильно зависит результат всего эксперимента. Для того чтобы интуитивно понять основное отличие в этих подходах, я предлагаю читателю поделить их на две группы: жадные (greedy) и нежадные (non-greedy).

Далее в источнике