SELECTION AN OPTIMAL NUMBER OF VARIABLES IN REGRESSION MODELS USING ADJUSTED COEFFICIENT OF DETERMINATION AS A MIXED INTEGER LINEAR PROGRAMMING PROBLEM

Abstract


When constructing a regression model, the primary problem faced by the researcher is that it is not clear what the equation of connection between the explained and explanatory variables should be. This initial stage of construction the selection of the model structural specification is called. When choosing a regression specification in parallel, the question arises of which explanatory variables should be included in the equation. This is the problem of variables selection in regression models. Its essence is to single out from the set of “candidates” for inclusion a subset of the most informative of them based on some quality criterion. The article is devoted to the problem of variables selection in regression models estimated using the ordinary least squares. The previously proposed approach to selection a given number of variables based on mixed 0-1 linear programming is considered. The unknown parameters in this problem are the beta coefficients of standardized regression and Boolean variables that are responsible for the occurrence of factors in the model. The optimal values of unknown parameters are found on the basis of maximizing the value of the coefficient of determination of regression. Unfortunately, to solve the problem under consideration, it is required to manually set the number of selected factors, which is often impossible to determine in advance. Therefore, the goal was to formalize the problem so that as a result of its solution the optimal number of selected regressors was also determined. For this purpose, the adjusted determination coefficient, depending on the number of model factors, was used as the objective function. As a result, the problem of mixed integer linear programming was formulated. The unknown parameters in it are still beta coefficients and Boolean variables, as well as an integer variable - the number of regressors. Based on data on prices and characteristics of sedans and hatchbacks of the American automobile industry, a computational experiment was carried out confirming the correctness of the developed mathematical apparatus. The problem formalized in this work in the form of a mixed integer linear programming looks more preferable from a computational point of view than the same problem formalized in modern scientific literature as a mixed quadratic linear programming.

Full Text

