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 превосходит.
Как это работает
Как это работает
База данных преобразуется один раз в вертикальный формат: каждый элемент отображается на свой tidset — множество идентификаторов транзакций, в которых он встречается. Это ключевая структура данных — вся последующая работа заключается в операциях над множествами (tidset'ами), а не в проходах по исходным транзакциям.
Формула
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}Поддержка набора элементов — это мощность пересечения tidset'ов его элементов, то есть количество транзакций, содержащих все эти элементы. Подсчет превращается в пересечение, что быстро, а частые одиночные элементы (те, чей tidset достаточно велик) служат отправной точкой для поиска.
Формула
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |Наборы элементов расширяются путем пересечения tidset'ов: tidset для X ∪ {y} является пересечением tidset'ов X и {y}. ECLAT исследует решетку наборов элементов в глубину в пределах классов эквивалентности (наборы элементов с общим префиксом), поэтому пересечения повторно используются, а поиск остается локальным.
Формула
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}Расширение сохраняется только в том случае, если его 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 существенное преимущество в эффективности.
Похожие методы
Источники
Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.
Открыть ссылку DOIСкопировано.