Изменения

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

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

===Зачем нужно===

===Когда применяется=== * Меньше Нужно использовать меньше памяти для храненияданных* Уменьшение времени Нужно уменьшить время обработки* Увеличение качества Нужно увеличить качество обработки* Понимание природы Нужно понять природу признаков

='''Замечание:'''<br>Уменьшение размерности — шаг в предобработке данных ==Два основных подхода уменьшения размерности===

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

'''Извлечение признаков''' (''feature extraction'') включает все другиеметоды (в том числе даже те, у которых $k > n$).* в В целом, дольше работают;* могут Могут извлекать сложные признаки.

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

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

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

==Встроенные методы=====Классификация методов выбора признаков===*Встроенные методы (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'') очень похожа на оберточные методы, но для выбора признаков используется непосредственно структуру некоторого классификатора. В оберточных методах классификатор служит только для оценки работы на данном множестве признаков, тогда как встроенные методы используют какую-то информацию о признаках, которую классификаторы присваивают во время обучения. Одним из примеров встроенного метода является реализация на [[Дерево решений и случайный лес| случайном лесе]]: каждому дереву на вход подаются случайное подмножество данных из датасета с каким-то случайным набор признаков, в процессе обучения каждое из деревьев решений производит "голосование" «голосование» за релевантность его признаков, эти данные агрегируются, и на выходе получаются значения важности каждого признака набора данных. Дальнейший выбор нужных нам признаков уже зависит от выбранного критерия отбора.

