COMPARISON OF ALGORITHMS OF CONSTRUCTION OF ASSOCIATIVE RULES ON THE BASIS OF THE DATA SET OF CUSTOMER TRANSACTIONS

Full Text

ВВЕДЕНИЕ Анализ покупательской корзины относится к задачам интеллектуального анализа данных (data mining). Data mining - это процесс поиска в большом объеме данных каких-либо закономерностей и получения знаний, которые требуются для принятия решений во многих сферах человеческой деятельности [1-4]. Правило ассоциации (associate rule) состоит из двух частей, предшествующей (если) и последующей (то). Предшествующая задача - это элемент, находящийся в данных. А последующая -это элемент или множество элементов, которые встречаются в сочетании с предшествующей задачей [5]. В интеллектуальном анализе данных правила ассоциации являются полезными и помогают спрогнозировать поведение клиента. Они играют важную роль в анализе покупательских корзин [6, 7]. Для оценки качества полученных рекомендаций используются следующие метрики: 1. Поддержка (support) позволяет узнать, в какой части покупательских корзин содержатся все элементы того или иного ассоциативного правила. 2. Достоверность (confidence) показывает, насколько хорошим является правило для предсказания правой части, когда условие слева верно. 3. Интерес (lift) играет важную роль при анализе полученных правил и показывает, насколько хорошо было предсказано то, что находится в правой части. Другими словами, lift измеряет силу правила, сравнивая полное правило с предположенной правой частью и рассчитывается, как отношение достоверности правила к частоте появления следствия. Алгоритм Apriori Алгоритм Apriori использует горизонтальное представление множеств: - набор данных, - минимальная поддержка, - все частые множества признаков. Алгоритм Eclat На первом этапе алгоритм Eclat выполняет преобразование горизонтального предоставления множеств в вертикальное (по-другому можно назвать TID-множества) и в дальнейшем работа ведется именно с ним. В данном представлении поддержка будет выражаться, как отношение мощности множества к общему числу корзин. Последующие этапы этого алгоритма аналогичны этапам алгоритма Apriori, кроме функции подсчета поддержки кандидата, которая теперь не требует сканирования базы. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ После реализации данных алгоритмов и оптимизации под исходный набор данных, были заданы уровень поддержки в диапазоне 0,001 и достоверность 0,8. Данные параметры можно считать оптимальными для получения наиболее полезных правил. Результат выполнения программы представлен в таблице 1. Из полученной таблицы стоит выделить первое правило с высоким коэффициентом поддержки и интереса, что с первого взгляда может говорить о его полезности. Более подробно правило можно описать так: люди, покупающие ликер и вино с вероятностью 90% также приобретут пиво. Поддержка же говорит о том, что данные товары встречаются в 0,19% из общего числа транзакций, а интерес указывает на силу правила. Однако следует учесть, что товары находятся в одном и том же отделе магазина и наиболее вероятно расположены рядом друг с другом, поэтому полученное правило правильнее трактовать, как очевидное, нежели полезное. Последующие четыре правила тоже являются вполне очевидными, т.к. составляют средне статическую покупательскую корзину. Чтобы выявить полезные правила, были предприняты попытки зафиксировать левую часть правила популярным продуктом и посмотреть полученные правила. Результат представлен в таблице 2. Правила 1 и 5 могут считаться интересными, так как их следует учитывать при формировании отделов магазина. Если молочный отдел расположить рядом с кондитерскими изделиями, может увеличиться средний чек. Чтобы оценить полученные правила, был построен график их разброса, представленный на рисунке 1. Таким образом, удалось выявить, что наиболее оптимальным вариантов поиска полезных правил будет фиксирование в левой части нужного продукта и уже после анализ полученного результата. Данные действия могут помочь выстроить правильное расположение отделов, чтобы повысить покупательскую активность. На заключительном шаге было произведено сравнение алгоритмов построения ассоциативных правил Apriori и Eclat в данной задаче для выбора наиболее оптимального. Сначала изменялся параметр поддержки, результат можно увидеть в таблице 3, который свидетельствует о значительном преимуществе алгоритма Eclat, что в свою очередь можно обосновать работой с, так называемыми, TID-множествами. На следующем шаге, параметр поддержки был фиксированный и подавалось разное количество данных на вход. Результат отображен в таблице 4. Как можно заметить, алгоритм Apriori практически не способен работать на большом объеме данных. Таким образом, учитывая, что задачи анализа данных актуальны лишь при обработке большого числа входных значений, можно сделать вывод, что предпочтение стоит отдать алгоритму Eclat. Таблица 1. Ассоциативные правила со значением supp = 0,001 и conf = 0,8 Таблица 2. Ассоциативные правила для продукта «pastry» Рисунок 1. Разброс полученных правил Таблица 3. Сравнение алгоритмов по значению поддержки Таблица 4. Сравнение алгоритмов по объему данных

About the authors

Igor Anatol'evich Olyanich

Samara National Research University named after Academician S.P. Korolyov

Email: 14124123@mail.ru
Postgraduate Student

References

Supplementary files