Отбор признаков

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

Статья написана с использованием LLM Gemini(PRO) и проверена участником ~~Danis Sabirov~~

Содержание

1 Отбор признаков (Feature Selection)
2 Литература

Отбор признаков (Feature Selection)

Отбор признаков (англ. feature selection) — процесс выбора оптимального подмножества релевантных признаков (предикторов, переменных) для построения модели машинного обучения. Отбор признаков преследует несколько фундаментальных целей: преодоление «проклятия размерности» (curse of dimensionality), устранение мультиколлинеарности, минимизация времени обучения и радикальное повышение интерпретируемости результирующих моделей при сохранении или увеличении их обобщающей способности.

1. Математическая постановка задачи

Пусть задана обучающая выборка, представленная в виде матрицы объекты-признаки $X \in \mathbf{R}^{N \times D}$ , где $N$ — количество независимых объектов (наблюдений), а $D$ — исходная размерность признакового пространства. Каждому объекту (строке матрицы) $x_i \in \mathbf{R}^D$ поставлен в соответствие истинный ответ (целевая переменная) $y_i \in \mathbf{Y}$ . Для задач регрессии $\mathbf{Y} = \mathbf{R}$ , для задач многоклассовой классификации $\mathbf{Y} = {1, \dots, K}$ . Изображение:Tecture.png Определим полное множество индексов исходных признаков как:

$\Omega = {1, \dots, D}, \quad |\Omega| = D$

Задачей отбора признаков является нахождение оптимального подмножества индексов $S \subset \Omega$ фиксированной или переменной мощности $|S| = d$ (где $d \ll D$ ), которое минимизирует функционал эмпирического риска выбранного базового алгоритма обучения $A$ на отложенной выборке:

$S^* = \arg\min_{S \subset \Omega} \frac{1}{M} \sum_{m=1}^{M} \mathcal{L}\left(A(X_{S}^{train})_{x_m}, y_m\right)$

где $X_S$ — усеченная матрица объектов размерности $N \times d$ , содержащая только столбцы с индексами из множества $S$ , $\mathcal{L}$ — функция потерь алгоритма, а $M$ — размер валидационной выборки.

Полный перебор всех возможных комбинаций требует оценки $2^D$ вариантов, что представляет собой NP-трудную задачу. В силу этого на практике применяются эвристические подходы, разделяемые на три класса: фильтрация (filters), обертывание (wrappers) и встроенные методы (embedded).

2. Методы фильтрации (Filter Methods)

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

Порог дисперсии (Variance Threshold): Устраняет константные и квазиконстантные признаки, не несущие дискриминативной информации. Признак $j$ удаляется, если его выборочная дисперсия ниже заданного порога $\tau$ :

$\sigma^2_j = \frac{1}{N}\sum_{i=1}^{N} (x_{ij} - \mu_j)^2 < \tau, \quad \mu_j = \frac{1}{N}\sum_{i=1}^{N} x_{ij}$

Линейный коэффициент корреляции Пирсона: Измеряет степень линейной связи между непрерывным признаком $x^{(j)}$ и непрерывной целевой переменной $y$ :

$r_j = \frac{\sum_{i=1}^{N} (x_{ij} - \mu_j)(y_i - \mu_y)}{\sqrt{\sum_{i=1}^{N} (x_{ij} - \mu_j)^2 \sum_{i=1}^{N} (y_i - \mu_y)^2}}$

Критерий Хи-квадрат ( $\chi^2$ -тест): Применяется для качественных (категориальных) признаков. Проверяет гипотезу о независимости признака $j$ и целевой переменной. Статистика вычисляется на основе таблицы сопряженности:

$\chi^2_j = \sum_{u=1}^{U} \sum_{v=1}^{V} \frac{(O_{uv} - E_{uv})^2}{E_{uv}}$

где $O_{uv}$ — наблюдаемое число объектов, сочетающих $u$ -е значение признака и $v$ -й класс, а $E_{uv}$ — ожидаемое число объектов при гипотезе о независимости.

Взаимная информация (Mutual Information): Базируется на энтропии Шеннона и улавливает произвольные нелинейные зависимости. Для дискретных случайных величин формула имеет вид:

$I(X^{(j)}; Y) = \sum_{x \in X^{(j)}} \sum_{y \in \mathbf{Y}} p(x, y) \ln \frac{p(x, y)}{p(x)p(y)}$

где $p(x, y)$ — совместное распределение вероятностей, а $p(x)$ и $p(y)$ — маргинальные распределения.

Изображение:L1L2.png

3. Методы обертывания (Wrapper Methods)

