c++ - métrico - Algoritmo de escalamiento multidimensional ''estable''

escalamiento multidimensional no métrico (3)

He leído los códigos de la biblioteca MDS "SimpleMatrix" y he encontrado que utiliza una matriz de permutación aleatoria para decidir el orden de los puntos. Después de corregir el orden de permutación (solo use srand (12345) en lugar de srand (tiempo (0))), el resultado de los mismos datos no cambia.

Tengo una red de malla inalámbrica de nodos, cada uno de los cuales es capaz de informar su "distancia" a sus vecinos, medida en intensidad de señal (simplificada) para ellos. Los nodos están geográficamente en el espacio 3d, pero debido a la interferencia de radio, la distancia entre los nodos no tiene por qué ser trigonométricas (¿trigonómicamente?). Es decir, dados los nodos A, B y C, la distancia entre A y B puede ser 10, entre A y C también 10, pero entre B y C 100.

Lo que quiero hacer es visualizar el diseño de la red lógica en términos de conectividad de los nodos, es decir, incluir la distancia lógica entre los nodos en lo visual.

Hasta ahora mi investigación ha demostrado que el escalamiento multidimensional (MDS) está diseñado para exactamente este tipo de cosas. Dado que mis datos pueden expresarse directamente como una matriz de distancia 2d, es incluso una forma más simple del MDS más general.

Ahora, parece que hay muchos algoritmos MDS, ver, por ejemplo, http://homepage.tudelft.nl/19j49/Matlab_Toolbox_for_Dimensionality_Reduction.html y http://tapkee.lisitsyn.me/ . Necesito hacer esto en C ++ y espero poder usar un componente ya hecho, es decir, no tener que volver a implementar un algoritmo desde un papel. Entonces, pensé esto: https://sites.google.com/site/simpmatrix/ sería el boleto. Y funciona, pero:

El diseño no es estable, es decir, cada vez que se vuelve a ejecutar el algoritmo, la posición de los nodos cambia (vea las diferencias entre las imágenes 1 y 2 a continuación, esto se debe a que se ejecutó dos veces, sin más cambios). Esto se debe a la matriz de inicialización (que contiene la ubicación inicial de cada nodo, que luego el algoritmo corrige iterativamente) que se pasa a este algoritmo: paso un vacío y luego la implementación deriva una aleatoria. En general, el diseño se aproxima al diseño que esperaba de los datos de entrada dados. Además, entre diferentes recorridos, la dirección de los nodos (en sentido horario o antihorario) puede cambiar. Ver imagen 3 a continuación.
La "solución" que pensé era obvia, era pasar una matriz de inicialización predeterminada estable. Pero cuando puse todos los nodos inicialmente en el mismo lugar, no se movieron en absoluto; cuando los coloco en un eje (nodo 0 en 0,0; nodo 1 en 1,0; nodo 2 en 2,0, etc.), se mueven solo a lo largo de ese eje. (ver imagen 4 abajo). Sin embargo, las distancias relativas entre ellos están bien.

Así que parece que este algoritmo solo cambia la distancia entre nodos, pero no cambia su ubicación.

Gracias por leer hasta aquí. Mis preguntas son (Me encantaría que solo una o algunas de ellas sean respondidas, ya que cada una de ellas podría darme una pista sobre qué dirección seguir):

¿Dónde puedo encontrar más información sobre las propiedades de cada uno de los muchos algoritmos MDS?
¿Existe un algoritmo que derive la ubicación completa de cada nodo en una red, sin tener que pasar una posición inicial para cada nodo?
¿Existe una manera sólida de estimar la ubicación de cada punto para que el algoritmo pueda escalar correctamente la distancia entre ellos? No tengo una ubicación geográfica de cada uno de estos nodos, ese es el punto central de este ejercicio.
¿Hay algoritmos para mantener el ''ángulo'' en el que la red se deriva constante entre ejecuciones?

Si todo lo demás falla, mi próxima opción será usar el algoritmo que mencioné anteriormente, aumentar el número de iteraciones para mantener la variabilidad entre ejecuciones en unos pocos píxeles (tendría que experimentar con cuántas iteraciones tomaría ), luego ''gire'' cada nodo alrededor del nodo 0 para, por ejemplo, alinear los nodos 0 y 1 en una línea horizontal de izquierda a derecha; de esa manera, ''corregiría'' la ubicación de los puntos después de que sus distancias relativas hayan sido determinadas por el algoritmo MDS. También tendría que corregir el orden de los nodos conectados (en el sentido de las agujas del reloj o en el sentido contrario a las agujas del reloj) alrededor de cada nodo. Esto podría volverse peludo muy rápidamente.

Obviamente, preferiría una solución algorítmica estable: aumentar las iteraciones para suavizar la aleatoriedad no es muy confiable.

Gracias.

EDITAR: Me remitieron a cs.stackexchange.com y se hicieron algunos comentarios allí; para sugerencias algorítmicas, consulte https://cs.stackexchange.com/questions/18439/stable-multi-dimensional-scaling-algorithm .

Imagen 1 - con matriz de inicialización aleatoria:

Imagen 2: después de ejecutarse con los mismos datos de entrada, se gira cuando se compara con 1:

Imagen 3: igual que la anterior 2, pero los nodos 1-3 están en otra dirección:

Imagen 4: con el diseño inicial de los nodos en una línea, su posición en el eje y no cambia:

La mayoría de los algoritmos de escalado establecen efectivamente "resortes" entre nodos, donde la longitud de reposo del resorte es la longitud deseada del borde. Luego intentan minimizar la energía del sistema de resortes. Sin embargo, cuando inicializa todos los nodos uno encima del otro, la cantidad de energía liberada cuando se mueve cualquier nodo es la misma en todas las direcciones. Así que el gradiente de energía con respecto a la posición de cada nodo es cero, por lo que el algoritmo deja el nodo donde está. De manera similar, si los inicia todos en una línea recta, el gradiente siempre está en esa línea, por lo que los nodos solo se mueven a lo largo de ella.

(Esa es una explicación errónea en muchos aspectos, pero funciona para una intuición)

Intente inicializar los nodos para que queden en el círculo unitario, en una cuadrícula o de cualquier otra manera, de modo que no sean todos colineales. Asumir que el esquema de actualización del algoritmo de la biblioteca es determinista, debería proporcionarle visualizaciones reproducibles y evitar condiciones de degeneración.

Si la biblioteca no es determinista, busque otra biblioteca que sea determinista o abra el código fuente y reemplace el generador de aleatoriedad con un PRNG inicializado con una semilla fija. Sin embargo, recomendaría la primera opción, ya que otras bibliotecas más avanzadas deberían permitirle establecer los bordes que también quiere "ignorar".

Obviamente no hay una solución exacta en general para este problema; con solo 4 nodos ABCD y distancias AB=BC=AC=AD=BD=1 CD=10 no puede dibujar claramente un diagrama 2D adecuado (ni siquiera uno 3D).

Lo que hacen esos algoritmos es simplemente colocar resortes entre los nodos y luego simular una repulsión / atracción (dependiendo de si el resorte es más corto o más largo que la distancia prescrita) probablemente también agregue fricción espacial para evitar la resonancia y la explosión.

Para mantener un diagrama "estable", cree una solución y luego actualice las distancias, reutilizando la posición actual de la solución anterior como punto de partida. Elegir dos nodos fijos y alinearlos parece una buena idea para evitar una desviación lenta, pero diría que las fuerzas de resorte nunca terminan creando un momento de rotación y, por lo tanto, espero que basta con escalar y centrar la solución de todos modos.