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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Методы-обертки)
(Фильтры)
 
(не показаны 42 промежуточные версии этого же участника)
Строка 1: Строка 1:
= Выбор признаков (Feature selection) =
+
'''Выбор признаков (''Feature selection'')'''
  
== Уменьшение размерности ==
+
= Уменьшение размерности =
 
 
Под '''уменьшением размерности''' (англ. ''dimensionality reduction'') в машинном обучении подразумевается уменьшение числа признаков набора данных. Наличие в нем признаков избыточных, неинформативных или слабо информативных может понизить эффективность модели, а после такого преобразования она упрощается, и соответственно уменьшается размер набора данных в памяти и ускоряется работа алгоритмов ML на нем. Уменьшение размерности может быть осуществлено методами выбора признаков (англ. ''feature selection'') или выделения признаков (англ. ''feature extraction'').
 
  
 +
Под '''уменьшением размерности''' (англ. ''dimensionality reduction'') в машинном обучении подразумевается уменьшение числа признаков набора данных. Наличие в нем признаков избыточных, неинформативных или слабо информативных может понизить эффективность модели, а после такого преобразования она упрощается, и, соответственно, уменьшается размер набора данных в памяти и ускоряется работа алгоритмов ML на нем. Уменьшение размерности может быть осуществлено методами выбора признаков (англ. ''feature selection'') или выделения признаков (англ. ''feature extraction'').
  
 
{{Определение
 
{{Определение
Строка 12: Строка 11:
 
}}
 
}}
  
===Зачем нужно===
+
==Зачем нужно==
 
* Ускорение обучения и обработки
 
* Ускорение обучения и обработки
 
* Борьба с шумом и мультиколлинеарностью
 
* Борьба с шумом и мультиколлинеарностью
Строка 25: Строка 24:
 
}}
 
}}
  
===Когда применяется===
+
==Когда применяется==
* Меньше памяти для хранения
+
 
* Уменьшение времени обработки
+
* Нужно использовать меньше памяти для хранения данных
* Увеличение качества обработки
+
* Нужно уменьшить время обработки
* Понимание природы признаков
+
* Нужно увеличить качество обработки
 +
* Нужно понять природу признаков
  
 
[[Файл:Таблица_1.jpg|600px|thumb|right|Методы уменьшения размерности]]
 
[[Файл:Таблица_1.jpg|600px|thumb|right|Методы уменьшения размерности]]
  
===Два основных подхода уменьшения размерности===
+
'''Замечание:'''<br>
 +
Уменьшение размерности — шаг в предобработке данных
 +
 
 +
==Два основных подхода уменьшения размерности==
  
 
'''Выбор признаков''' (''feature selection'') включает методы, для которых $G ⊂ F$. Они:
 
'''Выбор признаков''' (''feature selection'') включает методы, для которых $G ⊂ F$. Они:
* быстро работают;
+
* Быстро работают;
* не могут «выдумывать» сложных признаков.
+
* Не могут «выдумывать» сложных признаков.
  
'''Извлечение признаков''' (''feature extraction'') включает все другие
+
'''Извлечение признаков''' (''feature extraction'') включает все другие методы (в том числе даже те, у которых $k > n$).
методы (в том числе даже те, у которых $k > n$).
+
* В целом, дольше работают;
* в целом, дольше работают;
+
* Могут извлекать сложные признаки.
* могут извлекать сложные признаки.
 
  
===Цели извлечения и выбора признаков===
+
==Цели извлечения и выбора признаков==
 
* Уменьшение числа ресурсов, требуемых для обработки больших наборов данных
 
* Уменьшение числа ресурсов, требуемых для обработки больших наборов данных
 
* Поиск новых признаков
 
* Поиск новых признаков
 
* Эти признаки могут быть линейными и нелинейными относительно исходных
 
* Эти признаки могут быть линейными и нелинейными относительно исходных
  
====Цели выбора признаков:====
+
===Цели выбора признаков:===
 
