Metaheurísticas de memoria adaptativa para el problema de agrupamiento

Resumen El Agrupamiento es un problema clásico de la
computación que encuentra aplicaciones en los más
diversos campos. Pertenece al área del aprendi- zaje no
supervisado que se engloba dentro del aprendizaje de
máquinas una disciplina de la inteligencia arti?cial. La
Zoni?cación por otra parte es un problema de estudios
urbanos, una disciplina asociada a la arquitec- tura. Las
Metaheurísticas de Memoria Adaptativa representan
estrategias favorables para encontrar soluciones a estos problema
debido a que desa- rrollan una búsqueda inteligente,
basada en el empleo de estructuras de memoria. En este documento
se describirán Metaheurísticas para resol- ver los
problemas de Agrupamiento clásico y de Zoni?cación,
mostrando los resultados de dichos algoritmos en conocidos
conjuntos de datos, te- niendo en cuenta medidas externas para
evaluar el agrupamiento y reali- zando comparaciones con los
resultados obtenidos por otros algoritmos.

Opinión del tutor En nuestra opinión el autor del
trabajo: Metaheurísticas de Memo- ria Adaptativa para el
Problema de Agrupamiento, del estudiante de 5to año de
Ciencias de la Computación Arnaldo Pérez
Castaño que opta por el título de Licenciado en
Ciencias de la Computación, es un excelente alumno,
dedicado y con alto grado de independencia. La tesis elaborada
por el aspirante consta de una introducción, un primer
capítulo de Prelimi- nares que cuenta con dos
epígrafes, un segundo capítulo de Algoritmos de
agrupamiento, un tercer capítulo de Búsqueda
Tabú y un último en el que se exponen los
Resultados Computacionales obtenidos y ?naliza con las
Conclusiones y trabajo futuro. El aspirante ha trabajado
arduamente en esta nueva rama de las mate- máticas y
ciencias computacionales desde sus Prácticas
Investigativas de 4to año, realizando una revisión
bibliográ?ca, así como un amplio estudio de
técnicas de memoria adaptativa y conceptos que condujeron
al aspi- rante al desarrollo de adecuaciones de un algoritmo
Tabú para la solución de problemas de
Optimización Multiobjetivo. El trabajo realizado se re?eja
en la participación en la Jornada Cien- tí?ca
ICIMAF 2013 culminando con una memoria del evento ISBN: 978-
959-7056-33-1. El aspirante demuestra tener dominio de la
materia, las adecuaciones al algoritmo son novedosas, la tesis en
tres capítulos es coherente y la literatura
cientí?ca utilizada es actual. Por las razones antes
expuestas, consideramos se le otorgue al as- pirante Arnaldo
Pérez Castaño el grado de Licenciado en Ciencias de
la Computación. 2

Introducción En la presente tesis se describen
Metaheurísticas de Memoria Adapta- tiva, cuya ?nalidad es
encontrar soluciones al Problema de Agrupamiento. Las
Metaheurísticas son métodos de optimización,
más especí?camente algoritmos de
aproximación que se apoyan en heurísticas para
dirigir la búsqueda en el espacio solución. En este
caso las Metaheurísticas es- tarán embebidas en un
marco multiobjetivo, de modo que se optimizan varias funciones al
mismo tiempo y la salida del algoritmo es la imagen del conjunto
Pareto, conocido como Frente Pareto. El Problema de Agrupamiento
(en inglés clustering) consiste en par- ticionar un
conjunto de n objetos en k grupos de modo tal que objetos de un
mismo grupo tengan la mayor similitud posible y objetos en gru-
pos distintos posean la mayor disimilitud posible. La medida de
similitud puede de?nirse de varias formas, usualmente se piensa
en la distancia euclidiana, pero en general cualquier medida
puede ser válida y depender del contexto del problema.
Como problema forma parte de la clase de complejidad NP-completo
y puede verse dentro del campo de la optimización
combinatoria. Los al- goritmos de agrupamiento forman parte de la
inteligencia arti?cial, más especí?camente de una
de sus ramas conocida como aprendizaje de má- quinas que
se divide en dos grupos: los algoritmos de aprendizaje no 6

