A stochastic approach to median string computation
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/9689
Registro completo de metadatos
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor | Reconocimiento de Formas e Inteligencia Artificial | en |
dc.contributor.author | Olivares Rodríguez, Cristian | - |
dc.contributor.author | Oncina, Jose | - |
dc.contributor.other | Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos | en |
dc.date.accessioned | 2009-02-19T12:15:14Z | - |
dc.date.available | 2009-02-19T12:15:14Z | - |
dc.date.created | 2008 | - |
dc.date.issued | 2008 | - |
dc.identifier.citation | OLIVARES RODRÍGUEZ, Cristian; ONCINA CARRATALÁ, Jose. "A stochastic approach to median string computation". En: Structural, Syntactic, and Statistical Pattern Recognition : joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008 : proceedings. Berlin : Springer, 2008. (Lecture Notes in Computer Science; 5342/2008). ISBN 978-3-540-89688-3, pp. 431-440 | en |
dc.identifier.isbn | 978-3-540-89688-3 | - |
dc.identifier.issn | 0302-9743 (Print) | - |
dc.identifier.issn | 1611-3349 (Online) | - |
dc.identifier.uri | http://hdl.handle.net/10045/9689 | - |
dc.description.abstract | 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. | en |
dc.description.sponsorship | Spanish CICyT, through project DPI2006-15542-C04-01. The IST Program of the European Community, under the PASCAL Network of Excellence, IST–2002-506778. The program CONSOLIDER INGENIO 2010 (CSD2007-00018). | en |
dc.language | eng | en |
dc.publisher | Springer Berlin / Heidelberg | en |
dc.rights | The original publication is available at www.springerlink.com | en |
dc.subject | Median string | en |
dc.subject | Multistring | en |
dc.subject | Pattern recognition | en |
dc.subject | Stochastic edit distance | en |
dc.subject.other | Lenguajes y Sistemas Informáticos | en |
dc.title | A stochastic approach to median string computation | en |
dc.type | info:eu-repo/semantics/article | en |
dc.peerreviewed | si | en |
dc.identifier.doi | 10.1007/978-3-540-89689-0_47 | - |
dc.relation.publisherversion | http://dx.doi.org/10.1007/978-3-540-89689-0_47 | - |
dc.rights.accessRights | info:eu-repo/semantics/restrictedAccess | - |
dc.relation.projectID | info:eu-repo/grantAgreement/EC/FP7/216886 | - |
Aparece en las colecciones: | INV - GRFIA - Artículos de Revistas Investigaciones financiadas por la UE |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
median.pdf | Versión final (acceso restringido) | 415,96 kB | Adobe PDF | Abrir Solicitar una copia |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.