Обсуждение участника:Gen05 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача уменьшения размерности)
(Фильтры)
 
(не показано 58 промежуточных версий этого же участника)
Строка 1: Строка 1:
== Выбор признаков (Feature selection) ==
+
'''Выбор признаков (''Feature selection'')'''
  
== Уменьшение размерности ==
+
= Уменьшение размерности =
  
 +
Под '''уменьшением размерности''' (англ. ''dimensionality reduction'') в машинном обучении подразумевается уменьшение числа признаков набора данных. Наличие в нем признаков избыточных, неинформативных или слабо информативных может понизить эффективность модели, а после такого преобразования она упрощается, и, соответственно, уменьшается размер набора данных в памяти и ускоряется работа алгоритмов ML на нем. Уменьшение размерности может быть осуществлено методами выбора признаков (англ. ''feature selection'') или выделения признаков (англ. ''feature extraction'').
  
===Задача уменьшения размерности===
+
{{Определение
 +
|definition=
 +
Объекты описаны признаками $F = (f_1, . . . , f_n)$. <br>
 +
Задачей является построить множество признаков $G = (g_1, ... , g_k) : k < n$ (часто $k << n$), переход к которым сопровождается наименьшей потерей информации.
 +
}}
  
Объекты описаны признаками F = (f1, . . . , fn).
+
==Зачем нужно==
Задачей является построить множество признаков G = (g1, . . . , gk) : k < n (часто
+
* Ускорение обучения и обработки
k ≪ n), переход к которым сопровождается наименьшей потерей
+
* Борьба с шумом и мультиколлинеарностью
информации.
+
* Интерпретация и визуализация данных
  
'''Зачем нужно?'''
+
{{Определение
*Ускорение обучения и обработки
+
|definition=
*Борьба с шумом и мультиколлинеарностью
+
Проклятие размерности (''curse of dimensionality'') — это набор проблем, возникающих с ростом размерности
*Интерпретация и визуализация данных
+
* Увеличиваются требования к памяти и вычислительной мощности
 +
* Данные становятся более разреженными
 +
* Проще найти гипотезы, не имеющие отношения к реальности
 +
}}
  
===Проклятие размерности (curse of dimensionality)===
+
==Когда применяется==
Проклятие размерности (curse of dimensionality) — это набор
+
 
проблем, возникающих с ростом размерности
+
* Нужно использовать меньше памяти для хранения данных
*Увеличиваются требования к памяти и вычислительной мощности
+
* Нужно уменьшить время обработки
*Данные становятся более разреженными
+
* Нужно увеличить качество обработки
*Проще найти гипотезы, не имеющие отношения к реальности
+
* Нужно понять природу признаков
===Ситуации применения===
+
 
 +
[[Файл:Таблица_1.jpg|600px|thumb|right|Методы уменьшения размерности]]
 +
 
 +
'''Замечание:'''<br>
 
Уменьшение размерности — шаг в предобработке данных
 
Уменьшение размерности — шаг в предобработке данных
*Меньше памяти для хранения
+
 
*Уменьшение времени обработки
+
==Два основных подхода уменьшения размерности==
*Увеличение качества обработки
+
 
*Понимание природы признаков
+
'''Выбор признаков''' (''feature selection'') включает методы, для которых $G ⊂ F$. Они:
===Методы уменьшения размерности===
+
* Быстро работают;
[[Файл:Таблица_1.jpg]]
+
* Не могут «выдумывать» сложных признаков.
===Два основных подхода уменьшения размерности===
+
 
Выбор признаков (feature selection) включает методы, для которых
+
'''Извлечение признаков''' (''feature extraction'') включает все другие методы (в том числе даже те, у которых $k > n$).
G ⊂ F. Они
+
* В целом, дольше работают;
*быстро работают;
+
* Могут извлекать сложные признаки.
*не могут «выдумывать» сложных признаков.
+
 
Извлечение признаков (feature extraction) включает все другие
+
==Цели извлечения и выбора признаков==
методы (в том числе даже те, у которых k > n).
+
* Уменьшение числа ресурсов, требуемых для обработки больших наборов данных
*в целом, дольше работают;
+
* Поиск новых признаков
*могут извлекать сложные признаки.
+
* Эти признаки могут быть линейными и нелинейными относительно исходных
===Цели извлечения и выбора признаков===
+
 