==Классификация методов выбора признаков==* Встроенные методы (''embedded'')* Фильтрующие методы (''filter'')** Одномерные (''univariate'')** Многомерные (''multivariate'')* Методы-обертки (''wrapper'')** Детерминированные (''deterministic'')** Стохастические (''stochastic'')* Гибридные и ансамблирующие методы {{Пример|example='''Cлучайный лес'''[[Файл:Таблица_2Таблица_3.jpg|500px|thumb|right|Случайный лес]]{{main|Дерево решений и случайный лес}}* Учитывать число вхождений признака в дерево.* Учитывать глубину вершины вхождения признака в дерево.}} {{Пример|example='''SVM-RFE'''# Обучить SVM на обучающем подмножестве# Установить веса признаков, равными модулям соответствующих коэффициентов# Отранжировать признаки согласно их весам# Выбросить некоторое число признаков с наименьшими весами# Повторять, пока не останется нужное число признаков}} =Методы-обертки=[[File:Feature_selection_wrapper_rus.png|600px|thumb|right|Схема встроенного методаПроцесс работы оберточных методов]] '''Метод-обертка''' (''wrapper method'') использует алгоритм (классификатор или регрессор) для оценки качества получаемого подмножества признаков и использует алгоритмы дискретной оптимизации для поиска оптимального подмножества признаков.

===Пример: случайный лес===*Учитывать число вхождений признака в дерево'''Оберточные методы''' (англ.*Учитывать глубину вершины вхождения признака в дерево''wrapper methods'') находят подмножество искомых признаков последовательно, используя некоторый классификатор как источник оценки качества выбранных признаков, т.е. этот процесс является циклическим и продолжается до тех пор, пока не будут достигнуты заданные условия останова. Оберточные методы учитывают зависимости между признаками, что является преимуществом по сравнению с фильтрами, к тому же показывают большую точность, но вычисления занимают длительное время, и повышается риск [[Файл:Таблица_3.jpg|600pxпереобучение|thumb|rightпереобучения]]===Пример: SVM-RFE===#Обучить SVM на обучающем подмножестве#Установить веса признаков, равными модулям соответствующих коэффициентов#Отранжировать признаки согласно их весам#Выбросить некоторое число признаков с наименьшими весами#Повторять, пока не останется нужное число признаков.

==Методы-обертки==Метод-обертка (wrapper method) использует алгоритм(классификатор или регрессор) для оценки качества получаемогоподмножества Существует несколько типов оберточных методов: детерминированные, которые изменяют множество признаков и использует по определенному правилу, а также рандомизированные, которые используют генетические алгоритмы дискретнойоптимизации для поиска оптимального выбора искомого подмножества признаков.===Схема метода-обертки===[[Файл:Таблица_4.jpg|600px|thumb|right]]===Классификация методов-оберток===*Детерминированные:**SFS (''sequential forward selection'')**SBE (''sequential backward elimination'')**SVM-RFE**Перестановочная полезность (''Permutation importance'')*Стохастические — сводят задачу выбора признаков к задачеоптимизации в пространстве бинарных векторов:**Поиск восхождением на холм**Генетические алгоритмы**. . .===Анализ методов-оберток===

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

*Очень долго работают*Могут переобучиться при неправильной работе с разбиением набора данных =Фильтры= [[Файл:ТАблица_5.jpg|600px|thumb|right|Процесс работы фильтрующих методов]] '''Фильтры''' (англ. ''filter methods'') измеряют релевантность признаков на основе функции $\mu$, и затем решают по правилу $\kappa$, какие признаки оставить в результирующем множестве. Фильтры==могут быть:* Одномерные (англ. ''univariate'') {{---}} функция $\mu$ определяет релевантность одного признака по отношению к выходным меткам. В таком случае обычно измеряют «качество» каждого признака и удаляют худшие;* Многомерные (англ. ''multivariate'') {{---}} функция $\mu$ определяет релевантность некоторого подмножества исходного множества признаков относительно выходных меток. Преимуществом группы фильтров является простота вычисления релевантности признаков в наборе данных, но недостатком в таком подходе является игнорирование возможных зависимостей между признаками. Фильтры (''filter methods'') оценивают качество отдельных признаков илиподмножеств признаков и удаляют худшие.

*мера значимости признаков μ$\mu$*правило обрезки κ определяет, какие признаки удалить на основе μ$\mu$===Схема фильтрующих методов===[[Файл:ТАблица_5.jpg|600px|thumb|right]]===Классификация фильтрующих методов===*Одномерные (''univariate''):**Евклидово расстояние**Коэффициент корреляции (Пирсона или Спирмена)**Попарные расстояния (внутренние или внешние)**Условная дисперсия**Прирост информации (IG)**Индекс Джини**χ2$\chi^2$*Многомерные (''multivariate''):**Выбор признаков на основе корреляций (CFS)**Фильтр марковского одеяла (MBF)===Корреляция==='''Коэффициент корреляции Пирсона''' <br><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[[Файл:Таблица_6.jpg|600px|thumb|right]-1;1]</tex> '''Коэффициент корреляции Спирмана'''#Отсортировать объекты двумя способами (по каждому из признаков).#Найти ранги объектов для каждой сортировки.#Вычислить корреляцию Пирсона между векторами рангов. '''Information gain'''<ref>[https://en.wikipedia.org/wiki/Information_gain_in_decision_trees Определение information gain]</ref>: <br> $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))}$*Число признаков*Порог значимости признаков*Интегральный порог значимости признаков*Метод сломанной трости*Метод локтя===Анализ одномерных фильтров==='''Преимущества:'''*Исключительно быстро работают*Позволяют оценивать значимость каждого признака'''Недостатки:'''*Порог значимости признаков*Игнорируют отношения между признаками и то, что реально используетпредсказательная модель===Анализ многомерных фильтров==='''Преимущества:'''*Работают достаточно быстро*Учитывают отношения между признаками'''Недостатки:'''*Работают существенно дольше фильтров*Не учитывают то, что реально использует предсказательная модель==Гибриды и ансамбли==

==Примечания=Гибридный подход===Будем комбинировать подходы, чтобы использовать их сильные стороныСамый частый вариант:*сначала применим фильтр (или набор фильтров), отсеяв лишниепризнаки*затем применим метод-обертку или встроенный метод===Схема гибридного подхода===[[Файл:Таблица_7.jpg|600px|thumb|right]]===Ансамблирование в выборе признаков===Подход к ансамблированию состоит в построении ансамбля алгоритмов выборапризнаков[[Файл:ТАблица_8.jpg|600px|thumb|right]]===Ансамбль на уровне моделей===Строим ансамбль предсказательных моделей[[Файл:Таблица_9.jpg|600px|thumb|right]]===Ансамбль на уровне ранжирований===Объединяем ранжирования[[Файл:Таблица_10.jpg|600px|thumb|right]]===Ансамбль на уровне мер значимости===Объединяем меры значимости[[Файл:Таблица_11.jpg|600px|thumb|right]]===Анализ гибридных и ансамблирующих методов===Преимущества:*Чаще всего лучше по времени и по качествуНедостатки:*Иногда теряется интерпретируемость*Иногда требуется заботиться о проблеме переобучения<references/>