Введение Регрессионный анализ [1, 2] в настоящее время является распространенным статистическим методом исследования влияния одной или нескольких объясняющих переменных на объясняемую переменную. За последние годы появилось множество научных работ, посвященных использованию в регрессионном моделировании аппарата математического программирования [3-6]. Полученная в результате оценивания регрессионная модель применяется для установления степени влияния факторов на выходную переменную, прогнозирования неизвестных значений объясняемой переменной, принятия широкого круга управленческих решений и т.д. При этом одной из основных проблем, возникающих в процессе построения регрессии, является выбор спецификации модели. Для этого в первую очередь необходимо определиться с составом входящих в модель факторов, т.е. выделить из множества «кандидатов» на включение подмножества наиболее информативных из них на основе некоторого критерия качества. Эта проблема называется задачей отбора информативных регрессоров (ОИР) [7]. В условиях роста объемов информации эта проблема весьма актуальна в области интеллектуального анализа данных и машинного обучения. Проведенный в работе [7] анализ методов ОИР позволил сделать вывод, что единственным из них, который гарантирует точное решение задачи, является метод перебора всех возможных регрессий. Остальные алгоритмы, такие как шаговая регрессия, ступенчатая регрессия, алгоритм последовательной замены, лассо Тибширани, метод наименьших углов, носят, по сути, эвристический характер. Точное решение задачи ОИР также может быть получено, если формализовать ее в виде задачи математического программирования. Так, в работе [8] задача ОИР при оценивании регрессионной модели с помощью метода наименьших модулей (МНМ) сведена к задаче частично булевого линейного программирования, а при оценивании с помощью метода наименьших квадратов (МНК) - к задаче частично булевого квадратичного программирования. При этом число регрессоров должно быть зафиксировано исследователем. Но в связи с тем, что оптимальное число отбираемых регрессоров априори неизвестно, появилась работа [9], в которой выбор оптимального числа регрессоров формализован в виде задачи частично целочисленного линейного программирования для критерия средней абсолютной ошибки и в виде задачи частично целочисленного квадратичного программирования для критерия средней квадратичной ошибки. В статье [10] задача выбора оптимального числа информативных регрессоров сведена к задаче частично целочисленного квадратичного программирования для скорректированного коэффициента детерминации, критерия Акаике и Шварца, а в работе [11] еще и для критерия Мэллоуза. В работах [12, 13] рассмотрены вычислительные аспекты проблемы ОИР как задачи частично целочисленного программирования. Таким образом, в современных литературных источниках проблема ОИР при оценивании регрессионной модели с помощью МНК формализована только в виде задачи частично булевого квадратичного программирования при фиксированном числе регрессоров и в виде задачи частично целочисленного квадратичного программирования при неизвестном числе регрессоров. Однако автору в работах [14, 15] удалось свести задачу ОИР при оценивании регрессионной модели с помощью МНК к задаче частично булевого линейного программирования для заданного числа регрессоров. Данная статья является логическим продолжением работ [14, 15]. Ее целью является формализация проблемы выбора оптимального числа информативных регрессоров по скорректированному коэффициенту детерминации при МНК-оценивании регрессионных моделей в виде задачи частично целочисленного линейного программирования. 1. Проблема ОИР для заданного числа регрессоров как задача частично булевого линейного программирования Рассмотрим модель множественной линейной регрессии: (1) где , - значения зависимой (объясняемой) переменной y; , , …, , - значения m независимых (объясняющих) переменных (регрессоров) , , …, ; , - ошибки аппроксимации; , , …, - неизвестные параметры; - объем выборки. Пусть неизвестные параметры модели (1) оцениваются с помощью МНК, суть которого состоит в минимизации суммы квадратов ошибок аппроксимации: (2) Приведем строгую постановку задачи отбора информативных регрессоров (ОИР) [7]. Пусть задана выборка из наблюдений для зависимой переменной , , и для возможных независимых переменных , , . Необходимо выделить из возможных регрессоров переменных, минимизируя функцию потерь (2) для регрессии (1). Для того чтобы свести эту задачу к задаче частично булевого программирования так, как это сделано в работе [14], проведем нормирование (стандартизацию) всех переменных по формулам , , …, , где , …, - средние значения переменных; , …, - среднеквадратические отклонения переменных; , , …, - стандартизованные переменные, для которых среднее значение равно 0, а среднеквадратическое отклонение равно 1. Тогда регрессии (1) ставится в соответствие ее стандартизованная модель: , (3) где , …, - неизвестные параметры (бета-коэффициенты); - ошибки аппроксимации. В работах [14, 15] показано, что МНК-оценки стандартизованной модели (3) являются решением системы линейных алгебраических уравнений, представленной в матричном виде: , где - матрица коэффициентов интеркорреляции; - вектор-столбец коэффициентов корреляции между объясняемой переменной и объясняющими переменными; - вектор-столбец бета-коэффициентов. Коэффициент детерминации регрессии (1) связан с бета-коэффициентами соотношением (4) Тогда проблема ОИР может быть сформулирована в виде следующей задачи частично булевого линейного программирования: (5) , , (6) , , (7) , . (8) (9) где Ki - i-я строка матрицы коэффициентов интеркорреляции K; hi - i-й элемент вектора h; - заранее выбранное большое положительное число; Решение задачи (5)-(9) позволяет оценить лишь бета-коэффициенты , Для перехода к оценкам параметров регрессии (1) необходимо воспользоваться следующими формулами: , , Для решения задачи частично булевого линейного программирования (5)-(9) требуется задавать число информативных регрессоров m, которое априори практически всегда неизвестно. Исходя из этого переформулируем эту задачу так, чтобы ее решение выдавало оптимальное число информативных регрессоров. 2. Проблема выбора оптимального числа регрессоров как задача частично целочисленного линейного программирования Рассмотрим скорректированный коэффициент детерминации модели (1): , (10) где - коэффициент детерминации; - количество наблюдений; m - количество объясняющих переменных. Коэффициент (10) применяется для того, чтобы можно было сравнивать модели с разным числом объясняющих переменных. Он «штрафует» регрессию за дополнительно включенные факторы. Чем больше значение скорректированного коэффициента детерминации, тем адекватнее модель. С учетом формул (4) и (10) можно ввести функционал (11) где переменная удовлетворяет ограничениям , (12) Тогда решение задачи частично целочисленного нелинейного программирования с целевой функцией (11) и с ограничениями (6)-(9), (12) гарантирует выбор оптимального числа m информативных регрессоров. Проведем линеаризацию задачи (11), (6)-(9), (12). Из выражения (10) следует, что (13) В равенстве (13) нелинейным является только слагаемое . Перепишем выражение (13) в виде (14) где переменные , подчинены условию . (15) Условия (15) можно заменить следующими линейными ограничениями: , , (16) , . (17) Так, если , то из выражения (16) следует, что ; а если , то из формулы (17) следует, что . Введем целевую функцию (18) Тогда задача частично целочисленного линейного программирования с целевой функцией (18) и с линейными ограничениями (4), (6)-(9), (14), (12), (16), (17) равносильна задаче нелинейного программирования (11), (6)-(9), (12) и дает точное решение проблемы выбора оптимального числа информативных регрессоров по скорректированному коэффициенту детерминации в оцениваемой с помощью МНК регрессионной модели. 3. Вычислительный эксперимент Для проведения вычислительного эксперимента были использованы статистические данные эконометрического пакета Gretl (встроенный файл data7-12.gdt) о ценах и характеристиках седанов и хэтчбеков американской автомобильной промышленности за 1995 г. Объем выборки Объясняемая переменная: price - цена, тыс. долл.; объясняющие переменные: hatch - тип автомобиля (1 - хэтчбек, 0 - седан); wbase - колесная база (расстояние между передней и задней осями), дюйм; length - длина автомобиля, дюйм; width - ширина автомобиля, дюйм; height - высота автомобиля, дюйм; weight - вес автомобиля, сотни фунтов; cyl - количество цилиндров двигателя; liters - объем двигателя, литры; gasmpg - экономичность расхода топлива, миль на галлон; trans - трансмиссия (1 - автомат, 0 - в противном случае). Была поставлена следующая задача: из 10 объясняющих переменных выбрать оптимальное число информативных регрессоров по скорректированному коэффициенту детерминации в оцениваемой с помощью МНК регрессионной модели. Заметим, что эта задача может быть решена полным перебором всех возможных регрессий, общее количество которых Поставленная задача с использованием пакета LPSolve IDE была сформулирована в виде задачи частично целочисленного линейного программирования с целевой функцией (18) и с линейными ограничениями (4), (6)-(9), (14), (12), (16), (17). Подробные результаты итерационного решения этой задачи в LPSolve IDE представлены в таблице. Подробные результаты решения задачи Итерация 1 1 1 1 1 1 1 1 1 1 1 10 0,636366 0,585150 2 1 1 1 1 1 1 1 1 1 0 9 0,635668 0,590127 3 1 1 1 1 1 1 1 0 1 1 9 0,636122 0,590638 4 1 1 1 1 1 1 1 0 1 0 8 0,635276 0,595306 5 1 1 1 0 1 1 1 1 1 0 8 0,635525 0,595582 6 1 1 1 0 1 1 1 0 1 1 8 0,636051 0,596166 7 1 1 1 0 1 1 1 0 1 0 7 0,635182 0,600672 Полученная в результате МНК-оценивания семифакторная регрессионная модель имеет вид (19) Ее коэффициент детерминации , а скорректированный коэффициент детерминации Отметим, что тот же самый результат показал метод полного перебора всех возможных регрессий, что подтверждает корректность предложенного в данной работе математического аппарата. Заключение В данной работе проблема выбора оптимального числа информативных регрессоров по скорректированному коэффициенту детерминации в регрессионных моделях, оцениваемых с помощью МНК, сведена к задаче частично целочисленного линейного программирования. Отметим, что в работе Р. Мияширо и Ю. Такано [10] эта проблема представлена в виде задачи частично целочисленного квадратичного программирования. А поскольку методы решения задач линейного программирования гораздо более эффективны, чем методы решения задач квадратичного программирования, применение описанного в данной работе математического аппарата на практике должно привести к снижению времени решения задачи. Помимо этого, представленный в настоящей работе новый подход, так же как и метод полного перебора регрессий, гарантирует точное решение поставленной задачи. Однако в первом случае это решение находится с помощью метода ветвей и границ, отсекающего подмножества решений, заведомо не содержащих оптимальных решений. А это означает, что теоретически метод полного перебора всех регрессий должен уступать по скорости предложенному подходу. Исследование этих двух вопросов будет представлено в дальнейших работах автора.