====Цель извлечения признаков:====
+
===Цели выбора признаков:===
*Уменьшение числа ресурсов, требуемых для обработки больших наборов
+
* Уменьшение переобучения и улучшение качества предсказания
данных
+
* Улучшение понимания моделей
*Поиск новых признаков
+
 
*Эти признаки могут быть линейными и нелинейными относительно исходных
+
==Типы ненужных признаков==
====Цели выбора признаков:====
 
*Уменьшение переобучения и улучшение качества предсказания
 
*Улучшение понимания моделей
 
===Типы ненужных признаков===
 
 
Существуют также два типа признаков, которые не являются необходимыми:
 
Существуют также два типа признаков, которые не являются необходимыми:
*Избыточные (redundant) признаки не привносят
+
* Избыточные (''redundant'') признаки не привносят дополнительной информации относительно существующих
дополнительной информации относительно существующих
+
* Нерелевантные (''irrelevant'') признаки просто неинформативны
*Нерелевантные (irrelevant) признаки просто
+
 
неинформативны
+
=Встроенные методы=
==Встроенные методы==
+
 
===Классификация методов выбора признаков===
+
{{Определение
*Встроенные методы (embedded)
+
|definition=
*Фильтрующие методы (filter)
+
Встроенные методы (''embedded methods'') — это методы выбора
**Одномерные (univariate)
 
**Многомерные (multivariate)
 
*Методы-обертки (wrapper)
 
**Детерминированные (deterministic)
 
**Стохастические (stochastic)
 
*Гибридные и ансамблирующие методы
 
===Встроенные методы===
 
Встроенные методы (embedded methods) — это методы выбора
 
 
признаков, при которых этот выбор осуществляется в процессе работы
 
признаков, при которых этот выбор осуществляется в процессе работы
 
других алгоритмов (классификаторов и регрессоров)
 
других алгоритмов (классификаторов и регрессоров)
*Опираются на конкретный алгоритм
+
* Опираются на конкретный алгоритм
*Специфичны для каждого алгоритма
+
* Специфичны для каждого алгоритма
===Схема встроенного метода===
+
}}
[[Файл:Таблица_2.jpg]]
+
 
===Пример: случайный лес===
+
[[File:Feature_selection_embedded_rus.png|600px|thumb|right|Процесс работы встроенных методов]]
*Учитывать число вхождений признака в дерево.
+
 
*Учитывать глубину вершины вхождения признака в дерево.
+
Группа '''встроенных методов''' (англ. ''embedded methods'') очень похожа на оберточные методы, но для выбора признаков используется непосредственно структуру некоторого классификатора. В оберточных методах классификатор служит только для оценки работы на данном множестве признаков, тогда как встроенные методы используют какую-то информацию о признаках, которую классификаторы присваивают во время обучения.
[[Файл:Таблица_3.jpg]]
+
 
===Пример: SVM-RFE===
+
Одним из примеров встроенного метода является реализация на [[Дерево решений и случайный лес| случайном лесе]]: каждому дереву на вход подаются случайное подмножество данных из датасета с каким-то случайным набор признаков, в процессе обучения каждое из деревьев решений производит «голосование» за релевантность его признаков, эти данные агрегируются, и на выходе получаются значения важности каждого признака набора данных. Дальнейший выбор нужных нам признаков уже зависит от выбранного критерия отбора.
#Обучить SVM на обучающем подмножестве
+
 
#Установить веса признаков, равными модулям соответствующих коэффициентов
+
Встроенные методы используют преимущества оберточных методов и являются более эффективными, при этом на отбор тратится меньше времени, уменьшается риск [[переобучение|переобучения]], но т.к. полученный набор признаков был отобран на основе знаний о классификаторе, то есть вероятность, что для другого классификатора это множество признаков уже не будет настолько же релевантным.
#Отранжировать признаки согласно их весам
+
 
#Выбросить некоторое число признаков с наименьшими весами
+
==Классификация методов выбора признаков==
#Повторять, пока не останется нужное число признаков
+
* Встроенные методы (''embedded'')
==Методы-обертки==
+
* Фильтрующие методы (''filter'')
Метод-обертка (wrapper method) использует алгоритм
+
** Одномерные (''univariate'')
(классификатор или регрессор) для оценки качества получаемого
+
** Многомерные (''multivariate'')
подмножества признаков и использует алгоритмы дискретной
+
* Методы-обертки (''wrapper'')
оптимизации для поиска оптимального подмножества признаков.
+
** Детерминированные (''deterministic'')
===Схема метода-обертки===
+
** Стохастические (''stochastic'')
[[Файл:Таблица_4.jpg]]
+
* Гибридные и ансамблирующие методы
===Классификация методов-оберток===
+
 