supervisado y los de aprendizaje supervisado. El Agrupamiento es
una técnica del aprendizaje no supervisado, esto se
traduce en que no requie- ren de un conjunto de datos inicial
para entrenarse o aprender, de modo que predicen la clase de un
nuevo dato sin requerir una primera fase de entrenamiento. El
Agrupamiento es un problema clásico de la
computación que en- cuentra aplicaciones en las más
diversas áreas de la ciencia como pueden ser la
Minería de Datos, el procesamiento de lenguajes naturales,
la teoría de señales, la recuperación de
información o el análisis de la formación de
galaxias. Su gran utilidad en diversos campos de la ciencia y la
importancia de las Metaheurísticas como métodos
para brindar soluciones a problemas complejos de?nen la
motivación principal de esta tesis. Las
Metaheurísticas de Memoria Adaptativa brindan soluciones
satis- factorias al Problema de Agrupamiento. Esta es la
hipótesis que se plantea en el presente trabajo. De esta
forma los objetivos fundamentales de esta tesis serían,
pri- mero, desarrollar algoritmos de Memoria Adaptativa que
resuelvan satisfactoriamente Problemas de Optimización
Multiobjetivo, en par- ticular el Problema de Agrupamiento.
Además se propone como ob- jetivo la comparación de
los resultados obtenidos con algoritmos del estado del arte,
aunque NO constituya un objetivo de la presente te- sis la
obtención de resultados competitivos con los del estado
del arte. Primeramente se dedicará un primer
capítulo a presentar de?niciones que resultan
indispensables para comprender el contenido de esta tesis. En el
segundo capítulo se examinan un grupo de algoritmos
tradicionales 7

que brindan soluciones al Problema de Agrupamiento. En tanto el
tercer capítulo estará dedicado a describir una
importante Metaheurística de Me- moria Adaptativa: la
Búsqueda Tabú. Además se presentarán
dos algorit- mos de este tipo, uno que brinda soluciones al
Problema de Agrupamiento clásico y el otro al problema de
Zoni?cación. El cuarto capítulo presentará
resultados computacionales de los algoritmos descritos en el
capítulo an- terior, realizando comparaciones. Finalmente,
se darán las conclusiones y las recomendaciones para
trabajo futuro. 8

Capítulo 1 Preliminares 1.1. Teoría y de?niciones A
continuación se brindan algunas de?niciones que resultan
imprescin- dibles para comprender el funcionamiento de los
algoritmos que se des- criben en este documento. De?nición
1.1.1 (Problema de optimización multiobjetivo) Un problema
de optimización multiobjetivo se puede formular como: min
F (x) = (f1 (x), f2 (x), …, fq (x)) sujeto a X ? S donde S
representa el espacio factible. De?nición 1.1.2 (Dominado)
Se dice que un vector v = (v1 , v2 , …, vn ) do- mina a otro
vector u = (u1 , u2 , …, un ) si y solo si se cumple ui = vi y
?i tal que ui < vi . De?nición 1.1.3 (Pareto
óptimo) Una solución factible x se dice que es
Pareto óptima si y solo si ?y tal que F (y) domine a F
(x). 9

