Presentada por: J.S. Sánchez
Dirigida por: Filiberto Pla Bañón and F.J. Ferri i Rabasa

Resumen

El contenido de esta Tesis incide directamente sobre un conjunto de técnicas de clasificación y aprendizaje basadas en criterios de vecindad sobre espacios métricos, algunas de las cuales (por ejemplo, la regla de los k-Vecinos más Próximos) han estado consideradas como aproximaciones cuasi-óptimas para un gran número de problemas de estimación, convirtiéndose además en punto de referencia para el desarrollo de otros muchos procedimientos. A lo largo de este trabajo, proponemos un conjunto de conceptos y métodos alternativos a las aproximaciones clásicas basadas en criterios de vecindad, con el objetivo de superar ciertas deficiencias derivadas básicamente de la pérdida de efectividad a medida que la cantidad y la calidad de la información que utilizan disminuye, así como del elevado coste temporal que su aplicación práctica puede suponer. Los esquemas introducidos en cada apartado son empíricamente comparados con las principales técnicas convencionales, en aras de evaluar y valorar las ventajas e inconvenientes del comportamiento exhibido por cada uno de ellos. Como conclusión podemos decir que, en general, los resultados permiten garantizar una superioridad de los nuevos métodos aplicados sobre problemas reales, conservando además el comportamiento óptimo en el caso asintótico, es decir, disponiendo de un infinito número de muestras.



1. MOTIVACIÓN Y OBJETIVOS GENERALES

La calidad de un clasificador puede medirse desde muy diferentes puntos de vista pero, sin embargo, quizás las dos propiedades que mejor puedan definir la superioridad de una cierta regla de clasificación sobre otras son su eficacia y su eficiencia, es decir, porcentaje de aciertos y coste, respectivamente. Teniendo en cuenta esta doble perspectiva, la presente Tesis Doctoral supone un análisis sobre la calidad de algunos métodos de clasificación basados en criterios de vecindad. Tradicionalmente, el interés por este tipo de reglas se ha debido, no sólo a su simplicidad conceptual o a su sencillez de implementación y aplicación, sino también al hecho de mostrar un comportamiento asintóticamente óptimo en términos del error de Bayes (es decir, suponiendo un número ilimitado de muestras). Sin embargo, a pesar de todos los aspectos positivos que de alguna forma se les podría atribuir, estas aproximaciones no paramétricas presentan también algunos inconvenientes prácticos. Por una parte, su aplicación supone un elevado coste temporal, tanto más importante cuanto mayor es el número de muestras disponibles. Por otra parte, si intentamos aliviar esta carga computacional a partir de una reducción del número de muestras, se puede producir un considerable deterioro en su comportamiento.
En consecuencia, podríamos decir que el objetivo general de esta tesis hace referencia a un intento por mejorar la calidad de las reglas de clasificación basadas en criterios de vecindad. En primer lugar, nos centraremos en la efectividad real de estos métodos, es decir, en su comportamiento sobre problemas prácticos. Para ello, estudiaremos el concepto de vecindad que tradicionalmente han venido utilizando la mayor parte de estos esquemas de clasificación y, posteriormente, propondremos unas definiciones alternativas, que globalmente llamaremos vecindad envolvente. A continuación, se formularán diferentes reglas de clasificación a partir de la utilización de aquellos conceptos de vecindad, comprobando experimentalmente que su tasa de aciertos resulta generalmente superior a la de las técnicas basadas en una clásica definición de vecindad. Por último, respecto a aspectos de eficacia, implementaremos un conjunto de procedimientos para la selección de prototipos mediante la aplicación de aquellas nuevas reglas de clasificación, obteniendo igualmente unos resultados mejores que con los principales algoritmos de edición y condensado.
Siguiendo con los aspectos de calidad, en segundo lugar, estudiaremos la eficiencia de los métodos de clasificación basados en criterios de vecindad. De hecho, en la literatura afín a esta disciplina, podemos encontrar numerosas propuestas que tratan de aumentar la velocidad de clasificación. Por una parte, podemos mencionar diferentes algoritmos eficientes para el cálculo del vecino más próximo, entre los que cabe destacar aquellos que utilizan la técnica algorítmica de "ramificación y poda", así como también los esquemas basados en la construcción previa de alguna estructura espacial (fundamentalmente, el diagrama de Voronoi). Por otra parte, diversas propuestas (conocidas, en general, como técnicas de condensado) intentan disminuir la correspondiente carga computacional mediante una reducción controlada del número de muestras, sin que ello suponga un excesivo deterioro de la efectividad de la regla de clasificación. En esta tesis, definiremos algunos procedimientos de condensado a partir del concepto alternativo de vecindad y, por otra parte, propondremos el diseño y la aplicación de una estructura rápida en forma de árbol de decisión que permitirá simular eficientemente el resultado de la regla del vecino más próximo. Por consiguiente, podríamos resumir los objetivos fundamentales de esta Tesis Doctoral en los siguientes cuatro puntos (cada uno de ellos enmarcado en un capítulo de la memoria de Tesis Doctoral):
- Definición de conceptos alternativos de vecindad dentro de un contexto de clasificación: Capítulo 4.
- Análisis, desarrollo y evaluación de clasificadores no paramétricos basados en aquellos criterios de vecindad alternativos: Capítulo 4.
- Diseño, implementación y validación de métodos de aprendizaje (selección de prototipos, en general) para la regla de clasificación del vecino más próximo: Capítulo 5.
- Mejora de la velocidad de clasificación con la regla del vecino más próximo a través de una estructura equivalente y, generalmente, más eficiente: Capítulo 6.
A partir de aquí, este artículo intenta dar una visión global del contenido de cada capítulo de la memoria de tesis, incidiendo en las principales aportaciones y destacando sus principales resultados. Obviamente, debido al escaso espacio disponible para el artículo, no se podrán incluir los detalles de cada apartado sino que, por el contrario, tan sólo se hará una referencia del capítulo en el que aparece el desarrollo teórico y el análisis empírico completos de cada aspecto.

