Mineração ECLAT de Conjuntos de Itens Frequentes
- Proposto por
- Mohammed J. Zaki
- Ano
- 2000
- Tipo
- Frequent-itemset mining algorithm (vertical format)
- Família
- Pattern mining
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
ECLAT, introduzido por Mohammed Zaki em 2000, minera conjuntos de itens frequentes usando uma representação vertical de dados: em vez de escanear transações, ele armazena para cada item o conjunto de IDs de transação (um tidset) que o contêm, e computa o suporte de qualquer conjunto de itens pela interseção de tidsets.
Essa abordagem de profundidade, baseada em interseção, é rápida e eficiente em memória, uma alternativa aos escaneamentos horizontais do Apriori e à árvore do FP-Growth.
A intuição por trás do método
A maioria dos mineradores de conjuntos de itens pensa linha por linha: quais itens estão em cada transação? ECLAT vira a mesa de lado. Para cada item, ele mantém uma lista das transações que o contêm. Agora o suporte de um par de itens é apenas o tamanho da sobreposição de suas duas listas — uma simples interseção de conjuntos — e você nunca escaneia o banco de dados novamente. Para encontrar conjuntos de itens frequentes mais longos, intercepte as listas de conjuntos mais curtos. Caminhar em profundidade e podar sempre que uma interseção fica muito pequena enumera eficientemente todos os conjuntos de itens frequentes.
História
Mohammed Zaki introduziu ECLAT e o paradigma de mineração vertical em trabalhos que culminaram em seu artigo de 2000 na IEEE TKDE sobre mineração escalável de associações, refinando-o mais tarde com diffsets (dECLAT). Ele se juntou ao Apriori (1994, geração de candidatos horizontal) e FP-Growth (2000, baseado em árvore) como uma das três famílias canônicas de algoritmos de conjuntos de itens frequentes, cada um trocando escaneamentos, memória e densidade de dados de maneiras diferentes. ECLAT permanece uma opção padrão em toolkits de mineração de dados.
Quando usar
Use ECLAT para mineração de conjuntos de itens frequentes quando uma abordagem vertical baseada em interseção se adequa aos dados — é frequentemente muito rápida em conjuntos de dados densos e evita escaneamentos repetidos do banco de dados, tornando-a uma alternativa forte ao Apriori e uma igual ao FP-Growth. Ela brilha quando os tidsets são de tamanho moderado e cabem na memória, e a variante diffset lida bem com dados densos. Seus custos: tidsets para itens frequentes podem ser grandes e pesados em memória em grandes conjuntos de dados esparsos, interseções intermediárias adicionam sobrecarga, e como toda mineração baseada em suporte, é sensível ao limiar mínimo de suporte. Como sempre, conjuntos de itens frequentes são apenas o primeiro estágio; regras de associação com confiança/lift são geradas depois. Escolha entre ECLAT, FP-Growth e Apriori com base na densidade dos dados e na memória.
Limitações e considerações
- Tidsets para itens frequentes podem ser grandes, custando memória em grandes conjuntos de dados.
- Resultados de interseção intermediários adicionam sobrecarga de memória/tempo.
- Menos intuitivo que representações horizontais (Apriori).
- Sensível ao limiar mínimo de suporte, como toda mineração de conjuntos de itens.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Suporte computado por rápidas interseções de tidsets — sem escaneamentos repetidos do banco de dados.
- Busca em profundidade com classes de equivalência de prefixo reutiliza trabalho e localiza a memória.
- Frequentemente muito eficiente em conjuntos de dados densos, competitivo com FP-Growth.
- A otimização diffset reduz ainda mais a memória e o custo de interseção.
Aplicações
- Mineração de cestas de compras e associações de varejo.
- Análise de co-ocorrência de web e clickstream.
- Descoberta de co-ocorrência frequente em bioinformática.
- Qualquer tarefa de conjuntos de itens frequentes que favoreça uma abordagem vertical baseada em interseção.
- Conjuntos de dados transacionais densos onde o ECLAT diffset se destaca.
Como funciona
Como funciona
O banco de dados é transformado uma vez em formato vertical: cada item mapeia para seu tidset, o conjunto de IDs de transação nos quais ele aparece. Esta é a estrutura de dados chave — todo o trabalho subsequente são operações de conjunto em tidsets, não passagens sobre as transações originais.
Fórmula
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}O suporte de um conjunto de itens é a cardinalidade da interseção dos tidsets de seus itens — o número de transações que contêm todos eles. A contagem se torna interseção, o que é rápido, e itens únicos frequentes (aqueles cujo tidset é grande o suficiente) semeiam a busca.
Fórmula
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |Conjuntos de itens são estendidos pela interseção de tidsets: o tidset de X ∪ {y} é a interseção dos tidsets de X e {y}. ECLAT explora o reticulado de conjuntos de itens em profundidade dentro de classes de equivalência (conjuntos de itens compartilhando um prefixo), de modo que as interseções são reutilizadas e a busca permanece local.
Fórmula
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}Uma extensão é mantida apenas se seu tidset (e, portanto, suporte) atende ao limiar mínimo de suporte; caso contrário, esse ramo é podado (anti-monotonicidade: nenhum superconjunto pode ser frequente). Diffsets — armazenando apenas as diferenças entre tidsets — são uma otimização comum que encolhe ainda mais a memória e o custo de interseção.
Fórmula
\text{keep extensions with } \text{support} \ge \text{minsup}Erros comuns
- Mineração de dados esparsos muito grandes onde tidsets explodem a memória — considere diffsets ou FP-Growth.
- Definir o suporte mínimo muito baixo e produzir um número incontrolável de conjuntos de itens.
- Confundir conjuntos de itens frequentes com regras de associação (regras são um passo separado).
- Ignorar a variante diffset em dados densos onde ela ajuda muito.
Perguntas frequentes
Como o ECLAT difere do Apriori e do FP-Growth?
Todos os três encontram conjuntos de itens frequentes. Apriori usa um formato horizontal com geração de candidatos e muitos escaneamentos; FP-Growth comprime dados em uma árvore e minera recursivamente; ECLAT usa um formato vertical de tidset e computa o suporte pela interseção de listas de IDs de transação em profundidade. ECLAT e FP-Growth evitam os escaneamentos repetidos do Apriori.
O que é um tidset?
Um tidset (conjunto de IDs de transação) é a lista de transações que contêm um determinado item ou conjunto de itens. ECLAT os armazena verticalmente e computa o suporte de um conjunto de itens como o tamanho da interseção dos tidsets de seus itens, transformando a contagem em interseção de conjuntos.
O que são diffsets?
Diffsets armazenam apenas a diferença entre o tidset de um conjunto de itens e o de seu pai, em vez do tidset completo. Em dados densos, isso reduz drasticamente a memória e o custo de interseção, dando à variante dECLAT uma vantagem substancial de eficiência.
Métodos relacionados
Fontes
Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.
Abrir referência DOICopiado.