Upload
joao-gabriel-lima
View
709
Download
3
Embed Size (px)
Citation preview
Escalando o Algoritmo de aprendizagem da Escalando o Algoritmo de aprendizagem da estrutura Bayesiana k2 utilizando MapReduce estrutura Bayesiana k2 utilizando MapReduce
e banco de dados NoSQLe banco de dados NoSQL
J. Gabriel Limahttp://jgabriellima.in
Revisão...Revisão...
Redes Bayesianas: Um dos principais métodosprincipais métodos para a modelagem da incertezamodelagem da incerteza,
permitindo tanto a previsão quanto o diagnóstico de eventos.
Modelos que codificam os relacionamentos probabilísticoscodificam os relacionamentos probabilísticos entre as variáveis que definem um determinado domínio e que são utilizadas para representar processos probabilísticos e causaisrepresentar processos probabilísticos e causais.
grafo acíclico dirigidografo acíclico dirigido, composto por uma estrutura qualitativaqualitativa, representando as dependências entre suas variáveis; e quantitativaquantitativa, avaliando, em termos probabilísticos, essas dependências
Revisão...Revisão...
Redes Bayesianas: O aprendizado de estrutura é um importante problema a ser estudado pelo
fato de o tamanho do espaço de busca de possíveis estruturas aumentar exponencialmente junto com o número de variáveis do modelo.
Esse crescimento exponencial pode ser visualizado pela fórmula:
Algoritmo K2 Embora proposto em 1992, ainda se apresenta como uma grande grande
referênciareferência entre os algoritmos existentes para aprendizado de redes Bayesianas, sendo um dos mais confiáveis e bem sucedidosmais confiáveis e bem sucedidos algoritmos de aprendizado.
Percorre todo o especo de possíveis estruturas candidatastodo o especo de possíveis estruturas candidatas aplicando uma pontuação de acordo com a equação:
Revisão...Revisão...
MapReduce:O cálculo toma um conjunto de pares de entradas de chave/valor, e
produz um conjunto de pares de saídas chave/valor.
O usuário que implementa o MapReduce expressa o cálculo como duas funções: Map e Raduce.
MapMapEscrito pelo usuário, leva um par de entrada e produz um conjunto de pares intermediários de chave/valor.
Neste processo há uma junção de todos os valores intermediários associados com uma mesma chave intermediária, afim de passá-los
para a função Reduce.
A função ReduceReduce, também escrita pelo usuário, aceita
uma chave intermediária e um conjunto de valores para essa chave.
Ela faz uma fusão desses valores em conjunto, para formar um menor conjunto de valores possível.
Tipicamente apenas zero ou um valor de saída é produzido por um método Reduce.
Os valores intermédios são fornecidos para a função através de uma iteração. Isto permite-nos lidar com listas de valores que são demasiadamente grandes para caber na memória.
Estudo de Caso
Base de Segurança Pública do Estado do Pará:
Nº Total de Registros:Nº Total de Registros: 769.254769.254 BairrosBairros: 4646 CrimeCrime: 388388 LocalLocal: 3232 LogradouroLogradouro: 3.3123.312 UnidadeUnidade PolicialPolicial: 304304 Classe CrimeClasse Crime: 4646
ProblemáticasProblemáticas
BAIRRO → 4646 BAIRRO, CRIME → 6.2386.238 BAIRRO,CRIME,LOCAL → 26.77226.772
Muitas iterações dentro de muitas combinações 457784406908348220669381056297854997416
34114232516550750301927014...
MapReduce e o estudo de caso
As etapas mais com maior custo computacional foram todas substituidassubstituidas por redução de mapa.redução de mapa.
O fluxo do algoritmo foi modificadoO fluxo do algoritmo foi modificado de modo a invocar a redução de mapa no lugar da busca no banco de dados
Cenário:
Banco de Dados NoSQL MongoDB2 que implementa MapReduce nativamente utilizando seu Grid File System interno.
MapReduce e o estudo de caso
As Reduções de mapa a seguir , representam a etapa de busca por frequenciabusca por frequencia equivalente ao aijkaijk do algoritmo
Redução de Mapa por BairroBairro (Count: 46, Time: 17030ms17030ms)
Processamento interno do banco de dados
117100/769254 15%
260800/769254 33%
400600/769254 52%
534600/769254 69%
667600/769254 86%
Redução de Mapa por CRIME (Count: 388, Time: 22393ms)
Processamento interno do banco de dados
82600/769254 10%
193800/769254 25%307500/769254 39%
404900/769254 52%
517000/769254 67%
628800/769254 81%
734300/769254 95%
Para as bucas compostas, onde o resultado é a combinação entre estados de vários atributos:
Ex.:
BAIRRO,CRIMEBAIRRO,CRIME (Count: 6238, Time: 24348ms)
53800/769254 6%
141700/769254 18%
239300/769254 31%
330300/769254 42%
423300/769254 55%
513600/769254 66%
598800/769254 77%
690300/769254 89%
BAIRRO,CRIME,LOCAL (Count: 26772, Time: 20219ms)
53800/769254 6%
141700/769254 18%
239300/769254 31%
330300/769254 42%
423300/769254 55%
513600/769254 66%
598800/769254 77%
690300/769254 89%
Considerações FinaisConsiderações Finais
ConclusãoConclusão
Melhor desempenho do algoritmo bayesiano Maior aproveitamento dos dados Maior capacidade de processamento de consultas
complexas Apesar de aumentar o desempenho em relação às
buscas complexas, ainda temos as barreiras matemáticas.
Produtórios, Somatórios...