Поиск наиболее часто встречающихся наборов элементов
Большинство ранних исследований, посвященных поиску ассоциативных правил, связаны именно с темой поиска наиболее часто встречающихся элементов. Сюда относятся ключевые работы, посвященные алгоритму Apriori. Были проведены множество различных исследований с целью улучшения производительности и масштабируемости Apriori, включая попытки использования параллельных вычислений. Были так проведены исследования, направленные на улучшения скорости поиска наиболее часто встречающихся наборов элементов с помощью хеш-таблиц, карт и деревьев.
Два предшественника Apriori - алгоритмы AIS [14] и SETM [15]. AIS и SETM генерировали наборы-кандидаты на лету, в процессе сканирования базы данных. Каждая транзакция проверялась на наличие больших наборов, выявленных при предыдущем проходе. Соответственно, новые наборы формировались путем расширения имеющихся наборов. Эти алгоритмы оказались неэффективными, поскольку они генерировали и учитывали слишком много наборов-кандидатов, которые в дальнейшем оказывались недостаточно большими (нечастыми) [4].
Чтобы решить эту проблемы, были предложены [4] алгоритмы Apriori, AprioriTid И AprioriHybrid. Apriori и AprioriTid генерируют наборы элементов используя только большие наборы, найденные на предыдущем шаге, без повторного рассмотрения транзакций. AprioriTid улучшает Apriori за счет того, что использует базу данных только при первом проходе. При подсчетах на последующих шагах используются лишь данные, созданные при первом проходе и имеющие гораздо меньший размер, чем исходная база данных. Это приводит к колоссальному росту производительности - в три раза быстрее, чем AIS и в четыре раза быстрее, чем SETM в одном из экспериментов, проведенных авторами статьи [4]. Дальнейшая усовершенствованная версия алгоритма, названная AprioriHybrid, может быть получена, если при нескольких первых проходах использовать Apriori, а затем, на более поздних проходах, когда к-ые наборы-кандидаты уже могут быть целиком размещены в памяти компьютера, переключатся на AprioriTid.
Проблема Apriori в том, что он генерирует слишком много двухэлементных наборов, которые не являются частыми. В [12] предложен механизм прямого хеширования и обрезки данных (DHP), которые позволяют уменьшить количество наборов кандидатов за счет отбрасывания k-ых наборов из хеш таблицы, если их значение в хеш таблице не достигает величины минимальной поддержки. Как показали сравнительные эксперименты [2], эта замечательная фильтрующая особенность позволяет DHP завершить уже все вычисления в том момент, когда Apriori все еще находится на втором шаге.
L1={large 1-itemsets};
FOR (k=2; Lk-1 != 0; i++ ) DO BEGIN
Ck=apriori-gen(Lk-1);
FORALL transactions t in D DO BEGIN
Ct=subset(Ck,t);
FORALL candidates c in Ct DO
c.count++;
END
Lk={c in Ck | c.count >= minsup}
END
Answer = Sum Lk;
FUNC apriori-gen(set Lk-1) BEGIN
INSERT INTO Ck
SELECT p.item1, p.item2,…,p.itemk-1,q.itemk-1
FROM Lk-1 p, Lk-1 q
WHERE p.item1=q.item1,…,p.itemk-2=q.itemk-2, p.itemk-1<q.itemk-1;
FORALL itemset c in Ck DO
FORALL (k-1)-subsets s of c DO
IF (s not in Lk-1) THEN
DELETE c from Ck;
END
Рисунок 1: Алгоритм Apriori
L1={large 1-itemsets};
C1’=database D;
FOR (k=2; Lk-1 != 0; i++ ) DO BEGIN
Ck=apriori-gen(Lk-1);
Ck’=0;
FORALL entries t in Ck-1’ DO BEGIN
Ct={c in Ck | (c-c[k]) in t.set-of-itemsets ^ (c-c[k-1]) in t.set-of-itemsets};
FORALL candidates c in Ct DO
c.count++;
IF (Ct != 0) THEN Ck’ +=<t.TID,Ct>;
END
Lk={c in Ck | c.count >= minsup}
END
Answer = Sum Lk;
Рисунок 2: Алгоритм AprioriTid
Дальнейшие усилия по улучшению алгоритма Apriori связаны с распараллеливанием алгоритма. В [7] предложено 3 параллельных алгоритма, базирующихся на Apriori, позволяющих ускорить поиск часто используемых наборов элементов. Алгоритм Count Distribution (CD) минимизирует обмен данными (communication) за счет проведения дублирующих вычислений. Алгоритм Data Distribution (DD) использует основную память системы для передачи локальных данных на другие узлы системы. Алгоритм Candidate Distribution - это сбалансированный по нагрузке алгоритм, снижающий синхронизацию между процессорами и сегментирующий базу данных на основе различных шаблонов транзакций. Эти параллельные алгоритмы были протестированы. Среди прочих и алгоритм CD имел наилучшую производительность по сравнению с алгоритмом Apriori. Его накладные расходы не превышали 7.5% по сравнению с Apriori согласно [7].
Масштабируемость - другая важная область исследований для data mining, т.к. базы данных с каждым днем становятся все больше и больше. Алгоритмы должны быть способны масштабироваться, чтобы обработать большие наборы данных. Основываясь на работе [7], в работе [13] была предпринята попытка сделать DD и CD алгоритмы масштабируемыми. Были, соответственно, созданы алгоритмы Intelligent Data Distribution (IDD) и Hybrid Distribution (HD). IDD направлен на снижение накладных расходов на взаимодействие и исключение излишних вычислений [7] за счет использования агрегатной памяти (aggregate memory) для разделения кандидатов и эффективного перемещения данных. HD улучшен по сравнению с IDD за счет динамического разделения массива кандидатов для лучшего поддержания сбалансированной нагрузки. Эксперименты показали, что время отклика IDD в 4.4 раза меньше, чем DD на 32-процессорной системе, а HD оказался лучше CD на 9.5% при работе на 128-процессорах [13].
Другое исследования масштабирования при data mining [11] основано на введении облегченных структур данных, называемых Segment Support Map (SSM), которые уменьшают количество наборов-кандадитов, необходимых в расчетах. SSM содержит значения поддержки для одинарных наборов. Путем суммирования значений поддержки для одинарных наборов оцениваются верхние границы для k-элементных наборов. В применении к Apriori, усилия по генерированию одноэлементных наборов могут быть сэкономлены простым поиском тех одноэлементных наборов в SSM, у которых поддержка выше минимального порога. Более того, одноэлементные наборы, у которых поддержка меньше порогового значения, вообще исключаются, что позволяет снизить количество наборов более высокого уровня.
Другая область исследований, направленная на улучшение Apriori и основанна на применении оригинальных структур данных, связана с применением деревьев часто встречающихся элементов (frequent pattern tree, or FP-tree). FP-дерево сохраняет информацию о часто используемых шаблонах (patterns). Метод, основанный на FP-деревьях, называется FP-growth (метод выращивания наиболее популярных шаблонов). В нем, вместо генерации наборов-кандидатов, предлагается искать часто используемые шаблоны. В [9] не только показано, что FP-growth метод на порядок лучше, чем Apriori, но так же и то, что этот метод лучше масштабируется.
Переход от итерационных методов, подобно Apriori и DHP, к инновационному использованию структур данных, типа SSM и FP-деревьев, привел к тому, что поиск часто наборов встречающихся элементов стал более масштабируемым и эффективным. Необходимость в более быстрых и более масштабируемых алгоритмах по-прежнему существует, поскольку базы данных становятся все больше и больше с каждым днем. Исследования, посвященные распределенным алгоритмам для поиска часто встречающихся наборов, привлекают тем больше внимания, чем больше баз данных интегрируется вместе. Такая интеграция выдвигает переводит задачу поиска на новый уровень, требующий более гибких алгоритмов, принимающих во внимание различное представление одинаковых данных. Например, zip-коды могут быть представлены строками или числами, поэтому данные не могут быть нормализованы до проведения поиска. Можно ожидать увеличения количества исследований, связанных с параллельными алгоритмами, поскольку сетевые вычисления набирают все большую популярность.
По сравнении со множеством работ, посвященных поиску лучшего алгоритма поиска часто встречающихся наборов элементов, оценочный критерий - пороговое значение поддержки, - и механизм, стоящий за ним - подсчет - получили гораздо меньше внимания. Проблема с пороговым значением поддержки в том, что оно требует наличия экспертных знаний (которые, в лучшем случае, субъективные) в качестве параметра системы. Указание слишком низкого порогового значения пропустит наборы элементов, которые должны быть отброшены и наоборот. Более того, с ростом размеров баз данных, пороговые значения должны корректироваться. В следующем разделе будут освещены некоторые работы, посвященные решению этих проблем.