FPG — альтернативный алгоритм поиска ассоциативных правил

Введение

Узким местом в алгоритме Apriori является процесс генерации кандидатов в популярные предметные наборы. Например, если база данных (БД) транзакций содержит 100 предметов, то потребуется сгенерировать 2¹⁰⁰∼10³⁰ кандидатов. Таким образом, вычислительные и временные затраты, которые нужны на их обработку, могут быть неприемлемыми.

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

Одним из наиболее эффективных процедур поиска ассоциативных правил является алгоритм, получивший название Frequent Pattern-Growth (алгоритм FPG), что можно перевести как «выращивание популярных (часто встречающихся) предметных наборов». Он позволяет не только избежать затратной процедуры генерации кандидатов, но и уменьшить необходимое число проходов БД до двух. Рассмотрим его более подробно.

Алгоритм Frequent Pattern-Growth Strategy (FPG)

В основе алгоритма лежит предобработка БД транзакций, в процессе которой она трансформируется в компактную древовидную структуру, называемую Frequent-Pattern Tree – дерево популярных предметных наборов (откуда и название алгоритма). В дальнейшем для краткости будем называть эту структуру FP-дерево. К основным преимуществам данного метода относятся:

1. Сжатие БД транзакций в компактную структуру, которая обеспечивает наиболее эффективное и полное извлечение частых предметных наборов;
2. При построении FP-дерева используется технология «разделай и влавствуй» (англ.: divide and conquer), которая позволяет выполнить декомпозицию одной сложной задачи на множество более простых;
3. Позволяет избежать затратной процедуры генерации кандидатов, характерной для алгоритма Apriori.

Рассмотрим работу алгоритма FPG на конкретном примере. Пусть имеется БД транзакций (табл. 1).

Для данной БД требуется обнаружить все популярные предметные наборы с минимальной поддержкой, равной 3, используя алгоритм FPG.

Производится первое сканирование БД транзакций, и отбирается множество часто встречающихся предметов, т.е. предметов, которые встречаются три или более раза. Упорядочим обнаруженные частые предметы в порядке возрастания их поддержки и получим следующий набор: (c, 6), (b, 5), (d, 5), (e, 5), (a, 3).

Построим FP-дерево. Упорядочим предметы в транзакциях по убыванию значений их поддержек (табл. 2).

Создадим начальный (корневой) узел FP-дерева, который обычно обозначают ROOT (от англ. root – корень).

Начнем построение дерева с транзакции №1 для упорядоченных предметных наборов, т.е. (c b d e a), рис. 1. При построении дерева будем придерживаться следующего правила.

Правило. Если для очередного предмета в FP-дереве уже содержится узел, то для предмета не создается новый узел, а индекс существующего увеличивается на 1. В противном случае для этого предмета создается новый узел и ему присваивается индекс 1.

Рис. 1. Построение FP-дерева на транзакции № 1

Сначала берем предмет с из транзакции №1. Поскольку он является первым, то создаем для него узел и соединяем с родительским (корневым) (рис. 1, а). Затем берем следующий предмет b и поскольку других узлов с тем же именем FP-дерево пока не содержит, добавляем его в виде нового узла, потомка узла с (рис. 1, б). Таким же образом содаем узлы для предметов d, e и a из транзакции № 1 (случаи в, г, и д на рис. 1). На этом использование первой транзакции для построения FP-дерева закончено.

Для транзакции № 2, содержащей предметы c, b и a, выбираем первый предмет, c. Поскольку узел с таким именем уже существует, то в соответствии с правилом построения FP-дерева новый узел не создается, а индекс существующего увеличивается на 1 (рис. 2, а). При добавлении следующего предмета b используем то же правило: поскольку узел b является дочерним по отношению к текущему (т.е. c), то мы также не создаем новый узел, а увеличиваем индекс для имеющегося (рис. 2, б).

Для следующего предмета из второй транзакции a в соответствии с правилом построения FP-дерева необходимо создать новый узел, поскольку у узла b дочерние узлы с именем a отсутствуют (рис. 2, в).

Рис. 2. Построение FP-дерева на транзакции № 2

Транзакция № 3 содержит предметы (c d e a). В соответствии с правилом построения FP-дерева, предмет c не создаст нового узла, а увеличит индекс уже имеющегося узла на 1 (рис. 3, а). Следующий предмет d породит в FP-дереве новый узел, дочерний к узлу c, поскольку тот не содержит потомков с таким именем (рис. 3, б). Аналогично предметы e и a создадут новые узлы – потомки d (рис. 3 в, г).

Рис. 3. Использование транзакции № 3 для построения FP-дерева

Использование транзакции № 4, содержащей набор предметов (c b d e), не создаст новых узлов, а увеличит индексы узлов с аналогичной последовательностью имен. Дерево, полученное в результате использования транзакции № 4, представлено на рис. 4.

Рис. 4. Дерево, полученное в результате использования четвертой транзакции

Транзакция № 5 содержит набор (c b), предметы которого увеличат индексы одноименных узлов в FP-дереве, как показано на рис. 5.

Рис. 5. Дерево, полученное в результате использования пятой транзакции

Транзакция № 6 содержит предметы (b d e). Поскольку корневой узел не содержит непосредственного потомка с именем b, то в соответствии с правилом построения FP-дерева для него будет создан новый узел, который «потянет» за собой два других — d и e. Все узлы будут добавлены с индексами 1. В результате FP-дерево примет вид, представленный на рис. 6.

Рис. 6. Дерево, полученное в результате использования 6-й транзакции

И, наконец, последняя транзакция № 7, содержащая предметный набор (c d e), увеличит на 1 индексы соответствующих узлов. Получившееся дерево, которое также является результирующим для всей БД транзакций, представлено на рис. 7.

Рис. 7. Результирующее дерево, построенное по всей БД транзакций

Таким образом, после первого прохода БД и выполнения соответствующих манипуляций с предметными наборами мы построили FP-дерево, которое в компактном виде представляет информацию о частых предметных наборах и позволяет производить их эффективное извлечение, что и делается на втором сканировании БД.

Представление БД транзакций в виде FP-дерева очевидно. Если в исходной базе данных каждый предмет повторяется многократно, то в FP-дереве он представляется в виде узла, индекс которого указывает на то, сколько раз данный предмет появляется. Иными словами, если предмет в исходной БД транзакций появляется 100 раз, то в FP-дереве для него будет единственный узел с индексом 100.

Извлечение частых предметных наборов из FP-дерева

Для каждого предмета в FP-дереве, представленного своим узлом, можно указать путь, т.е. последовательность узлов, которую надо пройти от корневого узла до узла, связанного с данным предметом. Если предмет представлен в нескольких ветвях FP-дерева (что чаще всего и происходит), то таких путей будет насколько. Например, для FP-дерева на рис. 7 для предмета a можно указать 3 пути: { cbdea, cba, cdea }.

Такой набор путей называется условным базисом предмета (англ.: conditional base). Каждый путь в базисе состоит из двух частей — префикса и суффикса. Префикс — это собственно последовательность узлов, которые образуют путь. Суффикс — это сам узел, к которому «прокладывается» путь. Таким образом, в условном базисе все пути будут иметь различные префиксы и одинаковый суффикс. Например, в пути cbdea префиксом будет cbde, а суффиксом — a.

Процесс извлечения из FP-дерева частых предметных наборов будет заключаться в следующем.

1. Выбираем предмет (например, a) и находим в дереве все пути, которые ведут к узлам этого предмета Иными словами, для a это будет набор { cbdea, cba, cdea }. Затем для каждого пути подсчитываем, сколько раз данный предмет встречается в нем, и записываем это в виде (cbdea, 1), (cba, 1) и (cdea, 1).
2. Удалим сам предмет (суффикс набора) из ведущих к нему путей, т.е. { cbdea, cba, cdea }. После останутся только префиксы: { cbde, cb, cde }.
3. Подсчитаем, сколько раз каждый предмет появляется в префиксах путей, полученных на предыдущем шаге, и упорядочим в порядке убывания этих значений, получив новый набор транзакций.
4. На его основе построим новое FP-дерево, которое назовем условным FP-деревом (conditional FP-tree), поскольку оно связано только с одним объектом (в нашем случае, a).
5. В условном FP-дереве найдем все предметы (узлы), для которых поддержка (количество появлений в дереве) равна 3 и больше, что соответствует заданному уровню минимальной поддержки. Если узел встречается два или более раза, то его индексы, т.е. частоты появлений предмета в условном базисе, суммируются.
6. Начиная с корня дерева, записываем пути, которые ведут к каждому узлу, для которого поддержка/индекс больше или равны 3, возвращаем назад предмет (суффикс), удаленный на шаге 2, и подсчитываем индекс/поддержку, полученную в результате. Например, если предмет a имеет индекс 3, то можно записать (c b a, 3), что и будет являться популярным предметным набором.

