Título: Densidade e bolas fechadas em análise de agrupamentos
Palestrante:  Carlos Gonzalez

Data:   29/09/2008, 14h30
Local:  Sala 03B, IME-USP

Resumo:

Uma das conceitualizações possíveis em análise de agrupamentos consiste em
selecionar as áreas do espaço de características (feature space) que
apresentam maior densidade. O conceito básico de densidade surge de considerar
a quantidade de pontos que tem uma determinada região do espaço. Seguindo com
esta linha de raciocínio, precisamos determinar, de alguma maneira, a região
que vai ser considerada para calcular a densidade.

Neste sentido, noções topológicas bem conhecidas, como a de bola fechada,
podem nos auxiliar. Mas para isto precisamos analisar o seguinte problema:
dado um conjunto de elementos do espaço de características: como determinar
uma bola fechada mínima ou minimal que inclua este conjunto? Uma vez
solucionado este problema, podemos pensar várias maneiras de aplicar este
contexto metodológico em análise de agrupamentos. Se trabalharmos em análise
de agrupamentos hierárquico acumulativo, podemos determinar que dois
agrupamentos A_{1} e A_{2} serão selecionados para formar um novo agrupamento
se a densidade da menor bola fechada que inclui A_{1} e A_{2} tem a maior
densidade ou uma densidade maximal. Denominamos a este algoritmo ``grande
bola''. Também podemos usar alguma noção de distância para determinar, para
cada par de agrupamentos A_{1} e A_{2} o conjunto E dos elementos de A_{1} e
A_{2} que estão mais próximos, considerando para a seleção de agrupamentos a
densidade da menor menor bola fechada que inclua E. Este algoritmo é
denominado ``bola no meio''.

A principal vantagem (o que na realidade foi a motivação inicial) consiste em
que a generalidade de aplicação destes conceitos permite comparar tipos de
espaços e noções de noções de distância muito diferentes. Neste trabalho,
usamos este enfoque conceitual e os algoritmos mencionados para comparar o
conhecido espaço métrico que usa a noção de distância de Jaccard com os
espaços booleanos, nos quais as distâncias são elementos da mesma álgebra de
Boole usada como espaço de características.

São mostrados alguns resultados experimentais para uma comparação inicial
deste enfoque.