Skip to content
Назад к результатам поиска

ECLAT Frequent-Itemset Mining

Автор метода
Mohammed J. Zaki
Год
2000
Тип
Frequent-itemset mining algorithm (vertical format)
Семейство
Pattern mining

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

ECLAT, представленный Мохаммедом Заки в 2000 году, осуществляет поиск частых наборов элементов, используя вертикальное представление данных: вместо сканирования транзакций он хранит для каждого элемента множество идентификаторов транзакций (tidset), которые его содержат, и вычисляет поддержку любого набора элементов путем пересечения tidset'ов.

Этот подход, основанный на пересечениях и поиске в глубину, быстр и эффективен по памяти, являясь альтернативой горизонтальным сканированиям Apriori и древовидному представлению FP-Growth.

Интуиция метода

Большинство алгоритмов поиска наборов элементов работают построчно: какие элементы содержатся в каждой транзакции? ECLAT переворачивает эту парадигму. Для каждого элемента он хранит список транзакций, которые его содержат. Теперь поддержка пары элементов — это просто размер пересечения их списков, то есть простое пересечение множеств, и вам никогда не придется повторно сканировать базу данных. Чтобы найти более длинные частые наборы элементов, нужно пересекать списки более коротких. Обход в глубину и отсечение ветвей, когда пересечение становится слишком малым, эффективно перечисляют все частые наборы элементов.

История

Мохаммед Заки представил ECLAT и парадигму вертикального майнинга в работе, кульминацией которой стала его статья 2000 года в IEEE TKDE по масштабируемому майнингу ассоциаций, позже уточнив ее с помощью diffset'ов (dECLAT). Он присоединился к Apriori (1994, генерация кандидатов в горизонтальном формате) и FP-Growth (2000, на основе деревьев) как к одному из трех канонических семейств алгоритмов поиска частых наборов элементов, каждый из которых по-разному балансирует между сканированиями, памятью и плотностью данных. ECLAT остается стандартным вариантом в инструментариях интеллектуального анализа данных.

Когда применять

Используйте ECLAT для поиска частых наборов элементов, когда вертикальный подход, основанный на пересечениях, подходит для данных — он часто очень быстр на плотных наборах данных и позволяет избежать повторных сканирований базы данных, что делает его сильной альтернативой Apriori и конкурентом FP-Growth. Он превосходен, когда tidset'ы имеют умеренный размер и помещаются в памяти, а вариант diffset хорошо работает с плотными данными. Его недостатки: tidset'ы для частых элементов могут быть большими и требовать много памяти на больших разреженных наборах данных, промежуточные пересечения добавляют накладные расходы, и, как и все методы, основанные на поддержке, он чувствителен к минимальному порогу поддержки. Как всегда, частые наборы элементов — это только первый этап; правила ассоциации с достоверностью/подъемом генерируются впоследствии. Выбирайте между ECLAT, FP-Growth и Apriori в зависимости от плотности данных и объема памяти.

Ограничения и замечания

  • Tidset'ы для частых элементов могут быть большими, требуя много памяти на больших наборах данных.
  • Промежуточные результаты пересечения добавляют накладные расходы на память/время.
  • Менее интуитивен, чем горизонтальные представления (Apriori).
  • Чувствителен к минимальному порогу поддержки, как и все алгоритмы поиска наборов элементов.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Поддержка вычисляется путем быстрого пересечения tidset'ов — без повторных сканирований базы данных.
  • Поиск в глубину с классами эквивалентности по префиксу повторно использует вычисления и локализует память.
  • Часто очень эффективен на плотных наборах данных, конкурентоспособен с FP-Growth.
  • Оптимизация diffset дополнительно снижает потребление памяти и стоимость пересечения.

Применение

  • Анализ рыночной корзины и ассоциаций в розничной торговле.
  • Анализ совместной встречаемости веб-трафика и кликстрима.
  • Поиск частых совместных встречаемостей в биоинформатике.
  • Любая задача поиска частых наборов элементов, предпочитающая вертикальный подход, основанный на пересечениях.
  • Плотные транзакционные наборы данных, где diffset ECLAT превосходит.

Как это работает

Как это работает

1

База данных преобразуется один раз в вертикальный формат: каждый элемент отображается на свой tidset — множество идентификаторов транзакций, в которых он встречается. Это ключевая структура данных — вся последующая работа заключается в операциях над множествами (tidset'ами), а не в проходах по исходным транзакциям.

Формула
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

Поддержка набора элементов — это мощность пересечения tidset'ов его элементов, то есть количество транзакций, содержащих все эти элементы. Подсчет превращается в пересечение, что быстро, а частые одиночные элементы (те, чей tidset достаточно велик) служат отправной точкой для поиска.

Формула
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

Наборы элементов расширяются путем пересечения tidset'ов: tidset для X ∪ {y} является пересечением tidset'ов X и {y}. ECLAT исследует решетку наборов элементов в глубину в пределах классов эквивалентности (наборы элементов с общим префиксом), поэтому пересечения повторно используются, а поиск остается локальным.

Формула
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

Расширение сохраняется только в том случае, если его tidset (и, следовательно, поддержка) соответствует минимальному порогу поддержки; в противном случае эта ветвь отсекается (антимонотонность: ни один надмножество не может быть частым). Diffset'ы — хранение только различий между tidset'ами — являются распространенной оптимизацией, которая дополнительно сокращает объем памяти и стоимость пересечения.

Формула
\text{keep extensions with } \text{support} \ge \text{minsup}

Частые ошибки

  • Поиск очень больших разреженных данных, где tidset'ы раздувают память — рассмотрите diffset'ы или FP-Growth.
  • Установка слишком низкого минимального порога поддержки, что приводит к неуправляемому количеству наборов элементов.
  • Путаница между частыми наборами элементов и правилами ассоциации (правила — отдельный этап).
  • Игнорирование варианта diffset на плотных данных, где он значительно помогает.

Часто задаваемые вопросы

Чем ECLAT отличается от Apriori и FP-Growth?

Все три алгоритма находят частые наборы элементов. Apriori использует горизонтальный формат с генерацией кандидатов и множеством сканирований; FP-Growth сжимает данные в дерево и выполняет рекурсивный поиск; ECLAT использует вертикальный формат tidset и вычисляет поддержку путем пересечения списков идентификаторов транзакций в глубину. ECLAT и FP-Growth избегают повторных сканирований Apriori.

Что такое tidset?

Tidset (множество идентификаторов транзакций) — это список транзакций, содержащих данный элемент или набор элементов. ECLAT хранит их вертикально и вычисляет поддержку набора элементов как мощность пересечения tidset'ов его элементов, превращая подсчет в пересечение множеств.

Что такое diffset'ы?

Diffset'ы хранят только разницу между tidset'ом набора элементов и tidset'ом его родителя, а не полный tidset. На плотных данных это значительно снижает потребление памяти и стоимость пересечения, давая варианту dECLAT существенное преимущество в эффективности.

Похожие методы

Источники

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    Открыть ссылку DOI
    Скопировано.