A stochastic approach to median string computation

Cristian Olivares-Rodríguez, Jose Oncina

Resultado de la investigación: Contribución a los tipos de informe/libroContribución a la conferenciarevisión exhaustiva

9 Citas (Scopus)

Resumen

Due to its robustness to outliers, many Pattern Recognition algorithms use the median as a representative of a set of points. A special case arises in Syntactical Pattern Recognition when the points (prototypes) are represented by strings. However, when the edit distance is used, finding the median becomes a NP-Hard problem. Then, either the search is restricted to strings in the data (set-median) or some heuristic approach is applied. In this work we use the (conditional) stochastic edit distance instead of the plain edit distance. It is not yet known if in this case the problem is also NP-Hard so an approximation algorithm is described. The algorithm is based on the extension of the string structure to multistrings (strings of stochastic vectors where each element represents the probability of each symbol) to allow the use of the Expectation Maximization technique. We carry out some experiments over a chromosomes corpus to check the efficiency of the algorithm.

Idioma originalInglés
Título de la publicación alojadaStructural, Syntactic, and Statistical Pattern Recognition - Joint IAPR International Workshop, SSPR and SPR 2008, Proceedings
Páginas431-440
Número de páginas10
DOI
EstadoPublicada - 1 dic 2008
EventoJoint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, SSPR and SPR 2008 - Orlando, FL, Estados Unidos
Duración: 4 dic 20086 dic 2008

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen5342 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

ConferenciaJoint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition, SSPR and SPR 2008
País/TerritorioEstados Unidos
CiudadOrlando, FL
Período4/12/086/12/08

Áreas temáticas de ASJC Scopus

  • Ciencia computacional teórica
  • Informática (todo)

Huella

Profundice en los temas de investigación de 'A stochastic approach to median string computation'. En conjunto forman una huella única.

Citar esto