RESUMEN. Un árbol k-dimensional es un árbol de decisiones en que cada nodo interior (que no es hoja) hace una pregunta —cuyas respuestas deben estar completas: cubrir todas las posibilidades— sobre una de k variables o rasgos o dimensiones, y cuyas hojas tienen resultados o acciones.

Se da un procedimiento mecánico para formar un árbol k-d a partir de una matriz de aprendizaje (MA) cuyos renglones representan objetos que poseen diversos rasgos (sus columnas); una de las columnas nos dice la clase o respuesta o reacción que se espera que el árbol emita cuando se le describe el objeto en cuestión. El procedimiento permite que el árbol emita una respuesta a cualquier objeto con valores "razonables", y no sólo a aquéllos que forman la MA; luego, un árbol k-d es un clasificador supervisado. También se dan criterios de abstención.

Un árbol k-d es isomorfo a un sistema experto, y se esboza el procedimiento constructivo para formarlo a partir de las reglas de conocimiento. Se cubren los casos de variables cuantitativas, cualitativas, difusas. Se dan ejemplos simples. La ventaja es que para formar el árbol se procesan los datos del especialista (la matriz MA), en tanto que la formación del sistema experto requiere entrevistar al especialista, un proceso mucho más lento e intuitivo. Un árbol k-d puede representarse como un programa en "C" y como una función de dispersión («hashing»), que utiliza como llaves los valores de los rasgos. Por esto, su ejecución es rápida.

Palabras clave: árboles de decisión; árbol k-d; clasificador supervisado; sistema experto; matriz de aprendizaje; clasificación; clases; reglas del conocimiento; árbol b; testor; testor típico.

I. INTRODUCCIÓN

Un árbol k-d [7] es un árbol de decisión [6] que sirve para hallar una respuesta o curso de acción, dadas k variables o entradas. Cada nodo suyo hace una pregunta sobre una variable; para k variables, puede haber más de k preguntas antes de emitir una respuesta. Las hojas (nodos finales) no hacen pregunta, sino que "dan la respuesta" o curso a tomar.

Por ejemplo, el algoritmo de búsqueda binaria presente?(v, inf, sup) que nos dice si un valor v está en un arreglo delimitado por los valores inf y sup, puede verse como un árbol 1-d (o sea, uni-dimensional) donde en cada nodo se compara el valor v con valores bajos y altos (inicialmente, con inf y con sup). Para que un árbol de decisión sea del tipo k-d, se exige que cada pregunta considere todos los casos posibles, o sea que las respuestas estén completas (cubiertas). Empero, un árbol k-d no preguntará necesariamente sobre la misma variable en todos los nodos de un cierto nivel. Además, alguna rama puede no hacer una pregunta sobre cierta variable, y ser más corta por ello. Un ejemplo de árbol k-d puede verse en la figura 1. Originalmente, estos árboles se utilizaron como "clasificadores sí o no" al responder a la pregunta: ¿pertenece un objeto dado a cierto conjunto o archivo?

1.1 El árbol k-d se ha usado para hallar rápido cierta información
Tradicionalmente [1], los árboles k-d han sido utilizados para hallar la información asociada a ciertos valores de k variables. Por ejemplo, ¿qué información tenemos para tipo=avión, destino=Habana, fecha=miércoles? La respuesta puede ser: el vuelo Cubana 465. A veces la respuesta es f (no hay, no sé). Hace el papel, aunque no utiliza las técnicas, de un archivo cuya llave es la concatenación de las k variables. Regresaremos a este punto en la §4.3 sobre dispersión al azar.

1.2 Motivación para su uso como clasificadores supervisados
En [9] se explica cómo ver el árbol k-d como tabla de decisiones. Al leerlo, pensé que podría formarse mecánicamente [ver también referencias 10 y 14] a partir de un conjunto de datos "buenos" (la MA) y que podría servir como clasificador supervisado. La oportunidad llegó cuando casi al mismo tiempo, (a) fui expuesto a las técnicas de los testores típicos [11] por José Ruiz Shulcloper y Manuel Lazo [12], y (b) se arrancó el proyecto de clasificar las lecturas de medidores (o de consumidores) de energía eléctrica en normales o anómalos (cuyo pago no corresponde a su clase) [4]. Como muchos de los rasgos son no numéricos (colonia; tipo de negocio; nivel socio-económico), el árbol k-d ofrecía promesas.
El trabajo principal consistió en desarrollar el algoritmo (descrito en 2.2) para generación mecánica del árbol. José Ruiz esbozó un paradigma inicial, en tanto que Aarón Hernández construyó el generador (§2.3.1) del programa en "C" [4] que corresponde a cierto árbol k-d.

