WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

Отбор признаков, известный также как отбор переменных, отбор атрибутов или отбор поднабора переменных, это процесс отбора подмножества значимых признаков (переменных зависимых и независимых) для использования в построении модели. Техники отбора признаков используются по четырём причинам:

• упрощение моделей для того, чтобы сделать их проще для интерпретации исследователями/пользователями^[1],
• более короткое время тренировки,
• чтобы избежать проклятие размерности,
• улучшенное обобщение путём сокращения переобучения^[2] (формально, уменьшение дисперсии^[1]).

Центральный посыл использования техники отбора признаков — что данные содержат некоторые признаки, которые либо излишни, либо не значимы, а потому могут быть удалены без существенной потери информации^[2]. Излишни и не значимы являются двумя различными понятиями, поскольку один значимый признак может быть излишним при присутствии другого существенного признака, с которым он сильно коррелирует ^[3].

Техники отбора признаков следует отличать от выделения признаков. Выделение признаков создаёт новые признаки как функции от оригинальных признаков, в то время как отбор признаков возвращает подмножество признаков. Техники отбора признаков часто используются в областях, где имеется много признаков и выборки сравнительно малы (мало точек данных). Классическими местами применения отбора признаков являются анализ рукописных текстов и ДНК-микрочипы, где имеется много тысяч признаков и от десятков до сотен экземпляров выборки.

Введение

Алгоритм отбора признаков можно рассматривать как комбинацию техник поиска для представления нового поднабора признаков вместе с вычислением меры, которая отражает различие подмножеств признаков. Простейшим алгоритмом является проверка каждого возможного подмножества признаков и нахождения того, который минимизирует величину ошибки. Это исчерпывающий поиск по пространству и он вычислительно труден для наборов признаков, не являющихся очень маленькими. Выбор метрики сильно влияет на алгоритм и они различны для трёх основных категорий алгоритмов отбора признаков: обёртки, фильтры и методы вложения^[3].

• Методы обёртывания используют модель априорной оценки результата для оценки поднаборов признаков. Каждый новый поднабор используется для тренировки модели, которая проверяется на контрольной выборке. На этой контрольной выборке считается число ошибок (показатель ошибок модели), которое даёт оценку для данного подмножества. Так как методы обёртывания тренируют модель для каждого поднабора, они вычислительно очень затратны, но дают, как правило, лучший набор признаков для конкретного типа модели.
• Методы фильтров использует косвенный показатель вместо показателя ошибки для оценки поднабора признаков. Этот показатель выбирается так, чтобы его можно было легко вычислить при сохранении показателя полезности набора признаков. Обычно применяемые меры — взаимная информация^[3], поточечная взаимная информация^[en][4], коэффициент корреляции смешанных моментов Пирсона, алгоритм, основанный на Relief^[en][5] и расстояние между классами/внутри класса или результат критериев значимости для каждой комбинации класс/признак^[4][6]. Фильтры обычно вычислительно менее интенсивны, чем обёртки, но они дают наборы признаков, которые не настроены на специфичный тип прогнозирующей модели^[7]. Этот недостаток настройки означает, что набор признаков, полученный из фильтра более общий, чем набор, полученный из обёртки, что приводит к меньшей способности предсказания, чем у обёртки. Однако набор признаков не содержит при этом предположений о прогнозирующей модели, а потому более пригоден для обнаружения связей между признаками. Многие фильтры обеспечивают ранжирование признаков, не давая явного лучшего подмножества признаков, а точка отсечения в ранжировании выбирается с помощью перекрёстной проверки. Методы фильтров используются также как предварительные шаги обработки для методов обёртывания, что позволяет применять обёртывание для больших задач. Другим популярным подходом является алгоритм рекурсивного исключения признаков, обычно используемый вместе с методом опорных векторов для многократного построения модели и удаления признаков с малыми весами.
• Методы вложения являются обобщающей группой техник, которые осуществляют отбор признаков как часть процесса построения модели. Экземпляром такого подхода является метод LASSO^[en] (англ. Least absolute shrinkage and selection operator = метод оценивания коэффициентов линейной регрессионной модели) для построения линейной модели, который штрафует коэффициент регрессии на штраф L1, сокращая многие из них до нуля. Любые признаки, которые имеют ненулевые коэффициенты регрессии «выбираются» алгоритмом LASSO. Улучшения алгоритма LASSO включают алгоритм Bolasso, который формирует выборку путём бутстрепа^[8], регуляризацию эластичной сети^[en], которая комбинирует штраф L1 алгоритма LASSO со штрафом L2 гребневой регрессии, и метод FeaLect, который оценивает все признаки на основе комбинаторного анализа коэффициентов регрессии^[9]. Эти подходы по вычислительной сложности оказываются где-то между фильтрами и обёртками.

