Методы выбора оптимального набора информативных признаков для задач классификации текстов Борисова Татьяна 3 курс ВМК МГУ

Для чего нужен выбор признаков? Количество признаков может достигать – Это слишком много для многих алгоритмов обучения (нейронные сети, наивная байесовская модель и т.д.) – «проклятье размерности»

Достоинства выбора признаков Лучше работают алгоритмы обучения Проще понять природу данных Меньше размер хранилищ

Методы выбора признаков Filters (методы-фильтры) Wrappers (методы-обертки) Embedded (встроенные методы)

Filters (методы-фильтры) Этап препроцессинга Не зависит от результата работы классификатора Достоинства: – Вычислительно быстрые – Простая реализация – Хорошо масштабируются

Независимое ранжирование признаков Information gain (прирост информации) Mutual information (взаимная информация) Критерий хи-квадрат Term strength («мощность признака») mRMR (minimum redundancy-maximum relevance, минимальная избыточность- максимальная релевантность)

Обозначения

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

Information gain (прирост информации)

Mutual information (взаимная информация)

AB CD

Критерий хи-квадрат AB CD

Term strength («мощность признака»)

mRMR (minimum redundancy- maximum relevance) Не использует информацию о категориях Может использовать взаимную информацию, критерий корреляции и т.д. Показано, что этот метод приближает теоретически оптимальный maximum-dependency метод

mRMR (minimum redundancy- maximum relevance)

Методы выбора признаков Filters (методы-фильтры) Wrappers (методы-обертки) Embedded (встроенные методы)

Wrappers (методы-обертки) Алгоритм обучения используется как «черный ящик» Оценивается информативность конкретного подмножества признаков для алгоритма обучения

Принцип работы Выполняется поиск по пространству подмножеств исходного множества признаков Для каждого шага поиска используется информация о качестве обучения на текущем подмножестве признаков

Принцип работы

Экспоненциальные алгоритмы поиска

Последовательные алгоритмы поиска

Прямой жадный алгоритм (forward selection) Обратный жадный алгоритм (backward elimination) Алгоритм восхождения на вершину (hill climbing)

Рандомизированные алгоритмы поиска Использование рандомизации для выхода из локальных минимумов Anytime-алгоритмы

Рандомизированные алгоритмы поиска Симуляция отжига Генетические алгоритмы

Прямой и обратный жадный алгоритмы Пример – прямой жадный алгоритм – обратный жадный алгоритм

Прямой и обратный жадный алгоритмы прямой жадный алгоритм обратный жадный алгоритм

Методы выбора признаков Filters (методы-фильтры) Wrappers (методы-обертки) Embedded (встроенные методы)

Выбор признаков является одним из этапов алгоритма обучения Достоинства: Наилучшим образом приспособлены для конкретной модели Не нужно проводить кросс-валидацию или разбивать тренировочную выборку

Embedded (встроенные методы) Линейная регрессия – LASSO SVM – SVM-RFE (Recursive Feature Elimination) Полиномиальная логистическая регрессия – RMNL (Random Multinomal logit): основан на случайном лесе

Методы построения признаков PCA (Principal Component Analysis, метод главных компонент) Кластеризация Автокодировщик Регуляризованный случайный лес (RRF) Применяют также спектральные и волновые преобразования

Пример работы

Спасибо за внимание!