Relatório - WordPress.com

Criação de um Framework Generalista para Filtragem
Colaborativa Baseado em Computação Paralela e Apache
Hadoop
Antenor do Váu Cabrerisso1
1
Instituto de Computação – Universidade Federal do Amazonas (UFAM)
Manaus – AM – Brasil
[email protected]
Abstract. The Collaborative Filtering is a technique widely used in order to
generate recommendations. The main objective of this work is try to solve the
problem encountered by institutions where exists many systems from different
domains that need to generate recommendations. The solution is flexible enough
to not require modifications to treat the various databases available and it attempts to use parallelization techniques and treatment of sparse data in order to
optimize the execution time.
Resumo. A Filtragem Colaborativa (Collaborative Filtering) é uma técnica
muito utilizada com a finalidade de gerar recomendações. O principal objetivo deste trabalho é tentar resolver o problema encontrado por instituições
onde existem vários sistemas de domı́nios diferentes que precisam gerar
recomendações aos seus usuários. A solução proposta é flexı́vel para não necessitar de modificações ao tratar as várias bases de dados disponı́veis e as
tentativas de otimização estão concentradas principalmente na paralelização
do processamento dos conjuntos de dados e no tratamento de dados esparsos.
1. Introdução
A Filtragem Colaborativa (Collaborative Filtering) é uma técnica muito utilizada com a
finalidade de recomendar novos itens através da análise de similaridade entre usuários e
suas opiniões acerca de um conjunto de itens consumidos anteriormente ou seus perfis de
uso de um sistema [Resnick and Varian 1997].
Geralmente as bases de dados processadas por essa técnica são muito grandes e,
com a quantidade cada vez maior de informação gerada pela humanidade, tendem a um
crescimento exponencial que tornaria a aplicação da técnica muito custosa do ponto de
vista computacional.
Outro ponto tradicionalmente problemático e que é muito ampliado pelo tamanho das fontes de dados utilizadas é a grande quantidade de dados esparsos
[Sarwar et al. 2001]. Esse problema deriva principalmente do fato de que cada usuário
avalia apenas uma quantidade muito pequena dos itens disponı́veis no catálogo.
O principal objetivo deste trabalho é tentar resolver o problema encontrado por
instituições onde existem vários sistemas de domı́nios [Evans 2004] diferentes que precisam gerar recomendações aos seus usuários. A implementação deve ser flexı́vel o bastante
para não necessitar de modificações durante o tratamento das bases de dados disponı́veis.
2. Solução
A solução proposta é baseada na criação de um framework chamado RecomFrame que gera recomendações através do cálculo da matriz de co-ocorrência
[Leydesdorff and Vaughan 2006] para os itens avaliados pelos usuários do domı́nio estudado. Após esse passo, a matriz é multiplicada pelo vetor de itens avaliados de cada
usuário. Os resultados para cada item são então somados e os itens com maiores valores são recomendados. É importante salientar que os itens avaliados pelo usuário são
desconsiderados do resultado.
Como exemplo a tabela 1 representa os usuários de um sistema locação de filmes,
a tabela 2, os filmes disponı́veis e a tabela 3 as avaliações que foram coletadas:
Tabela 1. Lista de usuários
Id
1
2
3
4
5
Nome
Antonio
Paulo
Maria
Sandra
Wagner
Tabela 2. Lista de filmes
Id Nome
101 Fargo
102 Heavy Metal
103 Aristocats, The
104 All Dogs Go to Heaven 2
105 Theodore Rex
106 Sgt. Bilko
107 Diabolique
Tabela 3. Lista de avaliações (valores de 1 a 5)
Usuário
1
1
1
2
2
2
2
3
3
3
3
4
4
4
4
5
5
5
5
5
5
Filme
101
102
103
101
102
103
104
101
104
105
107
101
103
104
106
101
102
103
104
105
106
Avaliação
5
3
2
2
2
5
2
2
4
4
5
5
3
4
4
4
3
2
4
3
4
Com base nesses dados a matriz de co-ocorrência será:












5
3
4
4
2
2
1
3
3
3
2
1
1
0
4
3
4
3
1
2
0
4
2
3
4
2
2
1
2
1
1
2
2
1
1
2
1
2
2
1
2
0
1
0
0
1
1
0
1












