Feature selection в алгоритмах классификации

Существует один очень простой и эффективный способ улучшения алгоритмов классификации, который называется feature selection (выбор классификационных признаков). Этот метод позволяет при построении модели выбрать только самые показательные признаки (например, слова) и отсеять остальные.

Что такое показательные признаки? Если мы говорим о задаче классификации текстовых документов, то это слова которые несут информацию о классе к которому относится документ. Например, в контексте автомобильной тематики слово “Nissan”, скорее всего будет показательным признаком, а вот слово “новый” вряд ли. Использование для классификации не всех слов, а только показательных дает несколько преимуществ.

Во-первых, feature selection позволяет существенно уменьшить количество параметров модели (используемых для классификации слов), и как следствие снижает требования к объему памяти требуемой для классификации.

Во-вторых, feature selection может повысить точность алгоритма за счет удаления из модели слов с низким соотношением сигнал/шум. Представьте, что слово “аскетичный” встретилось в обучающей выборке 3 раза, – 1 раз в рамках класса “Авто” и 2 раза в рамках класса “Одежда”. Формально оно говорит в пользу класса “Одежда”, но вряд ли это слово можно считать хорошим классификационным признаком. Скорее всего, перевес в сторону одежды это случайность.

Но сам факт наличия такого слова в обучающей выборке не случайность. Это следствие закона Зипфа (Zipf’s law), который описывает распределение частот слов в натуральном языке. Простым языком это можно описать следующим образом, если вы возьмете любой достаточно большой корпус документов и посчитаете сколько в нем слов встречающихся ровно 1 раз, 2 раза, 3 раза и т.д., то окажется что большинство слов встречаются 1 раз. Это не должно быть большим сюрпризом, – в повседневной жизни мы используем довольно небольшое количество слов (высокочастотники), а большую часть слов мы практически не используем (низкочастотники).

Mutual Information Link to heading

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

Для того чтобы рассчитать численное значение взаимной информации необходимо составить матрицу цитирумости. Матрица цитируемости – это матрица 2x2 которая показывает взаимоотношение конкретного слова с конкретным классов. Возьмем, к примеру слово “Toyota” и класс “Авто”.

Из этой матрицы видно что слово “Toyota” было встречено в 65 342 документах в контексте класса “Авто”, а также в 143 документах за переделами класса “Авто”. Имея на руках такую матрицу мы можем рассчитать взаимную информацию по формуле:

$$ MI = \frac{N_{11}}{N} \log_2{ \frac{N N_{11}}{N_{1.} N_{.1}} } + \frac{N_{01}}{N} \log_2{ \frac{N N_{01}}{N_{0.} N_{.1}} } + \frac{N_{10}}{N} \log_2{ \frac{N N_{10}}{N_{1.} N_{.0}} } + \frac{N_{00}}{N} \log_2{ \frac{N N_{00}}{N_{0.} N_{.0}} } $$

где, $ N $ — сумма всей матрицы, $ N_{0.} = N_{00} + N_{01} $, $ N_{.1} = N_{01} + N_{11} $ и т.д.

Взаимная информация всегда находится в диапазоне от нуля до единицы. Чем выше значение, тем сильнее связь между наличием/отсутствием слова и наличием/отсутствием класса. Рассчитав взаимную информацию для всех пар слово-класс мы можем оставить для каждого класса первые N слов, объединить эти слова в общий словарь и теперь только их использовать для классификации. Количество слов необходимых для оптимальной классификации зависит от конкретной задачи и его необходимо подбирать эмпирически, постоянно проверяя результаты на тестовой выборке.

На тех задач на которых я тестировал этот метод, он давал прирост точности от 3 до 10%. В Introduction to Infromation Retrieval указано что на практике возможен прирост в десятки процентов по F₁¹. Все зависит от вашей конкретной задачи, а также классификационного алгоритма.