Algoritmo de cadena del vecino más cercano

Método basado en pila para agrupación

En la teoría del análisis de conglomerados , el algoritmo de la cadena del vecino más cercano es un algoritmo que puede acelerar varios métodos de agrupamiento jerárquico aglomerativo . Estos son métodos que toman una colección de puntos como entrada y crean una jerarquía de grupos de puntos fusionando repetidamente pares de grupos más pequeños para formar grupos más grandes. Los métodos de agrupación para los que se puede utilizar el algoritmo de cadena del vecino más cercano incluyen el método de Ward , la agrupación de enlace completo y la agrupación de enlace único ; Todos estos funcionan fusionando repetidamente los dos grupos más cercanos, pero utilizan diferentes definiciones de la distancia entre los grupos. Las distancias de conglomerado para las que funciona el algoritmo de cadena del vecino más cercano se denominan reducibles y se caracterizan por una simple desigualdad entre ciertas distancias de conglomerado.

La idea principal del algoritmo es encontrar pares de grupos para fusionar siguiendo rutas en el gráfico vecino más cercano de los grupos. Cada uno de estos caminos eventualmente terminará en un par de clústeres que son vecinos más cercanos entre sí, y el algoritmo elige ese par de clústeres como el par a fusionar. Para ahorrar trabajo reutilizando la mayor cantidad posible de cada ruta, el algoritmo utiliza una estructura de datos de pila para realizar un seguimiento de cada ruta que sigue. Al seguir rutas de esta manera, el algoritmo de la cadena del vecino más cercano fusiona sus clústeres en un orden diferente al de los métodos que siempre encuentran y fusionan el par de clústeres más cercano. Sin embargo, a pesar de esa diferencia, siempre genera la misma jerarquía de clusters.

El algoritmo de la cadena del vecino más cercano construye una agrupación en el tiempo proporcional al cuadrado del número de puntos a agrupar. Esto también es proporcional al tamaño de su entrada, cuando la entrada se proporciona en forma de una matriz de distancia explícita . El algoritmo utiliza una cantidad de memoria proporcional al número de puntos, cuando se utiliza para métodos de agrupamiento como el método de Ward que permiten el cálculo en tiempo constante de la distancia entre grupos. Sin embargo, para algunos otros métodos de agrupación, utiliza una mayor cantidad de memoria en una estructura de datos auxiliar con la que realiza un seguimiento de las distancias entre pares de agrupaciones.

Fondo

Una agrupación jerárquica de seis puntos. Los puntos que se agruparán se encuentran en la parte superior del diagrama y los nodos debajo de ellos representan grupos.

Muchos problemas en el análisis de datos tienen que ver con la agrupación de elementos de datos en grupos de elementos estrechamente relacionados. La agrupación jerárquica es una versión del análisis de conglomerados en la que los conglomerados forman una jerarquía o estructura similar a un árbol en lugar de una partición estricta de los elementos de datos. En algunos casos, este tipo de agrupamiento se puede realizar como una forma de realizar análisis de conglomerados en múltiples escalas diferentes simultáneamente. En otros, los datos a analizar tienen naturalmente una estructura de árbol desconocida y el objetivo es recuperar esa estructura realizando el análisis. Ambos tipos de análisis pueden verse, por ejemplo, en la aplicación del agrupamiento jerárquico a la taxonomía biológica . En esta aplicación, diferentes seres vivos se agrupan en grupos en diferentes escalas o niveles de similitud ( especie, género, familia, etc. ). Este análisis proporciona simultáneamente una agrupación a múltiples escalas de los organismos de la era actual y tiene como objetivo reconstruir con precisión el proceso de ramificación o árbol evolutivo que en épocas pasadas produjo estos organismos. ^[1]

La entrada a un problema de agrupamiento consta de un conjunto de puntos. ^[2] Un grupo es cualquier subconjunto adecuado de puntos, y un agrupamiento jerárquico es una familia máxima de grupos con la propiedad de que dos grupos cualesquiera de la familia están anidados o son disjuntos . Alternativamente, una agrupación jerárquica puede representarse como un árbol binario con los puntos en sus hojas; los grupos de la agrupación son los conjuntos de puntos en subárboles que descienden de cada nodo del árbol. ^[3]

