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