Обсуждение участника:Gen05

Выбор признаков (Feature selection)

Уменьшение размерности

Под уменьшением размерности (англ. dimensionality reduction) в машинном обучении подразумевается уменьшение числа признаков набора данных. Наличие в нем признаков избыточных, неинформативных или слабо информативных может понизить эффективность модели, а после такого преобразования она упрощается, и соответственно уменьшается размер набора данных в памяти и ускоряется работа алгоритмов ML на нем. Уменьшение размерности может быть осуществлено методами выбора признаков (англ. feature selection) или выделения признаков (англ. feature extraction).

Определение:

Объекты описаны признаками $F = (f_1, . . . , f_n)$. Задачей является построить множество признаков $G = (g_1, ... , g_k) : k < n$ (часто $k << n$), переход к которым сопровождается наименьшей потерей информации.

Зачем нужно

• Ускорение обучения и обработки
• Борьба с шумом и мультиколлинеарностью
• Интерпретация и визуализация данных

Определение:

Проклятие размерности (curse of dimensionality) — это набор проблем, возникающих с ростом размерности Увеличиваются требования к памяти и вычислительной мощности Данные становятся более разреженными Проще найти гипотезы, не имеющие отношения к реальности

Когда применяется

• Нужно использовать меньше памяти для хранения данных
• Нужно уменьшить время обработки
• Нужно увеличить качество обработки
• Нужно понять природу признаков

Методы уменьшения размерности

Замечание:
Уменьшение размерности — шаг в предобработке данных

Два основных подхода уменьшения размерности

Выбор признаков (feature selection) включает методы, для которых $G ⊂ F$. Они:

• Быстро работают;
• Не могут «выдумывать» сложных признаков.

Извлечение признаков (feature extraction) включает все другие методы (в том числе даже те, у которых $k > n$).

• В целом, дольше работают;
• Могут извлекать сложные признаки.

Цели извлечения и выбора признаков

• Уменьшение числа ресурсов, требуемых для обработки больших наборов данных
• Поиск новых признаков
• Эти признаки могут быть линейными и нелинейными относительно исходных

Цели выбора признаков:

• Уменьшение переобучения и улучшение качества предсказания
• Улучшение понимания моделей

Типы ненужных признаков

Существуют также два типа признаков, которые не являются необходимыми:

• Избыточные (redundant) признаки не привносят дополнительной информации относительно существующих
• Нерелевантные (irrelevant) признаки просто неинформативны

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

Определение:

Встроенные методы (embedded methods) — это методы выбора признаков, при которых этот выбор осуществляется в процессе работы других алгоритмов (классификаторов и регрессоров) Опираются на конкретный алгоритм Специфичны для каждого алгоритма

Процесс работы встроенных методов

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

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

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

Классификация методов выбора признаков

• Встроенные методы (embedded)
• Фильтрующие методы (filter)
  • Одномерные (univariate)
  • Многомерные (multivariate)
• Методы-обертки (wrapper)
  • Детерминированные (deterministic)
  • Стохастические (stochastic)
• Гибридные и ансамблирующие методы

Пример:

Cлучайный лес Случайный лес Учитывать число вхождений признака в дерево. Учитывать глубину вершины вхождения признака в дерево.

Пример:

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

Методы-обертки

Процесс работы оберточных методов

Метод-обертка (wrapper method) использует алгоритм (классификатор или регрессор) для оценки качества получаемого подмножества признаков и использует алгоритмы дискретной оптимизации для поиска оптимального подмножества признаков.

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

Существует несколько типов оберточных методов: детерминированные, которые изменяют множество признаков по определенному правилу, а также рандомизированные, которые используют генетические алгоритмы для выбора искомого подмножества признаков.

Классификация методов-оберток

• Детерминированные:
  • SFS (sequential forward selection)
  • SBE (sequential backward elimination)
  • SVM-RFE
  • Перестановочная полезность (Permutation importance)
