Прогнозирование спроса для сервиса доставки еды

"Научный аспект №6-2024" - Экономика и менеджмент

УДК 33

Ким Игорь Николаевич – магистрант Санкт-Петербургского государственного экономического университета.

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

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

Введение

В данной статье будет приведено описание моделей прогнозирования спроса. Будет приведено описание моделей машинного обучения для решения задачи регрессии. Для моделей прогнозирования спроса будут рассмотрены плюсы и минусы моделей.

Модели машинного обучения

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

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

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

Линейная регрессия

Постановка задачи: пусть у нас есть набор данных (X, y), где y – объясняемая переменная, а X – матрица признаков. Введем обозначения для модели [3]:

-  – матрица признаков наблюдений, где N – кол-во наблюдений и D – количество признаков у каждого объекта.

- y – вектор значений целевой переменной (таргета).

Задача: найти такую функцию f(x), которая наилучшим образом будет описывать зависимость  от . Общий вид искомой модели представлен в формуле (1) [3]:

(1)

где w – вектор параметров модели.

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

Если формула (1) верна, то каждое наблюдение можно описать в виде формулы (2) [3].

(2)

где  – коэффициент при j-ом признаке;

 – значение j-го признака в i-ом наблюдении;

 – случайная ошибка.

У модели линейной регрессии есть ряд ограничений с целью получения именно линейной модели, а не какой-то другой:

- математическое ожидание случайных ошибок было равно нулю;

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

- Отсутствие корреляции случайных ошибок.

Как уже сказано было ранее, для построения модели линейной регрессии важно подобрать оптимальные веса модели при признаках (). Существует ряд методов, которые могут помочь с решением данной задачи. Первый из них – это метод наименьших квадратов (в дальнейшем МНК), который подразумевает решение следующей оптимизационной задачи (см. формулу 3).  В дальнейших моделях данный метод будет использоваться для реализации модели линейной регрессии на языке Python [3].

(3)

Следовательно задача МНК – оптимизационная задача, которая заключается в минимизации среднеквадратического отклонения (СКО) между реальным значением функции и прогнозным (модельным). В рамках решения оптимизационной задачи множитель перед знаком суммы незначим.

Алгоритм МНК следующий:

- по функции ошибки считаем производные по каждому  и приравниваем к нулю;

- получаем на выходе систему из d линейных уравнений;

- решаем систему и получаем на выходе оценку значений .

Оценка  называется линейной, если параметр можно выразить в виде формулы (4). Именно такую оценку мы и получаем в ходе решения задачи минимизации СКО [3].

(4)

В следствие того, что решением задачи поиска оптимальных весов является линейная оценка, то и итоговая модель имеет название линейная регрессия. Стоит отметить, что МНК заложен в качестве базового алгоритма поиска оптимальных параметров модели в библиотеке sklearn, которая написана на языке Python.

Второй по популярности метод поиска оптимальных весов – метод максимального правдоподобия, в основу которого заложена идея вычисления вероятности получения истинного значения “y” при признаках X и весах w. В данной статье этот метод будет описан для непрерывной случайной величины.

- Пусть у нас есть некоторый неизвестный параметр , значение которого нужно оценить;

- введем случайную выборку чисел X из непрерывного распределения;

(5)

- выявим ее функция распределения F(x) и функцию плотности вероятности f(x);

- введем функцию правдоподобия, в виде произведения вероятностей (см. Формула (6)) [3];

(6)

- для дальнейшего удобства будем работать с натуральным логарифмом правдоподобия, так как с суммой легче работать, чем с произведением, и логарифм не меняет положением максимумов функции, что позволяет безболезненно ввести логарифм;

- решим задачу максимизации для

- на выходе получим формулу (7) для оценки неизвестного параметра, в нашем случае значений вектора w [3].

(7)

Свойства ММП [2]:

- состоятельность – при большом количестве наблюдений полученная оценка параметра будет стремиться к истинному значению параметра;

- асимптотическая нормальность – с ростом объема выборки оценки ММП лучше описываются нормальным распределением со средним равным истинному параметру и дисперсией равной величине обратной функции Фишера.

Третий метод, который может потенциально дать наилучшую оценку с меньшими техническими затратами – градиентный спуск. Идея метода заключается в том, что имея некоторое приближение к оптимальному значению неизвестного параметра, можно его улучшить, посчитав градиент функции потерь в точке и сдвинуть вектор весов в направлении антиградиента [1].

Градиент функции в точке направлен в сторону её наискорейшего роста, а антиградиент в сторону наискорейшего убывания. Математически градиент функции можно посчитать, вычислив частные производные функции. Формульное описание идеи представлено ниже (см. формула 8 и формула 9) [1].

(8)

где  – это темп обучения, который регулирует величину шага в направлении антиградиента.

 – функция потерь.