* Уменьшение переобучения и улучшение качества предсказания
 
* Уменьшение переобучения и улучшение качества предсказания
 
* Улучшение понимания моделей
 
* Улучшение понимания моделей
===Типы ненужных признаков===
+
 
 +
==Типы ненужных признаков==
 
Существуют также два типа признаков, которые не являются необходимыми:
 
Существуют также два типа признаков, которые не являются необходимыми:
 
* Избыточные (''redundant'') признаки не привносят дополнительной информации относительно существующих
 
* Избыточные (''redundant'') признаки не привносят дополнительной информации относительно существующих
 
* Нерелевантные (''irrelevant'') признаки просто неинформативны
 
* Нерелевантные (''irrelevant'') признаки просто неинформативны
  
==Встроенные методы==
+
=Встроенные методы=
[[Файл:Таблица_2.jpg|600px|thumb|right|Схема встроенного метода]]
 
===Классификация методов выбора признаков===
 
*Встроенные методы (embedded)
 
*Фильтрующие методы (filter)
 
**Одномерные (univariate)
 
**Многомерные (multivariate)
 
*Методы-обертки (wrapper)
 
**Детерминированные (deterministic)
 
**Стохастические (stochastic)
 
*Гибридные и ансамблирующие методы
 
===Встроенные методы===
 
[[File:Feature_selection_embedded_rus.png|450px|thumb|right|Процесс работы встроенных методов]]
 
Группа '''встроенных методов''' (англ. ''embedded methods'') очень похожа на оберточные методы, но для выбора признаков используется непосредственно структуру некоторого классификатора. В оберточных методах классификатор служит только для оценки работы на данном множестве признаков, тогда как встроенные методы используют какую-то информацию о признаках, которую классификаторы присваивают во время обучения.
 
  
Одним из примеров встроенного метода является реализация на [[Дерево решений и случайный лес| случайном лесе]]: каждому дереву на вход подаются случайное подмножество данных из датасета с каким-то случайным набор признаков, в процессе обучения каждое из деревьев решений производит "голосование" за релевантность его признаков, эти данные агрегируются, и на выходе получаются значения важности каждого признака набора данных. Дальнейший выбор нужных нам признаков уже зависит от выбранного критерия отбора.
+
{{Определение
 +
|definition=
 +
Встроенные методы (''embedded methods'') — это методы выбора
 +
признаков, при которых этот выбор осуществляется в процессе работы
 +
других алгоритмов (классификаторов и регрессоров)
 +
* Опираются на конкретный алгоритм
 +
* Специфичны для каждого алгоритма
 +
}}
 +
 
 +
[[File:Feature_selection_embedded_rus.png|600px|thumb|right|Процесс работы встроенных методов]]
 +
 
 +
Группа '''встроенных методов''' (англ. ''embedded methods'') очень похожа на оберточные методы, но для выбора признаков используется непосредственно структуру некоторого классификатора. В оберточных методах классификатор служит только для оценки работы на данном множестве признаков, тогда как встроенные методы используют какую-то информацию о признаках, которую классификаторы присваивают во время обучения.
 +
 
 +
Одним из примеров встроенного метода является реализация на [[Дерево решений и случайный лес| случайном лесе]]: каждому дереву на вход подаются случайное подмножество данных из датасета с каким-то случайным набор признаков, в процессе обучения каждое из деревьев решений производит «голосование» за релевантность его признаков, эти данные агрегируются, и на выходе получаются значения важности каждого признака набора данных. Дальнейший выбор нужных нам признаков уже зависит от выбранного критерия отбора.
  
 
Встроенные методы используют преимущества оберточных методов и являются более эффективными, при этом на отбор тратится меньше времени, уменьшается риск [[переобучение|переобучения]], но т.к. полученный набор признаков был отобран на основе знаний о классификаторе, то есть вероятность, что для другого классификатора это множество признаков уже не будет настолько же релевантным.
 