About the authors

M. P Bazilevskii

Irkutsk State Transport University

References

  1. Harrell Jr., Frank E. Regression modeling strategies: with applications to linear models, logistic and ordinal regression, and survival analysis. - Springer Series in Statistics, 2015. - 582 p.
  2. Kuhn M., Johnson K. Applied predictive modeling. - Springer, 2018. - 600 p.
  3. Базилевский М.П., Носков С.И. Оценивание индексных моделей регрессии с помощью метода наименьших модулей // Вестник Российского нового университета. Сер. Сложные системы: модели, анализ и управление. - 2020. - № 1. - С. 17-23.
  4. Базилевский М.П., Носков С.И. Программный комплекс построения линейной регрессионной модели с учетом критерия согласованности поведения фактической и расчетной траекторий изменения значений объясняемой переменной // Вестник Иркутск. гос. техн. ун-та. - 2017. - Т. 21, № 9 (128). - С. 37-44.
  5. Базилевский М.П., Носков С.И. Формализация задачи построения линейно-мультипликативной регрессии в виде задачи частично-булевого линейного программирования // Современные технологии. Системный анализ. Моделирование. - 2017. - № 3 (55). - С. 101-105.
  6. Носков С.И. О методе смешанного оценивания параметров линейной регрессии // Информационные технологии и математическое моделирование в управлении сложными системами. - 2019. - № 1 (2). - С. 41-45.
  7. Носков С.И., Базилевский М.П. Построение регрессионных моделей с использованием аппарата линейно-булевого программирования / ИрГУПС. - Иркутск, 2018. - 176 с.
  8. Konno H., Yamamoto R. Choosing the best set of variables in regression analysis using integer programming // Journal of Global Optimization. - 2009. - Vol. 44, no. 2. - P. 272-282.
  9. Park Y.W., Klabjan D. Subset selection for multiple linear regression via optimization. - 2020. - URL: https://arxiv.org/pdf/1701.07920.pdf 081 (accessed 13 March 2020).
  10. Miyashiro R., Takano Y. Mixed integer second-order cone programming formulations for variable selection in linear regression // European Journal of Operational Research. - 2015. - Vol. 247. - P. 721-731. doi: 10.1016/j.ejor.2015.06.081
  11. Miyashiro R., Takano Y. Subset selection by Mallows’ Cp: A mixed integer programming approach // Expert Systems with Applications. - 2015. - Vol. 42. - P. 325-331. doi: 10.1016/j.eswa.2014.07.056
  12. Bertsimas D., King A., Mazumder R. Best subset selection via a modern optimization lens // The Annals of Statistics. - 2016. - Vol. 44, no. 2. - P. 813-852.
  13. Bertsimas D., King A. OR Forum - An algorithmic approach to linear regression // Operations Research. - 2016. - Vol. 64, no. 1. - P. 2-16.
  14. Базилевский М.П. Сведение задачи отбора информативных регрессоров при оценивании линейной регрессионной модели по методу наименьших квадратов к задаче частично-булевого линейного программирования // Моделирование, оптимизация и информационные технологии. - 2018. - Т. 6, № 1 (20). - С. 108-117.
  15. Базилевский М.П. Отбор информативных регрессоров с учетом мультиколлинеарности между ними в регрессионных моделях как задача частично-булевого линейного программирования // Моделирование, оптимизация и информационные технологии. - 2018. - Т. 6, № 2 (21). - С. 104-118.

Statistics

Views

Abstract - 51

PDF (Russian) - 19

Refbacks

  • There are currently no refbacks.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies