Незадача коммивояжера и красный октябрь07.11.2017 14:47

Главнокоммивояжер Аристарх стоял у окна и с лёгкой грустью во взгляде провожал стаю улетающих на юг комаров. Осень. Конец сезона. Пора дубинки, полюбившиеся жителям города Н в качестве средства самозащиты от кровососов и предмета статуса (известно, некусаный горожанин — милее надкушенного), забирать из оружейных лавок и завозить на их место рогатины от снежных троллей.

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

Лето жаркое выдалось, потому сезон затянулся — мысль поселилась в голове Аристарха — годовой ритм миграции крылатых определенно укладывался в какие-то предопределённые природой рамки. А что если между продажами и погодой есть эта, как её, корреляция?

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

Посыл был понятен — связать деньги М с погодой W.

Здесь и далее важные признаки будем обозначать большими веселыми буквами.

Есть ли у нас план? Разумееся, план у нас есть:

Постановка незадачи коммивояжера
Природа данных
Механика продаж
Вот та корреляция, которую так ждал Аристарх
Модель Т
Продаем модель продавцам
Сделал, запустил — улучшай
Величина неравенства лавочников (закон Парето) — пара бесконечных моментов
Меряй лавочников Герцами
Памятка воспроизводителю
Разбор полетов или грабли коммивояжера

У нас было 54 месяца продаж команды из 400 человек в 30000 торговых точек. Данные в сводных таблицах ежемесячного отчёта о продажах продуктов по дням — для каждой точки продаж. Из них восстановили позиции транзакций — заказы отдельных продуктов с уникальной датой (здесь мы приняли допущение о том, что в один день клиентом размещался один заказ).

Продажи дубинок по неделям демонстрируют сезонный характер спроса — в конце сентября (36 неделя) сумма обязательств по возвратам (упрощая, возврат — это заказ со знаком минус) превышает поступления от продаж. Конец сезона приходит.

Масштаб бедствия — треть бизнеса дубинок

А что если между продажами и погодой есть эта, как её, корреляция? Ответить на поставленный вопрос нам помогут записи о погоде. История централизованного сбора метеорологических наблюдений со всей планеты национальной администрацией США тянется с начала прошлого века, наиболее полные данные доступны с 70-х. Один из источников, доступных для личного или академического использования — GSOD. Имея данные продаж в указанном интервале, мы можем проверить гипотезу графически.

Продажи измеряем в деньгах и штуках, а погоду?

Меряют погоду в Кемерово точно так же, как и в Аделаиде — эти методы стандартизированы международным сообществом. Полный список официальных станций по странам-участникам всемирной метеорологической организации содержит уникальные идентификаторы (например, аэропорт в Аделаиде имеет WMO_ID = 94672, а для Кемеровского центра по гидромеорологии и мониторингу окружающей среды WMO_ID = 29642), по которым можно искать записи в архивах. Специальное оборудование постоянно находится в психрометрической будке на высоте 2 м над землей — сотрудники станций используют лестницы для сбора показаний приборов.

Непростой это труд — производить замеры с частой 2 часа для следующих показателей:

T — температура воздуха, 2 м над землей,
P — давление воздуха (мм рт. ст.), приведенное к уровню моря,
U — относительная влажность, 2 м над землей,
Ff — скорость ветра, 10–12 м над землей, средняя за 10 минут,
Tn — минимальная температура за последние 12 часов,
Tx — максимальная температура за последние 12 часов,
Td — точка росы,
Tg — минимальная температура поверхности почвы ночью.

Как говорится, каждому — свое

Метеорологи — наблюдения делают, коммивояжеры — продажи. Транзакции — фиксируют заказы.

Предположительно, хороший коммивояжер следует процедуре и маршруту — жесткие временные ограничения обязывают. Хорошо, когда коммивояжеров много и эксклюзивных. Но не сейчас. В нашей ситуации торговые представители наняты дистрибьютором. Мы разбираем данные продаж дистрибьюторов в торговые точки — Sell-Out.

В принципе, и это является лучшей практикой, хорошо бы вести записи деятельности коммивояжеров. Как-то раз мы меряли каждого десятого из почти двух тысяч — следом за торговым представителем неделю ходил с секундомером супервайзер. Я потом эти замеры обрабатывал. Дело давно было и процесс измерений был следующий: неотступно следуя за коммивояжером, его непосредственный руководитель замерял все этапы визита и делал записи в блокноте. В конце смены, в региональном офисе, вносил в таблицу и отправлял нам. Тогда заметно выделялись два региона — качество данных (полнота, смещения колонок) требовало чистки. Две недели эксперимента пролетели в легкой суматохе — каждый супервайзер померял двоих коммивояжеров. Поинтересовался потом у руководителя проекта о успешности продаж в тех регионах — оказалась мала. С тех пор правило завел мерять шансы на успех коммивояжеров чистотой данных. Наш случай — где-то посредине.

