8.7.3. Схемы генерации наборов переменных.

Когда критерий качества набора предсказывающих переменных фиксирован для выбора оптимального или хотя бы «хорошего» набора, необходимо провести сравнение достаточно большого числа различных наборов переменных и выбрать среди них наилучший. Рассмотрим некоторые схемы генерации наборов, применяющиеся в настоящее время.

Схемы полного перебора («всех возможных регрессий», метод «ветвей и границ» . Задачу полного перебора можно сформулировать следующим образом: для найти набор из q предсказывающих переменных с минимальным значением остаточной суммы квадратов или, что эквивалентно, с максимальным значением коэффициента детерминации . Так как критерии, приведенные в п. 8.7.2, являются монотонными функциями от , то этот набор будет оптимальным и по любому из них.

Число различных подмножеств из q переменных, если всего имеется переменных, будет равно (числу сочетаний по q элементов из возможных), а полное число наборов при изменении q от 1 до будет Ясно, что это число очень быстро растет с ростом . Так, при оно будет примерно , а при Все же на современных ЭВМ возможна реализация полного перебора для значений порядка 15.

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

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

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

Объем вычислений при прямом переборе с ростом растет настолько быстро, что уже при превышает реальные возможности большинства ЭВМ. Выход из положения ищут с помощью методов ветвей и границ. Смысл этого метода заключается во введении какого-либо грубого правила, которое позволяет отбросить большинство наборов, не вычисляя для них значения критерия в силу их бесперспективности. Такое правило может быть основано на неравенстве где — любой набор предсказываю переменных, а — его подмножество.

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

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

Использование методов ветвей и границ позволяет рассматривать задачи с Наиболее эффективной является реализация алгоритма, предложенная в работе Фёрнивала [190]. Подробное описание одного из алгоритмов, реализующего метод «ветвей и границ», — алгоритма Хокинга—Лесли [206] на русском языке приведено в [79].