* * * * * * * * De?nición 1.1.4 (Conjunto Pareto) Es el
conjunto de soluciones Pareto óptimo, que se
denominará P . De?nición 1.1.5 (Frente Pareto) Se
de?ne como la imagen de P , que se denominará F .
De?nición 1.1.6 (PSET) Es la herramienta encargada de
mantener y ac- tualizar F . De?nición 1.1.7 (Vector Nadir)
Un punto y* = (y1 , y2 , …, yq ) es Nadir si yi = max(fi (x))
con x ? P . De?nición 1.1.8 (Vector Ideal) Un punto y* =
(y1 , y2 , …, yq ) es Ideal si yi = min(fi (x)) con x ? P .
De?nición 1.1.9 (Punto de referencia) Un punto de
referencia es un vec- tor z = (z1 , z2 , …, zq ) que de?ne el
nivel de aspiración que se desea alcan- zar en cada
función objetivo fi . El vector ideal es casi imposible de
alcanzar en la mayoría de los pro- blemas de la vida real,
así que muchas veces se emplea el punto de refe- rencia
para determinar cuando una solución Pareto óptima
es aceptable. El punto ideal y el Nadir brindan
información acerca de los rangos del Frente Pareto. La
siguiente de?nición está estrechamente vinculada
con Metaheurís- ticas de búsqueda que de?nen una
estructura de vecindad. De?nición 1.1.10 (Pareto
óptimo local) Una solución x es Pareto
óptima local si y solo si ?y ? N (x), F (x) domina a F
(y), donde N (x) representa la vecindad de x. 10

Figura 1.1: Punto ideal y Nadir para un caso bi-objetivo. 1.2.
Optimización multiobjetivo La optimización
multiobjetivo tiene sus inicios en el siglo XIX en los trabajos
de economía de Edgeworth y Pareto. Comenzó siendo
utilizada en este campo y gradualmente ha pasado a ser vital en
la ingeniería y en diferentes ciencias. Encuentra diversas
aplicaciones ya que se ajusta a problemas de la vida real donde
deben tenerse en cuenta varios objetivos que están en
con?icto. Por ejemplo, si se quisiera encontrar un terreno para
empezar un negocio se debería intentar minimizar el costo
y maximi- zar la calidad del terreno, basar la elección de
acuerdo a solo uno de los criterios anteriores puede resultar en
un terreno muy barato pero de poca calidad o en un terreno bueno
pero extremadamente caro. Aquí aparece el rol del decisor,
quien es el encargado de decidir, de todas las soluciones,
aquella que va de acuerdo a sus necesidades. Las
Metaheurísticas multiobjetivo comenzaron a ser ampliamente
in- vestigadas a ?nales de los 80s del siglo pasado, en un
interés por resolver complejos problemas multiobjetivo. La
solución de un problema multiob- jetivo generalmente no se
reduce a una única solución sino a un conjunto
11

de soluciones Pareto óptimas que de?nen el Frente Pareto.
El objetivo de una Metaheurística multiobjetivo es obtener
una aproximación del Frente Pareto que cumpla las
siguientes dos propiedades: Convergencia: garantiza soluciones
que brindan una buena aproxi- mación al Frente Pareto
óptimo. Uniformidad: garantiza una buena
distribución de las soluciones ob- tenidas a lo largo del
Frente Pareto óptimo evitando la pérdida de
información valiosa. Un aspecto ?nal de un PMO resulta la
etapa del decisor quien es el encargado de decidir ?nalmente, del
conjunto Pareto, cuales serán las so- luciones que se
ajusten a sus intereses. Los PMOs se dividen en dos ca-
tegorías fundamentales: los continuos y los combinatorios.
Los primeros tratan con soluciones codi?cadas con variables
continuas mientras que los segundos cuentan solo con variables
que toman valores discretos. La gran mayoría de los
trabajos realizados desde hace más de 40 años per-
tenecen a los continuos. 12

Capítulo 2 Algoritmos de agrupamiento En este
capítulo se describen algunos de los más populares
algoritmos de agrupamiento. El conocimiento de dichos algoritmos
resulta indispen- sable para abordar el estudio del Problema de
Agrupamiento y se dividen en dos grupos que se verán en
secciones continuas, estos son: los de particionamiento y los
jerárquicos. 2.1. Algoritmos de particionamiento El
objetivo que persiguen los algoritmos de particionamiento, es
pre- cisamente obtener una partición de un conjunto de
datos en k grupos o clases de manera que se maximice o minimice
una determinada función objetivo. Hallar la
partición óptima siempre sería posible si se
enumeran todas las posibles particiones, pero esto resulta
completamente infacti- ble para una computadora, debido a su
costo temporal exponencial. Por ejemplo, para un problema de 30
objetos, con 3 particiones, el número de particiones
posibles es de aproximadamente 2 * 1014 , haciendo indis-
pensable el uso de algoritmos que empleen heurísticas para
encontrar 13