2. CLASIFICACIÓN POR CRITERIOS DE VECINDAD

Entre los clasificadores estadísticos no paramétricos, cabe destacar las aproximaciones basadas en criterios de vecindad, sobre las cuales se ha centrado el presente trabajo. Bajo esta perspectiva, los esquemas de clasificación únicamente exigirán la definición de una cierta medida de disimilitud entre los distintos elementos del espacio de representación, es decir, que éste sea métrico (o pseudo- métrico).
Dentro de las diferentes ventajas que previamente ya hemos comentado para la clasificación basada en criterios de vecindad respecto a otros métodos no paramétricos, la más inmediata hace referencia a su simplicidad conceptual, que podría resumirse de la siguiente manera: la clasificación de un nuevo punto del espacio de representación se puede estimar en función de la clasificación conocida de los puntos dentro de un entorno suficientemente pequeño de aquel punto. Cabe señalar que la métrica del espacio de representación a la que nos referíamos en el párrafo anterior es necesaria, precisamente, para definir aquel "entorno suficientemente pequeño" del punto a clasificar.
En general, cualquier problema de clasificación abordado desde un enfoque basado en criterios de vecindad se podrá caracterizar del siguiente modo: 1) Se dispone de un conjunto de N prototipos (o muestras pre-clasificadas) en un espacio de representación E, llamado conjunto de entrenamiento o diseño, y que escribiremos como {X, ?} = {(x1, ?1), (x2, ?2), ..., (xN, ?N)}, donde ?i hace referencia a la clase verdadera de la muestra xi entre las M posibles clases del problema; 2) Tenemos que clasificar una nueva muestra, x, estadísticamente independiente del conjunto {X, ?}; 3) No hay ninguna otra información adicional acerca de la distribución de los parámetros estadísticos asociados al conjunto de entrenamiento; 4) Existe alguna métrica entre las distintas muestras disponibles definida en el espacio de representación E.
Siguiendo estas premisas, obviamente se debe asumir la absoluta corrección de la técnica empleada para asignar una etiqueta de clase a cada uno de los prototipos del conjunto de entrenamiento, puesto que de ello depende en gran medida la efectividad de cualquier clasificador. No obstante, en la práctica, esta asunción no siempre será totalmente cierta de manera que, en la mayoría de los casos, se requerirá la aplicación de algún proceso previo a la clasificación que, de algún modo, elimine del conjunto de entrenamiento todos los prototipos erróneamente etiquetados (estos procedimientos se conocen, generalmente, como edición del conjunto de entrenamiento y, conjuntamente con los ya mencionados esquemas de condensado, forman las denominadas técnicas de Selección de Prototipos). Si bien son muchas y muy variadas las reglas de clasificación que podrían encuadrarse dentro de los clasificadores basados en criterios de vecindad, en el Capítulo 3 de la memoria de tesis sólo se han mencionado las más interesantes (ya sea por lo que respecta a su desarrollo teórico o por lo que se refiere a sus resultados prácticos). En este artículo, no dedicamos ningún apartado de introducción a dichos clasificadores debido a la escasez del espacio disponible.

