АССОЦИАТИВНЫЕ ПРАВИЛА И ИХ ПРИМЕНЕНИЕ.

АННОТАЦИЯ

В статье рассказывается о ассоциативных правилах и их применении.

Ключевые слова: поиск ассоциативных правил, коммерция.

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

Обучение ассоциативным правилам или поиск ассоциативных правил — это метод обучения машин на базе правил обнаружения интересующих нас связей между переменными в большой базе данных. Метод предлагается для установления сильных правил, обнаруженных в базе данных с помощью некоторых мер интересности [1]. Этот основанный на правилах подход генерирует также новые правила по мере анализа дополнительных данных. Конечной целью, исходя из достаточно большого набора данных, помочь машине имитировать выделение признаков человеческим и создать возможность нахождения абстрактных ассоциаций из новых неклассифицированных данных [2].

Опираясь на концепцию строгих правил, Ракеш Агравал, Томаш Имелинский и Арун Свами ^[3] выдвинули ассоциативные правила для обнаружения закономерностей между продуктами в транзакциях большого размера для данных, записанных системами POS-терминалов в супермаркетах. Например, правило {лук, картофель} => {гамбургер}, найденное в данных о продажах супермаркета, могло бы означать, что, если покупатель покупает лук и картофель вместе, он, скорее всего, купит также и гамбургер. Такого рода информация может быть использована как базис для решений о маркетинговых действиях, например, стимулирующему ценообразованию или размещению продукции.

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

Перекрестные продажи или кросс-продажи — это предложение товара покупателю, который мог бы его заинтересовать в сочетании с уже приобретенным товаром. Данная стратегия может заметно увеличить прибыль компании. Так, например, 35% доходов Amazon приходится именно на перекрестные продажи. Ассоциативные правила используются при анализе покупательской корзины для выявления паттернов покупок и совместно покупаемых товаров. В отличии от кластеризации, которая выявляет сходства и/или различия между объектами, поиск ассоциативных правил рассматривает в наборе данных связи между атрибутами (поиск корреляции между товарами). Для данного типа анализа необходима выгрузка всех транзакций покупателей за продолжительное время, где каждая транзакция содержит информацию о товарах, которые оплатил конкретный покупатель в конкретное время. Транзакционная база данных является двумерной таблицей, в которой есть информация об идентификаторе транзакции, а также перечня покупок. Супермаркетам и предпринимателям малого и среднего бизнеса хорошо известно, что обычно в транзакции бывает не один товар, а группа товаров, и чаще всего между ними есть взаимосвязь. Для выстраивания связей между товарами используется метод анализа данных при обучении без учителя – поиск ассоциативных правил, который позволяет находить закономерность между связанными событиями. Ассоциативное правило имеет форму: если {предпосылка} ⇒ то {следствие}. То есть, если имеется выведенное правило, включающее в себя элементы 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.

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

1. Келлехер Д., Тирни Б. Наука о данных: Базовый курс. М.: Альпина Паблишер, 2020. — С.151-153.