Данные собираются из транзакций, которые вводят коммивояжеры в мобильные устройства и в них хватает мусора — заниматься приведением адресов в человеческий вид и к геокодам было влом (я посоветовал Аристарху решить задачу, пригласив стажера в интересный проект на роль junior monkeyjobber) и здесь стоит порекомендовать главнокоммивояжерам: 1) задуматься о автоматизации ввода и 2) беречь данные клиентов, тем более — адресные — вдруг вот открытки на новый год захочется отправить всем, а на почте получится конфуз.

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

Кратко о механике взаимодействия участников рынка в потребительских продуктах. Товары добираются к потребителям через цепочку посредников. Производители (Р1 и Р2) конкурируют на каждом шаге и полка в магазине — последний рубеж. Обычно за внимание дистрибьюторов борется пара крупных поставщиков, мелкие никому не интересны и им приходится нелегко.
Различают три типа транзакций:

• Sell-In — от производителя дистрибьютору,
• Sell-Out — от дистрибьютора в точку продаж,
• Sell-Through — потребителю.

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

Изобразим поток денег и погоду

Динамика спроса на дубинки изменяется вместе со средней температурой за неделю. Конец сезона совпадает с началом похолодания. Это в общем по рынку — география продаж у нас 603 тысячи квадратных километров — осень в разное время проносится по городам и сёлам, поэтому возвратами и занимаемся 10 недель. По всей необъятной.

Почему средняя температура?

Минимализм. Лень. Выпендреж. Ну и личный опыт — люблю летом усесться с книжкой в саду, да вот незадача — комары. Отмахиваться дубинкой и читать одновременно получается не очень, поэтому и приходится от них то благовония жечь, то фумигатор греть — методы суровые и от чтения отвлекают чуть менее сильно, чем кровососущие насекомые, а лучше сада летом места не сыскать, потому компромисс и неизбежен. Обратил раз внимание, что задержка между приходом вечерней свежести, когда пора накинуть толстовку и в капюшон укутаться, и исчезновением комаров составляет минут полчаса. Несколько дней подряд замерял температуру воздуха в это самое время — около 19°С проходит незримая граница, отделяющая приход комаров от сада. Так и родилась эвристика.

Кроме того, продажи действительно коррелируют с погодой. Только вот с ответом «корреляция Пирсона между возвратами и максимальной температурой за прошедшие 12 часов составляет 0.676722» я бы к главнокоммивояжеру не пошел — не поймут.

Промежуточный вывод — мы рассмотрели историю операций возврата сезонных товаров из розницы на склады дистрибьюторам и очертили незадачу коммивояжера зависимостью продаж от состояния окружающей среды (температуры воздуха на уровне 2 м над землёй) в момент посещения магазина оным.

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

Много данных — простые модели сработают?

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

Модель Т

Композиция из скользящих окон и дерева. Размер окон выбран равным 3, 1, и 7 дням (в честь виндовз)

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

Кроме того, Новый Год GDPR к нам мчится и простые понятные модели растут в цене.

Из коробки точность предсказания — доля верных ответов — составляет 99%. Можно полагать, что такой интерпретатор прогноза погоды будет вносить минимальные искажения.

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

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

Как подать такую модель бизнесу?

Я полагаю, успех продуктов, построенных с использованием машинного обучения, зависит от привычности звучания вопросов для людей. Задача бинарной классификации, которую мы только что решили, отвечает на вопрос: «Что произойдет в заданных условиях?» — это позволяет трактовать обещания синоптиков для каждого дня в отдельности.

Перефразируя вопрос, придем к более удобному ответу (и рассказу).

У нас есть модель конца сезона, она обучается на данных продаж и затем мы ей задаём вопрос: «Сколько из 10 следующих дней мы будем продавать, исходя из метеосводки?»

Ответ нанесем на карту местности, закодировав значение цветом: 10 соответствует британский гоночный зелёный, что должно ассоциироваться с хорошим состоянием дел; 0 обозначим бордовым, что у подготовленного читателя должно вызвать бурную гамму чувств. Неопределенность ответа 5 выражена отчётливо контрастирующим с фоном канареечным оттенком.

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

