Modifier la distance entre deux partitions

J'ai deux partitions de et je recherche la distance d'édition entre elles.$[1 \ldots n]$

Par cela, je veux trouver le nombre minimal de transitions uniques d'un nœud dans un groupe différent qui sont nécessaires pour passer de la partition A à la partition B.

Par exemple, la distance de {0 1} {2 3} {4}en {0} {1} {2 3 4}serait de deux

Après avoir cherché, je suis tombé sur ce document, mais a) je ne sais pas s'ils tiennent compte de l'ordre des groupes (quelque chose qui ne m'importe pas) à leur distance b) je ne sais pas comment cela fonctionne et c) Il n'y a pas de références.

Toute aide appréciée

Ce problème peut être transformé en problème d'affectation , également connu sous le nom de problème de correspondance bipartite pondérée maximale.

Notez d'abord que la distance d'édition est égale au nombre d'éléments qui doivent changer d'un ensemble à un autre. Cela équivaut au nombre total d'éléments moins le nombre d'éléments qui n'ont pas besoin de changer. Donc, trouver le nombre minimum d'éléments qui ne changent pas équivaut à trouver le nombre maximum de sommets qui ne changent pas.

Let et B = { B 1 , B 2 , . . . , B l } soit de partitions [ 1 , 2 , . . . , n ] . Aussi, sans perte de généralité, soit k ≥ l (autorisé car e d i $A = \{ A_1, A_2, ..., A_k \}$$B = \{ B_1, B_2, ..., B_l \}$$[1, 2, ..., n]$$k \ge l$ ). Soit alors B l + 1 , B l + 2 , ..., B k tous les ensembles vides. Alors le nombre maximum de sommets qui ne changent pas est:$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)} |$

où est une permutation de [ 1 , 2 , . . . , k ] .$f$$[1, 2, ..., k]$

C'est exactement le problème d'affectation où les sommets sont , ..., A k , B 1 , ..., B k et les arêtes sont des paires ( A i , B j ) de poids | A i ∩ B j | . Cela peut être résolu en temps O ( | V | 2 log | V | + | V | | E | ) .$A_1$$A_k$$B_1$$B_k$$(A_i, B_j)$$|A_i \cap B_j|$$O(|V|^2 \log |V| + |V||E|)$

Regardez le PDF de cet article

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

La définition de la distance d'édition là-dedans est exactement ce dont vous avez besoin, je pense. La partition «de référence» serait (arbitraire) l'une de vos deux partitions, l'autre serait simplement l'autre. Contient également des citations pertinentes.

Cordialement, Rob

Idée grincheuse du dimanche matin qui pourrait ou non être correcte:

Wlog, que soit la partition avec plus d'ensembles, P 2 l'autre. Tout d'abord, attribuez des noms différents par paire n 1 ( S ) ∈ Σ à vos ensembles P 1 . Ensuite, trouvez une meilleure dénomination n 2 ( S ) pour les ensembles P 2 selon les règles suivantes:$P_1$$P_2$$n_1(S) \in \Sigma$$P_1$$n_2(S)$$P_2$

• pour S ∈ P 2 avec S ∩ S ′ maximal parmi tous S ′ ∈ P 1 ; choisissez celui qui crée le moins de conflits si plusieurs choix sont possibles.$n_2(S) := n_1(S')$$S \in P_2$$S \cap S'$$S' \in P_1$
• Si maintenant pour certains S ≠ S ′ , attribuez celui qui partage le moins d'éléments avec S ″ , n 1 ( S ″ ) = n 2 ( S ) , le nom de l'ensemble dans P 1, il partage le deuxième plus grand nombre d'éléments, c'est-à-dire qu'il doit concourir pour le nom de cet ensemble.$n_2(S) = n_2(S')$$S \neq S'$$S'', n_1(S'') = n_2(S)$$P_1$
• Si l'ancienne règle ne peut pas être appliquée, vérifiez si les deux ensembles peuvent concourir pour le nom des autres ensembles avec lesquels ils partagent moins d'éléments (ils peuvent toujours avoir plus d'éléments de certains que les ensembles auxquels son nom a été attribué). !). Dans l'affirmative, attribuez ce nom à celui de S , S ' qui partage plus d'éléments avec l'ensemble respectif pour lequel ils peuvent rivaliser; l'autre conserve le nom anciennement conflictuel.$S'' \in P_1$$S, S'$
• Répétez cette procédure jusqu'à ce que tous les conflits soient résolus. Puisque n'a pas moins d'ensembles que P 2 , il y a suffisamment de noms.$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$$d_H(w_1, w_2)$