Algoritmo de crescimento de padrão frequente (FP) em mineração de dados

frequent pattern growth algorithm data mining

Tutorial detalhado sobre algoritmo de crescimento de padrão frequente que representa o banco de dados na forma de uma árvore de FP. Inclui comparação de crescimento de FP vs. Apriori:

Algoritmo Apriori foi explicado em detalhes em nosso tutorial anterior. Neste tutorial, aprenderemos sobre Frequent Pattern Growth - FP Growth é um método de mineração de conjuntos de itens frequentes.

algoritmo de classificação de seleção c ++

Como todos sabemos, Apriori é um algoritmo para mineração de padrões frequente que se concentra em gerar conjuntos de itens e descobrir o conjunto de itens mais frequente. Isso reduz bastante o tamanho do conjunto de itens no banco de dados; no entanto, o Apriori também tem suas próprias deficiências.

Leia nosso Série inteira de treinamento de mineração de dados para um conhecimento completo do conceito.

O que você aprenderá:

• Deficiências do algoritmo apriori
• Algoritmo de crescimento de padrão frequente
• Árvore FP
• Etapas do algoritmo de padrão frequente
• Exemplo de algoritmo de crescimento FP
• Vantagens do algoritmo de crescimento FP
• Desvantagens do algoritmo de crescimento FP
• Crescimento FP vs Apriori
• ECLAT
• Conclusão
• Leitura recomendada

Deficiências do algoritmo apriori

1. O uso de Apriori requer uma geração de conjuntos de itens candidatos. Esses conjuntos de itens podem ser grandes em número se o conjunto de itens no banco de dados for enorme.
2. A priori, são necessárias várias varreduras do banco de dados para verificar o suporte de cada conjunto de itens gerado e isso acarreta custos elevados.

Essas deficiências podem ser superadas usando o algoritmo de crescimento FP.

Algoritmo de crescimento de padrão frequente

Este algoritmo é uma melhoria do método Apriori. Um padrão frequente é gerado sem a necessidade de geração de candidatos. O algoritmo de crescimento FP representa o banco de dados na forma de uma árvore chamada árvore de padrão frequente ou árvore FP.

Esta estrutura em árvore manterá a associação entre os conjuntos de itens. O banco de dados é fragmentado usando um item frequente. Essa parte fragmentada é chamada de “fragmento de padrão”. Os conjuntos de itens desses padrões fragmentados são analisados. Assim, com este método, a busca por conjuntos de itens frequentes é reduzida comparativamente.

Árvore FP

Frequent Pattern Tree é uma estrutura semelhante a uma árvore feita com os conjuntos de itens iniciais do banco de dados. O objetivo da árvore FP é extrair o padrão mais frequente. Cada nó da árvore FP representa um item do conjunto de itens.

O nó raiz representa nulo, enquanto os nós inferiores representam os conjuntos de itens. A associação dos nós com os nós inferiores, que são os conjuntos de itens com os outros conjuntos de itens, é mantida durante a formação da árvore.

Etapas do algoritmo de padrão frequente

O método de crescimento de padrão frequente nos permite encontrar o padrão frequente sem geração de candidato.

Vamos ver as etapas seguidas para explorar o padrão frequente usando o algoritmo de crescimento de padrão frequente:

# 1) A primeira etapa é verificar o banco de dados para encontrar as ocorrências dos conjuntos de itens no banco de dados. Esta etapa é igual à primeira etapa do Apriori. A contagem de conjuntos de 1 item no banco de dados é chamada de contagem de suporte ou frequência de conjunto de 1 item.

diferença entre sql e sql server

#dois) O segundo passo é construir a árvore FP. Para isso, crie a raiz da árvore. A raiz é representada por nulo.

# 3) A próxima etapa é verificar o banco de dados novamente e examinar as transações. Examine a primeira transação e descubra o conjunto de itens nela. O conjunto de itens com a contagem máxima é obtido no topo, o próximo conjunto de itens com contagem inferior e assim por diante. Isso significa que o ramo da árvore é construído com conjuntos de itens de transação em ordem decrescente de contagem.

