Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Um sistema de recomendação de produtos baseado ...

Um sistema de recomendação de produtos baseado em grafos

Após trabalhar com diversas plataformas e não encontrar uma solução que atendesse os requisitos da empresa, o departamento de Pesquisa e Desenvolvimento do Magazine Luiza decidiu construir sua própria ferramenta de recomendação, baseada em um grande “interest graph”. Seja pelo e-commerce, através de aplicações mobile, clube de ofertas ou lojas físicas, informações do comportamento do cliente são armazenadas nesse grafo e posteriormente utilizadas nas recomendações.

Nesta apresentação, vamos mostrar os desafios enfrentados e um passo a passo da utilização de tecnologias como Cassandra, Redis, Gremlin, Titan, Faunus e Hadoop na extração de recomendações a partir de grafos.

* Apresentado na QCon14

Renato Pedigoni

April 10, 2014
Tweet

More Decks by Renato Pedigoni

Other Decks in Programming

Transcript

  1. Um sistema de recomendação de produtos baseado em grafos Renato

    Pedigoni! Engenheiro Líder @rpedigoni [email protected] André Fatala! Diretor P&D @andrefatala [email protected]
  2. 744 lojas físicas 8 centros de distribuição +24 mil colaboradores

    +22 milhões de clientes 14 milhões de visitantes únicos por mês
  3. –Dan Ariely "Big data is like teenage sex: everyone talks

    about it, nobody really knows how to do it, everyone thinks everyone else is doing it, so everyone claims they are doing it..."
  4. Grafos Vértices (entidades, objetos) Arestas (relacionamentos, conexões) pertence Pessoa Sessão

    Produto Categoria Depto visitou comprou avaliou timestamp timestamp quantidade timestamp avaliacao nome email timestamp titulo estoque titulo titulo
  5. Modelo: e-commerce Pessoa Sessão Produto Categoria Depto Produto Produto Produto

    iniciou visitou similar crosssell pertence pertence upsell
  6. Grafos persistentes Suporta grandes grafos Código aberto, uso gratuito (incl.

    comercial) Storage configurável: Cassandra, HBase, entre outros Nossa escolha: Entre as possibilidades:
  7. Grafos persistentes • Teorema "CAP"
 Consistência - Disponibilidade - Particionamento

    Nossa escolha - Sem ponto único de falha - Consistência eventual
  8. Exemplo > vert1 = g.addVertex(); > vert1.tipo = 'visitante'; >

    vert2 = g.addVertex(); > vert2.tipo = 'produto'; Visitante Produto
  9. Exemplo > vert1 = g.addVertex(); > vert1.tipo = 'visitante'; >

    vert2 = g.addVertex(); > vert2.tipo = 'produto'; > g.addEdge(vert1, vert2, 'visitou'); > g.commit() Visitante visitou Produto
  10. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" Recomendação
  11. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 visitou visitou visitou TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" visitou visitou visitou visitou visitou visitou Recomendação
  12. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" Recomendação
  13. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') Recomendação
  14. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') .in('visitou') Recomendação
  15. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') .in('visitou') Recomendação
  16. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') .in('visitou') Recomendação .out('visitou')
  17. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') .in('visitou') Recomendação .out('visitou')
  18. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') .in('visitou') Recomendação .out('visitou') .groupCount()
  19. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') .in('visitou') Recomendação .out('visitou') .groupCount() key value TV LCD 40" TV PLASMA 52" TV LED 42” TV LCD 32" 1 2 3 1
  20. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') .in('visitou') Recomendação .out('visitou') .groupCount() key value TV LCD 40" TV PLASMA 52" TV LED 42” TV LCD 32" 1 2 3 1 .sort{-it.value}
  21. Sessão! #21162 Quem viu, também viu TV LED 
 40"

    Sessão! #826482 Sessão! #4337189 TV LCD 
 40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" g.V('product_sku', 'tv_led_40') .in('visitou') Recomendação .out('visitou') .groupCount() key value TV LCD 40" TV PLASMA 52" TV LED 42” TV LCD 32" 1 2 3 1 .sort{-it.value}
  22. Produto Supernodes • Vértices com número desproporcional de arestas conectadas

    http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/ Benchmark
  23. Produto Supernodes • Vértices com número desproporcional de arestas conectadas

    Produto +1.000.000 http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/ Benchmark
  24. Produto Supernodes • Vértices com número desproporcional de arestas conectadas

    Produto Solução (Titan): vertex-centric indices +1.000.000 http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/ Benchmark
  25. Arestas de atalho TV LED 
 40" TV LCD 


    40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" Sessão" #21162 Sessão" #826482 Sessão" #4337189 visitou visitou visitou visitou visitou visitou visitou visitou visitou 1
  26. Arestas de atalho TV LED 
 40" TV LCD 


    40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" Sessão" #21162 Sessão" #826482 Sessão" #4337189 visitou visitou visitou visitou visitou visitou visitou visitou visitou 1
  27. Arestas de atalho TV LED 
 40" TV LCD 


    40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" Sessão" #21162 Sessão" #826482 Sessão" #4337189 visitou visitou visitou visitou visitou visitou visitou visitou visitou 1 quem_viu_tb_viu quem_viu_tb_viu
  28. Arestas de atalho TV LED 
 40" TV LCD 


    40" TV PLASMA 
 52" TV LED 
 42” TV LCD 
 32" Sessão" #21162 Sessão" #826482 Sessão" #4337189 visitou visitou visitou visitou visitou visitou visitou visitou visitou 1 quem_viu_tb_viu quem_viu_tb_viu g.V('product_sku', ‘tv_led_40’).out(‘quem_viu_tb_viu’)
  29. Faunus Roda sobre o Hadoop, armazena os dados no HDFS

    Ferramenta para operações globais no grafo Diversas utilidades Graph analytics Schema migration Sub grafos Detecção de comunidades
  30. Faunus: exemplo In degree distribution g.V.sideEffect('{it.degree=it.inE.count()}').degree.groupCount ==>1 167050! ==>10 2305!

    ==>100 6! ==>108 3! ==>119 3! ==>122 3! ==>133 1! ==>144 2! ==>155 1! ==>166 2! ==>18 471! ==>188 1! ==>21 306! ==>232 1! ==>254 1! ==>...
  31. Rexster • Parte da stack Tinkerpop • Permite acessar qualquer

    grafo Blueprints através de uma API REST • Além de HTTP, possui protocolo binário (RexPro)
  32. Gremlin Demo initialized User type userId Session type sessionId timestamp

    Product type category name viewed 50 users 90 products 102 sessions ! 690 edges
  33. Bob • Infra: AWS • +1.2 bilhões de arestas armazenadas

    • + 300 milhões de vértices • 20 milhões de recomendações por dia