Ich habe darüber nachgedacht, einen Blogbeitrag zu dieser interessanten Analyse von Kleinberg (2002) zu schreiben , in dem die Schwierigkeit der Clusterbildung untersucht wird. Kleinberg skizziert drei scheinbar intuitive Desiderata für eine Clustering-Funktion und beweist dann, dass keine solche Funktion existiert. Es gibt viele Cluster-Algorithmen, die zwei der drei Kriterien erfüllen. Es kann jedoch keine Funktion alle drei gleichzeitig erfüllen.

Kurz und informell sind die drei von ihm skizzierten Desiderata:

• Skaleninvarianz : Wenn wir die Daten so transformieren, dass alles in alle Richtungen gleichmäßig verteilt ist, sollte sich das Clustering-Ergebnis nicht ändern.
• Konsistenz : Wenn wir die Daten so strecken, dass die Abstände zwischen Clustern zunehmen und / oder die Abstände innerhalb von Clustern abnehmen, sollte sich das Clustering-Ergebnis nicht ändern.
• Reichhaltigkeit : Die Clustering-Funktion sollte theoretisch in der Lage sein, beliebige Partitionen / Clustering von Datenpunkten zu erzeugen (wenn der paarweise Abstand zwischen zwei Punkten nicht bekannt ist).

Fragen:

(1) Gibt es eine gute Intuition, ein geometrisches Bild, das die Inkonsistenz zwischen diesen drei Kriterien aufzeigen kann?

(2) Dies bezieht sich auf technische Details des Papiers. Sie müssen den obigen Link lesen, um diesen Teil der Frage zu verstehen.

In der Arbeit fällt es mir etwas schwer, dem Beweis zu Satz 3.1 an bestimmten Stellen zu folgen. Ich bin fest an: „Lassen Sie $f$ . Eine Clustering - Funktion, die erfüllt sein Consistency Wir behaupten , dass für jede Partition $\Gamma \in \text{Range}(f)$ , gibt es positive reelle Zahlen $a < b$ , so dass das Paar $(a, b)$ ist $\Gamma$ - zwingen. "

Ich verstehe nicht, wie dies der Fall sein kann ... Ist die Partition unter einem Gegenbeispiel nicht so, dass $a > b$ (dh der minimale Abstand zwischen Clustern ist größer als der maximale Abstand innerhalb von Clustern)?

Edit: das ist eindeutig kein Gegenbeispiel, ich habe mich verwirrt (siehe Antworten).

• Ackerman & Ben-David (2009). Qualitätsmaßstäbe für Clustering: Ein Arbeitssatz von Axiomen für Clustering
  • Weist auf einige Probleme mit dem Grundsatz der "Konsistenz" hin

Auf die eine oder andere Weise beruht jeder Clustering-Algorithmus auf dem Begriff der „Nähe“ von Punkten. Es scheint intuitiv klar zu sein, dass Sie entweder einen relativen (skaleninvarianten) Begriff oder einen absoluten (konsistenten) Begriff der Nähe verwenden können, aber nicht beide .

Ich werde zunächst versuchen, dies anhand eines Beispiels zu veranschaulichen, und dann erläutern, wie diese Intuition zum Satz von Kleinberg passt.

Ein anschauliches Beispiel

Angenommen, wir haben zwei Mengen und S 2 mit jeweils 270 Punkten, die in der Ebene wie folgt angeordnet sind:$S_1$$S_2$$270$

$\hskip{6em}$

Möglicherweise sehen Sie in keinem dieser Bilder Punkte, aber das liegt nur daran, dass viele der Punkte sehr nahe beieinander liegen. Wir sehen mehr Punkte, wenn wir hineinzoomen:$270$

$\hskip{3em}$

Sie werden wahrscheinlich spontan zustimmen, dass in beiden Datensätzen die Punkte in drei Clustern angeordnet sind. Es stellt sich jedoch heraus, dass, wenn Sie einen der drei Cluster von vergrößern , Folgendes angezeigt wird:$S_2$

$\hskip{3em}$

Wenn Sie an einen absoluten Begriff von Nähe oder Konsistenz glauben, werden Sie immer noch behaupten, dass aus nur drei Clustern besteht , unabhängig davon, was Sie gerade unter dem Mikroskop gesehen haben . In der Tat besteht der einzige Unterschied zwischen S 1 und S 2 darin, dass innerhalb jedes Clusters einige Punkte jetzt näher beieinander liegen. Wenn Sie andererseits an einen relativen Begriff der Nähe oder der Skaleninvarianz glauben, werden Sie sich geneigt fühlen zu argumentieren, dass S 2 nicht aus 3, sondern aus 3 × 3 = 9 Clustern besteht. Keine dieser Ansichten ist falsch, aber Sie müssen die eine oder andere Wahl treffen.$S_2$$S_1$$S_2$$S_2$$3$$3×3 = 9$

Ein Fall für die Invarianz der Isometrie

