[pt] RESULTADOS TEÓRICOS E EXPERIMENTAIS EM CLUSTERIZAÇÃO COM MÉTRICAS DE TEORIA DA INFORMAÇÃO - LUCAS SAADI MURTINHO (2020)
[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.