Clustering-Vergleich: Rand-Index vs. Variation of Information

Ich habe mich gefragt, ob jemand einen Einblick oder eine Intuition hinter dem Unterschied zwischen der Variation of Information und dem Rand-Index zum Vergleichen von Clusterings hat.

Ich habe den Artikel " Clustering - An Information Based Distance " von Marina Melia (Journal of Multivariate Analysis, 2007) gelesen , aber abgesehen von den Unterschieden in den Definitionen verstehe ich nicht, was die Variation von Informationen ist erfasst, dass der Rand-Index nicht erfasst.

Der Unterschied zwischen den beiden Methoden ist subtil. Der beste Weg, darüber nachzudenken, besteht darin, das Gitter zu betrachten, das durch die Merge-Split-Operation für Cluster definiert wird. Diese beiden Kennzahlen können rekonstruiert werden, indem eine Funktion in einem Cluster definiert und anschließend der Abstand zwischen zwei Cluster durch die Formel definiert wird:$f$

wobei C ∧ C ' die Verbindung der beiden Cluster im Gitter ist.

Nun sei und sei n i = | C i | . Das Setzen von f ( C ) = ∑ n 2 i ergibt den Randindex und das Setzen von f ( C ) = ∑ n i log n i ergibt VI.$C = \{ C_1, C_2, \ldots, C_k\}$$n_i = |C_i|$$f(C) = \sum n_i^2$$f(C) = \sum n_i \log n_i$

Meiner Meinung nach gibt es große Unterschiede. Der Rand-Index wird stark von der Granularität der Clusterings beeinflusst, mit denen er arbeitet. Im Folgenden werde ich den Mirkin-Abstand verwenden, der eine angepasste Form des Rand-Index ist (leicht zu sehen, aber siehe z. B. Meila). Ich werde auch die Aufteilungs- / Verbindungsentfernung verwenden, die auch in einigen Beiträgen von Meila erwähnt wird (Haftungsausschluss: Aufteilungs- / Verbindungsentfernung wurde von mir vorgeschlagen). Angenommen, ein Universum aus einhundert Elementen. Ich werde Top verwenden, um das Clustering mit einem einzelnen Cluster zu bezeichnen, der alle Elemente enthält. Bottom, um das Clustering zu bezeichnen, bei dem sich alle Knoten in separaten Singleton-Mengen befinden. Left, um das Clustering zu bezeichnen. {{1,2, .. 10}, {11, 12..20}, {21,22..30}, ..., {91,92, .. 100} und Recht zur Bezeichnung der Clusterbildung {{1,11, .. 91}, {2, 12, .. 92}, {3,13, .. 93}, ..., {10,20, .. 100}}.

Für mich sind Bottom und Top konsistente (verschachtelte) Cluster, wohingegen Left und Right maximal widersprüchliche Cluster sind. Die Abstände von den genannten Metriken für diese beiden paarweisen Vergleiche sind wie folgt:

               Top-Bottom     Left-Right 

Mirkin            9900          1800
VI                4.605         4.605
Split/join        99            180

Daraus folgt, dass Mirkin / Rand das konsistente Top-Bottom-Paar viel weiter auseinander halten als das maximal widersprüchliche Left-Right-Paar. Dies ist ein extremes Beispiel, um den Punkt zu veranschaulichen, aber Mirkin / Rand sind im Allgemeinen sehr stark von der Granularität der Clustering betroffen, auf die es angewendet wird. Der Grund Dahinter ist eine quadratische Beziehung zwischen dieser Metrik und Clustergrößen, durch die Tatsache erklärt , dass die Zählung von Paaren von Knoten , beteiligt ist. Tatsächlich ist der Mirkin-Abstand ein Hamming-Abstand zwischen Kantensätzen von Vereinigungen vollständiger Graphen, die durch Clustering induziert werden (dies ist die Antwort auf Ihre Frage, denke ich).

In Bezug auf die Unterschiede zwischen Variation of Information und Split / Join ist der erste, wie von Meila gezeigt, empfindlicher gegenüber bestimmten Konfliktsituationen. Das heißt, Split / Join berücksichtigt nur die beste Übereinstimmung für jeden Cluster und ignoriert die Fragmentierung, die im verbleibenden Teil dieses Clusters auftreten kann, während Variation of Information dies aufgreift. Das heißt, Split / Join ist leicht als die Anzahl der Knoten zu interpretieren , die verschoben werden müssen, um einen Cluster vom anderen zu erhalten , und in diesem Sinne ist sein Bereich leichter zu verstehen. In der Praxis ist das Fragmentierungsproblem möglicherweise auch nicht so häufig.

Jede dieser Metriken kann als die Summe von zwei Abständen gebildet werden, nämlich die Abstände von jedem der beiden Cluster zu ihrem größten gemeinsamen Subcluster. Ich halte es oft für vorteilhaft, mit diesen einzelnen Teilen zu arbeiten und nicht nur mit ihrer Summe. Die obige Tabelle wird dann:

               Top-Bottom     Left-Right 

Mirkin          0,9900          900,900
VI              0,4.605       2.303,2.303
Split/join      0,99             90,90

Die Subsumtionsbeziehung zwischen Oben und Unten wird sofort klar. Es ist oft sehr nützlich zu wissen, ob zwei Cluster konsistent sind (dh eines ist (fast) ein Subcluster des anderen), um die Frage zu lösen, ob sie nahe beieinander liegen . Ein Clustering kann von einem Goldstandard ziemlich weit entfernt sein, aber dennoch konsistent oder nahezu konsistent sein. In einem solchen Fall gibt es möglicherweise keinen Grund, die Clusterbildung in Bezug auf diesen Goldstandard als schlecht zu betrachten. Natürlich stimmen die trivialen Cluster von oben und unten mit allen Cluster überein , daher muss dies berücksichtigt werden.

Schließlich glaube ich, dass Metriken wie Mirkin, Variation of Information und Split / Join die natürlichen Werkzeuge sind, um Clustering zu vergleichen. Für die meisten Anwendungen sind Methoden, die versuchen, statistische Unabhängigkeit und Zufallskorrektur zu berücksichtigen, zu aufwendig und verschwommen, anstatt zu klären.

Zweites Beispiel Betrachten Sie die folgenden Clusterpaare: C1 = {{1, 2, 3, 4, 5, 6, 7, 8}, {9, 10, 11, 12, 13, 14, 15, 16}} mit C2 = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}}

