Encontrar correspondencias óptimas entre objetos dadas dos matrices de distancia cuadradas

Question

Me gustaría encontrar las correspondencias óptimas entre dos sistemas de objetos basados en las distancias entre los objetos DENTRO de los dos sistemas. Así, la entrada del algoritmo serían dos matrices de distancia cuadradas que expresen las distancias de cada objeto de un sistema a cada uno de los otros objetos dentro del mismo sistema. Por ejemplo, si un sistema tiene objetos {Q, R, S} y el otro tiene objetos {A, B, C} entonces las dos matrices de distancia podrían tener el siguiente aspecto

        Q       R       S
Q       0       .5      .2
R       .5      0       .7
S       .2      .7      0

        A       B       C
A       0       .8      .4
B       .8      0       .3
C       .4      .3      0

lo que significa, por ejemplo, que la distancia del objeto R a S es 0,7. Cada objeto tiene una distancia de 0 a sí mismo, pero las distancias no tienen por qué satisfacer los supuestos de un espacio métrico. Sin embargo, se puede suponer que cada una de las matrices de distancia es simétrica, como en este ejemplo. El resultado del algoritmo sería un conjunto de correspondencias entre los objetos de los sistemas que minimiza la suma de las diferencias absolutas entre las distancias de los objetos correspondientes bajo la restricción de que ningún objeto de un sistema se corresponde con más de un objeto del otro sistema . En el ejemplo anterior, las correspondencias óptimas serían R<->A, Q<->C, y S<->B, lo que da como resultado una suma de disimilitudes entre distancias de:

|0.4-0.5| + |0.8-0.7|   for the distance relations that R and A enter into. E.g. dist(R,Q)=.5 and dist(A,C)=.4
          +
|0.2-0.3| + |0.5-0.4|   for the distance relations that Q and C enter into.
          +
|0.3-0.2| + |0.7-0.8|   for the distance relations that S and B enter into.
          =
         0.6

que es menor que cualquier otra forma consistente (no se permiten correspondencias de 2 a 1) de colocar los objetos en correspondencia. La salida, entonces, para el algoritmo, podría ser así:

        Q       R       S
A       0       1       0
B       0       0       1
C       1       0       0

donde 1 significa que los objetos están colocados en correspondencias. Ya he desarrollado ( http://cognitrn.psych.indiana.edu/rgoldsto/pdfs/relalign.pdf ) un algoritmo iterativo de satisfacción de restricciones de redes neuronales para este problema, pero es demasiado lento y computacionalmente ineficiente para sistemas que contienen más de 20 o más objetos porque tiene una complejidad O(n^4). Parece que debería haber una solución algebraica lineal rápida para este problema. Hay un par de soluciones posiblemente relacionadas que no consigo que estén lo suficientemente relacionadas para mis necesidades. Por ejemplo, el "problema de la asignación" tiene una solución O(n^3) en la forma del "algoritmo húngaro", pero éste asume costes fijos para cada asignación, mientras que en el problema anterior el coste asociado a la asignación de A a Q, por ejemplo, depende de todas las demás asignaciones que se realicen porque estas otras asignaciones cambiarán las distancias entre los sistemas que se comparan. El problema también parece ser algo que podría manejarse con el Despliegue Multidimensional o el Análisis de Procrustes Generalizado, pero la diferencia clave en el problema actual es que no tenemos etiquetas que nos digan qué objetos de un sistema son los mismos que los del otro sistema - ¡eso es lo que estamos tratando de averiguar en primer lugar! Gracias por cualquier pista.

Answer 1

Un posible enfoque: utilizar el Húngaro dos veces.

Aquí están sus dos matrices de proximidad simétricas cuadradas (he multiplicado todo por 10; también he cambiado AB valor de 8 a 9 - mi fantasía, con su permiso)

        Q       R       S
Q              
R       5       
S       2       7       

        A       B       C
A       
B       9       
C       4       3       

Considera cada par de valores entre las matrices, su diferencia absoluta, como un coste y construye la matriz de costes

      AB     AC     BC
QR  |5-9|  |5-4|  |5-3|
QS  |2-9|  |2-4|  |2-3|
RS  |7-9|  |7-4|  |7-3|
             =
      AB     AC     BC
QR     4      1*     2
QS     7      2      1*
RS     2*     3      4

Realiza el cotejo húngaro. Siendo los valores estrellados de arriba los que suman el mínimo, por lo que el emparejamiento es

QR - AC
QS - BC
RS - AB

DE ACUERDO. En cada par, hay dos objetos del conjunto1 y dos objetos del conjunto2. Construye una matriz de objetos del conjunto1 X el conjunto2 que muestre cuántas veces se encuentran entre sí dentro de los pares.

   A   B   C
Q  1   1   2*
R  2*  1   1
S  1   2*  1

Realice la coincidencia húngara (tratando ahora estas frecuencias como ganancia, no como coste). Los valores marcados, cuya suma se maximiza, marcan los pares que se buscan.

Q - C
R - A
S - B

Como variante, puede ponderar los recuentos de la última matriz (de ganancia) por los valores de la matriz de costes anterior. Por ejemplo, R y A encuentro dos veces, como vemos. Una vez bajo RS-AB con coste 2 y una vez bajo QR-AC con coste 1 . Así que puedes ponderar la frecuencia, hacer que sea la suma de los costes. En tu ejemplo, como los costes son opuestos a las ganancias, deberías invertir de algún modo esas ponderaciones; o simplemente hacer todo el análisis basándote sólo en las ganancias desde el principio.

Answer 2

He intentado implementar la solución propuesta por ttnphns, con resultados interesantes. Para probar el enfoque, generé aleatoriamente 20 puntos en dos dimensiones para el Sistema 1, los copié con un poco de ruido para formar el Sistema 2, y luego creé una matriz de distancia 20 X 20 para cada sistema basada en las distancias euclidianas entre cada par de puntos dentro de un sistema. Si he creado el Sistema 2 con muy poco ruido, entonces la alineación es perfecta:

(Los polígonos sombreados en azul y rojo y sus aristas definitorias sólo se añaden para la legibilidad visual; no influyen en absoluto en el algoritmo)

Así que ¡bravo ttnphn por proponer una solución que realmente funciona! Sin embargo, si añado un poco más de ruido (se puede ver intuitivamente cuánto comparando las posiciones de los puntos en los lados izquierdo y derecho), la alineación es sólo ligeramente mejor que el azar:

Mi impresión de por qué el algoritmo no es muy tolerante con el ruido es que no está tratando las distancias como algo correctamente estructurado. Crea coincidencias consistentes entre los dos conjuntos de bordes de distancia a través de los dos sistemas, y luego coincidencias consistentes de elementos a través de los dos sistemas, pero no hay nada en el algoritmo que presione para que R corresponda a A específicamente porque Q muy probablemente corresponde a C y la distancia de Q a R es muy similar a la distancia de C a A. Mi algoritmo original es considerablemente más tolerante al ruido que el algoritmo húngaro doble de ttnphns, pero, por desgracia, su complejidad computacional (O(C*N^4), donde N es el número de elementos por sistema y C es el número de iteraciones de satisfacción de restricciones, normalmente al menos 1000) sigue impidiendo que se aplique a más de, digamos, 30 elementos por sistema.