Wenn Sie die obige Intuition mit Kleinbergs Theorem vergleichen, werden Sie feststellen, dass sie leicht uneins sind. In der Tat scheint Kleinbergs Theorem zu besagen, dass Sie Skaleninvarianz und -konsistenz gleichzeitig erreichen können , solange Sie sich nicht für eine dritte Eigenschaft interessieren, die als Reichhaltigkeit bezeichnet wird. Der Reichtum ist jedoch nicht die einzige Eigenschaft, die Sie verlieren, wenn Sie gleichzeitig auf Skaleninvarianz und Konsistenz bestehen. Sie verlieren auch eine andere, grundlegendere Eigenschaft: die Isometrie-Invarianz. Dies ist eine Eigenschaft, die ich nicht zu opfern bereit wäre. Da es in Kleinbergs Zeitung nicht vorkommt, werde ich mich kurz damit befassen.

Kurz gesagt, ein Clustering-Algorithmus ist isometrieunabhängig, wenn seine Ausgabe nur von den Abständen zwischen Punkten abhängt und nicht von zusätzlichen Informationen wie Beschriftungen, die Sie an Ihre Punkte anbringen, oder von einer Reihenfolge, die Sie Ihren Punkten auferlegen. Ich hoffe, das klingt nach einem sehr milden und sehr natürlichen Zustand. Alle in Kleinbergs Aufsatz diskutierten Algorithmen sind isometrieinvariant, mit Ausnahme des Einzelverknüpfungsalgorithmus mit der Cluster-Stoppbedingung. Laut Kleinbergs Beschreibung verwendet dieser Algorithmus eine lexikografische Anordnung der Punkte, sodass die Ausgabe davon abhängen kann, wie Sie sie beschriften. Zum Beispiel für einen Satz von drei äquidistanten Punkten die Ausgabe des Einfachverknüpfungsalgorithmus mit der $k$$2$-Cluster-Stoppbedingung gibt unterschiedliche Antworten, je nachdem, ob Sie Ihre drei Punkte als "Katze", "Hund", "Maus" (c <d <m) oder als "Tom", "Spike", "Jerry" (J <S <T):

$\hskip{6em}$

Dieses unnatürliche Verhalten kann natürlich leicht behoben werden, indem die Cluster-Stoppbedingung durch eine " ( ≤ k ) -Cluster-Stoppbedingung" ersetzt wird. Die Idee ist einfach , die Verbindungen zwischen äquidistanten Punkten nicht zu unterbrechen und das Zusammenführen von Clustern zu beenden, sobald wir höchstens k Cluster erreicht haben. Dieser reparierte Algorithmus erzeugt die meiste Zeit immer noch k Cluster und ist isometrieinvariant und maßstabsinvariant. In Übereinstimmung mit der oben gegebenen Intuition wird es jedoch nicht länger konsistent sein.$k$$(≤ k)$ $k$$k$

Zur genauen Definition der Isometrie-Invarianz sei daran erinnert, dass Kleinberg einen Clustering-Algorithmus auf einer endlichen Menge als eine Karte definiert, die jeder Metrik auf S eine Partition von S zuweist : Γ : { Metriken auf  S } → { Partitionen von  S $S$$S$$S$ EineIsometrie i zwischen zwei Metriken d und d ' auf S ist eine Permutation i : S → S, so dass d ' ( i ( x ) , i ( y ) ) = d ( x , y ) für alle Punkte x und y in S .

$Γ$$d$$d'$$i$$i(x)$$i(y)$$Γ(d')$$x$$y$$Γ(d)$

$S$$S$$S$

$\hskip{6em}$

Eine Variante des Satzes von Kleinberg

Die oben gegebene Intuition wird durch die folgende Variante des Satzes von Kleinberg eingefangen.

Theorem: Es gibt keinen nicht-trivialen isometrieinvarianten Clustering-Algorithmus, der gleichzeitig konsistent und skalierungsinvariant ist.

Hier meine ich mit einem einfachen Clustering-Algorithmus einen der folgenden beiden Algorithmen:

1. $S$

2. $S$

Die Behauptung ist, dass diese albernen Algorithmen die einzigen zwei isometrieinvarianten Algorithmen sind, die sowohl konsistent als auch skalainvariant sind.

$S$$Γ$$d₁$$S$$d₁(x,y) = 1$$x ≠ y$$S$$Γ$$Γ(d₁)$$Γ(d₁)$$Γ(d₁)$$Γ(d₁)$$d$$S$$≥ 1$$d$$Γ(d) = Γ(d₁)$$Γ$$Γ(d₁)$$d$$S$$≤ 1$$Γ(d)=Γ(d₁)$$Γ$

Natürlich ist dieser Beweis sehr ähnlich zu Margareta Ackermans Beweis von Kleinbergs ursprünglichem Theorem, der in Alex Williams 'Antwort diskutiert wird.

Dies ist die Intuition, die ich mir ausgedacht habe (ein Ausschnitt aus meinem Blog-Beitrag hier ).

$d_1$$d_2$$d_3$$d_2$$d_3$$d_1$$d_1 \rightarrow d_3$$d_2 \rightarrow d_3$