Skip navigation
Use este identificador para citar ou linkar para este item: http://repositorio.unb.br/handle/10482/44803
Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2022_PauloEduardoAlthoff.pdf5,34 MBAdobe PDFVisualizar/Abrir
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorFaleiros, Thiago de Paulo-
dc.contributor.authorAlthof, Paulo Eduardo-
dc.date.accessioned2022-09-13T21:41:17Z-
dc.date.available2022-09-13T21:41:17Z-
dc.date.issued2022-09-13-
dc.date.submitted2022-05-26-
dc.identifier.citationALTHOF, Paulo Eduardo. Efeitos do coarsening na classificação de grafos k-partidos. 2022. xvii, 80 f., il. Dissertação (Mestrado em Informática) — Universidade de Brasília, Brasília, 2022.pt_BR
dc.identifier.urihttps://repositorio.unb.br/handle/10482/44803-
dc.descriptionDissertação (Mestrado em Informática) — Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Brasília, 2022pt_BR
dc.description.abstractCom a quantidade de dados gerados no mundo ultrapassando a capacidade humana de avaliação, métodos de classificação automática de conteúdo se tornam cada vez mais relevantes. Grafos são uma forma de representação genérica de representação de entidades e suas interações, e podem ser aplicados praticamente em todo tipo de problema, principalmente em sua versão heterogênea. Por esse motivo é um dos temas que mais tem crescido no número de pesquisas na área de machine learning. Porém, essa mencionada quantidade de dados, resulta em grafos com elevado número de vértices e arestas, também gerando problemas nas questões de armazenamento e escalabilidade dos algoritmos aplicados a eles. Neste trabalho, é proposta a utilização de técnicas de coarsening, para reduzir o tamanho desses grafos como forma de endereçar estes problemas. Essa abordagem é bem estabelecida nas áreas de visualização e de particionamento de grafos, e já foi provada recentemente válida para problemas de classificação em grafos homogêneos. As questões investigadas neste trabalho dizem respeito aos níveis de economia de armazenamento e tempo de classificação proporcionados pelo coarsening, em comparação com os impactos causados pela redução dos grafos, em métricas de qualidade de classificação (Accuracy, Precision, Recall e F-score). O procedimento proposto foi avaliado em centenas de milhares de grafos, variando o número de vértices de entrada no intervalo de 15 a 100 mil vértices, com diferentes esquemas. Foram investigados os impactos também da quantidade de arestas intra-comunitárias e da esparsidade dos grafos nas citadas métricas. Quanto à economia de recursos, as reduções nos grafos apresentaram resultados expressivos, onde reduções de 20% no número de vértices chegam em economias de armazenamento de mais de 1/3, além de tornar as classificações cerca de duas vezes mais rápidas. Em contraste a isso, quanto à perda na qualidade das classificações, destaca-se como fato positivo a baixa perda apresentada para reduções em torno de 20%, com variações médias de 1.72±0.54%, 0.55 ± 0.17%, 1.78 ± 0.55%, 2.36 ± 0.77%, em relação ao grafo original, para as métricas de Accuracy, Precision, Recall e F-score, respectivamente. Com especial destaque para a perda da métrica de Precision, que, além de níveis médios baixos, apresentou uma relativa estabilidade com a variação dos tamanhos dos grafos, variando menos de 4% na comparação entre grafos de 2 mil e de 100 mil vértices. Esses resultados mostram que o coarsening tem grande potencial para gerar versões reduzidas dos grafos, reduzindo a quantidade de memória necessária para seu armazenamento e o tempo necessário para se classificá-los, sem, no entanto, resultar em perdas expressivas de qualidade.pt_BR
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES).pt_BR
dc.language.isoPortuguêspt_BR
dc.rightsAcesso Abertopt_BR
dc.titleEfeitos do coarsening na classificação de grafos k-partidospt_BR
dc.typeDissertaçãopt_BR
dc.subject.keywordClassificação de vérticespt_BR
dc.subject.keywordContração de redespt_BR
dc.subject.keywordGrafos heterogêneospt_BR
dc.subject.keywordGrafospt_BR
dc.rights.licenseA concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br, www.ibict.br, http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.pt_BR
dc.description.abstract1With the amount of data generated in the world surpassing human capacity of evaluation, automatic content classification methods have become increasingly relevant. Graphs are a generic representation form to represent entities and their interactions and can be applied to practically every kind of problem, mostly in its heterogeneous version. For this reason, it is one of the topics that has grown the most in the machine learning area. However, this mentioned amount of data results in graphs with a high number of vertices and edges, leading to problems in terms of storage and scalability for algorithms applied to them. In this work, the use of coarsening techniques is proposed to reduce the size of these graphs as a way to address these problems. This approach is well established in the areas of graph visualization and partitioning, and has been recently proven valid for classification problems in homogeneous graphs. The research questions investigated in this work concern the levels of storage savings and classification time provided by coarsening, in comparison with the impacts caused by graph reduction, on classification quality metrics (Accuracy, Precision, Recall and F-score). The proposed procedure was evaluated in hundreds of thousands of graphs, varying the number of vertices on the input graphs in the ranges from 15 to 100 thousand vertices, with different schemes. The impacts of the amount of intra-community edges and the sparseness of the graphs on the aforementioned metrics were also investigated. In the issue of resource savings, the reductions in the graphs showed expressive results, where reductions of 20% in the number of vertices imply in storage savings of more than 1/3, in addition to making the classifications about twice as fast. In contrast to this, regarding the loss in the quality of the ratings, stands out as a positive fact the low loss presented for reductions around 20%, with average variations of 1.72 ± 0.54%, 0.55 ± 0.17%, 1.78 ± 0.55%, 2.36 ± 0.77%, relative to the original graph, for the metrics of Accuracy, Precision, Recall and F-score, respectively. With special emphasis on the loss of Precision metric, which, in addition to low average levels, presented relative stability with graph sizes variation, varying less than 4% in the comparison between graphs of 2 thousand and 100 thousand vertices. These results show that coarsening has great potential to generate reduced versions of graphs, reducing memory required for their storage and the time needed to classify them, without resulting in significant quality losses.pt_BR
dc.contributor.emailpealthoff@gmail.compt_BR
dc.description.unidadeInstituto de Ciências Exatas (IE)pt_BR
dc.description.unidadeDepartamento de Ciência da Computação (IE CIC)pt_BR
dc.description.ppgPrograma de Pós-Graduação em Informáticapt_BR
Aparece nas coleções:Teses, dissertações e produtos pós-doutorado

Mostrar registro simples do item Visualizar estatísticas



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.