В настоящее время Big Data становятся неотъемлемой частью личной и профессиональной жизни людей. Сегодня по-настоящему успешный бизнес уже немыслим без анализа данных, а в медицине различные
инструменты Data Mining используются повсеместно.
Данная работа стартовала с практической задачи профилирования
крупной московской сети ресторанов: необходимо было на основе информации о деятельности каждого из ресторанов сети выделить некую
специализацию каждого заведения – наборы наиболее востребованных
там блюд. Ранее решение данной задачи не было автоматизировано, и
её приходилось кропотливо решать вручную, что делало точный ответ
невозможным[2].
Задача, наиболее близкая к данной, – это Market Basket Analysis,
автором которой стал Rakesh Agrawal в 1993 году[1]. Она подразумевает выделение нестрогих правил, по которым клиенты, приобретающие
некий набор товаров, зачастую покупают что-то ещё в дополнение к
имеющимся покупкам. Правила такого вида именуются ассоциативными, а вероятность, с которой выбор одних товаров влечёт выбор других,
называется значимостью (confidence). Задача анализа продуктовой корзины являлась предпосылкой к появлению области ассоциативных правил, однако в дальнейшем этот инструмент начали использовать для
увеличения перекрёстных продаж (cross-sell)[5] и продаж с повышением цены (up-sell)[5], а также для более эффективной прямой адресной
рассылки рекламных предложений (direct mail)[10].
Основная часть любого алгоритма поиска ассоциативных правил состоит в поиске часто встречающихся наборов. При условии наличия
решения этой подзадачи, получение ассоциативных правил осуществляется тривиальным образом, в то время как сам поиск частых наборов вычислительно сложен. В действительности, проблема, к которой
сводится поиск ассоциативных правил, является гораздо более востребованной и применяется ещё и для задач классификации и прогнозирования, например, при диагностике заболеваний сердца[8].
Итак, в настоящей работе была решена актуальная на сегодняшний
день задача проведения сравнительного анализа алгоритмов поиска часто встречающихся наборов с целью выявления наиболее эффективного
из них. До появления данного исследования никто не проводил единовременного сравнения всех существующих алгоритмов в равных условиях.
Помимо этого, я сформировал методологию сравнительного анализа, которая может быть применена по отношению к любым эвристическим алгоритмам.
Важным итогом работы стало появление критерия выбора вычислительно оптимального алгоритма, исходя из характеристик исходных
данных. Этот результат может быть применён в любой задаче, использующей поиск часто встречающихся наборов. Одна из таких задач, положившая начало данному исследованию, была решена – я построил
профили заведений крупной сети ресторанов Coffeemania. Результаты
работы были внедрены в реальное предприятие.
