FPGrowth все еще считается «состоянием искусства» в частых майнингах узора?

Question

Насколько я знаю, разработка алгоритмов для решения задачи частых шаблонов (FPM), дорога улучшений имеет некоторые основные контрольно -пропускные пункты. Во -первых, Априори Алгоритм был предложен в 1993 году Agrawal et al., вместе с формализацией проблемы. Алгоритм смог сдирать Некоторые наборы из 2^n - 1 Наборы (PowerSet) с помощью решетки для поддержания данных. Недостатком подхода была необходимость перечитать базу данных для вычисления частоты каждого набора расширенного.

Позже, в 1997 году, Zaki et al. предложил алгоритм Эклат, который вставлено Полученная частота каждого набора внутри решетки. Это было сделано путем добавления в каждый узел решетки, набор транзакционных иментов, которые имели элементы от корня в указанный узел. Основным вкладом является то, что не нужно перечитать весь набор данных, чтобы узнать частоту каждого набора, но память, необходимая для поддержания такой структуры данных, может превышать размер самого набора данных.

В 2000 году, Han et al. предложил алгоритм под названием Fpgrowth, наряду с структурой данных префикса под названием FPTree. Алгоритм смог обеспечить значительное сжатие данных, а также предоставив, что только частые наборы предметов будут получены (без кандидата в генерацию элементов). Это было сделано в основном путем сортировки элементов каждой транзакции в порядке уменьшения, так что наиболее частыми элементами являются те, которые с наименьшими повторениями в структуре данных дерева. Поскольку частота спускается только при прохождении дерева, алгоритм способен сдирать Нечастые наборы предметов.

Редактировать:

Насколько я знаю, это можно считать современным алгоритмом, но я хотел бы знать о других предлагаемых решениях. Какие еще алгоритмы для FPM считаются «современным»? Что это интуиция/Основное управление таких алгоритмов?

Является ли алгоритм FPGrowth по -прежнему считается «состоянием искусства» в частых майнингах? Если нет, то какой алгоритм может более эффективно извлекать частые наборы элементов из крупных наборов данных?

Answer 1

Состояние искусства, как в: Используется на практике или работал в теории?

Apriori используется повсюду, за исключением разработки новых алгоритмов частых элементов. Его легко реализовать и легко использовать в очень разных областях. Вы найдете сотни реализаций Apriori различного качества. И на самом деле легко ошибаться.

FPGrowth гораздо сложнее реализовать, но также гораздо интереснее. Таким образом, с академической точки зрения, все пытаются улучшить FPGrowth - получить работу, основанную на принятых Apriori, будет очень сложным.

Если у вас хорошая реализация, у каждого алгоритма есть это хорошо, и, на мой взгляд, это плохие ситуации. Хорошая реализация Apriori будет Только необходимо сканировать базу данных k раз, чтобы найти все частые наборы предметов длины k. Анкет В частности, если ваши данные вписываются в основную память, это дешево. То, что может убить Apriori,-это слишком много частых 2 элементов (в частности, когда вы не используете TRIE и аналогичные методы ускорения и т. Д.). Он работает лучше всего на больших данных с низким количеством частых наборов элементов.

Eclat работает на столбцах; Но это должно читать каждый столбец гораздо чаще. Есть некоторая работа над различиями, чтобы уменьшить эту работу. Если ваши данные не вписываются в основную память, Eclat страдает, вероятно, больше, чем Apriori. Сначала пройдя глубину, он также сможет вернуть первый интересный результат намного раньше, чем Apriori, и вы можете использовать эти результаты для настройки параметров; Таким образом, вам нужно меньше итераций, чтобы найти хорошие параметры. Но по дизайну он не может использовать обрезку так же аккуратно, как и Apriori.

FPGrowth сжимает набор данных в дерево. Это работает лучше всего, когда у вас много дублирующих записей. Вероятно, вы могли бы пожинать довольно некоторых выгод для Apriori и Eclat, если вы сможете преподносить свои данные и слияние дубликатов в взвешенные векторы. FPGrowth делает это на крайнем уровне. Недостатком является то, что реализация намного сложнее; И как только это дерево больше не вписывается в память, оно получает беспорядок для реализации.

Что касается результатов производительности и критериев - не доверяйте им. Есть так много вещей, чтобы реализовать неправильно. Попробуйте 10 различных реализаций, и вы получите 10 очень разных результатов производительности. В частности, для Apriori, у меня сложилось впечатление, что большинство реализаций разбиты в смысле пропустить некоторые основные вклады Apriori ... и из тех, у кого есть эти части правильно, качество оптимизации сильно варьируется.

На самом деле есть даже статьи о том, как эффективно реализовать эти алгоритмы:

Эффективные реализации Apriori и Eclat.
Кристиан Боргельт
Семинар частых реализаций набора элементов (FIMI 2003, Мельбурн, Флорида, США).

Вы также можете прочитать эти опросы об этом домене:

• Goethals, Барт. «Опрос по частым майнингам». Univ. Хельсинки (2003).

• Ференк Бодон, опрос по частым добыче предметов, технический отчет, Будапештский университет технологий и экономики, 2006,

• Частое набор элементов добыча
  Кристиан Боргельт
  Междисциплинарные обзоры Wiley: Раскрытие данных и обнаружение знаний 2 (6): 437-456. 2012

Answer 2

Большинство недавних частых подходов, которые я видел в литературе, основаны на оптимизации FPGrowth. Я должен признать, что я не видел много событий в литературе в FPM в течение многих лет.

Этот викибук Выделит многие варианты на FPGrowth, которые существуют.