La cadena media y su aplicación en reconocimiento de formas

Resumen

En el campo del Reconocimiento de Formas, las técnicas de clasificación basadas en distancia (y más especificamente el clasificador k-NN) necesitan de la obtención de prototipos adecaudos para cada clase. Una de las posibilidades es usar la media de la clase (o el conjunto formado por la media de las diversas subclases que componen la clase) como prototipo de la misma. Cuando se habla de espacios eculídeos (representación vectorial), hallar la media es un problema sencillo, pero no así si usamos la representación por cadenas. En dicho caso, el problema de hallar la cadena media es NP-Duro. Así, se pasan al definir aproximaciones sobre la cadena media para dichos usos. La aproximación clásica es la cadena mediana. Nuevas aproximaciones se proponen siguiendo diversos esquemas: en primer lugar, una aproximación voraz, que no resulta competitiva respecto a la cadena mediana. Posteriormente, se presentan dos aproximaciones basadas en perturbación iterativa que sí resultan competitivas a nivel de clasificación con respecto a la cadena mediana, a costa de un mayor coste computacional. Posteriormente, se tratan diversos aspectos interesantes sobre este tema. Se da una definición alterantiva de cadena media (que no otorga diferencias significativas con respecto a la definición clásica). Se introducen técnicas específicas de reducción de coste computacional en los algoritmos de perturbación iterativa (a costa de una cierta degradación en la calidad de los prototipos). Se realiza también el cálculo exacto de la cadena media mediante Ramificación y Poda, revelando los resultados. La buena calidad de las aproximaciones propuestas respecto a la solución exacta. Seguidamente, se aplican las aproximaciones a la realización de agrupamientos en las clases, mostrando un mejor comportamiento de las nuevas propuestas respecto al método usado habitualmente (k-medianas). Se hace una aplicación de las aproximaciones propues