soluciones aproximadas al óptimo. 2.1.1. K-Medias El
K-Medias es uno de los más populares algoritmos de
agrupamiento, considerado por muchos como elemental debido a su
fácil implementa- ción. Intenta llegar a una
partición óptima minimizando la suma de errores
cuadrados, con un procedimiento iterativo, semejante a una
búsqueda lo- cal. Ofrece buenos resultados cuando los
grupos resultantes son compac- tos y tienen la forma de una
hiperesfera, además la complejidad compu- tacional es
aproximadamente lineal lo cual lo convierte en una buena op-
ción para agrupar grandes conjuntos de datos. A pesar de
las ventajas mencionadas, K-means padece de problemas heredados
de la búsqueda local, uno de estos problemas es la
necesidad de de?nir la cantidad de particiones a priori, algo
poco común en problemas de la vida real. El al- goritmo se
puede resumir en los siguientes pasos. 1. Inicializar una
k-partición de manera aleatoria, de?niendo los k cen-
troides. 2. Asignar cada objeto al grupo cuyo centroide resulta
ser el más cer- cano. 3. Recalcula los centroides basado
en: mi = 1 Ni xj ?Ci xj donde Ci es el grupo del centroide mi .
4. Repetir pasos 2 y 3 hasta que ningún grupo cambie.
14

La condición de parada no tiene que ser precisamente que
ningún grupo cambie, pudiera ser que se ha alcanzado un
número pre?jado de iteraciones, que ningún
centroide ha cambiado o que se ha logrado un valor de la
distancia intra-clase que supere un umbral pre?jado. 2.2.
Algoritmos jerárquicos Los algoritmos jerárquicos
agrupan los objetos como una secuencia de particiones anidadas.
Los resultados del agrupamiento jerárquico son usualmente
representados por un árbol binario o dendograma. La
raíz del dendograma representa todo el conjunto de objetos
mientras que cada hoja representa uno de esos objetos. Por tanto,
los nodos intermedios des- criben la proximidad entre objetos y
la altura del árbol expresa la distancia entre cada par de
objetos, entre grupos o entre un grupo y un objeto. En la ?gura
2.1 se muestra un dendograma. La dirección del
agrupamiento aglomerativo jerárquico es de abajo hacia
arriba, mientras que la del divi- sivo jerárquico es en el
sentido contrario. Figura 2.1: Ejemplo de dendograma. 15

Existen varias formas de lograr un agrupamiento, una estrategia
se- ría comenzar con tantos grupos como objetos (un objeto
por grupo) hasta llegar a obtener un grupo con todos los objetos,
otra estrategia, sería co- menzar con todos los objetos en
un grupo hasta llegar a tener un grupo por cada objeto. Estas
estrategias reciben el nombre de aglomerativas y divisivas
respectivamente. La crítica común a los algoritmos
de agrupamiento jerárquico es su costo temporal, nunca
inferior a O(N 2 ), que representa una limitante para
aplicaciones de gran escala. Los métodos divisivos
requieren considerar 2N -1 – 1 posibles divisiones de dos
subconjuntos para un grupo con N objetos lo cual es muy costoso
computacionalmente, por este motivo los métodos
aglomerativos son más utilizados, ellos son analizados a
conti- nuación. 2.2.1. Aglomerativo general El
agrupamiento aglomerativo comienza con N grupos, uno por ob-
jeto, luego se realiza una serie de operaciones de mezcla hasta
llegar a un grupo incluyendo todos los objetos. El procedimiento
se resume a continuación. Para decidir cuales son los dos
grupos más cercanos existen diferentes medidas.
Seguidamente se describen algunas de ellas. 2.2.2. Medidas de
distancia entre grupos La mezcla de grupos depende de?nitivamente
de la medida utilizada para determinar la distancia entre grupos.
Un gran número de estas me- didas se ven generalizadas en
la fórmula de recurrencia propuesta por 16

