Rodando um Recomendador no Hadoop usando Mahout

By Ivanilton Polato e Frank Helbert. These slides are licensed under theAtribuição-Uso não-comercial-Compartilhamento pela mesma licença 3.0 Brasil Licence (CC BY-NC-SA 3.0)

Ivanilton Polato Frank HelbertUTFPR Câmpus Campo Mourão

Doutorado em Ciência da Computação

DINTER IME/USP-UTFPR

Abril/2012

Rodando um recomendador

Frank Helbert Ivanilton Polato 2

Motivações atuais!

Grandes quantidades (massivas) de dadosDemoram MUITO para processar serialmente!

Máquinas individuais falham!Mais máquinas juntas... probabilidade maior!O número de nós em um cluster não é constante!

Computação nas nuvensDisponibilidade de computação e dados

Escalabilidade de aplicaçõesComputação sob demanda

Frank Helbert Ivanilton Polato 3

Histórico

Fonte: Evert Lammerts (SARA.nl)

* http://nutch.apache.org/** http://labs.google.com/papers/mapreduce.html http://labs.google.com/papers/gfs.html

Frank Helbert Ivanilton Polato 4

HistóricoFev/03 – Primeira biblioteca Map/Reduce na Google Out/03 – Artigo sobre GFSDez/04 – Artigo sobre Map ReduceDez/05 – Doug Cutting implementa MR e DFS no NutchFev/06 – Hadoop se torna um projeto oficial da Apache, Doug Cutting é contratado pela Yahoo!, que adota o Hadoop Abr/07 – Yahoo! roda Hadoop em um cluster de 1000 nósJan/08 – Hadoop se transforma em um projeto principal da ApacheDez/11 – Apache disponibiliza versão 1.0.0

Frank Helbert Ivanilton Polato 5

O que é Apache Hadoop?

Framework para computação distribuídaUsado em clusters/grades computacionais

Milhares de nós

Hardware comum (Commodity cluster computing)

Petabytes de dados

Open Source (licença Apache)

Java

Inspirado originalmente pelo GFS e MapReduce da Google

Frank Helbert Ivanilton Polato 6

Suposições do Projeto

Os dados que serão processados não cabem em um nó

Cada nó é hardware comum

Falhas acontecem

Mover dados é caro

Mover computação é barato

Computação distribuída é fácil

Frank Helbert Ivanilton Polato 7

Ideias

Sistemas de arquivos distribuído

Replicação interna

Recuperação de falhas automáticas

Mover computação para os dados

Escrever programas que são fáceis de distribuir

Suposições do Projeto

Frank Helbert Ivanilton Polato 8

Composição do Apache Hadoop

Núcleo composto por:Hadoop Common: Bibliotecas principais

HDFS: Sistema de arquivos

MapReduce: Paradigma de programação

Projetos relacionados:HBase: BD distribuído e escalável

Hive e Pig: infraestrutura de DW

Na web: http://hadoop.apache.org/

Frank Helbert Ivanilton Polato 9

Possibilidades de uso

System Data

...WEB ANALYTICS...

Frank Helbert Ivanilton Polato 10

Quem usa?

Lista completa: http://wiki.apache.org/hadoop/PoweredBy

By Ivanilton Polato e Frank Helbert. These slides are licensed under theAtribuição-Uso não-comercial-Compartilhamento pela mesma licença 3.0 Brasil Licence (CC BY-NC-SA 3.0)

HDFSHadoop Distributed File System

Frank Helbert Ivanilton Polato 12

HDFS: Hadoop Distributed File System

Sistema de arquivos distribuídoGrande ordem de 10k nós

Milhões de arquivos

Projetado para hardware de baixo custoRedundância por replicação

Tolerância a falhas e recuperação

Otimizado para processamento em loteLocalização dos dados exposta

Grande largura de banda associada

Frank Helbert Ivanilton Polato 13

HDFS: Hadoop Distributed File System

Coerência dos dadosModelo “write-once-ready-many”

Arquivos existentes sofrem apenas operações de “append”

Arquivos quebrados em pedaços (blocos)Variam de 64mb (padrão) a 256mb

Blocos distribuídos pelos nós (um arquivo é dividido em N blocos e armazenado em M nós)

Blocos são replicados e as replicações distribuídas

Frank Helbert Ivanilton Polato 14

Todos os comandos são executados com o prefixo hadoop fs

Principais comandos similares unix/linux:ls »» lista arquivos

put »» envia arquivos ao fs (origem, destino)

get »» copia arquivos do fs (origem, destino)

rm »» remove arquivos do fs

