Clustering - Intuition hinter Kleinbergs Unmöglichkeitssatz

17

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 ΓRange(f) , gibt es positive reelle Zahlen a<b , so dass das Paar (a,b) ist Γ - 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)?

Gegenbeispiel?

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


Andere Papiere:

Alex Williams
quelle
In Bezug auf "Konsistenz": Diese Eigenschaft ist nur dann intuitiv erwünscht, wenn die Cluster bereits gut voneinander getrennt sind. Wenn dies nicht der Fall ist, gibt es ein Problem mit der Anzahl der Cluster in den Daten - für die Analyse ist dies eine Frage, da sie nicht überwacht werden. Dann ist es ganz normal zu erwarten, dass die Analyse die Zuweisungen während des Clusterprozesses ändert, wenn Sie den Abstand zwischen den Clustern (wie sie von Ihnen generiert wurden) allmählich erhöhen.
TTNPHNS
In Bezug auf "Reichtum": Es tut mir leid, dass ich nicht verstanden habe, was es bedeutet (zumindest, wie Sie es ausgedrückt haben). Clustering-Algorithmen gibt es viele. Wie können Sie davon ausgehen, dass sie alle bestimmten Anforderungen entsprechen?
TTNPHNS
In Bezug auf Ihr Bild: Um ein solches Muster zu erkennen, sind spezielle Clustering-Methoden erforderlich. Traditionelle / originelle Clustering-Methoden stammen aus der Biologie und Soziologie, wo Cluster mehr oder weniger kugelförmige "Inseln" sind, keine Atollringe. Diese Methoden können nicht verlangen, mit den Daten auf dem Bild fertig zu werden.
TTNPHNS
Das könnte Sie auch interessieren: Estivill-Castro, Vladimir. "Warum so viele Clustering-Algorithmen: ein Positionspapier." ACM SIGKDD Explorations Newsletter 4.1 (2002): 65-75.
Anony-Mousse
Ich habe die Zeitung nicht gelesen. In vielen Clustering-Algorithmen gibt es jedoch eine gewisse Distanzschwelle (z. B. DBSCAN, hierarchisches Clustering). Wenn Sie die Entfernungen skalieren, müssen Sie natürlich auch Ihren Schwellenwert entsprechend skalieren. Daher bin ich mit seiner Anforderung der Skaleninvarianz nicht einverstanden. Ich bin auch nicht einverstanden mit Reichtum. Nicht jede Partition muss für jeden Algorithmus eine gültige Lösung sein. Es gibt Millionen zufälliger Partitionen.
Anony-Mousse

Antworten:

11

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:S1S2270

zwei Sätze von 270 Punkten

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

1 mit Zoom einstellen

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:S2

set 2 mit zoom

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.S2S1S2S233×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 2k2-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):

Anhäufung von {Katze, Hund, Maus} gegen {Tom, Spike, Jerry}

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) kk

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 }SSS 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 .

Γ:{metrics on S}{partitions of S}dΓ(d)
iddSi:SSd(i(x),i(y))=d(x,y)xyS

Γddii(x)i(y)Γ(d)xyΓ(d)

SSS

eine Menge von Punkten in der Ebene und zwei Umdrehungen davon

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ΓdSd(x,y)=1xySΓΓ(d)Γ(d)Γ(d)Γ(d)dS1dΓ(d)=Γ(d)ΓΓ(d)dS1Γ(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.

Kommunikative Algebra
quelle
7

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

Bildbeschreibung hier eingeben

d1d2d3d2d3d1d1d3d2d3

Alex Williams
quelle
Meinst du unten links für d2? Das Schöne an Ihrem Diagramm ist, dass es zeigt, dass Konsistenz keine allgemein wünschenswerte Eigenschaft ist (oder dass sie zu locker formuliert ist).
xan
Ja, unten links, bearbeitete die Antwort entsprechend. Vielen Dank!
Alex Williams
Bevor ich Ihre Antwort vollständig verstanden habe, bin ich auf eine Logik gekommen, die sich als Ihre doppelte herausstellt: Beginnen Sie mit einem Clustering, bei dem sich alle Punkte in demselben Cluster befinden. Verwandeln Sie es in ein anderes Arrangement, indem Sie es in eine Miniaturversion eines anderen Arrangements verkleinern und auf eine Vollversion des anderen Arrangements skalieren.
xan