В рамках решения задачи поиска оптимальных весов параметров этот метод можно применить к функции потерь задачи, а именно формуле (6). Соответственно метод будет искать минимум функции потерь – скорее локальный, но в некоторых рассматриваемых случаях может и глобальный. В задаче, которая описана в этой работе, будет рассматриваться градиент евклидовой нормы (см. Формула 9) [1].

(9)

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

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

Для борьбы с мультиколлинеарностью обычно используется ряд методов, однако один из самых популярных – регуляризация, методы которой могут применяться не только в модели линейной регрессии, но и других, а также других задач. Идея метода заключается в наложении штрафов (ограничений) на вектор параметров (весов) [3].

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

Второй метод – L2 регуляризация, который призван уменьшать веса параметров равномерно, а значит модель будет менее консервативной. Если использовать данный регуляризатор, то оптимизационная задача прверащается в ту же задачу, но с ограничением на L2 норму.

Новая постановка задач с учетом L1 и L2 регуляризаторов будет отображена в формуле (10) и формуле (11) [3].

	(10)
	(11)

где  – гиперпараметр (коэффициент регуляризации),

Параметр  отвечает за то, насколько сильная регуляризация будет проводиться. Если он большой, то регуляризация сильная и модель будет более простой, меньше переобучаться, больше недообучаться, и наоборот. Данный параметр стоит подбирать.

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

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

Деревья решений

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

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

Определение самого решающего дерева можно сформулировать следующим образом:

Пусть задано бинарное дерево, в котором:

- каждой внутренней вершине v приписан предикат . Формула предиката изображена ниже [2];

(12)

где t – пороговое значение;

- каждому листу приписан прогноз  где Y – область допустимых значений целевой переменной.

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

Деревья решений обладают, как положительными качествами, так и отрицательными. Например, деревья решений имеют хорошую обобщающую способность, однако при этом они плохо экстраполируют зависимости за границы области допустимых значений целевой переменной. Построенная функция дерева решения является кусочно-постоянной, из-за чего производная равна 0 везде, где задана. Деревья решений хорошо описывают зависимости на обучающей выборке, однако могут дать плохой прогноз на тестовой выборке. Это происходит из-за того, что деревья могут разрастись до того момента, когда в листьях останется по 1 наблюдению и таких листьев будет много, что вызовет переобучение, то есть деревья на обучении идеально подстроятся под обучающий набор данных, однако это плохо для дальнейшего прогнозирования, так как большое количество листьев с одним наблюдением говорит о плохой обобщающей способности дерева. Именно поэтому при обучении стоит использовать некоторые регуляризации специфические конкретно для деревьев, чтобы сохранять хорошую обобщающую способность, например [2]:

- ограничивать глубину дерева;

- ограничивать минимальное количество объектов в листе;

- ограничивать минимальное количество объектов в узлах для дальнейшего разделения и т.д.

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

Подбор критерия ветвления также является подзадачей построение дерева решений. Сам процесс подбора можно описать так [2]:

- пусть у нас есть ответы дерева: , где ;

- пусть задана некоторая функция потерь ;

- при поиске оптимального разбиения узла нам надо вычислить для некоторой подвыборки, которая попала в узел, константу «c», которая смогла бы минимизировать среднее значение функции ошибки. Принято, что оптимальное значение этой величины равно [2]:

(13)

где  – подвыборка, которая попала в узел m дерева решений;

 – информативность узла.

Для дерева решений глубины 1 такая метрика будет равна следующему (см. Формула 14) [2].

(14)

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

(15)

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

Случайный лес

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

В качестве базового алгоритма в случайном лесе как раз используются деревья решений, чьи предсказания усредняются для получения итогового прогноза. Модель будет описана в формуле (16) [2].

(16)

где a(x) – модель, усредняющая предсказания базовых алгоритмов;

 – базовый алгоритм (дерево решений).

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

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

Алгоритм построения случайного леса довольно прост [2]:

1.               Определим для начала, сколько базовых алгоритмов хотим обучить – пусть оно равно N, где .

2.               Для каждого n из N:

1. сгенерируем выборку  при помощи бутстрапа;
2. построим решающее дерево  по выборке ;
3. по заданному критерию выбираем лучший признак для деления, делаем разбиение в дереве по нему и так до исчерпания выборки;
4. дерево строится, пока в каждом листе не более k объектов и пока не достигнем максимальной глубины дерева;
5. при каждом разбиении сначала выбираем m случайных признаков из исходных и оптимальное разделение выборки ищем среди них.

3.               Получаем предсказание ансамбля на объекте из тестовой выборки, усредняя отдельные ответы деревьев.

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

Градиентные модели

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