En los métodos de agrupamiento aglomerativo, la entrada también incluye una función de distancia definida en los puntos, o una medida numérica de su disimilitud. La distancia o disimilitud debe ser simétrica: la distancia entre dos puntos no depende de cuál de ellos se considere primero. Sin embargo, a diferencia de las distancias en un espacio métrico , no es necesario satisfacer la desigualdad del triángulo . ^[2] A continuación, la función de disimilitud se extiende desde pares de puntos hasta pares de conglomerados. Los diferentes métodos de agrupación realizan esta extensión de diferentes maneras. Por ejemplo, en el método de agrupación de enlace único , la distancia entre dos grupos se define como la distancia mínima entre dos puntos cualesquiera de cada grupo. Dada esta distancia entre grupos, una agrupación jerárquica puede definirse mediante un algoritmo codicioso que inicialmente coloca cada punto en su propio grupo de un solo punto y luego forma repetidamente un nuevo grupo fusionando el par de grupos más cercano. ^[2]

El cuello de botella de este algoritmo codicioso es el subproblema de encontrar qué dos grupos fusionar en cada paso. Los métodos conocidos para encontrar repetidamente el par de conglomerados más cercano en un conjunto dinámico de conglomerados requieren un espacio superlineal para mantener una estructura de datos que pueda encontrar los pares más cercanos rápidamente, o requieren más tiempo que el lineal para encontrar cada par más cercano. ^{[4] [5]} El algoritmo de cadena del vecino más cercano utiliza una cantidad menor de tiempo y espacio que el algoritmo codicioso al fusionar pares de clústeres en un orden diferente. De esta forma, se evita el problema de encontrar repetidamente pares más cercanos. Sin embargo, para muchos tipos de problemas de agrupamiento, se puede garantizar que se obtendrá el mismo agrupamiento jerárquico que el algoritmo codicioso a pesar del diferente orden de fusión. ^[2]

el algoritmo

Animación del algoritmo utilizando la distancia de Ward. Los puntos negros son puntos, las regiones grises son grupos más grandes, las flechas azules apuntan a los vecinos más cercanos y la barra roja indica la cadena actual. Para simplificar visualmente, cuando una fusión deja la cadena vacía, continúa con el clúster recientemente fusionado.

Intuitivamente, el algoritmo de cadena de vecinos más cercanos sigue repetidamente una cadena de clusters A → B → C → ... donde cada cluster es el vecino más cercano del anterior, hasta llegar a un par de clusters que son vecinos más cercanos entre sí. ^[2]

Con más detalle, el algoritmo realiza los siguientes pasos: ^{[2] [6]}

• Inicialice el conjunto de clústeres activos para que esté formado por n clústeres de un punto, uno para cada punto de entrada.
• Sea S una estructura de datos de pila , inicialmente vacía, cuyos elementos serán clústeres activos.
• Si bien hay más de un clúster en el conjunto de clústeres:
  • Si S está vacío, elija un grupo activo arbitrariamente y empújelo hacia S.
  • Sea C el grupo activo en la parte superior de S. Calcule las distancias desde C a todos los demás grupos y sea D el otro grupo más cercano.
  • Si D ya está en S , debe ser el predecesor inmediato de C . Extraiga ambos grupos de S y combínelos.
  • De lo contrario, si D aún no está en S , empújelo hacia S .

Cuando es posible que un grupo tenga varios vecinos más cercanos iguales, entonces el algoritmo requiere una regla de desempate consistente. Por ejemplo, se pueden asignar números de índice arbitrarios a todos los grupos y luego seleccionar (entre los vecinos más cercanos iguales) el que tiene el número de índice más pequeño. Esta regla previene ciertos tipos de comportamiento inconsistente en el algoritmo; por ejemplo, sin tal regla, el grupo vecino D podría aparecer antes en la pila que como predecesor de C. ^[7]

Análisis de tiempo y espacio.

Cada iteración del bucle realiza una única búsqueda del vecino más cercano de un clúster y agrega un clúster a la pila o elimina dos clústeres. Cada clúster solo se agrega una vez a la pila, porque cuando se elimina nuevamente, inmediatamente se vuelve inactivo y se fusiona. Hay un total de 2 n − 2 clusters que alguna vez se agregan a la pila: n clusters de un solo punto en el conjunto inicial y n − 2 nodos internos distintos de la raíz en el árbol binario que representa el clustering. Por lo tanto, el algoritmo realiza 2 n − 2 iteraciones de empuje y n − 1 iteraciones de popping. ^[2]

