Saturday, October 09, 2004 

The Similarity Metric : Compression as a means to parameter free data mining

Dada uma colecção de genomas, será possivel derivar a sua evolução histórica? E considerando-se antes uma colecção de linguagens? Ou uma colecção de partituras de musica? Mais genéricamente, dada uma colecção de sequências, será possivel agrupa-las concenientemente? Existirá alguma medida independente da aplicação que sirva para todos estes exemplos?

Resultados recentes em bioinformática e teoria da conputação parecem indicar que sim. Estes são motivados em observações na teoria da complexidade de Kolmogorov mas, de uma forma prática, podem ser sistemas simples podem ser concretizados em poucas linhas de código usando um compressor de dados off-the-shelf.

De uma forma sucinta, estes trabalhos assentam em duas grandes ideias:

Ming Li: A distância entre duas strings x e y pode ser definida como K(x|y) + K(y|x) ] / K(x,y) onde K(x|y) é a complexidade de Kolmogorov de x, dado y como informação auxiliar.

Keogh et al: A distância entre duas strings é C(xy)/[ C(x) + C(y) ] onde C(x) é o comprimento da string x comprimida.

Ficam os links para dois artigos bem interessantes:

Towards Parameter-Free Data Mining
The Similarity Metric

About me

www.flickr.com
This is a Flickr badge showing public photos from Bruno Martins. Make your own badge here.

Listening to


 All the Web
Me at BookCrossing
Campos Magneticos

Last posts

Friendly Blogs

Powered by Blogger, Flickr
and del.icio.us