Обсуждение участника: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

600px

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

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

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

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

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

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

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

Недостатки:

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

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

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

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

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

Недостатки:

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

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

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

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

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

признаки

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки:

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