Wie misst man die Form eines Clusters?

14

Ich weiß, dass diese Frage nicht genau definiert ist, aber einige Cluster sind in der Regel elliptisch oder liegen im Raum niedrigerer Dimensionen, während die anderen nichtlineare Formen aufweisen (in 2D- oder 3D-Beispielen).

Gibt es ein Maß für die Nichtlinearität (oder "Form") von Clustern?

Beachten Sie, dass es im 2D- und 3D-Raum kein Problem ist, die Form eines Clusters zu erkennen, aber in höherdimensionalen Räumen ist es problematisch, etwas über die Form zu sagen. Gibt es insbesondere ein Maß dafür, wie konvex ein Cluster ist?

Ich wurde für diese Frage von vielen anderen Cluster-Fragen inspiriert, bei denen die Leute über Cluster sprechen, aber niemand sie sehen kann (in höherdimensionalen Räumen). Außerdem weiß ich, dass es für 2D-Kurven einige Maßeinheiten für die Nichtlinearität gibt.

Miroslav Sabo
quelle
1
en.wikipedia.org/wiki/Topological_data_analysis kann jedoch hilfreich sein, wenn die Form nicht genau dem entspricht, was Sie meinen.
Ziyuang
1
Vielleicht könnten Sie das Konzept der Kompaktheit für Ihren Zweck anpassen .
User12719

Antworten:

4