Cada una de estas iteraciones puede dedicar tiempo a escanear hasta n − 1 distancias entre grupos para encontrar el vecino más cercano. Por tanto, el número total de cálculos de distancia que realiza es inferior a 3 n ² . Por la misma razón, el tiempo total utilizado por el algoritmo fuera de estos cálculos de distancia es O( n ² ) . ^[2]

Dado que la única estructura de datos es el conjunto de clústeres activos y la pila que contiene un subconjunto de los clústeres activos, el espacio requerido es lineal en el número de puntos de entrada. ^[2]

Exactitud

Para que el algoritmo sea correcto, debe darse el caso de que al extraer y fusionar los dos grupos superiores de la pila del algoritmo se conserve la propiedad de que los grupos restantes de la pila formen una cadena de vecinos más cercanos. Además, debería darse el caso de que todos los clusters producidos durante el algoritmo sean los mismos que los clusters producidos por un algoritmo codicioso que siempre fusiona los dos clusters más cercanos, aunque el algoritmo codicioso en general realizará sus fusiones en un orden diferente. que el algoritmo de la cadena del vecino más cercano. Ambas propiedades dependen de la elección específica de cómo medir la distancia entre los grupos. ^[2]

La exactitud de este algoritmo depende de una propiedad de su función de distancia llamada reducibilidad . Esta propiedad fue identificada por Bruynooghe (1977) en relación con un método de agrupamiento anterior que utilizaba pares mutuos de vecinos más cercanos pero no cadenas de vecinos más cercanos. ^[8] Una función de distancia d en conglomerados se define como reducible si, por cada tres conglomerados A , B y C en la agrupación jerárquica codiciosa tal que A y B son vecinos más cercanos entre sí, se cumple la siguiente desigualdad: ^[2]

re ( A ∪ B , C ) ≥ min(d( A , C ), d( B , C )) .

Si una función de distancia tiene la propiedad de reducibilidad, entonces fusionar dos grupos C y D solo puede hacer que el vecino más cercano de E cambie si ese vecino más cercano era uno de C y D. Esto tiene dos consecuencias importantes para el algoritmo de la cadena vecina más cercana. Primero, se puede demostrar usando esta propiedad que, en cada paso del algoritmo, los clusters en la pila S forman una cadena válida de vecinos más cercanos, porque cada vez que un vecino más cercano queda invalidado, se elimina inmediatamente de la pila. ^[2]

En segundo lugar, y aún más importante, de esta propiedad se deduce que, si dos grupos C y D pertenecen al agrupamiento jerárquico codicioso y son vecinos mutuos más cercanos en cualquier momento, entonces serán fusionados por el agrupamiento codicioso, por deben seguir siendo vecinos mutuos más cercanos hasta que se fusionen. De ello se deduce que cada par mutuo de vecinos más cercanos encontrado por el algoritmo de la cadena de vecinos más cercanos es también un par de clústeres encontrados por el algoritmo codicioso y, por lo tanto, que el algoritmo de la cadena de vecinos más cercanos calcula exactamente el mismo agrupamiento (aunque en un orden diferente) que el algoritmo codicioso. algoritmo. ^[2]

Aplicación a distancias de agrupamiento específicas

El método de Ward.

El método de Ward es un método de agrupamiento aglomerativo en el que la disimilitud entre dos grupos A y B se mide por la cantidad en la que fusionar los dos grupos en un solo grupo más grande aumentaría la distancia promedio al cuadrado de un punto a su centroide de grupo . ^[9] Es decir,

${\displaystyle d(A,B)=\sum _{x\in A,y\in B}{\frac {d^{2}(x,y)}{|A|+|B|}}-\sum _{x,y\in A}{\frac {d^{2}(x,y)}{|A|}}-\sum _{x,y\in B}{\frac {d^{2}(x,y)}{|B|}}.}$

Expresado en términos del centroide y cardinalidad de los dos grupos, tiene la fórmula más simple ${\displaystyle c_{A}}$ ${\displaystyle n_{A}}$

${\displaystyle d(A,B)={\frac {d^{2}(c_{a},c_{b})}{1/n_{A}+1/n_{B}}},}$

