Bestimmen Sie verschiedene Cluster von 1d-Daten aus der Datenbank

24

Ich habe eine Datenbanktabelle von Datenübertragungen zwischen verschiedenen Knoten. Dies ist eine riesige Datenbank (mit fast 40 Millionen Überweisungen). Eines der Attribute ist die Anzahl der Bytes (nBytes), die zwischen 0 Byte und 2 Terabytes übertragen werden. Ich möchte die nbytes so gruppieren, dass gegebene k Cluster einige x1 Übertragungen zu k1 Cluster gehören, x2 Übertragungen zu k2 usw.

Anhand der von mir verwendeten Terminologie hätten Sie vielleicht erraten, was ich vorhatte: K-means. Dies sind 1d-Daten, da mir nur nbytes am Herzen liegen. Als ich nach anderen Methoden suchte, sah ich, dass die EM einige Male zusammen mit einem Nicht-Clustering-Ansatz erwähnt wurde. Ich würde gerne wissen, wie Sie dieses Problem angehen (insbesondere, ob Sie sich zu Clustern zusammenschließen oder nicht).

Vielen Dank!

clustering k-means Shaun
quelle
Was sind "x1 Transfers", "x2 Transfers" usw.? Ist "Übertragungstyp" eine zweite Variable?
Peter Flom - Wiedereinsetzung von Monica
x1-Übertragungen sind für mich nur eine Möglichkeit zu sagen, dass diese 500 Übertragungen eine Übertragungsgröße um einen bestimmten Wert haben (dies wäre der Mittelwert für diesen Cluster in k-Mitteln).
Shaun
5
Ich bin kein Experte für Clustering, aber mit so vielen Daten und nur einer Dimension. Ich frage mich, ob Sie einfach einige Kernel-Dichtediagramme mit unterschiedlichen Bandbreiten erstellen und sehen können, wie viele Modi / Peaks Sie finden und ob das Ergebnis so aussieht es wäre nützlich für dich.
gung - Wiedereinsetzung von Monica
1
Sie haben gefragt, ob ein Cluster erstellt werden soll oder nicht. Was wäre Ihr Ziel beim Clustering? Würden Sie die Cluster für einen anderen Zweck verwenden, oder ist dies von theoretischem Interesse?
Peter Flom - Wiedereinsetzung von Monica
Einige der anderen Attribute aus der Tabelle sind Benutzername, Start- und Enddatum. Ich hoffe, dass ich durch Gruppierung der Übertragungen nach Übertragungsgröße auf andere Attribute einer bestimmten Übertragung verweisen kann, um zu sehen, wer in welchem ​​Monat des Jahres wie viel überträgt. Was wir mit dieser Beobachtung anfangen werden, weiß ich noch nicht. Aber so gehe ich jetzt.
Shaun

Antworten:

43

Verwenden Sie in eindimensionalen Daten keine Clusteranalyse.

Die Clusteranalyse ist normalerweise eine multivariate Technik. Oder lassen Sie es mich besser andersherum sagen: Für eindimensionale Daten - die vollständig geordnet sind - gibt es viel bessere Techniken. Die Verwendung von k-means und ähnlichen Techniken ist hier eine völlige Verschwendung, es sei denn, Sie unternehmen genug Aufwand, um sie tatsächlich für den 1-d-Fall zu optimieren.

Nur um Ihnen ein Beispiel zu geben: Für k-means ist es üblich, k zufällige Objekte als Ausgangssamen zu verwenden. Für eindimensionale Daten ist es relativ einfach, die entsprechenden Quantile (1 / 2k, 3 / 2k, 5 / 2k usw.) zu verwenden, nachdem Sie die Daten einmal sortiert und dann von diesem Ausgangspunkt aus optimiert haben. 2D-Daten können jedoch nicht vollständig sortiert werden. Und in einem Gitter werden wahrscheinlich leere Zellen vorhanden sein.