rmr »» remove arquivos e diretórios do fs

cat »» mostra o conteúdo de arquivo no fs

HDFS: Hadoop Distributed File System

By Ivanilton Polato e Frank Helbert. These slides are licensed under theAtribuição-Uso não-comercial-Compartilhamento pela mesma licença 3.0 Brasil Licence (CC BY-NC-SA 3.0)

MapReduce

Frank Helbert Ivanilton Polato 16

A ideia

A ideia do paradigma de programação Map e Reduce não é novaProvavelmente 40+ anos!

No Hadoop é a parte do framework responsável pelo processamento distribuído (paralelo) de grandes conjuntos de dados.

Provê um modelo de programação

Usa padrões já conhecidos:cat | grep | sort | unique > file

input | map | shuffle | reduce > output

Frank Helbert Ivanilton Polato 17

A natureza do MapReduce

Map em programação funcionalmap({1,2,3,4}, (x2)) {2,4,6,8}Todos os elementos são processados por um método e os elementos não afetam uns aos outros

Reduce em programação funcionalreduce({1,2,3,4}, (x)) {24} Todos elementos na lista são processados juntos

Tanto em Map quanto em Reduce:A entrada é fixa (imutável), e a saída é uma nova lista

Frank Helbert Ivanilton Polato 18

Continuando...

O paradigma MapReduce é adequado para trabalhar com grandes quantidades de dadosRealiza computação sobre os dados (pouca movimentação de dados)

Utiliza os blocos armazenados no DFS, logo não necessita divisão dos dados

Lida com o paralelismoUm Map por bloco, se possível

Frank Helbert Ivanilton Polato 19

MapReduce no Hadoop

A função Map atua sobre um conjunto de entrada com chaves e valores, produzindo uma lista de chaves e valoresA função Reduce atua sobre os valores intermediários produzidos pelo Map para, normalmente, agrupar os valores e produzir a saída

Input Output

map <k1, v1> lista(<k2, v2>)

reduce <k2, lista(v2)> lista(<k3, v3>)

Frank Helbert Ivanilton Polato 20

Exemplos: Word Count

Lê arquivos texto e conta a frequência das palavrasEntrada: arquivos texto

Saída: arquivo textoCada linha: palavra, separador (tab), quantidade

Map: gera pares de (palavra, quantidade)

Reduce: para cada palavra, soma as quantidades

Frank Helbert Ivanilton Polato 21

Map e Reduce (Pseudo-código)map(String key, String value):

// key: document name

// value: document contents

for each word w in value:

EmitIntermediate(w, “1”);

reduce(String key, Iterator values):

// key: a word

// values: a list of counts

int result = 0;

for each v in values:

result += ParseInt(v);

Emit(AsString(result));

By Ivanilton Polato e Frank Helbert. These slides are licensed under theAtribuição-Uso não-comercial-Compartilhamento pela mesma licença 3.0 Brasil Licence (CC BY-NC-SA 3.0)

Funcionamentoem um cluster

Frank Helbert Ivanilton Polato 23

MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean e Sanjay Ghemawat ACM, 2008

Frank Helbert Ivanilton Polato 24

HDFS: NameNode & DataNodes

NameNode (NN)Gerencia o namespace do sistema de arquivosMapeia nomes de arquivos para blocos

Mapeia blocos para DataNodes

Gerenciamento de replicação

DataNode (DN)Servidor de blocos que armazenaDados no sistema de arquivos local

Metadados dos blocos (hash)

Disponibiliza metadados para clientes

Fonte: Evert Lammerts (SARA.nl)

Frank Helbert Ivanilton Polato 25

MapReduce: JobTracker & TaskTrackers

JobTrackerControla os metadadosStatus de um jobStatus de Tasks nos TTsDecide o escalonamento

TaskTrackersSolicita trabalho do JTBusca código para executar do DFSAplica configurações específicas dos jobsComunicam-se com o JT nas tasksEnviar saídas, atualizações de tasks, matar tasks, ...

Fonte: Evert Lammerts (SARA.nl)

By Ivanilton Polato e Frank Helbert. These slides are licensed under theAtribuição-Uso não-comercial-Compartilhamento pela mesma licença 3.0 Brasil Licence (CC BY-NC-SA 3.0)

Mahout

Frank Helbert Ivanilton Polato 27

Apache Mahout

É uma biblioteca de algoritmos de aprendizagem de máquina

É um projeto da Apache Software FoundationSoftware Livre – Licença Apache

Bem documentado

Contribuição da Comunidade

Principal objetivo:Ser escalável para manipular volume gigantesco

de dados

Frank Helbert Ivanilton Polato 28

