Algoritmo de cadena del vecino más próximo

Método basado en pilas para agrupamiento

En la teoría del análisis de conglomerados , el algoritmo de la cadena del vecino más próximo 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 conglomerados de puntos fusionando repetidamente pares de conglomerados más pequeños para formar conglomerados más grandes. Los métodos de agrupamiento para los que se puede utilizar el algoritmo de la cadena del vecino más próximo incluyen el método de Ward , el agrupamiento por ligamiento completo y el agrupamiento por ligamiento único ; todos ellos funcionan fusionando repetidamente los dos conglomerados más cercanos, pero utilizan diferentes definiciones de la distancia entre conglomerados. Las distancias de conglomerado para las que funciona el algoritmo de la cadena del vecino más próximo se denominan reducibles y se caracterizan por una desigualdad simple entre ciertas distancias de conglomerado.

La idea principal del algoritmo es encontrar pares de clústeres para fusionar siguiendo rutas en el gráfico de vecinos más cercanos de los clústeres. Cada una de esas rutas terminará eventualmente 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 para 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 las rutas de esta manera, el algoritmo de cadena de vecinos más cercanos 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 clústeres.

El algoritmo de cadena de vecino más cercano construye una agrupación en el tiempo proporcional al cuadrado del número de puntos que se van 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 agrupación como el método de Ward que permiten el cálculo en tiempo constante de la distancia entre agrupaciones. 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 van a agrupar se encuentran en la parte superior del diagrama y los nodos que se encuentran debajo de ellos representan agrupaciones.

Muchos problemas en el análisis de datos se relacionan con la agrupación , es decir, 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 una estructura similar a un árbol en lugar de una partición estricta de los elementos de datos. En algunos casos, este tipo de agrupación se puede realizar como una forma de realizar un análisis de conglomerados en múltiples escalas diferentes simultáneamente. En otros casos, los datos que se van 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 se pueden ver, por ejemplo, en la aplicación de la agrupación jerárquica a la taxonomía biológica . En esta aplicación, diferentes seres vivos se agrupan en grupos a diferentes escalas o niveles de similitud ( especie, género, familia, etc. ). Este análisis proporciona simultáneamente una agrupación multiescalar 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 consiste en un conjunto de puntos. ^[2] Un grupo es cualquier subconjunto propio de los 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 disjuntos . Alternativamente, un agrupamiento jerárquico puede representarse como un árbol binario con los puntos en sus hojas; los grupos del agrupamiento 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 considera primero. Sin embargo, a diferencia de las distancias en un espacio métrico , no se requiere que satisfaga la desigualdad triangular . ^[2] A continuación, la función de disimilitud se extiende de pares de puntos a pares de clústeres. Diferentes métodos de agrupamiento realizan esta extensión de diferentes maneras. Por ejemplo, en el método de agrupamiento de enlace único , la distancia entre dos clústeres se define como la distancia mínima entre dos puntos cualesquiera de cada clúster. Dada esta distancia entre clústeres, un agrupamiento jerárquico puede definirse mediante un algoritmo voraz que inicialmente coloca cada punto en su propio clúster de un solo punto y luego forma repetidamente un nuevo clúster fusionando el par de clústeres más cercano . ^[2]