Os 3 (três) filmes mais bem posicionados na avaliação serão recomendados para
cada usuário conforme pode ser visto na 3:
Tabela 4. Filmes recomendados
Usuário
1
2
3
4
5
Recomendações
104 (32.0) - 106 (17.0) - 105 (15.0)
106 (20.0) - 105 (15.0) - 107 (4.0)
103 (24.0) - 102 (18.0) - 106 (16.0)
102 (36.0) - 105 (25.0) - 107 (9.0)
107 (11.0)
Com o objetivo de tornar a aplicação capaz de manipular grande volume de dados,
a implementação foi criado tendo por base o paradigma MapReduce adotado pelo Apache
Hadoop em sua versão 1.03. Foi escolhido um formato de entrada de dados genérico para
que fosse possı́vel abstrair o domı́nio das informações tratadas. Por conta disso o sistema
aceita apenas como entrada uma lista de avaliações conforme exemplificado pela tabela
3.
O fluxo de execução foi dividido em três etapas:
UserPreferences M/R: Transforma ao entrada de dados para que seja possı́vel
construir a matriz de co-ocorrências.
CoocurrenceMatrix M/R: Cria a matriz propriamente dita.
MatrixFactorization M/R: Esse passo é responsável por gerar as recomendações.
O processamento tem inı́cio com a criação de uma ”distributed cache” contendo a matriz
de co-ocorrências. Em seguida a matriz é processada para cada um dos usuários da base
de dados.
Como um dos objetivos do framework era a manipulação de vários
banco de dados diferentes, foi criado um conjunto de classes sob o pacote
net.cabrerisso.master.gdw2013.recomframe.util.formatter que disponibiliza classes
que facilitam muito a transformação de conjuntos de dados para o formato suportado.
Esse recurso não é disponibilizado pelo Apache Mahout e é um diferencial do RecomFrame.
Durante o desenvolvimento ficou evidente que seria inviável executar o fluxo chamando manualmente cada passo posterior após o término do atual. Para resolver esse
problema foi adotado o utilitário Hamake que é capaz de orquestrar a execução através
de uma única linha de comando. A utilização se dá através da criação de um arquivo no
formato XML contendo definições acerca do fluxo. A ferramenta exige que tanto esse
arquivo XML quanto o jar da aplicação sejam colocados no HDFS entretanto isso não se
mostrou um problema grave.
3. Resultados
Um dos grandes desafios desse trabalho foi a criação do ambiente para testes. Como não
existiam recursos financeiros e nem computacionais que viabilizassem a configuração de
um ambiente Hadoop realmente clusterizado, a opção foi o uso de uma máquina virtual
preparada para trabalhar no modo ”pseudo-distributed” do Hadoop que simula um cluster
real.
O ambiente foi preparado em uma máquina configurada com um processador Intel
Core i7-3612qm de 2.10 GHz, 8 Gb de memória RAM, sob o sitema operacional Microsoft Windows 8.
A máquina virtual foi implementada através do VirtalBox e configurada com 4
núcleos e 4 Gb de memória RAM.
Para validar os resultados da aplicação foi planejada uma comparação com o
método de recomendação baseado em co-ocorrência disponı́vel no Apache Mahout,
versão 0.9. Esse mecanismo foi escolhido devido à sua estabilidade e integração com
o Apache Hadoop. Também foram selecionados bancos de dados do projeto MovieLens
com várias taxas de avaliações, a saber: 100.000, 200.000, 500.000, 1.000.000.
Figura 1. Fluxo de dados da aplicação
Na tabela abaixo é possı́vel notar que os valores dos pesos de cada recomendação
divergem em comparação aos da tabela 4 entretanto os filmes recomendados são os mesmos.
Tabela 5. Recomendações do Mahout
Usuário
1
2
3
4
5
Recomendações
105 (3.75) - 104 (3.5) - 106 (3.4)
106 (2.86) - 105 (2.5) - 107 (2.0)
106 (3.20) - 103 (3.0) - 102 (3.0)
107 (4.50) - 105 (4.2) - 102 (4.0)
107 (3.7)
O Apache Mahout se comportou bem com bases de tamanhos variáveis e demonstrou estabilidade e escalabilidade.
O RecomFrame para bases de 100.000 conjuntos de avaliações mostrou um tempo
de execução bem próximo ao do Mahout para a mesma base mas não foi capaz de escalar
para bases de 500.000 entradas. Seu maior problema foi o consumo excessivo de memória
que acabou por levar o Hadoop a ”matar” o fluxo de execução. Foram realizados testes
com uma base contendo 200.000 entradas mas o problema se repetiu. Por conta disso não
foi possı́vel continuar com os experimentos de desempenho.
Figura 2. Tempos de execução do Mahout e do RecomFrame
4. Conclusão
Apesar dos problemas encontrados durante a fase de testes, o RecomFrame se mostrou
efetivo para processar uma quantidade considerável de conjuntos de avaliações e capaz
de realizar boas recomendações. Seu formato de entrada de dados permite que ele possa
ser utilizados para tratar dados de qualquer domı́nio que possa representar avaliações de
itens e se mostrou assim uma alternativa viável ao Mahout em algumas situações.
Como um ponto de melhoria o RecomFrame poderia ser otimizado, principalmente no passo de geração de recomendações para se tornar mais escalável. Uma possı́vel
solução envolveria a troca de algumas estruturas de dados que consomem muita memória
por versões mais leves como vetores ao invés de HashMaps e ArrayLists.
Outro ponto interessante seria a otimização do algoritmo em si, eliminando alguns
laços condicionais e paralelizando a execução em determinados pontos.
A realização de experimentos em um cluster Hadoop real seria muito importante
a fim de validar qualquer esforço de otimização futuro. Apesar do ambiente virtualizado
ser útil durante o desenvolvimento, não deveria ser considerado como ambiente de testes
devido a todas as suas restrições.
Referências
[Evans 2004] Evans, E. (2004). Domain-driven design: tackling complexity in the heart
of software. Addison-Wesley Professional.
[Leydesdorff and Vaughan 2006] Leydesdorff, L. and Vaughan, L. (2006).
Cooccurrence matrices and their applications in information science: Extending aca to
the web environment. Journal of the American Society for Information Science and
Technology, 57(12):1616–1628.
[Resnick and Varian 1997] Resnick, P. and Varian, H. R. (1997). Recommender systems.
Communications of the ACM, 40(3):56–58.
[Sarwar et al. 2001] Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. (2001). Itembased collaborative filtering recommendation algorithms. In Proceedings of the 10th
international conference on World Wide Web, pages 285–295. ACM.