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

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

Задача уменьшения размерности

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

Зачем нужно?

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

Проклятие размерности (curse of dimensionality)

Проклятие размерности (curse of dimensionality) — это набор проблем, возникающих с ростом размерности

• Увеличиваются требования к памяти и вычислительной мощности
• Данные становятся более разреженными
• Проще найти гипотезы, не имеющие отношения к реальности

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

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

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

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

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

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

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

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

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

Цель извлечения признаков:

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

данных

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

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

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

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

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

• Избыточные (redundant) признаки не привносят

дополнительной информации относительно существующих

• Нерелевантные (irrelevant) признаки просто

неинформативны

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

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

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

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

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

• Опираются на конкретный алгоритм
• Специфичны для каждого алгоритма

Схема встроенного метода

Пример: случайный лес

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

Пример: SVM-RFE

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

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

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

Схема метода-обертки

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

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

оптимизации в пространстве бинарных векторов:

• Поиск восхождением на холм
  • Генетические алгоритмы
  • . . .

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

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

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

Недостатки:

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

Фильтры

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

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

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

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

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

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

Корреляция

Коэффициент корреляции Пирсона Файл:Таблица 6.jpg Коэффициент корреляции Спирмана

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

Правило обрезки κ

• Число признаков
• Порог значимости признаков
• Интегральный порог значимости признаков
• Метод сломанной трости
• Метод локтя

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

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

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

Недостатки:

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

предсказательная модель

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

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

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

Недостатки:

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

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

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

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

• сначала применим фильтр (или набор фильтров), отсеяв лишние

признаки

• затем применим метод-обертку или встроенный метод

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки:

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