Главная » Хабрахабр » [Из песочницы] Использование ядерной регрессии для прогноза спроса в сетевых магазинах

[Из песочницы] Использование ядерной регрессии для прогноза спроса в сетевых магазинах

Доброго времени суток, уважаемые хабровчане! В данной публикации речь пойдет о модели прогноза спроса на товары в сетевых магазинах и ее реализации на C++.
Допустим, у нас имеется сеть магазинов, в каждый из которых завозят товары. Товары (для модели прогноза) попадают в каждый магазин произвольным образом. За некий период времени мы имеем статистику — сколько в каждом магазине продано тех или иных товаров. Требуется спрогнозировать продажи товаров за период времени, аналогичный выбранному, для всех магазинов по всем товарам, которые в них не завозились.

Примечания и допущения постановки задачи

  • Товары, завезенные в магазины, не заканчивались за период сбора статистики.
  • Если в магазин завезли новые для него товары (при том, что старые товары остались), продажи не перераспределяться между старыми и новыми товарами. Статистика по старым товарам останется прежней, просто кто-то дополнительно покупает новые товары. Прогнозирование при невыполнении этого условия потребует дополнительных данных о том, как насыщается спрос при увеличении количества товаров.
  • Период, за который собирали статистику, и период, для которого нужно сделать прогноз, идентичны по спросу.

Задача решается с помощью метода ядерной регрессии (используя формулу Надарая-Ватсона). В качестве функции ядра используется квадратическая ядерная функция с шириной окна $inline$kernel_H$inline$.
«Расстояние» между товарами с разной ценой считается как:

$$display$$R_=\left|log_{10}\left(\frac{price_1}{price_2}\right)\right|$$display$$

«Расстояние» между двумя магазинами считается как произведение задаваемого вручную коэффициента $inline$K_{shops}$inline$ и отрицательного десятичного логарифма взвешенной корреляции. Взвешенная корреляция вычисляется как произведение отношения количества типов товаров, которые есть в обоих магазинах к общему количеству типов товаров (вес «правдоподобия») и корреляции количеств проданных товаров (тех, которые общие для этих магазинов):

$$display$$Weight_{shops}=\frac{N_{1,2}}{N_{total}}$$display$$

$$display$$R_{shops} = - K_{shops} \cdot log_{10} \left( Correlation_{shops} \cdot Weight_{shops} \right) $$display$$

Расстояние между двумя товарами в двух разных магазинах считается как корень из суммы квадратов расстояний между данными товарами и между данными магазинами.

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

«Общий» метод учитывает все проданные товары во всех магазинах. Я запрограммировал два метода прогнозирования. «Крестообразный» метод учитывает все проданные товары в текущем магазине и количества проданных прогнозируемых товаров в других магазинах.

0$inline$, коэффициенте расстояния магазинов $inline$K_{shops}=1. Разница в результатах прогнозирования разными методами есть, но, на первый взгляд, небольшая (проверялась при окне $inline$kernel_H=3. При этом, при больших окнах функции ядра второй метод значительно быстрее первого. 0$inline$ на матрице 20 магазинов * 20 товаров).

Статистика представляет собой таблицу, в которой записаны количества проданных товаров (столбцы соответствуют товарам, строки — магазинам). Если товар не поступал в магазин, в соответствующей ячейке таблицы располагается "-1". Для удобства в первой строке таблицы указаны цены товаров.

Заголовочный файл класса хранения данных DataHolder.h

#pragma once
#include <memory> class DataHolder
{
protected: // prices vector std::vector<int> prices; // mask of initial data: 1 if has init and 0 if not std::vector<std::vector<bool>> maskData; // initial data matrix std::vector<std::vector<int>> initData; // full data matrix (with prognosis) std::vector<std::vector<int>> fullData; public: DataHolder() {} virtual ~DataHolder() {} // Load init data from csv file // calculate range between shops // @param filename - file path of loading data void loadData(std::string filename); // Save full data in csv file // @param filename - file path of saving data void saveData(std::string filename);
};

Исходный файл класса хранения данных DataHolder.cpp

#include "DataHolder.h" void DataHolder::loadData(std::string filename)
{ // Here is loading data from filename to initData fullData = initData;
} void DataHolder::saveData(std::string filename)
{ // Here is saving data from fullData to filename
}

Заголовочный файл класса расчета расстояний Prognoser.h

