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

Постановка задачи


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

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

Метод решения задачи


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

$$display$$R_{prod}=\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$$


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

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

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

Разница в результатах прогнозирования разными методами есть, но, на первый взгляд, небольшая (проверялась при окне $inline$kernel_H=3.0$inline$, коэффициенте расстояния магазинов $inline$K_{shops}=1.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;
}


Ссылки


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

Комментарии (5)


  1. ChePeter
    23.05.2018 17:13

    Все физики, особенно из крутых вузов, МФТИ, МГУ, убеждены, что если принять для простоты, что все люди одинаковы, как электроны и все районы одинаковы, как дырки в полупроводниковом переходе — то все крутейшие методы их науки будут успешно применяться на человеческих сообществах.
    Только вот товар, успешно продающийся на Остоженке ( это золотая миля Москвы), скорее всего не будет продаваться также успешно в Капотне ( там жилой район рядом НПЗ).
    Я не считаю ни один район Москвы плохим, в каждом достойные люди живут, но различия в доходах уже видны невооруженным взглядом.


    1. Matshishkapeu
      24.05.2018 23:22

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


  1. Kobalt_x
    23.05.2018 17:15

    Исходный код лучше выложить на github/bitbucket. И в чём приокл реализации ядерной регрессии именно на C++, честно говоря, неясно


  1. panchmp
    24.05.2018 20:53

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


    1. SunZi Автор
      24.05.2018 23:27

      panchmp, Kobalt_x: Задача тестовая. Ограничения на применение инструментов были выставлены условиями задачи. Обязательств по ее нераспространению не налагалось :)