*Детерминированные:
+
{{Пример
**SFS (sequential forward selection)
+
|example='''Cлучайный лес'''
**SBE (sequential backward elimination)
+
[[Файл:Таблица_3.jpg|500px|thumb|right|Случайный лес]]
**SVM-RFE
+
{{main|Дерево решений и случайный лес}}
**Перестановочная полезность (Permutation importance)
+
* Учитывать число вхождений признака в дерево.
*Стохастические — сводят задачу выбора признаков к задаче
+
* Учитывать глубину вершины вхождения признака в дерево.
оптимизации в пространстве бинарных векторов:
+
}}
*Поиск восхождением на холм
+
 
**Генетические алгоритмы
+
{{Пример
**. . .
+
|example='''SVM-RFE'''
===Анализ методов-оберток===
+
# Обучить SVM на обучающем подмножестве
 +
# Установить веса признаков, равными модулям соответствующих коэффициентов
 +
# Отранжировать признаки согласно их весам
 +
# Выбросить некоторое число признаков с наименьшими весами
 +
# Повторять, пока не останется нужное число признаков
 +
}}
 +
 
 +
=Методы-обертки=
 +
[[File:Feature_selection_wrapper_rus.png|600px|thumb|right|Процесс работы оберточных методов]]
 +
 
 +
'''Метод-обертка''' (''wrapper method'') использует алгоритм (классификатор или регрессор) для оценки качества получаемого подмножества признаков и использует алгоритмы дискретной оптимизации для поиска оптимального подмножества признаков.
 +
 
 +
'''Оберточные методы''' (англ. ''wrapper methods'') находят подмножество искомых признаков последовательно, используя некоторый классификатор как источник оценки качества выбранных признаков, т.е. этот процесс является циклическим и продолжается до тех пор, пока не будут достигнуты заданные условия останова. Оберточные методы учитывают зависимости между признаками, что является преимуществом по сравнению с фильтрами, к тому же показывают большую точность, но вычисления занимают длительное время, и повышается риск [[переобучение|переобучения]].
 +
 
 +
Существует несколько типов оберточных методов: детерминированные, которые изменяют множество признаков по определенному правилу, а также рандомизированные, которые используют генетические алгоритмы для выбора искомого подмножества признаков.
 +
 
 +
==Классификация методов-оберток==
 +
* Детерминированные:
 +
** SFS (''sequential forward selection'')
 +
** SBE (''sequential backward elimination'')
 +
** SVM-RFE
 +
** Перестановочная полезность (''Permutation importance'')
 +
* Стохастические — сводят задачу выбора признаков к задаче оптимизации в пространстве бинарных векторов:
 +
** Поиск восхождением на холм
 +
** Генетические алгоритмы
 +
 
 +
==Анализ методов-оберток==
 
Достоинства:
 
Достоинства:
*Более высокая точность, чем у фильтров
+
* Более высокая точность, чем у фильтров
*Используют отношения между признаками
+
* Используют отношения между признаками
*Оптимизируют качество предсказательной модели в явном виде
+
* Оптимизируют качество предсказательной модели в явном виде
 
Недостатки:
 
Недостатки:
*Очень долго работают
+
* Очень долго работают
*Могут переобучиться при неправильной работе с разбиением набора данных
+
* Могут переобучиться при неправильной работе с разбиением набора данных
==Фильтры==
+
 
Фильтры (filter methods) оценивают качество отдельных признаков или
+
=Фильтры=
подмножеств признаков и удаляют худшие
+
 
 +
[[Файл:ТАблица_5.jpg|600px|thumb|right|Процесс работы фильтрующих методов]]
 +
 
 +
'''Фильтры''' (англ. ''filter methods'') измеряют релевантность признаков на основе функции $\mu$, и затем решают по правилу $\kappa$, какие признаки оставить в результирующем множестве.
 +
 
 +
Фильтры могут быть:
 +
* Одномерные (англ. ''univariate'') {{---}} функция $\mu$ определяет релевантность одного признака по отношению к выходным меткам. В таком случае обычно измеряют «качество» каждого признака и удаляют худшие. Одномерные метрики делятся на 3 части:
 +
** Сравнивают два категориальных признака
 +
** Сравнивают категориальный и числовой признаки
 +