Ich würde es auch nicht Cluster nennen. Ich würde es Intervall nennen . Was Sie wirklich tun möchten, ist die Intervallgrenzen zu optimieren. Wenn Sie k-means verwenden, wird für jedes Objekt geprüft, ob es in einen anderen Cluster verschoben werden soll. Dies ist in 1D nicht sinnvoll: Es müssen nur die Objekte an den Intervallgrenzen überprüft werden. Das ist natürlich viel schneller, da es dort nur ~ 2k Objekte gibt. Wenn sie nicht bereits andere Intervalle bevorzugen, werden zentralere Objekte auch nicht.

Möglicherweise möchten Sie Techniken wie beispielsweise die Optimierung von Jenks Natural Breaks untersuchen .

Oder Sie können eine Schätzung der Kerneldichte durchführen und nach lokalen Minima der Dichte suchen, die dort aufgeteilt werden sollen. Das Schöne ist, dass Sie dafür nicht k angeben müssen!

PS Bitte benutzen Sie die Suchfunktion. Hier sind einige Fragen zu 1-D-Datenclustern, die Sie verpasst haben:

Anony-Mousse
quelle
Quantile stimmen nicht unbedingt mit Clustern überein. Eine 1d-Verteilung kann drei natürliche Cluster haben, wobei zwei jeweils 10% der Daten enthalten und der letzte 80% der Daten enthält. Daher denke ich, dass es hier möglich ist, Cluster zu bilden, obwohl es meiner Meinung nach sinnvoll ist, den Lauf zu optimieren, indem man Samen intelligent pflückt usw. oder andere Ideen verwendet.
Bitweise
Die Quantile sind wahrscheinlich gute Ausgangspunkte für die Optimierung , das war es, worauf ich mich bezog. Und um nur ein Beispiel zu geben, was Sie in 1D tun können, das in 2+ Dimensionen nicht so gut funktioniert.
Anony-Mousse
Ich stimme zu, dass es einen Versuch wert wäre, Quantile als Startwerte zu verwenden, aber ich würde trotzdem einige zufällige Initialisierungen versuchen (zum Beispiel die, die ich gegeben habe). In jedem Fall ist es die beste Methode, nur das Histogramm / Dichtediagramm zu betrachten, manuell Startwerte auszuwählen und diese dann mit dem Clustering zu optimieren. Das wird sehr schnell zu einer guten Lösung führen.
Bitweise
3
Jenks ist k-means in 1D.
Whuber
1
@whuber auch wenn es mathematisch ist, ich hoffe er war schlau genug auszunutzen, dass die Daten bestellt werden können . Wenn Sie den Lloyd-Ansatz verwenden, um k-means auf 1-d-Daten anzuwenden, sind Sie dumm, weil Sie eine Menge Berechnungen durchführen, die Sie überspringen könnten. Und für die meisten Menschen ist k-means Lloyd. Und manchen ist es wichtig, unnötige Neuberechnungen zu vermeiden.
Anony-Mousse
1

Ist Ihre Frage, ob Sie Clustering durchführen sollen oder welche Methode Sie zum Clustering verwenden sollten?

Ob Sie Clustering durchführen, hängt davon ab, ob Sie Ihre Daten automatisch partitionieren möchten (z. B. wenn Sie diese Partitionierung mehrmals wiederholen möchten). Wenn Sie dies nur einmal tun, können Sie sich das Histogramm der Verteilung Ihrer Werte ansehen und es nach Augenmaß aufteilen, wie in den Kommentaren vorgeschlagen. Ich würde es trotzdem empfehlen, die Daten mit dem Auge zu betrachten, da es Ihnen dabei helfen könnte, festzustellen, wie viele Cluster Sie möchten und ob das Clustering "funktioniert".

In Bezug auf die Art der Clusterung sollte k-means in Ordnung sein, wenn die Daten "echte" Cluster enthalten. Wenn Sie keine Cluster im Histogramm sehen, ist es ohnehin nicht sinnvoll, sie zu gruppieren, da eine Aufteilung Ihres Datenbereichs gültige Cluster ergibt (oder im Fall einer zufälligen Initiierung von kmeans unterschiedliche Cluster erhalten jeder Lauf).

Bitweise
quelle