Встроенные методы используют преимущества оберточных методов и являются более эффективными, при этом на отбор тратится меньше времени, уменьшается риск [[переобучение|переобучения]], но т.к. полученный набор признаков был отобран на основе знаний о классификаторе, то есть вероятность, что для другого классификатора это множество признаков уже не будет настолько же релевантным.
  
===Пример: случайный лес===
+
==Классификация методов выбора признаков==
[[Файл:Таблица_3.jpg|300px|thumb|right|Случайный лес]]
+
* Встроенные методы (''embedded'')
*Учитывать число вхождений признака в дерево.
+
* Фильтрующие методы (''filter'')
*Учитывать глубину вершины вхождения признака в дерево.
+
** Одномерные (''univariate'')
 +
** Многомерные (''multivariate'')
 +
* Методы-обертки (''wrapper'')
 +
** Детерминированные (''deterministic'')
 +
** Стохастические (''stochastic'')
 +
* Гибридные и ансамблирующие методы
 +
 
 +
{{Пример
 +
|example='''Cлучайный лес'''
 +
[[Файл:Таблица_3.jpg|500px|thumb|right|Случайный лес]]
 +
{{main|Дерево решений и случайный лес}}
 +
* Учитывать число вхождений признака в дерево.
 +
* Учитывать глубину вершины вхождения признака в дерево.
 +
}}
 +
 
 +
{{Пример
 +
|example='''SVM-RFE'''
 +
# Обучить SVM на обучающем подмножестве
 +
# Установить веса признаков, равными модулям соответствующих коэффициентов
 +
# Отранжировать признаки согласно их весам
 +
# Выбросить некоторое число признаков с наименьшими весами
 +
# Повторять, пока не останется нужное число признаков
 +
}}
 +
 
 +
=Методы-обертки=
 +
[[File:Feature_selection_wrapper_rus.png|600px|thumb|right|Процесс работы оберточных методов]]
  
===Пример: SVM-RFE===
+
'''Метод-обертка''' (''wrapper method'') использует алгоритм (классификатор или регрессор) для оценки качества получаемого подмножества признаков и использует алгоритмы дискретной оптимизации для поиска оптимального подмножества признаков.
#Обучить SVM на обучающем подмножестве
 
#Установить веса признаков, равными модулям соответствующих коэффициентов
 
#Отранжировать признаки согласно их весам
 
#Выбросить некоторое число признаков с наименьшими весами
 
#Повторять, пока не останется нужное число признаков
 
  
==Методы-обертки==
+
'''Оберточные методы''' (англ. ''wrapper methods'') находят подмножество искомых признаков последовательно, используя некоторый классификатор как источник оценки качества выбранных признаков, т.е. этот процесс является циклическим и продолжается до тех пор, пока не будут достигнуты заданные условия останова. Оберточные методы учитывают зависимости между признаками, что является преимуществом по сравнению с фильтрами, к тому же показывают большую точность, но вычисления занимают длительное время, и повышается риск [[переобучение|переобучения]].  
[[Файл:Таблица_4.jpg|600px|thumb|right|Схема метода-обертки]]
 
Метод-обертка (wrapper method) использует алгоритм (классификатор или регрессор) для оценки качества получаемого подмножества признаков и использует алгоритмы дискретной оптимизации для поиска оптимального подмножества признаков.
 
  
===Классификация методов-оберток===
+
Существует несколько типов оберточных методов: детерминированные, которые изменяют множество признаков по определенному правилу, а также рандомизированные, которые используют генетические алгоритмы для выбора искомого подмножества признаков.
*Детерминированные:
+
 