** Сравнивают два числовых признака
 +
* Многомерные (англ. ''multivariate'') {{---}} функция $\mu$ определяет релевантность некоторого подмножества исходного множества признаков относительно выходных меток.
 +
 
 +
Преимуществом группы фильтров является простота вычисления релевантности признаков в наборе данных, но недостатком в таком подходе является игнорирование возможных зависимостей между признаками.
 +
 
 +
Фильтры (''filter methods'') оценивают качество отдельных признаков или подмножеств признаков и удаляют худшие.
  
 
Две компоненты:
 
Две компоненты:
*мера значимости признаков μ
+
* мера значимости признаков $\mu$
*правило обрезки κ определяет, какие признаки удалить на основе μ
+
* правило обрезки κ определяет, какие признаки удалить на основе $\mu$
===Схема фильтрующих методов===
+
 
[[Файл:ТАблица_5.jpg]]
+
==Классификация фильтрующих методов==
===Классификация фильтрующих методов===
+
* Одномерные (''univariate''):
*Одномерные (univariate):
+
** Евклидово расстояние
**Евклидово расстояние
+
** Коэффициент корреляции (Пирсона или Спирмена)
**Коэффициент корреляции (Пирсона или Спирмена)
+
** Попарные расстояния (внутренние или внешние)
**Попарные расстояния (внутренние или внешние)
+
** Условная дисперсия
**Условная дисперсия
+
** Прирост информации (IG)
**Прирост информации (IG)
+
** Индекс Джини
**Индекс Джини
+
** $\chi^2$
**χ2
+
* Многомерные (''multivariate''):
*Многомерные (multivariate):
+
** Выбор признаков на основе корреляций (CFS)
**Выбор признаков на основе корреляций (CFS)
+
** Фильтр марковского одеяла (MBF)
**Фильтр марковского одеяла (MBF)
+
 
===Корреляция===
+
'''Коэффициент корреляции Пирсона''' <br>
Коэффициент корреляции Пирсона
+
  '''Замечание'''
[[Файл:Таблица_6.jpg]]
+
  Важно помнить, что мы смотрим не на корреляцию, а на модуль корреляции.
Коэффициент корреляции Спирмана
+
<tex>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]</tex>
#Отсортировать объекты двумя способами (по каждому из признаков).
+
 
#Найти ранги объектов для каждой сортировки.
+
'''Коэффициент корреляции Спирмана'''
#Вычислить корреляцию Пирсона между векторами рангов.
+
# Отсортировать объекты двумя способами (по каждому из признаков).
===Правило обрезки κ===
+
# Найти ранги объектов для каждой сортировки.
*Число признаков
+
# Вычислить корреляцию Пирсона между векторами рангов.
*Порог значимости признаков
+
 