Algoritmo 1: Aglomerativo general 1. Comienza con N grupos
simples (de un solo elemento). Calcula la distancia entre todo
par de grupos. 2. Encuentra los dos grupos Ci ,Cj más
cercanos y combinálos en un nuevo grupo Ci,j . 3. Repite
el paso anterior hasta que solo quede un grupo. Lance, Williams
(1967) y que posee la siguiente forma: D(Cl , (Ci , Cj )) = ai
D(Cl , Ci ) + aj D(Cl , Cj ) + ßD(Ci , Cj ) +?|D(Cl , Ci )
– D(Cl , Cj )| donde D es la función de distancia y a,
ß, ? son parámetros que toman valores en dependencia
del esquema utilizado. A continuación se mostra-
rán algunos esquemas: Enlace simple: la distancia entre
dos grupos esta dada por la dis- tancia entre los dos objetos
más cercanos de cada grupo. Cambien llamado método
del vecino más cercano. D(Cl , (Ci , Cj )) = min(D(Cl , Ci
), D(Cl , Cj )) En este caso los parámetros de la
fórmula general toman valores: a = 1/2, ß = 0, ? =
-1/2. Efectivo si los grupos están separados entre
sí. Enlace completo: utiliza la distancia máxima
entre un par de objetos de grupos diferentes para de?nir la
distancia entre grupos. D(Cl , (Ci , Cj )) = max(D(Cl , Ci ),
D(Cl , Cj )) 17

Efectivo en descubrir pequeños y compactos grupos. Enlace
promedio de grupo: la distancia entre grupos se de?ne como el
promedio de la distancia entre cada par de objetos donde cada uno
pertenece a un grupo distinto. 1 D(Cl , (Ci , Cj )) = (D(Cl , Ci
), D(Cl , Cj )) 2 Enlace de centroides: dos grupos son mezclados
dependiendo de la distancia entre sus centroides de?nida como: mi
= 1 ni x?Ci x donde ni es el número de objetos en el grupo
i. La fórmula general para este caso adopta la forma: D(Cl
, (Ci , Cj )) = ni ni + nj D(Cl , Ci )+ nj ni + nj D(Cl , Cj ) –
ni nj (ni + nj )2 D(Ci , Cj ) Lo cual es equivalente a la
distancia Euclidiana entre los centroides de dos grupos: D(Cl ,
(Ci , Cj )) = ||ml – mi,j ||2 2.2.3. Divisivo jerárquico
El agrupamiento divisivo procede de forma opuesta al
aglomerativo. En un principio todos los objetos pertenecen a un
mismo grupo y sucesi- vamente se van dividiendo hasta que existan
tantos grupos como objetos, o sea, un grupo por objeto. 18