Цветовое кодирование оставляет размер точки на карте свободным для выражения ещё одной идеи — это может быть как просто исторический объем бизнеса, так и решение задачи регрессии — прогноз продаж, о котором мы ещё поговорим.

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

* * *

Сцена вторая

В которой мы разлагаем спектр клиентов методом анализа частоты посещения и повышаем точность модели Т на порядок.

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

Меня зовут Вадим Сафронов и я инженер поддержки коммивояжера SAP — presales engineer.

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

А что если не все лавочники одинаково милы?

Величина неравенства клиентов достаточно точно описывается элегантной формулой:

Закон Парето — вероятность события больше х пропорциональна степени х, γ обычно от 2 до 3.

Сеть дистрибуции — все вместе взятые цепочки дистрибьютор-коммивояжер-лавка — обладает свойствами моделей малого мира. Это ожидаемо, ведь продажи — это отношения между людьми и динамика системы подобна таковой в прочих социальных сетях. Теория графов дает инструменты, позволяющие описать происходящее. Рассмотрим пару популярных и известных руководителям концепций. Длинный хвост (long tail) и удорожание сверхдостижений (diminishing returns) — малая часть клиентов создает большую долю операций и прибыли и непропорциональное увеличение затрат — штраф за перфекционизм (или плата за высоту уровня).

Почему вообще графы?

Идея управления отношениями с клиентами, предполагает связи между бизнес-партнерами (центральная сущность в мире SAP CRM). Сетевой эффект в потребительских товарах наблюдается как в размере бизнеса с клиентами, так и в популярности продуктов. Описывая цепочки отношений и отображая их ребрами в графе, где узлами будут бизнес-партнеры мы получаем новую структуру данных, позволяющую интересные преобразования и вычисления, например, Page Rank. О практическом соответствии частоты посещения коммивояжером лавки вероятности нахождения в ней в случайный момент времени и ожидаемой эргодичности коммивояжера можно провести увлекательный сравнительный эксперимент. (отмазка: виденные ранее данные уже невозможно и запрещено использовать — как будет что годное для открытого анализа — запилю)

Много, очень много задач из жизни коммивояжера решаются на графах. И это прекрасно. Например, привычная 80/20 пропорция между операциями — насколько применима?

Традиционная статистика вся построена на центральной предельной теореме, предполагающей независимость между отдельными точками данных в изучаемой выборке. Закон Парето, наоборот, предполагает тесную взаимосвязь между элементами в системе — характерное качество сетевых структур. Объяснение динамики формирования такого сильно скошенного влево распределения с тяжелым хвостом (модель предпочтительного присоединения) первым предложил Барабаси: когда есть выбор и возможность установить приоритет действия — динамика процесса будет не-пуассоновской. Например, если сеть растет и новые узлы формируют связи с уже существующими, предпочитая присоединяться к наиболее связанным с вероятностью р, либо случайно выбирая соседа с вероятностью 1-р. В зависимости от значения параметра, полученный граф является случайным (модель Эрдоша-Рейни) при р=0, либо демонстрирует присущие моделям малого мира малый диаметр (длина максимального кратчайшего пути между двумя узлами), высокую кластеризацию (соседние узлы чаще соединены между собой, например, друзья друзей часто знакомы).

Примечательным свойством закона Парето является вид графика функции — в двойной логарифмической шкале — это прямая. Вычисление параметра — показателя степени γ — задача, решенная не так давно (2007). До тех пор, пока подбор параметра был недоступен, просто строили график, да оценивали прямизну на глаз — значение γ влияет только на наклон графика. Сейчас для этого есть готовая библиотека powerLaw. Неспроста степенной закон — вторая тема в курсе Леонида Жукова в ВШЭ, которому за свободный доступ к материалам выскажу большое человеческое спасибо прямо здесь.

Практическая полезность закона Парето: 1) оптимизационные задачи решать удобно 2) в бизнес-школах учат, а вот это поважнее — говорить на языке бизнеса — это шанс быть понятым.

Тест кумулятивной степенной функции распределения: график в двойной логарифмической шкале.

Правило Парето близко к нашему случаю и 20% лавочников приносят 90% денег.

САМОЕ ВАЖНОЕ СЛЕДСТВИЕ:

В продажах понятие среднего не имеет смысла, так как дисперсия — бесконечна

Все еще оперируете «средним чеком»? Посмотрите лекцию о правиле Парето от Леонида Жукова (RU) или Юре Лесковека (EN) — там много интересного.