3. VECINDAD ENVOLVENTE

Anteriormente, hemos comentado que algunas reglas basadas en el clásico concepto de vecindad (por ejemplo, la regla k-NN) presentan un excelente comportamiento asintótico en cuanto al error de clasificación pero, sin embargo, cuando el número de prototipos disponibles en el conjunto de entrenamiento no es suficientemente grande, los resultados tienden, en general, a sufrir un importante deterioro. Consecuentemente, para determinados problemas reales (es decir, con un número finito de muestras e incluso, en muchas ocasiones, un número relativamente pequeño), la aplicación de estas reglas podría entenderse como una solución poco apropiada debido a los pobres resultados, es decir, a la baja tasa de aciertos en el correspondiente proceso de clasificación. Este problema se acentúa todavía más cuando el número de muestras es pequeño comparado con la dimensionalidad intrínseca del espacio de representación, lo cual responde a una situación práctica bastante habitual.
Esta pérdida en la efectividad asociada a la regla k-NN y, en general, a la mayor parte de los clasificadores basados en criterios de vecindad puede fundamentarse en el hecho de que, bajo las condiciones descritas en el párrafo anterior, la información obtenida a partir del concepto de vecindad utilizado por estos esquemas puede llegar a resultar insuficiente o inadecuada para estimar de forma precisa la clase de las nuevas muestras. En este sentido, puesto que las estimaciones de estos clasificadores se basan exclusivamente en aspectos de proximidad, considerada ésta como la mínima distancia (Euclídea) de una muestra a un determinado número (k) de prototipos, parece claro que ignoran cualquier otro tipo de información que pudiera contener ciertas propiedades relativas a la distribución geométrica o espacial de las muestras.
A partir de estas ideas generales, podríamos considerar que una apropiada definición de vecindad debería satisfacer fundamentalmente dos condiciones o criterios complementarios: a) criterio de distancia: los vecinos deben estar tan próximos a la muestra analizada como sea posible b) criterio de simetría: los vecinos deben estar tan homogéneamente distribuidos alrededor de dicha muestra como sea posible. La regla k-NN sólo tiene en cuenta la primera de estas propiedades, de modo que la muestra en cuestión podría no estar suficientemente rodeada por sus correspondientes vecinos, en el caso de que los prototipos del conjunto de entrenamiento no se encontraran homogéneamente distribuidos en el espacio de representación.
A continuación, definiremos las tres propuestas utilizadas en esta tesis, las cuales nos permiten materializar el concepto de vecindad envolvente que acabamos de introducir.

3.1. Vecindad de Centroide más Próximo