• Стохастические — сводят задачу выбора признаков к задаче оптимизации в пространстве бинарных векторов:
  • Поиск восхождением на холм
  • Генетические алгоритмы

Анализ методов-оберток

Достоинства:

• Более высокая точность, чем у фильтров
• Используют отношения между признаками
• Оптимизируют качество предсказательной модели в явном виде

Недостатки:

• Очень долго работают
• Могут переобучиться при неправильной работе с разбиением набора данных

Фильтры

Фильтры (англ. filter methods) измеряют релевантность признаков на основе функции $\mu$, и затем решают по правилу $\kappa$, какие признаки оставить в результирующем множестве.

Фильтры могут быть:

• Одномерные (англ. univariate) — функция $\mu$ определяет релевантность одного признака по отношению к выходным меткам. В таком случае обычно измеряют "качество" каждого признака и удаляют худшие;
• Многомерные (англ. multivariate) — функция $\mu$ определяет релевантность некоторого подмножества исходного множества признаков относительно выходных меток.

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

Фильтры (filter methods) оценивают качество отдельных признаков или подмножеств признаков и удаляют худшие

Две компоненты:

• мера значимости признаков $\mu$
• правило обрезки κ определяет, какие признаки удалить на основе $\mu$

Схема фильтрующих методов

Классификация фильтрующих методов

• Одномерные (univariate):
  • Евклидово расстояние
  • Коэффициент корреляции (Пирсона или Спирмена)
  • Попарные расстояния (внутренние или внешние)
  • Условная дисперсия
  • Прирост информации (IG)
  • Индекс Джини
  • $\chi^2$
• Многомерные (multivariate):
  • Выбор признаков на основе корреляций (CFS)
  • Фильтр марковского одеяла (MBF)

Коэффициент корреляции Пирсона
[math]r=\displaystyle \frac{\sum_{i, j}(x_{ij}-\bar{x_j})(y_i-\bar{y})}{\sqrt{\sum_{i, j}(x_{ij}-\bar{x_j})^2\sum_i(y_i-\bar{y})^2}}\in[-1;1][/math]

Коэффициент корреляции Спирмана

1. Отсортировать объекты двумя способами (по каждому из признаков).
2. Найти ранги объектов для каждой сортировки.
3. Вычислить корреляцию Пирсона между векторами рангов.

Information gain:
$IG(x, y)=\displaystyle -\sum_{i=1}^kp(c_i)\log_2{(p(c_i))}+\sum_{i=1}^{n}p(t_i)\sum_{j=1}^kp(c_j|t_i)log_2{(p(c_j|t_i))}$

Анализ одномерных фильтров

Преимущества:

• Исключительно быстро работают
• Позволяют оценивать значимость каждого признака

Недостатки:

• Порог значимости признаков
• Игнорируют отношения между признаками и то, что реально использует предсказательная модель

Анализ многомерных фильтров

Преимущества:

• Работают достаточно быстро
• Учитывают отношения между признаками

Недостатки:

• Работают существенно дольше фильтров
• Не учитывают то, что реально использует предсказательная модель

Гибриды и ансамбли

Гибридный подход

Будем комбинировать подходы, чтобы использовать их сильные стороны Самый частый вариант:

• сначала применим фильтр (или набор фильтров), отсеяв лишние признаки
• затем применим метод-обертку или встроенный метод

Схема гибридного подхода

Ансамблирование в выборе признаков

Подход к ансамблированию состоит в построении ансамбля алгоритмов выбора признаков

Ансамбль на уровне моделей

Строим ансамбль предсказательных моделей

Ансамбль на уровне ранжирований

Объединяем ранжирования

Ансамбль на уровне мер значимости

Объединяем меры значимости

Анализ гибридных и ансамблирующих методов

Преимущества:

• Чаще всего лучше по времени и по качеству

Недостатки:

• Иногда теряется интерпретируемость
• Иногда требуется заботиться о проблеме переобучения