**SFS (sequential forward selection)
+
==Классификация методов-оберток==
**SBE (sequential backward elimination)
+
* Детерминированные:
**SVM-RFE
+
** SFS (''sequential forward selection'')
**Перестановочная полезность (Permutation importance)
+
** 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|600px|thumb|right]]
+
==Классификация фильтрующих методов==
===Классификация фильтрующих методов===
+
* Одномерные (''univariate''):
*Одномерные (univariate):
+
** Евклидово расстояние
**Евклидово расстояние
+
** Коэффициент корреляции (Пирсона или Спирмена)
**Коэффициент корреляции (Пирсона или Спирмена)
+
** Попарные расстояния (внутренние или внешние)
**Попарные расстояния (внутренние или внешние)
+
** Условная дисперсия
**Условная дисперсия
+
** Прирост информации (IG)
**Прирост информации (IG)
+
** Индекс Джини
**Индекс Джини
+
** $\chi^2$
**χ2
+
* Многомерные (''multivariate''):
*Многомерные (multivariate):
+
** Выбор признаков на основе корреляций (CFS)
**Выбор признаков на основе корреляций (CFS)
+
** Фильтр марковского одеяла (MBF)
**Фильтр марковского одеяла (MBF)
+
 
===Корреляция===
+
'''Коэффициент корреляции Пирсона''' <br>
Коэффициент корреляции Пирсона
+
  '''Замечание'''
[[Файл:Таблица_6.jpg|600px|thumb|right]]
+
  Важно помнить, что мы смотрим не на корреляцию, а на модуль корреляции.
Коэффициент корреляции Спирмана
+
<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|600px|thumb|right]]
+
[[Файл:ТАблица_8.jpg|600px|thumb|right|Ансамблирование в выборе признаков]]
===Ансамблирование в выборе признаков===
+
 
Подход к ансамблированию состоит в построении ансамбля алгоритмов выбора
+
'''Ансамблевые методы''' применяются больше для наборов данных с очень большим числом признаков. В данном подходе для начального множества признаков создается несколько подмножеств признаков, и эти группы каким-то образом объединяются, чтобы получить набор самых релевантных признаков. Это довольно гибкая группа методов, т.к. для нее можно применять различные способы выбора признаков и объединения их подмножеств.
признаков
+
 
[[Файл:ТАблица_8.jpg|600px|thumb|right]]
+
Подход к ансамблированию состоит в построении ансамбля алгоритмов выбора признаков
===Ансамбль на уровне моделей===
+
* Строим ансамбль предсказательных моделей
Строим ансамбль предсказательных моделей
+
* Объединяем ранжирования
[[Файл:Таблица_9.jpg|600px|thumb|right]]
+
* Объединяем меры значимости
===Ансамбль на уровне ранжирований===
+
 
Объединяем ранжирования
+
[[Файл:Таблица_9.jpg|none|600px|thumb|Ансамбль на уровне моделей]]
[[Файл:Таблица_10.jpg|600px|thumb|right]]
+
[[Файл:Таблица_10.jpg|none|600px|thumb|Ансамбль на уровне ранжирований]]
===Ансамбль на уровне мер значимости===
+
[[Файл:Таблица_11.jpg|none|600px|thumb|Ансамбль на уровне мер значимости]]
Объединяем меры значимости
+
 
[[Файл:Таблица_11.jpg|600px|thumb|right]]
+
==Анализ гибридных и ансамблирующих методов==
===Анализ гибридных и ансамблирующих методов===
 
 
Преимущества:
 
Преимущества:
*Чаще всего лучше по времени и по качеству
+
* Чаще всего лучше по времени и по качеству
 
Недостатки:
 
Недостатки:
*Иногда теряется интерпретируемость
+
* Иногда теряется интерпретируемость
*Иногда требуется заботиться о проблеме переобучения
+
* Иногда требуется заботиться о проблеме переобучения
 +
 
 +
=Примечания=
 +
<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) комбинируют несколько разных методов выбора признаков, например, некоторое множество фильтров, а потом запускают оберточный или встроенный метод. Таким образом, гибридные методы сочетают в себе преимущества сразу нескольких методов, и на практике повышают эффективность выбора признаков.

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

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

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

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

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

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

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

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

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

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

Недостатки:

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

Примечания