Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/RVMR-7PVQPU
Type: | Dissertação de Mestrado |
Title: | Uma heuristica para o problema de classificação de classificação de conferências explorando relacionamentos múltiplos e indiretos |
Authors: | Guilherme Henrique Trielli Ferreira |
First Advisor: | Wagner Meira Junior |
First Referee: | Cristina Duarte Murta |
Second Referee: | Gisele Lobo Pappa |
Third Referee: | Marcos Andre Goncalves |
Abstract: | A habilidade de extrair conhecimento usável de grandes massas de dados tornou-se um dos mais importantes desafios para diversas comunidades, sejam elas científicas, industriais ou governamentais. A extração de tal conhecimento requer que os dados estejam representados de uma forma que não somente capture a informação relacional, mas também proporcione uma mineração efetiva e eficiente desses dados e uma capacidade de compreensão do conhecimento resultante. Na maioria dos casos, entretanto, os dados são modelados em grafos que não permitem a representação de relacionamentosmúltiplos. Essa restrição, por sua vez, pode causar uma falha na capacidade de abstração entre os dados e o modelo, fazendo com que informações essenciais da aplicação real sejam completamente negligenciadas. Este trabalho, portanto, versa sobre mineração de dados baseadas em relações, em que, em contraste a técnicas tradicionais, propomos uma heurística inovadora de mineraçãode multigrafos capaz de tratar relacionamentos múltiplos e indiretos nos dados, utilizando esses relacionamentos para identificar grupos correlacionados. Assim, construímos uma base teórica sobre a qual diversas aplicações reais podem ser modeladas, de forma a preservar relações importantes existentes nos dados, que eram ignoradaspor outros modelos. Aplicamos, então, a nossa técnica em um cenário real de redes de co-autoria, buscando agrupar e classificar fóruns científicos com base em afinidades de autoria. Para tal, modelamos os dados dessas redes como uma floresta de multigrafos e, então, osutilizamos para encontrar conjuntos de conferências que estejam interligadas. Caso tais conjuntos possam ser identificados em, pelo menos, um dado número de partes distintas da floresta, os mesmos serão vistos como pertencentes a uma mesma área de conhecimento.Resultados experimentais demonstram que a técnica é efetiva em extrair áreas distintas, mesmo diante de dados esparsos, a despeito do problema ser NP-Completo e o custo computacional da heurística ainda apresentar uma alta variabilidade. |
Abstract: | Extracting usable knowledge from large amounts of data has become one of the main challenges to a variety of fields, such as scientific, industrial or governmental areas. This task requires the data to be represented in a way that not only is the relational information captured, but that it also allows an effective and efficient mining of thesedata and the understanding of the resulting knowledge. In most of the cases, however, the data are modeled as graphs that arent able to represent multiple relations. This restriction may cause a flaw in the process of matching the real data with the model constructed, and, as a consequence, essential information of the real application is lost.Therefore, this work discuss data mining based on relations where, in contrast with traditional techniques, we propose an innovative heuristic of multigraph mining capable of dealing with multiple and indirect relations in the data, using these relations to identify correlated groups. We constructed a theoretical base on which many reallifeapplications can be modeled, so that they preserve important relations that exist in the data and are ignored by other models. We applied our new technique in a real scenario of co-authorship networks, in whichwe intend to group and classify scientific conferences based on authorship affinities. In order to do that, we modeled the data of these networks as multigraph sets, and then we use them to find groups of conferences that are correlated. If these groups can befound in, at least, a certain number of different parts of the multigraph, they will be considered as belonging to the same area. In spite of the fact that the problem we dealt with is NP-Complete and that there is a quite variety in the computational cost of the heuristic, experimental results show that our technique is effective in identifying different areas, even when the data is sparse. |
Subject: | Computação Recuperação de informação |
language: | Português |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/RVMR-7PVQPU |
Issue Date: | 12-Dec-2008 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
guilhermehenriquetrielliferreira.pdf | 834.97 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.