Metaheur´ısticas de Optimizaci´on en An´alisis de Conglomerados Javier Trejos Z.∗ CIMPA – Escuela de Matem´atica Universidad de Costa Rica 2060 San Jos´e, Costa Rica
Resumen En presencia de datos multivariados, los m´etodos usuales de clasificaci´ on por particiones obtienen ´ optimos locales del criterio a optimizar. La complejidad combinatoria del problema obliga a buscar heur´ısticas eficientes, tanto en tiempo como en calidad de las particiones. Por ello, se ha estudiado la implementaci´ on de m´etodos modernos de optimizaci´ on en el problema de clasificaci´ on por particiones para un n´ umero dado de clases. As´ı, se tienen m´etodos que implementan metaheur´ısticas como: Sobrecalentamiento simulado, B´ usqueda tab´ u, Algoritmos gen´eticos, Enjambres de part´ıculas, y Colonias de hormigas Se ha estudiado principalmente el problema de clasificar datos num´ericos minimizando un criterio de inercia o varianza intra-clases, aunque tambi´en se ha abordado el problema de clasificar datos binarios y datos bimodales. Se presentan resultados comparativos basados en simulaciones aleatorias de tablas de datos, con el fin de medir la calidad de los resultados.
Palabras clave: clasificaci´ on autom´ atica, an´ alisis de conglomerados, optimizaci´ on combinatoria, sobrecalentamiento simulado, b´ usqueda tab´ u, algoritmos gen´eticos, enjambres de part´ıculas, colonias de hormigas. Keywords: clustering, cluster analysis, combinatorial optimization, simulated annealing, tabou search, genetic algorithms, particle swarms, ant colonies.
1
Introducci´ on
Muchos m´etodos usuales en An´ alisis Multivariado de Datos encuentran ´ optimos locales de los criterios que minimizan. Tal es el caso en clasificaci´ on por particiones, escalamiento multidimensional, regresi´ on no lineal y conjuntos burdos. Recientemente, muchas heur´ısticas de optimizaci´ on han sido propuestas; su finalidad es encontrar ´ optimos globales en problemas de optimizaci´ on discreta. ∗ E-Mail:
[email protected]
1
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
2
Entre estas heur´ısticas, est´ an el sobrecalentamiento simulado (SS), la b´ usqueda tab´ u (BT), los algoritmos gen´eticos (AG), las colonias de hormigas (ACO), y los enjambres de part´ıculas (PSO), las cuales consisten en marcos generales de aplicaci´ on en diversos problemas, por lo que se ha dado en llamarlas metaheur´ısticas. Muchos autores han tratado de encontrar mejores soluciones a los problemas de An´ alisis Multivariado de Datos utilizando estas heur´ısticas de optimizaci´ on. En la Universidad de Costa Rica, el equipo PIMAD del Centro de Investigaci´ on en Matem´ atica Pura y Aplicada ha abordado distintos problemas: clasificaci´ on num´erica, clasificaci´ on binaria, clasificaci´ on bimodal, escalamiento multidimensional m´etrico, regresi´ on no lineal, selecci´ on de variables en regresi´ on lineal, y conjuntos burdos. El presente trabajo sintetiza los principales resultados encontrados en los problemas de clasificaci´ on estudiados. En la secci´ on 2 se presentan estos problemas: clasificaci´ on num´erica, clasificaci´ on binaria y clasificaci´ on bimodal. En la secci´ on 3 se presentan las metaheur´ısticas que hemos empleado para abordar los problemas de clasificaci´ on. En la secci´ on 4 se muestran los principales resultados comparativos obtenidos hasta el momento.
2
Problemas de clasificaci´ on
El objetivo de la clasificaci´ on autom´ atica (conocida como clustering en ingl´es) es encontrar grupos homog´eneos de objetos, de tal forma que objetos similares pertenezcan a la misma clase, y que sea posible distinguir entre objetos que pertenezcan a clases diferentes. En el caso num´ erico, se tiene el conjunto de objetos Ω = {x1 , . . . , xn } tal que para todo i, xi ∈ Rp , esto es, los objetos son descritos por p variables num´ericas o cuantitativas. En el caso de datos binarios los objetos xi pertenecen al conjunto {0, 1}p, es decir, son descritos por p variables binarias o de presencia–ausencia. El criterio m´ as ampliamente usado en el caso num´erico es la minimizaci´ on de la varianza o inercia intraclases: W (P ) =
K 1XX kxi − gk k2 n
(1)
k=1 i∈Ck
donde K es el n´ umero (fijado de antemano) de clases, P = (C1 , . . . , CK ) es la partici´ on que se busca, y gk es el centro de gravedad o vector promedio de Ck . Minimizar W (P ) es equivalente a maximizar la inercia interclases: B(P ) =
K X card(Ck ) k=1
n
kgk − gk2
(2)
donde g es el centro de gravedad total de Ω. Debe observarse que el criterio W satisface la propiedad de monotonicidad: ∗ ∗ min{W (P ) ∈ PK+1 } ≤ min{W (P ) ∈ PK }
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
3
∗ es el conjunto de todas las particiones de Ω en exactamente K clases donde PK no vac´ıas; esto significa que no tiene sentido comparar particiones con diferente n´ umero de clases, y por ello el n´ umero de clases es fijado previamente. Los m´etodos cl´ asicos, como k-medias (b´ usqueda local) o clasificaci´ on jer´ arquica (m´etodo voraz) encuentran por lo general m´ınimos locales de W [6]. Por lo tanto, hemos aplicado las heur´ısticas modernas de optimizaci´ on que se mencionan a continuaci´ on, buscando la mejor´ıa de los resultados dados por los m´etodos existentes. En el caso de datos binarios, el primer problema es definir un criterio num´erico de homogeneidad. Nosotros hemos estudiado [13], [19] las propiedades de varios criterios aditivos del tipo ([16])
W (P ) =
K X
δ(Ck )
k=1
donde δ(C) es una medida de homogeneidad de la clase C, y los que brindaron mejores resultados fueron la suma de las disimilitudes: X δsum (C) = d(x, x0 ) (3) x,x0 ∈C
y la suma ponderada de las disimilitudes: δwsm (C) =
X 1 d(x, x0 ). 2|C| 0
(4)
x,x ∈C
Estos criterios satisfacen la propiedad de monotonicidad. En el caso de clasificaci´ on bimodal o clasificaci´ on cruzada, sea X = (xij ) una matriz bimodal (por ejemplo, una tabla de contingencia) con xij ≥ 0. Se quiere minimizar el criterio de varianza definido por: W (P, Q) =
L X X K X X
(xij − gkl )2
(5)
k=1 l=1 i∈Ak j∈Bl
donde (P, Q) es una partici´ on bimodal (esto es, una partici´ on P = (A1 , . . . , AK ) de las filas y una partici´ on Q = (B1 , . . . , BL ) de las columnas de X), y X X gkl = xij . i∈Ak j∈Bl
En [18] describimos el uso de SS, y en [5] la aplicaci´ on de BT a este problema.
3
Uso de heur´ısticas de optimizaci´ on
Se define un problema de optimizaci´ on combinatoria como la minimizaci´ on de una funci´ on real de costo, definida sobre un conjunto finito o numerable de
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
4
estados. En el caso del particionamiento num´erico y binario, un estado es una on de costo es la partici´ on P = (C1 , C2 , . . . , CK ) de Ω en K clases, y la funci´ inercia intra-clases W (P ). En el caso del particionamiento bimodal un estado es una partici´ on bimodal (P, Q) = (A1 , . . . , AK ; B1 , . . . , BL ) y la funci´ on de costo es el criterio de varianza W (P, Q). Entre los m´etodos m´ as sencillos de optimizaci´ on combinatoria, est´ an la b´ usqueda local y los m´etodos voraces. Los primeros tratan de mejorar, paso a paso, el criterio de optimizaci´ on, hasta que haya estabilidad; si el punto inicial en la b´ usqueda no est´ a dentro de la regi´ on de influencia del ´ optimo global entonces se converger´ a a un ´ optimo local. En el caso de los algoritmos voraces, se trata de hacer mejor´ıas parciales al criterio en cada paso, sin que se revisen las decisiones anteriores en los pasos posteriores; de esta forma, generalmente se llega tambi´en a ´ optimos locales, aunque hay casos en que se puede converger a´ optimos globales. Los m´etodos m´ as conocidos de clasificaci´ on tienen las caracter´ısticas anteriores, ya que el algoritmo de clasificaci´ on jer´ arquica ascendente es un m´etodo voraz, y el m´etodo de las k-medias es uno de b´ usqueda local. Ambos conducen a ´ optimos locales del criterio a optimizar. En [2], [3] ´ o [6] se describen estos m´etodos.
3.1
Heur´ısticas basadas en vecindarios
Las principales heur´ısticas de optimizaci´ on combinatoria basadas en vecindarios son el sobrecalentamiento simulado [10], a veces llamado recocido simulado, y la b´ usqueda tab´ u. En ambos casos hemos implementado m´etodos para particionamiento [17]. 3.1.1
Sobrecalentamiento simulado
El sobrecalentamiento simulado usa un par´ ametro externo de control, llamado temperatura y denotado ct , que controla la probabilidad de acceder a un vecino con un valor del criterio peor que el del estado actual, y al descender la termperatura desciende tambi´en esta probabilidad hasta que la temperatura es cero y la b´ usqueda se convierte en una b´ usqueda local. Lo importante es que se puede probar —mediante una modelizaci´ on basada en cadenas de Markov homog´eneas— que el sobrecalentamiento simulado converge asint´ oticamente al optimo global. El arte de la implementaci´ ´ on requiere un adecuado manejo de los par´ ametros, especialmente el n´ umero de iteraciones (asociado a la longitud λ de las cadenas de Markov); las dem´ as escogencias son bastante est´ andar [1]. En particionamiento, un vecino se define por la transferencia de un u ´nico individuo, de la clase a la que pertenece actualmente, a una nueva clase. De esta forma, se puede simplificar el c´ alculo de la variaci´ on en el criterio ∆W una vez realizada la transferencia, lo cual hace que los tiempos de ejecuci´ on de los algoritmos se mejoren sustancialmente. En todo lo que sigue, las escogencias al azar son hechas con base en una distribuci´ on uniforme, acorde con cada contexto. El algoritmo de particionamiento
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
5
usando sobrecalentamiento simulado es como sigue: Algoritmo CASS. γ ∈ [0.8, 0.99].
El usuario escoge los par´ ametros χ0 ∈ [0.80, 0.95], λ ∈ N,
1. Inicializar P al azar; calcular W de acuerdo con (1). 2. Estimar la temperatura inicial c0 usando la tasa de aceptaci´ on inicial χ0 (ver [1]). 3. Hacer λ veces: (a) Hacer la transferencia de i de Ck a Ck0 de la siguiente manera: - escoger al azar i en {1, . . . , n}; la clase actual de i se denota k; - escoger al azar k 0 en {1, . . . , K}, diferente de k; - calcular ∆W . (b) Aceptar la transferencia si ∆W < 0, sino aceptarla con probabilidad exp(∆W/ct ). 4. Hacer ct+1 := γct y regresar al paso 3, hasta que ct ≈ 0. 3.1.2
B´ usqueda tab´ u
La b´ usqueda tab´ u [7] explora en cada iteraci´ on un conjunto de vecinos del estado actual y escoge el que tiene el mejor valor. Ahora bien, para evitar ciclos y poder tener acceso al ´ optimo global, en la escogencia del mejor vecino no se compara con el valor actual, y adem´ as se maneja una lista tab´ u, de longitud |T |, que no permite repetir los movimientos de las u ´ltimas iteraciones. El arte de la implementaci´ on establece que se introduzcan ciertos pasos de intensificaci´ on de la b´ usqueda en una regi´ on interesante, y de diversificaci´ on cuando se considera que una regi´ on ha sido suficientemente explorada; adem´ as, conviene implementar un criterio de aspiraci´ on que permita acceder a un buen estado a´ un no visitado que podr´ıa eventualmente estar en la lista tab´ u. El algoritmo, para el caso de particionamiento, es el siguiente: Algoritmo TabuClus.
Escoger los param´etros |T |, maxnum, sizeneigh ∈ N.
1. Inicializar P al azar; calcular W de acuerdo con (1). 2. Empezar la lista tab´ u con T := {W (P )}. Sea Popt := P . 3. Repetir maxnum veces: (a) Generar el vecindario V de P repitiendo sizeneigh veces: - escoger un objeto i en {1, . . . , n}; la clase actual de i se denota k; - escoger al azar k 0 en {1, . . . , K}, diferente de k; - hacer la transferencia de i de Ck a Ck0 .
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
6
(b) Calcular W (Pasp ) = min {W (P 0 )|(P 0 ) ∈ V}. (c) Si W (Pasp ) < W (Popt ) entonces P ∗ = Pasp y Popt = P ∗ . Sino, sea P ∗ tal que W (P ∗ ) = min {W (P 0 )|(P 0 ) ∈ V, W (P 0 ) 6∈ T }. (d) P := P ∗ . (e) Actualizar T introduciendo el valor W (P ∗ ) y sacando el valor m´ as viejo.
3.2
Heur´ısticas basadas en poblaciones
Los m´etodos basados en el manejo de poblaciones, usan un conjunto de estados del problema de optimizaci´ on (llamado poblaci´ on o conjunto de agentes) en lugar de un solo estado, y generalmente combinan los elementos para definir la poblaci´ on de la siguiente iteraci´ on. Entre estos m´etodos est´ an los evolutivos (entre los que se encuentran los algoritmos gen´eticos [8]), la optimizaci´ on por colonias de hormigas [4], y la optimizaci´ on por enjambres de part´ıculas [9]. M´ as recientemente, han surgido otras heur´ısticas, como los sistemas inmunes [22], que estamos estudiando para su respectiva implementaci´ on en particionamiento. En los tres casos que siguen, denotamos con M el tama˜ no de la poblaci´ on de agentes que se usa. 3.2.1
Algoritmo gen´ etico
El algoritmo gen´etico que hemos trabajado usa una representaci´ on cromos´ omica con los ´ındices de clases para los individuos a clasificar, selecci´ on aleatoria proporcional a la funci´ on de adaptaci´ on —que en nuestro caso es la inercia interclases B—, operadores de mutaci´ on y un cruzamiento adaptado; luego se hacen iteraciones hasta que se converge a repeticiones de una misma soluc´ on [8]. Algoritmo GAP. ≈ 0.
Escoger los param´etros M, maxiter ∈ N, pµ , pc ∈]0, 1[ y
1. Inicializar particiones P 1 , . . . , P M al azar; calcular B(P 1 ), . . . , B(P M ) de acuerdo con (2). 2. Sean t := 0, Π(t) := {P 1 , . . . , P M }. 3. Repetir hasta que σB < o hasta que t ≥ maxiter: (a) t := t + 1 (b) seleccionar Π(t) de Π(t − 1) mediante ruleta aleatoria; (c) aplicar un operador de cruzamiento con probabilidad pc ; (d) aplicar un operador de mutaci´ on con probabilidad pµ ; (e) si t ≡ 0 mod(5) entonces aplicar k-medias.
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
7
En el algoritmo anterior, la ruleta aleatoria consiste en seleccionar una muestra con repeticiones a partir del conjunto de particiones de la iteraci´ on anterior, donde cada partici´ on P m tiene probabilidad proporcional a B(P m ); este procedimiento hace que las particiones con mejores valores del criterio de inercia interclases tengan mayor chance de sobrevivir a lo largo de las iteraciones. El operador de cruzamiento consiste en seleccionar al azar dos particiones P m1 y P m2 de Π(t) tales que P m1 > P m2 , y seleccionar un ´ındice k ∈ {1, . . . , K}, que fija una clase de P m1 ; entonces, copiar en la partici´ on P m2 la clase k de P m1 . El operador de mutaci´ on consiste en escoger al azar una partici´ on P m en Π(t), un objeto i ∈ {1, . . . , n} y un ´ındice de clase k ∈ {1, . . . , K}, y entonces modificar P m asignando i a la clase k (si ´esta es diferente de la clase a la que pertenec´ıa el objeto antes de la operaci´ on). El criterio de parada calcula la desviaci´ on est´ andar σB del conjunto {B(P 1 ), . . . , B(P M )}. 3.2.2
Colonias de hormigas
Son menos conocidas las heur´ısticas de colonias de hormigas y enjambres de part´ıculas. En ambas se manejan, como en algoritmos gen´eticos, conjuntos de agentes. En optimizaci´ on por colonias de hormigas [21], estos agentes se asocian a particiones y las buenas soluciones hacen crecer la probabilidad de asignar objetos a la misma clase. La optimizaci´ on por colonias de hormigas trata de imitar el procedimiento de las colonias de estos insectos para entontrar alimento y llevarlo al hormiguero. Para ello, la t´ecnica se basa en dos elementos: el trazo de feromona τ , y la visibilidad η, con las cuales se definen las probabilidades p, definiendo todas ellas matrices de dimensi´ on n × n: [τij ]α [ηij ]β pij = Pn . α β l=1 [τil ] [ηil ]
(6)
Algoritmo AcoClus. Definir los par´ ametros M, tmax , S ∈ N; τ0 , α, β ∈ R+ ; ρ ∈ ]0, 1]. 1. Inicializar (τ )n×n con τij = τ0 . 2. Calcular (η)n×n como ηij = 1/kxi − xj k. 3. Inicializar las probabilidades pde acuerdo con (6). 4. Inicializar al azar particiones P 1 ,. . .,P M asociadas a cada hormiga. 5. Aplicar k-medias en cada P m para converger a un ´ optimo local de W . 6. Para t = 1 hasta tmax hacer: (a) Para m = 1 hasta M , hacer S veces: i. Escoger al azar un objeto i; ii. Escoger un objeto j con probabilidad pij , de acuerdo con (6)
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
8
iii. Asignar j a la misma clase de i. (b) Calcular B(P 1 ), . . . , B(P M ) y guardar el mejor valor. (c) Actualizar τ . La actualizaci´ on de la feromona τ se modifica de acuerdo con τij (t + 1) = (1 − ρ)τij (t) + ρ ∆τij (t + 1)
(7)
ametro donde los valores τij asocian a dos objetos i, j de Ω, y ρ ∈ ]0, 1] es un par´ de evaporaci´ on. Sea ∆τij (t + 1) =
M X
∆m τij (t + 1),
(8)
m=1
donde ∆m τij (t + 1) es la cantidad de feromona del agente en la asociaci´ on de los objetos i, j en la misma clase, y es definida por B(P m )/I si i, j pertenecen a la misma clase de P m (9) ∆m τij (t + 1) = 0 sino. As´ı, dos objetos que pertenezcan a la misma clase dejan un trazo de feromona. 3.2.3
Enjambres de part´ıculas
En enjambres de part´ıculas [20] las particiones est´ an asociadas a sus centros de gravedad, que se mueven en el espacio multidimensional con la particularidad de que los agentes–particiones se comunican de acuerdo con tres principios: inercia, imitaci´ on al mejor agente, y regresi´ on a la mejor posici´ on encontrada anteriormente. La PSO se basa en el uso de un conjunto de agentes o part´ıculas que corresponden a estados de un problema de optimizaci´ on, haciendo que cada agente se mueva en un espacio num´erico en busca de una posici´ on ´ optima. Una particularidad de la PSO es que los agentes se comunican entre s´ı, y entonces –como en un sistema social– un agente con una buena posici´ on (medida por su valor de la funci´ on objetivo) influye en los dem´ as, atray´endolos hacia ´el. Proponemos entonces el siguiente algoritmo para la minimizaci´ on de W (P ) usando PSO. Para ello el usuario define el n´ umero M de agentes-particiones, siendo cada agente un conjunto de K centroides ~g1 , . . . , ~gK ∈ Rp . Cada centroide ~gk tiene asociada una clase Ck mediante la asignaci´ on de los objetos de Ω al centroide m´ as cercano. Los centroides se mover´ an seg´ un los principios del PSO descritos m´ as adelante y luego se redefine la partici´ on mediante la asignaci´ on al centroide m´ as cercano. El PSO consistir´ a entonces en el desplazamiento, de intensidad aleatoria, de K centroides (o part´ıculas) para cada agente en Rp en la direcci´ on del mejor agente, limitando el desplazamiento en la direcci´ on de un vector ~vk (llamado velocidad) con un valor Vmax para evitar la explosi´ on y procurar la convergencia.
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
9
Algoritmo PsoClus. Definir M , Vmax , maxiter. 1. Inicializar al azar particiones P 1 ,. . .,P M . 1 M 2. Calcular los centroides ~g11 , . . . , ~gK , . . . , ~g1M , . . . , ~gK de los clases.
3. Repetir para t = 1, 2, . . . hasta convergencia o maxiter veces: (a) Para m = 1 hasta M hacer: ∗ i. Sea P ∗ el mejor agente-partici´ on seg´ un (1), asociado a (~g1∗ , . . . , ~gK ) ii. Para k = 1 hasta K hacer: • Para j = 1 hasta p hacer: m m ∗ m – Sea vkj (t) := vkj (t − 1) + random[0, 2](gkj − gkj (t − 1)) m m – Si vkj (t) > Vmax entonces vkj (t) := Vmax m m – Sino, si vkj (t) < −Vmax entonces vkj (t) := −Vmax m m m – gkj (t) := gkj (t − 1) + vkj (t − 1) iii. Asignar los n objetos de Ω al centroide ~gkm m´ as cercano.
3.3
Caso binario
Las implementaciones del SS y la BT para el caso de datos binarios son similares al caso num´erico. Para el AG, la funci´ on de fitness se define como B(P ) = W (Ω) − W (P ), y el resto de caracter´ısticas del algoritmo son como en el caso num´erico. No es posible hacer una adaptaci´ on del PSO a este caso en vista de que no se dispone de centro de clases en un espacio num´erico. La adaptaci´ on al uso de ACO a´ un no se ha hecho.
3.4
Caso bimodal
Hemos implementado el SS y la BT en el caso de tablas bimodales. En el primer caso, se trata de un algoritmo similar al del caso num´erico, excepto que se debe escoger al azar el modo (fila o columna) de la transferencia que se analiza en cada iteraci´ on. En la BT se generan vecindarios mediante escogencias aleatorias en cada uno de los dos modos, y se procede de manera similar al caso num´erico. M´ as detalles se pueden consultar en [18] y [5].
4
Resultados comparativos
Se han llevado a cabo numerosas comparaciones entre los m´etodos mencionados usando las heur´ısticas de optimizaci´ on aqu´ı descritas, y los m´etodos cl´ asicos de clasificaci´ on.
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
4.1
10
Tablas de datos reales
En la tabla 1 se presentan los resultados de aplicar los m´etodos aqu´ı descritos, sobre cuatro tablas de datos reales, usadas en la literatura para efectos de comparaci´ on de metodolog´ıas. La dimensi´ on n × p de cada tabla aparece al lado del nombre de la misma; luego del s´ımbolo # se indica el n´ umero de veces que se aplic´ o el m´etodo correspondiente. Bajo la sigla de aplicaci´ on de cada m´etodo se reporta el mejor valor del criterio W encontrado, y el porcentaje de veces que se encontr´ o en las corridas. Adem´ as de los m´etodos basados en heur´ısticas de optimizaci´ on, se reporta el resultado para k-medias y clasificaci´ on jer´ arquica de Ward. Los resultados de aplicar PSO no se reportan, ya que el m´etodo a´ un se encuentra en la etapa de calibraci´ on de los par´ ametros. ACO K
W
BT
%
SS AG W % W % Notas Escolares Francesas (9 × 5) # = 1000 # = 150 # = 100 28.2 100% 28.2 100% 28.2 100% 16.8 100% 16.8 100% 16.8 95% 10.5 100% 10.5 100% 10.5 97% 4.9 100% 4.9 100% 4.9 100% W
%
2 3 4 5
# = 25 28.2 100% 16.8 100% 10.5 100% 6.7 100%
3 4 5
# = 25 32213 100% 18281 100% 14497 100%
# = 200 32213 100% 18281 100% 14497 97%
3 4 5
# = 25 271.8 100% 235 96% 202.6 84%
Sociomatriz de Thomas (24 × 24) # = 200 # = 150 # = 100 271.8 100% 271.8 100% 272.9 85% 235.0 100% 235.0 100% 250.8 24% 202.6 98% 202.6 100% 223.8 4%
2 3 4 5
# = 25 0.999 100% 0.521 100% 0.378 100% 0.312 100%
# = 25 0.999 100% 0.521 76% 0.378 60% 0.312 32%
Peces de Amiard (23 × 16) # = 150 # = 100 32213 100% 32213 87% 18281 100% 22456 90% 14497 100% 20474 38%
Iris de Fisher (150 × 4) # = 150 # = 50 0.999 100% 0.999 100% 0.521 100% 0.521 100% 0.378 55% 0.378 82% 0.329 100% 0.312 6%
kM W
%
# = 10000 28.2 12% 16.8 12% 10.5 5% 4.9 8%
Ward W
28.8 17.3 10.5 4.9
# = 10000 32213 8% 18281 9% 14497 1%
33149 19589 14497
# = 10000 271.8 2% 235.0 0.15% 202.6 0.02%
279.3 239.4 204.7
# = 10000 0.999 100% 0.521 4% 0.378 1% 0.312 0.24%
– – – –
Tabla 1: Mejor valor de la inercia intraclases W y porcentaje de veces encontrado al aplicar # veces cada m´etodo: colonias de hormigas (ACO), b´ usqueda tab´ u (BT), sobrecalentamiento simulado (SS), algoritmo gen´etico (AG), k-medias (kM), y jer´ arquico de Ward. Seg´ un los resultados reportados en la tabla 1, el SS y la ACO son superiores a los dem´ as m´etodos, siguiendo la BT y luego el AG, sigue el k-means y finalmente el m´etodo de Ward. Se debe se˜ nalar que falta hacer la pruebas con PSO con el fin de comparar su rendimiento con el resto de heur´ısticas.
4.2
Tablas de datos simulados
Se realiz´ o un experimento exhaustivo [12] para comparar SS, BT, AG y ACO con k-medias y clasificaci´ on jer´ arquica de Ward. Se generaron tablas con generadores de n´ umeros seudo-aleatorios, y se llev´ o a cabo un experimento con 4 factores y dos niveles en cada uno. Los factores son: • El n´ umero n de individuos; se tom´ o n = 105 y n = 525. • El n´ umero K de clases; se tom´ o K = 3 y K = 7.
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
11
• La cardinalidad de las clases; se tom´ o todas las clases con misma cardinalidad, y una clase mayor que el resto (con aproximadamente el 50% de todos los objetos). • La varianza de las clases; se tom´ o todas las clases con igual varianza, y una clase con el triple de varianza que el resto. En todos los casos las tablas tienen p = 6 variables. Los vectores de medias fueron generados al azar en [0, 1]6 . Por lo tanto, se tiene 16 casos, y para cada uno se generaron 100 particiones iniciales al azar antes de aplicar los m´etodos de particionamiento. En este experimento se puede medir el porcentaje de mala clasificaci´ on, por la forma en que se construyeron las tablas de datos. En SS se usaron los siguientes par´ ametros: χ0 = 95%, γ = 0.9, Lt = 100n(K − 1), tmax = 150, l´ımite para detener las cadenas de Markov = 10n(K − 1), y m = 4 como valor m´ aximo permitido de iteraciones que repiten el mismo valor final. La BT emple´ o los siguientes valores: |T | = 7 y tmax = nK|T |. El AG se us´ o con los siguientes par´ ametros: M = 40, pc = 0.25, pm = 0.001, tmax = M K log(n), y frecuencia para aplicar nubes din´ amicas = 10. Para ACO se emple´ o τ0 = 0.001, α = 1, β = 0.8, ρ = 0.5, M = 20, y tmax = 25. La tabla 2 muestra un resumen de los resultados de las 100 corridas para cada m´etodo. SS
BT
n
K
W
%
W
105 105 525 525
3 7 3 7
5.422 5.146 5.993 5.339
100 100 100 100
5.422 5.146 5.993 5.339
105 105 525 525
3 7 3 7
13.15 9.895 15.809 8.261
100 100 100 100
13.15 9.895 15.809 8.261
AG % W % Cardinalidades iguales
kM W
%
Ward W
Varianzas iguales 99 5.422 100 74 5.146 82 100 5.993 100 82 5.339 88
5.422 5.146 5.993 5.339
91 19 98 45
5.42 5.15 5.99 5.34
Varianzas diferentes 99 13.15 100 51 9.895 69 51 15.809 82 100 8.261 94
13.15 9.895 15.81 8.261
100 1 2 53
13.85 10.17 16.41 9.37
Cardinalidades diferentes 105 105 525 525
3 7 3 7
5.007 6.991 5.672 8.105
100 62 8 100
5.007 6.991 5.672 8.105
Varianzas iguales 100 5.007 100 1 5.545 35 100 5.672 100 1 5.648 22
5.007 5.545 5.672 5.648
91 3 95 2
5.01 5.55 5.672 5.66
105 105 525 525
3 7 3 7
11.734 8.654 13.819 8.497
100 100 3 10
11.734 8.645 13.819 8.518
Varianzas diferentes 100 11.734 100 40 7.625 37 100 13.819 100 1 7.456 21
11.734 7.625 13.819 7.456
95 6 59 2
11.86 7.69 14.2 8.0
Tabla 2: Resultados de aplicar sobrecalentamiento simulado (SS), b´ usqueda tab´ u (BT), algoritmo gen´etico (AG), k-medias (kM) y clasificaci´ on jer´ arquica de Ward en las 16 tablas de datos; se reporta en mejor valor de W y el porcentaje de veces que ese valor fue encontrado en 100 corridas.
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
Tabla de datos δsum Datos did´ acticos Universidades alemanas Datos de Pejibaye δwsm Datos did´ acticos Universidades alemanas Datos de Pejibaye
K
SS
BT
AG
12
KM
W
%
W
%
W
%
W
%
4 6 6
0.0 89.87 263.90
100% 100% 100%
0.0 89.87 263.90
100% 75% 100%
2.0
20%
744.41
10%
0.0 89.87 334.57
34% 5% 1%
4 6 6
0.0 10.72 18.19
100% 100% 100%
0.0 10.72 18.19
100% 100% 95%
0.0 10.72 25.36
40% 75% 10%
0.0 10.72 18.19
62% 12% 2%
Tabla 3: Clasificaci´ on de datos binarios usando sobrecalentamiento simulado (SS), b´ usqueda tab´ u (BT), algoritmo gen´etico (AG) y k-medias (kM). W es el mejor valor del criterio y % el porcentaje de veces que este valor ha sido encontrado en 20 aplicaciones de cada m´etodo. Con base en los resultados presentados en la tabla 2 se ve que el m´etodo de Ward tiende a obtener resultados de menor calidad que los m´etodos de particionamiento cuando las desviaciones est´ andar son diferentes: de lo contrario, sus soluciones son comparables. Cuando las cardinalidades de las clases son todas iguales, los m´etodos de particionamiento obtienen los mismos ´ optimos; sin embargo, el SS es claramente superior, con una tasa de atracci´ on del mejor valor de W del 100%. Cuando la cardinalidad de las clases es diferente y se buscan muchas clases, el SS y la BT tienen grandes dificultades, con resultados m´ as pobres que para k-medias. En este caso, el AG es claramente superior a los otros m´etodos, a´ un si no siempre encuentra el ´ optimo. Tanto por la tasa de atracci´ on como por el valor del criterio, el AG es mejor que los restantes m´etodos en este experimento. Debe hacerse notar que, a pesar de que no se reportan los tiempos, el m´etodo de k-medias es mucho m´ as r´ apido que los dem´ as, y que el m´ as lento es el BT. En promedio este u ´ltimo tard´ o unos 16 minutos por corrida, el AG 2 minutos, el SS unos 30 segundos, y el k-medias muy pocos segundos. Para el caso de datos binarios, la tabla 3 muestra los resultados de aplicaci´ on de las heur´ısticas en tres tablas de datos reales, usando los criterios δsum y δwsm , y el ´ındice de disimilitud de Jaccard. Es claro que sobrecalentamiento simulado es el mejor. Los resultados obtenidos en clasificaci´ on bimodal han sido superiores a los obtenidos por los m´etodos existentes, como intercambios alternantes y k-medias. En P la tabla 4 se muestran los resultados del mejor valor encontrado de VAF = P 1− i,j (xij −ˆ xij )2 / i,j (xij −¯ x)2 (valor a maximizar) para los distintos m´etodos empleados, con una tabla 82 × 25 sobre sanitarios, con igual n´ umero de clases por filas y columnas. Puede verse que las heur´ısticas son superiores para 4, 6 y 7 clases.
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
K=L 2 3 4 5 6 7
IA 0.2289 0.3234 0.3729 0.4293 0.4635 0.4987
kM 0.2289 0.3234 0.3729 0.4293 0.4579 0.4958
SS 0.2289 0.3234 0.3804 0.4293 0.4651 0.4990
13
BT 0.2289 0.3234 0.3804 0.4293 0.4651 0.4978
Tabla 4: Valores de VAF para datos de sanitarios usando Intercambios Alternantes (IA), k-medias (kM), Sobrecalentamiento Simulado (SS), y B´ usqueda Tab´ u (BT).
5
Conclusiones y perspectivas
Seg´ un se ha podido apreciar, las heur´ısticas de optimizaci´ on combinatoria permiten mejorar los resultados de los m´etodos tradicionales de clasificaci´ on autom´ atica. Esto es muy claro en clasificaci´ on num´erica, sobre todo para el algoritmo gen´etico y el sobrecalentamiento simulado. En el caso binario tambi´en hay una mejor´ıa en los resultados, pero comparaciones m´ as amplias deben ser hecha a´ un en el marco de un experimento. Por otro lado, en el caso bimodal tambi´en se nota una leve mejor´ıa en los resultados. Un experimento tipo Monte Carlo se est´ a llevando a cabo en este momento y ser´ a publicado pr´ oximamente. Debe notarse que las heur´ısticas necesitan de un buen generador de n´ umeros aleatorios, por lo cual el usuario debe ser cuidadoso con la escogencia del generador. Para la generaci´ on de n´ umeros seudoaleatorios, nosotros hemos empleado el m´etodo sustractivo de D. Knuth [11] y empleando la tabla de n´ umeros aleatorios de la Rand Corporation [15] para las semillas iniciales. Finalmente, se˜ nalamos que estamos trabajando actualmente —adem´ as de las experimentaciones antes citadas— en un algoritmo gen´etico para datos bimodales. Tambi´en se quiere iniciar pronto la implementaci´ on de colonias de hormigas para datos binarios, y en el uso de heur´ısticas en clasificaci´ on difusa.
Agradecimientos Deseo agradecer a mis colegas William Castillo, Alex Murillo, Alexia Pacheco y Eduardo Piza, por su colaboraci´ on en trabajos previos, que sirvieron de base para elaborar este art´ıculo.
Bibliograf´ıa [1] Aarts, E.; Korst, J. (1990) Simulated Annealing and Boltzmann Machines. Wiley, Chichester.
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
14
[2] Anderberg, M.R. (1973) Cluster Analysis for Applications. Academic Press, New York. [3] Bock, H.-H. (1974) Automatische Klassifikation. Vandenhoeck & Ruprecht, G¨ ottingen. [4] Bonabeau, E.; Dorigo, M.; Therauluz, G. (1999) Swarm Intelligence. From Natural to Artificial Systems. Oxford University Press, New York: . [5] Castillo, W.; Trejos, J. (2002) “Two-mode partitioning: review of methods and application of tabu search”, in: K. Jajuga et al. (Eds.) Classification, Clustering, and Data Analysis, Springer, Berlin: 43–51. [6] Diday, E.; Lemaire, J.; Pouget, J.; Testu, F. (1982) El´ements d’Analyse de Donn´ees. Dunod, Paris. [7] Glover, F. et al. (1993) “Tabu search: an introduction”, Annals of Operations Research 41: 1–28. [8] Goldberg, D. E. (1989) Genetic Algorithm in Search, Optimization and Machine Learning. Addison-Wesley, Reading. [9] Kennedy, J.; Eberhart, R.C. (2000) Intelligent Swarm Systems. Academic Press, New York. [10] Kirkpatrick, S.; Gelatt, D.; Vecchi, M.P. (1983) “Optimization by simulated annealing”, Science 220: 671–680. [11] Knuth, D.E. (1981) The Art of Computer Programming. Vol. 2: Seminumerical Algorithms, Segunda edici´ on. Addison-Wesley, Reading. [12] Pacheco, A. (2003) “Experimentaci´ on para la comparaci´ on de m´etodos de clasificaci´ on autom´ atica”, Preprint CIMPA. Universidad de Costa Rica, San Jos´e. [13] Piza, E.; Trejos, J.; Murillo, A. (2000) “Clustering with non-Euclidean distances using combinatorial optimisation techniques” in: J. Blasius et al. (Eds.) Science Methodology in the New Millenium, CD-Rom paper Nr.P090504, ISBN 90-801073-8-7. [14] Press, W.H.; Flannery, B.P.; Teulolsky, S.A.; Vetterling, W.T.(1990) Numerical Recipes. The Art of Scientific Computing. Cambridge University Press, New York. [15] The Rand Corporation (1955) A Million Random Digits with 100,000 Normal Deviates. The Free Press, Glencoe. [16] Sp¨ ath, H. (1985) Cluster Dissection and Analysis. Theory, Fortran programs, Examples. Ellis Horwood, Chichester.
´ n en ana ´lisis de conglomerados metaheur´ısticas de optimizacio
15
[17] Trejos, J.; Piza, E.; Murillo, A. (1998) “Global stochastic optimization techniques applied to partitioning”, in: M. Rizzi et al. (Eds.) Advances in Data Science and Classification, Springer, Berlin: 185–190. [18] Trejos, J.; Castillo, W. (2000) “Simulated annealing optimization for twomode partitioning”, in: W. Gaul & R. Decker (Eds.) Classification and Information Processing at the Turn of the Millenium Springer, Berlin: 133– 142. [19] Trejos, J.; Piza, E. (2001) “Crit`eres et heuristiques d’optimisation pour la classification de donn´ees binaires”, Journ´ees de la Soci´et´e Francophone de Classification, Guadeloupe, 17-21 Dec 2001: 331–338. [20] Trejos, J.; Goddard, J.; Cobos, S.; Piza, E. (2002) “Clasificaci´ on de datos num´ericos mediante optimizaci´ on por enjambres de part´ıculas”, 5th International Conference on Operations Research, La Habana. [21] Trejos, J.; Murillo, A.; Piza, E. (2004) “Clustering by ant colony optimization”, In: D. Banks, L. House, F.R. Mc Morris, P. Arabie & W. Gaul (Eds.) Classification, Clustering, and Data Mining Applications, Springer, Berlin: 25–32. [22] Villalobos, M. (2005) An´ alisis de Heur´ısticas de Optimizaci´ on para Problemas Multiobjetivo. Tesis de doctorado, CINVESTAV, M´exico D.F.
