Введение

При всем существующем разнообразии методов Data Mining, практически все они сталкиваются с общей трудностью – вопросом отбора значимых для модели входных признаков (в зарубежной литературе такая проблема известна как feature selection).Сокращение числа независимых переменных призвано уменьшить размерность модели не только с тем, чтобы удалить из нее все незначащие признаки, не несущие в себе какой-то полезной для анализа информации, и тем самым упростить модель, но и чтобы устранить избыточные признаки. Дублирование информации в составе избыточного признака не просто не улучшает качество модели, но и порой, наоборот, ухудшает его (как, например, в случае с мультиколлинеарностью).

Очевидно, что одним из возможных выходов из сложившейся проблемы могло бы стать построение модели на всех возможных комбинациях наборов входных признаков с последующим отбором того варианта, который обладал бы наилучшей описательной способностью результирующего признака $Y$ и при этом содержал бы минимум независимых переменных. Однако такое решение возможно лишь при наличии незначительного количества факторов-претендентов на включение в модель. В случае же относительно большого списка потенциальных признаков подобная методика представляется достаточно затруднительной, так как количество моделей, которые необходимо будет построить, оказывается крайне велико и в общем случае равно $2^n$ – 1 штука (так называемое "проклятие" размерности). Ввиду этого необходимо иметь на вооружение какие-то иные алгоритмы отбора наиболее важных факторов, которые потребовали бы значительно меньших затрат усилий, а соответственно и времени.

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

• процедура Forward Selection (прямой отбор),
• процедура Backward Elimination (обратное исключение),
• процедура Stepwise,
• процедура Best Subsets (лучшие подмножества).

Рассмотрим работу данных методов на примере множественной регрессии.

Частный F-тест

Перед тем, как начать знакомиться непосредственно с самими методами отбора переменных в регрессионные модели, рассмотрим сущность критерия, называемого частным F-тестом, на основе которого, собственно, и разработаны первые 3 методики.

Критерий призван оценить целесообразность ввода дополнительной независимой переменной в линейную модель множественной регрессии, уравнение которой, как известно, имеет вид:

$Y= \beta_0+ \beta_1 X^{<1>} + \dots + \beta_n X^{<\mbox {n}>} + \varepsilon$, (1)

где

$Y$ – зависимая переменная,

$X^{<1>},\,X^{<2>},\,\dots,\,X^{<\mbox {n}>}$ – независимые переменные,

$\beta_0,\,\beta_1,\,\dots,\,\beta_n$ – параметры модели,

$\varepsilon$ – случайная составляющая.

Идея этого критерия основана в первую очередь на таком базовом понятии, как сумма квадратов регрессии $SSR$:

$SSR = \sum \limits_{i=1}^{n} {\Bigl(\widehat{Y_i}\,-\,\overline{Y}\Bigr)}^2$, (2)

где

$\widehat{Y_i}$ – оценка, полученная на основе регрессионной модели,

$\overline{Y}$ – среднее по всем наблюдениям $Y$,

$n$ – объем выборки.

Данный показатель характеризует ту долю общей вариации (изменчивости) результативного признака $Y$, которую получилось объяснить при помощи регрессии. Проиллюстрируем данный факт на примере простейшей однофаторной линейной модели (рисунок 1).

Поясним рисунок 1. Очевидно, что если бы регрессия не включала бы ни одного фактора, то модель бы выдавала значения, равные $\overline{Y}$. Соответственно, разности $Y_i\,-\,\overline{Y}\,(i = 1,\,2,\,\dots,\,n)$ представляли бы собой необъясненные случайные отклонения. Благодаря же вводу независимой переменной $X$ оценки, полученные на основании модели, стремятся оказаться как можно ближе к реальным значениям случайной величины $Y$. В связи с этим каждое расстояние $Y_i\,-\,\overline{Y}$ может быть разложено на 2 составляющие:

$\widehat{Y_i}\,-\,\overline{Y} $ – было объяснено регрессией,

$Y_i\,-\,\widehat{Y_i} $ – не удалось объяснить.

Соответственно, модель оказывается тем лучше, чем ближе к нулю величины $Y_i\,-\,\widehat{Y_i},\,i = 1,\,2,\,\dots,\,n$.

Теперь предположим, что на основе переменных $X^{<1>},X^{<2>},\dots,X^{<\mbox {k}>} $ была построена регрессионная модель, для которой доля изменчивости, объясненная линейной зависимостью, составила величину $SSR^{<\mbox {initial}>}$. Допустим, что мы хотим ввести в модель новый признак $X^{<\mbox {extra}>}$.

Сумма квадратов регрессии $SSR$, построенной на независимых переменных $X^{<1>},\,X^{<2>},\,\dots\,X^{<\mbox {k}>}$ и $X^{<\mbox {extra}>}$, составляет $SSR{<\mbox {full}>}$.

Очевидно, что $SSR^{<\mbox {full}>}\geq SSR^{<\mbox {initial}>}$.

Рассчитаем, насколько увеличилась объясняющая способность модели в результате ввода новой переменной $X^{<\mbox {extra}>}$:

$SSR^{<\mbox {extra}>}=SSR^{<\mbox {full}>}-SSR^{<\mbox {initial}>}$

Таким образом, $SSR^{<\mbox {extra}>}$ можно назвать вкладом переменной $SSR^{<\mbox {extra}>}$ в объяснение общей изменчивости результативного признака $Y$. Очевидно, чем больше данное значение, тем весомей этот вклад. Тогда возникает вопрос:

"Каким образом следует выбрать порог для $SSR^{<\mbox {extra}>}$, чтобы признать эту величину достаточно большой и, соответственно, принять решение о значимости признака ${}^{<\mbox {extra}>}$?".

С ответом на этот вопрос может помочь так называемый частный F-тест. По сути, данный критерий призван проверить следующую гипотезу:

против альтернативы

Для того чтобы проверить эти гипотезы, следует перейти от рассматриваемого показателя $SSR^{<\mbox {extra}>}$ к статистике следующего вида:

$\gamma = \frac{SSR<\mbox {extra}>}{MSE^{<\mbox {full}>}}$, (4)

где $MSE^{<\mbox {full}>}$ представляет собой сумму квадратов ошибок $SSE$ (модель построена по переменным $X^{<1>},\,X^{<2>},\,\dots\,X^{<\mbox {k}>}$ и $X^{<\mbox {extra}>}$), приходящуюся на одну степень свободы $df^{<\mbox {sse}>}$.

Значение $MSE^{<\mbox {full}>}$ может быть найдено по формуле:

$$MSE^{<\mbox {full}>} = \frac{\mbox {SSE}}{df^{<\mbox {sse}>}} = \frac{\sum \limits_{i=1}^{n} {\bigl(Y_i\,-\,\widehat{Y_i}\bigr)}^2}{n\,-\,k\,-\,2}$$

где

$Y_i$ – истинное значение результирующей переменной,
$\widehat{Y_i}$ – оценка, полученная на основании регрессионной модели,
$n$ – объем выборки,
$k$ – количество переменных исходной модели (без $X^{<\mbox {extra}>}$).

Доказано, что статистика, сформированная в соответствии с (4), при справедливости гипотезы H₀ распределена по закону Фишера (F-распределение).
Тогда проверка гипотезы H₀ будет сводиться к следующей последовательности действий:

1. Задаемся уровнем значимости $\alpha$, например 0,01 или 0,05.
   Данная величина характеризует риск принятия неправильного решения.
2. По специальным таблицам находим $00\,\alpha$-процентную точку $K_{\alpha}$ распределения Фишера со степенями свободы $d1= 1$ и $d2 = n-k-2$. Это значение будет являться граничным для статистики $ \gamma$ (4).
3. Сравниваем найденную $100\,\alpha$-процентную точку $K_{\alpha}$ со значением статистики $\gamma$.
   Если окажется, что $\gamma\,>\,K_{\alpha}$, то делается вывод о значимости признака $X^{<\mbox {extra}>}$ и, соответственно, его следует включить в модель (отдается предпочтение гипотезе H₁ с вероятностью $\alpha$ ошибиться).
   Если же $\gamma\,\leq \,K_{\alpha} $, то принимается решение о неэффективности включения переменной $X^{<\mbox {extra}>}$ в модель (то есть гипотеза H₀ принимается с вероятностью $1\,-\,\alpha$ как не противоречащая экспериментальным данным).
   

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

Методы отбора переменных

Метод прямого отбора (Forward Selection)

Данный алгоритм включает в себя следующие шаги:

1. Из списка всех возможных входных переменных выбирается та, которая имеет наибольшую корреляцию с $Y$, после чего модель, содержащая лишь одну выбранную независимую переменную, проверяется на значимость при помощи частного F-критерия. Если значимость модели не подтверждается, то алгоритм на этом заканчивается за неимением существенных входных переменных. В противном случае эта переменная вводится в модель и осуществляется переход к следующему пункту алгоритма.
   Следует отметить, что в данном случае проверка на значимость всей модели в целом будет равносильна проверке на значимость выбранной независимой переменной, так как на данном этапе модель еще не содержит других входных переменных.
2. По всем оставшимся переменным на основании формулы (4) рассчитывается значение статистики $ \gamma$, которая представляет собой отношение прироста суммы квадратов регрессии, достигаемая за счет ввода в модель соответствующей дополнительной переменной (по сравнению с величиной $SSR^{<\mbox {initial}>}$, рассчитанной только лишь на основе ранее уже введенных переменных), к величине $MSE^{<\mbox {full}>} $.
3. Из всех переменных-претендентов на включение в модель выбирается та, которая имеет наибольшее значение критерия, рассчитанного в пункте 2.
4. Проводится проверка на значимость выбранной в пункте 3 независимой переменной. Если ее значимость подтверждается, то она включается в модель, и осуществляется переход к пункту 2 (но уже с новой независимой переменной в составе модели). В противном случае алгоритм останавливается.

Процедуру отбора независимых переменных по методу Forward Selection можно представить в виде блок-схемы, изображенной на рисунке 2.

Метод обратного исключения (Backward Elimination)

Данная процедура похожа на предыдущий метод, но с тем отличием, что теперь уже изначально включены в модель все переменные и постепенно осуществляется "отсеивание" тех из них, которые не проходят проверку на значимость.

1. В модель включаются все имеющиеся независимые переменные.
2. По переменным, включенным к данному моменту в модель, рассчитывается величина, представляющая собой разность между суммой квадратов регрессии, построенной по всем текущим переменным модели, и аналогичным показателем, рассчитанным теперь уже без учета одной переменной, для которой вычисляется данный показатель. По каждой найденной величине $SSR_{I^{<\mbox {initial}>}}$ рассчитывается статистика $\gamma$.
3. Выбирается переменная с минимальным значением $\gamma$.
4. Решается вопрос о целесообразности присутствия в модели выбранной в пункте 3 переменной. Если она не проходит проверку на значимость, то производится ее исключение из модели, после чего осуществляется переход к пункту 2 алгоритма, но уже из расчета, что указанная переменная в модели не присутствует. В противном случае, когда переменная оказывается значимой, алгоритм останавливается.

На рисунке 3 приведена блок-схема процедуры отбора факторов методом обратного исключения.

Метод последовательного отбора (Stepwise)

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

Ниже на рисунке 4 приведена блок-схема соответствующего метода.

Отбор на основе "лучших подмножеств" (Best Subsets)

Данный метод предусматривает, что аналитик изначально должен определиться с максимально возможным количеством $p$ входных признаков, задействованных в модели. Далее поступают следующим образом: по всему перечню переменных строятся $p$ групп моделей, причем первую такую группу составляют все однофакторные модели, которые только можно построить на имеющемся наборе признаков, соответственно, во вторую попадают все двухфакторные модели и т. д. вплоть до $p$-й группы (куда входят все модели, включающие $p$ факторов). По всем полученным моделям рассчитываются статистические показатели, характеризующие качество модели, такие как коэффициент детерминации $R^2$, скорректированный коэффициент детерминации $R^2_{odj}$, стандартная ошибка оценивания $s$ (равная квадратному корню из суммы квадратов ошибки модели, приходящейся на одну степень свободы $MSE$) и другие. Затем из каждой полученной группы отбираются только $k$ самых лучших моделей с точки зрения рассчитанных показателей, после чего формируется отчет, включающий $k\,\times\,p$ моделей, на основании которого аналитик непосредственно делает окончательное заключение.

Пример использования алгоритмов отбора

Разберем механизм работы описанных выше методов отбора переменных в линейную модель множественной регрессии на конкретном примере. В качестве исследуемых признаков возьмем показатели из банковской сферы, приведенные в таблице 1.

Таблица 1 – Переменные, используемые при построении регрессионной модели

В таблице 2 содержится информация о 10 заемщиках по каждой из заявленных переменных.

Таблица 2 – Данные по заемщикам

Рассмотрим алгоритмы отбора переменных в модель множественной регрессии на имеющихся данных.

Прямой отбор (Forward Selection)

Разберем работу рассматриваемой процедуры на данных, приведенных в таблице 2.

Согласно рекомендациям этого метода, на первом шаге алгоритма приоритет на включение в модель имеет тот из факторов, который сильнее всего коррелирован с результирующим признаком.

Таблица 3 – Корреляция входных переменных с результирующим признаком

Как можем видеть из таблицы 3, $X2$ характеризуется наибольшей теснотой линейной связи с $Y$. Поэтому именно эта переменная должна быть первой подвергнута процедуре проверки на включение в модель. Найдем оценки значений результирующего признака, полученные на основании модели, которая включает только одну независимую переменную $X2$. Соответствующие результаты сведены в таблицу 4.

Таблица 4 – Исходные и расчетные данные, необходимые для проверки значимости переменной $X2$

Теперь, используя данные таблицы 4, рассчитаем величину частного F-критерия, соответствующую $X2$.

$$MSE^{<\mbox {extra}>} = \frac{SSE^{<\mbox {extra}>}}{df^{<\mbox {SSE}>}} = \frac{4,376}{8} = 0,547$$

$$F_{real} = \frac{SSR^{<\mbox {extra}>}}{MSE^{<\mbox {full}>}} = \frac{SSR^{<\mbox {full}>}\,-\,0}{MSE^{<\mbox {full}>}} = \frac{13,724}{0,547} = 25,09$$

По таблице значений F-критерия Фишера на уровне значимости $\alpha = 0,05$ найдем граничное значение для $F_{real}$ (при количестве степеней свободы $d1= 1$ и $d2 = 8$). Информацию, необходимую для получения заключения о значимости $X2$ для регрессионной модели (или, наоборот, его бесполезности) можно найти в таблице 5.

Таблица 5 – Дисперсионный анализ для проверки значимости фактора $X2$

Как можем видеть из таблицы 5, рассчитанное значение F-критерия существенно превышает пороговое значение $F_{table}$, что указывает на необходимость включения переменной $X2$ в регрессионную модель (при этом вероятность того, что решение о включении окажется неправильным, составляет $\alpha = 0,05$).

На данном шаге алгоритма исходный список потенциальных переменных модели сократился на 1 благодаря переводу $X2$ ("Срок кредита") в категорию значимых переменных. Таким образом, остается решить вопрос о включении для $X1$ ("Стаж на последнем месте работы") и $X3$ ("Сумма кредита").