В традиционной статистике наиболее популярной формой отбора признаков является ступенчатая регрессия^[en], которая является техникой оборачивания. Это жадный алгоритм, который добавляет лучший признак (или удаляет худший) на каждом шаге алгоритма. Главная проблема — когда остановить алгоритм. При обучении машин это обычно делается путём перекрёстной проверки. В статистике некоторые критерии оптимизированы. Это ведёт к наследованию проблемы вложения. Исследовались и более устойчивые методы, такие как метод ветвей и границ и кусочно-линейная сеть.

Выбор поднабора

Выбор поднабора оценивает поднабор признаков как группу стабильности. Алгоритмы выбора поднабора можно разбить на Обёртки, Фильтры и Вложения. Обёртки используют алгоритм поиска для поиска по пространству возможных признаков и оценивают каждый поднабор путём прогона модели на поднаборе. Обёртки может быть вычислительно затратна и имеет риск переподгонки (переобучения) модели. Фильтры похожи на Обёртки по подходу к поиску, но вместо оценки модели оценивается более простой фильтр. Техники вложения встраиваются в модель и специфичны для неё.

Многие популярные подходы используют жадный поиск восхождением к вершине, который итеративно оценивает поднабор признаков как кандидата, затем модифицирует поднабор и оценивает, насколько новый поднабор лучше старого. Оценка поднабора требует использования оценочной метрики^[en], которая ранжирует поднаборы признаков. Исчерпывающий поиск, как правило, невыполним, так что разработчик (или оператор) определяет точку останова, поднабор признаков с наибольшей достигнутой оценкой, обнаруженный к этому моменту выбирается как удовлетворительный поднабор признаков. Критерий остановки зависит т алгоритма. Возможные критерии: оценка поднабора превышает порог, программа превысила максимальное допустимое время, и так далее.

Альтернативные техники на основе поиска базируются на целевом поиске наилучшей проекции^[en], который находит проекции низкой размерности данных с высокой оценкой — выбираются признаки, которые имеют наибольшие проекции в пространстве низкой размерности.

Подходы для поиска:

• Исчерпывающий поиск
• Поиск по первому наилучшему совпадению
• Имитации отжига
• Генетический алгоритм^[10]
• жадный прямой отбор^[11][12][13]
• Жадное обратное исключение
• Метод роя частиц^[14]
• Целевой поиск наилучшей проекции^[en]
• Распределенный поиск^[15]
• Поиск с чередующимися окрестностями^[en][16][17]

Две популярные метрики фильтров для задач классификации — корреляция и взаимная информация, хотя ни одна из них не является истинной метрикой^[en] или «мерой расстояния» в математическом смысле, поскольку для них не выполняется неравенство треугольника, а потому они не представляют действительного «расстояния» – их следует, скорее, понимать как «оценку». Эти оценки вычисляются между признаками-кандидатами (или наборами признаков) и желаемой категорией. Есть, однако, истинные метрики, которые являются простыми функциями от взаимной информации^[18].

Другие возможные метрики фильтров:

• Отделимость классов
  • Вероятность ошибки
  • Межклассовое расстояние
  • Вероятностное расстояние
  • Энтропия
• Выбор признаков на основе непротиворечивости
• Выбор признаков на основе корреляции

Критерий оптимальности

Выбор критерия оптимальности сложен, так как имеется несколько целей в задаче отбора признаков. Многие критерии включают меру точности со штрафованием числом выбранных признаков (например, байесовский информационный критерий). Наиболее старыми являются статистика C_p Мэллоуса^[en] и информационный критерий Акаике (англ. Akaike information criterion, AIC). Они добавляют переменные, если t-статистика превосходит ${\displaystyle {\sqrt {2}}}$ .