permitiendo que se calcule en tiempo constante por cálculo de distancia. Aunque es muy sensible a los valores atípicos , el método de Ward es la variación más popular del agrupamiento aglomerativo tanto por la forma redonda de los grupos que normalmente forma como por su definición de principios como el agrupamiento que en cada paso tiene la variación más pequeña dentro de sus grupos. ^[10] Alternativamente, esta distancia puede verse como la diferencia en el costo de k-medias entre el nuevo grupo y los dos antiguos.

La distancia de Ward también es reducible, como se puede ver más fácilmente en una fórmula diferente para calcular la distancia de un grupo fusionado a partir de las distancias de los grupos de los que se fusionó: ^{[9] [11]}

${\displaystyle d(A\cup B,C)={\frac {n_{A}+n_{C}}{n_{A}+n_{B}+n_{C}}}d(A,C)+{\frac {n_{B}+n_{C}}{n_{A}+n_{B}+n_{C}}}d(B,C)-{\frac {n_{C}}{n_{A}+n_{B}+n_{C}}}d(A,B).}$

Las fórmulas de actualización de distancia como ésta se denominan fórmulas "del tipo Lance-Williams" en honor al trabajo de Lance y Williams (1967). Si es la más pequeña de las tres distancias en el lado derecho (como sería necesariamente cierto si y son vecinos más cercanos entre sí), entonces la contribución negativa de su término se cancela por el coeficiente de uno de los otros dos términos, dejando una distancia positiva. valor añadido a la media ponderada de las otras dos distancias. Por lo tanto, la distancia combinada es siempre al menos tan grande como el mínimo de y , cumpliendo con la definición de reducibilidad. ${\displaystyle d(A,B)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n_{C}}$ ${\displaystyle d(A,C)}$ ${\displaystyle d(B,C)}$

Debido a que la distancia de Ward es reducible, el algoritmo de cadena del vecino más cercano que utiliza la distancia de Ward calcula exactamente la misma agrupación que el algoritmo codicioso estándar. Para n puntos en un espacio euclidiano de dimensión constante, se necesita tiempo O ( n ² ) y espacio O ( n ) . ^[6]

Enlace completo y distancia media.

La agrupación de enlace completo o del vecino más lejano es una forma de agrupación aglomerativa que define la disimilitud entre grupos como la distancia máxima entre dos puntos cualesquiera de los dos grupos. De manera similar, la agrupación de distancia promedio utiliza la distancia promedio por pares como disimilitud. Al igual que la distancia de Ward, estas dos formas de agrupamiento obedecen a una fórmula del tipo Lance-Williams. En enlace completo, la distancia es la máxima de las dos distancias y . Por tanto, es al menos igual al mínimo de estas dos distancias, requisito para ser reducible. Para la distancia promedio, es solo un promedio ponderado de las distancias y . Nuevamente, esto es al menos tan grande como el mínimo de las dos distancias. Por tanto, en ambos casos, la distancia es reducible. ^{[9] [11]} ${\displaystyle d(A\cup B,C)}$ ${\displaystyle d(A,C)}$ ${\displaystyle d(B,C)}$ ${\displaystyle d(A\cup B,C)}$ ${\displaystyle d(A,C)}$ ${\displaystyle d(B,C)}$

A diferencia del método de Ward, estas dos formas de agrupamiento no tienen un método de tiempo constante para calcular distancias entre pares de conglomerados. En cambio, es posible mantener una serie de distancias entre todos los pares de conglomerados. Siempre que se fusionan dos grupos, la fórmula se puede utilizar para calcular la distancia entre el grupo fusionado y todos los demás grupos. Mantener esta matriz durante el transcurso del algoritmo de agrupamiento requiere tiempo y espacio O ( n ² ) . El algoritmo de cadena del vecino más cercano se puede utilizar junto con este conjunto de distancias para encontrar el mismo agrupamiento que el algoritmo codicioso para estos casos. Su tiempo y espacio total, usando esta matriz, también es O ( n ² ) . ^[12]

Los mismos límites de tiempo y espacio O ( n ² ) también se pueden lograr de una manera diferente, mediante una técnica que superpone una estructura de datos de cola de prioridad basada en quadtree sobre la matriz de distancia y la utiliza para realizar el algoritmo de agrupamiento codicioso estándar. Este método de quadtree es más general, ya que funciona incluso para métodos de agrupación que no son reducibles. ^[4] Sin embargo, el algoritmo de la cadena del vecino más cercano coincide con sus límites de tiempo y espacio mientras utiliza estructuras de datos más simples. ^[12]