El cuello de botella de este algoritmo voraz es el subproblema de encontrar qué dos clústeres fusionar en cada paso. Los métodos conocidos para encontrar repetidamente el par de clústeres más cercano en un conjunto dinámico de clústeres requieren un espacio superlineal para mantener una estructura de datos que pueda encontrar los pares más cercanos rápidamente, o toman 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 voraz al fusionar pares de clústeres en un orden diferente. De esta manera, evita el problema de encontrar repetidamente los pares más cercanos. Sin embargo, para muchos tipos de problemas de agrupamiento, se puede garantizar que se obtenga el mismo agrupamiento jerárquico que el algoritmo voraz a pesar del orden de fusión diferente. ^[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 señalan a los vecinos más cercanos y la barra roja indica la cadena actual. Para simplificar la visualización, cuando una fusión deja la cadena vacía, continúa con el grupo fusionado recientemente.

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

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

• Inicialice el conjunto de clústeres activos para que conste de 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.
• Mientras haya más de un clúster en el conjunto de clústeres:
  • Si S está vacío , elija un clúster activo arbitrariamente y empújelo hacia S.
  • Sea C el cúmulo activo en la parte superior de S. Calcule las distancias desde C a todos los demás cúmulos y sea D el otro cúmulo más cercano.
  • Si D ya está en S , debe ser el predecesor inmediato de C. Extraiga ambos clústeres de S y fusionelos.
  • De lo contrario, si D no está ya en S , empújelo hacia S.

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

Análisis del tiempo y el espacio

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

Cada una de estas iteraciones puede dedicar tiempo a escanear hasta n − 1 distancias entre clústeres para encontrar el vecino más cercano. Por lo tanto, el número total de cálculos de distancia que realiza es menor que 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 la extracción y fusión de los dos clústeres superiores de la pila del algoritmo preserve la propiedad de que los clústeres restantes en la pila formen una cadena de vecinos más cercanos. Además, debe darse el caso de que todos los clústeres producidos durante el algoritmo sean los mismos que los clústeres producidos por un algoritmo voraz que siempre fusiona los dos clústeres más cercanos, aunque el algoritmo voraz en general realizará sus fusiones en un orden diferente al del algoritmo de cadena de vecinos más cercanos. Ambas propiedades dependen de la elección específica de cómo medir la distancia entre clústeres. ^[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 de vecinos más cercanos mutuos pero no cadenas de vecinos más cercanos. ^[8] Una función de distancia d en clústeres se define como reducible si, para cada tres clústeres A , B y C en el agrupamiento jerárquico voraz tales que A y B son vecinos más cercanos mutuos, se cumple la siguiente desigualdad: ^[2]

d ( A ∪ B , C ) ≥ mín(d( A , C ), d( B , C )) .

Si una función de distancia tiene la propiedad de reducibilidad, entonces la fusión de 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 cadena de vecinos más cercanos. Primero, se puede demostrar usando esta propiedad que, en cada paso del algoritmo, los grupos en la pila S forman una cadena válida de vecinos más cercanos, porque siempre que un vecino más cercano se invalida se elimina inmediatamente de la pila. ^[2]

En segundo lugar, y aún más importante, de esta propiedad se deduce que, si dos clústeres C y D pertenecen a la agrupación jerárquica voraz y son vecinos mutuos más cercanos en cualquier momento, entonces serán fusionados por la agrupación voraz, ya que deben seguir siendo vecinos mutuos más cercanos hasta que se fusionen. De ello se deduce que cada par de vecinos mutuos más cercanos encontrado por el algoritmo de cadena de vecinos más cercanos es también un par de clústeres encontrados por el algoritmo voraz y, por lo tanto, que el algoritmo de cadena de vecinos más cercanos calcula exactamente el mismo agrupamiento (aunque en un orden diferente) que el algoritmo voraz. ^[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 la fusión de los dos grupos en un solo grupo más grande aumentaría la distancia cuadrada promedio de un punto a su centroide del 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 la 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 variante más popular del agrupamiento aglomerativo tanto por la forma redonda de los grupos que forma típicamente como por su definición basada en principios como el agrupamiento que en cada paso tiene la menor varianza 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 grupos antiguos.

La distancia de Ward también es reducible, como se puede ver más fácilmente a partir de 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 del lado derecho (como sería necesariamente cierto si y son vecinos mutuos más cercanos), entonces la contribución negativa de su término se cancela con el coeficiente de uno de los otros dos términos, dejando un valor positivo agregado al promedio ponderado de las otras dos distancias. Por lo tanto, la distancia combinada siempre es 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)}$

Como la distancia de Ward es reducible, el algoritmo de cadena de vecinos más próximos que utiliza la distancia de Ward calcula exactamente la misma agrupación que el algoritmo voraz 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

El agrupamiento por ligamiento completo o por el vecino más lejano es una forma de agrupamiento aglomerativo que define la disimilitud entre los grupos como la distancia máxima entre dos puntos cualesquiera de los dos grupos. De manera similar, el agrupamiento por distancia promedio utiliza la distancia promedio por pares como la disimilitud. Al igual que la distancia de Ward, estas dos formas de agrupamiento obedecen a una fórmula de tipo Lance-Williams. En el ligamiento completo, la distancia es el máximo de las dos distancias y . Por lo tanto, es al menos igual al mínimo de estas dos distancias, el requisito para ser reducible. Para la distancia promedio, es simplemente un promedio ponderado de las distancias y . Nuevamente, esto es al menos tan grande como el mínimo de las dos distancias. Por lo 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 las distancias entre pares de agrupamientos. En su lugar, es posible mantener una matriz de distancias entre todos los pares de agrupamientos. Siempre que se fusionan dos agrupamientos, se puede utilizar la fórmula para calcular la distancia entre el agrupamiento fusionado y todos los demás agrupamientos. Mantener esta matriz a lo largo del algoritmo de agrupamiento requiere tiempo y espacio O ( n ² ) . El algoritmo de cadena del vecino más cercano se puede utilizar junto con esta matriz de distancias para encontrar el mismo agrupamiento que el algoritmo voraz para estos casos. Su tiempo y espacio totales, utilizando esta matriz, también son 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 voraz estándar. Este método quadtree es más general, ya que funciona incluso para métodos de agrupamiento que no son reducibles. ^[4] Sin embargo, el algoritmo de cadena de vecino más cercano coincide con sus límites de tiempo y espacio mientras usa estructuras de datos más simples. ^[12]

Enlace simple

En la agrupación por vínculo único o por vecino más próximo, la forma más antigua de agrupación jerárquica aglomerativa, ^[11] la disimilitud entre agrupaciones se mide como la distancia mínima entre dos puntos cualesquiera de las dos agrupaciones. Con esta disimilitud,

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

cumpliendo como una igualdad más bien 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 probar la reducibilidad.)