Другими критериями являются байесовский информационный критерий (БИК, англ. Bayesian information criterion, BIC), который использует ${\displaystyle {\sqrt {\log {n}}}}$ , минимальная длина описания (англ. minimum description length, MDL), который асимптотически использует ${\displaystyle {\sqrt {\log {n}}}}$ , Бонферрони / RIC, который использует ${\displaystyle {\sqrt {2\log {p}}}}$ , отбор признаков с максимальной зависимостью, и набор новых критериев, которые продиктованы идеей уровня ложноположительных результатов^[en] (англ. false discovery rate, FDR) и которые используют нечто, близкое к ${\displaystyle {\sqrt {2\log {\frac {p}{q}}}}}$ . Критерий максимума энтропийной скорости может также быть использован для выбора наиболее значимого поднабора признаков^[19].

Структурное обучение

Фильтр отбора признаков является специальным случаем более общей парадигмы с названием «структурное обучение». Выбор признаков находит значимый набор признаков для конкретной целевой переменной, в то время как структурное обучение находит связи между переменными, обычно выражая эти связи в виде графа. Наиболее распространённые алгоритмы структурного обучения предполагают, что данные генерируются байесовской сетью, так что структура является ориентированной графовой моделью. Оптимальное решение задачи фильтра отбора признаков является марковским ограждением целевого узла и в байесовской сети имеется единственное марковское ограждение для каждого узла^[20].

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

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

1. Вычисляется взаимная информация как оценка между всеми признаками (${\displaystyle f_{i}\in F}$ ) и целевым классом ( ${\displaystyle c}$ )
2. Выбирается признак с наибольшей оценкой (например, ${\displaystyle argmax_{f_{i}\in F}(I(f_{i},c))}$ ) и добавляется в набор отобранных признаков (${\displaystyle S}$ )
3. Вычисляется оценка, которая может быть получена из взаимной информации
4. Выбираем признак с наибольшей оценкой и добавляем в набор отобранных признаков (например, ${\displaystyle argmax_{f_{i}\in F}(I_{derived}(f_{i},c))}$ )
5. Повторяем шаги 3. и 4. Пока не наберём определённое число признаков (например, ${\displaystyle |S|=l}$ )

Наиболее простой подход использует взаимную информацию в качестве «производной» оценки^[21].

Однако, есть различные походы, которые пытаются уменьшить избыточность между признаками.

Выбор признаков на основе критерия независимости Lasso Гильберта — Шмидта

Для данных высокой размерности и небольших данных (например, размерность > ${\displaystyle 10^{5}}$ и размер выборки < ${\displaystyle 10^{3}}$ ), полезным является критерий независимости Lasso Гильберта — Шмидта (HSIC Lasso)^[27]. Задача оптимизации HSIC Lasso задаётся как

${\displaystyle \mathrm {HSIC_{Lasso}} :\min _{\mathbf {x} }{\frac {1}{2}}\sum _{k,l=1}^{n}x_{k}x_{l}{\mbox{HSIC}}(f_{k},f_{l})-\sum _{k=1}^{n}x_{k}{\mbox{HSIC}}(f_{k},c)+\lambda \|\mathbf {x} \|_{1},\quad \ x_{1},\ldots ,x_{n}\geq 0,}$

где ${\displaystyle {\mbox{HSIC}}(f_{k},c)={\mbox{tr}}({\bar {\mathbf {K} }}^{(k)}{\bar {\mathbf {L} }})}$ является ядерной мерой независимости, называемой (эмпирическим) критерием независимости Гильберта — Шмидта (англ. Hilbert-Schmidt independence criterion, HSIC), ${\displaystyle {\mbox{tr}}(\cdot )}$ обозначает след, ${\displaystyle \lambda }$ является параметром регуляризации, ${\displaystyle {\bar {\mathbf {K} }}^{(k)}=\mathbf {\Gamma } \mathbf {K} ^{(k)}\mathbf {\Gamma } }$ и ${\displaystyle {\bar {\mathbf {L} }}=\mathbf {\Gamma } \mathbf {L} \mathbf {\Gamma } }$ являются входными и выходными центрироваными матрицами Грама, ${\displaystyle K_{i,j}^{(k)}=K(u_{k,i},u_{k,j})}$ и ${\displaystyle L_{i,j}=L(c_{i},c_{j})}$ являются матрицами Грама, ${\displaystyle K(u,u')}$ и ${\displaystyle L(c,c')}$ являются ядерными функциями, ${\displaystyle \mathbf {\Gamma } =\mathbf {E} _{m}-{\frac {1}{m}}\mathbf {1} _{m}\mathbf {1} _{m}^{T}}$ является центрированной матрицей, ${\displaystyle \mathbf {E} _{m}}$ является m-мерной единичной матрицей (m: число элемнтов выборки), ${\displaystyle \mathbf {1} _{m}}$ является m-мерным вектором со всеми единицами, а ${\displaystyle \|\cdot \|_{1}}$ является ${\displaystyle \ell _{1}}$ -нормой. HSIC всегда принимает неотрицательное значение и равно нулю тогда и только тогда, когда две случайные переменные статистически независимы при применении универсального производящего ядра, такого как гауссово ядро.