# 4) A próxima transação no banco de dados é examinada. Os conjuntos de itens são ordenados em ordem decrescente de contagem. Se qualquer conjunto de itens desta transação já estiver presente em outra ramificação (por exemplo, na 1ª transação), esta ramificação da transação compartilhará um prefixo comum para a raiz.

Isso significa que o conjunto de itens comum está vinculado ao novo nó de outro conjunto de itens nesta transação.

# 5) Além disso, a contagem do conjunto de itens é incrementada à medida que ocorre nas transações. Tanto o nó comum quanto a contagem de novos nós aumentam em 1 à medida que são criados e vinculados de acordo com as transações.

# 6) O próximo passo é minerar a árvore FP criada. Para isso, o nó mais baixo é examinado primeiro junto com os links dos nós mais baixos. O nó mais baixo representa o comprimento do padrão de frequência 1. A partir disso, atravesse o caminho na Árvore FP. Este caminho ou caminhos são chamados de base de padrão condicional.

A base do padrão condicional é um sub-banco de dados que consiste em caminhos de prefixo na árvore FP que ocorrem com o nó mais baixo (sufixo).

# 7) Construa uma Árvore FP condicional, que é formada por uma contagem de conjuntos de itens no caminho. Os conjuntos de itens que atendem ao suporte de limite são considerados na Árvore FP condicional.

# 8) Os padrões frequentes são gerados a partir da Árvore FP condicional.

Exemplo de algoritmo de crescimento FP

Limite de suporte = 50%, confiança = 60%

tabela 1

Solução:

Limite de suporte = 50% => 0,5 * 6 = 3 => min_sup = 3

1. Contagem de cada item

mesa 2

2. Classifique o conjunto de itens em ordem decrescente.

Tabela 3

o comprimento da string conta espaços java

3. Construir árvore FP

1. Considerando o nó raiz nulo.
2. A primeira varredura da Transação T1: I1, I2, I3 contém três itens {I1: 1}, {I2: 1}, {I3: 1}, onde I2 está vinculado como filho à raiz, I1 está vinculado a I2 e I3 está vinculado a I1.
3. T2: I2, I3, I4 contém I2, I3 e I4, onde I2 está vinculado à raiz, I3 está vinculado a I2 e I4 está vinculado a I3. Mas esta ramificação compartilharia o nó I2 tão comum quanto já é usado em T1.
4. Aumente a contagem de I2 em 1 e I3 é vinculado como criança a I2, e I4 é vinculado como criança a I3. A contagem é {I2: 2}, {I3: 1}, {I4: 1}.
5. T3: I4, I5. Da mesma forma, um novo ramo com I5 é vinculado a I4 quando uma criança é criada.
6. T4: I1, I2, I4. A sequência será I2, I1 e I4. I2 já está vinculado ao nó raiz, portanto, será incrementado em 1. Da mesma forma, I1 será incrementado em 1, pois já está vinculado a I2 em T1, portanto {I2: 3}, {I1: 2}, {I4: 1}
7. T5: I1, I2, I3, I5. A sequência será I2, I1, I3 e I5. Assim, {I2: 4}, {I1: 3}, {I3: 2}, {I5: 1}.
8. T6: I1, I2, I3, I4. A sequência será I2, I1, I3 e I4. Assim, {I2: 5}, {I1: 4}, {I3: 3}, {I4 1}.

4. A mineração da árvore FP é resumida abaixo:

1. O item de nó mais baixo I5 não é considerado porque não tem uma contagem mínima de suporte, portanto, é excluído.
2. O próximo nó inferior é I4. I4 ocorre em 2 ramos, {I2, I1, I3:, I41}, {I2, I3, I4: 1}. Portanto, considerando I4 como sufixo, os caminhos de prefixo serão {I2, I1, I3: 1}, {I2, I3: 1}. Isso forma a base do padrão condicional.
3. A base do padrão condicional é considerada um banco de dados de transações, uma árvore FP é construída. Isso conterá {I2: 2, I3: 2}, I1 não é considerado, pois não atende a contagem de suporte mínimo.
4. Este caminho irá gerar todas as combinações de padrões frequentes: {I2, I4: 2}, {I3, I4: 2}, {I2, I3, I4: 2}
5. Para I3, o caminho do prefixo seria: {I2, I1: 3}, {I2: 1}, isso irá gerar uma árvore FP de 2 nós: {I2: 4, I1: 3} e padrões frequentes são gerados: {I2 , I3: 4}, {I1: I3: 3}, {I2, I1, I3: 3}.
6. Para I1, o caminho do prefixo seria: {I2: 4} isso irá gerar uma árvore FP de nó único: {I2: 4} e padrões frequentes são gerados: {I2, I1: 4}.

O diagrama fornecido a seguir descreve a árvore FP condicional associada ao nó condicional I3.

Vantagens do algoritmo de crescimento FP

1. Este algoritmo precisa varrer o banco de dados apenas duas vezes quando comparado ao Apriori, que varre as transações para cada iteração.
2. O pareamento de itens não é feito neste algoritmo e isso o torna mais rápido.
3. O banco de dados é armazenado em uma versão compacta na memória.
4. É eficiente e escalonável para minerar padrões frequentes longos e curtos.

Desvantagens do algoritmo de crescimento FP

1. FP Tree é mais pesado e difícil de construir do que Apriori.
2. Pode ser caro.
3. Quando o banco de dados é grande, o algoritmo pode não caber na memória compartilhada.

Crescimento FP vs Apriori

ECLAT

O método acima, crescimento a priori e FP, extrai conjuntos de itens frequentes usando o formato de dados horizontal. ECLAT é um método de mineração de conjuntos de itens frequentes usando o formato de dados vertical. Ele transformará os dados do formato de dados horizontal no formato vertical.

Por exemplo,Uso de crescimento a priori e FP:

O ECLAT terá o formato da tabela como:

Este método formará 2 conjuntos de itens, 3 conjuntos de itens, k conjuntos de itens no formato de dados vertical. Este processo com k é aumentado em 1 até que nenhum conjunto de itens candidato seja encontrado. Algumas técnicas de otimização, como diffset, são usadas junto com a Apriori.

Este método tem uma vantagem sobre o Apriori, pois não exige a varredura do banco de dados para encontrar o suporte de k + 1 conjuntos de itens. Isso porque o conjunto de Transações carregará a contagem de ocorrência de cada item da transação (suporte). O gargalo surge quando há muitas transações que consomem muita memória e tempo computacional para cruzar os conjuntos.

Conclusão

O algoritmo Apriori é usado para regras de associação de mineração. Funciona com o princípio de que “os subconjuntos não vazios de conjuntos de itens frequentes também devem ser frequentes”. Ele forma candidatos a conjuntos de itens k a partir de conjuntos de itens (k-1) e verifica o banco de dados para encontrar os conjuntos de itens frequentes.

Algoritmo de crescimento de padrão frequente é o método de encontrar padrões frequentes sem geração de candidato. Ele constrói uma Árvore FP em vez de usar a estratégia de geração e teste de Apriori. O foco do algoritmo FP Growth é fragmentar os caminhos dos itens e extrair padrões frequentes.

Esperamos que estes tutoriais da Série de Data Mining tenham enriquecido seu conhecimento sobre Data Mining !!

PREV Tutorial | PRIMEIRO Tutorial

Leitura recomendada

• Técnicas de mineração de dados: algoritmo, métodos e principais ferramentas de mineração de dados
• Algoritmo a priori em mineração de dados: implementação com exemplos
• Exemplos de algoritmos de árvore de decisão em mineração de dados
• Exemplos de mineração de dados: aplicações mais comuns de mineração de dados 2021
• Mineração de dados: processo, técnicas e questões importantes na análise de dados
• Processo de mineração de dados: modelos, etapas do processo e desafios envolvidos
• Padrão de perguntas do exame de certificação de teste de software CSTE
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning