Processamento de Dados Massivos/Projeto e implementação de aplicações Big Data/Entropia de Shannon em redes de conteúdo categorizado

Descrição da Aplicação

Entropia de Shannon é uma medida de imprevisibilidade em uma variável aleatória , que quantifica o valor esperado da informação contida na mensagem. Esta métrica, basicamente nos diz o quão previsível é o conteúdo avaliado. Valores próximos de 0 indicam grande previsibilidade enquanto o contrário sugere um comportamento mais aleatório. Extrapolamos este conceito, no intuito de quantificar o quão especialista ou generalista são usuários de uma rede na qual o conteúdo gerado por eles é pre-categorizado. A aplicação aqui proposta foi utilizada para analisar usuários da rede social online Pinterest, uma rede baseada em compartilhamento de videos e imagens pre-categorizados em 33 categorias. Vale ressaltar que o algoritmo proposta é generalizado para qualquer rede de conteúdo categorizado.

Denominação

Entropia de Shannon.

Contexto

Análise de comportamento de usuários é uma área bastante explorada e complexa, existem diversos estudos na literatura focados nas mais diversas redes sociais e serviços. Nossa contribuição para este campo da ciência foi o de propor um algoritmo voltada para analise de especificidade/generalidade do conteúdo pre-categorizado gerado por usuários de uma rede. No intuito de demostrar uma aplicação para o sistema, analisamos 683.273 usuários da rede Pinterest e seus 229.661.143 items categorizados em 33 diferentes categorias.

Algoritmo

Entropia de Shannon é definida por:

onde N é o número de categorias utilizadas pelo usuário e Pi é a probabilidade geral dos items serem da categoria N. De maneira geral, quanto mais próximo H for de 0, mais previsível o conteúdo do usuário é, portanto mais especialista em determinadas categorias.

Exemplo: Pinterest

Os usuários da rede possuem albums categorizados em 33 categorias pre-definidas. Esses albums por sua vez, contem fotos ou videos de interesse do usuário. Em essência a estrutura de conteúdo dentro da rede se assemelha ao seguinte:

Portanto o usuário mais generalista possível, seria aquele que coleciona o mesmo número de items para todas as 33 categorias. Desta forma sua entropia seria definida por:

$H=-\sum _{i=0}^{33}{\frac {1}{33}}\log \left({\frac {1}{33}}\right)=1.52$

Enquanto o mais especialista seria aquele que gera conteúdo apenas para uma única categoria:

$H=-\log(1)=0$

Requisitos

• Escalabilidade: Escalabilidade é necessária devida a quantidade de items a serem processados, em nosso exemplo a média de items por usuário foi de 336 items.
• Armazenamento: A aplicação não demanda muito armazenamento em memória principal, devido ao calculo ser individual por usuário e os dados necessários serem pre-processados. Portanto apenas os suas respecitivas informações devem ser carregadas. Entretanto, devido ao volume do conteúdo gerado, é necessário uma quantidade significativa de espaço em disco, outra limitação é a natureza da coleta dos dados. Eles foram coletados utilizando http-requests que retornava 50 items por vez. Desta maneira, se o usuário possui muitos albums e muitos items, seu número de arquivos relacionados será bastante elevado. Na prática, a consequência disto é que muitas vezes o limit de INodes do HD foi estourado, forçando-nos a dividir o conteudo do usuário em HDs/Maquinas diferentes. Quanto ao resultado do algoritmo, sua demanda de espaço é pequena, pois é necessário apenas os IDs dos vértices e seus respectivos valores finais.

Projeto

Oportunidades de paralelização

Como o calculo de entropia é individual para cada usuário, e seu calculo depende somente da natureza da distribuição do seu conteúdo, uma primeira paralelização é evidente: cada map ser responsável pelo calculo de um usuário. Porem há uma massiva quantidade de conteúdo para cada usuário, por isso decidiu-se realizar duas paralelizações na forma de dois procedimentos map-reduce. O primeiro será responsavel pelo pre-processamento dos dados necessários para o calculo da entropia: cada map sera responsável pela identificação dos items de um album específico e o reduce fará a sumarização desses dados em um vetor de tamanho N, onde é N é o número de categorias existentes. O segundo map receberá este vetor e ira calcular o Pi (probabilidade) de cada categoria para este usuário e o reduce simplemente utilizará este dado para o calculo de H(x), mostrado da Seção Algoritmo.