Практическое следствие — ранжирование базы клиентов.

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

Напомним, данные наши собой представляют позиции заказов, о которых известно: продукт, количество, клиент, коммивояжер, календарный день, координаты. Добавляем переменную Т — температуру окружающей среды — эти данные мы можем получить из открытых источников (GSOD).

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

Как меру частоты посещения — она позволит разложить спектр клиентов на разделимые множества — примем среднюю частоту визитов в Герцах.

Алгоритм

для каждого клиента (торговая точка):

измерим сумму транзакций — в деньгах или единицах товара (внешние факторы, вроде инфляции, могут снижать точность прогноза в нестабильной валюте).
Затем ранжируем все множество клиентов по полученному признаку и разделяем на равные корзинки. Выберем число корзин равным 10 и разобьем базу клиентов на децили. Назначим классам клиентов буквенные коды ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'], лучшие клиенты — корзинка А.
измерим частоту посещения коммивояжером.
Повторим шаг 2 для признака частота

Теперь поведение каждого из клиентов может быть описано частотным и денежным признаками и кодировано двухбуквенным кодом. Самый выгодный сегмент клиентов, АА.

Здесь мы видим заказы, обороты, и сегменты клиентов (сумма процентов может отличаться от 100 из-за округления). Присмотримся к областям, окрашенным в британский гоночный зеленый — здесь и далее этот оттенок подчеркивает оптимизм ожиданий — легко видеть, что сегмент АА производит почти половину прибыли — всего 3% от клиентской базы.

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

Повышение качества прогноза на порядок — ощутимо! Ценой сравнительно простого вычисления частоты посещения лавки коммивояжером мы добились 99.9% доли верных ответов классификатора. Теперь можем расширить диапазон вопросов к модели и получать ответы на: «Сколько из 10 последующих дней наши самые выгодные клиенты будут покупать?» или «Когда этот клиент перестанет покупать?» — благодаря учету поведения клиентов.

Итоговая модель Т + F

В данном упражнении мы:
1) Определили незадачу коммивояжера
2) Рассмотрели способ ее решения и улучшения
3) Предложили средства измерения и контроля

Что дальше делать?

Главнокоммивояжер склонился над картой. Заря заливалась на севере. Куда бежать уже было понятно — к самым милым лавочникам. А вот сколько телег для дубинок с собой брать? Явление — теперь предсказуемое, диктовало одно — пришло время мерять незадачу коммивояжера. Мурлыкая себе под нос что-то о ланитах и блеске Авроры, Аристарх удалился в опочивальню.

* * *

Памятка воспроизводителю

Перцовый вазелин придает поцелуям на морозе огня, научно-популярный коллаж, 2017

Привет, воспроизводитель!

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

Кроме того, разыскивается самый главнокоммивояжер.

Анналы истории:

— Аристарх зафиксировал 54 месяца в 37 тысячах лавок, измерил незадачу в 17 категориях и поделился данными города Н, а кроме того — изменил способ целеполагания для дистрибьюторов — теперь с учетом поведения лавочников. (2017)
— Анонимный главнокоммивояжер зафиксировал 30 месяцев в 34 тысячах лавок в 7 категориях и отсортировал лавочников по милости и еще чему. (2016)
— Главнокоммивояжер — знакомый знакомого за ужином поделился методом добычи данных из дистрибьюторов и лавочников. (2014)
— Заместитель главнокоммивояжера рассказала, почему дистрибьюторы не любят открывать свои дела с лавочниками. Именно эта удивительная способность добыть данные операций партнеров в сети дистрибуции и отличает главнокоммивояжера от кого попало. (2007)

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

Дерзай!

* * *

Разбор полетов или грабли коммивояжера

Здесь место повстречавшимся техническим и организационным незадачам:

— Жаба задавила купить данные погоды для тестов и теперь не знаем, насколько прогноз из одного источника согласуется с архивом другого. Похоже, придется покупать. (UPD: теперь уже знаем — около десяти дней разброс и если карта красная, то, скорее всего, уже возвраты идут)
— Бывает так, что на рынке нет единой, либо стандартной платформы для работы дистрибьюторов (бывает, что и есть — Аристарху повезло, не то что анонимному главнокоммивояжеру). В результате у партнеров внедрены разные информационные системы и модели данных — ETL становится в 30 раз интереснее.
— Задержки ввода и передачи данных уничтожают временные ряды — худший из встреченных дистрибьюторов отчитывался раз в месяц.

* * *

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

(вот тот код, который делает все описанное)