Título
[pt] RESULTADOS TEÓRICOS E EXPERIMENTAIS EM CLUSTERIZAÇÃO COM MÉTRICAS DE TEORIA DA INFORMAÇÃO
Título
[en] THEORETICAL AND EXPERIMENTAL RESULTS IN INFORMATION-THEORETIC CLUSTERING
Autor
[pt] LUCAS SAADI MURTINHO
Vocabulário
[pt] ENTROPIA
Vocabulário
[pt] GINI
Vocabulário
[pt] MEDIDAS DE IMPUREZA
Vocabulário
[pt] CLUSTERIZACAO
Vocabulário
[pt] TEORIA DA INFORMACAO
Vocabulário
[en] ENTROPY
Vocabulário
[en] GINI
Vocabulário
[en] IMPURITY MEASURES
Vocabulário
[en] CLUSTERING
Vocabulário
[en] INFORMATION THEORY
Resumo
[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.
Resumo
[en] We present theoretical and experimental results related to the problem
of clustering a set of vectors (which can be interpreted as probability
distributions) with the goal of minimizing a weighted impurity measure
of the resulting partition. The problem of clustering while minimizing the
weighted Gini impurity of the partition is shown to be NP-complete and
APX-hard, via a connection with the geometrical k-means problem. We
also analyze a family of algorithms for information-theoretic clustering that
rely on the dominant (largest) component of the vectors to be clustered.
These algorithms are shown to be very fast compared to the state of the art,
while able to achieve comparable results in terms of the resulting partition s
weighted entropy.
Orientador(es)
EDUARDO SANY LABER
Banca
MARCO SERPA MOLINARO
Banca
EDUARDO SANY LABER
Banca
THIBAUT VICTOR GASTON VIDAL
Catalogação
2020-09-21
Apresentação
2020-04-07
Tipo
[pt] TEXTO
Formato
application/pdf
Idioma(s)
INGLÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=49518@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=49518@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.49518
Arquivos do conteúdo
NA ÍNTEGRA PDF