und C3 = {{1, 2, 3, 4}, {5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}} mit {{1, 2, 3 , 4}, {5, 6, 7, 8, 9, 10, 11, 12}, {13, 14, 15, 16}}

Hier kann C2 aus C1 gebildet werden, indem die Knoten 9 und 10 bewegt werden, und C3 kann aus C3 gebildet werden, indem die Knoten 11 und 12 bewegt werden. Beide Änderungen sind identisch ("zwei Knoten bewegen"), außer dass sich die Größen der beteiligten Cluster unterscheiden . Die Clustering-Metriktabelle für diese beiden Beispiele lautet wie folgt:

            C1-C2         C3-C4

Mirkin       56            40 
VI            0.594         0.520
Split/Join    4             4

Es ist zu sehen, dass Mirkin / Rand und Variation of Information von den Clustergrößen (und Mirkin in größerem Ausmaß; dies wird deutlicher, wenn die Clustergrößen voneinander abweichen) beeinflusst werden, während der Split / Join-Abstand nicht (sein Wert ist 4) während es Knoten von einem Cluster zum anderen "verschiebt" (immer über das größte gemeinsame Subclustering). Dies kann abhängig von den Umständen ein wünschenswertes Merkmal sein. Die einfache Interpretation von Split / Join (Anzahl der zu verschiebenden Knoten) und die Unabhängigkeit von der Clustergröße sind erwähnenswert. Zwischen Mirkin und Variation of Information halte ich Letzteres für sehr vorzuziehen.