1.3 ¿Por qué usarlos en vez de sistemas expertos?

Concluido el generador del programa en "C", noté la facilidad con que generaba árboles de decisión complejos, que hubiesen sido muy tediosos de construir manualmente sin error. ¿Por qué no usarlo para analizar los datos que los especialistas humanos han acumulado a través de sus múltiples casos, diagnósticos, préstamos, etc.? Además de aprender de una gran cantidad de datos (Cf. nota #1 de pie de página), y no de la memoria del especialista, evitaríamos usar un método donde el entrevistador (llamado "ingeniero del conocimiento" [2]) trata de entender las decisiones, valores y casos que el experto le narra, y va lentamente y con procedimientos manuales y de ensayo y error, construyendo la base de conocimientos [12]. La duda: ¿será un árbol k-d "inferior" a un sistema experto? La respuesta: el teorema de la §3.1. Contribuciones principales de este trabajo: (§II) la construcción mecánica de un árbol k-d que es un clasificador; (§III) el descubrimiento que un árbol k-d puede substituir a un sistema experto.
El §IV analiza otros isomorfismos y equivalencias, y contiene conclusiones y sugerencias.

II. EL ÁRBOL K-D COMO CLASIFICADOR SUPERVISADO

En esta sección se construye un árbol k-d que clasifica sin error los datos de la matriz de aprendizaje, y exhibe buen comportamiento frente a objetos "cercanos" a alguno de los de la MA. Si el objeto a clasificar no se ncuentra "cerca" de alguno de los de MA, el árbol k-d se abstiene. Es un clasificador cauteloso.

2.1 Algunas definiciones

2.1.1 Matriz de aprendizaje (MA)

Es una matriz de objetos (sus renglones) cuyos rasgos (sus columnas), variables o dimensiones tienen valores numéricos (edad, salario, años de estudio; números reales en general) o no-numéricos (sexo; profesión; partido político; color; colonia donde vive; universidad donde estudió), pudiendo ser booleanos ó k-valentes (color = verde, amarillo, rojo, azul o café). Una de las columnas de MA nos dice a qué clase pertenece cada renglón u objeto. Por conveniencia, todos los objetos de una clase aparecen juntos (ver tabla 1). Por simplicidad, eliminamos duplicación (renglones con los mismos valores) en la misma clase, y no permitimos que el mismo objeto pertenezca a más de una clase. Es decir, en MA no hay filas duplicadas.

Objeto número Clase Color Altura Peso
 

Objeto número     Clase           Color        Altura          Peso

1                     C1 = militar                         rojo                      alto                         ligero

2                    C1 =                                      rojo                       alto                           pesado

3                    C1 =                                      morado                alto                          pesado

4                    C1 =                                      verde                   mediano                 ligero

5                    C1 =                                      verde                    chaparro               ligero

6                    C2 = médico                       azul                       mediano                 ligero

7                   C2 =                                      rojo                       chaparro                pesado

8                   C2 =                                      amarillo                alto                         ligero

9                   C2 =                                      morado                alto                         ligero

10                 C3 = abogado                     verde                   chaparro                pesado

11                 C3 =                                      azul                       alto                          ligero

12                 C3 =                                      amarillo               chaparro               pesado

2.1.2 Confusión

La confusión inducida por un rasgo (columna) en la MA es el número de pares de objetos que tienen el mismo valor en ese rasgo pero que pertenecen a clases distintas. Por extensión, la confusión inducida por un conjunto de rasgos (por ejemplo{color, altura}) se define similarmente.
Ejemplo: la confusión inducida en la MA de la tabla 1 por el rasgo color es 7, calculada así:

Confusión de los rojos: par (1, 7) + par (2, 7) = 2. Confusión de los morados: (3, 9) = 1. Confusión de los verdes: (4, 10) + (5, 10) = 2. Confusión de los azules: (6, 11) = 1.
Confusión de los amarillos: (8, 12) = 1.

Ejemplo: la confusión inducida por el conjunto de rasgos {altura, peso} en la misma MA es 8, siendo los ocho pares: (1, 8), (1, 9), (1, 11), (4, 6), (7, 10), (7, 12), (8, 11), (9, 11).

2.1.3 Testor típico

Un conjunto de rasgos que no produce confusión se denomina testor. Si el conjunto es mínimo, en el sentido de que cualquier rasgo que le quitemos provoca que el nuevo conjunto ya produzca confusión, se denomina testor típico [11]. Una MA puede contener varios testores típicos, de distinta longitud. Inclusive, una sola columna (rasgo) puede ser testor típico.
Ejemplo: es fácil ver que, para la MA de la tabla 1, el único testor típico es {color, altura, peso}.

2.2 Construcción del árbol k-d a partir de MA

Vamos a construir un árbol k-d para cada testor típico de MA. La idea es formar un árbol de decisiones (IF's anidados) donde se van haciendo preguntas adecuadas. El árbol k-d para el único testor típico {color, altura, peso} de la tabla 1 puede verse ya construido en la figura 1.

Algoritmo para producir un árbol k-d a partir de un testor típico y una MA.

ENTRADAS: el testor típico, en nuestro ejemplo {color, altura, peso}, y la matriz MA (en nuestro caso, la de la tabla 1) donde desaparecen todos los rasgos excepto los del testor típico.

SALIDA: El árbol (una estructura de datos) k-d correspondiente a ese testor típico y esa MA.

PASO 1. Escoger el rasgo que menos confusión produce. La confusión del color es 7; la de la altura es 11 (de alto) + 1 (de mediano) + 5 (de chaparro) = 17; la del peso = 15 (de ligero) + 8 (de pesado) = 23.

Luego, la primera variable a preguntar es ¿color? Esto corresponde al primer nodo de la figura 1. Como las respuestas deben estar completas, debemos poner todos los colores posibles como ramas saliendo del nodo ¿color? (ver figura 1). Para cada rama emanando del nodo colocado en el paso 1, si todos los objetos que tienen ese valor como rasgo pertenecen a la misma clase, hemos llegado a una hoja (nodo terminal), a la que etiquetaremos con esa clase única. Si los objetos en cambio pertenecen a más de una clase, apliquemos a esa rama el paso 2. Por ejemplo, para la primera rama, color=rojo, vemos que algunos objetos rojos son militares y otro es médico, por lo que esta rama pasa a procesarse por el paso 2.

PASO 2. Hallar la sub-matriz que corresponde al nodo de esta rama, y aplicarle recursivamente el Algoritmo para hallar el árbol k-d de esa sub-matriz. {FIN DEL ALGORITMO}

Ejemplo: Para los objetos color rojo, la sub-matriz es
 

Objeto número     Clase           Color        Altura          Peso

1                     C1 = militar                         rojo                      alto                         ligero

2                    C1 =                                      rojo                       alto                           pesado

7                   C2 =                                      rojo                       chaparro                pesado

Al aplicar recursivamente el algoritmo para formar el árbol k-d de esta sub-matriz, vemos que el rasgo altura tiene confusión 0 (en esta sub-matriz), en tanto que la confusión de peso es 1. Por consiguiente, la segunda variable a preguntar (para rojo) es ¿altura? Ver figura 1.

Al considerar la rama color=morado, la sub-matriz es
 

Objeto número     Clase           Color        Altura          Peso

3                    C1 =                                      morado                alto                          pesado

9                   C2 =                                      morado                alto                         ligero

La confusión para altura es 1; la confusión para peso es 0. Luego, la segunda variable a preguntar (para morado) es ¿peso? Ver en la figura 1 el árbol terminado.
En un nivel, no todas las preguntas son las mismas. Por ejemplo, en el nivel 2, los objetos rojos preguntan por ¿altura? en tanto que los morados preguntan por ¿peso?

2.3 Completando el árbol así obtenido

El árbol formado en §2.2 tiene algunos nodos que no están completos. Por ejemplo (Fig. 1), los azules preguntan por ¿altura?, pero no ofrecen alternativa si la respuesta es "chaparro".

azul —> ¿altura? mediano: —> médico
alto: —> abogado

Esto se debe a que algunas combinaciones legales no estuvieron presentes en la MA. Para completar el árbol, búsquense en los nodos incompletos las respuestas faltantes. A cada valor faltante se le asigna la misma rama que tiene el valor presente más cercano al faltante. Si ninguno está lo suficientemente cercano, se añade una hoja con el valor faltante y la etiqueta "abstención". En el ejemplo, el valor faltante es "chaparro". De los dos valores presentes (mediano y alto), "mediano" está cercano a "chaparro" (distancia 1).6 Entonces, agregamos la rama"chaparro" como si fuese un duplicado de la rama "mediano", quedando así el nodo:

azul —> ¿altura? mediano: —> médico
chaparro: —> puede ser
médico <— rama agregada
alto: —> abogado

Es decir, para cada valor faltante v en un nodo incompleto, se ve en ese nodo si el valor v' más cercano a v está razonablemente cerca de v. De ser así, se agrega "v —> r" al nodo, donde r es (una copia de) la rama de v'. Si v no está cerca de v', se agrega una hoja "v —> abstención." El objeto de procesar en un paso posterior los valores cercanos es permitir que el Algoritmo del árbol k-d pueda primero posicionar (en un nodo) dos valores cercanos en ramas distintas, si así aparecieren en MA. Sólo en el caso de ausencia de información en MA es que se usan las funciones de semejanza. El árbol es capaz de diferenciar si se utilizaron valores en MA ("es médico") o valores cercanos ("puede ser médico").

2.3.1 Formación de un programa en "C"

Se ha hecho un programa [4] generador que produce (obedeciendo §2.2 y §2.3) a partir de una MA (cuyas columnas se supone forman un testor típico), un programa en "C" como el siguiente (compárense con la figura ):

switch(color)
         {case"rojo":switch(altura)
                    {case"alto":printf("militar");
                      case"chaparro":printf("médico");
                      break;
                      default:printf("abstención");
                     break;
                      }
             break;
case "morado": switch ( peso) { ....}
break;
case "verde": switch ( peso) {... }
break;
.... /* Falta usar §2.3 para "completar" */
default: printf ("abstención");
break;
}

2.4 Uso de variables reales

El algoritmo del §2.2 trata sólo con variables que poseen un número pequeño de valores: booleanas, k-valentes, intervalos, enteros pequeños. Si alguna variable tiene un número grande de valores, o es real, habrá que dividirla en intervalos para transformarla a k-valente, o, más generalmente, usar un criterio de comparación C: R x Rà D donde la cardinalidad de D sea pequeña. Es mejor que el experto defina estos intervalos (pueden no ser igualmente espaciados y dependen del problema a resolver) o este criterio de comparación.

2.5 Comportamiento del árbol k-d en clasificación

Como se puede apreciar, el árbol k-d "aprende perfectamente" todos los objetos de la MA (quedan incorporados en un programa en C, §2.3.1), siendo 100% su porcentaje de aciertos en ellos. Si un objeto no está en MA pero se encuentra cercano (según la nota de pie de página # 3) a alguno que sí está, es clasificado en la misma clase que este último (Cf. §2.3). Aquí, el árbol k-d toma un riesgo "razonable" (Cf. §4.6) ya que los objetos fuera de MA sobre los que se atreve a opinar, están cerca de alguno en MA, según las funciones de semejanza (que sólo entran en juego para objetos que no están en MA). Si un objeto a clasificar está lejos de todos los de MA, el árbol se abstiene. Mientras más objetos diferentes tenga MA mejor clasificará el árbol k-d. Podemos calificar a este clasificador como de "seguro, pero temeroso" o cauteloso, ya que no se aventura más allá de MA o de los objetos cercanos a MA. Fuera de ahí, no opina.

III .EL ÁRBOL K-D COMO SISTEMA EXPERTO

La literatura abunda en la descripción de sistemas expertos [2], por lo que la siguiente tabla servirá para recordar sus principales características y para compararlos con los árboles k-d. Luego viene el procedimiento para fabricar un árbol k-d a partir de una base de conocimientos.

SISTEMA EXPERTO ÁRBOL K-D
 

¿Qué es?	Programa que almacena y aplica experiencias y conocimientos —a menudo difíciles de extraer— de "expertos"  o especialistas. Toma decisiones en situaciones complejas  pero limitadas (campos strechos)
Estructura	Máquina de inferencia, reglas del conocimiento (if ... then  ... else ..) que se disparan o actúan cuando es apropiado.	Árbol de decisiones donde cada nodo  está completo (posee todas las alternativas a la pregunta).
Obtención del conocimiento	Entrevistas a personas expertas * Poco tiempo disponible * Uso de Ingenieros del Conocimiento * Conversaciones difíciles * Se codifican opiniones, al fin.	Análisis de la realidad (base de datos de los objetos, v. gr., préstamos) * Extracción de los criterios automáticamente, por programa.
¿Se extraen todos los factores?	Tal vez no — Quizá se le olvide algo a  la persona experta.	Sí — todas las variables o rasgos de la base de  datos se toman en cuenta conforme su poder de discriminación.
Tipo de información	Que se usa Cuantitativa (números reales, enteros, valores booleanos). Cualitativa (valores discretos: profesión "médico","abogado", colonia  donde vive, partido político "PRI", "PRD", "PAN")  o k-valente. Pueden ser intervalos: estatura  chaparrito" "chaparro" "mediano" "alto"  "altote".
Modelo de ejecución	Basado en reglas — No hay flujo explícito de control	Basado en procedimientos —  Es un anidamiento de IF's.
Complejidad	Baja - Después de 200 ó 300 reglas, empiezan a interferirse	No hay interferencia.  Un árbol puede corresponder a muchos casos. (§2.5)
Tamaño en ejecución	Grande. La máquina de inferencia y la base de conocimientos debe estar en memoria	Mediano. Únicamente el árbol k-d  generado (programa en "C") debe estar presente en memoria.
Velocidad de ejecución	Aceptable. Las reglas se interpretan pero a  menudo dentro de un sistema interactivo	. Grande. Se toma una decisión  sobre un sujeto desconocido ejecutando k o  menos preguntas (en "C" compilado).

1Si la MAformada posee varios testores típicos, puede escogerse el mejor o varios de los mejores (Cf. §4.7).

1Hemos hecho árboles para diez mil casos u objetos. Para mayores cardinalidades, úsense también §§4.3 y 4.4.

Con respecto a la construcción de un árbol k-d a partir de la base de conocimientos de un sistema experto, daremos reglas para fabricar una MA a partir de esa base. Porque ya sabemos (Cf. §II) cómo construir un árbol k-d a partir de una MA, y estamos seguros de perfección (100% de aciertos) del árbol así construido (§2.5), cuando clasifica alguno de los renglones de esa MA.

El paso inverso, fabricar un sistema experto a partir de un árbol k-d, se reduce a examinar el programa en "C" (§2.3.1) y reescribir los postulados «switch» como reglas del sistema experto.

3.1 Conjetura: Todo sistema experto es equivalente a un árbol k-d

Este teorema (que hemos denominado simplemente "conjetura") puede demostrarse por construcción. Vamos a dar ejemplos de conversión de las reglas de un sistema experto basado en reglas a una matriz de aprendizaje. Dada la gran variedad de estos sistemas expertos, es probable que falten métodos de conversión en lo que sigue. Podría haber algún tipo de variable o de regla de ejecución de un sistema experto que fuese difícil (o imposible) de imitar con un árbol k-d. Pero los casos más útiles (§3.1.1 a §3.1.3) son susceptibles de arbolizarse.

3.1.1 Reglas (del sistema experto) con conectivos lógicos

Las variables lógicas se representan con un 1 en la MA; las que aparecen negadas, con un 0. Los conectivos & ("y") implican dos variables en la misma fila; los conectivos OR implican dos filas distintas. Las "conclusiones" se representan por clases. Ejemplo: (if x1 & ~x2 then R1) (if [x2 or x1] & x3 then R2). Estas dos reglas dan lugar a las siguientes filas de MA: X1 X2 X3 X4 CLASE 1 0 R1 1 1 R2 1 1 R2

3.1.2 Reglas con resultados parciales

Es común que las reglas de un sistema experto no den luego la respuesta, sino que generen resultados parciales que son utilizados por otras reglas. El truco es eliminar por substitución la respuesta parcial y producir una regla más larga. Ejemplo:

(if x1 & x2 then P1)................................. .(1)
(if x1 or x4 then P2)..................................(2)
(if P1 & P2 then R3)..................................(3)
(if P1 & ~P2 then R4)................................(4)

Comenzamos por substituir en la regla (3) los valores de P1 y P2: (if (x1 & x2) & (x1 or x4) then R3) = (if (x1 & x2) or (x1 & x2 & x4) then R3) que se pasa a MA
La regla (4) se convierte en (if (x1 & x2) & ~(x1 or x4) then R4) = (if (x1 & x2) & (~x1 & ~x4) then R4) que tiene un predicado siempre falso. La regla nunca se cumple. No la pasamos a MA. Queda así, pues, la regla (3) convertida a renglones de MA:

3.1.3 Reglas con predicados "difusos"

Muchos predicados supuestamente "difusos" en sistemas expertos pueden convertirse a intervalos "duros", pasando estas variables "difusas" a otras que son k-valentes. Otro tipo de conversión hace uso de las gráficas de parecido o funciones de semejanza. Finalmente, habrá sistemas expertos que genuinamente hagan uso de variables difusas. Habrá que usar en ellos variables multivaluadas [8], caso que no hemos estudiado.

Ejemplo: (if (poca fiebre) & (bastante pálido) then P1) (5)

Se ve (en la información del sistema experto) que "poca fiebre" es equivalente a 39 < T < 40. Se convierte la temperatura T (variable real) a otra variable T' que es k-valente.

Para el color, se ve (en la información del sistema experto) que "bastante pálido" es = amarillo ó cenizo ó blanco. La regla (5) se convierte en (if T' = B & [color = amarillo OR color = cenizo OR color = blanco] then P1) (6)

Esta nueva regla (6) da lugar a varios renglones (objetos) de MA:

O bien, pueden declararse en las gráficas de equivalencia de los valoresn del rasgo color (Cf. nota # 3 de pie de página) que amarillo, cenizo y blanco son equivalentes:

IV. EXTENSIONES Y CONCLUSIONES

Se examina aquí la relación entre los árboles k-d y otras construcciones que ocurren en Ciencias de la Computación, tratando de ver su convertibilidad o equivalencia. El trabajo termina con una sección de conclusiones y otra de recomendaciones.

4.1 Tabla de decisiones [7]

En esta tabla, cada renglón describe una situación, y cada columna denota un atributo o rasgo. La última columna describe la acción a tomar. Las tablas de decisiones no necesitan tener los nodos completos. Es decir, para algunos valores de rasgos puede no saberse la decisión.
Equivalencia: Si se completan sus nodos incompletos, pueden transformarse en árboles k-d. De hecho, un árbol k-d es una tabla de decisiones con los nodos completos. La conversión es sencilla: cada renglón de la tabla de decisiones se copia a la MA.

4.2 Árbol de decisiones [6, 10]

Es otra forma de representar una tabla de decisiones. Cada nodo interior es una pregunta. Las ramas contienen más preguntas, o acciones a tomar (cuando son hojas). No se requiere que los nodos sean completos. Equivalencia: Se aplican las mismas observaciones que a una tabla de decisiones.

4.3 Función de dispersión al azar (hashing)

Función que mapea su entrada (se admiten valores numéricos y no numéricos) en una dirección de memoria. En esta dirección de memoria se guarda la 'acción' a tomar: esta entrada pertenece a la clase "militar"; o se guarda ahí la información "Cubana 465" (Cf. §1.1), etc. La dirección en memoria se calcula a partir de algunos bits de cada valor de entrada; en ella se guarda información que corresponde a este conjunto de valores de entrada.

Equivalencia: Si las clases son pocas (menos de 500, digamos), se puede fabricar un árbol k-d asociando a cada combinación posible de entrada (de la función de dispersión) un renglón de la matriz MA. Luego, esta función es equivalente a un árbol k-d. Sin embargo, a menudo, esta función no guarda clases en memoria, sino otra información relacionada con los valores de las "llaves" de entrada. Por ejemplo, con "Adolfo Guzmán" como entrada, una función de dispersión produce la dirección 12,376, donde se guarda la información "Oaxaqueño; I. P. N.; SoftwarePro International" que queremos asociar a Adolfo Guzmán. El árbol k-d que el §2.2 fabrica no tiene manera de "darnos esa información" ya que su salida no es tan rica: únicamente emite clases, más la salida "abstención". A menudo también, los rasgos tienen muchos bytes cada uno (un nombre, digamos, tiene 25 bytes) y todas las combinaciones son posibles. Resulta impráctico fabricar una matriz de aprendizaje y usar el §2.2. Empero, los árboles k-d, cuando nacieron [1, 7], eran (y son) capaces de almacenar y representar este tipo de información, y brindan una alternativa al uso de llaves para guardar información.

4.4 Archivo con llave compuesta por varios valores; archivo de acceso directo

Si la función de dispersión al azar (§4.3) computa una dirección de disco y no de memoria principal, se tiene un archivo indexado o de acceso directo. Su llave es compuesta, pues está formada por información proveniente de varios campos o rasgos (que son los valores de las variables de entrada). Nótese que el acceso al registro correspondiente a una combinación de rasgos es rápido, pues no hay búsqueda o lectura secuencial sobre el disco. Equivalencia: Estos archivos son equivalentes a las funciones de dispersión al azar (§4.3), pero más grandes (tienen mayor dominio y mayor rango). Se usan para almacenar grandes volúmenes de información, que "no cabrían" en un árbol k-d generado por el §2.2 (ya que está restringido a residir en memoria principal), pero sí en uno que resida en memoria secundaria [1]. Nota: el ambiente gráfico Windows y sistemas operativos tales como Unix poseen memoria virtual, por lo que en ellos esta restricción no existe o está mitigada.

4.4.1 Directorios

En un archivo de acceso directo, la función que computa la dirección a partir de la llave, puede hacer uso de otros archivos auxiliares, llamados directorios, para hacer el mapeo de un valor de la llave a una dirección en disco. Por ejemplo, un directorio puede tener una serie de pares: (valor de la llave, dirección en disco donde se encuentra la información asociada). Como la longitud del directorio (número de registros) sería igual a la longitud del archivo de información, resulta conveniente organizar el directorio en árbol. Así, el primer nodo del directorio (una página del archivo, digamos 256 registros) dice lo siguiente: si buscas una llave de la AAAA a la ARGE mira en la página 2; de la ARGE a la BOCU mira en la página 3, ..(el primer nodo puede tener 256 de estas informaciones). Las páginas 2, 3, ... pueden a su vez referirme a otras páginas del directorio (a seguir mirando), o al lugar en disco donde yace la información buscada. Los directorios son árboles k-d poco profundos, y sus páginas o nodos contienen información que guía hacia otros nodos, y eventualmente a la posición donde se encuentra la información ligada a la llave.

4.5 Árbol b («b-tree»)

Es un caso especial, "balanceado" (b = balanceado) de un directorio representado como un árbol. Trata de conservar las ramas del árbol de la misma longitud, para minimizar la lectura de nodos de directorio. Ver [7]. Equivalencia: El árbol b, como un archivo indexado, asocia información a combinaciones de valores de las variables o rasgos. En este sentido, funciona como el árbol k-d, y ambos árboles son equivalentes. Como los archivos de acceso directo, un árbol b puede manejar gran cantidad de información (lo hace en disco). En la práctica, un archivo de acceso directo está formado de dos partes (que a menudo residen en el mismo archivo físico): un directorio (que puede ser del tipo árbol b) de llaves, y la información propiamente dicha.

4.6 Conclusiones

Se ha indicado (§II) cómo formar un árbol k-d a partir de un testor típico de la matriz de aprendizaje, para hacer un clasificador supervisado de comportamiento fuerte ante rasgos con valores no numéricos y numéricos indistinta y simultáneamente. Este clasificador únicamente clasifica (pero con buen porcentaje de aciertos) los objetos en la MA y los cercanos a ellos.

La manufactura mecánica de estos árboles es un método nuevo para la construcción barata y rápida de sistemas expertos. En vez de lentas entrevistas al especialista, el algoritmo del §2.2 puede analizar las bases de datos de casos y experiencias anteriores, y convertirlas en árboles k-d de manera automática, rauda y sin errores.

Para un sistema experto ya existente, se ha visto (§III) cómo fabricar un árbol k-d a partir de su base de conocimientos. En ambos casos, la ventaja del árbol k-d es su rapidez de ejecución y su producción mecánica, la que no posee los errores ni la subjetividad de una base de conocimientos hecha a mano.

También se han señalado, un tanto superficialmente (§IV), las conexiones con árboles de decisiones, funciones de dispersión al azar, archivos indexados y árboles b. Estas conexiones nos permiten conocer mejor nuestras herramientas; así sabremos cuándo utilizarlas y cómo intercambiarlas, según sea necesario. Y aprovecharemos las experiencias y características de unas cuando manejemos otras.

4.7 Recomendaciones para trabajos futuros

• * Dadas una MA y una matriz de control MC, extienda el algoritmo del §2.2 para que (1) genere todos los testores típicos de MA, (2) haga todos sus árboles k-d, (3) los aplique a MC, y (4) escoja el o los mejores árboles, tomando en cuenta los de mayor porcentaje de acierto en MC. Esto resolverá de manera mecánica el problema de determinar cuáles son los mejores rasgos en casos de clasificación supervisada.
• * Unión de árboles k-d. Dadas dos matrices MA1 y MA2, yo puedo generar su unión y de ella fabricar el árbol k-d correspondiente. El problema es generar (mecánicamente) tal árbol a partir no de MA1 y MA2, sino de árbol1 y árbol2.
• * Deltas de árboles k-d. En un caso real, dada una MAv vieja y otra MAr más reciente, algo ha cambiado en los objetos, con respecto a pertenencia a las clases. Por ejemplo, ahora hay más objetos verdes en la clase C1 que antes. ¿A qué conclusiones podemos llegar analizando MAv y MAr? ¿Y analizando árbolv y árbolr?

• A los ingenieros Enzo Molino Ravetto (Gerencia de Informática), Ramón Soberón (Subgerencia), René Rodríguez (Subgerencia de Medición), y ... Montoya (División Oriente) de Comisión Federal de Electricidad, por haber concebido y patrocinado el proyecto SIPEI [4].
• A SoftwarePro International e Informática Directiva Aplicada, S. A., por haber hecho posible estos desarrollos, e incorporarlos en su reciente producto, Classfinder ®.
• A los compañeros del Proyecto SIPEI: José Ruiz Shulcloper, Job Morales, María Esther Guevara Cruz, y Ángel Pacheco, por su colaboración entusiasta y decidida.

1. J. L. Bartley. Multidimensional binary search trees used for associative searching. Comm. ACM 18(9), 509-517 (Sept. 1975).

2. Z. Chen. Integrated use of expert systems at the K-tree level. ACM SIGART Bulletin 2(4), 6-11 (1991).

3. Adolfo Guzmán, José Ruiz Shulcloper. Hallazgo automático de clasificadores supervisados en problemas complejos. SoftwarePro International, Austin, TX. 1995 (Informe técnico en elaboración). Será sometido a Journal of Pattern Recognition.

4. Informe final sobre el SIPEI [CFE, Gerencia de Informática]. Informática Directiva Aplicada, S.A. México, 1994.

5. Manuel Lazo. Modelos basados en la teoría de testores, para la selección de rasgos y la clasificación supervisada, con descripciones no clásicas de objetos. Tesis en opción al grado de Doctor en Ciencias Matemáticas. Univ. Central de Las Villas. Santa Clara, Cuba. 1994.

6. J. R. Quinlan. Decision trees and decision making. Trans. Systems Man Cybernetics 20(2), 339-346 (April 90).

7. Hanan Samet. The design and analysis of special data structures. Addison Wesley 1990. (§2.4 K-D Trees, 66-80).

8. María Karina Sánchez Cajica. Tesis en opción al grado de licenciado en computación. Benemérita Universidad Autónoma de Puebla. Puebla, México. 1994.

9. E. N. Schwartz, Using complete k-trees to generate code in Pascal for an expert system. ACM SIGART Bulletin 1(2), 12-13.

10. E. N. Schwartz, G. Kiernan, A. Koltun. Response to "Are complete K-trees something more than decision trees?" ACM SIGART Bulletin 2(4), p4 (1991).

11. José Ruiz Shulcloper, Eduardo Alba-Cabrera, Manuel Lazo-Cortés. Introducción a la teoría de testores. Serie Verde, CINVESTAV-IPN (Mexico) (1995, en prensa).

12. José Ruiz Shulcloper, Manuel Lazo Cortés. Modelos matemáticos para el reconocimiento de patrones. Ed. UCLV, Santa Clara, Cuba.

13. José Ruiz Shulcloper, Eunice Ponce de León, Nancy López et al. ALVOT: Sistema de programas de algoritmos de votación para la clasificación. Revista Ciencias Matemáticas, 3(1), 41-67 (1986). Cuba.

14. Gabriel Valente. Are complete K-trees something more than decision trees? ACM SIGART Bulletin 2(2), p6 (1991).

©Adolfo Guzmán Arenas
SoftwarePro International