Publications

Advanced search

Abstract

Ramón A. Mollineda. Técnicas de Agrupamiento Jerárquico para la Selección de Prototipos y Clasificación basadas en Distancias. Uso en Cadenas Cíclicas.. Universitat Politècnica de València. 2001. Advisor(s): Dr. E. Vidal and Dr. F. Ferri

Los esquemas jerárquicos de análisis de agrupamientos construyen una organización jerárquica de particiones anidadas de muestras del problema original. En cada nivel de agrupamiento (partición) se mezclan aquellos grupos (clusters) que más se asemejen de acuerdo a cierta métrica predefinida. Las métricas usuales sólo consideran información de los dos clusters involucrados, y por ende, pueden ser consideradas como ``absolutas''. Se propone mezclar aquellos dos clusters que optimicen un funcional, en el que la información de semejanza entre los dos clusters seleccionados tienda a ser máxima relativo a la semejanza de ambos con cierta ``vecindad'' de clusters de la partición actual. Los experimentos mostraron que este nuevo esquema relativo construye (generalmente) agrupamientos notablemente mejores que los métodos convencionales, en especial, para determinadas vecindades de clusters. Estos agrupamientos resultaron muy similares, y en algunos casos mejores, que los obtenidos por el algoritmo C-Medias. Las técnicas de agrupamiento jerárquico también fueron aplicadas a problemas supervisados, dando lugar a técnicas de reducción de prototipos (condensado). Estas técnicas persiguen la obtención de conjuntos reducidos de prototipos a partir de conjuntos originales (usualmente grandes) particionados en clases, de forma que los primeros conserven en lo posible el poder discriminante de los segundos con la regla de 1-Vecino más Próximo (1-NN). En situaciones supervisadas, el procedimiento jerárquico agrupa muestras por clase y obtiene para cada grupo (cluster) un prototipo representativo que garantiza la correcta clasificación de sus miembros. El uso de clusters permite diferentes estrategias de mezcla, lo que conduce a una mejor adaptación de los prototipos a las distribuciones subyacentes de los datos. Adicionalmente, este esquema puede ser eficientemente implementado haciendo uso de ciertas propiedades geométricas de los clusters. Los conjuntos condensados resultantes de este método han sido consistentemente mejores (menos prototipos más discriminantes) que los obtenidos por métodos previos de similar estrategia, y de características semejantes a los condensados producidos por dos de los algoritmos de la familia LVQ. La definición conceptual de este esquema de condensado por mezcla jerárquica permite su aplicación a espacios métricos en general. Para estudiar su comportamiento en espacios no vectoriales, se seleccionó el espacio de las cadenas cíclicas. Para la evaluación de la distancia entre estas estructuras fueron introducidas una familia de técnicas aproximadas muy eficientes computacionalmente, en todos los casos inspiradas en el método cuadrático propuesto por Bunke and Bühler (BB). Las técnicas propuestas incorporan restricciones espaciales al funcionamiento de BB, así como mecanismos que permiten obtener alineamientos cíclicos íntegros entre las secuencias operandos. En otros casos, se ha aprovechado la condición de cotas de algunas de estas aproximaciones para introducir medidas ponderadas. Todas las extensiones propuestas a BB obtuvieron aproximaciones notablemente mejores que el algoritmo original manteniendo su coste cuadrático de ejecución. Con respecto a los algoritmos exactos para el cálculo de la distancia cíclica, las técnicas introducidas demotraron ser muy precisas en su estimación de la solución exacta, en tiempos significativamente menores en orden y en magnitud. Por último, se diseñaron experimentos de clasificación con el 1-NN a partir de conjuntos reducidos de cadenas seleccionadas por la técnica de condensado propuesta. Se obtuvieron reglas del 1-NN con un número muy reducido de prototipos (secuencias cíclicas) de referencia, y con medidas (aproximadas) de disimilitud relativamente rápidas de calcular. El error de clasificación sobre los conjuntos de test con medidas aproximadas y con los conjuntos reducidos fue, en general, del mismo orden (ligeramente mayor), que el calculado con los algoritmos exactos de distancia cíclica usando todos los prototipos del conjunto de entrenamiento, pero con una diferencia muy notable de tiempo de cómputo en favor de los primeros.