Supongamos un conjunto de N puntos, X = {x1, x2, ..., xN}, y sea p un cierto punto para el que queremos buscar sus k vecinos en X. A partir de la primera definición de vecindad envolvente, que recibe el nombre de Vecindad de Centroide más Próximo (Nearest Centroid Neighbourhood, NCN), el criterio de simetría consiste en exigir que el centroide de los k vecinos se encuentre tan próximo a p como sea posible.
Resultará posible satisfacer ambas condiciones mediante un sencillo procedimiento recursivo en el que el primer vecino del punto p corresponde a su vecino más próximo, mientras que los sucesivos vecinos se tomarán de manera que minimicen la distancia entre p y el centroide de todos los vecinos seleccionados hasta el momento. Así, si calculamos el k-ésimo vecino a partir de los k ? 1 vecinos previamente elegidos por el principio de centroide más próximo, conseguiremos cumplir con los criterios de distancia y simetría. En realidad, la condición de distancia se satisface por el hecho de tomar el vecino más próximo como el punto de partida para el cálculo de los posteriores k-1 vecinos.

3.2. Vecindad de Grafo

El tipo de vecindad que propondremos en esta sección establecerá también aquellas mismas restricciones aunque, en este caso, a partir de una serie de estructuras ampliamente estudiadas en el campo de la Geometría Computacional, y repetidamente aplicadas en otras muchas áreas del Reconocimiento de Formas. En concreto, introduciremos dos definiciones de vecindad envolvente a partir de dos casos de grafos de proximidad: el Grafo de Gabriel (Gabriel Graph, GG) y el Grafo de Vecindad Relativa (Relative Neighbourhood Graph, RNG).
Tanto en el caso del GG como del RNG, dos puntos serán vecinos de grafo si entre ellos se puede definir una cierta zona de influencia vacía, es decir, si existe una cierta región del espacio que no contenga a ningún otro punto en su interior. En el caso del GG, la representación geométrica de esta zona de influencia entre dos vecinos de grafo (denominados vecinos de Gabriel), p y q, corresponde a una hiperesfera diametral, (p,q), de centro el punto medio entre ambos vecinos, y cuyo diámetro es igual a la distancia entre ellos.
De forma análoga, para el caso del RNG, la representación geométrica de la vecindad relativa entre dos puntos, p y q, se fundamenta en la definición de una hiperluna, (p,q), formada por la intersección entre dos hiperesferas, cuyos centros se sitúan sobre ambos vecinos y cuyos radios corresponden a la distancia entre ellos.

4. CLASIFICACIÓN POR CRITERIOS DE VECINDAD ENVOLVENTE