Para un conjunto de N objetos, un algoritmo de este tipo comenza-
ría considerando las 2N -1 – 1 posibles divisiones de los
objetos en dos subconjuntos no vacíos, lo cual posee un
alto costo computacional, por lo cual el agrupamiento divisivo es
realmente poco utilizado en la prác- tica. Aún
así brinda una clara visión de la estructura de los
objetos, dado que los grupos más grandes son generados en
fases iniciales del proceso de agrupamiento y son menos propensos
a sufrir de decisiones erróneas acumuladas, que una vez
cometidas son arrastradas a lo largo del pro- ceso. Uno de los
métodos para resolver el agrupamiento divisivo es un algo-
ritmo heurístico conocido como DIANA (DIvisive ANAlysis)
que solo con- sidera una parte de todas las posibles divisiones.
El grupo con el máximo diámetro es seleccionado
para ser dividido. Suponiendo que el grupo Cl será
dividido en los grupos Ci y Cj los pasos de DIANA se pueden
apreciar en el algoritmo 2. Entre las críticas que suelen
apuntarse de los algoritmos divisivos clá- sicos
está su alta sensibilidad ante el ruido, que se traduce en
la presen- cia de errores en los datos debido a diferentes
factores en las etapas de medición, almacenamiento y
procesamiento, que no son manejados ade- cuadamente por los
algoritmos divisivos, y que afectan la forma de los grupos,
además de distorsionar el algoritmo. Una vez que un objeto
es asignado a un grupo no se le vuelve a considerar, lo cual
signi?ca que no es posible corregir una mala clasi?cación.
19

Algoritmo 2: DIANA 1. Ci = Cl y Cj = Ø. 2. Para cada
objeto xm ? Ci a) Para la primera iteración calcula su
distancia promedio hacia todos los objetos. d(xm , Ci {xm }) =
1 Nci -1 xp ?Ci ,p=m d(xm , xp ) b) Para las iteraciones
restantes calcula la diferencia entre la distancia promedio a Ci
y la distancia promedio a Cj : d(xm , Ci {xm }) – d(xm , Cj ) =
1 Nci -1 xp ?Ci ,p=m d(xm , xp ) – 1 Ncj xq ?Cj d(xm , xq ) 3. a)
Para la primera iteración mueve el objeto con
máximo valor según 2 hacia Cj . b) Para las
iteraciones restantes, si el máximo valor de 2b) es mayor
que 0, mueve el objeto con la máxima diferencia a Cj .
Repite 2b) y 3b). En caso contrario para. 2.3. Medidas de
similitud En el agrupamiento, la función objetivo resulta
fundamental para ob- tener una solución óptima. Es
esta función la encargada de evaluar la homogeneidad de
los elementos dentro de cada grupo o de evaluar lo diferentes que
son los grupos entre sí. 20

i 2.3.1. Intra-clase Una de las funciones más utilizadas
es la suma de los errores cua- drados en ocasiones llamada
distancia intra-clase. La idea detrás de esta
función es minimizar la diferencia o error que existe en
similitud entre cada elemento de un grupo y el centroide o
representante de ese grupo. El cen- troide se calcula como el
vector promedio: mi = 1 |Ci | x?C x La distancia intra-clase se
puede formular como: Intra = k n ai,j ||xj – mi ||2 i=1 j=1 donde
mi representa el centroide del i-ésimo grupo y ai,j es una
varia- ble binaria que toma valor 1 solo si xj se encuentra en el
i-ésimo grupo, además k i=1 ai,j = 1, ?j. La
partición que minimice la suma de los errores cuadrados se
considera óptima. 2.3.2. Inter-clase Otra función
de similitud ampliamente difundida es la inter-clase, que tiene
como premisa fundamental garantizar que la distancia entre los
gru- pos sea la mayor posible, con el objetivo de que objetos en
grupos dis- tintos tengan la mayor disimilitud. La idea es
maximizar su valor y puede formularse como: Inter = k k d(mi , mj
) i=1 j=i+1 donde d es una función que mide la distancia
entre mi y mj , ambos centroides. 21