Найдем прирост суммы квадратов регрессии $SSR^{<\mbox {extra}>}$, который можно наблюдать при поочередном включении в модель $X1$ и $X3$ (при условии, что переменная $X2$ входит в состав регрессии). Результаты вычислений приведены в таблице 6.

Таблица 6 – Расчет прироста $SSR$ за счет ввода переменных $X1$ и $X3$

Получим значения частного F-критерия для $X1$ и $X3$. Соответствующие данные можно найти в таблице 7.

Таблица 7 – Расчет частного F-критерия для $X1$ и $X3$ при введенной в модель переменной $X2$

В таблице 7 запись "$X1|X2$" означает, что расчет ведется для переменной $X1$ без учета той доли вариации, которая уже была объяснена ранее введенной переменной $X2$.

Как можем видеть из таблицы 7, наибольшее значение частного F-критерия соответствует $X1$. Поэтому именно эта переменная должна быть проверена в первую очередь на возможность ее включения в модель. Как и ранее, признаком значимости для исследуемого показателя является факт превышения рассчитанного для него значения F-статистики по отношению к граничной величине $F_{table}$. В нашем случае, очевидно, выполняется неравенство:

$$F_{real}\,\Bigl(= 7,777\Bigr)\,>\,F_{table}\,\Bigl(= 5,591\Bigr)$$

В связи с этим нулевую гипотезу об отсутствии значимости рассматриваемой переменной следует отклонить как противоречащую экспериментальным данным (при этом вероятность ошибки составляет $\alpha = 0,05$). Таким образом, делаем вывод:

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

Среди претендентов на включение в модель осталась всего лишь одна переменная $X3$. Все остальные успешно прошли проверку на значимость. Получим для $X3$ значение частного F-критерия, который дает соответствующий признак из расчета, что переменные $X1$ и $X2$ уже вошли в модель. Результаты вычислений можно найти в таблице 8.

Таблица 8 – Расчет частного F-критерия для переменной $X3$ при введенных в модель $X2$ и $X1$

Как и ранее, существенность вклада переменной в объясняющую способность регрессионной модели определяется величиной $F_{real}$. Данное значение для переменной $X3$ не сумело превысить требуемый уровень $F_{table}$, ввиду чего соответствующий признак "Сумма кредита" нельзя признать значимым. Иначе говоря, следует принять гипотезу $H_0$, требующую не включать рассматриваемую переменную в модель с вероятностью $1-\alpha$ правильности этого решения.

Таким образом, получаем следующий отчет о включенных в модель признаках (таблица 9).

Таблица 9 – Результаты отбора переменных в регрессионную модель процедурой Forward Selection

Обратное исключение (Backward Elimination)

Рассмотрим на тех же данных из таблицы 2 работу этого метода.

1. Изначально полагаем, что регрессия включает все предложенные независимые переменные. Проверим, не содержит ли она переменных, от которых можно было бы отказаться по причине незначительности их вклада в объясняющую способность модели. С этой целью выделим ту из переменных, которая характеризуется минимальным значением частного F-критерия, найденного из расчета, что остальные переменные включены в модель.

   Таблица 10 – Значение частного F-критерия всех переменных модели, включающей $X1$, $X2$, $X3$

   Анализируемая переменная	SSR <full>	SSR <initial>	SSR <extra>	MSE <full>	Freal
   X1	16,16	13,966	2,194	0,323	6,793
   X2	16,16	9,419	6,741	0,323	20,87
   X3	16,16	16,026	0,134	0,323	0,415

   Как можно видеть из таблицы 10, больше всего шансов быть исключенной из модели после проведения F-теста имеется у переменной $X3$, так как ей соответствует минимальное значение $F_{real} = 0,415$. В связи с этим именно данный признак должен быть первым проверен на значимость.

   По таблице значений F-критерия Фишера на уровне значимости $\alpha = 0,05$ при степенях свободы $d1=1$ и $d2=10-3-1=6$ находим, что $F_{table} = 5,987$. Переменная $X3$ не сумела преодолеть этот порог ($F_{real} = 0,415\,<\,5,987$), ввиду чего данный признак ("Сумма кредита") должен быть исключен из рассмотрения.