Ich mag Gaussian Mixture Modelle (GMM's).

Eines ihrer Merkmale ist, dass sie im Probit-Bereich wie stückweise Interpolatoren wirken. Dies impliziert unter anderem, dass sie als Ersatzbasis fungieren können, als universeller Approximator. Dies bedeutet, dass für nicht-gaußsche Verteilungen wie logarithmische, weibliche oder verrückte nicht-analytische Verteilungen, sofern einige Kriterien erfüllt sind, die GMM die Verteilung approximieren kann.

Wenn Sie also die Parameter der optimalen AICc- oder BIC-Approximation mit GMM kennen, können Sie diese auf kleinere Dimensionen projizieren. Sie können es drehen und die Hauptachsen der Komponenten des approximierenden GMM betrachten.

Die Folge wäre eine informative und visuell zugängliche Möglichkeit, die wichtigsten Teile höherdimensionaler Daten mithilfe unserer visuellen Wahrnehmung in 3D zu betrachten.

EDIT: (sicher, whuber)

Es gibt verschiedene Möglichkeiten, die Form zu betrachten.

  • Sie können Trends in den Mitteln betrachten. Ein Lognormal wird durch eine Reihe von Gaußschen approximiert, deren Mittel sich mit der Zeit immer mehr annähern und deren Gewichte mit der Zeit kleiner werden. Die Summe entspricht ungefähr dem schwereren Schwanz. In n-Dimensionen würde eine Folge solcher Komponenten eine Keule bilden. Sie können auch die Abstände zwischen den Mitteln (in hohe Bemaßung konvertieren) und den Richtungskosinus zwischen ihnen verfolgen. Dies würde zu viel leichter zugänglichen Dimensionen führen.
  • Sie können ein 3D-System erstellen, dessen Achsen das Gewicht, die Größe des Mittelwerts und die Größe der Varianz / Kovarianz sind. Wenn Sie eine sehr hohe Anzahl von Clustern haben, können Sie diese auf diese Weise im Vergleich zueinander anzeigen. Es ist eine wertvolle Möglichkeit, 50.000 Teile mit jeweils 2.000 Maßen in ein paar Wolken in einem 3D-Raum umzuwandeln. Ich kann die Prozesssteuerung in diesem Bereich ausführen, wenn ich möchte. Ich mag die Rekursion der Verwendung des Gaußschen Mischungsmodells, das auf der Steuerung von Komponenten des Gaußschen Mischungsmodells basiert, die an Teile-Parameter angepasst sind.
  • In Bezug auf die Unordnung können Sie nach sehr geringem Gewicht oder nach Gewicht pro Kovarianz oder dergleichen wegwerfen.
  • Sie können die GMM-Wolke in Bezug auf BIC, , Mahalanobis-Abstand zu Komponenten oder insgesamt, Wahrscheinlichkeit der Mitgliedschaft oder insgesamt darstellen. R2
  • Man könnte es so sehen, als würden sich Blasen kreuzen . Der Ort gleicher Wahrscheinlichkeit (null Kullback-Leibler-Divergenz) existiert zwischen jedem Paar von GMM-Clustern. Wenn Sie diese Position verfolgen, können Sie nach der Wahrscheinlichkeit der Mitgliedschaft an dieser Position filtern. Sie erhalten Punkte für die Klassifizierungsgrenzen. Dies wird Ihnen helfen, "Einzelgänger" zu isolieren. Sie können die Anzahl solcher Grenzen über dem Schwellenwert pro Mitglied zählen und eine Liste der "Verbundenheit" pro Komponente abrufen. Sie können auch Winkel und Entfernungen zwischen Standorten anzeigen.
  • Sie können den Raum unter Verwendung von Zufallszahlen aus den Gaußschen PDF-Dateien neu abtasten, dann eine Hauptkomponentenanalyse durchführen und die Eigenformen und die damit verbundenen Eigenwerte betrachten.

BEARBEITEN:

Was bedeutet Form? Sie sagen, Spezifität sei die Seele jeder guten Kommunikation. Was meinst du mit "messen"?

Ideen, was es bedeuten kann:

  • Augapfel Norm Sinn / Gefühl der allgemeinen Form. (extrem qualitative, visuelle Zugänglichkeit)
  • Maß für die GD & T-Form (Koplanarität, Konzentrizität usw.) (äußerst quantitativ)
  • etwas Numerisches (Eigenwerte, Kovarianzen, etc ...)
  • eine nützliche Koordinate mit reduzierter Dimension (wie GMM-Parameter zu Dimensionen werden)
  • ein reduziertes Geräuschsystem (irgendwie geglättet, dann präsentiert)

Bei den meisten "verschiedenen Möglichkeiten" handelt es sich um Variationen.

EngrStudent - Setzen Sie Monica wieder ein
quelle
3

Dies mag ziemlich simpel sein, aber Sie erhalten möglicherweise einen Einblick, indem Sie eine Eigenwertanalyse für jeden Ihrer Cluster durchführen.

Ich würde versuchen, alle einem Cluster zugewiesenen Punkte mit einem multivariaten Gaußschen Wert zu versehen. Dann können Sie die Eigenwerte der angepassten Kovarianzmatrix berechnen und grafisch darstellen. Es gibt viele Möglichkeiten, dies zu tun. Die wohl bekannteste und am weitesten verbreitete Methode wird als Hauptkomponentenanalyse oder PCA bezeichnet .

Sobald Sie die Eigenwerte haben (auch als Spektrum bezeichnet), können Sie deren relative Größe untersuchen, um festzustellen, wie "gestreckt" der Cluster in bestimmten Dimensionen ist. Je weniger einheitlich das Spektrum ist, desto "zigarrenförmiger" ist der Cluster, und je einheitlicher das Spektrum ist, desto kugelförmiger ist der Cluster. Sie könnten sogar eine Art Metrik definieren, die angibt, wie ungleichmäßig die Eigenwerte sind (spektrale Entropie?); siehe http://en.wikipedia.org/wiki/Spectral_flatness .

Als Nebeneffekt können Sie die Hauptkomponenten (die mit großen Eigenwerten verbundenen Eigenvektoren) untersuchen, um festzustellen, "wohin" die "zigarrenförmigen" Cluster in Ihrem Datenraum zeigen.

Dies ist natürlich eine grobe Näherung für einen beliebigen Cluster, da nur die Punkte im Cluster als einzelnes Ellipsoid modelliert werden. Aber wie gesagt, es könnte dir einen Einblick geben.

lmjohns3
quelle
+1 Einfach vielleicht; aber das sieht effektiv und praktisch aus. Die multivariate Gauß-Anpassung scheint keinen Vorteil zu haben: Verwenden Sie einfach die SVD der zentrierten Daten innerhalb des Clusters (bei der es sich im Wesentlichen um PCA auf dem Cluster handelt).
Whuber
@whuber ja, ich denke, dass diese das gleiche tun! Die Anpassung ist eher das, was der Theorie zufolge hinter den Kulissen geschieht, während PCA eine konkrete Implementierung dieses Prozesses ist. Ich bearbeite meine Antwort, um dies klarer zu machen.
lmjohns3
2

Korrelationscluster-Algorithmen wie 4C, ERiC oder LMCLUS betrachten Cluster normalerweise als lineare Mannigfaltigkeiten. Dh k-dimensionale Hyperebenen in einem d-dimensionalen Raum. Nun, für 4C und ERiC nur lokal linear, so dass sie tatsächlich nicht konvex sein können. Trotzdem versuchen sie, Cluster mit reduzierter lokaler Dimension zu erkennen.

Das Auffinden beliebig geformter Cluster in hochdimensionalen Daten ist ein recht schwieriges Problem. Insbesondere wegen des Fluchs der Dimensionalität, der den Suchraum explodieren lässt und gleichzeitig auch erfordert, dass Sie über viel größere Eingabedaten verfügen, wenn Sie weiterhin signifikante Ergebnisse erzielen möchten . Viel zu viele Algorithmen achten nicht darauf, ob das, was sie finden, noch signifikant ist oder auch zufällig sein könnte.

Tatsächlich glaube ich, dass es andere Probleme zu lösen gibt, bevor über die Konvexität der Nichtkonvexität komplexer Cluster im hochdimensionalen Raum nachgedacht wird.

Schauen Sie sich auch die Komplexität der Berechnung der konvexen Hülle in höheren Dimensionen an ...

Haben Sie auch einen echten Anwendungsfall, der keine Neugierde weckt?

Anony-Mousse - Setzen Sie Monica wieder ein
quelle
2

Wenn Ihre Dimensionalität nicht viel höher als 2 oder 3 ist, ist es möglicherweise möglich, den interessierenden Cluster mehrmals in den 2D-Raum zu projizieren und die Ergebnisse zu visualisieren oder Ihre 2D-Messung der Nichtlinearität zu verwenden. Ich dachte an die Methode Random Projections http://users.ics.aalto.fi/ella/publications/randproj_kdd.pdf .

Zufällige Projektionen können verwendet werden, um die Dimensionalität zu reduzieren und einen Index zu erstellen. Die Theorie besagt, dass wenn zwei Punkte in D-Dimensionen nahe beieinander liegen und Sie mit d eine zufällige Projektion in d-Dimensionen durchführen

Der Vollständigkeit halber können Sie sich vorstellen, einen Globus auf eine ebene Fläche zu projizieren. Egal wie Sie es planen, New York und New Jersey werden zusammen sein, aber nur selten werden Sie New York und London zusammenbringen.

Ich weiß nicht, ob dies Ihnen konsequent weiterhelfen kann, aber es könnte eine schnelle Möglichkeit sein, die Cluster zu visualisieren.

James
quelle