Problemas de clasificación y optimización

PROBLEMAS DE CLASIFICACIÓN Y OPTIMIZACIÓN Por el Dr. EMILIO CARRIZOSA PRIEGO, Profesor Titular de Estadística e Investigación Operativa y Premio del año 1998 de la Real Maestranza de Caballería para Investigadores Jóvenes. Conferencia pronunciada el día 12 de marzo de 2003 ABSTRACT El desarrollo de técncias que permitan clasificar entes (seres vivos, elementos, problemas, ... ) en distintas categorías ha sido recurrente en diversas ramas del saber. La creación y difusión de grandes bases de datos y la consiguiente necesidad de extraer conocimiento de las mismas han revitalizado el interés de la comunidad científica por tales técnicas. En estas páginas se ilustra cómo la Programación Matemática puede contribuir al diseño de métodos autoináticos de clasificación y profundizar en el conociiniento teórico de los mismos. Nuestra intención no es hacer una revisión cotnpleta del estado del arte en el ten1a, sino más bien describir someramente las aportaciones que en esle campo se están realizando en el seno del grupo PAi FQM-809 y en el proyecto de investigación BFM2002-04525-C02-02 del MCYT. Palabras clave: Programación Matemática. Análisis Discriminante. 1. INTRODUCCIÓN Atendiendo al Diccionario de la Real Academia Española de la Lengua, clasificación es la acción de disponer u ordenar entes en clases. No aclara el Diccionario qué propiedades satisfacen las clases en las que deben disponerse los entes en cuestión. Nosotros supondremos que estas clases constituyen una partición del conjunto y nos restringünos por consiguiente a la clasificación nítida, por contraposición a los métodos basados en conjuntos borrosos. Tampoco aclara el Diccionario si las clases deben crearse (artificialmente) en el proceso mismo de clasificación o por el contrario existen previamente. De hecho ambas posibilidades han sido ampliamente estudiadas en la literatura, y proporcionan una clasificación de los problemas de clasificación. 227 Real Academia Sevillana de Ciencias Memorias 2002-2003 - -------- En el primer caso hablaremos de clasificación no supervisada, e.g. [13, 16, 17): debe determinarse una partición de modo que los elementos que queden en la misma clase de la partición sean homogéneos, mientras que los elementos de clases distintas tengan características dispares, donde los conceptos de homogeneidad y disparidad deberán ser definidos formalmente. En el caso en el que las clases de la partición estén definidas previamente hablaremos de problemas de clasificación supervisada, e.g. [12, 15, 21), y el objetivo perseguido es construir una regla que asigne cada objeto a la clase a la que pertenece. Problemas de los dos tipos aparecen, juntos o separados, en los más variados campos. Como ilustración, en el reciente texto [18) se describen aplicaciones en áreas tales como Marketing, Telecomunicaciones, Banca, Medicina, Farmacología, Genética, Informática, Educación, etc. 2, PLANTEAMIENTO GENERAL Se considera un conjunto de objetos, (la población) y dos funciones sobre G = G X= X. G es un conjunto finito, que llamaremos de etiquetas, e induce una partición de la población es un conjunto finito de clases. Diremos que G(o) E G es la clase de la partición a la cual el objeto o E pertenece. Por otro lado, X(o) representa, en un sentido que precisaremos después, una serie de características, cuantitativas o cualitativas, del objeto o. Llamaremos por eso X espacio de características, y tendremos en cuenta asimismo que X suele venir expresado como un subconjunto de un producto finito de espacios, II ' ( 1) donde cada representa el conjunto de valores que puede tomar la i-ésima propiedad o característica objeto de estudio. Como ilustración podemos mencionar los casos clásicos, = R si la i-ésima variable es cuantitativa o ... para variable cualitativas, los que podemos añadir otros más recientes y motivados por las aplicaciones, como Xi= R que modela la posibilidad de que el valor de la i-ésima propiedad sea desconocido, o X. es un aespacio de series temporales, o de distribuciones de fre- ' cuencias sobre un conjunto Kj de entes (para modelar e.g. la frecuencia relativa de apariciones de cada una de las palabras de en una página web). Una función se dice regla de clasificación sobre 228 Emilio Carrizosa Priego Se tiene un subconjunto.finito no vacío de objetos e que llamaremos muestra de aprendizaje. Conociendo las funciones G, X restringidas a se desea construir una regla de clasificación : G con un doble objetivo (descriptivo y predictivo): l. Clasificar correctamente todos los objetos de la meutra de aprendizaje, i.e., resolver la ecuación funcional = G(o) (2) 2. Clasificar correctamente todos los objetos de la población, i.e., resolver la ecuación funcional = G(o) (3) No se asumen propiedades de inyección sobre la función X, por lo que la ecuación (2) puede no tener solución. Como solo se dispone de las imágenes de las funciones G y X sobre los objetos de la muestra de aprendizaje, en ningún caso habrá garantías de poder clasificar correctamente todos los objetos de la población. En estas circunstancias, habrá que entender la resolución de (2) y (3) como la búsqueda de una regla de clasificación que las viole mínimamente. Para dar sentido preciso a lo anterior, introducimos una función de costo C : x R+, donde C(1t,o) representa el costo incurrido por clasificar en la clase rc(X(o)) el objeto o. Englobando varios modelos de función de costo existentes en la literatura, expresamos C a través de disimilaridades a las regiones clasificadas mediante con la misma etiqueta: Para cada g G sea dg una disimilaridad sobre X, i.e., d : X x Res una g función no negativa con d (x,x) No imponemos ninguna restricción sobre la disimilaridad d , que puede ser e.g. una métrica binaria, dg(x,z) = { O, si x z (4) para > O, una métrica inducida por un calibrador, como se verá en la sección 3, o, en g el caso de espacio de características definidos a través de (1 ), construido combinando disimilaridades en los e.g. [9, 17]. Definase la función de costo C como: = (X(o), {x E X: = G(o))) = inf : = G(o)} (5) Por ejemplo, para la métrica binaria ( 4 ), la función de costo C adquiere la fonna: 229 Real Academia Sevillana de Ciencias -Me,norias 2002-2003 { si "G(o) O, si = G(o) (6) Cada regla de clasificación¡¡ lleva asociado el vector de costos cuya o-ésima coordenada da el costo incurrido al clasificar o mediante La búsqueda de reglas de clasificación con costos de clasificación pequeños sobre puede formalizarse como el problema de optimización multiobjetivo. (7) donde la minimización hay que entenderla en con respecto al orden parcial natural, y e es el conjunto de reglas de clasificación permitidas. En la práctica sustituiremos el problema multiobjetivo (7) por alguna escalarización del mismo, resolviendo en lugar de (7) el problema escalar min (8) para una cierta E En particular, con una función de agregación lineal se obtiene min I (9) para unos ciertos positivos con suma l, que convierten (9) en el problema de minimizar el costo en un elemento seleccionado aleatoriamente ( con probabilidades de Obviamente, (9) no es la única escalarización posible o razonable de (7). Como ejemplo, también podemos seguir el enfoque minimax, min max (10) Obsérvese que en la expresión anterior, al igual que en todas las que siguen, los errores se consideran solo sobre la muestra de aprendizaje. El comportamiento sobre \ de la regla de clasificación así obtenida es, en principio, imprevisible: los datos disponibles no son, en muchas ocasiones, experimentales, sino observacionales. Pueden seguirse dos estrategias de aproximación al problema sobre el enfoque minimax, en el que se explora el peor caso, y se derivan cotas para el error de la "peor" extensión, e.g. [l2J; como alternativa, podemos seguir un enfoque muestra!, suponiendo que es una muestra aletoria de la población donde el mecanismo de generación aleatoria es conocido, e.g. es un muestreo aleatorio simple, o un 1nuestreo estratificado con probabilidades de generación en cada estrato (grupo) conocidas o estimadas. 230 Emilio Carrizosa Priego 3. CLASIFICADORES LINEALES Consideraremos en esta sección el caso más sin1ple en el que el espacio X en el que se representan las características de los objetos medidas por X es RP, que sólo hay dos etiquetas, G = {g 1, g2 ), y que el epsacio de reglas de clasificación permitidas se reduce al conjunto de reglas definidas por un hiperplano: Cualquier hiperplano en divide a éste en dos regiones (un semiespacio cerrado y su complementario) que podemos identificar con las regiones en las que la regla de clasificación toma respectivamente los valores g1 y g2• Las hipótesis anteriores son, evidentemente, restrictivas. No obstante, la construcción de clasificadores lineales para dos grupos puede usarse corno subrutina para la construcción de clasificadores no lineales para un número arbitrario de grupos. En efecto, la separación de varios grupos puede realizarse mediante un proceso secuencial en el que en cada iteración se separan dos grupos, constituidos por varios grupos. El lector puede encontrar e.g. en [4) más detalles y referencias sobre la implantación de estos métodos. Para la construcción de clasificadores no lineales, una estrategia muy exitosa en las aplicaciones prácticas se basa en realizar una inmersión (no lineal) de en un espacio R de mayor dimensión. Se consideran entonces las reglas lineales o, q que dan lugar a reglas no lineales E canónicamente: (11) corno se describe e.g. en [ 1 O]. Definamos '!é 1 \ {O}) x R. Para cada par (µ,B) E consideremos los serniespacios e hiperplanos = H#(µ,B) {x (u;x) # con#E Para cada se obtiene la regla de clasificación si x E (12) si x Siguiendo a [19), en la definición de la función de costos C de (4), imponemos que las disimilaridades vienen inducidas por calibraciones en e.g. [22). En otras palabras, se tiene un conjunto coinpacto conveso B C conteniendo al origen en su interior de modo que d(x,y) = (13) 231 Real Academia Sevillana de Ciencias -Memorias 2002-2003 donde y es el calibrador con bola unidad B, y(x)=min tB) Se tiene entonces, e.g. [24], es el calibrador dual de y, y(s)+ max{s,O). De esta forma, el problema multiobjetivo (7) puede reformularse como min (( ((X(o);u)-B)' donde G(o)=g),i= 1,2. ' ' (B-(X(o);u))' (14) (15) (16) Este problema guarda una cierta analogía formal con el problema multiobjetivo abordado en [5] en el que se minimizaban simultaneamente las distancias verticales en un problema de regresión. Sin embargo, mientras que en el caso de la regresión vertical el problema multiobjetivo era poliédrico (lineal a trozos y convexo), en este caso, el objetivo asociado a cada o E es el cociente de dos funciones convexas homogéneas, aparentemente sin propiedad de convexidad alguna. Una descripción de las soluciones eficientes de (16), como la obtenida en [5], sigue siendo un problema abierto. El grado de conocimiento sobre el problema es mayor en las escalarizaciones de (7). En efecto, el problema (9) se convierte en particualr en min introducido en [19]. ((X(o);u)-B)' (B-(X(o);u))' (17) Este problema guarda gran paralelismo, no solo formal, con el problema de determinación de un hiperplano mediano en : un hiperplano que minimiza la suma de las distancias (medidas con el calibrador y) a un conjunto de puntos dados de dimensión máxima, e.g. [23, 26]. Para el problema de determinación de hiperplanos medianos, en [24] se descompone el espacio en regiones poliédricas en las cuales la función a minimizar es cuasicóncava o suma de dos cuasicóncavas; se tiene, [7], que existe una solución en una cara ceroo uno-dimensional respectivamente de alguno de los politopos anteriores, que se corresponden a hiperplanos que pasan por p o p-1 puntos afínmente independientes. 232 Emilio Carrizosa Priego El mismo tipo de descomposición del espacio es válido para el problema (17), para el que se prueba en [25] que, bajo débiles condiciones, existe una regla de clasificación óptima, generada por un hiperplano que contiene a p-1 puntos afínmente independientes de cuando y es un calibrador arbitrario, incrementándose este número a p cuando es una norma. Una estrategia de resolución es válida pra la escalarización (l 0), que en este caso se convierte en min max (max max )) . (18) Un hiperplano centro es un hiperplano que minimiza la máxima de las distancias a un conjunto de puntos, e.g. [26, 27]. En [8] se realiza una linealización parcial de los objetivos, transformando el problema (localmente) en uno de minimizar una función cuasicóncava. De esta manera llegan a probar que, cuando los conjuntos no son linealmente separables y de dimensión máxima, existe un hiperplano óptimo tal que el número de puntos sobre él o a distancia igual al valor óptimo, es al menos p+ 1. En el caso en que el calibrador sea una norma, además podemos garantizar que estos p+ 1 puntos son afínmente independientes. 4. MODELOS BASADOS EN PROTOTIPOS Los métodos descritos previamente explotan fuertemente el hecho de que el espacio X de características, con la representación (1 ), es RP. Cuando no es ese el caso, otros métodos, que no estén basados en la esctructura de espacio vectorial de R", pueden ser más apropiados. Uno de estos métodos es el basado en la generación de prototipos para las distintas clases g E G, como se ha descrío en [ 6, 20]. Se tiene una disimilaridad d : X X X-, R. De cada clase g E G se tiene un conjunto P, C C) de candidatos a prototipos (representantes) de la clase g. Como espacio de reglas de clasificación n se considera el siguiente: cada subconjunto P e u P de k prototipos con todas las clases representadas, se identifica con la g g regla de clasificación rrP al vecino más próximo, [11], rr(x) = G(arg min { d(x,X(o)) : o E y P, } ), (19) donde los empates se rompen mediante un criterio preestablecido. Para la estructura de costes (6) inducida por la métrica binaria (4), en [6,20] se demuestra que el problema (9) es NP-duro, aunque es posible formularlo como un problema de programación lineal en números enteros, resoluble exactamente para problemas de tamaño muy reducido, o aproximadamente mediante heurísticas para problemas de mayor tamaño. 233 Real Academia Sevillana de Ciencias -Memorias 2002-2003 5. CLASIFICACIÓN Y REGRESIÓN Es posible acercarse a los problemas de clasificación desde la regresión y la estimación paramétrica. Tal es el caso de multitud de métodos basados en hipótesis distribucionales (e.g. normalidad) de los datos. como ocurre en el clásico y potente método de Fisher, [14]. o en (generalizaciones de) la regresión logística, que describimos. Suponernos que, si un objeto tiene características x, entonces éste proviene del grupo g E G con una probabilidad P/ÍJ,x) donde ÍJ = (ÍJ 8 ),,,G es un vector de parámetros. Imponernos una forma separable, salvo constantes multiplicativas, para Pg, i.e. dando lugar a .f/ÍJ<'x) P/ÍJ,x) = ------- L,, G .f,.(Í1,,x) (20) (21) En caso particular más notorio es el de la regresión logística, en el que se supone X = RP y se hace en (20) (22) donde(·;·) denota el producto escalar usual. El conjunto de objetos O se entiende entonces como una realización del experimento aleatorio regido por la ley anterior, de modo que su verosimilitud conjunta L({J;X)) viene dada por L({J;cJ) = n Pcr,,, (ÍJ,X(o)), (23) oEG donde los empates, caso de existir, se rompen con un mecanismo prefijado. El espacio de reglas de clasificación considerado n viene parametrizado a través de ÍJ : para cada 1} se define la regla de asignación al grupo más probable como = arg max (24) Como es desconocido, se propone la regla de máxima verosimilitudft identificada con un estimador de máxima verosimilitud para obtenido maximizando como se definió en (23): max log (25) 234 E,nilio Carrizosa Priego ----------------- -- ------ Definiendo la función de costo C como C(n,o) = log (n,X(o)), (26) el problema de determinación de la regla de máxima verosimilitud (25) aparece como el problema de determinación de la regla de mínimo costo, como se definició en (8). El problema (25), en general multimodal, deberá ser resuelto numéricamente. Mientras que un óptimo local puede ser obtenido con los procedimientos usuales de búsqueda local, para la optimización global serán necesarias técnicas más sofisticadas. En particular, bajo débiles hipótesis adicionales en el modelo (20), podemos utilizar métodos de optimización d.c., como los descritos en [1,2,3]. Para ello, suponemos que las funciones E --, log(f ,x)) son d.c. para cada x E esto es, log(f ,x)) = ,x)), gg (27) donde, para cada x E las funciones son convexas (y nosoros suponemos que conocidas). Entonces, sencillas manipulaciones algebraicas nos llevan a poder expresar la función objetivo de (25) como donde y son las funciones convexas = X(o)) X(o))) + X(o))) X(o))) X(o)) . Para una estructura poliédrica de el problema (25) puede resolverse e.g. por aproximación exterior. REFERENCES BLANQUERO, R. Localización de servicios en el plano mediante técnicas de optimización d.c. Tesis Doctoral. Universidad de Sevilla, 1999. [2] BLANQUERO, R. y E. CARRIZOSA. "On covering methods for D.C. optimization", Journal of Global Optimization 18, 265-274, 2000. [3] BLANQUERO, R .. E. CARRIZOSA y E. CONDE. "Finding GM-estimators with Global-Optimization techniques", Journal ofGlohal Optimization 21, 223-237, 2001. [4] BOCK, H.H. "Classification methodology", en Handhook of data mining and knowledge discovery, W. Klósgen and J.M. Zytkow (Eds.), Oxford, Oxford University Press, 258-267, 2002. [5] CARRIZOSA, E., E. CONDE, F.R. FERNÁNDEZ, M. MUÑOZ y J. PUERTO. "Pareto-Optimality in Linear Regression", Journal of Mathematical Analysis and Applications l 90, 129-141, 1995. 235