#pragma once
#include <math.h>
#include <numeric>
#include "DataHolder.h"
class RangeCalculator : public DataHolder
{ friend class Prognoser;
private: // count of shops int shopsCount; // count of products int productsCount; // marix of range squares between prices std::vector<std::vector<double>> priceRanges; // marix of range squares between shops std::vector<std::vector<double>> shopsRanges; // sums of earn of shops std::vector<long> shopEarnSums; public: RangeCalculator() {} virtual ~RangeCalculator() {} // calculate ranges and advanced parameters void calculateRanges();
private: // calculate and fill priceRanges void fillPriceRanges(); // calculate and fill shopsRanges void fillShopsRanges(); // calculate range between shops // @param i - first shop index // @param j - second shop index double calculateShopsRange(int i, int j); // calculate earnings of shop // @param i - shop index double calculateShopEarnings(int i); // calculate shopEarnSums void calculateShopEarnSums(); // calculate range between different shops // @param i - first shop index // @param j - second shop index double calculateShopsRangeByCorrelation(int i, int j); // calculate correlation between two vectors double calculateCorrelation(const std::vector<int> &X, const std::vector<int> &Y);
};

Исходный файл класса расчета расстояний Prognoser.cpp

#include "RangeCalculator.h" void RangeCalculator::calculateRanges()
{ shopsCount = initData.size(); productsCount = initData[0].size(); calculateShopEarnSums(); fillPriceRanges(); fillShopsRanges();
} void RangeCalculator::fillPriceRanges()
{ // initialize vector priceRanges.resize(productsCount); for (int i = 0; i < productsCount; ++i) priceRanges[i].resize(productsCount); // calculate and fill double range = 0, range2 = 0; for (int i = 0; i < productsCount; ++i) { priceRanges[i][i] = 0; for (int j = i + 1; j < productsCount; ++j) { range = log10((double)prices[i] / (double)prices[j]); range2 = range * range; priceRanges[i][j] = range2; priceRanges[j][i] = range2; } }
} void RangeCalculator::fillShopsRanges()
{ // initialize vector shopsRanges.resize(shopsCount); for (int i = 0; i < shopsCount; ++i) shopsRanges[i].resize(shopsCount); // calculate and fill double range = 0, range2 = 0; for (int i = 0; i < shopsCount; ++i) { shopsRanges[i][i] = 0; for (int j = i + 1; j < shopsCount; ++j) { range = calculateShopsRange(i, j); range2 = range * range; shopsRanges[i][j] = range2; shopsRanges[j][i] = range2; } }
} double RangeCalculator::calculateShopsRange(int i, int j)
{ if (i != j) { return calculateShopsRangeByCorrelation(i, j); } else return 0;
} double RangeCalculator::calculateShopsRangeByCorrelation(int i, int j)
{ // collects products of shops, that are in both shops std::vector<bool> maskX = maskData[i]; // mask of products in first shop std::vector<bool> maskY = maskData[j]; // mask of products in second shop std::vector<bool> maskXY(productsCount); // mask of products in both shops for (int k = 0; k < productsCount; ++k) maskXY[k] = maskX[k] * maskY[k]; // count of products in first shop int vecLen = std::accumulate(maskXY.begin(), maskXY.end(), 0); // weight of correlation calculation double weightOfCalculation = (double)vecLen / (double)productsCount; // calculating X and Y vectors std::vector<int> X(vecLen); std::vector<int> Y(vecLen); int p = 0; for (int k = 0; k < productsCount; ++k) { if (maskXY[k]) { X[p] = initData[i][k]; Y[p] = initData[j][k]; ++p; } } // calculating range between shops double correlation = calculateCorrelation(X, Y); // correlation double weightedCorrelation = correlation * weightOfCalculation; double range = -log10(fabs(weightedCorrelation) + 1e-10); return range;
} double RangeCalculator::calculateCorrelation(const std::vector<int> &X, const std::vector<int> &Y)
{ int count = X.size(); double sumX = (double)std::accumulate(X.begin(), X.end(), 0); double sumY = (double)std::accumulate(Y.begin(), Y.end(), 0); double midX = sumX / (double)count; double midY = sumY / (double)count; double cor1 = 0, cor2 = 0, cor3 = 0; for (int i = 0; i < count; ++i) { cor1 += (X[i] - midX) * (Y[i] - midY); cor2 += (X[i] - midX) * (X[i] - midX); cor3 += (Y[i] - midY) * (Y[i] - midY); } double cor = cor1 / sqrt(cor2 * cor3); return cor;
} double RangeCalculator::calculateShopEarnings(int i)
{ double earnings = 0; for (int j = 0; j < productsCount; ++j) { earnings += prices[j] * initData[i][j]; } return earnings;
} void RangeCalculator::calculateShopEarnSums()
{ shopEarnSums.resize(shopsCount); for (int i = 0; i < shopsCount; ++i) shopEarnSums[i] = calculateShopEarnings(i);
}

Заголовочный файл класса расчета прогнозов Prognoser.h