Apache Mahout

Trabalha com: Matrizes e Vetores, Estruturas esparsas e densas, Agrupamento, Cobertura, K-Means, Análise densidade de funções, Filtragem colaborativa, Taste – motor de filtragem

Mahout pode ser usado com o Hadoop explorando a escalabilidade para processar os dados

Frank Helbert Ivanilton Polato 29

Gerando recomendações

1. Construir uma matriz que relaciona os itensMatriz de co-ocorrência

Computa o número de vezes que cada par de itens aparecem juntos na lista de preferências de algum usuário

Se existem 9 usuários que expressam preferência pelos itens X e Y, então X e Y co-ocorrem 9 vezes

Co-ocorrência é como similaridade, quanto mais dois itens aparecem juntos, mais provável que sejam similares

Frank Helbert Ivanilton Polato 30

Gerando recomendações

Matriz de co-ocorrência para um conjunto de dados com sete itens

Frank Helbert Ivanilton Polato 31

Gerando recomendações

2. Computando o vetor de cada usuárioUm vetor para cada usuário

Com n itens na base de dados, o vetor de preferências terá n dimensões

Se o usuário não exprime nenhuma preferência por um determinado item, o valor correspondente no vetor será zero

Neste exemplo, o vetor do usuário três é [2.0, 0.0, 0.0, 4.0, 4.5, 0.0, 5.0]

Frank Helbert Ivanilton Polato 32

Gerando recomendações

3. Computando as recomendaçõesPara computar as recomendações para o usuário

três, basta multiplicar seu vetor pela matriz de co-ocorrência

Computar cada valor da saída corresponde a estimar a preferência por um determinado item

Frank Helbert Ivanilton Polato 33

Gerando recomendações

Multiplicando a matriz de co-ocorrência com o vetor de preferências do usuário três para chegar ao vetor que nos leva às recomendações

Frank Helbert Ivanilton Polato 34

Gerando recomendações

Intuitivamente, olhando para a linha 3 da tabela, se o item desta linha co-ocorre com muitos itens que o usuário 3 expressou sua preferência, então é provável que seja algo que o usuário 3 goste

By Ivanilton Polato e Frank Helbert. These slides are licensed under theAtribuição-Uso não-comercial-Compartilhamento pela mesma licença 3.0 Brasil Licence (CC BY-NC-SA 3.0)

Rodando o recomendador

Frank Helbert Ivanilton Polato 36

Integrando o Mahout no Hadoop

Precisamos do RecommenderJob

Modo Newbie:Apenas coloque o JAR pré-compilado da

distribuição do Mahout no diretório do hadoop.

mahout-core-0.6-job.jarModo Expert:

Faça as alterações necessárias no Mahout para sua persolnalização, gere o JAR e coloque no diretório do hadoop.

Frank Helbert Ivanilton Polato 37

Chamada do Mahout no Hadoop

:~$ bin/hadoop jar mahout-core-0.6-job.jar org.apache.mahout.cf.taste.hadoop.item.RecommenderJob -Dmapred.input.dir=input/movieRec10M.txt -Dmapred.output.dir=outputCosine --usersFile input/movieUsers.txt --numRecommendations 10 --maxPrefsPerUser 100 --similarityClassname SIMILARITY_COSINE

Frank Helbert Ivanilton Polato 38

Formato dos dados

O recomendador do Mahout espera que os dados estejam da forma:RecommenderJob (org.apache.mahout.cf.taste.hadoop.item.RecommenderJob)

userID,itemID[,preferencevalue]UserID é um Long

ItemID é um Long

Preferencevalue é um Double

Frank Helbert Ivanilton Polato 39

Carregar os dados no HDFS

Comando:

hadoop fs -put <caminho_local_do_arquivo> <caminho_do_arquivo_no_hdfs>

Ex:

:~$ hadoop fs -put moviesRecommendation1M.txt input/moviesRec.txt

Frank Helbert Ivanilton Polato 40

Executando o RecomenderJob

Parâmetros de chamada:--usersFile(path): (xor) arquivo contendo os Ids dos

usuários considerados na computação

--itemsFile(path): (xor) arquivo contendo os Ids dos itens;

--numRecommendations(integer): número de recomendações computadas por usuário (padrão:10)

--booleanData(boolean): tratar a entrada como não tendo valores de preferência (padrão:falso)

--maxPrefsPerUser(integer): número máximo de preferências consideradas por usuário (padrão:10)

Frank Helbert Ivanilton Polato 41

Executando o RecomenderJob

Parâmetros de chamada:--similarityClassname(classname): (obrigatório) medida de

