Аннотация 2
Введение 5
1 Анализ алгоритмов для работы с предметными наборами 7
1.1 Обзор технологии аффинивного анализа данных 7
1.2 Алгоритмы для работы с предметными наборами 9
2 Методология сравнительного анализа алгоритмов поиска частых предметных наборов 20
2.1 Анализ критериев для выбора оптимального алгоритма 20
2.2 Выборка данных для анализа 24
3 Разработка программного модуля для сравнения алгоритмов 26
3.1 Описание программного модуля 26
3.2 Результаты тестирования алгоритмов 35
Заключение 38
Список используемой литературы 39
В настоящее время Big Data становятся неотъемлемой частью личной и профессиональной жизни людей. Сегодня по-настоящему успешный бизнес уже немыслим без анализа данных, а в медицине различные инструменты Data Mining используются повсеместно.
Аффинитивный анализ активно используется розничными сетями всех стран мира для поиска взаимосвязи в подкупах, совершаемых клиентами магазина [12]. Целью аффинитивного анализа является поиск правил, описывающих закономерность в совершаемых покупках. Первое математическое описание данной задачи было предложено Rakesh Agrawal в 1993 году, и она известна под названием Market Basket Analysis [11]. «Задача подразумевает выделение нестрогих правил, по которым клиенты, приобретающие некий набор товаров, зачастую покупают что-то ещё в дополнение к имеющимся покупкам. Правила такого вида именуются ассоциативными, а вероятность, с которой выбор одних товаров влечёт выбор других, называется значимостью (confidence). Задача анализа продуктовой корзины являлась предпосылкой к появлению области ассоциативных правил, однако в дальнейшем этот инструмент начали использовать для увеличения перекрёстных продаж (cross-sell) и продаж с повышением цены (up-sell), а также для более эффективной прямой адресной рассылки рекламных предложений (direct mail)» [20].
Основная часть любого алгоритма поиска ассоциативных правил состоит в поиске часто встречающихся наборов. При условии наличия решения этой подзадачи, получение ассоциативных правил осуществляется тривиальным образом, в то время как сам поиск частых наборов вычислительно сложен. В действительности, проблема, к которой сводится поиск ассоциативных правил, является гораздо более востребованной и применяется ещё и для задач классификации и прогнозирования, например, при диагностике заболеваний сердца [8].
Исходя из значительного количества исследований в области часто встречающихся наборов и наличия множества свежих публикаций, можно с уверенностью сделать вывод об актуальности проблем, сводящихся к поиску частых наборов.
Задача существует уже более 20-ти лет, и за это время появилось огромное количество алгоритмов, решающих её с той или иной степенью эффективности. Однако сложность состоит в том, что до появления данной работы не существовало полноценного сравнительного анализа одновременно всех существующих алгоритмов поиска частых наборов в равных условиях [14]. При решении конкретной задачи важно иметь возможность осознанного выбора алгоритма с наибольшей производительностью, однако это невозможно было сделать при отсутствии полномасштабного исследования.
Цель данной работы — разработка программного модуля для сравнения алгоритмов поиска частых предметных наборов. Для достижения этой цели в рамках данной работы были сформулированы следующие задачи:
• провести теоретический анализ алгоритмов;
• разработать программное обеспечение для сравнения быстродействия алгоритмов;
• провести тестирование программного обеспечения на существующем наборе данных.
Выделим основные результаты работы:
1. На основе исследований был проведен сравнительный анализ алгоритмов поиска частных предметных наборов. Установлено, что существует два принципа работы алгоритмов: Генерация решений и тестирование (candidate-generation-and-test) и Наращивание паттернов (pattern-growth). Алгоритмы друг от друга также отличаются используемыми структурами данных для хранения исходных данных и промежуточных результатов работы алгоритмов.
2. Произведен анализ критериев для определения оптимального алгоритма поиска частых предметных наборов. Рассматривались такие критерии, как асимптотика, простота реализации, объем затрачиваемой памяти и время поиска решения. В ходе анализа установлено, что время поиска решения является ключевым фактором при выборе оптимального алгоритма.
3. Описана выборка данных, на которых проводится тестирование алгоритмов поиска частых предметных наборов. Результаты тестирования и графики приведены в третье главе.
4. На языке программирование Python было разработано программное обеспечение, производящее сравнение быстродействия алгоритмов поиска частых предметных наборов на загруженных пользователем данных. Реализована поддержка следующих алгоритмов: Apriori, Apriori Hybrid, PrePost, PrePost+, Eclat, dEclat, PPV, FIN, FP-Growth, Relim, LCMFreq и H- mine. В программном обеспечении реализована возможность визуализации результатов вычислительного эксперимента по замеру быстродействия алгоритмов в виде графиков. Программное обеспечение работает на облачном сервере Google colab.