Первая из моделей – модель градиентного бустинга над деревьями решений, а именно xgboost [5]. Идея модели состоит в том, что в ней задействована идея градиентного спуска со смещением в сторону антиградиента, однако градиентный бустинг использует лишь задумку градиентного спуска, а именно градиентный бустинг заключается в итеративном построении моделей, которые на каждой итерации текущий алгоритм пытается сократить ошибку текущего ансамбля. Внутри самого алгоритма могут быть заложены различные базовые модели – деревья решений, линейные модели т.д., однако на практике используют именно градиентный бустинг над решающими деревьями, так как сумма линейных регрессий – это линейная регрессия [1].

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

Алгоритм градиентного бустинга сформулируем следующим образом [1]:

1.               Пусть у нас есть некоторая функция ошибки – L (y, x).

2.               Для реализации алгоритма градиентного бустинга возьмем K базовых алгоритмов – деревьев решений и построим из них ансамбль (см. Формула 33).

(17)

3.               Тогда функция ошибки будет выглядеть следующим образом для примера с среднеквадратическим отклонением:

(18)

Сам алгоритм будет состоять соответственно из K итераций, где на каждой итерации обучается новый алгоритм. Приведем пример для первой итерации, а далее все будет только повторяться до обучения K-го алгоритма [1].

1.           Обучим алгоритм , который будет лучше всего приближать целевую функцию (см. Формула 35). По сути, получаем предсказания первого базового алгоритма.

(19)

2.               Посчитаем отклонение предсказаний алгоритма от истинных значений целевого признака (см. Формула 20). Формула (21) – общий вид [1]:

	(20)
	(21)

где - градиент функции потерь.

3.           Скорректируем  с помощью , чтобы  предсказывал уже не сами значения целевого признака, а ошибки первого базового алгоритма, а именно  (см. Формула 22). Формула (23) – общий вид [1].

	(22)
	(23)

4.               Далее просуммируем два алгоритма и получим новый ансамбль (см. Формула 24). Ожидаем, что новый ансамбль  будет лучше предсказывать целевую переменную. Таким способом и будет обновляться композиция на каждой итерации [1]:

(24)

где  – вес или значимость каждого базового алгоритма в ансамбле. В коде обычно задается в виде learning_rate.

5.               Далее будет проведено дополнительно K-1 итерации, начиная с формулы (36) и в итоге на выходе будет получен итоговая модель, которая будет давать наилучший прогноз целевой переменной. На K-ом шаге будет получен K-ый алгоритм – итоговая модель (см. Формула 25) [1].

(25)

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

Второй алгоритм, который относится к семейству градиентных – это LGBM (light gradient boosting machine) [4]. Идея и сам алгоритм реализации метода схожи с предыдущим рассмотренным алгоритмом, однако есть ключевая разница: LGBM модель по-другому строит деревья. Об этом будет сказано немного позже. Также LGBM модель обучается намного быстрее и менее требовательна к затрачиваемым ресурсам нежели xgboost.

Почему LGBM быстрее? Ответ кроется как раз в обучении деревьев. В отличии от xgboost модель LGBM при построении деревьев проводит неполное разбиение всех узлов, а выбирает только те узлы для разбиения, которые сильнее сокращают значение функции ошибки. Соответственно деревья, которые строит модель LGBM, получаются несимметричными и более глубокими, что сокращает время и количество вычислений. Также LGBM использует меньше наблюдений и признаков в отличие от xgboost [4].

Модель отбирает только те наблюдения для обучения, чей градиент более высокий, так как это говорит о потенциале роста качества итоговой модели. Это происходит из-за того, что в градиентном бустинге градиент используется со знаком минус, а значит большие значения градиента помогут быстрее приблизиться к минимуму в формуле (25) [4]. Этот способ помогает сократить количество наблюдений в обучении и тем самым ускоряет алгоритм. Сокращение признаков происходит за счет объединения взаимоисключающих признаков.

Вывод

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

Список литературы

1. Губко П.А., Елистратова Е.С., Учебник по машинному обучению от Яндекса; Ансамбли в машинном обучении и градиентный бустинг [Электронный ресурс]; - Режим доступа: https://education.yandex.ru/handbook/ml (дата обращения 20.03.24)
2. Синицин Ф.Г. Учебник по машинному обучению от Яндекса. Решающие деревья [Электронный ресурс]; - Режим доступа: https://education.yandex.ru/handbook/ml (дата обращения 14.03.24)
3. Синицин Ф.Г., Соколов А.Е. Учебник по машинному обучению от Яндекса. Линейный модели [Электронный ресурс]; - Режим доступа: https://education.yandex.ru/handbook/ml (дата обращения 10.03.24)
4. Сборник функций библиотеки lightgbm[Электронный ресурс] – Режим доступа: https://lightgbm.readthedocs.io/en/latest/index.html (дата обращения: 01.05.2024)
5. Сборник функций библиотеки xgboost [Электронный ресурс] – Режим доступа: https://xgboost.readthedocs.io/en/stable/parameter.html (дата обращения: 01.05.2024)