Какой самый эффективный алгоритм для этого?
, поэтому любой метод грубой силы был бы слишком неэффективным.
Прежде всего, метод грубой силыэто слишком дорогоВ методе грубой силы, если длина каждой транзакции равна N, мы должны проверить 2 ^ N паттернов .Таким образом, подсчет числа вхождений каждого паттерна с помощью алгоритма грубой силы нереалистичен.
В основном существует два хорошо известных эффективных алгоритма: алгоритм Apriori и алгоритм роста FP , для майнинга частых паттернов.Хотя наиболее эффективный алгоритм для текущей задачи должен быть определен тестами с вашими практическими входными данными, эти алгоритмы всегда являются сильными кандидатами в такой задаче.
1.Алгоритм Априори
Алгоритм априори был введен R.Агравал и Р. Срикант в 1994 году. Различные репозитории GitHub предоставляют его реализации .
Базовый обзор выглядит следующим образом.
Давайте пометим каждую строку i = 0, 1, 2, 3, 4, 5, чтобы различить «элементы» :
i = 0,1,2,3,4,5
[ 1,1,0,0,1,0,
1,1,1,0,1,1,
0,0,1,0,0,1,
1,1,1,0,1,1,
0,1,0,1,0,0,
1,1,0,1,1,0 ]
Далее мы введем фигурную скобку {...}.Например, первая строка имеет шаблон {0,1,4}, а вторая - {0,1,2,4,5}.
Сначала мы рассмотрим 6 минимальных шаблонов, C1 = { {0},{1},{2},{3},{4},{5} } и посчитаем, сколько раз эти шаблоны встречались.В этом примере все их шаблоны существуют, и мы получаем
F1 = { ({0};4), ({1};5), ({2};3), ({3};2), ({4};4), ({5};3) },
, где левые и правые значения означают элемент и частоту соответственно .Затем мы создаем объединения размером 2 из пар элементов F1 и получаем кандидатов следующего размера C2 = { {0,1},{0,2},{0,3},{0,4},{0,5},{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5} }.Подсчитав вхождения их, мы получим ...
F2 = { ({0,1};4), ({0,2};2), ({0,3};1), ({0,4};4), ({0,5};2),
({1,2};2), ({1,3};2), ({1,4};4), ({1,5};2),
({2,3};0), ({2,4};2), ({2,5};3),
({3,4};1), ({3,5};0),
({4,5};2) } ...?
В этом примере {2,3} and {3,5} не существует, и поэтому мы их удаляем.Кроме того, мы также можем удалить шаблоны {0,3} and {3,4}, потому что они встречаются только один раз и не часто.Таким образом, мы получаем
F2 = { ({0,1};4), ({0,2};2), ({0,4};4), ({0,5};2),
({1,2};2), ({1,3};2), ({1,4};4), ({1,5};2),
({2,4};2), ({2,5};3),
({4,5};2) }.
Далее мы снова создаем объединения размером 3 из пар элементов F2 и получаем следующие кандидаты:
C3 = { {0,1,2}, {0,1,4}, {0,1,5}, {0,1,3}, {0,2,4}, {0,2,5}, {0,4,5},
{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5},
{2,4,5} } ...?
Здесь мы уже знаем, что {2,3} and {3,5} не существует.Таким образом, мы можем удалить эти шаблоны. Этот шаг называется отсечением , что повышает эффективность этого алгоритма .Кроме того, мы также уже знаем, что {0,3} and {3,4} не часты.Таким образом, наш следующий кандидат -
C3 = { {0,1,2}, {0,1,4}, {0,1,5}, {0,2,4}, {0,2,5}, {0,4,5},
{1,2,4}, {1,2,5}, {1,4,5},
{2,4,5} }.
Затем мы подсчитываем их вхождения и получаем
F3 = { ({0,1,2};2), ({0,1,4};4), ({0,1,5};2), ({0,2,4};2), ({0,2,5};2), ({0,4,5};2),
({1,2,4};2), ({1,2,5};2), ({1,4,5};2),
({2,4,5};2) ).
Повторяя этот процесс, мы получаем
F4 = { ({0,1,2,4};2), ({0,1,2,5};2), ({0,1,4,5};2), ({0,2,4,5};2),
({1,2,4,5};2) },
и, наконец,
F5 = { ({0,1,2,4,5};2) }.
F6 пусто и, таким образом, к этому времени мы закончили подсчет числа встречаемости каждого частого паттерна.Результаты приведены в таблице F1 ~ F5. Мы можем определить наиболее частые шаблоны из этих таблиц.Если мы навязываем ваше условие о числе 1, ответы будут {0},{1},{4},{0,1},{0,4},{1,4} и {0,1,4}.Эти результаты сведены в один набор {0,1,4}.
Существует различных идей для улучшения алгоритма априори:
- Предварительная обработка: в данном случае удаление 0 и уменьшение памятиРазмер базы данных при первом доступе улучшит следующий процесс генерации кандидатов.
- Если мы хотим знать только самые частые шаблоны, мы можем выбросить менее частые шаблоны в каждом Fk.
- Прямое хешированиеи обрезка (DHP)
- растровое изображение, ...
2.Алгоритм роста FP
Априорный алгоритм интуитивно понятен и прост.Но в алгоритме априори мы все еще должны генерировать много кандидатов и проверять их.Чтобы избежать такого дорогостоящего процесса генерации, J был предложен алгоритм F требуемый P задний рост .Хан, Дж. Пей и Й. Инь в 2000 году. Различные репозитории GitHub снова существуют .
В этом алгоритме мы сначала подсчитываем частоту каждого элемента и сортируем их в порядке убывания.Например, в данном примере результат равен
(1;5),(4;4),(0;4),(5;3),(2;3),(3;2)
где левые и правые значения означают элемент и частоту соответственно.
Далее мы сортируем каждый шаблон строки в этом порядке.
i = 0,1,2,3,4,5
[ 1,1,0,0,1,0, --> {1,4,0}
1,1,1,0,1,1, --> {1,4,0,5,2}
0,0,1,0,0,1, --> {5,2}
1,1,1,0,1,1, --> {1,4,0,5,2}
0,1,0,1,0,0, --> {1,3}
1,1,0,1,1,0 ] --> {1,4,0,3}
Затем мы построим так называемое FP дерево следующим образом .Дерево FP - это дерево префиксов, содержащее информацию о конкурентах для частого анализа паттернов.Даже если входная база данных очень большая, результирующее дерево FP обычно компактно и помещается в основную память.
Обход узлов дерева с немного сложнымНо эффективный алгоритм подсчета, описанный выше в оригинальной статье, позволяет рассчитывать частоту каждого паттерна.Например, давайте рассмотрим следующий путь от узла красного круга 3 к корню.Этот путь начинается с 3 и представляет собой базу условных шаблонов (CPB) из 3.Паттерны, полученные вдоль этой красной линии, выглядят следующим образом, и их частоты обычно равны 1 из-за КПБ 3:
Еще один пример приведен ниже:
Таким образом, начиная со всех узлов один за другим, мы можем найти все паттерны и их частоты.Реализация этого алгоритма не так уж и сложна, и это мой быстрый DEMO с C ++ .
Наложите ваше условие насчет числа 1, мы снова найдем {0,1,4}как наиболее частая схема на этом дереве.
Существует также много интересных исследований, связанных с майнингом на основе FP деревьев.