Editar distancia entre dos particiones

Tengo dos particiones de $[1 \ldots n]$ y estoy buscando la distancia de edición entre ellas.

Con esto, quiero encontrar el número mínimo de transiciones individuales de un nodo en un grupo diferente que son necesarias para pasar de la partición A a la partición B.

Por ejemplo, la distancia desde {0 1} {2 3} {4}adentro {0} {1} {2 3 4}sería dos

Después de buscar me encontré con este documento, pero a) no estoy seguro de si están teniendo en cuenta el orden de los grupos (algo que no me importa) a su distancia b) No estoy seguro de cómo funciona yc) No hay referencias

Cualquier ayuda apreciada

ds.algorithms edit-distance lattice zenna
fuente

¿Cuál consideraría que es la distancia entre {0 1 2 3} y {0 1} {2 3}? ¿Sería 2? En segundo lugar, no veo por qué los "gráficos" entran en escena. Parece que tiene dos particiones de [n] y desea calcular una distancia entre ellas.

Suresh Venkat

Sí, serían dos. De hecho, estas son particiones establecidas en los nodos de un gráfico (es decir, una partición de gráfico). Es probable que esto no sea importante para la solución, pero este es el problema que estoy tratando de resolver, de ahí por qué lo mencioné.

zenna

Si el gráfico es irrelevante, elimine todas las referencias a "gráficos" y "nodos" de su pregunta; no ayuda, distrae.

Jukka Suomela

¿No se puede definir la distancia de edición en términos de la distancia en la red de partición?

Tegiri Nenashi

@Tegiri: de hecho, es la distancia geodésica en la red de particiones. Desafortunadamente, calcular esa red para cualquier conjunto de cardinalidad mucho mayor que 10 es intratable.

zenna

Respuestas:

Este problema se puede transformar en el problema de asignación , también conocido como problema de coincidencia bipartita ponderada máxima.

Tenga en cuenta primero que la distancia de edición es igual al número de elementos que deben cambiar de un conjunto a otro. Esto es igual al número total de elementos menos el número de elementos que no necesitan cambiar. Por lo tanto, encontrar el número mínimo de elementos que no cambian es equivalente a encontrar el número máximo de vértices que no cambian.

Deje que y sea particiones de . Además, sin pérdida de generalidad, sea (permitido porque $A = \{ A_1, A_2, ..., A_k \}$ $B = \{ B_1, B_2, ..., B_l \}$ $[1, 2, ..., n]$ $k \ge l$ ). Entonces dejemos que , , ..., sean el conjunto vacío. Entonces el número máximo de vértices que no cambian es: $edit(A, B) = edit(B, A)$ $B_{l+1}$ $B_{l+2}$ $B_k$

$\max_f \sum_{i=1}^k |A_i \cap B_{f(i)} |$

donde es una permutación de . $f$ $[1, 2, ..., k]$

Este es exactamente el problema de asignación donde los vértices son , ..., , , ..., y los bordes son pares con peso . Esto se puede resolver en el tiempo . $A_1$ $A_k$ $B_1$ $B_k$ $(A_i, B_j)$ $|A_i \cap B_j|$ $O(|V|^2 \log |V| + |V||E|)$

bbejot
fuente

¿Podría nombrar el algoritmo, que le da complejidad a este tiempo, por favor?

D-503

Creo que @bbejot se refiere al algoritmo sucesivo de la ruta más corta (con la subrutina Dijkstra implementada utilizando montones de fibonacci).

Wei

Me tomó mucho tiempo analizar esto porque no soy una persona de matemáticas, pero gracias. Pasé mucho tiempo buscando y esto fue lo único que pude encontrar que mostraba cómo convertir el problema de distancia de partición al problema de asignación, o a cualquier algoritmo que pudiera llamar desde una biblioteca de Python. (La parte difícil para mí ha sido descubrir cómo usar scipy.optimize.linear_sum_assignment y luego configurar las matrices basadas en estas instrucciones).

Sigfried

Necesitaba hacer los pesos negativos. De lo contrario, scipy.optimize.linear_sum_assignment me da 0 para todo.

Sigfried

Mira el PDF de este documento

http://www.ploscompbiol.org/article/info:doi/10.1371/journal.pcbi.0030160

La definición de distancia de edición allí es exactamente lo que necesita, creo. La partición de 'referencia' sería (una arbitraria) una de sus dos particiones, la otra sería simplemente la otra. También contiene citas relevantes.

Mejor, Rob

Robar
fuente

Gracias Rob Sin embargo, a menos que me falte algo, esta es una distancia de edición definida en términos de movimientos de fusión dividida. Estos están bien estudiados y, como señala el artículo, la variación de la información es una medida teórica de la información de esto. Sin embargo, estoy interesado en las transiciones de movimiento de un solo elemento.

zenna

Cranky idea del domingo por la mañana que podría o no ser correcta:

Wlog, deja que sea la partición con más conjuntos, el otro. Primero, asigne diferentes nombres por pares a sus conjuntos . Luego, encuentre un mejor nombre para los conjuntos según las siguientes reglas: $P_1$ $P_2$ $n_1(S) \in \Sigma$ $P_1$ $n_2(S)$ $P_2$

para con máximo entre todos ; elija el que cree la menor cantidad de conflictos si son posibles varias opciones. $n_2(S) := n_1(S')$ $S \in P_2$ $S \cap S'$ $S' \in P_1$
$n_2(S) = n_2(S')$ $S \neq S'$ $S'', n_1(S'') = n_2(S)$ $P_1$
$S'' \in P_1$ $S, S'$
$P_1$ $P_2$

$w_1 = n_1(1) \cdot \dots \cdot n_1(n)$ $w_2 = n_2(1) \cdot \dots \cdot n_2(n)$ $n_j(i) = n_j(S), i \in S \in P_j$ ). Then, the desired quantity is $d_H(w_1, w_2)$ , i.e. the Hamming distance between the bit strings.

Raphael
fuente