Metaheurísticas para o problema de agrupamento de dados em grafo (2010)
- Authors:
- Autor USP: NASCIMENTO, MARIÁ CRISTINA VASCONCELOS - ICMC
- Unidade: ICMC
- Sigla do Departamento: SCC
- Subjects: TEORIA DOS GRAFOS; APRENDIZADO COMPUTACIONAL; BIOINFORMÁTICA; ALGORITMOS GENÉTICOS; SISTEMAS HÍBRIDOS; REDES NEURAIS; MINERAÇÃO DE DADOS
- Language: Português
- Abstract: O problema de agrupamento de dados em grafos consiste em encontrar clusters de nós em um dado grafo, ou seja, encontrar subgrafos com alta conectividade. Esse problema pode receber outras nomenclaturas, algumas delas são: problema de particionamento de grafos e problema de detecção de comunidades. Para modelar esse problema, existem diversas formulações matemáticas, cada qual com suas vantagens e desvantagens. A maioria dessas formulações tem como desvantagem a necessidade da definição prévia do número de grupos que se deseja obter. Entretanto, esse tipo de informação não está contida em dados para agrupamento, ou seja, em dados não rotulados. Esse foi um dos motivos da popularização nas últimas décadas da medida conhecida como modularidade, que tem sido maximizada para encontrar partições em grafos. Essa formulação, além de não exigir a definição prévia do número de clusters, se destaca pela qualidade das partições que ela fornece. Nesta tese, metaheurísticas Greedy Randomized Search Procedures para dois modelos existentes para agrupamento em grafos foram propostas: uma para o problema de maximização da modularidade e a outra para o problema de maximização da similaridade intra-cluster. Os resultados obtidos por essas metaheurísticas foram melhores quando comparadas àqueles de outras heurísticas encontradas na literatura. Entretanto, o custo computacional foi alto, principalmente o da metaheurística para o modelo de maximização da modularidade. Com o passar dosanos, estudos revelaram que a formulação que maximiza a modularidade das partições possui algumas limitações. A fim de promover uma alternativa à altura do modelo de maximização da modularidade, esta Tese propõe novas formulações matemáticas de agrupamento em grafos com e sem pesos que visam encontrar partições cujos clusters apresentem alta conectividade. Além disso, as formulações propostas ão capazes de prover partições sem a necessidade de definição prévia do número de clusters. Testes com centenas de grafos com pesos comprovaram a eficiência dos modelos propostos. Comparando as partições provenientes de todos os modelos estudados nesta Tese, foram observados melhores resultados em uma das novas formulações propostas, que encontrou partições bastante satisfatórias, superiores às outras existentes, até mesmo para a de maximização de modularidade. Os resultados apresentaram alta correlação com a classificação real dos dados simulados e reais, sendo esses últimos, em sua maioria, de origem biológica
- Imprenta:
- Publisher place: São Carlos
- Date published: 2010
- Data da defesa: 26.02.2010
-
ABNT
NASCIMENTO, Mariá Cristina Vasconcelos. Metaheurísticas para o problema de agrupamento de dados em grafo. 2010. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2010. Disponível em: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17052010-155334/. Acesso em: 07 out. 2024. -
APA
Nascimento, M. C. V. (2010). Metaheurísticas para o problema de agrupamento de dados em grafo (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17052010-155334/ -
NLM
Nascimento MCV. Metaheurísticas para o problema de agrupamento de dados em grafo [Internet]. 2010 ;[citado 2024 out. 07 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17052010-155334/ -
Vancouver
Nascimento MCV. Metaheurísticas para o problema de agrupamento de dados em grafo [Internet]. 2010 ;[citado 2024 out. 07 ] Available from: http://www.teses.usp.br/teses/disponiveis/55/55134/tde-17052010-155334/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
