Publicado em: 9 de junho de 2024
Colaboradores: Joshua Noble
O algoritmo Apriori é um algoritmo de aprendizado de máquina não supervisionado utilizado no aprendizado de regras de associação. Aprendizado de regras de associação é uma técnica de mineração de dados que identifica padrões, conexões e dependências frequentes entre diversos grupos de itens chamados conjuntos de itens nos dados. Alguns casos de uso comuns são sistemas de previsão e recomendação de doenças, como análise de cestas de mercado para plataformas de comércio eletrônico.
Introduzido em 1994 por Rakesh Agrawal e Ramakrishnan Srikant (link fora de ibm.com) o nome, 'Apriori' reconhece o conhecimento prévio de conjuntos de itens frequentes que o algoritmo utiliza na computação. O algoritmo executa iterações sobre os dados para identificar k-itemsets, ou seja, k itens que frequentemente ocorrem juntos. Em seguida, ele utiliza os k-itemsets para identificar os k+1 itemsets. O algoritmo Apriori se baseia na ideia 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.
Etapa 1: geração de conjuntos de itens frequentes
Primeiro o algoritmo identifica os itens exclusivos, às vezes chamados de conjuntos de itens individuais, no conjunto de dados, com suas frequências. Em seguida, combina os itens que aparecem juntos com uma probabilidade acima de um limite especificado em conjuntos de itens candidatos e filtra os conjuntos de itens pouco frequentes para reduzir o custo de computação em etapas posteriores. Esse processo, conhecido como mineração de conjuntos de itens frequentes, procura somente conjuntos de itens com frequências consideráveis.
Etapa 2: expansão e posterior poda de conjuntos de itens
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.
Etapa 3: repete as etapas 1 e 2
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.
Saiba mais sobre as barreiras à adoção da IA, particularmente a falta de soluções de governança e gerenciamento de riscos da IA.
Cadastre-se para receber o guia sobre modelos de base
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.
onde IA é o item A, Occ(IA) é o número de ocorrências do item A e S(IA) = 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:
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:
onde A é o antecedente, B é o consequente e C(A,B) é a confiança de que A leva a B.
Estendendo o exemplo anterior, suponha que haja 150 transações onde maçãs e bananas foram compradas juntas. A confiança é calculada como:
Esse resultado indica uma chance de 60% de que uma compra de maçã leve a uma compra de banana. Da mesma forma, assumindo um total de 500 transações para bananas, então a confiança de que uma compra de banana leva a uma compra de maçã é calculada da seguinte forma:
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 com o qual a probabilidade de o item A levar ao item B é maior do que a probabilidade do item A. Essa métrica quantifica a força da associação entre A e B. Ela pode ajudar a indicar se há uma relação real entre os itens do conjunto de itens ou se estão sendo agrupados por coincidência.
Onde LA, B é o aumento do item A que leva ao item B, CA, B é a confiança de que o item A leva ao item B, SA é o suporte para o item A.
Para o exemplo acima, vemos que:
O alto valor de elevação indica que a probabilidade de maçãs e bananas serem compradas juntas é 4,8 vezes maior do que a de maçãs serem compradas sozinhas. Além disso, pode-se observar que:
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 (link fora de ibm.com) para calcular os limites de suporte e confiança de cada regra e, em seguida, podar as regras que não atendem a um limite pode ser computacionalmente proibitivo. Para tornar a aplicação do algoritmo Apriori mais eficiente, ele é frequentemente combinado com outras técnicas de mineração de regras de associação. Dois dos mais comuns são o algoritmo FP-growth (link fora do ibm.com) e sua variante FP-Max para reduzir as restrições de memória e computação. O algoritmo Apriori também pode ser combinado com Decision Trees, em que o algoritmo Apriori identifica o conjunto de itens frequente e a técnica da árvore de decisão ajuda a identificar as regras de associação.
Outra variante popular do algoritmo Apriori é a Contagem dinâmica de conjuntos de itens (DIC) (link fora do ibm.com), que começa a contar os possíveis conjuntos de itens mais cedo, sem esperar que todas as transações sejam registradas. O 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 Apriori também podem ser úteis em aplicativos de inteligência artificial baseados em aprendizado não supervisionado, como os algoritmos de agrupamento quando os dados permitem. Ele ajuda a identificar relacionamentos 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 utilizado para encontrar regras de associação forte entre sintomas e doenças, para melhorar a eficiência do diagnóstico e elaborar planos de tratamento direcionados. Por exemplo, quais pacientes têm maior probabilidade de desenvolver diabetes (link fora de ibm.com) ou o papel que a dieta ou o estilo de vida desempenham na doença (link fora de ibm.com). Também pode auxiliar na identificação de 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.
Saiba como implementar o algoritmo Apriori em Python utilizando o watsonx
Saiba como implementar o algoritmo Apriori com a linguagem de programação R com o watsonx.
Aprenda sobre o clustering, um algoritmo de aprendizado de máquina não supervisionado que organiza e classifica diferentes objetos, pontos de dados ou observações em grupos ou clusters com base em semelhanças ou padrões.