Al igual que con el enlace completo y la distancia promedio, la dificultad de calcular las distancias de los clústeres hace que el algoritmo de cadena del vecino más cercano tome tiempo y espacio O ( n ² ) para calcular el agrupamiento de enlace simple. Sin embargo, el agrupamiento de enlace simple 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 utilizando el algoritmo de Prim y luego ordena los bordes del árbol de expansión mínimo y usa esta lista ordenada para guiar la fusión de pares de clústeres. Dentro del algoritmo de Prim, cada borde sucesivo del árbol de expansión mínimo se puede encontrar mediante una búsqueda secuencial a través de una lista no ordenada de los bordes más pequeños que conectan el árbol parcialmente construido con cada vértice adicional. Esta opción ahorra el tiempo que el algoritmo de otro modo gastaría ajustando 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 ) , coincidiendo con 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 del centroide

Otra medida de distancia que se utiliza habitualmente en el agrupamiento aglomerativo es la distancia entre los centroides de pares de agrupamientos, también conocido 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, la fusión de dos de estos puntos en un agrupamiento más grande hace que la distancia entre agrupamientos disminuya, lo que constituye una violación de la reducibilidad. Por lo tanto, el algoritmo de cadena del vecino más cercano no encontrará necesariamente el mismo agrupamiento que el algoritmo voraz. Sin embargo, Murtagh (1983) escribe que el algoritmo de 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 voraz en tiempo O ( n ² ) para esta medida de distancia. ^[5]

Distancias sensibles al orden de fusión

La presentación anterior explícitamente no permitía distancias sensibles al orden de fusión. De hecho, permitir tales distancias puede causar problemas. En particular, existen distancias de clúster 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 clúster se definen mediante una fórmula recursiva (como algunas de las que se analizaron anteriormente), se debe tener cuidado de que no utilicen la jerarquía de una manera que sea sensible al orden de fusión. ^[14]

Historia

El algoritmo de cadena de vecinos más próximos 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 de vecinos más próximos mutuos sin aprovechar las cadenas de vecinos más próximos. ^{[8] [17]}

Referencias

1. Gordon, Allan D. (1996), "Agrupamiento jerárquico", en Arabie, P.; Hubert, LJ; De Soete, G. (eds.), Agrupamiento y clasificación , River Edge, NJ: 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 Agrupamiento jerárquico: Introducción", Agrupamiento , IEEE Press Series on Computational Intelligence, vol. 10, John Wiley & Sons, pág. 31, ISBN 978-0-470-38278-3.
4. Eppstein, David (2000), "Agrupamiento jerárquico rápido 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, doi :10.1145/351827.351829, S2CID  1357701.
5. Day, 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), "Agrupamiento en conjuntos de datos masivos", en Abello, James M.; Pardalos, Panos M.; Resende, Mauricio GC (eds.), Handbook of massive data sets , 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, Sr.  1480413.
10. Tuffery, Stéphane (2011), "9.10 Agrupamiento jerárquico aglomerativo", Minería de datos y estadísticas para la toma de decisiones , Wiley Series in Computational Statistics, págs. 253–261, ISBN 978-0-470-68829-8.
11. Lance, GN; Williams, WT (1967), "Una teoría general de las estrategias de ordenamiento clasificatorio. I. Sistemas jerárquicos", The Computer Journal , 9 (4): 373–380, doi : 10.1093/comjnl/9.4.373.
12. Gronau, Ilan; 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 simple", Journal of the Royal Statistical Society, Serie C , 18 (1): 54–64, JSTOR  2346439, MR  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.