Сорокоумов И.А.

магистрант, Волгоградский государственный технический университет

Алгоритм поиска ассоциативных правил для анализа потребительской корзины

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

Результаты, полученные путём анализа рыночной корзины, необходимы для дальнейшей оптимизации ассортимента товаров и запасов, размещения их в торговых залах, увеличения объема продаж за счет предложения клиентам сопутствующих товаров. Например, если в результате анализа будет установлено, что совместная покупка макарон и кетчупа является типичным шаблоном, то разместив эти товары на одной и той же витрине можно «спровоцировать» покупателя на их совместное приобретение.

Для решения задачи анализа рыночной корзины используются ассоциативные правила вида «если… то...». Например, «если клиент купил пиво, то он купит и чипсы». Каждая покупка именуется «транзакцией», на основании большего набора таких транзакций и строят исследования поведения клиента.
Существует несколько алгоритмов для анализа потребительской корзины, из основных можно выделить Apriori, FP-growth algorithm. Каждый из алгоритмов из всей совокупности чеков выделяет ассоциативные правила (association rules) — повторяющиеся связи между товарами в корзинах.

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

Исходные данные для ассоциативного правила: Х и Y — 2 товара, категории или товарные группы; X — ключевой товар, причина;Y — сопровождающий товар, следствие.

Поддержка (Support) — высчитывается для одного товара/пары, показывает соотношение количества чеков с выбранным товаром/парой и общего количества чеков.

Достоверность (Confidence) — показывает соотношение чеков Х и Y к числу чеков в которых покупают только ключевой товар — Х.

Алгоритм Apriori

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

Алгоритм Apriori — масштабируемый алгоритм поиска ассоциативных правил. Для того, чтобы было возможно применить алгоритм, необходимо провести предобработку данных: во-первых, привести все данные к бинарному виду; во-вторых, изменить структуру данных.

Таблица 1. Обычный вид базы данных транзакций

Номер транзакции	Наименование элемента	Количество
1001	А	2
1001	D	3
1001	E	1
1002	А	2
1002	F	1
1003	B	2
1003	A	2
1003	C	2

Таблица 2. Нормализованный вид:

TID	A	B	C	D	E	F	G	H	I	K	…
1001	1	0	0	1	1	0	0	0	0	0	…
1002	1	0	0	0	0	1	0	0	0	0	…
1003	1	1	1	0	0	0	0	0	1	0	…

Количество столбцов в таблице равно количеству элементов, присутствующих в множестве транзакций D. Каждая запись соответствует транзакции, где в соответствующем столбце стоит 1, если элемент присутствует в транзакции, и 0 в противном случае.

На первом шаге необходимо найти часто встречающиеся наборы элементов, а затем, на втором, извлечь из них правила. Количество элементов в наборе будем называть размером набора, а набор, состоящий из k элементов, – k-элементным набором.

Выявление часто встречающихся наборов элементов – операция, требующая много вычислительных ресурсов и, соответственно, времени. Примитивный подход к решению данной задачи – простой перебор всех возможных наборов элементов. Это потребует O(2^|I|) операций, где |I| – количество элементов. Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств.

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

На рисунке 1 показан набор элементов I – {A, B, C, D}. Предположим, что набор из элементов {A, B} имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с {A, B}, выделена фоном. Использование этой эвристики позволяет существенно сократить пространство поиска

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

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

Опишем функцию генерации кандидатов. На это раз нет никакой необходимости вновь обращаться к базе данных. Для того, чтобы получить k-элементные наборы, воспользуемся (k-1)-элементными наборами, которые были определены на предыдущем шаге и являются часто встречающимися.

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

1. Объединение. Каждый кандидат C_k будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1)- элементного набора. Приведем алгоритм этой функции Apriorigen в виде небольшого SQL-подобного запроса:

insert into C_k
select p.item₁, p.item₂, …, p.item_k-1, q.item_k-1

From F_k-1 p, F_k-1 q

where p.item₁= q.item₁, p.item₂ = q.item₂, … , p.item_k-2 = q.item_k-2,

p.item_k-1 <q.item_k-1

2. Удаление избыточных правил. На основании свойства
анти-монотонности, следует удалить все наборы c ϵ C_k если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.

После генерации кандидатов следующей задачей является подсчет поддержки для каждого кандидата. Для этого целесообразно использовать подход, основанный на хранении кандидатов в хэш-дереве. Внутренние узлы дерева содержат хэш-таблицы с указателями на потомков, а листья – на кандидатов.
Хэш-дерево с кандидатами-наборами построено, теперь, используя хэш-дерево, легко подсчитать поддержку для каждого кандидата. Для этого нужно "пропустить" каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, т.е. C_k ∩ T_i = C_k. На корневом уровне хэш-функция применяется к каждому элементу из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым элементам и т.д. На k-уровне хэшируется k-элемент. И так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, тогда увеличиваем счетчик поддержки этого кандидата на единицу.

После того, как каждая транзакция из исходного набора данных "пропущена" через дерево, можно проверить удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, она нам пригодится при извлечении правил. Эти же действия применяются для нахождения (k+1)-элементных наборов и т.д.

После того как найдены все часто встречающиеся наборы
элементов, можно приступить непосредственно к генерации правил.
Извлечение правил – менее трудоемкая задача. Во-первых, для подсчета достоверности правила достаточно знать поддержку самого набора и множества, лежащего в условии правила. Например, имеется часто встречающийся набор {A, B, C} и требуется подсчитать достоверность для правила АВ => C. Поддержка самого набора нам известна, но и его множество {A, B}, лежащее в условии правила, также является часто встречающимся в силу свойства анти-монотонности, и значит его поддержка нам известна. Тогда мы легко сможем подсчитать достоверность. Это избавляет нас от нежелательного просмотра базы транзакций, который потребовался в том случае если бы это поддержка была неизвестна.

Чтобы извлечь правило из часто встречающегося набора F, следует найти все его непустые подмножества. И для каждого подмножества s мы сможем сформулировать правило s => (F - s), если достоверность правила conf(s =>(F - s)) = supp(F)/supp(s) не меньше порога minconf.Заметим, что числитель остается постоянным. Тогда достоверность имеет минимальное значение, если знаменатель имеет максимальное значение, а это происходит в том случае, когда в условии правила имеется набор, состоящий из одного элемента. Все супермножества данного множества имеют меньшую или равную поддержку и, соответственно, большее значение достоверности. Это свойство может быть использовано при извлечении правил. Если мы начнем извлекать правила, рассматривая сначала только один элемент в условии правила, и это правило имеет необходимую поддержку, тогда все правила, где в условии стоят супермножества этого элемента, также имеют значение достоверности выше заданного порога. Например, если правило A ⇒ BCDE удовлетворяет минимальному порогу достоверности minconf, тогда AB ⇒ CDE также удовлетворяет. Для того, чтобы извлечь все правила используется рекурсивная процедура.

Литература

1. Белл М. Анализ потребительской корзины [Электронный ресурс] . –[2016]. – Режим доступа: http://www.albionresearch.com/ data_mining/market_basket.php

2. Бородин Ю. Методы поиска ассоциативных правил [Электронный ресурс] –[2016]. – Режим доступа: http://www.intuit.ru/studies/courses/6/6/lecture/186