Padrões de acesso aos dados

Como dito antes, por limitações de armazenamento é possível que conteúdo de um usuário esteja distribuido em maquinas/HDs diferentes. Portanto é preciso, durante o primeiro map-reduce que as maquinas recebem os dados por completo do usuário, gerando assim um alto trafego de comunicação na rede. Porem uma vez feito isso, todas as informações necessárias para o segundo map-reduce já estarão disponíveis em memória e portanto mensagens adicionais não precisarão ser feitas.

Linha do tempo integrada

Toda a aplicação se resume a dois paradigmas de map-reduce. Portanto, obviamente o primeiro deve terminar por completo antes de começar o próximo. Porem dentro de um mesmo map-reduce, como há sempre várias threads para processar as informações de um usuário, elas não precisam esperar que acabe todo o processo de um usuário para começar a pegar informações do outro. Pois a sincronia nesse nivel é feita pelo reduce.

Desenvolvimento

Estratégias de paralelização

Como explicado anteriormente, o calculo da entropia foi dividido em dois procedimentos map-reduce. Extrapolando esta ideia para a rede especifica do Pinterest, temos:

O primeiro map-reduce, tem como entrada um vetor contendo o identificador do usuário e os albums associados a ele. O map pega cada album e cria duas rows, uma associando a categoria dele com o número de items e outra (sum) dedicada a ser agregada pelo reduce, isto é feito pois para o calculo da entropia é necessario calcula a probabilidade geral da categoria e para calcular isso é necessário saber o somatório dos items que o usuário possui e os item associados a cada categoria. Este primeiro Map pode ser definido por:

Na fase de reduce, o resultado do Map é agregado em um vetor de forma que cada row contenha a identificação da categoria, o número de items associados a ela e o número total de items do usuário. Basicamente, a ideia é que todas as informações necessárias para calcular a probabilidade de categoria para cada usuário estejam disponíveis. Este reduce pode ser representado por:

O segundo map-reduce, recebe como entrada a saída do primeiro reduce. Primeiramente calcula a Probabilidade Pi (N Photos / "Sum") de cada categoria e realiza a multiplicação Pi * log(Pi).

Desta maneira, o trabalho do reduce se resume em agregar todos os P(i) em modulo e dividir pelo número de categorias utilizadas pelo usuário, neste caso o número de rows associadas a ele.

Estrategias de Armazenamento

Ao terminar uma iteração os dados são salvos no sistema de arquivos virtual distribuído do Hadoop (HDFS) para serem lidos no início da próxima iteração. Esse sistema de arquivos é abstraído para o programador.

Estratégias de comunicação

A cada iteração do map-reduce, o sistema é responsável por sincronizar e transportars os dados, portanto a grande maioria de mensagens trocar é na realidade abstraída do programador. Apenas um cuidado maior é tomado na hora da transição entre os dois map-reduces implementados, pois o primeiro deve acabar antes do segundo começar.

Implementação

Plataformas e ferramentas

Utilizamos um ambiente composto por 5 servidores, sendo 3 deles com 16 cores intel(R) Xeon(R) E5620 @ 2.40GHz, 32gb de memória ram e 2 HDs Sata de 3 tera. Os outros dois servidores possuem a mesma confguração, porem com 8 cores ao invés de 16 e 24 gb de ram. O ambiente foi montado utilizando Hadoop com o sistema de arquivos distribuido HDFS (Hadoop Distributed File System). O sistema operacional de todos os servidores é o Ubuntu 12.04.

Resultados

A seguir, mostramos o resultado da entropia de categoria dividido por gêneros. É possível perceber que mulheres tendem a ser mais generalistas que homens. De forma semelhante, podemos usar a mesma métrica e metodologia para entender a origem dos conteúdos na internet (eg, uma figura do www.deviantart.com). Usa-se a mesma equação da Entropia de Shannon, substituindo $n$ pelo número de domínios diferentes usado pelo usuário $u$ e $p_{i}$ pela probabilidade de um pin ser daquele domínio específico, de forma a calcular a sua Entropia de Domínimo. Os resultados a seguir revelam, de novo, que mulheres são mais generalistas que homens na rede.

Entropia de Shannon para categorias e domínio de origens dos conteúdos por usuário, dividido por gênero