Enlace único

En la agrupación de enlace único o de vecino más cercano, la forma más antigua de agrupación jerárquica aglomerativa, ^[11] la disimilitud entre los grupos se mide como la distancia mínima entre dos puntos cualesquiera de los dos grupos. Con esta diferencia,

${\displaystyle d(A\cup B,C)=\min(d(A,C),d(B,C)),}$

cumpliendo como una igualdad más que como una desigualdad el requisito de reducibilidad. (El enlace simple también obedece a una fórmula de Lance-Williams, ^{[9] [11]} pero con un coeficiente negativo a partir del cual es más difícil demostrar la reducibilidad).

Al igual que con el enlace completo y la distancia promedio, la dificultad de calcular las distancias de los grupos hace que el algoritmo de la cadena del vecino más cercano tome tiempo y espacio O ( n ² ) para calcular el agrupamiento de enlace único. Sin embargo, la agrupación de enlace único se puede encontrar de manera más eficiente mediante un algoritmo alternativo que calcula el árbol de expansión mínimo de las distancias de entrada usando el algoritmo de Prim , y luego ordena los bordes mínimos del árbol de expansión y usa esta lista ordenada para guiar la fusión de pares de racimos. Dentro del algoritmo de Prim, cada borde mínimo sucesivo del árbol de expansión se puede encontrar mediante una búsqueda secuencial a través de una lista sin clasificar de los bordes más pequeños que conectan el árbol parcialmente construido con cada vértice adicional. Esta elección ahorra el tiempo que de otro modo el algoritmo dedicaría a ajustar los pesos de los vértices en su cola de prioridad . Usar el algoritmo de Prim de esta manera tomaría tiempo O ( n ² ) y espacio O ( n ) , haciendo coincidir los mejores límites que podrían lograrse con el algoritmo de cadena del vecino más cercano para distancias con cálculos de tiempo constante. ^[13]

Distancia centroide

Otra medida de distancia comúnmente utilizada en la agrupación aglomerativa es la distancia entre los centroides de pares de conglomerados, también conocida como método de grupo ponderado. ^{[9] [11]} Se puede calcular fácilmente en tiempo constante por cálculo de distancia. Sin embargo, no es reducible. Por ejemplo, si la entrada forma el conjunto de tres puntos de un triángulo equilátero, fusionar dos de estos puntos en un grupo más grande hace que la distancia entre grupos disminuya, una violación de la reducibilidad. Por lo tanto, el algoritmo de la cadena del vecino más cercano no necesariamente encontrará la misma agrupación que el algoritmo codicioso. Sin embargo, Murtagh (1983) escribe que el algoritmo de la cadena del vecino más cercano proporciona "una buena heurística" para el método del centroide. ^[2] Se puede utilizar un algoritmo diferente de Day y Edelsbrunner (1984) para encontrar el agrupamiento codicioso en tiempo O ( n ² ) para esta medida de distancia. ^[5]

Distancias sensibles al orden de fusión

La presentación anterior prohibía explícitamente distancias sensibles al orden de fusión. De hecho, permitir tales distancias puede causar problemas. En particular, existen distancias de conglomerados sensibles al orden que satisfacen la reducibilidad, pero para las cuales el algoritmo anterior devolverá una jerarquía con costos subóptimos. Por lo tanto, cuando las distancias de los grupos se definen mediante una fórmula recursiva (como lo son algunas de las analizadas anteriormente), se debe tener cuidado de no utilizar la jerarquía de una manera que sea sensible al orden de fusión. ^[14]

Historia

El algoritmo de la cadena del vecino más cercano fue desarrollado e implementado en 1982 por Jean-Paul Benzécri ^[15] y J. Juan. ^[16] Basaron este algoritmo en métodos anteriores que construían agrupaciones jerárquicas utilizando pares mutuos de vecinos más cercanos sin aprovechar las cadenas de vecinos más cercanos. ^{[8] [17]}

Referencias

