Using nuclear regression to forecast demand in chain stores
Good day, dear habrovchane! In this publication, we will discuss the model of forecasting demand for goods in chain stores and its implementation in C ++.
Suppose we have a network of stores, in each of which goods are delivered. Products (for the forecast model) fall into each store in an arbitrary way. For a certain period of time, we have statistics on how many goods in each store are sold. It is required to predict the sale of goods for a period of time, similar to the selected one, for all stores for all goods that were not imported into them.
The problem is solved using the nuclear regression method (using the Nadaraya-Watson formula). The kernel function is a quadratic kernel function with a window width. $ inline $ kernel_H $ inline $ .
"Distance" between products with different prices is considered as:
The "distance" between the two stores is considered as the product of the manually specified ratio. $ inline $ K_ {shops} $ inline $ and negative decimal logarithm of weighted correlation. The weighted correlation is calculated as the product of the ratio of the number of types of goods in both stores to the total number of types of goods (weight of "likelihood") and the correlation of the quantities of goods sold (those that are common to these stores):
The distance between two products in two different stores is counted as the root of the sum of the squares of the distances between the given goods and between these stores.
')
The manually set factor for the “distance” between two stores together with the specified window width allows to take into account the “distance” between goods and stores in the proportion we need.
I programmed two prediction methods. The “common” method takes into account all the goods sold in all stores. The "cross-shaped" method takes into account all the goods sold in the current store and the quantities of projected items sold in other stores.
There is a difference in the prediction results by different methods, but, at first glance, it is small (checked at the window $ inline $ kernel_H = 3.0 $ inline $ shopping distance factor $ inline $ K_ {shops} = 1.0 $ inline $ on the matrix 20 stores * 20 products). In this case, with large windows of the kernel function, the second method is much faster than the first.
Statistics is a table in which the quantities of goods sold are recorded (the columns correspond to the goods, the rows to the stores). If the goods did not enter the store, the "-1" is located in the corresponding cell of the table. For convenience, the first row of the table shows the prices of goods.
KV Vorontsov. Lectures on regression recovery algorithms.
Formulation of the problem
Suppose we have a network of stores, in each of which goods are delivered. Products (for the forecast model) fall into each store in an arbitrary way. For a certain period of time, we have statistics on how many goods in each store are sold. It is required to predict the sale of goods for a period of time, similar to the selected one, for all stores for all goods that were not imported into them.
Notes and Assumptions
- The goods delivered to the stores did not end during the period of statistics collection.
- If new goods are brought to the store (while old goods remain), sales are not redistributed between old and new goods. Statistics on old products will remain the same, just someone additionally buys new products. Forecasting if this condition is not met will require additional data on how demand is saturated with an increase in the quantity of goods.
- The period for which statistics were collected, and the period for which you need to make a forecast, are identical in demand.
Method for solving the problem
The problem is solved using the nuclear regression method (using the Nadaraya-Watson formula). The kernel function is a quadratic kernel function with a window width. $ inline $ kernel_H $ inline $ .
"Distance" between products with different prices is considered as:
$$ display $$ R_ {prod} = \ left | log_ {10} \ left (\ frac {price_1} {price_2} \ right) \ right | $$ display $$
The "distance" between the two stores is considered as the product of the manually specified ratio. $ inline $ K_ {shops} $ inline $ and negative decimal logarithm of weighted correlation. The weighted correlation is calculated as the product of the ratio of the number of types of goods in both stores to the total number of types of goods (weight of "likelihood") and the correlation of the quantities of goods sold (those that are common to these stores):
$$ 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 $$
The distance between two products in two different stores is counted as the root of the sum of the squares of the distances between the given goods and between these stores.
')
The manually set factor for the “distance” between two stores together with the specified window width allows to take into account the “distance” between goods and stores in the proportion we need.
I programmed two prediction methods. The “common” method takes into account all the goods sold in all stores. The "cross-shaped" method takes into account all the goods sold in the current store and the quantities of projected items sold in other stores.
There is a difference in the prediction results by different methods, but, at first glance, it is small (checked at the window $ inline $ kernel_H = 3.0 $ inline $ shopping distance factor $ inline $ K_ {shops} = 1.0 $ inline $ on the matrix 20 stores * 20 products). In this case, with large windows of the kernel function, the second method is much faster than the first.
Source
Statistics is a table in which the quantities of goods sold are recorded (the columns correspond to the goods, the rows to the stores). If the goods did not enter the store, the "-1" is located in the corresponding cell of the table. For convenience, the first row of the table shows the prices of goods.
Header file of data storage class 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 data storage class source file
#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 } Header file of the distance calculation class 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 distance calculation class source file
#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 forecast calculation class header file
#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 distance calculation class source file
#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; } Links
KV Vorontsov. Lectures on regression recovery algorithms.
Source: https://habr.com/ru/post/359170/
All Articles