O que é o algoritmo Apriori?

Lançado em 1994 por Rakesh Agrawal e Ramakrishnan Srikant o nome, "Apriori" reconhece o conhecimento prévio de conjuntos de itens frequentes que o algoritmo usa na computação. O algoritmo executa iterações sobre os dados para identificar k conjuntos de itens, ou seja, k itens que frequentemente ocorrem juntos. Em seguida, ele utiliza os k conjuntos de itens para identificar os k+1 conjuntos de itens. O algoritmo A priori se baseia no insight de que adicionar itens a um grupo comprado com frequência só pode torná-lo menos frequente, não mais. O processo depende da propriedade Apriori que afirma que, se um conjunto de itens aparecer com frequência em um conjunto de dados, todos os seus subconjuntos também deverão ser frequentes. Por outro lado, se um conjunto de itens for identificado como pouco frequente, todos os seus superconjuntos serão considerados infrequentes.

O algoritmo Apriori é aplicável a todos os tipos de conjuntos de dados, especialmente aqueles gerados por bancos de dados transacionais, e é frequentemente utilizado para análise de cestas de mercado para dar suporte a sistemas de recomendação. Por exemplo, ao utilizar uma plataforma de comércio eletrônico que vende roupas e sapatos, um comprador pesquisa sapatos e decide adicionar um par de sapatos pretos formais ao carrinho de compras. O comprador, então, percebe que a interface recomenda a compra de outros itens, como meias. Uma das maneiras pelas quais esse sistema de recomendação funciona é aprender os padrões de compra dos clientes e associar itens que provavelmente tenham sido comprados juntos.

Uma das maiores vantagens de se utilizar o algoritmo Apriori é sua simplicidade e adaptabilidade. No entanto, os algoritmos Apriori não são tão eficientes para lidar com grandes conjuntos de dados. O processo de iteração múltipla da geração de candidatos ao conjunto de itens pode se tornar computacionalmente caro e intensivo em memória. O Apriori é frequentemente combinado com outras técnicas para mitigar esses problemas.

A função Apriori é integrada a muitas linguagens de programação populares, inclusive Python, Java e R, facilitando a integração de regras de associação de qualidade junto com conjuntos de itens frequentes em aplicativos ou sistemas existentes.

Cada uma das principais etapas do algoritmo Apriori procura identificar conjuntos de itens e todos os seus possíveis superconjuntos procurando os mais frequentes para criar as regras de associação.

O algoritmo primeiro identifica os itens únicos no conjunto de dados, às vezes chamados de 1-itemsets, juntamente com suas frequências. Em seguida, combina os itens que aparecem juntos com uma probabilidade acima de um limite especificado, formando itemsets candidatos e eliminando itemsets infrequentes para reduzir o custo computacional nas próximas etapas. Esse processo, conhecido como mineração de itemsets frequentes, busca apenas itemsets com frequências significativas.

Utilizando a propriedade Apriori, o algoritmo combina conjuntos de itens frequentes para formar conjuntos de itens maiores. As combinações de conjuntos de itens maiores com menor probabilidade são removidas. Isso reduz ainda mais o espaço de pesquisa e torna a computação mais eficiente.

O algoritmo repete as etapas 1 e 2 até que todos os conjuntos de itens frequentes que atendem à probabilidade de limite definida sejam gerados exaustivamente. Cada iteração gera associações mais complexas e abrangentes nos conjuntos de itens.

Depois que o Apriori tiver criado os conjuntos de itens, a força das associações e relações geradas poderá ser investigada.

O algoritmo do Apriori utiliza as métricas de suporte, confiança e elevação para definir os critérios operacionais e melhorar a eficiência do desempenho.

O suporte é definido como a relação entre o número de vezes que um item ocorre nas transações e o número total de transações. Essa métrica, portanto, define a probabilidade de ocorrência de cada item individual nas transações. A mesma lógica pode ser estendida aos conjuntos de itens.

$S\left(I_A\right)=\frac{Occ\left(I_A\right)}{TotalTransactions}$

onde I_A é o item A, Occ(I_A) é o número de ocorrências do item A e S(I_A) = suporte do item A

Por exemplo, em uma loja de varejo, 250 entre 2.000 transações em um dia podem incluir uma compra de maçãs. Utilizando a fórmula:

$S\left(I_{Apples}\right)=\frac{250}{2000}=0.125$

Esse resultado implica que há uma chance de 12,5% de que tenham sido compradas maçãs naquele dia.

Você pode indicar um limite mínimo de suporte quando aplicar o algoritmo Apriori. Isso significa que qualquer item ou conjunto de itens com suporte menor do que o suporte mínimo especificado será considerado infrequente.

A métrica de confiança identifica a probabilidade de itens ou conjuntos de itens ocorrerem juntos nos conjuntos de itens. Por exemplo, se houver dois itens em uma transação, pressupõe-se que a existência de um item leve à outra. O primeiro item ou conjunto de itens é o antecedente e o segundo é o consequente. A confiança é, portanto, definida como a razão entre o número de transações com tanto o antecedente como o consequente para o número de transações que têm apenas o antecedente. Esse cenário é representado como:

$C(A,B)=\frac{Occ(A\cap B)}{Occ\left(A\right)}$

onde A é o antecedente, B é o consequente e C(A,B) é a confiança de que A leva a B.