2.4. 2.3.3. Diámetro El diámetro se de?ne sobre un
grupo C y mide la distancia máxima entre dos elementos del
mismo. Se puede formular como: D = max d(xi , xj ) xi ? C, xj ? C
2.3.4. Radio Se de?ne para un grupo C, mide la distancia
mínima de las máximas distancias de un elemento a
los restantes. Se puede formular como: Radio = min (maxxj ?C d(xj
, xk )) ?xk ? C Medidas para evaluar el agrupamiento Una
cuestión de vital importancia es la calidad del
agrupamiento brin- dado por un algoritmo. Para alcanzar una
evaluación del mismo se han creado diferentes medidas que
determinan la calidad del agrupamiento. En esta sección, X
se re?ere al conjunto de datos y C al agrupamiento ofrecido por
un determinado algoritmo. A continuación se describen
algu- nas de estas medidas. 2.4.1. Medidas internas Las medidas o
criterios internos evalúan la estructura del agrupamiento
exclusivamente desde X, sin ninguna información externa.
Para llegar a una evaluación utilizarían, por
ejemplo, la matriz de similitud para evaluar la validez de C.
22

2 s2 q Las medidas internas al igual que las externas (que
serán introduci- das en la siguiente sección)
están fuertemente relacionadas con métodos
estadísticos, pruebas de hipótesis. El Coe?ciente
de Correlación Copenético (CCC) es un índice
empleado para validar estructuras de agrupamiento
jerárquico. Dada la matriz de si- militud S de X. El CCC
mide el grado de similitud entre S y la matriz copenética
Q, cuyos elementos almacenan el nivel de proximidad donde pares
de objetos son agrupados en el mismo grupo por primera vez. Sean
µs y µq las medias de S y Q respectivamente. µs
= µq = 1 M 1 M N -1 N i=1 i=j+1 N -1 N i=1 i=j+1 si,j qi,j
donde M = N (N – 1)/2, CCC se de?ne como: CCC = 1 ( M N -1 i=1 1
M N -1 N i=1 i=j+1 si,j qi,j – µs µq N 1 N -1 N i=j+1
si,j – µ2 )( M i=1 i=j+1 qi,j – µ2 ) El valor de CCC
se encuentra en el intervalo [-1, 1] y un valor cercano a 1
determina una alta similitud entre S y Q. 2.4.2. Medidas externas
Si P es una partición especi?cada a priori para X tal que
|X| = N , entonces la evaluación externa de C se consigue
comparando C con P . Considerando un par de puntos xi , xj ? X,
existen 4 casos de como pu- dieran estar ubicados en C y en P .
1. xi , xj pertenecen al mismo grupo en C y a la misma clase en P
. 23

Figura 2.2: Ejemplo de una partición especi?cada a priori
P y un agrupa- miento C, brindado por el algoritmo. 2. xi , xj
pertenecen al mismo grupo en C y a distinta clase en P . 3. xi ,
xj pertenecen a distinto grupo en C y a la misma clase en P . 4.
xi , xj pertenecen a distinto grupo en C y a distinta clase en P
. En la ?gura 2.2 se puede apreciar un ejemplo donde se ponen en
evi- dencia estos 4 casos. La Tabla 2.1 analiza dichos casos.
Casos 1 2 3 4 Pares de puntos (x1 , x3 ); (x2 , x5 ) (x1 , x4 );
(x3 , x4 ); (x6 , x7 ) (x1 , x6 ); (x2 , x4 ); (x2 , x7 ); (x3 ,
x6 ) (x4 , x5 ); (x4 , x7 ); (x5 , x7 ) (x1 , x2 ); (x1 , x5 );
(x1 , x7 ); (x2 , x3 ); (x2 , x6 ) (x3 , x5 ); (x3 , x7 ); (x4 ,
x6 ); (x5 , x6 ) Tabla 2.1: Análisis del ejemplo 3.1. 24
Total 2 3 7 9

El número de pares de puntos para los cuatro casos se
denotan como a, b, c, d. Como el número total de puntos es
M = N (N – 1)/2, se tiene M = a + b + c + d. Algunos
índices externos que frecuentemente son utilizados para
me- dir la similitud entre C y P se describen a
continuación. 1. Rand Index: 2. Coe?ciente de Jaccard: R =
a + d M J = a (a + b + c) Como puede apreciarse en la
de?nición, los valores de estas medidas están en el
intervalo [0, 1], para valores cercanos a 1 mayor será la
similitud entre P y C. 25