Smart search in a distributed environment

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Smart Search in a Distributed Environment Pedro Manuel Meneses Henriques Mestrado Integrado em Engenharia Informática e Computação Orientador: João Pedro Mendes Moreira 24 de Junho de 2016 c Pedro Manuel Meneses Henriques, 2016 Smart Search in a Distributed Environment Pedro Manuel Meneses Henriques Mestrado Integrado em Engenharia Informática e Computação Aprovado em provas públicas pelo Júri: Presidente: Ademar Aguiar Arguente: Paulo Azevedo Vogal: João Moreira 24 de Junho de 2016 Resumo A quantidade de informação digital com que lidamos hoje em dia é muito superior há de alguns anos atrás. Para lidar com este crescimento usamos cada vez mais o processamento distribuído, dividindo o trabalho por múltiplas máquinas obtendo uma solução mais rápida e eficiente. Com esta distribuição surge um problema, como consultar a informação distribuída e qual a maneira mais eficiente de o fazer. A solução encontrada foi recorrer a uma base de dados central que mantém a informação coerente e acessível a qualquer serviço sempre que necessária. Ao fazer uma pesquisa, com o aumento da informação aumenta também o número de resultados. É importante ordenar a lista de resultados pelos mais relevantes antes de os entregar ao utilizador final. Foram usados algoritmos de sistemas de recomendação, nomeadamente técnicas colaborativas e baseadas em conteúdo. De forma a combinar as previsões de cada um dos algoritmos de recomendação foi desenvolvida uma técnica híbrida que permite fazer previsões em stream, desde o início do sistema, onde existem poucos utilizadores e avaliações, até o fim onde o anterior já não se verifica. Deste modo conseguimos eliminar os problemas que existem em cada uma das abordagens. No arranque do sistema interessa dar mais peso aos algoritmos baseados em conteúdo, pois estes utilizam apenas as preferências do próprio utilizador. Pelo contrário os algoritmos colaborativos precisam de um grande número de utilizadores e avaliações, e devem ser usados quando estas condições se verificam. Foi demonstrado que existe uma diferença significativa no desempenho ao utilizar esta técnica híbrida de combinação, em detrimento das outras abordagens individuais. É uma técnica inovadora, pois outros algoritmos de sistemas de recomendação estudados utilizam o conceito de pesos estáticos, não adaptando estes pesos ao longo do tempo. Palavras-chave: recommendation systems, content-based filtering, collaborative filtering, combining recommendation systems, ensemble techniques, cold start, database systems, nosql, mongodb, distributed systems, indexing, elasticsearch, rmse, coverage, precision, ndcg, friedman test, nemenyi post hoc, apache mahout, user cf, item cf, svd, weighted ensemble, scala, java i ii Abstract The amount of digital information we deal today is much higher than a few years ago. So we started to use distributed systems, assigning jobs among multiple machines to build a better and more efficient solution. With this distribution a new problem arises, how to query this distributed information and what is the most efficient way to do it. The solution was to use a central database that maintains a consistent and accessible information to any service when required. When making a query, with the increase of information the number of results also increases. It is important that we order this list by the most relevant results, before delivering them to the end user. We used recommendation systems, namely content-based and collaborative techniques. In order to combine the prediction of each recommendation algorithm, a hybrid technique was developed that allow us to make predictions on stream, since the beginning of the system where there are a low amount of users and ratings, to the end when the former don’t apply. This way we can eliminate problems that exist in each one of the approaches. At system startup we can give more weight to the content-based algorithms, because they only use user own preferences. On the contrary collaborative algorithms need a large amount of users and ratings, and therefore should be used when these conditions are met. It was demonstrated that there is a significant difference in performance when using this ensemble technique, over the other individual approaches. It is a innovative technique, since other recommendation algorithms studied use static weights, that don’t adapt over time. Keywords: recommendation systems, content-based filtering, collaborative filtering, combining recommendation systems, ensemble techniques, cold start, database systems, nosql, mongodb, distributed systems, indexing, elasticsearch, rmse, coverage, precision, ndcg, friedman test, nemenyi post hoc, apache mahout, user cf, item cf, svd, weighted ensemble, scala, java iii iv Agradecimentos A realização desta dissertação contou com importantes apoios e incentivos sem os quais não seria possível a realização da mesma. Ao Professor João Pedro Mendes Moreira, pela sua orientação, total apoio e disponibilidade, pelas opiniões e críticas, ajudando sempre com qualquer problema no decorrer do trabalho. Ao CEO da MOG Technologies, Luís Miguel Sampaio por todo o apoio, paciência, ensinamentos e ajuda esclarecendo sempre qualquer dúvida que surgisse. A todos na MOG Technologies, pelo carinho com que acolheram e ajudaram no dia a dia na empresa. Ao Diogo Pinto e Rui Grandão, caminhamos juntos nesta última fase da universidade, o meu muito obrigado pela ajuda ao longo destes meses, desejo os maiores sucessos e felicidades. A todos os docentes, coordenadores e colegas da Faculdade de Engenharia da Universidade do Porto, que contribuíram para o sucesso da minha formação académica e crescimento pessoal. À Margarida por toda a paciência em ouvir e entender mesmo não sendo um tema da sua área. Por toda a ajuda, companhia e apoios diários, o meu muito obrigado. E por último um especial agradecimento à minha família, por todo o apoio que deram nesta e em todas as fases da minha vida. A eles dedico este trabalho. Pedro Manuel Meneses Henriques v LISTA DE FIGURAS xii Lista de Tabelas 2.1 Perfil do utilizador com um histórico dos acessos . . . . . . . . . . . . . . . . . 10 2.2 Valores críticos para o teste de Nemenyi. . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Tabela com os diferentes pedidos que podem ser feitos ao servidor. . . . . . . . . 29 4.1 Tabela com as diferentes situações onde foram calculadas as medidas de avaliação daexperiência. ................................... 39 4.2 Tabela com a correspondência do número Avaliações/Utilizadores (A/U) com RMSE e Coverage (entre parêntesis) dos vários algoritmos testados com o dataset explicito. 40 4.3 Tabela com RMSE e Coverage (entre parêntesis) comparando os algoritmos de ensemble com o melhor algoritmo da Tabela 4.2 (o baseado em conteúdo). . . . . 41 4.4 Tabela com os pesos dados no Ensemble Weighted a cada algoritmo da Tabela 4.2.42 4.5 Tabela com a comparação de pares do RMSE no Nemenyi Post-Hoc. . . . . . . . 44 4.6 Tabela com a comparação de pares da cobertura no Nemenyi Post-Hoc. . . . . . 46 4.7 Tabela com os diferentes datasets onde foram calculados o valor do nDCG. . . . 48 4.8 Tabela com o valor do nDCG@20 dos vários algoritmos testados com o dataset implícito. ...................................... 49 4.9 Tabela com o valor do nDCG@20 comparando os algoritmos de ensemble com o melhor algoritmo da Tabela 4.8 (SVD). ...................... 49 4.10 Tabela com os pesos dados no Ensemble Weighted a cada algoritmo da Tabela 4.8.50 4.11 Tabela com a comparação de pares do nDCG no Nemenyi Post-Hoc. . . . . . . . 52 A.1 Valores críticos para df graus de liberdade . . . . . . . . . . . . . . . . . . . . . 61 A.2 Valorescríticosparak<6 ............................. 62 xiii LISTA DE TABELAS xiv Abreviaturas, Símbolos e Definições Media asset Termo que é utilizado para representar um ficheiro de vídeo, áudio, metadata ou uma agregação dos anteriores MXF Material eXchange Format SMPTE Society of Motion Picture and Television Engineers Ingest Conjunto de regras que permitem automatizar alguns processos de um media asset SQL Linguagem usada em sistemas de bases de dados relacionais NoSQL Sistema de bases de dados não relacional SGBD Sistema de Gestão de Bases de Dados REST Representational state transfer WWW World Wide Web FWLS Feature-Weighted Linear Stacking xv Capítulo 1 Introdução 1.1 Contexto e enquadramento Este trabalho insere-se na área de produção multimédia, estando sendo desenvolvido com o apoio da MOG Technologies, sediada no Parque de Ciência e Tecnologia da Maia no Porto. A MOG é uma empresa com mais de 10 anos de experiência, baseada em padrões standard da indústria multimédia e tem vindo a estabelecer-se no mercado como fornecedor mundial em soluções centralizadas de ingest e ferramentas de desenvolvimento MXF. Material eXchange Format (MXF) é um formato container de vídeo e áudio profissional, definidos por um conjunto de padrões da SMPTE. É um recipiente que suporta uma variedade de formatos comprimidos de vídeo e áudio, juntamente com um invólucro de metadados que descreve o conteúdo do material incluído no ficheiro. É usada pelas principais empresas nacionais e internacionais como a RTP, NBC, FOX, Disney Channel, BBC, MTV e ABC. 1.2 Motivação e Objetivos Numa estação de produção multimédia são diariamente carregadas centenas de novas gravações de peças televisivas. Estas gravações passam por um processo de ingest, onde são transformadas e transferidas para onde são mais precisas, quer seja a estação do editor de vídeo, do áudio ou mesmo do produtor. Com estas transferências, a mesma peça pode ficar replicada por diferentes máquinas e servidores, o que torna difícil a sua localização. O objetivo desta aplicação, é encontrar uma solução que procure pelos media assets em múltiplos servidores, devolvendo sempre o melhor conjunto de resultados ajustado ao utilizador que fez a pesquisa. Porque um editor de vídeo ao fazer a pesquisa de uma peça, interessa ser apresentada a versão não editada, enquanto que um produtor quer ver a versão final e pronta a transmitir. Do ponto de vista tecnológico, este é um tema muito interessante pois a tecnologia evoluiu de uma maneira em que passamos a deixar de depender de um único dispositivo ou serviço, para os 1 Introdução sistemas distribuídos, em que um trabalho pode ser dividido e distribuído por múltiplas máquinas, contribuindo para uma solução mais rápida e eficiente. Pretendemos no fim do trabalho, desenvolver um produto que consiga procurar por todos os media assets que possam estar distribuídos, ao mesmo tempo que colocamos no topo da lista de resultados aqueles itens mais relevantes ao utilizador que fez a pesquisa. Este último deve ser alcançado através da aprendizagem dos hábitos do utilizador. Embora no início, com pouca ou nenhuma informação sobre o utilizador a aplicação ordene os resultados com pouca precisão, o objetivo é ir melhorando ao longo do tempo à medida que esta informação aumenta. 1.3 Estrutura da Dissertação Para além da introdução, esta dissertação contém mais quatro capítulos e quatro anexos. No capítulo 2, é descrito o estado da arte sobre bases de dados, ferramentas de indexação, sistemas de recomendação e como fazer uma avaliação dos resultados. Em cada secção são também apresentados trabalhos relacionados com o tema. No capítulo 3, é apresentada a descrição do trabalho realizado, nomeadamente quais as soluções encontradas para o problema descrito na secção anterior bem como as tecnologias escolhidas. No capítulo 4, é feita uma análise do desempenho do produto produzido, suportado por testes estatísticos de modo validar estes resultados. No capítulo 5, são apresentadas as principais conclusões bem como novas técnicas interessantes que podem ser continuadas num trabalho futuro. No anexo A, são apresentadas tabelas de apoio à revisão bibliográfica. No anexo B, é apresentado o protocolo de comunicação com o servidor onde está a correr a aplicação desenvolvida. No anexo C, são apresentados os algoritmos brute force desenvolvidos para descobrir os melhores pesos a usar nas técnicas de ensemble. No anexo C.2, é apresentado o artigo desenvolvido com foco na técnica de combinação de algoritmos de sistemas de recomendação. 2 Capítulo 2 Revisão Bibliográfica Ao longo deste capítulo pretendemos estudar o que já existe sobre os temas que vão ser abordados nesta tese, encontrando trabalhos relacionados com eventuais aplicações das tecnologias em questão. Vamos estudar soluções de bases de dados existentes, ferramentas de indexação e sistemas de recomendação, de forma a escolhermos as que melhor se aplicam ao produto que vai ser desenvolvido. Vamos também investigar medidas de avaliação de modo a conseguirmos avaliar o produto desenvolvido. 2.1 Bases de dados Uma base de dados é na sua essência nada mais que uma coleção de informação que existe ao longo de um período de tempo, frequentemente muitos anos [1]. Na sua definição mais comum é uma coleção de dados, estruturada de maneira a que um sistema gestor de bases de dados ou SGBD consiga aceder rapidamente a pedaços de informação. É uma coleção de esquemas, tabelas, pesquisas, vistas e outros objetos. 2.1.1 Persistência Uma base de dados pode por vezes tomar grandes dimensões e para serem consultadas no futuro, em caso de falha ou necessidade de reiniciar o sistema, não podem ser guardadas numa memória temporária. Têm que ser guardadas numa memória persistente de um servidor, como um disco rígido ou SSD. Em termos de desempenho é melhor usar um disco SSD, sendo mais rápidos que um disco rígido convencional, pois os tempos de acesso e escrita a um disco são lentos sendo normalmente o bottleneck de um sistema. 3 Revisão Bibliográfica 2.1.2 Bases de dados relacionais (SQL) A base de dados relacional foi o primeiro modelo de dados descrito teoricamente [2], que se baseia em que todos os dados são representados como relações algébricas e os resultados são tratados pelo cálculo ou álgebra relacional. São caraterizados por dois conceitos principais, o de entidade que são os dados recolhidos e guardados numa tabela, e o de relação que associa cada registo a registos de outras tabelas, criando assim uma relação entidade-associação. Um Sistema Gestor de Bases de Dados [1] é uma aplicação que interage com as bases de dados e que permite aos utilizadores criarem novas bases de dados e respetivos esquemas. Tem a capacidade de fazer interrogações e modificar os dados, suporta o armazenamento de grandes quantidades de dados ao longo de um elevado período de tempo, controla o acesso aos dados de modo a não permitir consultas não autorizadas, e permite o uso simultâneo de vários utilizadores sem o perigo de corromper os dados acidentalmente. 1SELECT title,producer 2FROM Movie,MovieExec 3WHERE title=’Star Wars’ AND producer# = cert#; Listing 2.1: Junção de duas tabelas em SQL Estes dados são geralmente normalizados e separados por várias tabelas, sendo que no momento da consulta é feita uma junção desta informação de modo a poder reconstruir os objetos que representam, como exemplificado no código 2.1. Os principais sistemas SGBD [3] são o Oracle, MySQL, Microsoft SQL Server, PostgreSQL e SQLite. 2.1.3 Bases de dados não relacionais (NoSQL) Nos últimos anos a WWW desafiou as bases de dados relacionais como nunca ninguém previu. Primeiro era usado um único servidor com um conjunto de dados pequenos. No outro momento foi preciso configurar replicação de dados para que escale as pesquisas e trate de potenciais falhas. Chegamos a um ponto em que temos que separar os dados por múltiplos clusters e reconstruir a lógica das aplicações de modo a lidar com isso, para no fim chegar à conclusão que estamos usando um esquema de tabelas fixo modelado há muitos meses, o que leva a gastar tempo desnecessariamente que podia ser aproveitado de uma melhor maneira [4]. Com a popularização das linguagens orientadas a objetos, os programadores começaram a tratar os dados como objetos. As bases de dados não relacionais são de mais fácil integração, utilização e manutenção e ao contrário do modelo anterior permite que as relações sejam feitas com objetos e seus atributos e não apenas com campos individuais. 4 Revisão Bibliográfica As bases de dados NoSQL são geralmente mais rápidas, deixando o processamento e lógica dos dados para o lado do cliente [4], não requerem esquemas de tabelas fixos e evitam operações de junção usando dados desnormalizados, sendo desenhadas para escalar horizontalmente. Existem vários modelos de bases de dados não relacionais que diferem entre si tanto na implementação como na forma da representação dos valores e objetos, que vão ser abordados nas secções seguintes. 2.1.3.1 Chave-valor Este é o modelo mais simples de bases de dados NoSQL, onde os dados são representados como uma coleção de chave-valor como ilustrado na Figura 2.1, onde cada chave pode aparecer no máximo uma vez numa coleção. Estas bases de dados não fornecem uma forma de efetuar pesquisas ao conteúdo dos valores armazenados, uma vez que o principal objetivo é o de associar um conjunto de bytes a uma chave única, sendo esta uma das principais caraterísticas que tornam este sistema simples e atrativo. Figura 2.1: Modelo chave-valor: valor guardado com uma chave única Alguns dos principais sistemas de bases de dados [5] são o Redis, Memcached e Riak KV. 2.1.3.2 Baseado em colunas É usado para guardar dados em registos, com a possibilidade de guardar um grande número de colunas dinâmicas como ilustrado na listagem 2.2. Como o nome das colunas e as chaves não é fixo, e como um registo pode conter milhões de colunas, pode ser visto como uma coleção de chave-valor, abordado em 2.1.3.1, multidimensional. O BigTable [6] é considerado a origem desta classe de bases de dados e é atualmente usado internamente nos sistemas da Google. É uma base de dados distribuída que é dividida em pedaços pequenos e servida por milhares de servidores. Alguns dos principais sistemas de bases de dados são [5] o Cassandra, HBase, BigTable e Accumulo. 5 Revisão Bibliográfica Uma mais valia deste algoritmo é que não precisa de entender o conteúdo dos itens, ao contrário da filtragem baseada em conteúdo, pois utiliza as avaliações de utilizadores similares. Os algoritmos de filtragem colaborativa têm que ter a capacidade de lidar com dados esparsos, escalar com o aumento de utilizadores e itens, além de fazer recomendações em um curto período de tempo [18]. Os problemas mais comuns com este algoritmo são: •Necessidade de um grande número de utilizadores e avaliações, pois são estes dados que são usados para treinar o modelo (problema cold start). •Itens têm que ser avaliados por um grande número de utilizadores de modo a serem recomendados a outras pessoas. Itens novos têm poucas ou avaliações insuficientes. •Um utilizador tem que avaliar itens suficientes para que o sistema consiga inferir sobre as suas preferências, pois quando um novo utilizador entra no sistema não tem avaliações. •Devido à medida de similaridade entre utilizadores, um utilizador tem que ser similar a outros na comunidade para conseguir receber recomendações (problema grey sheep). Aqueles com gostos incomuns podem não receber sugestões úteis. 2.3.6 Técnicas híbridas e combinando sistemas de recomendação O aumento de novas estratégias de recomendações está a dar origem a uma grande variedade de opções para o desenvolvimento de sistemas de recomendação. Vários estudos compararam o desempenho de um sistema híbrido com um colaborativo e os baseados em conteúdo, e demonstraram que os primeiros podem fornecer previsões mais precisas que as posteriores que são abordagens puras. Estas técnicas podem ser implementadas de muitas formas, tipicamente combinando técnicas de filtragem colaborativas com as baseadas em conteúdo, para aliviar deficiências e problemas comuns de um ou outro sistema, melhorando a previsão e desempenho das recomendações. Um dos eventos que mais contribuíram para a área dos sistemas de recomendação foi o Netflix Prize. De 2006 a 2009 a Netflix patrocinou um prémio de 1 000 000 $ para a equipa que conseguisse um sistema 10% mais preciso do que o atual da companhia, usando um dataset com mais de 100 milhões de classificações de filmes feitas pelos seus utilizadores. Este concurso gerou muita pesquisa para novas estratégias e algoritmos, tendo a equipa vencedora, utilizado a técnica referida em 2.3.6.1, usando um ensemble de 107 diferentes algoritmos. Cada conjunto de resultados foi combinado de modo a melhorar o resultado final e foi também de onde surgiu o termo blending. Ficou demonstrado que a opinião coletiva geralmente é a mais certa que a de um único perito. As principais abordagens aos sistemas híbridos [19] são: •Com peso: o resultado dos diferentes algoritmos são combinados numericamente ou segundo alguma medida de votação. 12 Revisão Bibliográfica •Comutação: o sistema escolhe entre os algoritmos o melhor para a situação e aplica o selecionado. •Misturado: as recomendações de vários algoritmos são apresentadas em conjunto e ao mesmo tempo pelo meio de alguma medida de classificação ou estratégia de combinação. •Combinação de caraterísticas: caraterísticas de diferentes fontes de conhecimento são combinadas em grupo e dadas a um único algoritmo de recomendação. •Aumento das caraterísticas: um algoritmo é usado para computar um conjunto de caraterísticas, que depois é passado como conjunto adicional de entrada para o próximo algoritmo. •Cascata: é dado uma prioridade a cada sistema de recomendação, em que os com mais baixa prioridade desempatam os algoritmos de maior prioridade. •Objetivo: a recomendação segue um processo sequencial de maneira a que um algoritmo utilize um modelo produzido por outro. 2.3.6.1 Feature-Weighted Linear Stacking Os métodos de ensemble como os de stacking são desenhados para aumentar a precisão dos algoritmos, juntando as previsões de múltiplos sistemas de recomendação. Estudos recentes demonstraram que o uso das caraterísticas dos modelos, adicionando novas entradas descrevendo cada exemplo do dataset, pode impulsionar o desempenho dos modelos de ensemble. A técnica Feature-Weighted Linear Stacking (FWLS) [20] incorpora as caraterísticas dos modelos para uma previsão melhorada, enquanto mantém as mais valias da regressão linear como a rapidez, estabilidade e interoperabilidade. O FWLS combina modelos de previsões lineares usando coeficientes que eles mesmos são funções lineares das caraterísticas. Esta técnica foi uma medida fundamental para a equipa que acabou em segundo lugar no Netflix Prize falado anteriormente. Esta equipa utilizou duas caraterísticas para a combinação dos algoritmos: o número de utilizadores e o número de avaliações de filmes. b(x) = ∑ i wigi(x)(2.3) wié um peso constante dado a cada algoritmo gi(x)é a previsão dos diferentes algoritmos xé o valor de entrada dos algoritmos A técnica mais básica de combinar vários algoritmos é utilizando o Standard Linear Stacking. Como podemos ver pela equação 2.3 e pelo exemplo da Figura 2.4,wié um peso constante dado a cada algoritmo. É um modo simples de combinar várias previsões, mas não consegue se ajustar ao longo do tempo quando as caraterísticas dos modelos mudam. 13 Revisão Bibliográfica Figura 2.4: Standard Linear Stacking A técnica FWLS por outro lado modela os pesos wicomo funções lineares das caraterísticas: wi(x) = ∑ j vi,jfj(x)(2.4) vi,jsão os pesos aprendidos do modelo fj(x)é a função de uma caraterística (meta-feature) Desta maneira a equação 2.3 pode ser rescrita da seguinte forma e visto um exemplo na Figura 2.5: b(x) = ∑ i,j vi,jfj(x)gi(x)(2.5) Figura 2.5: Feature Weighted Linear Stacking Podem ser usadas muitas caraterísticas (meta-features) de modo a combinar vários algoritmos: •Número de utilizadores •Número de avaliações de cada utilizador •Número total de avaliações dos filmes •Número médio de avaliações dos utilizadores que avaliaram o filme 14 Revisão Bibliográfica •Soma das correlações dos filmes que um utilizador já avaliou com o filme que vai ser feita uma previsão •Desvio padrão das avaliações de cada utilizador •Desvio padrão das avaliações dos filmes •Desvio padrão das datas que um filme foi avaliado •Máximo de correlações dum filme com qualquer outro 2.3.7 Medidas de avaliação dos erros Um bom sistema de recomendação é aquele que consegue fornecer previsões precisas. Para isso é preciso avaliar a qualidade dos resultados através do erro que cada sistema tem em relação ao valor observado, ou seja, aquele que no final foi dado pelo utilizador. As métrica mais usadas para medir a previsão são o Mean Absolute Error (MAE) e o Root Mean Squared Error (RMSE): MAE =1 n∑ i,jpi,j−ri,j(2.6) RMSE =s1 n∑ i,j (pi,j−ri,j)2(2.7) pi,jé a classificação prevista do utilizador i no item j ri,jé a classificação dada pelo utilizador i no item j né o numero total de classificações do conjunto a ser testado A métrica mais usada é o RMSE pois penaliza os erros maiores em comparação com o MAE. Um erro crítico destas métricas é que não fazem nenhuma distinção entre os erros que são feitos nos itens do topo das recomendações, dos erros feitos no resto dos itens. Além disso, apenas podem ser aplicadas a previsões onde o resultado está entre o intervalo de valores. Para resultados probabilísticos, ou quando os dados são implícitos (vi o filme ou não vi o filme), o desempenho das posições geradas pelo modelo são avaliadas com métricas baseadas em precisão. Um sistema de recomendação é tão bom quanto o número de vezes que consegue fazer uma previsão. Não interessa ter um erro muito baixo, se na maior parte das vezes não consegue devolver previsões. De modo a avaliarmos a percentagem de cobertura de um algoritmo utilizamos a seguinte equação: Coverage =1 n∑ i|pi|(2.8) 15 Revisão Bibliográfica |pi|é o número total de previsões do utilizador i né o numero total de classificações do conjunto a ser testado 2.3.8 Medidas de avaliação de precisão Ao contrário das medidas anteriores que medem a precisão do resultado de um algoritmo entre um intervalo de valores, as métricas de precisão medem a posição de cada item na lista de recomendações geradas. Exemplos destas métricas são a Precision,Recall eNormalised Discounted Cumulative Gain (nDCG): Precisionp=1 |U|∑ u∈URelItemsp u p(2.9) Recallp=1 |U|∑ u∈URelItemsp u |RelItemsu|(2.10) RelItemsunúmero de itens relevantes para utilizador u RelItemsp unúmero de itens relevantes para utilizador u na lista de recomendações até a posição p Precisionp(Precisão até p) conta a fração de itens relevantes na lista de recomendações, enquanto que o Recallpé a fração de elementos relevantes que já foram recomendados. O problema com as duas medidas anteriores é que não sofrem nenhuma alteração com a ordenação da lista de recomendações. Um resultado altamente relevante pode estar abaixo de outro com menos importância, não mudando o valor da precisão. A premissa do algoritmo DCGpé que os documentos altamente relevantes que apareçam numa posição baixa da lista de resultados devem ser penalizados, com o valor sendo reduzido logaritmicamente, proporcional à posição do resultado. O ganho acumulado com desconto DCGpé definido da seguinte forma: DCGp=Reli+ p ∑ i=2 Reli log2i(2.11) Relié a relevância do resultado na posição i A lista de resultados dos sistemas de recomendação variam em tamanho dependendo da pesquisa efetuada. Comparar o desempenho de uma pesquisa para outra não pode ser feita consistentemente usando apenas o DCGp, então o ganho cumulativo a cada posição pdeve ser normalizada transversalmente entre pesquisas. Isto é feito ordenando a lista de resultados por relevância, produzindo o máximo valor de DCGpaté à posição p, que também é chamado de DCGpideal (IDCGp) 16 Revisão Bibliográfica até àquela posição. Para uma pesquisa o ganho acumulado com desconto normalizado (nDCGp) é calculado da seguinte forma: nDCGp=DCGp IDCGp (2.12) IDCGpindica o valor ideal ou perfeito até posição p De notar que num algoritmo perfeito DCGpvai ser igual a IDCGp, fazendo com que o resultado de nDCGpseja 1. 2.3.9 Friedman test com Nemenyi post-hoc O teste de Friedman é um teste estatístico não-paramétrico desenvolvido por Milton Friedman em 1940. O teste classifica cada algoritmo segundo o seu desempenho atribuindo o valor 1 ao primeiro, 2 ao segundo e assim sucessivamente. Em caso de empate é atribuído o valor médio dos dois. O teste pode ser definido com as seguintes equações [21]: Rj=∑ i rj i(2.13) O Friedman Test compara os vários algoritmos segundo uma hipótese nula, que declara que todos os algoritmos são equivalentes tal como devem ser os seus Rj. X2 F=12 Nk(k+1)∑ j R2 j−3N(k+1)(2.14) rj ié o rank do algoritmo j no dataset i R2 jé a soma do rank do algoritmo j em todos os datasets Né o número total de datasets ké o número total de algoritmos O Friedman test está distribuído segundo o teste qui-quadrado X2 Fcom k−1 graus de liberdade quando N>10 e k>5 (tabela em Anexo A.1). Para um conjunto pequeno de algoritmos e datasets, os valores críticos exatos foram calculados (Zar, 1998; Sheskin, 2000) e podem ser consultados na tabela em Anexo A.2. Se a hipótese nula for rejeitada podemos proceder com um teste Nemenyi post-hoc. Este teste foi criado por Nemenyi em 1963, e diz que o desempenho de dois algoritmos é significativamente diferente quando a respetiva média do rank difere em pelo menos a diferença crítica (CD): CD =qαrk(k+1) 6N(2.15) 17 Revisão Bibliográfica O valor crítico qαé baseado na tabela Studentized Range dividido por √2 (Tabela 2.2). # Algoritmos 2 3 4 5 6 7 8 9 10 q0.05 1.960 2.343 2.569 2.728 2.850 2.949 3.031 3.102 3.164 q0.10 1.645 2.052 2.291 2.459 2.589 2.693 2.780 2.855 2.920 Tabela 2.2: Valores críticos para o teste de Nemenyi. 2.3.10 Trabalhos relacionados Um exemplo da implementação destes algoritmos é na loja de venda de artigos online Amazon, onde são apresentados produtos recomendados ao utilizador (Figura 2.6) baseado no seu perfil de utilizador, ou seja o seu histórico de itens visualizados e comprados no passado, ou fazendo uma comparação do seu perfil com os dos outros utilizadores da loja mostrando resultados dos outros utilizadores com costumes de compra similares. O objetivo é mostrar novos produtos aos utilizadores na esperança que vejam alguma coisa que gostem mas que não conheciam, e que consequentemente façam uma compra [17]. Estes sistemas podem ser valiosos tanto para o utilizador final, que podem ver produtos relevantes, incluindo alguns que não tenham considerado antes, como para as empresas que podem utilizar tais sistemas para aumentar as receitas. Figura 2.6: Recomendação: Produtos similares O Spotify também utiliza destas técnicas, como recomendar músicas similares às que costumamos ouvir e mostrar listas das músicas mais populares de um determinado estilo de música, ou populares na nossa zona e país. Outro exemplo é o Youtube que sugere vídeos similares ao que estamos a ver e apresenta na página inicial vídeos de temas que vemos frequentemente. 18 Revisão Bibliográfica 2.4 Information retrieval Todas as aplicações que recorrem ao input do utilizador, devem previamente recorrer a uma análise do texto introduzido. Desta maneira, pode desde logo ser corrigido algum erro ortográfico, procurar palavras num contexto parecido, como palavras sinónimas e a correspondência em outras línguas. Devem ser criados métodos que lidem com a importância da frequência de termos e seus pesos, de modo a ordenar da melhor maneira os resultados de uma pesquisa. É também interessante recorrer a uma linguagem formal simples, que permite ao utilizador filtrar os resultados presentes na metadata dos media itens, sem ter que recorrer a formulários com diferentes campos. 2.4.1 Similaridade entre palavras O algoritmo Edit Distance [22] com o pseudo-código definido em 2.4, é usado para quantificar quão diferentes são duas palavras, contando o número mínimo de operações necessárias para transformar uma palavra na outra: Inserção de uma letra com um custo de 1 valor Eliminação de uma letra com um custo de 1 valor Substituição de uma letra com um custo de 1 valor 1int LevenshteinDistance(string s, int len_s, string t, int len_t) 2{int cost; 3 4/*base case: empty strings */ 5if (len_s == 0) return len_t; 6if (len_t == 0) return len_s; 7 8/*test if last characters of the strings match */ 9if (s[len_s-1] == t[len_t-1]) 10 cost = 0; 11 else 12 cost = 1; 13 14 /*return minimum of delete char */ 15 return minimum(LevenshteinDistance(s, len_s - 1, t, len_t ) + 1, 16 LevenshteinDistance(s, len_s , t, len_t - 1) + 1, 17 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost); 18 } Listing 2.4: Pseudo-código recursivo do algoritmo Levenshtein Distance É usada uma linguagem natural de processamento, onde é feita uma análise ortográfica, que determina correções candidatas para uma palavra escrita incorretamente, escolhendo uma palavra 19 Revisão Bibliográfica que tenha pouca distância da palavra introduzida. Estudos demonstraram que 80% ou mais dos erros ortográficos são causados pela introdução errada de uma única letra [17]. Uma alternativa ao quadro de custos descrito previamente em que todas as operações têm um custo igual, podemos generalizar permitindo diferentes custos para diferentes tipos de operações [23]. Por exemplo um custo maior pode ser dado em substituir a letra Spor P, do que a substituição por A(a última letra está mais próxima de Sno teclado). Colocando os custos desta maneira, dependendo da substituição de uma letra por outra na vizinhança, é uma maneira eficaz com resultados muito positivos em casos práticos. 2.4.2 Sinónimos e outras línguas Vão ser utilizados dicionários de palavras como o listado em 2.5 que contém palavras sinónimas associadas à pesquisada e a correspondência em outras línguas previamente definidas. Estes dicionários podem ser definidos com o auxílio de várias ferramentas como o ElasticSearch e o Apache Solr. 1{ 2ipod,i-pod,i pod 3foozball,foosball 4universe,cosmos 5big apple,new york,new york city,nyc 6} Listing 2.5: Exemplo de um dicionário de sinónimos e palavras associadas 2.4.3 Frequência de termos A maneira mais simples de fazer pesquisas segundo uma interrogação é saber se um determinado documento contém ou não a interrogação. No caso de documentos com grandes coleções, o número de resultados correspondentes pode exceder em muito o número que os humanos conseguem analisar. É essencial que o motor de pesquisa consiga classificar e ordenar por pontuações os documentos resultantes da interrogação [23]. Figura 2.7: Exemplo da frequência dos termos em três documentos Um documento que contenha mais frequentemente um termo tem mais a ver com a interrogação e portanto deve receber uma pontuação maior. É atribuído um peso para cada termo no 20 Revisão Bibliográfica documento que depende do número de ocorrências. Um exemplo desta contagem de frequências de vários termos por documentos pode ser visto na Figura 2.7. Mas a técnica anterior sofre de um problema crítico, todos os termos de uma interrogação são considerados iguais quanto à sua relevância. Por exemplo na indústria multimédia é provável que quase todos os documentos contenham a palavra vídeo. Para resolver este problema é introduzido um mecanismo que tenta atenuar o efeito dos termos que ocorrem com muita frequência numa coleção, a frequência inversa [23]. A frequência inversa dos termos em documentos, funciona dando uma pontuação alta a um termo raro, ou seja que aparece poucas vezes, enquanto que a pontuação dada a um termo que aparece frequentemente é menor. 2.4.4 JavaCC e JJTree O JavaCC (Java Compiler Compiler) combinado com o JJTree é o mais popular gerador de árvores de gramática para uso com aplicações Java. É uma ferramenta que lê um ficheiro com uma especificação da gramática e converte-a para um programa Java que pode reconhecer padrões que correspondam à gramática. É uma ferramenta útil para utilizar como auxiliar à construção de uma gramática para permitir utilizar uma linguagem formal de pesquisa simples e inteligente. Divide-se em dois processos a análise lexical e sintática. Na primeira o processador tem uma análise superficial sobre o código fonte e divide-o em tokens. Um token pode ser uma palavra, pontuação, número ou string. Os espaços em branco não são considerados tokens, são normalmente ignorados e usados para separação de tokens. Na análise sintática é feita uma análise ao código introduzido a ver se respeita as regras da gramática definida. Se uma das regras é violada é lançado um erro. 1expressao := numero 2| -expressao 3| expressao ’+’ expressao 4| expressao ’-’ expressao 5| expressao ’*’ expressao 6| expressao ’/’ expressao 7 8numero := digito+ (’.’ digito+)? 9 10 digito := ’0’ | ’1’ | ’2’ | ’3’ | ’4’ | ’5’ | ’6’ | ’7’ | ’8’ | ’9’ Listing 2.6: Exemplo das regras de uma gramática As regras definidas no código 2.6 são compostas por três elementos: a expressão, número e dígito. Estes elementos servem para definir uma linguagem simples de operações matemáticas de soma, diferença, multiplicação e divisão com suporte para números negativos e decimais. 21 Implementação 1search fantasy in tags, 2search action in tags, 3search > 7200 in durationSeconds Listing 3.2: Exemplo de uma pesquisa avançada Na listagem em 3.2 vemos a combinação de várias pesquisas filtrando por filmes de fantasia, animação e aqueles com duração superiores a duas horas. Através desta combinação de pesquisas torna-se virtualmente possível fazer qualquer tipo de pesquisa à base de dados, quer seja comparando strings ou usando operadores numéricos como >,<,≥e≤. Uma descrição mais pormenorizada da sintaxe da gramática está disponível no Anexo B.3. Geralmente o utilizador vai usar a interface do produto que constrói a pesquisa automaticamente. Mas nada impede a utilizadores mais avançados de construir as suas próprias filtragens, porque é impossível cobrir na interface todos as combinações e campos possíveis. Além de simplificar as pesquisas ao utilizador, torna-se fácil a interpretação dos termos na parte do servidor. Em vez de definir múltiplos campos HTTP, a pesquisa é enviada tal como nos exemplos em cima e a análise da mesma é feita utilizando analisadores de gramáticas. Este reconhecimento de padrões é feito através da geração de árvores de gramáticas falada na secção 2.4.4. 3.2.2 Boost dos resultados Existem vários tipos de utilizador do produto. Desde produtores, a editores de vídeo, áudio, grafismo, entre outros. Torna-se necessário dar mais a peso a algumas caraterísticas de cada item consoante o tipo de utilizador que está a utilizar o produto. Por exemplo um editor de vídeo pode querer ver em primeiro lugar os ficheiros vídeos das reportagens enquanto que um editor de áudio por sua vez prefere os ficheiros áudio. Podemos também querer ver as reportagens dos últimos dois dias no topo da lista, enquanto que uma pessoa que trabalha nos arquivos prefere ver reportagens mais antigas. Para resolver esta situação podemos configurar para todos os tipos de perfis de utilizador um conjunto de regras, que verificam cada um dos itens da base de dados e multiplicam a respetiva estimativa por um valor definido. 1editor = [ 2{ 3field = "time_ticks", 4value = "last_7_days" // number,string,last_x_days 5operator = "DATE" // Available: >,<,=,>=,<=,BETWEEN,DATE 6boost = 1.2 7} 8] Listing 3.3: Boost de assets dos últimos sete dias 28 Implementação No exemplo do código 3.3 definimos para o perfil de editor, um valor boost de 1.2 para os media asset mais recentes permitindo que estes subam algumas posições na lista de recomendações. 3.2.3 REST A aplicação comunica com o cliente através do protocolo REST abordado na secção 2.5, utilizando objetos serielizados em JSON. É depois implementada uma interface que o cliente utiliza, responsável por interpretar e apresentar os resultados de forma mais visível para os humanos. De seguida podemos ver uma lista dos diferentes pedidos que podem ser feitos à aplicação: URL Definição: /search Obter uma lista de resultados que correspondam ao termo da pesquisa, ordenados pelos algoritmos de sistemas de recomendação /chosen Guarda na base de dados o item que o utilizador clicou da lista de resultados /recommendations Obter uma lista de top N recomendações que podem ser utilizadas para fazer auto-complete à medida que o utilizador digita Tabela 3.1: Tabela com os diferentes pedidos que podem ser feitos ao servidor. Uma descrição detalhada de cada um dos diferentes pedidos e respostas está disponível e pode ser consultada no Anexo B. 3.3 ElasticSearch O ElasticSearch é uma das ferramentas mais populares de pesquisa empresarial [11]. As suas principais características incluem a pesquisa de texto completo, ordenação por frequência de termos em documentos, destaque de palavras ou frases, pesquisa com filtros, indexação em tempo real, integração com dados NoSQL e é projetado para escalabilidade e tolerância a falhas. Esta ferramenta foi escolhida em comparação ao Apache Solr, devido á sua maior simplicidade, rapidez, ser mais escalável, disponibilidade de clientes em diferentes linguagens (Python, PHP, Javascript, Java), possibilidade de fazer perguntas mais complexas, toda a ferramenta ser configurado e questionada através de JSON e a um melhor suporte a dicionários e correção ortográfica. Empresas como o GitHub [12] e o Soundcloud [13] mudaram do Apache Solr para o ElasticSearch devido a problemas de desempenho e escalabilidade, e como milhões de documentos vão ser indexados ao longo dos anos é preferível desde o início utilizar esta ferramenta de modo a evitar problemas futuros. 29 Implementação 3.3.1 Pesquisa com similaridade entre palavras Ao pesquisar no ElasticSearch é utilizado o algoritmo Levenshtein Edit Distance com o máximo de uma operação entre palavras, ou seja, são apresentadas palavras similares onde seja apenas necessário fazer a inserção, eliminação ou substituição de uma letra. Deste modo corrigimos desde logo algum erro ortográfico que o utilizador possa ter feito, pois como referido nos estudos da secção 2.4.1, foi demonstrado que mais de 80% dos erros ortográficos são causados pela introdução errada de uma única letra. 3.4 MongoDB Foi utilizada uma bases de dados não relacional. A aplicação vai ser integrada num produto que está constantemente em evolução, por vezes com diferentes máquinas a utilizar diferentes esquemas, e desta maneira garantimos que qualquer que seja a versão em uso, o esquema de tabelas será sempre válido e compatível. Existe também uma maior simplicidade a guardar objetos mais complexos sem a necessidade de fazer a conversão das estruturas de e para as tabelas nas bases de dados. Um dos maiores objetivos do MongoDB é o desempenho, usando o máximo de RAM disponível enquanto faz cache e tenta escolher os índices corretos automaticamente. Sendo uma ferramenta poderosa, tenta manter tantas caraterísticas quanto possíveis do modelo relacional, mas não é pretendido que faça tudo o que uma base de dados relacional faz. Sempre que possível o servidor envia o processamento e lógica para o lado do cliente. Mantendo este desenho simplificado é uma das principais razões para que o MongoDB consiga tão alto desempenho [4]. Além dos motivos previamente mencionados a escolha do MongoDB deveu-se também a ser o sistema de bases de dados NoSQL mais popular [24] e com melhor suporte, com muitas ferramentas de replicação e tolerância a falhas. Permite também separar várias bases de dados por diferentes discos [25], de maneira a impedir que as operações de leitura e escrita ao disco sejam o ponto de estrangulamento do sistema. A base de dados com os dados mais frequentemente utilizados (os media assets mais recentes), podem ser colocadas num disco SSD de alto desempenho, enquanto que os dados de media assets com alguns anos podem ser colocados num disco rígido que embora tenha velocidades de escrita e leitura inferiores, têm muito mais espaço disponível a um custo mais acessível. 3.5 Apache Mahout O Apache Mahout é uma biblioteca open source de machine learning que contém um conjunto de ferramentas que permite criar sistemas de recomendação customizados, bem como aplicações de clustering e classificação. É uma ferramenta desenhada para o desempenho, escalabilidade e flexibilidade e está pronta para usada em ambientes empresariais. 30 Implementação O Apache Mahout começou em 2008 quando resolveram separar tecnologias do projeto Apache Lucene, que focava-se mais na pesquisa de conteúdo e em técnicas de information retrieval. Desde aí que a ferramenta tem crescido e hoje em dia é apropriada para aplicações com grandes datasets que requerem escalabilidade porque conta com implementações que correm em cima do Apache Hadoop e o Apache Spark. Um dos requisitos da implementação era criar um sistema que pudesse correr numa única máquina. Embora o Apache Mahout seja mais adequado para ser executado num sistema distribuído utilizando o Apache Hadoop, também permite ser executado numa única máquina. Os sistemas de recomendação desta aplicação foram construídos recorrendo a esta ferramenta. Figura 3.3: Arquitetura Apache Mahout 31 Implementação 3.5.1 Modelo de dados Os modelos de dados do Mahout são a interface com a informação sobre a preferência dos utilizadores. Esta informação pode ser retirada de qualquer fonte de dados, por exemplo um ficheiro ou uma base de dados. Nesta aplicação utilizamos uma base de dados não relacional, com o MongoDB. Os utilizadores e itens são identificados unicamente pelo ID no Apache Mahout. 3.5.2 Sistemas de recomendação do Apache Mahout O Apache Mahout contém os principais algoritmos de sistemas de recomendação. Neste contexto em particular vão ser explorados os algoritmos de filtragem baseada em conteúdo bem como os de colaboração colaborativa, recorrendo a utilizadores e a itens. 3.5.2.1 Filtragem colaborativa baseada em utilizadores Este algoritmo foca-se nas similaridades entre as preferências dos utilizadores. Começa primeiro por criar uma vizinhança nude utilizadores que são parecidos ao utilizador uutilizando medidas de similaridade. De seguida, usando nué estimada a preferência de upara o item itendo em consideração todas as preferências dos vizinhos nuque avaliaram o item i. 1para cada outro utilizador W diferente de U 2calcular similaridade S entre utilizador U e W 3guarda utilizadores com maior similaridade S na vizinhanca N 4 5para cada vizinho V em N 6se V tem preferencia para item I 7obter preferencia P 8guardar preferencia do utilizador U com o item I aplicando peso 9 10 retorna preferencia normalizada de U para item I Listing 3.4: Pseudocódigo do algoritmo FC baseado em utilizadores 3.5.2.2 Filtragem colaborativa baseada em itens Este algoritmo também vai recomendar um item iao utilizador uutilizando uma medida de similaridade. Difere do baseado em utilizadores porque foca-se principalmente nas semelhanças entre as preferências de diferentes itens do que diferentes utilizadores. 1para cada item J que utilizador U tem preferencia 2calcular similaridade S entre items J e I 3 4para cada item J similar com I 5calcular preferencia com peso P para item I multiplicando 32 Implementação 6preferencia de U do item J por S 7guardar P numa preferencia geral P0 8 9retornar P0 normalizado Listing 3.5: Pseudocódigo do algoritmo FC baseado em itens 3.5.2.3 Filtragem baseada em conteúdo Ao contrário dos algoritmos baseados em filtragem colaborativa, os baseados em conteúdo precisam de analisar o conteúdo dos itens de modo a conseguir sugerir recomendações. Como tal, foi definida uma função de semelhança (Listagem 3.6) que devolve um valor de similaridade entre um item e outro. Desta maneira, e após termos alguma preferência do utilizador u, quer seja através de itens já avaliados, ou indo ao perfil do utilizador, conseguimos sugerir itens similares. 1def similarity(item1, item2): 2tags1 = item1["tags"] 3tags2 = item2["tags"] 4similarity = 0.0 5 6for tag in tags1: 7if tag in tags2: 8similarity += 0.1 9 10 return similarity if similarity < 1 else 1 Listing 3.6: Pseudocódigo da medida de similaridade baseada em conteúdo 3.5.3 Combinação dos diferentes algoritmos Para combinar as diferentes abordagens de sistemas de recomendação foram utilizadas técnicas como as faladas em 2.3.6, nomeadamente a combinação dos resultados dos diferentes algoritmos para melhorar o resultado final. Foi criada uma nova classe de recomendadores do Apache Mahout para suportar esta combinação. É uma classe genérica que aceita qualquer conjunto de recomendadores, ou seja, nada impede de usar algoritmos repetidos mudando apenas os valores de inicialização, porque um pode resultar melhor em determinada situação que outro. Foram criados dois algoritmos diferentes para a combinação dos resultados, o primeiro e o mais simples referido daqui para a frente como Ensemble Average, faz a média do resultado de saída de todos os algoritmos: 33 Implementação EnsembleAverage(u,j) = 1 |g|∑ i gi(u,j)(3.1) gi(u,j)é a classificação prevista do utilizador u com o item j pelo algoritmo gi |g|é o numero total de algoritmos O segundo algoritmo, daqui em diante referido como Ensemble Weighted, segue uma abordagem semelhante ao Feature-Weighted Linear Stacking (FWLS) abordado em 2.3.6.1. É importante dizer que o FWLS serve para aplicar um peso a cada algoritmo segundo uma função de caraterística num dataset estático, onde não existe uma medida temporal. Pelo contrário o sistema de recomendação desenvolvido no âmbito desta tese, pretende fazer previsões em stream (sequenciais), onde existe o conceito do tempo em que a avaliação foi adicionada ao modelo, e é da maior importância dar mais peso ou não a uma caraterística ao longo do tempo. O objetivo é arrancar o sistema no início sem nenhum utilizador nem avaliação, e ao longo do tempo adaptar as funções de peso em função do número de utilizadores e avaliações. Este algoritmo pode ser definido com as seguintes equações: EnsembleWeighted(u,j,m,f) = ∑ i wi(m,f)gi(u,j)(3.2) gi(u,j)é a classificação prevista do utilizador u com o item j pelo algoritmo i wi(m,f)devolve o peso do algoritmo i consoante as caraterísticas do modelo atual ∑iwi(m,f)tem um valor obrigatório igual a 1. A função wi(m,f)devolve o valor do peso para o algoritmo icaso as caraterísticas do modelo atual estejam dentro do intervalo de configuração: wi(m,f) =      pi,xif m≤x,x∈f 0 otherwise (3.3) msão as caraterísticas atuais do modelo fé o conjunto de caraterísticas ordenadas definidas na configuração pi,xé o peso do algoritmo i para uma caraterística x das configurações f Podemos colocar (configuração na Listagem 3.7) que enquanto houver menos de 10 utilizadores e 500 avaliações utilizar um peso de 0.7 para a filtragem baseada em conteúdo, e apenas 0.3 para a colaborativa. De igual modo, quando já tivermos 50 000 avaliações e 300 utilizadores, configuramos um peso de 0.8 para a filtragem colaborativa e 0.2 para a baseada em conteúdo. 34 Implementação 1weightFunctions = [ 2{ 3// users, ratings 4features = [10, 500] //x na equacao 3.3 5//order=content,user-cf,svd-cf,item-cf 6weights = [0.7, 0.1, 0.1, 0.1] // p_x na equacao 3.3 7}, 8{ 9// users, ratings 10 features = [300, 50000] 11 //order=content,user,svd,item 12 weights = [0.2, 0.1, 0.2, 0.5] 13 } 14 ] Listing 3.7: Configuração dos pesos do Ensemble Weighted Para aprender os melhores pesos a aplicar em cada algoritmo, foram desenvolvidos dois algoritmos brute force, que testam todas as combinações possíveis de forma a encontrar o melhor resultado possível para a experiência em execução. O algoritmo para minimizar o erro RMSE e o para maximizar o nDCG podem ser consultados no Anexo C. De notar que embora tenhamos só falado em duas caraterísticas nomeadamente o número de utilizadores e avaliações totais, podemos utilizar um conjunto vasto de caraterísticas. Uma lista de possíveis caraterísticas foram faladas no fim da secção 2.3.6.1. No entanto a combinação destas duas têm já resultados comprovados pois foram usadas por uma das equipas vencedoras do Netflix Prize. 35 Implementação 36 Capítulo 4 Avaliação Empírica Neste capítulo são apresentados os resultados das experiências efetuadas, sendo possível analisar o desempenho das abordagens implementadas com os diferentes algoritmos, utilizando as medidas de avaliação sugeridas em 2.3.7 e2.3.8. 4.1 Dataset Nos testes com a biblioteca Apache Mahout foi usado o dataset MovieLens do GroupLens. Esta coleção contém informação sobre o nome e categoria dos filmes, bem como as preferências dos utilizadores em cada filme que avaliaram. O dataset conhecido como MovieLens100k, referido daqui para a frente como dataset explicito, contém cerca de 100 000 avaliações num intervalo entre 1 e 5, por parte de 700 utilizadores em 10000 filmes com 6100 categorias. Um segundo dataset referido daqui para a frente como dataset implícito, é uma variação do primeiro com a diferença de ter sido convertido (com o código em 4.1) de forma a emular um modelo de dados implícito, ou seja, uma entrada (user,item) significa que o utilizador viu, gostou ou está interessado no filme. 1#user_id,item_id,rating 2#1,16,4.0 3 4for rating in file: 5str = line.split(",") 6user_id = str[0] 7item_id = str[1] 8 9doc = {"user_id" : user_id, "item_id" : item_id} 10 database.save(doc) Listing 4.1: Pseudocódigo da conversão do dataset 37 Avaliação Empírica EnsembleA EnsembleW Content User SVD Item 0.4 0.6 0.8 1 1.2 1.4 1.6 Algoritmos RMSE Figura 4.3: Distribuição do RMSE dos algoritmos: mínimo, primeiro quartil, mediana, terceiro quartil e máximo. Combinando os resultados dos vários algoritmos (Tabelas 4.2 e4.3) conseguimos construir o nosso teste. A Figura 4.3 resume a distribuição dos erros dos vários algoritmos. Baseado numa inspeção visual, podemos assumir que os algoritmos User e SVD foram os que tiveram maiores erros. Por outro lado o Ensemble Weighted e o Item obtiveram os erros menores. Ficamos com k=6 (algoritmos) e N=12 (datasets). Como k>5 e N>10 vamos utilizar a fórmula do Friedman’s Rank Test com α=0.05 e de seguida fazer o Nemenyi Post-Hoc Test caso a hipótese nula seja refutada: d f =k−1 X2(d f =5,α=0.05) = 11.0705 F(k=6,N=12) = 25.1340 CD(qα=2.85) = 2.1767 (4.1) Como o resultado de F>X2rejeitamos a hipótese nula H0, provando que existe diferença no desempenho dos vários algoritmos, como pretendíamos demonstrar. Ensemble A Ensemble W Conteúdo User FC SVD FC Ensemble W 0.8370 - - - - Conteúdo 0.2729 0.0113 - - - User FC 0.1560 0.0043 0.9998 - - SVD FC 0.0699 0.0012 0.9911 0.9995 - Item FC 0.9965 0.5376 0.5741 0.3962 0.2209 Tabela 4.5: Tabela com a comparação de pares do RMSE no Nemenyi Post-Hoc. 44 Avaliação Empírica Figura 4.4: Diferença crítica do RMSE no Nemenyi Post-Hoc Test: algoritmos significativamente diferentes não estão ligados (CD=2.1767, α=0.05) Analisando a diferença crítica CD do Nemenyi Test comparando os pares na Tabela 4.5 e observando a Figura 4.4, conseguimos ver que a distribuição do Ensemble Weighted tem uma diferença significativa em comparação à dos algoritmos SVD e User (p< 0.01), bem como com o baseado em conteúdo (p< 0.05). O SVD tem um erro médio muito superior em relação ao Ensemble Weighted (+0.1287). Demonstramos que existe uma melhoria ao utilizar o algoritmo de ensemble em detrimento do baseado em conteúdo, User FC e SVD. No entanto não conseguimos provar o mesmo em relação ao Item FC. Para isso vamos fazer de novo o teste estatístico, desta vez utilizando os valores de cobertura de cada algoritmo. 45 Avaliação Empírica EnsembleA EnsembleW Content User SVD Item 0 0.2 0.4 0.6 0.8 1 Algoritmos Coverage Figura 4.5: Distribuição da cobertura dos algoritmos: mínimo, primeiro quartil, mediana, terceiro quartil e máximo. A Figura 4.5 resume a distribuição da cobertura dos vários algoritmos. Baseado numa inspeção visual, vemos à partida que ambos os algoritmos de ensemble e o baseado em conteúdo mantêm uma distribuição constante e muito próxima dos 100%. Por outro lado os algoritmos colaborativos começam com uma cobertura de 0% e vão oscilando ao longo do tempo. Fazendo de novo o teste com α=0.05 e usando os valores de cobertura: X2(d f =5,α=0.05) = 11.0705 F(k=6,N=12) = 33.7570 CD(qα=2.85) = 2.1767 (4.2) Como o resultado de F>X2rejeitamos de novo a hipótese nula H0, provando que existe também uma diferença de desempenho a nível da cobertura entre os vários algoritmos. Ensemble A Ensemble W Conteúdo User FC SVD FC Ensemble W 0.5013 - - - - Conteúdo 0.1758 0.9911 - - - User FC 0.0001 0.0603 0.2460 - - SVD FC 0.1975 0.9943 1.0000 0.2209 - Item FC 0.0001 0.0699 0.2729 1.0000 0.2460 Tabela 4.6: Tabela com a comparação de pares da cobertura no Nemenyi Post-Hoc. 46 Avaliação Empírica Figura 4.6: Diferença crítica da cobertura no Nemenyi Post-Hoc Test: algoritmos significativamente diferentes não estão ligados (CD=2.1767, α=0.05) Analisando a diferença crítica CD do Nemenyi Test comparando os pares na Tabela 4.6 e observando a Figura 4.6, conseguimos ver que a distribuição do Ensemble Average tem uma diferença significativa em comparação à dos algoritmos User FC e Item FC (p< 0.01), tendo o último uma cobertura muito inferior em relação ao primeiro (-24%). Foi demonstrado que a hipótese H1mantém-se, validando os resultados da experiência com o dataset explícito. Combinar os vários algoritmos com as técnicas de ensemble leva a um desempenho superior às restantes abordagens individuais. 4.5 Experiência com o dataset implícito Para analisar o desempenho das experiências efetuadas com este dataset foi usada uma das medidas de avaliação de precisão presentes em 2.3.8, nomeadamente o nDCG. Escolhemos não utilizar o Precision ou o Recall pois estas não avaliam a posição de um item na lista de resultados, ou seja, um item aparecer em primeiro ou em último na lista de recomendações devolvidas não fazia diferença. É importante referir que não vão ser apresentados os valores de cobertura de cada algoritmo ao longo desta secção, pois todos os algoritmos conseguiram uma cobertura de 100%, tornando-se numa medida sem interesse em ser apresentada e comparada. O dataset foi avaliado com o seguinte processo para cada um dos utilizadores: 47 Avaliação Empírica 1. São retiradas N avaliações aleatórias do perfil do utilizador 2. Modelo é treinado de novo 3. É pedida uma lista de N recomendações ao sistema 4. Se é devolvida uma lista não vazia (a) Calculado nDCG comparando a lista devolvida com as avaliações retiradas 5. Avaliações retiradas são de novo adicionados ao modelo 6. Se não é o último utilizador: (a) Passa para o seguinte e volta ao passo 1 7. Caso contrário: (a) Fim do processo O dataset implícito foi ordenado por ordem cronológica e foram criados 6 datasets (Tabela 4.7) com diferentes janelas. Cada janela indica o intervalo retirado do dataset principal. Desta maneira conseguimos perceber como é que cada algoritmo vai evoluindo à medida que tem acesso a mais informação. Dataset Percentagem Intervalo da janela Número de avaliações Número de utilizadores 1 0.1% 0%-0.1% 106 4 2 0.5% 0%-0.5% 527 15 3 1% 0%-1% 1054 25 4 10% 0%-10% 10534 158 5 50% 0%-50% 52670 392 6 100% 0%-100% 105339 668 Tabela 4.7: Tabela com os diferentes datasets onde foram calculados o valor do nDCG. Começamos por referir que ao contrário da experiência anterior com o dataset explícito em que o algoritmo baseado em conteúdo foi o melhor individualmente, o mesmo não se observou nesta experiência. De alguma forma a medida de similaridade definida em 3.5.2.3 não funcionou tão bem para este tipo de dataset. É uma situação que deve ser investigada no futuro, que provavelmente podia ser resolvida se houvesse mais dados disponíveis sobre cada filme. Esta medida compara dois filmes somando um valor por cada categoria igual, e tendo acesso a mais informação de certo conseguiria ter um desempenho superior. Os dados da Tabela 4.8 são o resultado do processo especificado no início desta secção em cada um dos datasets da Tabela 4.7. A sublinhado na tabela está o melhor algoritmo em cada um dos 6 datasets, estando a soma no final da mesma. De lembrar que um valor perfeito de nDCG é igual a 1, significando que todos os filmes retirados foram devolvidos na lista de recomendações. 48 Avaliação Empírica Dataset Conteúdo User FC SVD FC Item FC 0.1% 0.1612 0.3805 0.4638 0.2981 0.5% 0.1672 0.5281 0.5114 0.3810 1% 0.1096 0.5358 0.5663 0.2510 10% 0.0600 0.3557 0.4617 0.1446 50% 0.0129 0.2266 0.3082 0.0840 100% 0.0041 0.2625 0.3637 0.1018 Média 0.0858 0.3815 0.4458 0.2101 Superior 0/6 1/6 5/6 0/6 Tabela 4.8: Tabela com o valor do nDCG@20 dos vários algoritmos testados com o dataset implícito. No algoritmo User FC foi utilizado o Log Likelihood Similarity com N=40 como medida de similaridade de vizinhança, pois foi o que obteve melhores resultados. Para o algoritmo Item FC o com melhores resultados foi o Tanimoto Coefficient Similarity. Contrário ao que seria de esperar no início do sistema com apenas 106 avaliações, os algoritmos colaborativos tiveram um valor de nDCG bastante alto, mostrando que no arranque funcionam melhor com datasets implícitos do que com explícitos. Analisando individualmente cada um dos algoritmos, o melhor é sem dúvida o SVD, tendo sido superior em 5 dos 6 datasets. É interessante verificar que o valor da precisão vai aumentando na maioria dos algoritmos até às 1054 avaliações, mas depois disso tende a diminuir à medida que a informação aumenta. Esta situação pode ser explicada devido ao ruído dos itens da vizinhança, com muitos filmes que são populares entre os restantes utilizadores a se sobrepor aos filmes retirados. Na experiência anterior do dataset explícito, todos os algoritmos foram pelo menos uma vez os melhores em uma das situações (Tabela 4.2). Neste momento não existe evidência que ao combinar os vários algoritmos pudesse levar a um ganho no desempenho porque o algoritmo SVD mantevese consistentemente o melhor, tendo sido só ultrapassado pelo User FC numa única situação com uma diferença de 0.0167. Dataset Ensemble Average Ensemble Weighted 0.1% 0.2840 -0.1798 0.4976 0.0338 0.5% 0.5388 0.0274 0.5995 0.0881 1% 0.4862 -0.0800 0.5957 0.0295 10% 0.3333 -0.1284 0.4703 0.0087 50% 0.1924 -0.1158 0.3116 0.0034 100% 0.2178 -0.1459 0.3687 0.0050 Média 0.3421 -0.1038 0.4739 0.0281 Soma erro ∑= -0.6225 ∑= 0.1685 Superior 0/6 6/6 Tabela 4.9: Tabela com o valor do nDCG@20 comparando os algoritmos de ensemble com o melhor algoritmo da Tabela 4.8 (SVD). 49 Avaliação Empírica No entanto prosseguimos a experiência combinando os vários algoritmos. A sublinhado na Tabela 4.9 está o melhor algoritmo em cada um dos 6 datasets, estando a soma no final da mesma. Como foi explicado no capítulo anterior, O Ensemble Average faz uma média do resultado de saída de todos os outros algoritmos, enquanto que o Ensemble Weighted, faz uso de um conjunto de pesos aprendidos que variam ao longo do tempo consoante o nível de utilizadores e avaliações. Comparando com os resultados da Tabela 4.8, o algoritmo Ensemble Weighted conseguiu um ganho no desempenho tendo sido o melhor em todas as situações. Com este método conseguimos um aumento na precisão de 0.0281. Dataset w1 w2 w3 w4 0.1% 0 0 0.96 0.04 0.5% 0.02 0.04 0.94 0 1% 0.02 0.02 0.96 0 10% 0 0 1 0 50% 0 0 1 0 100% 0 0 1 0 Média 0.0067 0.0100 0.9767 0.0067 Tabela 4.10: Tabela com os pesos dados no Ensemble Weighted a cada algoritmo da Tabela 4.8. Os pesos dados pelo Ensemble Weighted ao longo do tempo foram aprendidos com o algoritmo brute force descrito no Anexo C.2. Podemos ver na Tabela 4.10 os melhores pesos possíveis para esta experiência. Como era esperado deu um peso de quase 100% em todas as situações ao algoritmo SVD, combinando ao longo dos datasets pequenas percentagens dos outros algoritmos de modo a conseguir o ganho descrito anteriormente. Embora o algoritmo baseado em conteúdo tenha sido o que obteve pior resultado nesta experiência, é interessante verificar que foram usadas pequenas percentagens deste algoritmo, provavelmente porque no início do dataset as abordagens colaborativas nem sempre conseguem fazer previsões para todos os casos, tendo a abordagem baseada em conteúdo complementado as colaborativas. 50 Avaliação Empírica 0.1% 0.5% 1% 10% 50% 100% 0 0.1 0.2 0.3 0.4 0.5 0.6 Dataset nDCG@20 Filtragem baseada em conteúdo Filtragem colaborativa User Filtragem colaborativa SVD Filtragem colaborativa Item Ensemble Average Ensemble Weighted Figura 4.7: Valor do nDCG@20 dos vários algoritmos em todos os datasets. Analisando a Figura 4.7 conseguimos ver como é que os valores de nDCG variam ao longo do tempo. O Ensemble Weighted é aquele que consegue consistentemente os melhores resultados, tendo uma magnitude de bom nível em relação às restantes abordagens. É interessante verificar que nos últimos três datasets o peso dado pelo Ensemble Weighted ao SVD foi 100%, mas mesmo assim conseguimos um melhor resultado com a primeira abordagem. Tal aconteceu porque por defeito o Apache Mahout em caso de empate do valor da estimativa dos vários itens, ordena os resultados de uma maneira aleatória. Por outro lado o Ensemble Weighted ordena por estimativa e em caso de empate por ordem alfabética. De alguma maneira nesta experiência, fazendo esta segunda ordenação leva a que mais itens relevantes apareçam no topo da lista de resultados. Foram faladas em duas hipóteses H0eH1anteriormente. Uma dizia que não existe diferença no desempenho dos vários algoritmos e a outra o oposto. De modo a validar os resultados apresentados anteriormente, temos que conseguir refutar H0. 51 Avaliação Empírica EnsembleA EnsembleW Content User SVD Item 0 0.1 0.2 0.3 0.4 0.5 0.6 Algoritmos nDCG Figura 4.8: Distribuição do nDCG dos algoritmos: mínimo, primeiro quartil, mediana, terceiro quartil e máximo. Combinando os resultados dos vários algoritmos (Tabelas 4.8 e4.9) conseguimos construir o nosso teste. A Figura 4.8 resume a distribuição da precisão dos vários algoritmos. Baseado numa inspeção visual, vemos à partida que os algoritmos Item e baseado em conteúdo são os que conseguem obter uma menor precisão. Por outro lado o Ensemble Weighted e o SVD obtiveram as precisões maiores. Ficamos com k=6 (algoritmos) e N=6 (datasets). Como k>5 vamos utilizar a fórmula do Friedman’s Rank Test com α=0.05 e de seguida fazer o Nemenyi Post-Hoc Test caso a hipótese nula seja refutada: d f =k−1 X2(d f =5,α=0.05) = 11.0705 F(k=6,N=6) = 27.4286 CD(qα=2.85) = 3.0784 (4.3) Como o resultado de F>X2rejeitamos a hipótese nula H0, provando que existe diferença no desempenho dos vários algoritmos, como pretendíamos demonstrar. Ensemble A Ensemble W Conteúdo User FC SVD FC Ensemble W 0.0917 - - - - Conteúdo 0.3388 0.0001 - - - User FC 0.9723 0.4324 0.0611 - - SVD FC 0.7339 0.8200 0.0090 0.9898 - Item FC 0.9400 0.0052 0.8895 0.5335 0.1880 Tabela 4.11: Tabela com a comparação de pares do nDCG no Nemenyi Post-Hoc. 52 Avaliação Empírica Figura 4.9: Diferença crítica do nDCG no Nemenyi Post-Hoc Test: algoritmos significativamente diferentes não estão ligados (CD=3.0784, α=0.05) Analisando a diferença crítica CD do Nemenyi test comparando os pares na Tabela 4.11 e observando a Figura 4.9, conseguimos ver uma diferença significativa entre as distribuições do: •Ensemble Weighted e o baseado em conteúdo (p< 0.01) •Ensemble Weighted e o Item FC (p< 0.01) •SVD e o baseado em conteúdo (p< 0.01) Foi demonstrado que a hipótese H1mantém-se, validando os resultados da experiência com o dataset implícito. Foi provado que combinar os vários algoritmos com a técnica de ensemble leva a um desempenho superior às abordagens baseadas em conteúdo e Item FC. Embora a precisão do Ensemble Weighted seja superior ao SVD e User FC, não ficou demonstrado que essa diferença seja muito significativa. 4.6 Conclusões No início do capítulo, de modo a validar os resultados das duas experiências, propusemo-nos a estudar duas hipóteses, a hipótese nula H0que afirma não existir diferença no desempenho dos vários algoritmos de recomendação, e a hipótese alternativa H1que afirma haver uma diferença no desempenho. 53 BIBLIOGRAFIA 60 Anexo A Revisão Bibliográfica A.1 Distribuição Qui-quadrada df α< 0.1 α< 0.05 α< 0.025 α< 0.01 α< 0.001 1 2.706 3.841 5.024 6.635 10.828 2 4.605 5.991 7.378 9.210 13.816 3 6.251 7.815 9.348 11.345 16.266 4 7.779 9.488 11.143 13.277 18.467 5 9.236 11.070 12.833 15.086 20.515 6 10.645 12.592 14.449 16.812 22.458 7 12.017 14.067 16.013 18.475 24.322 8 13.362 15.507 17.535 20.090 26.125 9 14.684 16.919 19.023 21.666 27.877 10 15.987 18.307 20.483 23.209 29.588 11 17.275 19.675 21.920 24.725 31.264 12 18.549 21.026 23.337 26.217 32.910 13 19.812 22.362 24.736 27.688 34.528 14 21.064 23.685 26.119 29.141 36.123 15 22.307 24.996 27.488 30.578 37.697 16 23.542 26.296 28.845 32.000 39.252 17 24.769 27.587 30.191 33.409 40.790 18 25.989 28.869 31.526 34.805 42.312 19 27.204 30.144 32.852 36.191 43.820 20 28.412 31.410 34.170 37.566 45.315 Tabela A.1: Valores críticos para df graus de liberdade 61 Revisão Bibliográfica A.2 Tabela do Friedman Test k N α< 0.1 α< 0.05 α< 0.01 3 3 6 6 - 3 4 6 6.5 8 3 5 5.2 6.4 8.4 3 6 5.33 7 9 3 7 5.43 7.14 8.86 3 8 5.25 6.25 9 3 9 5.56 6.22 8.67 3 10 5 6.2 9.6 3 11 4.91 6.54 8.91 3 12 5.17 6.17 8.67 3 13 4.77 6 9.39 3∞4.61 5.99 9.21 4 4 6 6 - 4 3 6.6 7.4 8.6 4 4 6.3 7.8 9.6 4 5 6.36 7.8 9.96 4 6 6.4 7.6 10 4 7 6.26 7.8 10.37 4 8 6.3 7.5 10.35 4∞6.25 7.82 11.34 5 5 7.47 8.53 10.13 5 4 7.6 8.8 11 5 5 7.68 8.96 11.52 5∞7.78 9.49 13.28 Tabela A.2: Valores críticos para k < 6 A.3 Metadata de um media asset 1{ 2"_id" : ObjectId("5693eace1993a316044e04c2"), 3"ClusterName" : "", 4 5"DateEnqueuedUtc" : { 6"Ticks" : NumberLong(635881600786495841) 7}, 8"DateFinishedUtc" : { 9"Ticks" : NumberLong(635881605640183456) 62 Revisão Bibliográfica 10 }, 11 "DateScheduledUtc" : { 12 "Ticks" : NumberLong(635881600786145821) 13 }, 14 "DateStartedUtc" : { 15 "Ticks" : NumberLong(635881600789356005) 16 }, 17 "ErrorMessage" : "", 18 "Id" : "5693eace1993a316044e04c2", 19 "IsActive" : true, 20 "Label" : "Ingest TELEPIX Tue Jan 12 2016 01:47", 21 "LastUpdate" : { 22 "Ticks" : NumberLong(635881605640183456) 23 }, 24 "Metadata" : { 25 "CreationDate" : "2016-01-10T01:10:40Z", 26 "CustomMetadata" : [ 27 { 28 "Key" : "umid", 29 "Value" : "06.0a.2b.34.01.01.01.05.01.01.0d.23.13.a1.3a.42.e6.c0.a0 .37.56.b6.e5.11.b1.35.00.d0.28.0f.6f.90" 30 }, 31 { 32 "Key" : "name", 33 "Value" : "" 34 }, 35 { 36 "Key" : "codec", 37 "Value" : "MPEG2 Video" 38 }, 39 { 40 "Key" : "aspect_ratio", 41 "Value" : "16:9" 42 }, 43 { 44 "Key" : "end_timecode", 45 "Value" : "14:36:15:25" 46 } 47 ], 48 "DPP" : [], 49 "DppTimecodeParts" : [], 50 "DropFrame" : true, 51 "Duration" : "00:14:22:07", 52 "EditRate" : "", 53 "FileDate" : "2016-01-10T00:48:57Z", 54 "FrameRate" : "59.94i", 55 "Locators" : [], 56 "NumAudioChannels" : 4, 57 "StartTimecode" : "14:21:53:16" 63 Revisão Bibliográfica 58 }, 59 "NamingCounter" : 2, 60 "OperationHostAddress" : "ops-xpr-073", 61 "OutputName" : "UNIVERSAL_010816_TONI BRAXTON-UNBREAK MY HEART-INTERVIEW_B CAM_1421_1_001", 62 "ParentRuleId" : "MediaIndexer{D49B766E-0D1C-443C-BD74-936EF8D2D2D3}", 63 "Priority" : 1, 64 "QueueIndex" : 2.14748e+009, 65 "Status" : { 66 "operationHostAddress" : "ops-xpr-073", 67 "operationId" : "", 68 "percentComplete" : 100, 69 "resultData" : "", 70 "state" : 3 71 }, 72 "Title" : "UNIVERSAL_010816_TONI BRAXTON-UNBREAK MY HEART-INTERVIEW_B CAM_1421_1", 73 "ToLocalOH" : false, 74 "Version" : "1.0.0", 75 "WorkflowId" : "1ad5ec67-9cd0-6865-62df-277dbe5096f2", 76 "FlowTimeout" : 300, 77 "ForceFlushTimeInterval" : -1, 78 "ForceMetadataExtraction" : true, 79 "InterplayCommitTimeInterval" : -1, 80 "MaxSimultaneousMetadataExtractionRequests" : 1, 81 "MetadataExtractionInterval" : 400000, 82 "MetadataExtractionPorts" : [ 83 8731, 84 8732, 85 8733 86 ], 87 "MetadataExtractionTimeout" : "PT5M", 88 "OperationLogsDateLimit" : 30, 89 "OperationLogsSizeLimit" : 200 90 } Listing A.1: Metadata com 3KB 64 Anexo B Protocolo de comunicação com o servidor B.1 Recomendação de itens Obter uma lista de top N recomendações para o utilizador com login feito, para que a interface consiga fazer auto-complete à medida que o utilizado digita. B.1.1 URL do pedido (GET) 1http://localhost/recommendations B.1.2 Formato do pedido Campos Tipo Opcional Definição id Integer / String Não O ID do utilizador no sistema number Integer Sim Número de recomendações (defeito=20) role String Sim Tipo de perfil do utilizador B.1.3 Exemplo de um pedido 65 Protocolo de comunicação com o servidor 1http://localhost/recommendations?id=1&number=20&role=editor B.2 Pesquisa de itens Obter uma lista de resultados que corresponde aos termos da pesquisa do utilizador, ordenados pelos algoritmos de sistemas de recomendação. B.2.1 URL do pedido (GET) 1http://localhost/search B.2.2 Formato do pedido Campos Tipo Opcional Definição query String Não Query construída com a gramática definida na próxima secção id Integer / String Não O ID do utilizador no sistema max Integer Sim Número máximo de itens na resposta (defeito=10) role String Sim Tipo de perfil do utilizador 66 Protocolo de comunicação com o servidor B.3 Sintaxe da gramática O pedido na Listagem B.1 é o mais simples, o utilizador está pesquisando por ’avc’ em todos os campos da base de dados. 1http://localhost/search? 2id=1& 3max=10& 4role=editor& 5query=’search avc in all’ Listing B.1: Pedido simples Para filtrar em mais que um campo, basta adicionar outra frase com a sintaxe: STRING in FIELD. A Listagem B.2 é um exemplo de um utilizador pesquisando por ’avc’ no campo ’codec’, filtrando por assets com um frame rate igual a 60 (para filtrar por mais campos basta adicionar outra frase). 1http://localhost/search? 2id=1& 3max=5& 4role=editor& 5query=’search avc in codec, 6search 60 in framerate’ Listing B.2: Pedido avançado Existe também suporte para filtrar usando um intervalo de valores numéricos. Como exemplo as últimas duas frases da pesquisa da Listagem B.2, filtram por assets com uma duração no intervalo 4-30 minutos. Os operadores disponíveis são >,<,≥,≤e=(este último pode ser omitido pois é o usado por defeito). 1http://localhost/search? 2id=1& 3max=10& 4role=editor& 5query=’search avc in all, 6search >= 240001 in timecode, 7search <= 1800000 in timecode’ Listing B.3: Pedido avançado com intervalo 67 Protocolo de comunicação com o servidor B.4 Guardar resultados clicados Guarda na base de dados o item que o utilizador clicou da lista de resultados retornados. Desta maneira os algoritmos de recomendação conseguem dar resultados mais precisos. B.4.1 URL do pedido (POST) 1http://localhost/chosen B.4.2 Formato do pedido Campos Tipo Opcional Definição id Integer / String Não O ID do utilizador no sistema item Integer / String Não O ID do item (asset) no sistema B.4.3 Exemplo de um pedido 1{ 2id: 1, 3item: "56f27ab037895407d4c1fed0" 4} B.5 Resposta devolvida pelo servidor Formato de resposta que é retornada a todos os pedidos feitos ao servidor. 68 Protocolo de comunicação com o servidor B.5.1 Formato da resposta Campos Tipo Definição took Integer Tempo em milissegundos que o pedido levou data Array Array com a lista de respostas total_results Integer Tipo de perfil do utilizador msg String SUCCESS: nenhum erro (código HTTP 200 OK) INPUT_ERROR: sintaxe errada, campo obrigatório em falta (código HTTP 400 Bad Request) ELASTICSEARCH_ERROR: erro na conexão com o ElasticSearch (código HTTP 503 Service Unavailable) NO_RESULTS: sem resultados (código HTTP 200 OK) B.5.2 Exemplo de uma resposta 1{ 2"took": 9, 3"now": 14604492457, 4"date": "2016-04-12 09:20:45", 5"data": [ 6{ 7"NumAudioChannels": "8", 8"CustomMetadata": { 9"codec": "MPEG2 Video", 10 "aspect_ratio": "16:9", 11 "umid": "06.0a.2b.34.01.01.01.05.01.01.0d.12.13.a1.0f.e2.2c.6b.bc .03.59.65.05.80.cb.f1.d4.ae.52.a9.9d.07" 12 } 13 /*More asset information */ 14 } 15 ], 16 "total_results": 2, 17 "msg": "SUCCESS" 18 } 69 Algoritmos brute force 109 svdBased =value[2] if not isnan(value[2]) else 0 110 itemBased = value[3] if not isnan(value[3]) else 0 111 val = contentBased*weights[0] + userBased*weights[1] + svdBased* weights[2] + itemBased*weights[3] 112 113 if not isnan(val): 114 itemsUnOrdered.append( [key, val] ) 115 116 # Order by value 117 itemsOrdered = sorted(itemsUnOrdered, key=lambda x: (-x[1], x[0])) 118 119 # Calculate nDCG 120 sumNDCG += calculatenDCG(itemsOrdered[0:numRecommendations], relevantItemIDs) 121 countNDCG += 1 122 ###### 123 124 nDCG = sumNDCG / countNDCG 125 126 if nDCG > bestnDCG: 127 bestnDCG = nDCG 128 weights = [w1, w2, w3, w4] 129 130 print(bestnDCG, weights) 131 132 return 133 134 calculate(loadItems("data.csv")) 76 Combining Recommendation Systems with a Dynamic Weighted Technique Pedro Meneses Henriques1, Jo˜ao Mendes-Moreira1,2 1Department of Informatics Engineering, Faculty of Engineering, University of Porto Rua Dr. Roberto Frias, s/n; 4200-465 Porto, Portugal [email protected] 2LIAAD-INESC TEC Campus da FEUP; Rua Dr. Roberto Frias, s/n; 4200-465 Porto, Portugal [email protected] Abstract. Recommender systems represent user preferences for items that the user might be interested to view or purchase. These systems have become extremely common in electronic commerce, providing relevant suggestions and directing users towards those items that best meet their needs and preferences. Different techniques have been analysed including content-based, collaborative and hybrid approaches. The last one is used to improve performance prediction combining different recommender systems using the best features of each method, smoothing problems as cold-start. We evaluate our ensemble method using MovieLens dataset with promising results. Keywords: recommendation systems, content-based filtering, collaborative filtering, combining recommendation systems, ensemble techniques, blending, weighted ensemble, cold start 1 Introduction Recommender systems obtained along the years an important role in commercial websites. Their ability to suggest items to the users intelligently has with any doubt commercial impact being used in many websites. Recommender systems are usually classified as: collaborative filtering, contentbased filtering and hybrid recommender systems. Despite collaborative filtering are considered the most efficient approach they have an important weakness known as cold start. Whenever a new user or item enters in the system, collaborative filtering works badly because it works based on the past profiles of the users and items. Since a new user or item has no past, collaborative filtering is not able to give good recommendations. Differently, content-based filtering has not so good global recommender performance but it does not suffer from the cold start problem. It is possible to use the best of each method using hybrid approaches such as ensemble recommender systems [1]. Ensemble methods use several recommender systems giving a weight to each of them. However, in the age of information, big data, internet of things, the speed data arrives and changes the characteristics of the stored data, it’s not guaranteed that the ensemble weights are always the best through time. In the beginning it is expected that content-based methods can have better performance than collaborative filtering methods. While through time, collaborative filtering are expected to improve. For that reason we propose an ensemble of recommender systems that dynamically adjust the weights of each method over time. Two different experiments are executed, one using a explicit dataset with user ratings within a range from 1 to 5 and a second with an implicit dataset to emulate a model with boolean data, where a entry means the user liked or is interested in the item. In both experiments we proved that there is in fact a difference in the performance of the different algorithms and that our proposed ensemble technique has promising results over static ensemble and the individual pure approaches. We divided the paper into five sections. State of the art, is where we study the techniques that are currently used in recommendation systems. The next section, Methodology, covers the algorithms and techniques used to blend the different recommender systems. In the Datasets section, we start by collecting the raw data and proceed with the necessary steps to get familiar with the data and construct the final datasets used in our experiments. In the last two sections, the results from the two experiments are organized, presented, evaluated and discussed. 2 State of the art Recommendation systems are a subclass of information filtering systems that predict a preference of a user to a particular item. These systems have become extremely common in recent years and are used in a variety of situations. The most popular are recommendation systems of movies, musics, news, books, articles and search results. These systems work by producing a list of recommendations usually with content-based and collaborative algorithms. Content-based use a measure of similarity in order to recommend items similar to the user preferences. Collaboratives build a user profile based on past actions, like bought or seen items, in order to compare with other users profiles, recommending items that the user might be interested. 2.1 User profile Almost all recommendation techniques rely on a user profile where is kept a history of items accessed in the past, which allow us to build a profile with preferences and interests of each user. It is presented on Table 1 an example of an access history [2] of the user with id 10, that has information about the accessed items, i.e. time of access, user id, item id and the transaction group. The transaction is incremental and defined as the set of items accessed at the same time. Table 1. User profile with a history of access Time User Item Group Transaction 23/11/2015 09:32:05 10 46 A T1 23/11/2015 09:32:05 10 19 D T1 30/11/2015 12:04:37 10 30 D T2 2.2 Content-based filtering In the content-based approach [2] we use the user profile referred on section 2.1. The system makes recommendations using a similarity measure between items, comparing items with user preferences. The purpose of this method is to recommend items that belong to a group of items that the user has recently been interest. It is used the last history transactions, each one with a different weight in descending order. Within each transaction the group of items that have more hits are the ones with a greater weight. It is a supervised learning technique, where the user profile is used as training data and items are evaluated as relevant or not [3] according to a similarity measure. It is important to have a good similarity measure so that we can have a good accuracy when using this algorithm. The most common problems with this algorithm are: –Items must have available data related to their features, which is often incomplete or unavailable; –Algorithm is trained with the features of the items, so previsions will always be similar to the ones already rated; –A user has to rate enough items in order the system can infer about user preferences. So when a new user enters the system he has no ratings. 2.3 Collaborative filtering In the collaborative approach [3] we also use the user profile referred on section 2.1, to allow mutual assistance between users. Using the user profile the system can make predictions, comparing that user with similar ones in the neighbourhood. We can use this information to complement user profiles. There are different approaches in collaborative filtering. User-based predicts user interests based on rating information from similar user profiles. Item-based predicts based not on user similarity, but on the similarity between items using user ratings of those items. Latent factor models, such as Singular Value Decomposition (SVD), transforms both users and items to the same latent factor space, thus making them directly comparable. Collaborative filtering does not need to understand items content unlike content-based approaches, because it uses the ratings of similar users. The collaborative algorithms have the ability do deal with sparse data, scale with the increase of users or items and make predictions in a short period of time [4]. The most common problems with these algorithms are: –Cold start: when there are not enough ratings about existing users and items the system is not able to return good recommendations; –Gray sheep: when there are not similar users to a given one in the neighbourhood, that user is not able to receive useful recommendations. 2.4 Hybrid techniques The increase of new recommendation strategies is giving rise to a wide variety of options for the development of recommendation systems. Several studies have compared the performance of a hybrid system with collaboratives and content-based pure approaches, and demonstrated that the former can provide more accurate predictions. This technique can be implemented in many ways, typically combining the two approaches, alleviating common problems of either techniques, improving the overall performance of predictions. One of the events which most contributed to the recommendation systems area was the Netflix Prize. From 2006 to 2009, Netflix sponsored a 1 000 000 $ prize, for the team that create a system 10% more accurate that the one currently used by the company, using a dataset with more than 100 million movie ratings. The contest generated a lot of research for new strategies and algorithms, with one of the winning teams using the technique refereed in section 2.4.1, using an ensemble of 107 different algorithms. Each set of results was combined in order to improve the final result. It was demonstrated that wisdom of crowds is usually better than one single expert. The main approaches to hybrid systems [1] are: – Weighted: The scores of each algorithm are combined using a linear combination or a voting scheme. – Switching: The system switches between algorithms depending on the best for the current situation. – Mixed: Recommendations from different algorithms are presented at the same time using a classification measure. – Feature combination features: Features from different data sources are combined together and given to a single algorithm. – Cascade: It is given a priority to each of the algorithms, with the ones with lower priority breaking ties of the higher ones. – Feature augmentation output: Output from one algorithm is used as input feature of another algorithm. – Meta-level: The model learned by one algorithm is used as input of another. 2.4.1 Feature-Weighted Linear Stacking The Feature-Weighted Linear Stacking (FWLS) technique [5] incorporates model features for improved predictions, while maintaining the speed of linear regression, stability and interoperability. FWLS combines model linear predictions using coefficients, that are themselves linear functions of features. This was a key technique for the team that finished second in the Netflix Prize. This team used two features to combine the algorithms: number of users and number of ratings. The most basic technique is using standard linear stacking with the form b(x) = X i wigi(x) (1) where each model weight wi, is a learned constant value and gi(x), the prediction functions of the learned models. It is a simple way to combine multiple predictions, but lacks the ability to adjust weights according to current model features. On the other hand, FWLS models the blending weights wias linear functions of features wi(x) = X j vi,jfj(x) (2) for learned weights vi,j where fjmaps each datapoint x ∈X to its corresponding meta-feature function fj(x). Under this assumption Equation 1 can be rewritten as b(x) = X i,j vi,jfj(x)gi(x) (3) Many meta-features can be used to combine several algorithms, namely: (1) number of users; (2) number of ratings of each user; (3) total number of item ratings; (4) average number of ratings from users who rated the item; (5) sum of correlations of items that a user already rated with the prediction being made; (6) standard deviation of ratings of each user; (7) standard deviation of item ratings; (8) standard deviation of the dates a item was rated; (9) maximum item correlations with any other. 3 Methodology We used Apache Mahout to model our proposed ensemble technique in addiction to the collaborative and content-based algorithms already presented in this framework. The ensemble technique referred from now on as Ensemble Weighted, follows a similar approach to Feature-Weighted Linear Stacking addressed in section 2.4.1. It is important to say that FWLS applies a weight to each algorithm according to a feature function in a static dataset, where there isn’t a time measure. It lacks the ability to adjust weights over time, when the model features change. On the other hand, the algorithm we propose intends to make predictions in stream, where the weight of a feature depends on the time a rating is added to the model. The goal is to start the system without any user or rating, and over time adjust the weights according to the number of users or ratings using EnsembleW eighted(u, j, m) = X i wi(m)gi(u, j) (4) where the weight value wi(m) for the current model features mis defined as wi(m) = (pi,x if m≤x, x ∈f 0 otherwise (5) where wi(m) is the sum of all algorithms equalizing 1, fis an array ranking the feature numbers with corresponding weights, and pi,x is the weight of feature x∈fby algorithm i. As an example, while there are less than 10 users and 500 ratings, we can give a weight of 0.7 to content-based approaches and 0.3 to collaborative ones. Similarly, when we have 300 users and 50 000 ratings, we can use a weight of 0.8 for the collaborative approaches and 0.2 to content-based ones. To learn the best weights to apply in each algorithm, we developed two brute force algorithms, one for error metrics and another for precision, where we test all possible combinations in order to find the best result for the current experience. Note that although we have only talked about two features, namely the number of users and ratings, we can use a wide range of features. A list of possible features were analysed at the end of section 2.4.1. However the combination of these two have already proven results because they were used by one of the winning teams of Netflix Prize. 4 Datasets To test our framework we used MovieLens 100k dataset from GroupLens. This collection contains information about the name and tags of the movie, as well the corresponding user rating for each movie evaluated. 4.1 Explicit dataset The MovieLens 100k dataset, referred from now on as explicit dataset, contains approximately 100 000 ratings within a range from 1 to 5, by 700 users in 10000 movies with a total of 6100 tags. We will measure at each step the error and coverage of the various algorithms, thus achieving a simulation close to the real world with over 100 000 ratings. We chose 12 main situations (Table 2) to calculate error metrics when a new user is inserted on the system. These situations are representative of the entire dataset, because the evaluation metrics are calculated at the beginning of the system without any rating (Situation 1), after beginning (Situation 2-3), half Table 2. Situations where error metrics were calculated in explicit dataset Situation Ratings Users 1 0 1 2 500 7 3 1500 20 4 3000 32 5 7500 65 6 10500 89 7 20000 157 8 32500 225 9 50000 358 10 62000 437 11 74000 503 12 100000 667 Table 3. Datasets where precision metrics were calculated in implicit dataset Dataset Size Window Ratings Users 1 0.1% 0%-0.1% 106 4 2 0.5% 0%-0.5% 527 15 3 1% 0%-1% 1054 25 4 10% 0%-10% 10534 158 5 50% 0%-50% 52670 392 6 100% 0%-100% 105339 668 (Situation 4-9) and at the end (Situation 10-12). This way we can measure how content-based algorithms relate to collaborative ones, during the various stages of a recommendation system. 4.2 Implicit dataset A second dataset referred from now on as implicit dataset, is a variation of the first dataset. It has been converted to emulate a model with boolean data, where the (user,item) tuple means the user saw, liked or is interested in the movie. The implicit dataset was ordered chronologically and split into 6 datasets (Table 3) with different windows. Each window indicates the interval taken from de main dataset. This way we can understand how each algorithm evolves as they have access to more information. 5 Results Two hypothesis that will be studied over the next experiments are defined H0:there is no difference in the performance of the various recommendation algorithms H1:there is a difference in the performance of the various recommendation algorithms 0 0.5 1.5 3 7.5 10.5 20 32.5 50 62 74 100 0.5 1 1.5 Content-based User SVD Item Static Ensemble Dynamic Ensemble Fig. 1. RMSE values of the different algorithms over time The motivation is to reach the end of this section refuting the null hypothesis H0keeping the alternative hypothesis H1, so that we can validate the results of both experiments. Both hypothesis will be rejected or not with the help of statistical tests. The chosen tests were the Friedman Test complemented with Nemenyi Post-Hoc if the null hypothesis H0is rejected [6]. 5.1 Results: explicit dataset To analyse the performance of the experiment with this dataset, we used the Root Mean Squared Error (RMSE) and the Coverage [7]. One of the main problems in the collaborative algorithms is the cold start problem where it is necessary a large amount of users and ratings so that the algorithm can return good recommendations. As we know in the beginning of recommendation systems, these conditions are not met and one of the most used techniques to mitigate this problem is using content-based algorithms, that do not need ratings from others users because they use the own user preferences to find relevant items based on a similarity measure. On the other hand, when there are many users and ratings, collaborative algorithms tend to have a lower error than the content-based. These are the differences that we intend to find and analyse throughout this experience. Analysing Figures 1 and 2, we can understand how the error and coverage vary over time. Using the brute force algorithm we can discover what are the best weights to use in each of the ensemble methods. In the static method, the weights cannot change over time, so the best value found to use in all situations was a weight of 1 to content-based and 0 to the rest. This means that in this experience, using the static method is exactly the same as using the content-based algorithm. 0 0.5 1.5 3 7.5 10.5 20 32.5 50 62 74 100 0 0.5 1 Content-based User SVD Item Static Ensemble Dynamic Ensemble Fig. 2. Coverage values of the different algorithms over time Table 4. Weights given to each algorithm by Dynamic Ensemble in explicit dataset R/U Content User SVD Item 0 / 1 1.00 0 0 0 500 / 7 0.90 0.05 0 0.05 1500 / 20 1.00 0 0 0 3000 / 32 0.95 0 0 0.05 7500 / 65 0.20 0 0.80 0 10500 / 89 0.90 0.10 0 0 20000 / 157 0 0.20 0.40 0.40 32500 / 225 0 0.10 0.70 0.20 50000 / 358 0 0.15 0.45 0.40 62000 / 437 0 0 0 1.00 74000 / 503 0 0.05 0 0.95 100000 / 667 0.05 0 0.95 0 Average 0.500 0.054 0.275 0.254 In Table 4 we can see in each situation the best weight found by the brute force algorithm on the dynamic method. As expected at the beginning with no other users the only that can return predictions is the content-based. The others cannot, because without neighbours the collaborative similarity measure do not work. After the beginning a small percentage of collaborative approaches are used, becoming the only ones used in the middle and end. It’s interesting to see that a weight of almost 1 is given to the content-based approach until 32 users and 3000 ratings because although the collaboratives algorithms have a lower error, they also have a much lower coverage. In general the ensemble algorithms are those that have better coverage, and most often the ones with the smallest error. Based on a visual inspection of the error distribution in Figure 3 the User and SVD approaches have the largest errors, while Dynamic and Item the lowest. Inspecting the coverage distributions on Figure 4, all pure collaboratives begin with a coverage of 0% and vary over time, while both ensemble and content-based