Ampliando o exemplo anterior, suponha que haja 150 transações onde maçãs e bananas foram compradas juntas. A confiança é calculada como:

$C(Apples,Bananas)=\frac{150}{250}=0.6$

Esse resultado indica uma chance de 60% de que uma compra de maçã leve a uma compra de banana. Da mesma forma, suponha que haja um total de 500 transações de bananas, então a confiança de que uma compra de banana leva a uma compra de maçã é calculada como:

$C(Bananas,Apples)=\frac{150}{500}=0.3$

Aqui, há apenas 30% de chance de que uma compra de banana leve a uma compra de maçã.

Embora a confiança seja uma boa medida de probabilidade, não é uma garantia de uma associação clara entre os itens. O valor da confiança pode ser alto por outros motivos. Por esse motivo, um limite mínimo de confiança é aplicado para filtrar associações fracamente prováveis durante a mineração com regras de associação.

Lift é o fator que indica o quanto a probabilidade de o item A levar ao item B é maior do que a probabilidade isolada de A ocorrer. Essa métrica quantifica a força da associação entre A e B, ajudando a determinar se existe uma relação real entre os itens do itemset ou se foram agrupados por coincidência. 

$L(A,B)=\frac{C(A,B)}{S\left(A\right)}$ 


Onde L_{A, B} é o aumento do item A que leva ao item B, C_{A, B} é a confiança de que o item A leva ao item B, S_A é o suporte para o item A.

No exemplo acima, podemos observar que: 

$L(Apples,Bananas)=\frac{0.6}{0.125}=4.8$

O alto valor de lift indica que a probabilidade de maçãs e bananas serem compradas juntas é 4,8 vezes maior do que a probabilidade de maçãs serem compradas sozinhas. Além disso, pode-se observar que: 

$L(Bananas,Apples)=\frac{0.3}{0.25}=1.2$

O baixo valor de aumento aqui indica que uma compra de banana levando a uma compra de maçã pode ser apenas uma coincidência.

Em muitos casos, aplicar uma abordagem de força bruta para calcular os limites de suporte e confiança para cada regra e, em seguida, podar as regras que não atingem um limite pode ser computacionalmente proibitivo. Para tornar a aplicação do algoritmo Apriori mais eficiente, ele geralmente é combinado com outras técnicas de mineração de regras de associação. Dois dos mais comuns são o algoritmo de crescimento FP e sua variante FP-Max, para reduzir restrições de memória e computação. O algoritmo Apriori também pode ser combinado com árvores de decisão, onde o algoritmo Apriori identifica o conjuntos de itens frequente, e a técnica de árvore de decisão ajuda a identificar as regras de associação.

Outra variante popular do algoritmo Apriori é a Dynamic Itemset Counting (DIC) (link externo a ibm.com), que começa a contar os possíveis conjuntos de itens mais cedo, sem esperar que todas as transações sejam registradas. A DIC divide o conjunto de dados em segmentos menores e processa cada segmento em separado. Essa segmentação possibilita a interrupção antecipada quando o algoritmo não consegue identificar nenhum conjunto de itens frequente, mas o particionamento dos dados também ajuda a reduzir consideravelmente o custo de computação.

Os algoritmos a priori também podem ser úteis em aplicações de inteligência artificial baseadas em aprendizado não supervisionado, como algoritmos de agrupamento, quando os dados são compatíveis com esse tipo de análise. Eles permitem identificar relações e associações entre entidades aparentemente independentes, agrupando-as em possíveis clusters.

A descoberta e o agrupamento de conjuntos de itens tem várias aplicações e o algoritmo Apriori também é conhecido como a primeira coisa que os mineradores de dados tentam devido à sua versatilidade. Veremos alguns dos casos de uso comuns em diversos setores.

Uma das aplicações mais comuns do algoritmo da Apriori é a análise de carrinho de compras. Os varejistas analisam o histórico de compras dos clientes e otimizam a disposição das lojas, colocando itens comprados com frequência próximos uns dos outros ou na mesma prateleira. As plataformas de e-commerce utilizam algoritmos Apriori para estudar relacionamentos baseados em produtos com base nas preferências do usuário e análise de mineração de padrões de compra para criar sistemas eficientes de recomendação de clientes. O mesmo tipo de análise pode ser utilizado para otimizar a aquisição de serviços, como escolher cursos de treinamento de um catálogo ou recomendar outros tipos de cobertura na escolha do seguro.

O algoritmo Apriori pode ser usado para encontrar regras de associação fortes entre sintomas e doenças para melhorar a eficiência do diagnóstico e elaborar planos de tratamento direcionados. Por exemplo, quais pacientes provavelmente desenvolverão diabetes ou o papel que a dieta ou o estilo de vida desempenham na doença. Também pode ajudar a identificar fatores associados a reações adversas a medicamentos.

Os algoritmos a priori também são aplicáveis em bancos de dados não transacionais. Os analistas de dados geralmente utilizam o Apriori para minerar o uso da web, analisar dados de sequência de cliques e interpretar o comportamento do usuário.

Outra aplicação comum do algoritmo da Apriori é identificar padrões fraudulentos em transações financeiras. A identificação de padrões de compra específicos como possivelmente fraudulentos possibilita que uma instituição financeira aja rapidamente para suspender transações ou entrar em contato com o titular da conta.