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