Abstand zwischen zwei Partitionen bearbeiten

17

Ich habe zwei Partitionen von und suche nach dem Bearbeitungsabstand zwischen ihnen.[1n]

Auf diese Weise möchte ich die minimale Anzahl von einzelnen Übergängen eines Knotens in eine andere Gruppe finden, die erforderlich sind, um von Partition A zu Partition B zu gelangen.

Zum Beispiel wäre der Abstand von {0 1} {2 3} {4}in {0} {1} {2 3 4}zwei

Nach der Suche bin ich auf dieses Papier gestoßen, aber a) ich bin nicht sicher, ob sie die Reihenfolge der Gruppen (etwas, das mir egal ist) in ihrer Entfernung berücksichtigen. B) ich bin nicht sicher, wie es funktioniert und c) Es gibt keine Referenzen.

Jede Hilfe dankbar

zenna
quelle
5
Wie groß ist die Entfernung zwischen {0 1 2 3} und {0 1} {2 3}? Wäre es 2? Zweitens verstehe ich nicht, warum überhaupt "Graphen" ins Bild kommen. Es hört sich so an, als hätten Sie zwei Partitionen von [n] und möchten einen Abstand zwischen ihnen berechnen.
Suresh Venkat
Ja, es wären zwei. In der Tat sind dies festgelegte Partitionen auf den Knoten eines Graphen (dh eine Graphenpartition). Dies ist wahrscheinlich nicht wichtig für die Lösung, aber dies ist das Problem, das ich zu lösen versuche, daher habe ich es erwähnt.
Zenna
3
Wenn das Diagramm irrelevant ist, entfernen Sie bitte alle Verweise auf "Diagramme" und "Knoten" aus Ihrer Frage. es hilft nicht, es lenkt ab.
Jukka Suomela
Kann der Bearbeitungsabstand nicht in Bezug auf den Abstand auf dem Partitionsgitter definiert werden?
Tegiri Nenashi
@Tegiri - Es ist in der Tat die geodätische Entfernung auf dem Partitonengitter. Leider ist die Berechnung dieses Gitters für eine beliebige Menge von Kardinalitäten, die viel größer als 10 ist, nicht möglich.
Zenna

Antworten:

21

Dieses Problem kann in das Zuordnungsproblem umgewandelt werden , das auch als maximal gewichtetes zweiteiliges Übereinstimmungsproblem bezeichnet wird.

Beachten Sie zunächst, dass der Bearbeitungsabstand der Anzahl der Elemente entspricht, die von einem Satz zum anderen geändert werden müssen. Dies entspricht der Gesamtzahl der Elemente abzüglich der Anzahl der Elemente, die nicht geändert werden müssen. Das Ermitteln der minimalen Anzahl von Elementen, die sich nicht ändern, entspricht dem Ermitteln der maximalen Anzahl von Scheitelpunkten, die sich nicht ändern.

