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

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa

Descrição da Aplicação[editar | editar código-fonte]

Entropia de Shannon é uma medida de imprevisibilidade em uma variável aleatória [1], 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[editar | editar código-fonte]

Entropia de Shannon.

Contexto[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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:

PinterestConteudo.png

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:

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

Requisitos[editar | editar código-fonte]

  • 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[editar | editar código-fonte]

Oportunidades de paralelização[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Estratégias de paralelização[editar | editar código-fonte]

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

MapReduceCompleto.png

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:

PrimeioMap.png

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:

PrimeiroReduce.png

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).

SegundoMap.png


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.

SegundoReduce.png

Estrategias de Armazenamento[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Plataformas e ferramentas[editar | editar código-fonte]

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[editar | editar código-fonte]

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 pelo número de domínios diferentes usado pelo usuário e 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.

Resultados

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

Referências[editar | editar código-fonte]

  1. Ihara, Shunsuke (1993). Information theory for continuous systems. World Scientific. p. 2. ISBN 978-981-02-0985-8.