#pragma once
#include "RangeCalculator.h" class Prognoser
{
private: // shared_ptr by RangeCalculator object std::shared_ptr<RangeCalculator> rc; // koefficient to multiply by shops ranges double kShopsR; // square of kernel window width double h2; public: // constructor // @param rc - shared_ptr by RangeCalculator object // @param kShopsR - koefficient to multiply by shops ranges // @param h - kernel window width Prognoser(std::shared_ptr<RangeCalculator> rc, double kShopsR, double h); virtual ~Prognoser(); // prognose all missing data // @param func_ptr - calculating of weighted sums function pointer void prognose(void (Prognoser::*func_ptr)(int, int, double&, double&)); // calculate weighted sums with "cross" method // @param shopInd - shop index // @param prodInd - product index // @param weightsSum - sum of weights // @param contribSum - weighted sum of contributions void calculateWeightSumsCross(int shopInd, int prodInd, double& weightsSum, double &contribSum); // calculate weighted sums with "total" method // @param shopInd - shop index // @param prodInd - product index // @param weightsSum - sum of weights // @param contribSum - weighted sum of contributions void calculateWeightSumsTotal(int shopInd, int prodInd, double& weightsSum, double &contribSum);
private: // calculate kernel // @param r2h2 - r*r/h/h, where r - range and h - window width double calculateKernel(double r2h2); // calculate prognosis of selected position with selected method // @param shopInd - shop index // @param prodInd - product index // @param func_ptr - calculating of weighted sums function pointer int calculatePrognosis(int shopInd, int prodInd, \ void (Prognoser::*func_ptr)(int, int, double&, double&));
};

Исходный файл класса расчета расстояний Prognoser.cpp

#include "Prognoser.h" Prognoser::Prognoser(std::shared_ptr<RangeCalculator> rc, double kShopsR, double h)
{ this->rc = rc; this->kShopsR = kShopsR; this->h2 = h * h;
} Prognoser::~Prognoser()
{} double Prognoser::calculateKernel(double r2h2)
{ if (r2h2 > 1) return 0; else return (1 - r2h2) * (1 - r2h2) * 15 / 16;
} void Prognoser::prognose(void (Prognoser::*func_ptr)(int, int, double&, double&))
{ for (int i = 0; i < rc->shopsCount; ++i) { for (int j = 0; j < rc->productsCount; ++j) { if (!rc->maskData[i][j]) { rc->fullData[i][j] = calculatePrognosis(i, j, func_ptr); } } }
} void Prognoser::calculateWeightSumsCross(int shopInd, int prodInd, double& weightsSum, double &contribSum)
{ double r2 = 0, r2h2 = 0, weight = 0; // calculate sums by shops for (int i = 0; i < rc->shopsCount; ++i) { if (rc->maskData[i][prodInd] && shopInd!=i) { r2 = rc->shopsRanges[shopInd][i]; r2 = r2 * kShopsR * kShopsR; r2h2 = r2 / h2; weight = 0 ? r2h2 >= 1. : calculateKernel(r2h2); weightsSum += weight; contribSum += weight * rc->initData[i][prodInd] * \ rc->shopEarnSums[i] / rc->shopEarnSums[shopInd]; } } // calculate sums by products for (int j = 0; j < rc->productsCount; ++j) { if (rc->maskData[shopInd][j] && prodInd != j) { r2 = rc->priceRanges[prodInd][j]; r2h2 = r2 / h2; weight = 0 ? r2h2 >= 1. : calculateKernel(r2h2); weightsSum += weight; contribSum += weight * rc->initData[shopInd][j]; } }
} void Prognoser::calculateWeightSumsTotal(int shopInd, int prodInd, double& weightsSum, double &contribSum)
{ double r2 = 0, r2h2 = 0, weight = 0; for (int i = 0; i < rc->shopsCount; ++i) { for (int j = 0; j < rc->productsCount; ++j) { if (i != shopInd || j != prodInd) if(rc->maskData[i][j]) { r2 = rc->shopsRanges[shopInd][i]; r2 = r2 * kShopsR * kShopsR; r2 += rc->priceRanges[prodInd][j]; r2h2 = r2 / h2; weight = 0 ? r2h2 >= 1. : calculateKernel(r2h2); weightsSum += weight; contribSum += weight * rc->initData[i][j] * \ rc->shopEarnSums[i] / rc->shopEarnSums[shopInd];; } } }
} int Prognoser::calculatePrognosis(int shopInd, int prodInd, \ void (Prognoser::*func_ptr)(int, int, double&, double&))
{ double weightsSum = 0; // sum of weights double contribSum = 0; // sum of weighted contributions //calculateWeightSumsCross(shopInd, prodInd, weightsSum, contribSum); (this->*func_ptr)(shopInd, prodInd, weightsSum, contribSum); int prognosis = -1; if (weightsSum > 0) prognosis = int(contribSum / weightsSum); return prognosis;
}

К. В. Воронцов. Лекции по алгоритмам восстановления регрессии.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Иди-ка ты на !@# со своей «токсичностью»

IT — не детский садик. Это место для взрослых, руководствующихся логикой и здравым смыслом. Их не надо опекать, не надо следить за словами, не надо переживать, что у них сформируются комплексы. Если человек некомпетентен, надо дать ему об этом явно ...

nomoregoogle.com — свежий сборник альтернатив сервисам технологического гиганта

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