Написано впереди: алгоритм Apriori и алгоритм FP-Growth — очень классические алгоритмы майнинга, и я также периодически изучаю эти два алгоритма. Эта статья в основном отражает мое собственное понимание и разницу между этими двумя алгоритмами.Пожалуйста, дайте мне больше советов, если есть какая-либо ошибка.
Априорный алгоритм
Алгоритм Априори использует итеративный метод послойного поиска, то есть с использованием k-элементных наборов для изучения (k+1)-элементных наборов (последующиеHUI-Miner,FHNиUMEpiи другие алгоритмы такие же). Алгоритм используетсвойство замыкания вниз, то есть все непустые подмножества набора часто используемых элементов также должны быть наборами часто используемых элементов. Если набор элементов А не соответствует минимальному порогу поддержки, то есть набор элементов А не является частым, то, если набор элементов В добавляется к набору элементов А, новый набор элементов (АУБ) также не может быть частым.
Шаг алгоритма
- Просканируйте набор данных, чтобы определить поддержку каждого унарного элемента, и с помощью вычисленной поддержки вы можете получить набор всех частых 1-элементных наборов.F1;
- Используя последний обнаруженный набор (k-1) элементов, путем попарной комбинации генерируется новый набор k-элементов-кандидатов;
- Вычислить его поддержку для полученного набора элементов-кандидатов, снова просмотреть базу данных и использовать свою собственную функцию для определения всех наборов k-кандидатов, включенных в каждый элемент транзакции t;
- Удалить все наборы элементов-кандидатов, поддержка которых меньше порогового значения;
- Повторяйте шаги 2–4 до тех пор, пока не перестанут создаваться новые наборы часто встречающихся элементов, алгоритм завершает работу.
недостаток
Из приведенных выше шагов алгоритма видно, что 1) априорный алгоритм должен сканировать набор данных несколько раз, чтобы вычислить поддержку частых наборов элементов из набора элементов-кандидатов, Когда набор данных велик, стоимость ввода-вывода становится неприемлемой. 2) Во-вторых, он очень велик при создании наборов элементов-кандидатов, что обычно считается недостатком.экспоненциальный рост, что несомненно неприемлемо по потреблению памяти и времени.
преимущество
Несомненно, алгоритм Apriori, как самый ранний и самый классический алгоритм извлечения частых наборов элементов, используетаприорные свойства, создал новую идею майнинга; он прост и легок для понимания, с низкими требованиями к набору данных; наконец, алгоритм широко используется на практике и может добывать множество полезных правил ассоциации
Алгоритм роста FP
Алгоритм FP-Growth внес много улучшений в различные проблемы априорного алгоритма, особенно разработанную структуру FP-Tree для хранения ключевой информации, заимствование Tree позволяет избежать сканирования набора данных для подтверждения результатов (последующиеUP-Growth,UP-GNVиRFM-Growthи другие алгоритмы используют эту структуру хранения). Частые шаблоны могут быть сгенерированы напрямую путем рекурсивного вызова метода FP-Growth, поэтому нет необходимости генерировать шаблоны-кандидаты в течение всего процесса обнаружения.
Шаг алгоритма
- Сканировать набор данных, построить заголовок упорядоченного элемента на основе часто встречающихся унарных элементов и отсортировать каждый элемент элемента во время второго сканирования набора данных;
- Создайте структуру хранения FP-Tree на основе заголовка элемента и отсортированного набора данных.
- Создавайте наборы элементов высокого порядка снизу вверх по элементам в заголовке элемента (что также означает FP-дерево снизу вверх), и каждый набор элементов высокого порядка представляет собой путь ответвления.
недостаток
Сокращение недостаточно тщательно, и используемое граничное значение на самом деле недостаточно близко к истинной поддержке.
преимущество
FP-Tree представляет собой набор наборов данных, который не содержит данных о нечастых унарных элементах; каждый раз, когда вы ищете часто встречающиеся наборы элементов, вам не нужно повторно сканировать набор данных, нужно зафиксировать только один элемент, и каждый узел проходится снизу вверх, пока не будет построен корень из поддерева FP (проекция)
Суммировать
-
По основной идее,
- Априорный алгоритмИспользуйте два частых набора элементов низкого порядка для создания часто используемых наборов элементов высокого порядка.
- Алгоритм FP-ростаИспользуя набор часто встречающихся элементов низкого порядка в качестве предпосылки, отфильтруйте все наборы часто встречающихся элементов высокого порядка, которые содержат этот набор часто встречающихся элементов.
-
Во время реализации,
- Алгоритм Apriori должен сканировать набор данных несколько раз, чтобы подтвердить поддержку часто используемых наборов элементов.
- Алгоритм FP-Growth строит больше вложенных FP-деревьев, фиксируя узел для добычи частых наборов элементов.
-
Эти два алгоритма представляют разные идеи майнинга.Согласно этим идеям, более эффективные алгоритмы могут быть получены путем комбинирования различных стратегий сокращения и структур хранения.
Ps.Помимо изучения различий в производительности этих алгоритмов,нужно еще выяснить подноготную.Почему этот алгоритм узнают все? Почему люди не используют другие алгоритмы, которые, кажется, работают намного лучше, чем он?