Tanto quanto eu sei o desenvolvimento de algoritmos para resolver o problema da Mineração de Padrão Frequente (FPM), o caminho das melhorias tem alguns pontos de verificação principais. Primeiramente, o algoritmo Apriori foi proposto em 1993 por Agrawal et al. , juntamente com a formalização do problema. O algoritmo conseguiu remover alguns conjuntos dos 2^n - 1conjuntos (conjunto de energia) usando uma treliça para manter os dados. Uma desvantagem da abordagem foi a necessidade de reler o banco de dados para calcular a frequência de cada conjunto expandido.
Mais tarde, no ano de 1997, Zaki et al. propuseram o algoritmo Eclat , que inseriu a frequência resultante de cada conjunto dentro da rede. Isso foi feito adicionando, em cada nó da rede, o conjunto de IDs de transação que tinham os itens da raiz ao nó referido. A principal contribuição é que não é necessário reler todo o conjunto de dados para saber a frequência de cada conjunto, mas a memória necessária para manter essa estrutura de dados construída pode exceder o tamanho do próprio conjunto de dados.
Em 2000, Han et al. propuseram um algoritmo chamado FPGrowth , juntamente com uma estrutura de dados da árvore de prefixos denominada FPTree. O algoritmo foi capaz de fornecer compactação de dados significativa, além de conceder que apenas conjuntos de itens frequentes seriam gerados (sem geração de conjunto de itens candidatos). Isso foi feito principalmente pela classificação dos itens de cada transação em ordem decrescente, para que os itens mais frequentes sejam aqueles com menos repetições na estrutura de dados da árvore. Como a frequência apenas desce enquanto percorre a árvore em profundidade, o algoritmo é capaz de eliminar conjuntos de itens não frequentes.
Editar :
Até onde eu sei, isso pode ser considerado um algoritmo de última geração, mas eu gostaria de saber sobre outras soluções propostas. Quais outros algoritmos para o FPM são considerados "avançados"? Qual é a intuição / contribuição principal de tais algoritmos?
O algoritmo FPGrowth ainda é considerado "estado da arte" na mineração de padrões frequente? Caso contrário, quais algoritmos podem extrair conjuntos de itens frequentes de grandes conjuntos de dados com mais eficiência?
Respostas:
Estado da arte como em: usado na prática ou trabalhado na teoria?
O APRIORI é usado em qualquer lugar, exceto no desenvolvimento de novos algoritmos de conjunto de itens frequentes. É fácil de implementar e reutilizar em domínios muito diferentes. Você encontrará centenas de implementações APRIORI de qualidade variável. E é fácil entender errado o APRIORI.
FPgrowth é muito mais difícil de implementar, mas também muito mais interessante. Portanto, do ponto de vista acadêmico, todo mundo tenta melhorar o crescimento FP - obter trabalho com base no APRIORI aceito será muito difícil agora.
Se você tem uma boa implementação, todo algoritmo é bom e é ruim na minha opinião. Uma boa implementação do APRIORI precisará apenas varrer o banco de dados k vezes para encontrar todos os conjuntos de itens frequentes de comprimento k . Em particular, se seus dados couberem na memória principal, isso é barato. O que pode matar o APRIORI são muitos conjuntos de 2 itens frequentes (especialmente quando você não usa um Trie e técnicas de aceleração semelhantes etc.). Funciona melhor em grandes dados com um baixo número de conjuntos de itens frequentes.
Eclat trabalha em colunas; mas precisa ler cada coluna com muito mais frequência. Há algum trabalho em diffsets para reduzir esse trabalho. Se seus dados não couberem na memória principal, o Eclat provavelmente sofrerá mais que o Apriori. Ao aprofundar primeiro, ele também poderá retornar um primeiro resultado interessante muito antes de Apriori, e você poderá usar esses resultados para ajustar parâmetros; então você precisa de menos iterações para encontrar bons parâmetros. Mas, por design, não pode explorar a poda tão bem quanto Apriori.
FPGrowth comprime o conjunto de dados na árvore. Isso funciona melhor quando você tem muitos registros duplicados. Provavelmente, você também poderá obter alguns ganhos para Apriori e Eclat se puder pré-ordenar seus dados e mesclar duplicatas em vetores ponderados. FPGrowth faz isso em um nível extremo. A desvantagem é que a implementação é muito mais difícil; e uma vez que essa árvore não se encaixa mais na memória, fica uma bagunça para implementar.
Quanto aos resultados de desempenho e benchmarks - não confie neles. Há tantas coisas para implementar incorretamente. Experimente 10 implementações diferentes e você obtém 10 resultados de desempenho muito diferentes. Em particular para a APRIORI, tenho a impressão de que a maioria das implementações está quebrada no sentido de perder algumas das principais contribuições da APRIORI ... e daquelas que possuem essas partes corretas, a qualidade das otimizações varia muito.
Na verdade, existem até documentos sobre como implementar esses algoritmos com eficiência:
Você também pode querer ler estas pesquisas sobre este domínio:
fonte
A maioria das abordagens recentes de Padrão Frequente que eu vi na literatura se baseia na otimização da profundidade de FPG. Devo admitir que não vejo muitos desenvolvimentos na literatura no FPM há muitos anos.
Este wikibook destaca muitas das variantes do FPGrowth que existem por aí.
fonte