*Интегральный порог значимости признаков
+
'''Information gain'''<ref>[https://en.wikipedia.org/wiki/Information_gain_in_decision_trees Определение information gain]</ref>: <br> $IG(T, C)=\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))}$
*Метод сломанной трости
+
 
*Метод локтя
+
==Правило подрезки $k$==
===Анализ одномерных фильтров===
+
* Число признаков
Преимущества:
+
* Порог значимости признаков
*Исключительно быстро работают
+
* Интегральный порог значимости признаков
*Позволяют оценивать значимость каждого признака
+
* Метод сломанной трости
Недостатки:
+
* Метод локтя
*Порог значимости признаков
+
 
*Игнорируют отношения между признаками и то, что реально использует
+
==Анализ одномерных фильтров==
предсказательная модель
+
'''Преимущества:'''
===Анализ многомерных фильтров===
+
* Исключительно быстро работают
Преимущества:
+
* Позволяют оценивать значимость каждого признака
*Работают достаточно быстро
+
'''Недостатки:'''
*Учитывают отношения между признаками
+
* Порог значимости признаков
Недостатки:
+
* Игнорируют отношения между признаками и то, что реально использует предсказательная модель
*Работают существенно дольше фильтров
+
 
*Не учитывают то, что реально использует предсказательная модель
+
==Анализ многомерных фильтров==
==Гибриды и ансамбли==
+
'''Преимущества:'''
 +
* Работают достаточно быстро
 +
* Учитывают отношения между признаками
 +
'''Недостатки:'''
 +
* Работают существенно дольше фильтров
 +
* Не учитывают то, что реально использует предсказательная модель
 +
 
 +
=Гибриды и ансамбли=
 +
 
 +
[[Файл:Таблица_7.jpg|600px|thumb|right|Схема процесса работы гибридного подхода]]
 +
 
 +
==Гибридный подход==
 +
 
 +
'''Гибридные методы''' (англ. ''hybrid methods'') комбинируют несколько разных методов выбора признаков, например, некоторое множество фильтров, а потом запускают оберточный или встроенный метод. Таким образом, гибридные методы сочетают в себе преимущества сразу нескольких методов, и на практике повышают эффективность выбора признаков.
  
===Гибридный подход===
 
 
Будем комбинировать подходы, чтобы использовать их сильные стороны
 
Будем комбинировать подходы, чтобы использовать их сильные стороны
 
Самый частый вариант:
 
Самый частый вариант:
*сначала применим фильтр (или набор фильтров), отсеяв лишние
+
* сначала применим фильтр (или набор фильтров), отсеяв лишние признаки
признаки
+
* затем применим метод-обертку или встроенный метод
*затем применим метод-обертку или встроенный метод
+
 
===Схема гибридного подхода===
+
==Ансамблирование в выборе признаков==
[[Файл:Таблица_7.jpg]]
+
[[Файл:ТАблица_8.jpg|600px|thumb|right|Ансамблирование в выборе признаков]]
===Ансамблирование в выборе признаков===
+
 
Подход к ансамблированию состоит в построении ансамбля алгоритмов выбора
+
'''Ансамблевые методы''' применяются больше для наборов данных с очень большим числом признаков. В данном подходе для начального множества признаков создается несколько подмножеств признаков, и эти группы каким-то образом объединяются, чтобы получить набор самых релевантных признаков. Это довольно гибкая группа методов, т.к. для нее можно применять различные способы выбора признаков и объединения их подмножеств.
признаков
+
 
[[Файл:ТАблица_8.jpg]]
+
Подход к ансамблированию состоит в построении ансамбля алгоритмов выбора признаков
===Ансамбль на уровне моделей===
+
* Строим ансамбль предсказательных моделей
Строим ансамбль предсказательных моделей
+
* Объединяем ранжирования
[[Файл:Таблица_9.jpg]]
+
* Объединяем меры значимости
===Ансамбль на уровне ранжирований===
+
 
Объединяем ранжирования
+
[[Файл:Таблица_9.jpg|none|600px|thumb|Ансамбль на уровне моделей]]
[[Файл:Таблица_10.jpg]]
+
[[Файл:Таблица_10.jpg|none|600px|thumb|Ансамбль на уровне ранжирований]]
===Ансамбль на уровне мер значимости===
+
[[Файл:Таблица_11.jpg|none|600px|thumb|Ансамбль на уровне мер значимости]]
Объединяем меры значимости
+
 
[[Файл:Таблица_11.jpg]]
+
==Анализ гибридных и ансамблирующих методов==
===Анализ гибридных и ансамблирующих методов===
 
 
Преимущества:
 
Преимущества:
*Чаще всего лучше по времени и по качеству
+
* Чаще всего лучше по времени и по качеству
 
Недостатки:
 
Недостатки:
*Иногда теряется интерпретируемость
+
* Иногда теряется интерпретируемость
*Иногда требуется заботиться о проблеме переобучения
+
* Иногда требуется заботиться о проблеме переобучения
 +
 
 +
=Примечания=
 +
<references/>

Текущая версия на 18:54, 29 июня 2022

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


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

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

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

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

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

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

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

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

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

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

Недостатки:

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

Фильтры

Процесс работы фильтрующих методов

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

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

  • Одномерные (англ. univariate) — функция $\mu$ определяет релевантность одного признака по отношению к выходным меткам. В таком случае обычно измеряют «качество» каждого признака и удаляют худшие. Одномерные метрики делятся на 3 части:
    • Сравнивают два категориальных признака
    • Сравнивают категориальный и числовой признаки
    • Сравнивают два числовых признака
  • Многомерные (англ. 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[1]:
$IG(T, C)=\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))}$

Правило подрезки $k$

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

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

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

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

Недостатки:

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

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

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

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

Недостатки:

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

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

Схема процесса работы гибридного подхода

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

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

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

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

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

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

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

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

  • Строим ансамбль предсказательных моделей
  • Объединяем ранжирования
  • Объединяем меры значимости
Ансамбль на уровне моделей
Ансамбль на уровне ранжирований
Ансамбль на уровне мер значимости

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

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

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

Недостатки:

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

Примечания