HSIC Lasso можно записать как

${\displaystyle \mathrm {HSIC_{Lasso}} :\min _{\mathbf {x} }{\frac {1}{2}}\left\|{\bar {\mathbf {L} }}-\sum _{k=1}^{n}x_{k}{\bar {\mathbf {K} }}^{(k)}\right\|_{F}^{2}+\lambda \|\mathbf {x} \|_{1},\quad \ x_{1},\ldots ,x_{n}\geq 0,}$

где ${\displaystyle \|\cdot \|_{F}}$ является нормой Фробениуса. Задача оптимизации является задачей Lasso, а потому она может быть эффективно решена с помощью современных методов решения Lasso, таких как двойственный метод обобщённого Лагранжиана^[en].

Отбор признаков на основе корреляции

Отбор признаков на основе меры корреляции (англ. Correlation Feature Selection, CFS) оценивает подмножества признаков на базе следующей гипотезы: «Хорошие поднаборы признаков содержат признаки, сильно коррелирующие с классификацией, но не коррелирующие друг с другом»^[28][29]. Следующе равенство даёт оценку поднабора признаков S, состоящего из k признаков:

${\displaystyle \mathrm {Merit} _{S_{k}}={\frac {k{\overline {r_{cf}}}}{\sqrt {k+k(k-1){\overline {r_{ff}}}}}}.}$

Здесь ${\displaystyle {\overline {r_{cf}}}}$ является средним значением всех корреляций признак-классификация, а ${\displaystyle {\overline {r_{ff}}}}$ является средним всех корреляций признак-признак. Критерий CFS определяется следующим образом:

${\displaystyle \mathrm {CFS} =\max _{S_{k}}\left[{\frac {r_{cf_{1}}+r_{cf_{2}}+\cdots +r_{cf_{k}}}{\sqrt {k+2(r_{f_{1}f_{2}}+\cdots +r_{f_{i}f_{j}}+\cdots +r_{f_{k}f_{1}})}}}\right].}$

Переменные ${\displaystyle r_{cf_{i}}}$ и ${\displaystyle r_{f_{i}f_{j}}}$ являются корреляциями, но не обязательно коэффициентами корреляции Пирсона или ρ Спирмена^[en]. Диссертация Марка Холла не использует ни одну из них, но использует три различных меры связанности, минимальную длину описания (англ. minimum description length, MDL), симметричную неопределённость и Relief^[en].

Пусть x_i будет индикаторной функцией вхождения в множество для признака f_i. Тогда формула выше может быть переписана как задача оптимизации:

${\displaystyle \mathrm {CFS} =\max _{x\in \{0,1\}^{n}}\left[{\frac {(\sum _{i=1}^{n}a_{i}x_{i})^{2}}{\sum _{i=1}^{n}x_{i}+\sum _{i\neq j}2b_{ij}x_{i}x_{j}}}\right].}$

Комбинаторные задачи выше являются, фактически, смешанными 0–1 задачами линйного программирования, которые могут быть решены с помощью алгоритма ветвей и границ^[30].

Регуляризованные деревья

Было показано, что признаки из дерева решений или ансамбли деревьев избыточны. Недавний метод с названием «регуляризованное дерево»^[31] может быть использован для выбора поднабора признаков. Регуляризованные деревья штрафуются с помощью переменной, подобной переменным, выбранным на предыдущих узлах дерева для расщепления текущего узла. Для регуляризованных деревьев нужно строить только одну модель (иди один ансамбль деревьев), а потому вычислительно алгорим эффективен.

