1D Number Array Clustering

74

Nehmen wir also an, ich habe ein Array wie dieses:

[1,1,2,3,10,11,13,67,71]

Gibt es eine bequeme Möglichkeit, das Array in so etwas zu partitionieren?

[[1,1,2,3],[10,11,13],[67,71]]

Ich habe ähnliche Fragen durchgesehen, aber die meisten Leute schlugen vor, k-means zu verwenden, um Punkte wie scipy zu gruppieren , was für einen Anfänger wie mich ziemlich verwirrend ist. Ich denke auch, dass k-means besser für zwei oder mehr dimensionale Cluster geeignet ist, oder? Gibt es Möglichkeiten, ein Array von N Zahlen abhängig von den Zahlen in viele Partitionen / Cluster zu unterteilen?

Einige Leute schlagen auch eine starre Bereichspartitionierung vor, aber die Ergebnisse werden nicht immer wie erwartet wiedergegeben

arrays cluster-analysis data-mining dimension partition-problem EH
quelle

Antworten:

112

Verwenden Sie keine mehrdimensionalen Clustering-Algorithmen für ein eindimensionales Problem. Eine einzelne Dimension ist viel spezieller als Sie naiv denken, weil Sie sie tatsächlich sortieren können, was die Dinge viel einfacher macht.

Tatsächlich wird es normalerweise nicht einmal als Clustering bezeichnet, sondern z. B. als Segmentierung oder Optimierung natürlicher Brüche.

Vielleicht möchten Sie sich Jenks Natural Breaks Optimization und ähnliche statistische Methoden ansehen . Die Kernel-Dichteschätzung ist auch eine gute Methode mit einem starken statistischen Hintergrund. Lokale Minima in der Dichte sind gute Orte, um die Daten aus statistischen Gründen in Cluster aufzuteilen. KDE ist möglicherweise die beste Methode zum Clustering eindimensionaler Daten.

Mit KDE wird wieder deutlich, dass sich eindimensionale Daten viel besser verhalten. In 1D haben Sie lokale Minima; aber in 2D können Sie Sattelpunkte und solche "vielleicht" Aufteilungspunkte haben. Sehen Sie sich diese Wikipedia-Abbildung eines Sattelpunkts an , wie ein solcher Punkt zum Teilen von Clustern geeignet sein kann oder nicht.

In dieser Antwort finden Sie ein Beispiel für die Vorgehensweise in Python (grüne Markierungen sind die Cluster-Modi; rote Markierungen Punkte, an denen die Daten geschnitten werden; die y-Achse ist eine logarithmische Wahrscheinlichkeit der Dichte):

KDE mit Python

Hat aufgehört - Anony-Mousse
quelle
2
Implementierung hier: macwright.org/2013/02/18/literate-jenks.html
Tirno
Könnten Sie Ihre Antwort mit dem Grund aktualisieren, warum meanshiftoder dbscanmöglicherweise keine guten Ansätze für das Clustering von 1D vorliegen? Siehe scikit-learn.org/stable/modules/clustering.html
opyate
1
Im Wesentlichen sind beide sehr naive Annäherungen an die Kernel Density Estimation. Mean-Shift ist ein modussuchender Ansatz für multivariates KDE, und DBSCAN verwendet das primitivste KDE (Box-Kernel), um zu definieren, was dicht ist und was nicht. Es gibt keinen Vorteil, sie für eindimensionale Daten zu verwenden .
Hat aufgehört - Anony-Mousse
1
Ckmeans.1d.dp (k-means angepasst für dimensionales Clustering) ist jedoch einen Blick wert. Siehe journal.r-project.org/archive/2011-2/…
skoush
1
@skoush ist eine langsamere k-means-Variante, die das globale Optimum ergibt (nur in 1d). Wenn das SSQ-k-means-Ziel Ihr Problem jedoch nicht löst, spielt es keine Rolle, ob Sie eine um 0,1% bessere (nach SSQ) k-means-Lösung finden als mit dem schnelleren Standardalgorithmus.
Hat aufgehört - Anony-Mousse
4

Sie können nach diskretisierten Algorithmen suchen. Das 1D-Diskretisierungsproblem ist dem, was Sie fragen, sehr ähnlich. Sie bestimmen die Grenzwerte nach Häufigkeit, Binning-Strategie usw.

weka verwendet in seinem Diskretisierungsprozess die folgenden Algorithmen.

weka.filters.supervised.attribute.Discretize

verwendet entweder die MDL-Methode von Fayyad & Irani oder das MDL-Kriterium von Kononeko

weka.filters.unsupervised.attribute.Discretize

verwendet einfaches Binning

Atilla Ozgur
quelle