Методы обертывания используют целевой алгоритм машинного обучения в качестве функции оценки (score) для проверяемого подмножества признаков. Впервые подробно исследованы в работе Kohavi, John (1997).

Прямой последовательный отбор (Forward Stepwise Selection): Итерационный процесс, стартующий с пустого множества $S_0 = \emptyset$ . На шаге $t$ алгоритм жадно добавляет один признак, максимизирующий локальное качество:

$j_t = \arg\max_{j \in \Omega \setminus S_{t-1}} \text{Score}\left(A(X_{S_{t-1} \cup {j}})\right), \quad S_t = S_{t-1} \cup {j_t}$

Обратное последовательное исключение (Backward Stepwise Elimination): Процесс, обратный прямому отбору. Стартует с полного набора признаков $S_0 = \Omega$ , на каждом шаге отбрасывается переменная, удаление которой наносит минимальный ущерб точности модели.

Рекурсивное исключение признаков (Recursive Feature Elimination, RFE): Алгоритм (Guyon et al., 2002), обучающий модель на полном множестве, ранжирующий признаки по величине квадрата весовых коэффициентов линейного классификатора $c_j = w_j^2$ (или значимости в деревьях) и последовательно отсекающий наименее важные элементы.

4. Встроенные методы (Embedded Methods)

Встроенные методы осуществляют селекцию признаков непосредственно в ходе оптимизации внутренних параметров модели (процессы обучения и отбора математически неразделимы).

L1-регуляризация (LASSO): Метод аппроксимации разреженных решений (Tibshirani, 1996). За счет сингулярности (острых углов) ограничения L1-нормы в области нулевых значений, оптимизатор принудительно зануляет веса избыточных предикторов:

$Q_{LASSO}(w) = \frac{1}{2N} \sum_{i=1}^{N} \left(y_i - \sum_{j=1}^{D} w_j x_{ij}\right)^2 + \lambda \sum_{j=1}^{D} |w_j| \to \min_{w}$

где $\lambda$ — управляющий гиперпараметр. Признак $j$ считается исключенным, если $w_j = 0$ .

Elastic Net Регуляризация: Комбинирует штрафы L1 и L2 (Zou, Hastie, 2005) для преодоления ограничений LASSO при работе с коррелированными группами признаков:

$Q_{EN}(w) = \frac{1}{2N} \sum_{i=1}^{N} \left(y_i - \sum_{j=1}^{D} w_j x_{ij}\right)^2 + \lambda_1 \sum_{j=1}^{D} |w_j| + \lambda_2 \sum_{j=1}^{D} w_j^2 \to \min_{w}$

Уменьшение примеси в ансамблях деревьев (Mean Decrease Impurity, MDI): Метод оценки важности признаков в алгоритме Random Forest (Breiman, 2001). Значимость признака $j$ вычисляется как взвешенная сумма улучшений критерия информативности (например, Джини) по всем узлам $t$ , где было произведено разбиение по данному признаку:

$\text{MDI}(j) = \frac{1}{|T|} \sum_{t \in T} w(t) \left[ I(t) - \frac{N_{tL}}{N_t}I(t_L) - \frac{N_{tR}}{N_t}I(t_R) \right]$

где $I(t)$ — значение неопределенности в узле, $w(t)$ — доля объектов, прошедших через узел, а $t_L$ и $t_R$ — левое и правое поддеревья соответственно.

5. Функции потерь и информационные критерии оценки

Для оценки оптимальности подмножеств признаков в линейных и классических вероятностных моделях используют критерии, накладывающие явный штраф за избыточную параметризацию (мощность подмножества $d$ ):

Информационный критерий Акаике (AIC):

$\text{AIC} = 2d - 2\ln(L_{max})$

где $L_{max}$ — максимизированное значение функции правдоподобия (Likelihood function) модели.

Байесовский информационный критерий Шварца (BIC):

$\text{BIC} = d\ln(N) - 2\ln(L_{max})$

Штрафует за размерность жестче, чем AIC, при объемах выборки $\ln(N) > 2$ .

Скорректированный коэффициент детерминации ( $R^2_{adj}$ ): Используется в задачах регрессии:

$R^2_{adj} = 1 - (1 - R^2)\frac{N - 1}{N - d - 1}$

6. Метрики качества работы методов отбора

Интегральная оценка алгоритмов селекции оперирует не только ошибкой аппроксимации, но и показателями стабильности:

Стабильность отбора (Индекс Жакара): Оценивает инвариантность метода к малым возмущениям обучающей выборки. Для двух подмножеств $S_1$ и $S_2$ , полученных на разных подвыборках:

$J(S_1, S_2) = \frac{|S_1 \cap S_2|}{|S_1 \cup S_2|}$

Скорректированный индекс Кунчевой (Kuncheva's Stability Index): Учитывает вероятность случайного совпадения признаков в высокоразмерных пространствах:

$I_K(S_1, S_2) = \frac{r \cdot D - d^2}{d \cdot (D - d)}$

где $r = |S_1 \cap S_2|$ — размер пересечения подмножеств, а $d$ — их фиксированная мощность ( $|S_1|=|S_2|=d$ ). Диапазон значений: $[-1, 1]$ .

7. Практические рекомендации и типичные ошибки

Утечка данных (Data Leakage) при кросс-валидации: КРИТИЧЕСКАЯ И САМАЯ РАСПРОСТРАНЕННАЯ ОШИБКА. Расчет любых статистик фильтрации (например, взаимной информации или корреляций) должен производиться строго внутри тренировочных фолдов. Если выполнить отбор признаков на всей матрице $X$ до разбиения на фолды кросс-валидации, информация из валидационных подвыборок попадет в модель, что приведет к сильному оптимистическому смещению оценок качества (ошибка генерализации будет занижена).

Чувствительность к масштабу данных: Большинство регуляризаторов (LASSO, Elastic Net) и оберток на базе линейных моделей критичны к масштабу. Перед началом процедуры отбора матрица признаков $X$ подлежит обязательной стандартизации:

$\tilde{x}{ij} = \frac{x{ij} - \mu_j}{\sigma_j}$

Проблема группировки при мультиколлинеарности: Если в выборке присутствует группа строго коррелированных признаков (например, $r > 0.95$ ), классический метод LASSO случайным образом выберет один из них, занулив остальные. Это делает интерпретацию модели нестабильной. Для сохранения всей группы информативных связанных переменных необходимо отдавать предпочтение регуляризатору Elastic Net.

Литература

Breiman L. Random forests // Machine learning. — 2001. — Vol. 45. — P. 5-32.

Guyon I., Weston J., Barnhill S., Vapnik V. Gene selection for cancer classification using support vector machines // Machine learning. — 2002. — Vol. 46. — P. 389-422.

Kohavi R., John G. H. Wrappers for feature subset selection // Artificial intelligence. — 1997. — Vol. 97, no. 1-2. — P. 273-324.

Tibshirani R. Regression shrinkage and selection via the lasso // Journal of the Royal Statistical Society: Series B (Methodological). — 1996. — Vol. 58, no. 1. — P. 267-288.

Zou H., Hastie T. Regularization and variable selection via the elastic net // Journal of the Royal Statistical Society Series B: Statistical Methodology. — 2005. — Vol. 67, no. 2. — P. 301-320.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D1%82%D0%B1%D0%BE%D1%80_%D0%BF%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA%D0%BE%D0%B2»

@@ Строка 7: / Строка 7: @@
 === 1. Математическая постановка задачи ===
 Пусть задана обучающая выборка, представленная в виде матрицы объекты-признаки <tex>X \in \mathbf{R}^{N \times D}</tex>, где <tex>N</tex> — количество независимых объектов (наблюдений), а <tex>D</tex> — исходная размерность признакового пространства. Каждому объекту (строке матрицы) <tex>x_i \in \mathbf{R}^D</tex> поставлен в соответствие истинный ответ (целевая переменная) <tex>y_i \in \mathbf{Y}</tex>. Для задач регрессии <tex>\mathbf{Y} = \mathbf{R}</tex>, для задач многоклассовой классификации <tex>\mathbf{Y} = {1, \dots, K}</tex>.
-[[Изображение: sueta.png]]
+[[Изображение: tecture.png]]
 Определим полное множество индексов исходных признаков как:
 :<tex>\Omega = {1, \dots, D}, \quad |\Omega| = D</tex>
@@ Строка 33: / Строка 33: @@
 :<tex>I(X^{(j)}; Y) = \sum_{x \in X^{(j)}} \sum_{y \in \mathbf{Y}} p(x, y) \ln \frac{p(x, y)}{p(x)p(y)}</tex>
 :: где <tex>p(x, y)</tex> — совместное распределение вероятностей, а <tex>p(x)</tex> и <tex>p(y)</tex> — маргинальные распределения.
+[[Изображение : L1L2.png]]
 === 3. Методы обертывания (Wrapper Methods) ===
 Методы обертывания используют целевой алгоритм машинного обучения в качестве функции оценки (score) для проверяемого подмножества признаков. Впервые подробно исследованы в работе Kohavi, John (1997).