2. Проверим, оправданно ли включены в регрессию две оставшиеся переменные $X1$ и $X2$. В связи с этим для каждой из них пересчитаем значение частного F-критерия с учетом, что теперь модель уже не включает $X3$.

   Таблица 11 – Значение частного F-критерия всех переменных модели, включающей $X1$ и $X2$

   Анализируемая переменная	SSR <full>	SSR <initial>	SSR <extra>	MSE <full>	Freal
   X1	16,026	13,724	2,302	0,296	7,777
   X2	16,026	9,419	6,741	0,296	22,774

   Переменной $X1$ соответствует минимальное значение частного F-критерия, в связи с чем проверим ее на значимость. $F_{table}$ в данном случае будет равно $5,591$ ($d1=1$,$ d2=7$), что меньше, чем $F_{real} = 7,777$. Следовательно, $X1$ не следует удалять из модели.

С признанием переменной $X1$ значимой следует завершить алгоритм Backward Elimination. Таким образом, получаем, что согласно рекомендациям данной методике, регрессионная модель должна включать только 2 признака:
$X1$ – "Стаж на последнем месте работы",
$X2$ – "Срок кредита".
Такой результат полностью совпадает с тем, что дает процедура Forward Selection.

Метод Stepwise

1. Осуществляем прямой ход процедуры Forward Selection, по итогам которого имеем, что переменная $X2$ должна быть включна в модель (все расчеты были уже проведены в соответствующем пункте).

   Так как на данном этапе помимо $X2$ регрессия не содержит других переменных, то задействовать алгоритм Backward Elimination не представляется возможным.

2. Проводим мероприятия по включению новой переменной в регрессию. Выбранная переменная$X1$, которой соответствует максимальное значение частного F-критерия, проходит проверку на значимость и потому получает право войти в состав модели.

   Но на этом второй этап алгоритма, в отличие от процедуры Forward Selection, не заканчивается. Ввиду того, что теперь регрессия содержит 2 входные переменные, ранее включенный признак $X2$ может оказаться незначимой "на фоне" $X1$, так как часть дисперсии результативного признака, которая прежде объяснялась $X2$ , теперь может быть объяснена за счет нового фактора. Найдем значение частного F-критерия для $X2$ из расчета, что переменная $X1$ предварительно введена в модель.

   Таблица 12 – Проверка на значимость переменной $X2$ при включении в модель $X1$

   Источник	Количество степеней свободы (df)	Сумма квадратов (SS)	SS на одну степень свободы (MS)	Freal	Ftable
   Регрессия, обусловленная X2|X1	1	6,607	6,60	22,321	5,591
   Ошибки	7	2,074	0,296

   Как можем видеть из таблицы 12, $F_{real}\,>\,F_{table}$. Следовательно, признак $X2$ не следует исключать из модели.

3. Проверяем на значимость последнюю переменную $X3$. Соответствующую проверку она пройти не сумеет. Следовательно, алгоритм Stepwise завершит свою работу.

Заключение

Рассмотренные в данной статье методы последовательного отбора переменных не ограничиваются только случаем с линейной моделью множественной регрессии, но и могут иметь более широкий круг применения, в частности, быть использованы при логистической регрессии. При этом необходимо лишь выбрать иной критерий проверки переменной на значимость, нежели частный F-тест. Альтернативой ему в данном случае может стать тест Вальда (Wald test), тест множителей Лагранжа (Lagrange multiplier test) или тест отношения правдоподобия (Likelihood ratio test).