Amazon item-to-item CF

01 · CONTEXTO

O problema: recomendar rápido para milhões

Este caso parte de um artigo em que engenheiros da Amazon descrevem o algoritmo de recomendação que chamam de filtragem colaborativa item a item. O ambiente que eles descrevem é duro: uma grande loja pode ter dezenas de milhões de clientes e milhões de itens distintos no catálogo, e o artigo situa a própria Amazon acima de 29 milhões de clientes.

Além da escala, há requisitos de produto. Muitas aplicações exigem o resultado em tempo real, em no máximo meio segundo, sem abrir mão da qualidade. Clientes novos têm pouquíssima informação, clientes antigos podem ter milhares de compras e avaliações, e cada interação gera dado novo ao qual o algoritmo precisa reagir de imediato.

As recomendações aparecem em campanhas de email e em páginas do site, incluindo o carrinho de compras, onde as sugestões partem dos itens que a pessoa já colocou ali.

02 · ALTERNATIVAS

Por que as abordagens comuns não bastavam

O artigo compara três abordagens comuns com a proposta dos autores. A primeira, a filtragem colaborativa tradicional, representa cada cliente como um vetor de itens e procura os clientes mais parecidos com a pessoa.

1. A pessoa pede recomendações e o serviço precisa decidir o que mostrar naquele momento.

2. Na versão tradicional, a parte online cresce com o número de clientes e de itens do catálogo.

3. Com conjuntos muito grandes de clientes e itens, esse trabalho online causa problemas graves de desempenho e escala.

Reduzir os dados, por amostragem, particionamento ou redução de dimensionalidade, alivia o custo, mas os próprios autores dizem que todos esses métodos também reduzem a qualidade das recomendações.

03 · OFFLINE

A tabela de itens similares

A ideia central inverte a pergunta. Em vez de achar clientes parecidos com a pessoa, o algoritmo associa cada item comprado ou avaliado a itens similares e combina esses similares em uma lista de recomendação.

Para isso ele monta uma tabela de itens similares, procurando itens que os clientes tendem a comprar juntos. A tabela cara é criada offline, antes dos pedidos.

Em termos de arquitetura, isso equivale a um pipeline de dados em lote: lê o histórico de compras e grava um resultado pronto para consulta.

1. O ponto de partida é o histórico de quem comprou o quê.

2. Para cada item, o job percorre os clientes que o compraram e os demais itens que esses clientes compraram, evitando comparar pares de produtos sem cliente em comum.

3. Em seguida calcula a similaridade entre o item e os relacionados; um método comum é o cosseno, com um vetor por item cujas dimensões são os clientes que o compraram.

4. O resultado fica numa tabela de itens similares, pronta para ser consultada depois.

Esse cálculo offline é muito demorado, mas, segundo os autores, amostrar os clientes que compram best-sellers reduz ainda mais o tempo de execução com pouca perda de qualidade.

04 · ONLINE

Responder ao pedido sem recalcular

No caminho online não há busca por clientes parecidos. O algoritmo pega os itens da pessoa, procura na tabela os similares de cada um, agrega e recomenda os mais populares ou correlacionados.

1. A pessoa abre uma página ou o carrinho e o serviço recebe o pedido.

2. O serviço lê os itens que a pessoa comprou ou avaliou, e esse número define o custo do cálculo online.

3. Para cada um desses itens, o serviço consulta a tabela de similares já calculada.

4. Os similares são agregados e o serviço devolve os mais populares ou correlacionados.

O custo dessa etapa depende só de quantos itens a pessoa comprou ou avaliou, e a parte online escala independentemente do tamanho do catálogo e do total de clientes. Por isso, dizem os autores, o algoritmo é rápido mesmo em conjuntos extremamente grandes.

05 · LIÇÕES

O que levar para a entrevista

Ao concluir, os autores listam o que um bom algoritmo de recomendação precisa: escalar sobre bases enormes de clientes e catálogos, gerar recomendações online em tempo subsegundo e reagir de imediato a mudanças nos dados do usuário.

Em entrevista, vale usar o mesmo raciocínio: separe o que muda a cada pedido do que pode ser pré-calculado, e diga qual é a entrada variável do caminho online. Também vale perguntar qual é a defasagem aceitável da tabela pré-calculada.