Densidade e bolas fechadas em análise de agrupamentos

-----------------------------------------------------------------------------
Seminário do Grupo de Lógica, Inteligência Artificial
e Métodos Formais - LIAMF
Seminário Registrado na CPG do IME/USP
Página: http://www.ime.usp.br/~liamf/seminarios/index.html
-----------------------------------------------------------------------------

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.

Todos são benvindos

--
Marcelo Finger
Departamento de Ciencia da Computacao
Instituto de Matematica e Estatistica | home page:
Universidade de Sao Paulo | www.ime.usp.br/~mfinger
Rua do Matao, 1010 | Tel: +55 11 3091 6310, 3091 6135
05508-090 Sao Paulo, SP Brazil | Fax: +55 11 3091 6134, 3814 4135