En el Capítulo 4 de la memoria de esta tesis, se presenta un conjunto de nuevas reglas de clasificación no paramétricas basadas en las tres definiciones de vecindad envolvente que acabamos de introducir. El objetivo global de todas ellas se centra, fundamentalmente, en la posibilidad de estimar la clase de una nueva muestra, teniendo en cuenta no sólo los aspectos de proximidad (condición de distancia) propios de los clásicos clasificadores basados en criterios de vecindad, sino también aquellas propiedades relacionadas con la distribución espacial de los prototipos (condición de simetría). A partir de esta doble información, se pretende obtener un modelo de clasificación eficaz, fundamentalmente, para los ya mencionados problemas caracterizados por disponer de un reducido número de prototipos respecto a la elevada dimensionalidad intrínseca del espacio de representación.
Los clasificadores que proponemos se basan en la idea general de estimar la clase de una muestra a partir de la votación de un determinado número de vecinos, pero utilizando para ello una métrica que permita analizar la distribución de estos prototipos alrededor de la muestra. Para conseguir este objetivo, las diferentes alternativas consistirán en la utilización de los conceptos de NCN, vecindad de Gabriel y vecindad relativa durante el proceso de clasificación, dando lugar a sendas reglas de decisión basadas en criterios de vecindad envolvente, y que denominamos regla k-NCN, regla GN y regla RN, respectivamente. En cuanto a la talla de las correspondientes vecindades, cabe decir que para la regla k-NCN se encuentra fijada por un cierto parámetro k (de igual manera que ocurre en la regla k-NN), mientras que en las otras dos propuestas, este tamaño de la vecindad viene determinada por las propias definiciones de grafos.
Si bien estas reglas pretenden, básicamente, ser una solución para problemas de talla finita, debemos destacar también el hecho de que el comportamiento asintótico de estos esquemas envolventes puede asimilarse al de la regla k-NN puesto que, en este caso, ambos modelos de vecindad tienden a ser idénticos. Teniendo en cuenta los resultados de convergencia obtenidos para el análisis asintótico de la regla k-NN, resulta trivial comprobar que el k-ésimo vecino envolvente de un punto x también converge a dicho punto con probabilidad 1. De igual modo, por grande que sea el valor de la talla de los k vecinos envolventes, éstos convergerán al punto x si se cumple que N tiende a infinito y k/N tiende a 0.
Los principales aspectos positivos de estas reglas de clasificación envolventes se pueden resumir en dos propiedades básicas. Por una parte, el vecino más próximo siempre formará parte de la vecindad envolvente (bajo la forma de cualquiera de los conceptos introducidos), lo cual permitirá fijar la estimación de la clase de una muestra sobre una región suficientemente próxima a ella. En segundo lugar, pese a que el espacio que abarca la vecindad envolvente será, en general, mayor que el de la vecindad clásica o vecindad en términos de mínima distancia, aquella tenderá a estar distribuido simétricamente alrededor de la muestra. Por último, los resultados de los diversos experimentos presentados en el Capítulo 4 de la tesis nos permiten formular algunas conclusiones de especial relevancia. Así, en primer lugar, se puede observar como la tasas de aciertos de los esquemas de clasificación basados en los diferentes conceptos de vecindad envolvente se sitúan por encima de los resultados de la regla k-NN. Por consiguiente, parece factible afirmar que estas definiciones alternativas permiten efectuar unas estimaciones más precisas y ajustadas que la vecindad por mínima distancia, utilizada por la clásica regla k-NN. No obstante, también cabe decir que, dentro de las nuevas aproximaciones, la estructura del GG no parece constituir la solución más apropiada para emplearla como método de clasificación puesto que, en general, sus resultados son inferiores a las tasas de aciertos obtenidas por el resto de los esquemas. Este aspecto puede explicarse por el hecho de que la talla de la vecindad de Gabriel en la regla GN, como queda reflejado en la Sección 5 del Capítulo 4, resulta mucho más elevada que el valor de la vecindad considerada en cualquier otro modelo de clasificación.

5. SELECCIÓN DE PROTOTIPOS POR VECINDAD ENVOLVENTE

