[pt] RESULTADOS TEÓRICOS E EXPERIMENTAIS EM CLUSTERIZAÇÃO COM MÉTRICAS DE TEORIA DA INFORMAÇÃO

• Ano de defesa: 2020
• Autor(a) principal: LUCAS SAADI MURTINHO
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] ENTROPIA; [pt] GINI; [pt] MEDIDAS DE IMPUREZA; [pt] CLUSTERIZACAO; [pt] TEORIA DA INFORMACAO; [en] ENTROPY; [en] GINI; [en] IMPURITY MEASURES; [en] CLUSTERING; [en] INFORMATION THEORY
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=49518&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=49518&idi=2; http://doi.org/10.17771/PUCRio.acad.49518

[pt] Esta dissertação apresenta resultados teóricos e experimentais relativos ao problema de clusterização de um conjunto de vetores (que possam ser interpretados como distribuições de probabilidade) com o objetivo de minimizar uma medida de impureza da partição resultante. Por meio de uma conexão entre o problema geométrico de k-médias e o problema de clusterização para minimizar a impureza ponderada de Gini da partição, prova-se que este último é NP-completo e APX-difícil. Também analisamos uma família de algoritmos para clusterização com base nas componentes dominantes (as maiores componentes) dos vetores a serem particionados. Mostra-se que, em alguns casos, dois desses algoritmos conseguem obter bons resultados em termos da entropia ponderada da partição resultante, em um tempo bem menor do que os algoritmos considerados como o estado da arte.