Регуляризованные деревья естественным образом работают с численными и категорийными признаками, взаимодействиями и нелинейностями. Они инвариантны относительно масштаба атрибутов (единиц) и нечувствительны к выбросам, а потому требуют малой предварительной обработки данных, такой как нормализация^[en]. Регуляризованный случайный лес (англ. Regularized random forest, RRF)^[32] является одним из типов регуляризованных деревьев. Управляемый RRF является улучшенным методом RRF, который управляется оценкой важности из обычного случайного леса.

Обзор методов метаэвристики

Метаалгоритм (или метаэвристика) является общим описанием алгоритма, предназначенного для решения трудных (типично, NP-трудных задач) задач оптимизации для которых не имеется никаких методов решения. Обычно метаалгоритм является стохастическим алгоритмом, стремящимся достичь глобального оптимума. Есть много метаалгоритмов от простого локального поиска до сложного алгоритма глобального поиска.

Основные принципы

Методы отбора признаков обычно представлены тремя классами по тому, как они комбинируют алгоритмы выбора и построения модели.

Метод фильтров

Методы фильтров выбирают переменные независимо от модели. Они базируются только на общих признаках, таких как корреляция переменной с предсказанием. Методы фильтров подавляют наименее интересные переменные. Другие переменные будут частью классификации или модели регрессии, использованной для классификации или предсказания. Эти методы очень эффективны по времени вычисления и устойчивы к переобучению^[33].

Однако, методы фильтров стремятся к выбору избыточных переменных, поскольку они не учитывают связь между переменными. По этой причине эти методы главным образом используются как методы предварительной обработки.

Метод обёртывания

Методы обёртывания оценивают поднаборы переменных и позволяют, в отличие от подходов фильтрации, обнаружить возможную взаимосвязь между переменными^[34]. Два главных недостатка этих методов:

• Увеличивается риск переобучения, когда число наблюдений недостаточно.
• Существенное время вычисления, когда число переменных велико.

Метод вложения

Методы вложения были предложены как попытка комбинации преимуществ двух предыдущих методов. Обучающий алгоритм имеет преимущество собственного процесса выбора переменной и осуществляет выбор признаков и классификацию одновременно.

Выбор признаков, вложенных в алгоритмы обучения

Некоторые обучающие алгоритмы осуществляют отбор признаков как часть алгоритма:

• Техники ${\displaystyle l_{1}}$ -регуляризации, такие как разреженная регрессия, LASSO, и ${\displaystyle l_{1}}$ -SVM
• Регуляризованные деревья^[31], например, регуляризованный случайный лес, реализованный в пакете RRF^[32]
• Дерево решений^[56]
• Меметический алгоритм^[en]
• Случайный мультиномиальный логит (англ. Random multinomial logit, RMNL)
• Автокодирующая сеть с узким уровнем
• Выделение субмодулярных^[en] признаков^[57][58][59]
• Выбор признаков на основе локального обучения^[60]. По сравнению с традиционными методами данный метод не использует эвристического поиска, может легко справляться с задачами с многими классами, и работает как на линейных, так и нелинейных задачах. Метод также поддержан с теоретической стороны. Численные эксперименты показали, что метод может достичь близкое к оптимальному решение даже в случае, когда данные содержат более 1M незначимых признаков.

См. также

• Кластерный анализ
• Data mining
• Снижение размерности
• Выделение признаков
• Оптимизация гиперпараметров
• Алгоритм Relief^[en]

Примечания

Литература

Литература для дальнейшего чтения

• Feature Selection for Classification: A Review (Survey, 2014)
• Feature Selection for Clustering: A Review (Survey, 2013)
• Tutorial Outlining Feature Selection Algorithms, Arizona State University
• JMLR Special Issue on Variable and Feature Selection
• Feature Selection for Knowledge Discovery and Data Mining (Book)
• An Introduction to Variable and Feature Selection (Survey)
• Toward integrating feature selection algorithms for classification and clustering (Survey)
• Efficient Feature Subset Selection and Subset Size Optimization (Survey, 2010)
• Searching for Interacting Features
• Feature Subset Selection Bias for Classification Learning

Ссылки

• Feature Selection Package, Arizona State University (Matlab Code)
• NIPS challenge 2003 (see also NIPS)
• Naive Bayes implementation with feature selection in Visual Basic (includes executable and source code)
• Minimum-redundancy-maximum-relevance (mRMR) feature selection program
• FEAST (Open source Feature Selection algorithms in C and MATLAB)

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.