Los métodos de edición y condensado, o globalmente, Selección de Prototipos para la regla NN constituyen dos técnicas complementarias y fuertemente relacionadas que, de forma genérica, intentan obtener un conjunto reducido de prototipos sin que existan solapamientos entre regiones de clases distintas. En consecuencia, la finalidad de estos procedimientos parece evidente: aumentar la tasa de aciertos resultante del proceso de clasificación y, al mismo tiempo, simplificar la carga computacional asociada a la regla de decisión NN. Obviamente, para poder reducir la talla del conjunto de entrenamiento de una manera correcta y eficaz, deberemos "limpiar" previamente el correspondiente conjunto de entrenamiento, en el sentido de descartar aquellos puntos que pudieran inducir a error en la posterior aplicación de algún procedimiento de condensado, es decir, aquellos prototipos cuya probabilidad de pertenencia a su clase se vea superada por la probabilidad de pertenencia a otra clase distinta. En resumen, lo que se persigue a partir de la edición de los prototipos es la obtención de un conjunto de entrenamiento en el que las clases se encuentren perfectamente separadas y, por tanto, resulten unas fronteras de decisión suficientemente sencillas. De este modo, la posterior aplicación de alguna de las técnicas de condensado dará lugar a un conjunto reducido de prototipos, en el que el resultado de la clasificación podrá aproximarse al resultado de aplicar la regla NN sobre la totalidad del conjunto de entrenamiento.
Los algoritmos de edición propuestos en el Capítulo 5 consisten, básicamente, en aplicar las reglas de clasificación envolventes que acabamos de presentar, utilizando el método de estimación leaving-one-out. En general, las razones que nos impulsaron a seguir este esquema se pueden resumir en el hecho de centrar nuestra atención sobre problemas con pocos prototipos comparado con la dimensionalidad intrínseca del espacio de representación. Teniendo en cuenta este objetivo, puesto que los clasificadores envolventes superaban a la regla k-NN, parece lógico pensar que también en la edición podrán obtener mejores resultados. En cuanto al método de estimación, cabe destacar que utilizaremos el estimador leaving-one-out porque, para los casos que nos preocupan (pocas muestras frente a la dimensionalidad del espacio), los métodos de edición basados en particiones (como, por ejemplo, el conocido algoritmo Multiedit) obtienen unos resultados extremadamente pobres.
En cuanto a las técnicas de condensado, podemos decir que básicamente se proponen dos aproximaciones combinadas de edición-condensado. Por una parte, la aplicación del esquema de edición por NCN conjuntamente con el algoritmo de condensado de Hart y, por otro lado, la utilización del GG y el RNG en las dos etapas de la Selección de Prototipos (es decir, edición y condensado). Fijándonos en esta segunda propuesta, cabe destacar que en el Capítulo 5 de la tesis se presenta además un algoritmo que permite reconstruir la correspondiente estructura de grafo "dañada" después de la edición para, posteriormente, poder aplicar el procedimiento de condensado. Este esquema de actualización del grafo permite obtener un considerable ahorro en tiempo de cálculo, puesto que el tiempo total (construcción + reconstrucción) prácticamente coincidirá con el tiempo necesario para construir la estructura una única vez. Cabe señalar que, a partir de este algoritmo de reconstrucción, el tiempo necesario para la actualización del grafo depende, básicamente, del número de prototipos marcados que hayan resultado eliminados durante la etapa de edición, puesto que éste será el factor que determinará para cuántos pares de nodos se necesitará realizar alguna comprobación nueva (es decir, comprobar si dos puntos son vecinos de grafo o no). Dado que el número de prototipos descartados en la edición siempre resulta bastante pequeño, se deduce que el número de nuevas búsquedas, comparado con el número total de posibles pares de nodos en la nueva estructura, será también bastante reducido.
A la vista de los resultados obtenidos en el Capítulo 5, se puede afirmar que los esquemas de Selección de Prototipos por vecindad envolvente permiten, en general, superar a los métodos tradicionales. No obstante, se ha podido observar que las diferencias entre los distintos algoritmos analizados resultan más o menos significativas en función de las características particulares de cada problema. De entre las distintas propuestas, todo parece indicar que las más apropiadas corresponden a los procedimientos de edición y edición-condensado basados en el concepto de NCN. En primer lugar, podemos destacar el hecho de que estas alternativas siempre consiguen situar su tasa de aciertos entre la de los mejores esquemas y, además, utilizando para ello un muy reducido número de prototipos. Por otra parte, resulta también interesante destacar que la carga computacional asociada a los algoritmos por NCN es inferior al coste requerido por las aproximaciones basadas en grafos de proximidad.
Dentro de los métodos de Selección de Prototipos por vecindad de grafo, podemos hablar de dos aspectos fundamentalmente relevantes. Por una parte, la utilización de la vecindad de Gabriel como técnica de edición no parece erigirse como la solución más idónea, puesto que su tasa de aciertos es, en general, sensiblemente inferior a la del resto de aproximaciones (salvo en el caso del algoritmo Multiedit, cuyos resultados se encuentran incluso por debajo de los obtenidos por los esquemas basados en GG). El segundo hecho a destacar viene determinado por el escaso número de prototipos eliminados mediante el uso de los procedimientos basados en grafos de proximidad (GG o RNG), comparado con el número de prototipos descartados por el resto de técnicas (especialmente, aquellas que utilizan el concepto de NCN). No obstante, a pesar de estos inconvenientes, cabe añadir que la aplicación de estas propuestas puede resultar útil en determinados problemas concretos: en alguno de los problemas tratados y analizados en esta tesis, la tasa de aciertos conseguida mediante la edición por vecindad relativa supera a la de cualquiera de los otros esquemas de edición probados.

