АЛГОРИТМЫ ПОИСКА АССОЦИАТИВНЫХ ПРАВИЛ ДЛЯ ИСПОЛЬЗОВАНИЯ В ЭЛЕКТРОННОЙ КОММЕРЦИИ

АННОТАЦИЯ

В статье рассказывается о поиске ассоциативных правил и его применении в электронной коммерции. Рассмотрены популярные алгоритмы: Apriori, ECLAT, FP-growth, FP-max.

Ключевые слова: поиск ассоциативных правил, популярный набор, транзакционная база данных, поддержка.

В электронной коммерции используется множество рычагов для увеличения продаж, так как именно прибыль является главной целью любого бизнеса. Одним из таких инструментов являются перекрестные продажи, которые не требуют дополнительных издержек в отличии от привлечения новых клиентов (по данным исследований, привлечь нового клиента от 5 до 25 раз дороже, чем удержать существующего) [1].

Перекрестные продажи или кросс-продажи — это предложение товара покупателю, который мог бы его заинтересовать в сочетании с уже приобретенным товаром. Данная стратегия может заметно увеличить прибыль компании. Так, например, 35% доходов Amazon приходится именно на перекрестные продажи [2].

Супермаркетам и предпринимателям малого и среднего бизнеса хорошо известно, что обычно в транзакции бывает не один товар, а группа товаров, и чаще всего между ними есть взаимосвязь. Для выстраивания связей между товарами используется метод анализа данных при обучении без учителя – поиск ассоциативных правил, который позволяет находить закономерность между связанными событиями. Ассоциативное правило имеет форму: если {предпосылка} ⇒ то {следствие}. То есть, если имеется выведенное правило, включающее в себя элементы x, y, z, то можно утверждать, что при наличии в транзакции элементов x, y – в нее будет включен с большой вероятностью и элемент z.

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

Поиском ассоциативных правил занимаются уже около тридцати лет, и за это время появилось множество алгоритмов, решающих данную задачу [3], и все они делятся на два подхода: «генерация кандидатов», который основан на свойстве нисходящего замыкания поддержки, и «наращивание шаблонов», который осуществляет поиск рекурсивно: база данных делится на части и идет поиск локальных ответов, которые и наращиваются до общего результата.

Для поиска ассоциативных правил в алгоритмах используется такое ключевое понятие как «поддержка» (support) – отношением транзакций, которые включают в себя элементы к общему числу транзакций:

        [4]

где  – это количество транзакций в наборе, в которой находятся все элементы множества B, а N – это количество всех транзакций в наборе.

В рамках данной статьи будут рассмотрены следующие алгоритмы: Apriori, ECLAT, FP-growth, FP-max.

Apriori – наиболее распространенный алгоритм поиска ассоциативных правил [5]. Алгоритм использует поиск в ширину и древовидную структуру хеширования для эффективного подсчета наборов элементов-кандидатов. Apriori ищет сначала все транзакции (которые подходят по заданной поддержке), содержащие один элемент, затем составляет из них пары по принципу «иерархической монотонности» (если x встречается часто и y также встречается часто, то [x, y] встречаются часто). Алгоритм является очень простым для понимания и для реализации, но общая эффективность может быть низкой из-за многократного «сканирования» датасета.

ECLAT (Equivalence CLAss Transformation) – данный алгоритм использует поиск в глубину (Depth-First Search) и основывается на пересечении множеств [6]. На первом подходе выявляются все частые itemsets, для этого генерируря пустое множество I. А после алгоритм вызывает сам себя, присваивая I+1 на кажом шаге до тех пор, пока не будет достигнута длина I. Префикс — это последовательность узлов, которые образуют путь, префиксное дерево (trie) используется для хранения значений, где нулевой корень дерева – это пустое множество I, и самая левая ветвь – child нулевого корня. Во время прохода по itemsets прописываются items в каждом itemsets. Количество ветвей равняется количества items в itemsets и itemset будет записан только один раз, именно поэтому ECLAT быстрее Apriori.

FP-growth (Frequent Pattern-Growth) – алгоритм, в основе которого при предобработке трназакционной базы данных, БД трансформируется в компактную Frequent-Pattern Tree (древовидная структура популярных наборов, при построении которой используется принцип «разделяй и властвуй» - декомпозиция сложных задач на простые). Такая трансформация позволяет эффективно и полно извлечь частые наборы (так как не генерирует кандидатов, в отличии от алгоритма Apriori).

FP-max – это вариант FP-Growth, который фокусируется на получении максимальных itemset. Набор элементов X (itemset X) называется максимальным, если X является частым и не существует частого шаблона, содержащего X. Другими словами, частый шаблон X не может быть под-шаблоном более частого шаблона, чтобы соответствовать определению максимального набора элементов.

Для выявления эффективности алгоритмов была использована транзакционная база данных онлайн-ресторана города Казань, средняя длина транзакции = 5, общее количество транзакций – 20246. На рисунке 1 представлен результат работы алгоритмов в зависимости от разных значений минимальной поддержки и ее влияние на время работы алгоритмов.

Рисунок 1. График зависимости времени работы от значения минимальной поддержки

Список литературы:

1. Harvard Business Review: The Value of Keeping the Right Customers [Электронный ресурс]. URL: https://hbr.org/2014/10/the-value-of-keeping-the-right-customers (дата обращения: 08.06.2021)
2. Invesp: The Importance of Cross Selling and E-commerce Product Recommendations – Statistics and Trends [Электронный ресурс]. URL: https://www.invespcro.com/blog/e-commerce-product-recommendations/ (дата обращения: 08.06.2021)
3. Busarov Vyacheslav, Grafeeva Natalia, Mikhailova Elena. A Comparative Analysis of Algorithms for Mining Frequent Itemsets. Communications in Computer and Information Science. –– SPRINGER, 2016. –– P. 136–150
4. Стокипный А. Л. Способ эффективного представления исследуемого набора данных в методах поиска ассоциативных правил / А. Л. Стокипный // Кібернетика та системний аналіз. – Харьков,2009. – С. 153–161.
5. Келлехер Д., Тирни Б. Наука о данных: Базовый курс. М.: Альпина Паблишер, 2020.  — С.151-153.
6. Agrawal R. Fast algoritms for missing association rules in large databases / R. Agrawal, R. Srikant // Proceedings of the 20th International Conference on Very Large Data Bases. — Santiago de Chile, 1994. – С. 487–499.