Мощный алгоритм поиска ассоциативных правил в больших наборах элементов!
Вступление
Мы представили алгоритм априори и указали на его основные недостатки в предыдущем посте. В этой статье будет раскрыт расширенный метод, называемый алгоритмом роста FP. Мы рассмотрим весь процесс алгоритма роста FP и объясним, почему он лучше, чем Apriori.
Почему это хорошо?
Напомним из предыдущего поста, двумя основными недостатками алгоритма априори являются:
- Размер наборов-кандидатов может быть очень большим.
- Высокие затраты на подсчет поддержки, поскольку нам приходится сканировать базу данных наборов элементов снова и снова.
Чтобы преодолеть эти проблемы, самый большой прорыв Fp Growth заключается в том, что
Генерация кандидатов не требуется!
Все проблемы Apriori можно решить, используя дерево FP. Чтобы быть более конкретным, размер набора элементов больше не будет проблемой, поскольку все данные будут храниться в более компактной версии. Более того, нет необходимости сканировать базу данных снова и снова. Вместо этого обход дерева FP может сделать ту же работу более эффективно.
FP Дерево
Дерево FP - это основная концепция всего алгоритма роста FP. Вкратце, дерево FP - это сжатое представление базы данных наборов элементов. Древовидная структура не только резервирует набор элементов в БД, но также отслеживает связь между наборами элементов.
Дерево строится путем поочередного сопоставления каждого набора элементов с путем в дереве. Вся идея этой конструкции заключается в том, что
У более часто встречающихся предметов будет больше шансов поделиться предметами
Затем мы рекурсивно анализируем дерево, чтобы получить частый образец. Рост шаблона, название алгоритма, достигается путем объединения частого шаблона, сгенерированного из условных деревьев FP.
Алгоритм роста FP
Не стесняйтесь проверить хорошо прокомментированный исходный код. Это действительно может помочь понять весь алгоритм.
Причина, по которой FP Growth настолько эффективна, заключается в том, что это подход разделяй и властвуй. И мы знаем, что эффективный алгоритм должен использовать какую-то структуру данных и передовые методы программирования. В нем реализовано дерево, связанный список и концепция поиска в глубину. Процесс можно разделить на два основных этапа, каждый этап можно разделить на два этапа.
Этап 1: построение дерева FP
Шаг 1. Очистка и сортировка
Для каждой транзакции мы сначала удаляем элементы, которые ниже минимальной поддержки. Затем мы сортируем элементы в порядке убывания поддержки частоты.
Шаг 2: Постройте дерево FP, таблицу заголовков с очищенными наборами элементов
Прокрутите очищенные наборы элементов, сопоставьте их с деревом по одному. Если какой-либо элемент уже существует в ветке, они используют один и тот же узел, и счетчик увеличивается. В противном случае элемент будет в новой созданной ветке.
Таблица заголовков также создается во время этой процедуры. Для каждого уникального элемента в транзакциях есть связанный список. С помощью связанного списка мы можем найти вхождение элемента в дереве за короткий период времени, не просматривая дерево.
Этап 2: майнить главное дерево и условные деревья FP
Шаг 1. Разделите основное дерево FP на условные деревья FP
Исходя из каждого частого 1-шаблона, мы создаем базы условных шаблонов с набором префиксов в дереве FP. Затем мы используем эти базовые шаблоны для построения условных FP-деревьев тем же методом, что и на этапе 1.
Шаг 2: рекурсивно извлеките каждое условное дерево
Частые шаблоны генерируются из условных деревьев FP. Для одного частого паттерна создается одно условное дерево FP. Рекурсивная функция, которую мы использовали для поиска условных деревьев, близка к поиску в глубину. Он следит за тем, чтобы из оставшихся элементов больше не было деревьев, прежде чем двигаться дальше.
Давайте внимательно посмотрим на процесс ниже
Одинаковый уровень в том же цвете. Рабочий процесс алгоритма приведен ниже.
- Проверка первого 1-частого паттерна "а"
- Получите условное дерево FP для "a" розовым цветом
- Добывайте розовое дерево и пройдите глубже до уровня 2.
- Отметьте "f" на розовом дереве и обнаружите, что дерево больше не может быть построено.
- Отметьте букву "c" на розовом дереве.
- Добывайте желтое дерево и пройдите глубже до уровня 3.
Реализация Python
Функция роста FP
С первого взгляда на эту основную функцию роста FP вы можете усомниться в двух ее частях.
Зачем использовать отдельные списки для набора элементов и частоты вместо словаря?
Причина в том, что ключ в словаре Python должен быть неизменяемым, поэтому мы не можем использовать set () в качестве ключа. Однако неизменная версия набора frozenset приемлема. К сожалению, поскольку порядок этих элементов имеет решающее значение в алгоритме роста FP, мы не можем сохранить этот порядок после преобразования в frozenset. Единственное решение - хранить его в отдельных списках.
Почему дерево FP не используется в качестве входной переменной в функции mineTree?
В этом сила таблицы заголовков. Поскольку мы уже сохранили все вхождения в таблице заголовков, нет необходимости передавать корневой узел в функцию. Мы можем быстро найти элемент в дереве с помощью связанного списка в таблице.
Строительство дерева
Со списком наборов элементов мы сначала создаем полупустую таблицу заголовков, которая содержит только элементы и их частоту. Мы перебираем каждый набор элементов, очищаем и сортируем элементы в порядке убывания по частоте. Затем мы обновляем дерево, передавая элемент один за другим из очищенного набора элементов.
Если элемент уже существует в дереве, мы просто увеличиваем счетчик. В противном случае мы создаем новую ветку с элементом и прикрепляем ее к родительскому узлу. Важным шагом здесь является обновление таблицы заголовков, поскольку это новое вхождение элемента. Свяжите новое вхождение со связанным списком из таблицы заголовков.
Добыча деревьев
Шахта дерево
Начиная с 1-частого паттерна, мы находим все пути префиксов и строим по ним базы условных паттернов. С базами условных шаблонов дерево строится с использованием той же самой функции constructTree, описанной выше. И если дерево может быть успешно построено, мы идем глубже и начинаем работать над этим деревом. Здесь и происходит рекурсия.
Помните, я упоминал, что для каждого частого шаблона строится одно условное дерево? Вы можете увидеть рост модели в строке 8.
Найти путь префикса
Получите первое вхождение элемента в дереве, которое является головным узлом связанного списка в таблице заголовков. Затем пройдите по дереву до корня, чтобы получить путь префикса. После этого мы переходим к следующему узлу связанного списка и повторяем обход.
Восхождение по дереву FP
Поднимитесь по дереву с помощью саморекурсии. Продолжайте добавлять элементы и вызывать себя, пока не достигнет корня.
Сравнение
Рост FP vs Априори
Я организовал основные функции обоих алгоритмов и представил их в таблице выше. Наблюдая за таблицей, мы можем сказать, что рост FP в большинстве случаев лучше, чем Apriori. Вот почему Априори - это просто фундаментальный метод, а FP Growth - его улучшение.
Время выполнения с другой минимальной поддержкой
Мы берем набор данных из репозитория исходного кода и пробуем поэкспериментировать. Первое, что мы делаем, это проверяем, как минимальная поддержка определяет время выполнения.
Из графика видно, что рост FP всегда быстрее, чем Apriori. Причина этого уже объяснена выше. Интересным наблюдением является то, что для обоих наборов данных время выполнения apriori начало быстро увеличиваться после определенного минимума. С другой стороны, время выполнения FP Growth просто зависит от значения.
Время выполнения с другим количеством транзакций
Время выполнения обоих алгоритмов увеличивается по мере увеличения количества наборов элементов. Однако мы можем ясно видеть, что наклон увеличения априори намного выше. Это означает, что алгоритм Apriori более чувствителен к размеру наборов элементов по сравнению с Fp Growth.
По возрастанию и по убыванию
Вам может быть интересно, почему мы должны сортировать элементы в порядке убывания, прежде чем использовать его для построения дерева. Что будет, если попробовать по возрастанию? Как видно из графика, сортировка по убыванию всегда быстрее. И разница в скорости более очевидна при меньшей поддержке.
Но почему? Я хотел бы высказать некоторые свои предположения. Напомним основную концепцию FP Growth.
У более часто встречающихся предметов будет больше шансов поделиться предметами
Начиная с предметов с более высокой поддержкой, будет больше шансов поделиться ветвями. Чем больше общих ветвей, тем меньше размер дерева. И чем меньше дерево, тем меньше затраты на запуск всего алгоритма. Следовательно, сортировка элементов в порядке убывания заставит этот метод работать быстрее.
Заключение
Хочу поделиться интересной историей. Когда я писал эту статью после работы, мимо прошел штатный инженер и увидел, что я что-то пишу об Apriori и Fp Growth. Он сказал: «Интересно, но нереально». Он также пояснил, что этот алгоритм не учитывает взвешивание. Например, как насчет транзакции с несколькими одинаковыми товарами? Есть также более тонкие условия, которые не включены в этот алгоритм. И поэтому компании не будут внедрять это в своем бизнесе.
