Contribuciones al estudio del problema de la clasificación mediante grafos piramidales

Abstract

En esta memoria se ha desarrollado una metodología para abordar problemas relativos a la clasificación y de un conjunto de objetos o individuos de una determinada población, mediante unas estructuras llamadas "Pirámides", introducidas por E. Diday en 1984, y que pretenden ser una generalización del concepto de Jerarquía, en el sentido de permitir la existencia no de grupos disjuntos o encajados, sino también de grupos solapados, y por tanto permitir clasificaciones en las que los grupos en que queda dividida la población a un determinado nivel, no tengan que ser forzosamente particiones de la misma, como pasa con las clasificaciones inducidas por las Jerarquías, sino que puedan ser recubrimientos. Este tipo de clasificaciones permite pues que un determinado individuo pueda pertenecer a dos grupos de una misma clasificación y por tanto, en la realidad, pueda ser caracterizado por las propiedades de los distintos grupos a los que pertenezca y no por las de un único grupo como en el caso jerárquico, con lo cual este nuevo modelo de clasificación y representación de datos se adaptará a la realidad que aquel. <br/><br/>En primer lugar se ha situado este nuevo modelo de representación en el marco del Análisis Multivariante y se han presentado algunos conceptos y resultados ya conocidos, pero imprescindibles para el desarrollo del tema: Caracterización de las matrices asociadas a las disimilaridades piramidales, relación con los preordenes compatibles, etc. Se recuerda que toda disimilaridad ultramétrica es también piramidal y que, en consecuencia, toda Jerarquía Total Indexada es una Pirámide Indexada, con lo cual podemos considerar a los modelos piramidales como una generalización de los modelos jerárquicos.<br/> <br/>Se ha desarrollado también una nueva formalización de las bases sobre las que se amparan los modelos de representación y clasificación. En este sentido se ha precisado la axiomática y se han dado nuevos teoremas de Existencia y Unicidad de la pirámide inducida por una disimilaridad piramidal y recíprocamente, de la disimilaridad piramidal inducida por una pirámide.<br/><br/>Una vez establecidos los resultados teóricos mencionados, se ha profundizado en otros aspectos teóricos conducentes a hacer que los métodos piramidales puedan llegar a ser útiles en la realización de trabajos prácticos como lo han sido los modelos jerárquicos clásicos.<br/><br/>En este sentido se ha diseñado un algoritmo de clasificación piramidal, inspirado en el descrito por el propio Diday, convenientemente modificado, con el fin de obtener una pirámide indexada lo más sencilla posible desde el punto de de la representación visual.<br/><br/>Se han caracterizado los grupos sobrantes en una pirámide indexada y se ha demostrado que son los únicos que pueden ser eliminados de una pirámide sin que ello suponga pérdida de información sobre la clasificación. Se ha definido un índice de agregación adecuado a los modelos de representación piramidal y se ha demostrado que el algoritmo de clasificación piramidal descrito, utilizando un tal índice de agregación, produce siempre una pirámide indexada en sentido estricto, sin inversiones, sin cruzamientos y sin grupos sobrantes.<br/><br/>Finalmente se ha efectuado una programación informática del algoritmo en Turbo Prolog. El programa, llamado PIR. PRO, a partir de una matriz de disimilaridad dada sobre los individuos de la población, efectúa una clasificación piramidal de la misma por los métodos del Mínimo, del Máximo y del UPGMA, obteniéndose como resultado una de las pirámides indexadas correspondientes, la disimilaridad piramidal asociada, el grafo piramidal y como coeficientes de adecuación entre la disimilaridad inicial y la piramidal obtenida, el coeficiente de correlación cofenética (rho) y el coeficiente gamma de Goodman-Kurskal.<br/><br/>Debido a las restricciones impuestas en el algoritmo, se establece que el algoritmo piramidal del mínimo produce siempre la jerarquía del mínimo, que como es sabido, es única.<br/><br/>Un sencillo experimento de simulación nos confirma la mejora que suponen las representaciones piramidales frente a las ultramétricas, en el sentido de ser próxima la realidad.<br/><br/>En problemas reales de clasificación, una vez obtenida la pirámide es necesario evaluar el nivel de adecuación de la estructura piramidal obtenida, a la estructura inicial de los datos. Para ello disponemos de numerosos coeficientes de adecuación, en nuestro caso hemos considerado el coeficiente de correlación cofenética y el de Goodman-Kurskal. A pesar de disponer de estos parámetros, en un caso concreto, es difícil valorar hasta qué punto sus valores realmente significativos. Así pues, seria conveniente encontrar algún criterio que nos permitiese evaluar el nivel de significación de dichos parámetros. En este sentido hemos intentado una validación estadística de los métodos piramidales del mínimo y del máximo así como la obtención de algún criterio evaluar la potencia-eficiencia de los mismos.<br/><br/>Debido al desconocimiento de las distribuciones de los estadísticos utilizados (gamma y rho), se han tratado cuestiones inferenciales un punto de vista empírico. Mediante algunas pruebas de simulación por métodos de Monte Carlo se ha tabulado, a partir de la distribución muestral del estadístico gamma, un test de significación de la bondad de ajuste de una representación piramidal por los métodos del mínimo y del máximo. Asimismo se ha establecido que, en general, el método piramidal del máximo recupera mejor una posible estructura piramidal subyacente en la población a clasificar que el método del mínimo, a menos que pueda preverse que la estructura de la población inicial se asemeje a una jerarquía encadenada.

<I>In this memory it is developed a methodology to tackle problems about the classifications and representations population's members through structures called "Pyramids". Pyramidal trees, introduced by E. Diday, are a logical generalization of ultrametric trees. They are less restrictive structures where recovering replaces the concept of partition, obtaining a representation which bears information is closer to the dissimilarities. <br/><br/>A new formalization of mathematics bases of the pyramidal models is developed. In this sense, the axiomatic has fixed and new theorems of existence and uniqueness of the pyramid induced from pyramidal dissimilarity, they are considered, and mutually. <br/><br/>An algorithm of pyramidal classification is designed in order to obtain an easiest pyramid. The spare groups in an indexed pyramid are characterized. A suitable criterion to the pyramidal models is definited to calculate the distance between groups. From mentioned algorithm and using this criterion indexed pyramid in strict sense, without reversals, crossings and spare groups. Moreover, a computer programming of the algorithm is developed in Turbo Prolog.<br/><br/>In applied problems is necessary to measure the fitting between the pyramidal tree from some algorithm and the initial structure. Using some simulation techniques by means of Monte Carlo methods, sample distribution of is obtained, to tabulate a goodness-of-fit test of the pyramidal representation using the minimum method and the maximum method. Finally, we have studied the efficiency of the maximum method and the minimum method through other simulation tests. </i>