O Apriori da IBM minerou o que os compradores compram juntos ao podar candidatos impossíveis

Os varejistas queriam saber quais produtos são comprados juntos, mas o número de combinações possíveis de itens explodia exponencialmente com o número de SKUs.

O Apriori, publicado em 1994, explora uma propriedade: qualquer superconjunto de um conjunto de itens infrequente deve ele próprio ser infrequente. Ele conta itens individuais, mantém os frequentes, expande-os em pares e repete, de modo que nunca conta um candidato cujo pai já falhou.

O truque converte uma busca que rapidamente se torna ingerenciável em uma que toca apenas a pequena fronteira dos conjuntos frequentes. Isso transformou a análise de cesta de mercado em uma consulta de banco de dados prática.

Se um conjunto é raro, todo superconjunto dele também é

A clausura descendente poda a busca antes que ela cresça, de modo que o tempo de execução acompanha os conjuntos frequentes, não todos os conjuntos.

Uma varredura do banco de dados por nível mantém a memória limitada aos conjuntos candidatos.

Ela fornece conjuntos frequentes exatos, não uma heurística ou uma aproximação por amostragem.

A mesma poda se generaliza para mineração de sequências e padrões além das cestas.

Antes de buscar em um espaço enorme, procure uma propriedade monotônica que permita descartar ramos inteiros de uma vez. Uma regra que elimina uma região reduz a caça de exponencial para linear.

O Apriori tornou-se o algoritmo canônico de regras de associação e uma lição padrão em mineração de dados. Ele semeou o campo que alimenta análises de recomendação, sortimento e venda cruzada, e posteriormente o fpgrowth e outros métodos que reduzem suas varreduras.