TP___Redes_Complexas

Prévia do material em texto

Análise de Algoritmos de Detecção de Comunidades
para Agrupamento de Pokémons
Arthur Gabriel
DCOMP, Universidade Federal de São João del-Rei, Brasil
arthurgabrielbd@gmail.com
Resumo
Este trabalho apresenta uma análise de uma método
de agrupamento em comunidades aplicados ao pro-
blema de Pokémons com base em seu tipo. A ideia
é utilizar como base de dados a informação oficial
dos 718 Pokémons existentes para teste dos algorit-
mos. O objetivo é observar e analisar as vantagens
e desvantagens da aplicação de cada técnica, além
do comportamento da rede com a variação de parâ-
metros.
1 Introdução
A necessidade de análise de um conjunto de dados onde a
classificação de cada um de seus elementos não é conhecida
é um problema bastante comum. A tarefa de associar ob-
jetos em grupos (clusters) é realizada pelo ser humano com
relativa naturalidade. Faz parte do cotidiano humano agrupar
objetos como, por exemplo, animais, filmes, músicas pessoas
e lugares, o que é feito através da observação de certas carac-
terísticas destes objetos.
Pode-se então separar os objetos em classes ou grupos
(clusters), tal que objetos dentro de um mesmo grupo são
muito similares, enquanto objetos entre grupos distintos são
muito dissimilares. As similaridades entre os objetos são ava-
liadas com base nos atributos que os descrevem. O agrupa-
mento de dados, comumente chamado na literatura de cluste-
rização, pode ser definido como o processo de agrupar objetos
em classes.
O objetivo deste trabalho é a aplicação de algoritmos em
uma rede de Pokémons a fim de agrupá-los de acordo com a
similaridade entre eles, formando no fim comunidades.
2 Motivação
O tema foi escolhido por ser atrativo ao autor, neste caso tra-
balhar analisando Pokémons é bem divertido.
Podemos fazer uma ponte entre o tema discutido com as-
suntos da Biologia. Como o objetivo é agrupar diferentes es-
pécies em comunidades de acordo com a similaridade entre
elas, podemos então, comparar com problemas reais da Bi-
ologia como estudos sobre o comportamento de espécies de
animais em determinados ecossistemas, ou encontrar novos
agrupamentos de espécies de micro-organismos por meio da
similaridade entre eles.
Apesar do tema apresentar dados criados artificialmente, o
mundo Pokémon, em geral, é bastante semelhante ao nosso
mundo real e várias espécies de pokémons são inspiradas em
animais que realmente existem, portanto seria plausível utili-
zar essa base de dados como uma rede para experimentos.
3 Metodologia Utilizada
Para a realização dos experimentos e análise do grafo foi uti-
lizado a biblioteca em Python3 igraph e pandas para leitura
dos dados da base.
A utilização de uma base de dados composta por muitos
atributos e instâncias é muito bom para adicionar mais infor-
mações ao algoritmo e fazê-lo ter uma experiência mais só-
lida, porém somente adicionar dados sem a análise prévia do
mesmo não implica na melhora do algoritmo. É importante
sempre verificar se existe ganho real em um dado atributo ou
instância. Para isso é feito uma análise da base de dados.
3.1 Análise da Base de Dados
A base de dados utilizada consiste em uma tabela em for-
mato Comma-separated values (CSV) contendo 718 instân-
cias que descrevem cada espécie de Pokémon divididas den-
tre os 18 possíveis tipos e seus respectivos atributos. Todas
as informações foram tiradas de fontes oficiais do universo
Pokémon.
Os atributos utilizados estão relacionados aos dados ofici-
ais divulgados em jogos da franquia Pokémon. Nesta base de
dados foram coletados sete tipos de características:
1. Habitat: Referente ao local onde o Pokémon é encon-
trado. A hipótese é que certos tipos de Pokémons tem
tendência a se localizarem em um ambiente específico
como, por exemplo Pokémons de água são encontrados
em oceanos e lagos.
2. Cor: Referente a cor predominante do Pokémon. A hi-
pótese é que certos tipos terem uma tendência a possuir
a mesma cor como, por exemplo Pokémons de fogo ten-
dem a ser vermelhos.
3. Formato do Corpo: Referente a estrutura corporal do
Pokémon. O fato de certos tipos de Pokémon terem a
mesma estrutura corporal como, por exemplo Pokémons
voadores possuem apenas um par de asas.
4. Resistente a: Referente a resistência de um tipo de Po-
kémon a ataques de outro. Um exemplo é a resistência
do tipo pedra a ataques do tipo elétrico.
5. Vulnerável a: Referente a vulnerabilidade de um tipo
de Pokémon a ataques de outro. Um exemplo é a vulne-
rabilidade do tipo pedra a ataques do tipo água.
6. Forte contra: Referente a alta efetividade de um ataque
de um tipo de Pokémon a outro.
7. Fraco contra: Referente a baixa efetividade de um ata-
que de um tipo de Pokémon a outro.
Para verificar o relacionamento e a correlação entre os atri-
butos foi construído uma matriz de correlação. A figura 1
mostra o resultado obtido.
Figura 1: Matriz de correlação entre os atributos.
A matriz de correlação mostra valores entre -1.0 e 1.0, onde
valores próximos a 1.0 mostram atributos que apresentam a
mesma informação, enquanto valores próximos a -1.0 mos-
tram atributos com informações contrárias. A partir da matriz
é possível concluir que não há atributos fortemente correlaci-
onados, ou seja cada atributo fornece informações diferentes
e contribuem positivamente para as técnicas de aprendizado
gerarem bons resultados.
Como já dito, existem 18 tipos de pokémons diferentes, e
com isso existe uma distribuição diferente entre as quantida-
des de pokémons que possuem cada tipo. Por conta de sim-
plificação, os experimentos utiliza somente os dados do tipo
primário da cada pokémon (tipo 1), que no caso é a caracte-
rística básica mais dominante deles. A imagem 2 mostra essa
distribuição.
3.2 Modelagem da Rede
A rede modelada é um grafo G = (V,A), onde V =
{v1, v2, ..., vn} representa o conjunto de vértices e A =
{(v1, v2), ..., (vx, vy)} representa o conjunto das arestas que
ligam os vértices. Cada vértice do grafo representa uma es-
pécie de Pokémon, e cada aresta representa se há ou não uma
similaridade K entre dois diferentes vértices (espécies). Essa
Figura 2: Distribuição dos pokémons de acordo com o tipo 1 deles.
similaridade K é definida pelo usuário e será melhor expli-
cada nos experimentos. O grafo terá arestas não direcionadas,
já que a similaridade entre dois Pokémons é unilateral.
4 Experimentos
Nesta seção será abordado os experimentos realizados e a res-
pectiva análise dos resultados de cada um. É importante des-
tacar que para simplificar o problema será considerado que
cada Pokémon possui apenas um tipo.
4.1 Experimento 1
Neste experimento será aplicado um teste para agrupamento
dos Pokémons, a fim de gerar comunidades. A ideia principal
deste experimento é aplicar um coeficiente K de similaridade
entre as espécies. Essa similaridade será o valor calculado
pela soma de cada atributo igual na verificação da similari-
dade entre duas espécies (vértices). O valor K representa a
quantidade de características que devem ser iguais para que
haja uma aresta. Para cada atributo igual entre as espécies,
será adicionado irá contar 1 ponto. O pseudo-código abaixo
mostra isso:
Se ((tipo+habitat+cor+bodyStyle+strong+weak+
resistant + vulnerable) > K) então: Adiciona uma aresta
entre os vértices.
Ao gerar a rede inicialmente, ela começará sem arestas de
ligação e a partir do valor de K definido para a execução do
programa, as ligações entre os vértices serão feitas. O valor
de K varia de 0 a 8, e de acordo com essa variação são no-
tados diferentes comportamentos na rede. As figuras 3, 4, 5,
6, 7, 8, 9, 10, e 11 apresentam os resultados obtidos após a
variação de K.
Além disso, para uma melhor visualização do grafo, os vér-
tices foram coloridos de acordo com o tipo de cada Pókemon.
Ficando da seguinte maneira:
bug: orange | fire: red | normal: brown dark: black |
flying: cyan | poison: purple dragon: white | ghost: pur-
ple | psychic: pink electric: yellow | grass: green | rock:
brown fairy: pink | ground: gray | steel: silver fighting:
red | ice: white | water: blue5 Conclusão
De acordo com os resultados obtidos podemos afirmar que
com o aumento do valor K foi possível identificar dife-
rentes comportamentos na rede. Valores bem pequenos de
K = {1, 2}, a rede é extremamente densa em quantidade de
arestas. Já valores intermediários de K = {3, 4, 5, 6}, é pos-
sível ver que a rede formar comunidades de Pokémons com o
mesmo tipo, isso se deve ao fato deles terem em média esses
valores de K como características semelhantes. Com valo-
res grandes de K = {7, 8}, as comunidades são destruídas
sobrando somente mini grupos com espécies extremamente
parecidas (como as evoluções de um mesmo Pokémon).
Os testes foram satisfatórios para valores intermediários de
K, podendo ser observado o agrupamento de espécies de Pó-
kemons de acordo com seu tipo. Talvez para problemas reais,
por serem mais complexos a aplicação deste algoritmo não
gere resultados tão interessantes como os observados. Uma
ideia seria trabalhar melhor na função de similaridade, para
que fique mais complexa. Outra ideia seria pegar um pro-
blema real e simplificá-lo a ponto de se encaixar melhor com
o algoritmo apresentado.
Figura 3: Resultado obtido para K=0.
Figura 4: Resultado obtido para K=1.
Figura 5: Resultado obtido para K=2.
Figura 6: Resultado obtido para K=3.
Figura 7: Resultado obtido para K=4.
Figura 8: Resultado obtido para K=5.
Figura 9: Resultado obtido para K=6.
Figura 10: Resultado obtido para K=7.
Figura 11: Resultado obtido para K=8.
	Introdução
	Motivação
	Metodologia Utilizada
	Análise da Base de Dados
	Modelagem da Rede
	Experimentos
	Experimento 1
	Conclusão