fp-growth.md

theme	transition	title	enableMenu	enableSearch	enableChalkboard	slideNumber
solarized	slide	FP Growth	true	false	true	true

FP Growth

Luís Antônio

---

Antes do Growth

---

Frequent pattern discovery

A tarefa de encontrar os padrões mais frequentes e relevantes em grandes conjuntos de dados. (Wikipedia)

---

Autores

• J. Han
• Jian Pei
• Yiwen Yin

---

Vamos tentar entender na prática

---

Ordenando

{width=50%}

---

Suporte

O suporte indica o quão frequente um conjunto de itens ocorre na base de dados. Se o suporte desse conjunto é muito pequeno significa que não temos informações suficiente para tirar conclusões.

---

Suporte

---

Considerando um SP mínino de 50%

---

Certo, agora vamos para o 2° passo

Árvore se sufixos

---

O que é isso?

---

Ordenando os itens para cada transação

---

Agora, é só inserir

---

T1 (Manteiga, Pão, Leite)

---

T2 (Manteiga, Leite, Café)

---

T3 (Café)

---

T4 (Manteiga, Pão, Café)

---

T5 (Manteiga, Pão, Leite)

---

T6 (Manteiga, Pão, Leite, Café)

---

Conjuntos intermediários

Baseado nessa árvore construiremos os conjuntos intermediários conditional pattern base e conditional FP tree, para depois gerar os conjuntos frequentes.

---

Conditional Pattern

Para achar o conditional pattern base precisamos iterar sobre cada item da coluna de frequência inversa, e guardar o caminho da raiz até o nó em questão. Exemplo: podemos encontrar um nó Café, pelos caminhos: { Manteiga, Pão, Leite }, {Manteiga, Leite}, {Manteiga, Pão}. Observe na Árvore que o caminho direto da raiz ao Café não é contado.

---

Conditional FP tree

A partir do conditional pattern base, criamos o conditional FP tree que são os itens dos conjuntos de conditional pattern base que estão acima do suporte mínimo.

---

Conjuntos frequentes

Agora finalmente podemos encontrar nossos conjuntos frequentes.

---

Obrigado