Для пояснения методики извлечения популярного набора из FP-дерева продолжим рассмотрение примера для БД транзакций из табл. 1 и построенного для неё FP-дерева.

Начнем с предмета a, который имеет поддержку 3 и соответственно является часто встречающимся предметом. Префиксы путей, ведущих к узлам, связанным с a, будут: (c b d e a, 1), (c b a, 1), (c d e a, 1). На основе полученного условного базиса для суффикса a, построим условное FP-дерево (рис. 8).

Рис. 8. Условное FP-дерево для предмета a

Поскольку предметы d и e встречаются два раза, то их индексы суммируются, и в итоге мы получим следующий порядок предметов: (c, 3), (b, 2), (d, 2), (e, 2). Таким образом, только узел c удовлетворяет уровню минимальной поддержки 3. Следовательно, для предмета a может быть сгенерирован только один популярный набор (c, a, 3).

Затем переходим к следующему предмету b с поддержкой 5. Условное FP-дерево, построенное для него, будет содержать только один узел c, поскольку в дереве присутствует один путь с=>b, а суффикс b исключается. Это проиллюстрировано на рис. 9.

Рис. 9. Условное FP-дерево для суффикса b

Таким образом, префиксы путей будут (c b, 4) и (b, 1), и, следовательно, для предмета b будет иметь место только один популярный набор (c b, 4).

Для предмета c, поскольку он является непосредственным потомком корневого узла, нельзя указать путь (см. рис. 7). Значит, префикс путей для него будет пустым, из чего следует, что и популярные предметные наборы отсутствуют.

Следующий предмет, для которого мы произведем поиск популярных предметных наборов, будет d с поддержкой равной 5. Условное FP-дерево, связанное с предметом d представлено на рис. 10.

Рис. 10. Условное FP-дерево для предмета d

Префиксы путей для условного дерева, связанного с предметом d, будут: (c b d, 2), (c d, 2) и (b d, 1). Учитывая, что индексы для узлов b суммируются, то соответствующие популярные предметные наборы будут (c, d, 4) и (b, d, 3).

И, наконец, для последнего предмета е, имеющего поддержку 5, условное FP-дерево представлено на рис. 11.

Рис. 11. Условное FP-3 дерево для предмета e

Префиксы путей, ведущих в условном дереве к узлам, связанным с предметом e, будут: (c b d e, 2) (c d e, 2) (b d e, 1). Подсчитав суммарную поддержку каждого предмета в условном дереве и упорядочив предметы по ее убыванию, получим: (d, 5), (c, 4), (b, 3). Следовательно, популярными предметными наборами для предмета e будут: (d, e, 5), (d, c, e, 4), (d, b, e, 3).

Таким образом, мы получили следующие популярные предметные наборы:

(c, a, 3), (c, b, 4), (c, d, 4), (b, d, 3), (d, e, 5), (d, c, e, 4), (d, b, e, 3).

Сравнительные исследования классического алгоритма Apriori и FPG показали, что с увеличением числа транзакций в БД временные затраты на поиск частых предметных наборов растут для FPG намного медленнее, чем для Apriori (рис. 12).

Рис. 12. Сравнение алгоритмов FPG и Apriori

Повышение эффективности обработки популярных наборов

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

Одним из таких методов является алгоритм разделения (Partition-based Apriori algorithm), который требует всего два прохода по БД. Он основан на идее так называемых локальных предметных наборов. При этом вся БД разделяется на N непересекающихся подмножеств, каждое из которых достаточно мало, чтобы поместиться в оперативной памяти ПК.

На первом сканировании алгоритм считывает каждое подмножество и обнаруживает предметные наборы, которые являются популярными для данного подмножества (локально-популярные предметные наборы). На втором сканировании алгоритм вычисляет поддержку всех локально-популярных предметных наборов на всеё БД. Таким образом, второе сканирование определяет множество всех потенциальных ассоциативных правил. Методика, реализуемая данным алгоритмом, поясняется на рис. 13.

Рис. 13. Метод локальных предметных наборов

Еще одним способом повышения эффективности методики поиска ассоциативных правил, основанной на популярных наборах, является сэмплинг (рис. 14). С его помощью производится отбор случайной выборки R из исходной БД транзакций, после чего поиск популярных наборов осуществляется на этой выборке. Таким образом ищется компромисс между точностью и вычислительными затратами.

Рис. 14. Схема применения сэмплинга

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

Другие материалы по теме:

Введение в анализ ассоциативных правил 

Выявление обобщенных ассоциативных правил

Apriori - масштабируемый алгоритм поиска ассоциативных правил