6. ÁRBOL DE DECISIÓN EQUIVALENTE A LA REGLA NN

En el Capítulo 6 de la tesis, se hace referencia al problema de la eficiencia de los clasificadores basados en criterios de vecindad y, en particular, de la regla de decisión NN. En este sentido, después de analizar las principales alternativas presentes en la literatura para incrementar la velocidad de clasificación, se introduce un algoritmo que permite diseñar un árbol de decisión equivalente al clasificador NN, mediante el cual podremos estimar la clase de una nueva muestra en función de la región del espacio de representación que ocupa. La solución propuesta en esta tesis corresponde a aquellas aproximaciones que aceleran la clasificación a partir de la utilización de una estructura "rápida", capaz de simular el comportamiento de la regla NN.
Con esta misma filosofía, podemos mencionar, básicamente, dos líneas de trabajo. Por una parte, un procedimiento (algoritmo de Bose) para definir una red neuronal cuya clasificación es análoga al resultado de aplicar directamente la regla NN y se construye a partir de la totalidad de los hiperplanos que definen el diagrama de Voronoi. En segundo lugar, una configuración en forma de árbol de decisión, denominada k-d tree, construida mediante hiperplanos paralelos a los ejes del espacio de características y que, por tanto, sólo pueden clasificar "aproximadamente" igual que la regla NN. En este último caso, las limitaciones parecen claras puesto que, en muchos casos, obtendremos una clasificación distinta a la que resultaría de utilizar un clasificador NN convencional.
Tomando como principal punto de referencia la solución de la red neuronal, la propuesta que aparece en el Capítulo 6 consiste en la utilización de un pequeño subconjunto de los hiperplanos que conforman el diagrama de Voronoi para llegar a un clasificador NN en forma de árbol de decisión. En concreto, los hiperplanos que se consideran en este algoritmo son los correspondientes a las fronteras de Voronoi, es decir, aquellos hiperplanos que se encuentran separando regiones de Voronoi pertenecientes a clases distintas. De este modo, las reglas de decisión de los nodos no terminales corresponderán a las ecuaciones de dichos hiperplanos, mientras que las hojas de la estructura de árbol harán referencia a las distintas clases del problema. Mediante esta técnica, se evita la necesidad de calcular distancias de una muestra a todos los prototipos del conjunto de entrenamiento (esta tarea es, precisamente, la que implica el elevado coste computacional asociado a la regla NN), puesto que la clasificación simplemente consistirá en recorrer la estructura del árbol, comparando dicho punto con la ecuación de los hiperplanos que forman las fronteras de Voronoi, es decir, con las reglas de decisión de cada nodo no terminal, hasta alcanzar una hoja y, finalmente, asignar al punto la clase correspondiente a dicha hoja. Cabe mencionar que, en el caso de los árboles de decisión, el número máximo de comparaciones a realizar será igual a la altura del árbol y, por consiguiente, este número representa una cota superior para el coste de la clasificación de una muestra.
En principio, el hecho de utilizar sólo un reducido número de hiperplanos ya constituye una importante ventaja sobre el mencionado algoritmo de Bose para construir la red neuronal. Además, resulta evidente que un árbol de decisión representa una configuración, en general, bastante más intuitiva y fácil de comprender que una red neuronal. Por último, cabe mencionar la existencia de algoritmos que permiten transformar un árbol de decisión en una red neuronal equivalente de modo que, en cualquier caso, siempre tendremos la posibilidad de llegar a un clasificador en forma de red neuronal. En este caso, comparando la red neuronal que obtendremos a partir del árbol con respecto a la resultante del algoritmo de Bose, podemos añadir que la primera capa de nuestra red neuronal transformada contendrá un menor número de neuronas que la correspondiente a la obtenida mediante la totalidad de los hiperplanos del diagrama de Voronoi, lo cual supone otra interesante ventaja en cuanto a los respectivos tiempos de clasificación.