similaridade;

SIMILARITY_COOCCURRENCE

SIMILARITY_LOGLIKELIHOOD

SIMILARITY_TANIMOTO_COEFFICIENT

SIMILARITY_CITY_BLOCK

SIMILARITY_COSINE

SIMILARITY_PEARSON_CORRELATION

SIMILARITY_EUCLIDEAN_DISTANCE

By Ivanilton Polato e Frank Helbert. These slides are licensed under theAtribuição-Uso não-comercial-Compartilhamento pela mesma licença 3.0 Brasil Licence (CC BY-NC-SA 3.0)

Mão na massa...

Frank Helbert Ivanilton Polato 43

Atividade

Em grupos

Rodar o Hadoop na máquina localPseudo-Distributed mode

Colocar rating para 10 filmes que já assistiu

Enviar arquivos para o HDFS

Rodar o recomendador

Aplicar script python nos resultados

Juntar recomendações e rodar exemplo no cluster (fully distributed mode)

Frank Helbert Ivanilton Polato 44

Instalando Hadoop (Pseudo-Distributed)

Extraia o conteúdo do arquivo

hadoop-1.0.1-pre-config.tar.gz no seu home

Dentro de hadoop-1.0.1/conf altere:hadoop-env.sh (alterar linha 9: java home)

DE: /usr/lib/jvm/java-6-openjdk

PARA: /usr/lib/jvm/java-6-sun

OU: verifique sua versão do java!

Verifique os 3 arquivos .xml no diretório conf:core-site.xml

hdfs-site.xml

mapred-site.xml

Frank Helbert Ivanilton Polato 45

Verifique o ssh da máquina. A maquina deve se conectar ao localhost sem necessidade de password.

:~$ ssh localhost

Agora vamos formatar (criar) o HDFS:

:~$ bin/hadoop namenode -format

E agora vamos inicializar o Hadoop (start-

Instalando Hadoop (Pseudo-Distributed)

Frank Helbert Ivanilton Polato 46

Edite o arquivo yourRec.txt e coloque suas recomendações nele:Crie um id único a partir de 1000 (chute um valor);

Procure no arquivo filmes.txt por filmes que você já assistiu e classifique-os com nota de 1 a 5.

Cada linha de seu arquivo deverá conter a seguinte estrutura:

<user_id_criado>,<id_filme>,<rating>

ex: 1977,123,4

Faça isto para no mínimo dez filmes.

Preenchendo com suas recomendações

Frank Helbert Ivanilton Polato 47

Preenchendo com suas recomendações

Agora vamos juntar suas recomendações com o arquivo de recomendações de outros usuários com o comando:

:~$ cat yourRec.txt >> rec.txt

Edite o arquivo user.txt que contenha apenas uma linha com seu user_id criado nela.

Frank Helbert Ivanilton Polato 48

Enviando arquivos ao HDFS

Agora que os arquivos estão preenchidos, envie seus dois arquivos para o fs com os comandos:

:~$ bin/hadoop fs -put rec.txt input/rec.txt

:~$ bin/hadoop fs -put user.txt input/user.txt

Frank Helbert Ivanilton Polato 49

Rodando o RecommenderJob

Verificar se o arquivo mahout-core-0.6-job.jar está no diretório raiz do hadoop.

A partir do diretório raiz do hadoop, executar o comando:

:~$ bin/hadoop jar mahout-core-0.6-job.jar

org.apache.mahout.cf.taste.hadoop.item.RecommenderJob

-Dmapred.input.dir=input/rec.txt -Dmapred.output.dir=output

--usersFile input/user.txt

--numRecommendations 10

Frank Helbert Ivanilton Polato 50

Resultados!

Acesse em seu navegador: http://localhost:50070/Opção: “Browse the filesystem”

Verificar os filmes recomendados para você usando o script imprimeFilmes.py com o seguinte comando:

:~$ python imprimeFilmes

Frank Helbert Ivanilton Polato 51

Referências:

LivrosHadoop – The Definitive Guide Tom White – 2ª Ed.

Hadoop in ActionChuck Lam – 1ª Ed.

Mining of Massive DatasetsRajaraman, A. & Ullman, J.D., 2011

Mahout in ActionOwen, S. et al., Manning, 2011

Web: http://wiki.apache.org/hadoop/

Frank Helbert Ivanilton Polato 52

Apêndice

Criar chave ssh e permitir acesso sem senha:

:~$ sudo apt-get install ssh

:~$ ssh-keygen -t rsa

:~$ cat .ssh/id_rsa.pub >> authorized_keys

:~$ ssh localhost