WIRS. Un Algoritmo de Reducción de Instancias Basado en Ranking

WIRS. Un Algoritmo de Reducci´on de Instancias Basado en Ranking * Carlos G. Vallejo, Jos´e A. Troyano, and F. Javier Ortega Departamento de Lenguajes y Sistemas Inform´aticos Universidad de Sevilla Av. Reina Mercedes s/n 41012, Sevilla [email protected] Resumen En este art´ıculo se presenta el algoritmo WIRS, una t´ecnica de reducci´on de instancias que tiene como objetivo seleccionar las instancias m´as representativas de una base de datos de aprendizaje. Este tipo de t´ecnicas se utilizan para conseguir bases de datos m´as peque˜nas sobre las que se pueda aplicar el algoritmo de los vecinos m´as cercanos con menor coste computacional y sin excesiva p´erdida de precisi´on. El algoritmo WIRS es una adaptaci´on del algoritmo WITS en el que se ha sustituido el criterio de la tipicidad por el de ranking a la hora de calcular el orden de las instancias necesario para aplicar WITS. Para calcular el ranking utilizamos una soluci´on similar a la empleada por PageRank, el algoritmo de c´alculo de relevancia de p´aginas web del buscador Google. Los experimentos demuestran que el uso del ranking como criterio de ordenaci´on obtiene resultados comparables a los obtenidos por la versi´on original de WITS, mejorando incluso estos resultados para algunas de las bases de datos utilizadas. Key words: Reducci´on de Instancias, Vecino m´as Cercano, PageRank, InstanceRank, WITS. 1. Introducci´on La t´ecnica de los vecinos m´as cercanos consigue muy buenos resultados de clasificaci´on mediante un algoritmo muy simple. En esta t´ecnica no hay una etapa de aprendizaje propiamente dicha, ya que no se llega a construir ning´un modelo. Cada vez que se clasifica una instancia, ´esta es comparada con todas las instancias de la base de datos de aprendizaje y se decide la clase que le corresponde en funci´on de las clases de las instancias m´as parecidas. Esta comparaci´on con todos los elementos de la base de datos permite que el algoritmo de clasificaci´on tenga en cuenta regiones en el espacio de b´usqueda que ser´ıan omitidas por otros algoritmos que s´ı realizan una generalizaci´on a partir de los datos. Pero no todos son beneficios, el coste de disponer de una t´ecnica simple y potente se encuentra en los requerimientos de almacenamiento (al no existir modelo hay que *Este trabajo ha sido parcialmente financiado por el Ministerio de Educaci´on y Ciencia (TIN 2004-07246-C03-03) 2 C. G. Vallejo, J. A. Troyano, F. J. Ortega mantener todas las instancias) y de tiempo (hay que comparar cada instancia a clasificar con todas las de la base de datos) en la etapa de clasificaci´on. Para resolver este problema se han propuesto varias soluciones, que se pueden organizar en dos categor´ıas: las orientadas a reducir el n´umero de instancias de la base de datos sin perder calidad en la clasificaci´on ([1], [2], [3]) y las que buscan acelerar la b´usqueda de las instancias m´as parecidas con la ayuda de estructuras de datos e ´ındices ([4], [5]). Nuestro trabajo se enmarca dentro de la primera de las categor´ıas, conocida como reducci´on de instancias, y consiste en una adaptaci´on del algoritmo WITS. En contra de lo que pudiera parecer, cuando se aplica una t´ecnica de reducci´on de instancias no siempre es en perjuicio de la precisi´on del clasificador. En ocasiones, se clasifica mejor con el conjunto de instancias reducido que con la base de datos original. En estos casos se dice que la t´ecnica edita la base de datos, ya que puede eliminar instancias ruidosas. El algoritmo WITS se apoya en el concepto de tipicidad, que mide lo representativa que es una instancia para su clase. Todas las instancias de la base de datos de entrenamiento se ordenan seg´un su tipicidad y esta ordenaci´on es usada por el algoritmo para determinar el orden en el que se van procesando las instancias. Nuestra propuesta consiste en sustituir el concepto de tipicidad, y la ordenaci´on que se deriva a partir de ´el, por un ranking calculado con t´ecnicas similares a las utilizadas en el c´alculo de la relevancia de los nodos de un grafo. En concreto, hemos utilizado una adaptaci´on del algoritmo PageRank, que aporta uno de los criterios en los que se apoya el buscador Google para medir la relevancia de una p´agina web en internet. El resto del art´ıculo se organiza de la siguiente forma. En la secci´on segunda se presenta el algoritmo WITS. La secci´on tercera presenta las ideas b´asicas de PageRank y el algoritmo para calcular el ´ındice de relevancia de las instancias. La secci´on cuarta contiene nuestra propuesta: el algoritmo de selecci´on de instancias WIRS que integra las ideas del algoritmo WITS con una adaptaci´on de PageRank (que hemos denominado InstanceRank) que permite crear un ranking de instancias; tambi´en se incluye en esta secci´on el dise˜no experimental y los resultados obtenidos. Por ´ultimo, en la secci´on quinta se extraen las conclusiones y se presentan las l´ıneas de trabajo futuro. 2. WITS: Selecci´on de instancias basadas en la tipicidad WITS (Weighted Instance Typicality Search) es una t´ecnica de selecci´on (y, por tanto, de reducci´on) de instancias propuesta por Morring y Martinez [6]. Se basa en el concepto de tipicidad de una instancia, propuesto por Zhang [7] como una medida de la representatividad de una instancia dentro de una clase: es el cociente entre la similitud media de la instancia con todas las de su misma clase (similitud intra-clase) y la similitud media con todas las de distinta clase (similitud extra-clase), donde la similitud de dos instancias xeyse define como 1−dist(x, y). Caracter´ısticamente, las instancias centrales de un cluster tendr´an una mayor similitud intra-clase, y de ah´ı una mayor tipicidad, los puntos de WIRS: Un Algoritmo de Reducci´on de Instancias Basado en Ranking 3 la frontera tendr´an una tipicidad intermedia y los elementos que conformen ruido o que sean excepcionales tendr´an una tipicidad m´as baja: la tipicidad es un concepto relativo. WITS es un algoritmo de orden O(n2). Produce un gran suavizado de los bordes de las clases, y puede conseguir cubrir de una forma bastante completa problemas en los que la frontera de decisi´on sea muy compleja. En WITS se toma como entrada el conjunto de instancias de entrenamiento Ty se devuelve el conjunto Sde instancias en el que cada una lleva un peso asociado, del siguiente modo: se considera el conjunto de instancias del conjunto de entrenamiento Tdividido en cubetas, cada una de ellas formadas por las instancias de una clase. A cada paso del algoritmo, y mientras queden instancias y haya errores, se considera una instancia candidata de la cubeta que contenga el mayor n´umero de instancias mal clasificadas por las instancias seleccionadas hasta el momento, y dentro de ella, la instancia restante de mayor tipicidad. Se calcula un peso ´optimo de candidata de manera que minimice el n´umero de errores producido por S∪candidata. Si ese error mejora sustancialmente el error que hab´ıa hasta el momento, se selecciona candidata, a˜nadi´endola a S, asoci´andole el peso ´optimo calculado anteriormente y recalculando el n´umero de errores de cada cubeta. Una especial menci´on merece la manera de evaluar cu´ando se mejora sustancialmente el error y c´omo se calcula el peso ´optimo: se considera que una instancia candidata mejora sustancialmente el error anterior si el error posterior, supuesto que se a˜nadiera la instancia, es menor que un cierto par´ametro de la aplicaci´on G, de modo que las instancias ruidosas o las que producir´ıan un sobreajuste perjudicial no se a˜naden. Este par´ametro suele tomarse proporcional al tama˜no del conjunto de entrenamiento. El peso ´optimo se calcula tom´andolo de una serie de posibles valores de la forma bk; en [6] se considera b= 1,1 y k= (0,1,2, . . . , 20), de modo que los pesos candidatos son [1.0, 1.1, 1.21, 1.331, . . . ,6.116, 6.727]. En la evaluaci´on del error se considera el vecino m´as cercano, k= 1. La distancia utilizada es HVDM (Heterogeneous Value Difference Metric), presentada en [8], que usa la distancia eucl´ıdea para los atributos continuos y VDM para los nominales, que es una m´etrica que determina la distancia entre los valores de los atributos seg´un la proximidad que tengan las clases que los suelen acompa˜nar. En la fase de generalizaci´on se utiliza la distancia anterior, ponderando las distancias seg´un los pesos asignados a las instancias. Se elige como clase de la instancia a generalizar la de la clase del vecino m´as cercano (k= 1), seg´un esa distancia ponderada. La estructura general del algoritmo WITS es la siguiente: func WITS(T: conjunto de instancias) dev S: conjunto de instancias ponderadas algoritmo para cada instancia ins en T: calcula la tipicidad de ins fin para ordena las instancias en orden descendente de tipicidad para cada instancia ins en T: 4 C. G. Vallejo, J. A. Troyano, F. J. Ortega asigna ins a la cubeta de su clase, manteniendo el orden fin para S:= ∅ numErroresAnterior := |T| para cada cubeta cubeta: numErroresCubeta := numero de elementos en cubeta fin para mientras haya instancias en las cubetas ynumErroresAnterior > 0: sea sigCubeta la cubeta con mayor numErroresCubeta cand := siguiente instancia de sigCubeta elimina cand de sigCubeta pesoCand := peso que minimiza el n´umero de errores numErroresPosterior := error obtenido por cand ∪Sevaluado sobre T si numErroresAnterior −numErroresPosterior ≥G: asigna el peso pesoCand acand S:= cand ∪S numeroErroresAnterior := numErroresPosterior para cada cubeta: recalcula numErroresCubeta fin para fin si fin mientras fin algoritmo 3. PageRank El PageRank, presentado por Brin y Page en [9], es la medida de la importancia de una p´agina web en internet utilizada por el buscador Google. Si consideramos Internet como un grafo dirigido, en el que los nodos son las p´aginas web y la existencia de una arista entre dos nodos denota que hay un enlace del primero hacia el segundo, se puede extraer un ´ındice de relevancia de cada nodo sin m´as que considerar la topolog´ıa del grafo (aunque Google realmente tiene en cuenta muchos m´as factores). Este ´ındice de relevancia es el PageRank, y se basa, como sustrato te´orico, en la existencia de un ”navegador aleatorio”que va visitando p´aginas web pulsando los enlaces que ve en ellos, o bien se va a una p´agina totalmente distinta. Esto se traduce en lo siguiente: si llamamos PR(V) al PageRank de la p´agina V, y llamamos In(V) al conjunto de las p´aginas que tienen enlaces hacia V(en la terminolog´ıa de grafos, los v´ertices origen de las aristas que tienen como destino V), y Out(V) el conjunto de los v´ertices hacia los que tiene enlace V(los v´ertices destino de las aristas que tienen como origen a V) es PR(V) = (1 −d) + dX W∈In(V) PR(W) |Out(W)| donde des un valor entre 0 y 1 ([9] recomienda 0.85) que modela la probabilidad de que el ”navegador aleatorio”navegue por los enlaces de una p´agina y (1−d) la probabilidad de que vaya a una p´agina cualquiera al azar. El PageRank de cada p´agina web puede calcularse mediante un sencillo algoritmo iterativo y representa una distribuci´on de probabilidad sobre las p´aginas web. WIRS: Un Algoritmo de Reducci´on de Instancias Basado en Ranking 5 El TextRank, debido a Mihalcea [10], es una adaptaci´on del PageRank a un problema muy distinto al anterior: la extracci´on de palabras clave y res´umenes de textos en el ´ambito del lenguaje natural. Una palabra o frase (en general, un v´ertice de un grafo) tiene un ranking mayor o menor dependiendo de la influencia que sobre ´esta tengan las dem´as; a este ranking se le denomina TextRank. En este contexto, una palabra o frase puede influir m´as o menos sobre otra, dependiendo de su similitud; por esta raz´on, y a diferencia del PageRank, la influencia tiene una cierta ponderaci´on: un v´ertice Vi influye en un v´ertice Vjcon un peso wij (por tanto, el grafo es ponderado). La expresi´on del PageRank anterior se convierte en el TextRank en TR(Vi) = (1 −d) + dX Vj∈In(Vi) wji Pvk∈Out(Vj)wjk TR(Vj) Por otra parte, la influencia de una palabra o frase sobre otra es rec´ıproca, de ah´ı que el grafo que describe la situaci´on sea no dirigido (wij =wji,In(V) = Out(V)), lo que simplifica mucho los c´alculos. La expresi´on del TextRank, al igual que la del PageRank, puede calcularse mediante un c´alculo iterativo, que converge. 4. WIRS: Selecci´on de instancias basada en ranking En este trabajo presentamos el algoritmo WIRS (Weighted Instance Ranking Search). En esta propuesta hemos partido de la premisa de que la medida de relevancia que aporta el ranking puede ser ´util para determinar qu´e instancias son m´as importantes dentro de la base de datos, de la misma forma en la que PageRank mide la importancia de una p´agina web en internet o TextRank la de una palabra o frase dentro de un texto. Por otra parte, hemos utilizado la estructura general del algoritmo WITS en cuanto a la mec´anica del orden de selecci´on de las instancias para su inclusi´on o no en el clasificador: se consideran las cubetas en orden descendente de n´umero de errores y dentro de cada una de ellas seg´un su ranking. Tambi´en hemos utilizado de WITS el criterio de seleccionar una instancia s´olo si su inclusi´on en el conjunto de instancias mejora sustancialmente las prestaciones del clasificador. 4.1. InstanceRank Hemos considerado las instancias de una base de datos como v´ertices de un grafo. Cada arista de este grafo ser´a la similitud entre las instancias que forman los extremos de la arista, que est´a etiquetada con esa similitud. Este grafo, por su naturaleza, es completo y no dirigido. Hemos definido la similitud entre dos instancias como una funci´on de la distancia entre esas dos instancias. Para la distancia entre dos instancias hemos utilizado la distancia eucl´ıdea para los atributos continuos. Para los discretos hemos considerado distancia 0 para los que tienen el mismo valor y 1 para los que tienen distinto valor. Finalmente, la distancia se ha normalizado, de manera que ∀v1, v2∈T0≤dist(v1, v2)≤1 Posteriormente hemos calculado la similitud entre dos instancias como una medida que cumple que ∀v1, v2, v3∈T: sim(v1, v1)=1 sim(v1, v2) = sim(v2, v1) sim(v1, v2)≥sim(v1, v3) + sim(v3, v2) 6 C. G. Vallejo, J. A. Troyano, F. J. Ortega Como funciones de similitud hemos experimentado con las siguientes: sim(dist)=1−dist k sim(dist) = 1 1 + k dist sim(dist) = e−kdist (1−dist) sim(dist) = e−k dist2 donde kes un par´ametro cuyo valor habr´a que ajustar adecuadamente. Estas cuatro funciones cumplen las tres propiedades anteriores, y sus valores est´an normalizados entre 0 y 1. La gr´afica de estas funciones se puede ver en la Fig. 1, en la que hemos representado los valores para k= 1 y k= 20 para cada una de ellas, estando los dem´as valores incluidos en el ´area delimitada por estos dos. 0 0.5 1 11 − dist / k sim 0 0.5 1 11/(1 + k dist) 0 0.5 1 1e−k dist/(1−dist) 0 0.5 1 1e−k dist2 Figura 1. Funciones de similitud Hemos aplicado una adaptaci´on del algoritmo TextRank para calcular la importancia de la instancia, que nos ha permitido establecer un ranking entre las instancias, por el que las hemos ordenado. La expresi´on del c´alculo del InstanceRank, donde el conjunto de entrenamiento es Ty las instancias son {Vi,1≤i≤ |T|}, es la siguiente: IR(Vi) = (1 −d) + d |T| X j=1 sim(Vj, Vi) P|T| k=1 sim(Vj, Vk)IR(Vj) El ranking introducido por el InstanceRank dentro de las instancias se ha utilizado para su elecci´on dentro del algoritmo WITS. 4.2. Bases de datos utilizadas, criterios de comparaci´on y l´ınea base Las bases de datos con las que hemos trabajado han sido tomadas del Repositorio de Bases de Datos de Aprendizaje Autom´atico de la Universidad de California en Irvine [11]. Las bases utilizadas son: Glass, Ionosphere, Iris, Pima, Sonar, Vote y Zoo, cuyas caracter´ısticas se detallan en el Cuadro 1. Los clasificadores obtenidos con WIRS se han probado con el vecino m´as cercano (kNN con k= 1), utilizando validaci´on cruzada estratificada con diez pliegues, por ser ´esta la medida m´as extendida en el ´ambito de la miner´ıa de datos y para poder comparar consistentemente los resultados con los de Morring y Martinez. Se ha programado dentro del entorno de WEKA [12] y utilizando su API, lo que facilita la escritura del clasificador y, especialmente, su evaluaci´on. WIRS: Un Algoritmo de Reducci´on de Instancias Basado en Ranking 7 Cuadro 1. Descripci´on de las bases de datos utilizadas Base de Atributos Atributos N´umero de % instancias N´umero de Datos Nominales Reales Clases clase mayoritaria instancias Glass 0 10 7 35.51 214 Ionosphere 0 34 2 64.10 351 Iris 0 4 3 33.33 150 Pima 0 8 2 65.10 768 Sonar 0 60 2 53.37 208 Vote 16 0 2 61.38 435 Zoo 1 6 7 40.59 101 En la evaluaci´on de los resultados se han considerado la precisi´on, medida en el porcentaje del n´umero de aciertos sobre el total de ejemplos de test (siempre teniendo en cuenta que se usa validaci´on cruzada con diez pliegues) y la reducci´on, medida en la proporci´on entre el n´umero de instancias en el conjunto de instancias seleccionadas respecto al n´umero de instancias en el conjunto de entrenamiento, de modo que un valor num´erico m´as peque˜no indica una mayor reducci´on. Como l´ınea base hemos tomado los resultados de la t´ecnica del vecino m´as cercano sin ning´un tipo de edici´on/reducci´on sobre los datos y los de WITS. 4.3. Ajuste de par´ametros En el desarrollo de WIRS se tuvieron que ajustar varios par´ametros hasta conseguir los resultados ´optimos. El par´ametro G, que en WITS indica la mejor´ıa en la clasificaci´on a partir de la que una instancia se incluye en el conjunto se ha tomado igual: 0.005 veces el n´umero de instancias del conjunto de entrenamiento, redondeando hacia arriba. Los dem´as par´ametros que hubo que ajustar fueron: la posible influencia de una instancia sobre s´ı misma en el c´alculo del InstanceRank, el valor de den ´este, la funci´on de similitud utilizada y el valor de ken estas funciones de similitud. Se comprob´o que era preferible no considerar la influencia de una instancia sobre s´ı misma en el c´alculo del rango. Para ajustar los otros par´ametros se realizaron experimentos con un amplio rango de valores de k(entre 1 y 20) y d(entre 0.65 y 1.0, con intervalos de 0.05) para cada una de las funciones de similitud, estudiando en cada caso los valores de estos par´ametros para los que se obten´ıan la mayor precisi´on media y la mayor reducci´on media en las siete bases de datos consideradas. Tambi´en se estudi´o cu´ando se obten´ıa el mejor compromiso entre reducci´on y precisi´on, siguiendo para ello el siguiente criterio: se ordenaron descendentemente los valores de kydpara los que se obten´ıa la mejor precisi´on, numerando cada uno de los casos; lo mismo se hizo para la reducci´on. Se tom´o finalmente como valor de compromiso el que hac´ıa que el producto del puesto en el ranking de reducci´on por el del puesto en el de precisi´on fuera menor. Los resultados se resumen en el Cuadro 2. Los mejores resultados fueron consistentemente para la funci´on sim(d) = 1 1+k d , por lo que se pas´o a estudiar ´esta para valores de dcon intervalos de 0.005. Se presentan los resultados en la Fig. 2, que se realiz´o con el fin de determinar la zona con mayor probabilidad de que haya un m´aximo; se observa que la zona de mayor precisi´on se da 8 C. G. Vallejo, J. A. Troyano, F. J. Ortega Cuadro 2. Valores de kydcon reducci´on y precisi´on m´aximas, y mejor equilibrio, para cada una de las cuatro funciones de similitud reducci´on m´axima precisi´on m´axima equilibrio red/prec sim red prec k d red prec k d red prec k d 1−dist/k 7.50 83.23 2 0.850 7.61 84.20 3 1.000 7.61 84.20 3 1.000 1/(1 + k dist) 7.47 84.73 9 0.955 7.71 85.83 8 0.900 7.70 85.57 8 0.940 e−k dist/(1−dist)6.90 84.13 4 1.000 7.62 84.52 2 0.900 7.55 84.48 4 0.850 e−kd27.15 84.47 6 0.850 7.72 84.88 13 0.900 7.68 84.52 12 0.900 alrededor de k= 8. En un an´alisis a´un m´as detallado se determin´o que los mejores valores en cuanto a equilibrio entre precisi´on y tasa de reducci´on se daban para k= 8, d = 0,940. Figura 2. WIRS: precisi´on con sim(dist) = 1 1+k dist , 4 ≤k≤20, 0.875 ≤d≤1.000 Tambi´en se ajust´o un par´ametro propio de InstanceRank (y PageRank) que indica el nivel de error aceptable por debajo del cual se detienen las iteraciones. Se tom´o un valor adecuado que consiguiera que el c´alculo del InstanceRank se hiciera con la suficiente precisi´on como para garantizar la correcta ordenaci´on de las instancias. Se estudi´o tambi´en el n´umero de iteraciones necesarias para conseguir esa precisi´on observ´andose que se manten´ıa en unos niveles m´as que aceptables en cuanto a tiempo de ejecuci´on (entre 3 y 10 iteraciones). WIRS: Un Algoritmo de Reducci´on de Instancias Basado en Ranking 9 4.4. Resultados experimentales Los resultados para estos valores de los par´ametros, comparados con los obtenidos por kNN (con k= 1) y WITS para esos mismos conjuntos de datos se detallan en el Cuadro 3. Para cada t´ecnica se detalla el tama˜no del conjunto reducido respecto del original y la precisi´on. En el cuadro se han resaltado en negrita los casos en los que cada t´ecnica ha destacado sobre la otra en tasa de reducci´on o en precisi´on. En los casos en los que la precisi´on mayor la consigue kNN, se ha resaltado en cursiva la t´ecnica, de entre WITS y WIRS, que ha alcanzado mayor precisi´on. Naturalmente, no se produce ninguna reducci´on en kNN. Cuadro 3. WIRS (con sim(dist) = 1/(1 + k dist), k = 8, d = 0,94), kNN y WITS: comparaci´on en reducci´on y precisi´on Base de kNN (k= 1) WITS WIRS datos % |S|/|T|% Precisi´on % |S|/|T|% Precisi´on % |S|/|T|% Precisi´on Glass 100.00 73.83 9.03 65.79 16.46 64.49 Ionosphere 100.00 84.62 7.33 88.06 4.50 92.31 Iris 100.00 94.00 4.64 93.53 6.07 95.33 Pima 100.00 73.56 1.56 74.48 1.42 76.43 Sonar 100.00 87.55 7.58 76.92 11.54 79.81 Vote 100.00 95.64 1.36 94.83 3.45 93.56 Zoo 100.00 94.44 7.62 94.06 10.45 97.03 Media 100.00 86.23 5.59 83.95 7.70 85.57 Como se observa, WIRS obtiene mayor reducci´on que WITS en dos de los conjuntos de datos (Ionosphere y Pima), en los que consigue adem´as mayor precisi´on que WITS e incluso que kNN. WIRS consigue mayor precisi´on que WITS e incluso que kNN en otros dos conjuntos de datos, Iris y Zoo, aunque en ´estos WITS es el que obtiene mayor reducci´on. En Vote WIRS queda ligeramente por debajo de WITS en precisi´on, aunque este ´ultimo algoritmo es superado por kNN. En dos de las bases, Glass y Sonar, los resultados tanto de WITS como de WIRS son notoriamente peores que los de kNN; en uno de los casos WITS queda por encima (Glass), y en el otro WIRS (Sonar). Resumiendo, WIRS resulta extraordinariamente competitivo en cuanto a precisi´on con uno de los algoritmos que actualmente marcan el estado del arte en t´ecnicas de reducci´on de instancias. En algunos casos tambi´en resulta competitivo en cuanto a reducci´on. 5. Conclusiones En este trabajo hemos presentado el algoritmo WIRS, una t´ecnica de selecci´on de instancias basada en el algoritmo WITS que utiliza la informaci´on proporcionada por un ranking de relevancia de instancias para determinar el orden en el que deben ser procesados los registros de la base de datos de entrenamiento. El ranking de relevancia de las instancias ha sido calculado con un algoritmo similar a PageRank, utilizado por Google para determinar la importancia de las p´aginas web de internet. Los resultados