1. Gordon, Allan D. (1996), "Agrupación jerárquica", en Arabie, P.; Hubert, LJ; De Soete, G. (eds.), Agrupación y clasificación , River Edge, Nueva Jersey: World Scientific, págs. 65-121, ISBN 9789814504539.
2. Murtagh, Fionn (1983), "Un estudio de los avances recientes en algoritmos de agrupamiento jerárquico" (PDF) , The Computer Journal , 26 (4): 354–359, doi : 10.1093/comjnl/26.4.354.
3. Xu, Rui; Wunsch, Don (2008), "3.1 Agrupación jerárquica: Introducción", Agrupación , Serie de prensa del IEEE sobre inteligencia computacional, vol. 10, John Wiley e hijos, pág. 31, ISBN 978-0-470-38278-3.
4. Eppstein, David (2000), "Agrupación jerárquica rápida y otras aplicaciones de pares dinámicos más cercanos", J. Experimental Algorithmics , 5 (1), ACM: 1–23, arXiv : cs.DS/9912014 , Bibcode : 1999cs. ......12014E, dirección :10.1145/351827.351829, S2CID  1357701.
5. Día, William HE; Edelsbrunner, Herbert (1984), "Algoritmos eficientes para métodos de agrupamiento jerárquico aglomerativo" (PDF) , Journal of Classification , 1 (1): 7–24, doi :10.1007/BF01890115, S2CID  121201396.
6. Murtagh, Fionn (2002), "Agrupación en conjuntos de datos masivos", en Abello, James M.; Pardalos, Panos M.; Resende, Mauricio GC (eds.), Manual de conjuntos de datos masivos , Massive Computing, vol. 4, Springer, págs. 513–516, Bibcode : 2002hmds.book.....A, ISBN 978-1-4020-0489-6.
7. Para conocer esta regla de desempate y un ejemplo de cómo se necesita el desempate para evitar ciclos en el gráfico vecino más cercano, consulte Sedgewick, Robert (2004), "Figura 20.7", Algoritmos en Java, Parte 5: Algoritmos de gráficos ( 3ª ed.), Addison-Wesley, pág. 244, ISBN 0-201-36121-3.
8. Bruynooghe, Michel (1977), "Méthodes nouvelles en Classification automatique de données taxinomiqes nombreuses", Statistique et Analyse des Données , 3 : 24–42.
9. Mirkin, Boris (1996), Clasificación matemática y agrupamiento, optimización no convexa y sus aplicaciones, vol. 11, Dordrecht: Kluwer Academic Publishers, págs. 140-144, ISBN 0-7923-4159-7, señor  1480413.
10. Tuffery, Stéphane (2011), "9.10 Agrupación jerárquica aglomerativa", Minería de datos y estadísticas para la toma de decisiones , Serie Wiley en estadística computacional, págs. 253-261, ISBN 978-0-470-68829-8.
11. Lanza, GN; Williams, WT (1967), "Una teoría general de las estrategias de clasificación clasificatoria. I. Sistemas jerárquicos", The Computer Journal , 9 (4): 373–380, doi : 10.1093/comjnl/9.4.373.
12. Gronau, Ilán; Moran, Shlomo (2007), "Implementaciones óptimas de UPGMA y otros algoritmos de agrupamiento comunes", Information Processing Letters , 104 (6): 205–210, doi :10.1016/j.ipl.2007.07.002, MR  2353367.
13. Gower, JC; Ross, GJS (1969), "Árboles de expansión mínima y análisis de conglomerados de enlace único", Revista de la Royal Statistical Society, Serie C , 18 (1): 54–64, JSTOR  2346439, SEÑOR  0242315.
14. Müllner, Daniel (2011), Algoritmos modernos de agrupamiento aglomerativo, jerárquico , vol. 1109, arXiv : 1109.2378 , código Bib : 2011arXiv1109.2378M.
15. Benzécri, J.-P. (1982), "Construction d'une Classification ascendante hiérarchique par la recherche en chaîne des voisins réciproques", Les Cahiers de l'Analyse des Données , 7 (2): 209–218.
16. Juan, J. (1982), "Programme de Classification Hiérarchique par l'algorithme de la recherche en chaîne des voisins réciproques", Les Cahiers de l'Analyse des Données , 7 (2): 219–225.
17. de Rham, C. (1980), "La clasificación hiérarchique ascendante selon la méthode des voisins réciproques", Les Cahiers de l'Analyse des Données , 5 (2): 135-144.