Sei und Partitionen von . Auch ohne Verlust der Allgemeinheit sei (erlaubt, weil ). Dann sei , , ..., die leere Menge. Dann ist die maximale Anzahl von Scheitelpunkten, die sich nicht ändern:B = { B 1 , B 2 , . . . , B l } [ 1 , 2 , . . . , N ] k l e d i t ( A , B ) = e d i t (A={A1,A2,...,Ak}B={B1,B2,...,Bl}[1,2,...,n]klB L + 1 B l + 2 B kedit(A,B)=edit(B,A)Bl+1Bl+2Bk

maxfi=1k|AiBf(i)|

wobei eine Permutation von .[ 1 , 2 , . . . , k ]f[1,2,...,k]

Dies ist genau das Zuordnungsproblem, bei dem die Eckpunkte , ..., , , ..., und die Kanten Paare mit dem Gewicht. Dies kann in gelöst werden.A k B 1 B k ( A i , B j ) | A iB j | O ( | V | 2 log | V | + | V | | E | )A1AkB1Bk(Ai,Bj)|AiBj|O(|V|2log|V|+|V||E|)

bbejot
quelle
Könnten Sie den Algorithmus nennen, der diesmal bitte Komplexität verleiht?
D-503
Ich glaube, @bbejot bezieht sich auf den sukzessiven Shortest-Path-Algorithmus (mit der Subroutine Dijkstra, die mit Hilfe von Fibonacci-Heaps implementiert wurde).
Wei
Ich habe lange gebraucht, um das zu analysieren, weil ich kein Mathematiker bin, aber danke. Ich habe lange gesucht und nur so konnte ich das Problem der Partitionsentfernung in ein Zuweisungsproblem umwandeln - oder in einen beliebigen Algorithmus, den ich aus einer Python-Bibliothek aufrufen konnte. (Der schwierige Teil für mich war, herauszufinden, wie man scipy.optimize.linear_sum_assignment verwendet und dann die Matrizen basierend auf diesen Anweisungen erstellt.)
Sigfried
Ich musste die Gewichte negativ machen. Ansonsten gibt mir scipy.optimize.linear_sum_assignment für alles 0.
Sigfried
2

Schauen Sie sich das PDF dieses Papiers an

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

Die Definition des Bearbeitungsabstands ist genau das, was Sie brauchen, denke ich. Die 'Referenz'-Partition wäre (eine beliebige) Ihrer beiden Partitionen, die andere wäre einfach die andere. Enthält auch relevante Zitate.

Am besten, Rob

rauben
quelle
Vielen Dank, Rob. Sofern mir nichts fehlt, ist dies jedoch eine Bearbeitungsentfernung, die in Form von Split-Merge-Bewegungen definiert ist. Diese sind gut untersucht, und die Variation von Informationen ist, wie der Aufsatz hervorhebt, ein informationstheoretisches Maß dafür. Ich interessiere mich jedoch für einzelne Elementbewegungsübergänge.
Zenna
1

Verschrobener Sonntagmorgen-Gedanke, der richtig oder falsch sein könnte:

Wlog, sei die Partition mit mehr Mengen, die andere. zunächst Ihren Mengen paarweise unterschiedliche Namen zu . Dann finden Sie eine beste Benennung für die Mengen nach den folgenden Regeln:P 2 N - 1 ( S ) & Sigma; P 1 n 2 ( S ) , P 2P1P2n1(S)ΣP1n2(S)P2

  • S P 2 S S ' S 'P 1n2(S):=n1(S) für mit maximal unter allen ; Wählen Sie den Konflikt aus, der am wenigsten Konflikte verursacht, wenn Mehrfachauswahl möglich ist.SP2SSSP1
  • Wenn nun für einige , ordne diejenige zu, die weniger Elemente mit teilt , der Name der Menge in teilt es die zweithäufigsten Elemente mit, dh lässt es um den Namen dieser Menge konkurrieren.n2(S)=n2(S)SSS,n1(S)=n2(S)P1
  • Wenn die frühere Regel nicht angewendet werden kann, prüfen Sie, ob beide Mengen um den Namen anderer Mengen konkurrieren können, mit denen sie weniger Elemente gemeinsam haben (sie enthalten möglicherweise noch mehr Elemente aus einigen als die Mengen, denen sie zugewiesen wurden Name!). Wenn ja, weisen Sie diesen Namen dem Namen von , der mehr Elemente mit der jeweiligen Menge teilt, um deren Namen sie konkurrieren können. der andere behält den früher widersprüchlichen Namen.SP1S,S
  • Wiederholen Sie diesen Vorgang, bis alle Konflikte gelöst sind. Da nicht weniger Mengen als , gibt es genügend Namen.P1P2

Nun können Sie die Bitfolgen Ihrer Elemente in jeder Partition betrachten, dh und . mit ). Die gewünschte Größe ist dann , dh der Hamming-Abstand zwischen den Bitfolgen.w 2 = n 2 ( 1 ) n 2 ( n ) n j ( i ) = n j ( S ) , i S P j d H ( w 1 , w 2 )w1=n1(1)n1(n)w2=n2(1)n2(n)nj(i)=nj(S),iSPjdH(w1,w2)

Raphael
quelle