Wie kann eine Sammlung sortierter Daten "intelligent" abgelegt werden?

Ich versuche, eine sortierte Sammlung intelligent abzulegen. Ich habe eine Sammlung von Daten. Aber ich weiß, dass diese Daten in ungleich große Behälter passen. Ich weiß nicht, wie ich die Endpunkte intelligent auswählen soll, damit sie richtig zu den Daten passen. zum Beispiel: $n$ $m$

Angenommen, ich habe 12 Artikel in meiner Sammlung und weiß, dass die Daten in 3 Fächer passen:

Index:  1 2 3 4 5 6 7 8 9 10 11 12
Value:  1 1 1 3 3 3 3 3 3 5  5  6

Wie wähle ich intelligent meine Haltepunkte für die Fächer von ? $i = \{1-3\}, \{4-9\}, \{10-12\}$

Die aktuelle Implementierung, die ich habe, unterteilt die Daten in gleich große Bins und verwendet dann den Durchschnitt der Endpunkte, um die Indizes für das Ende der Bins zu finden. So funktioniert es:

Index:  1 2 3 4 5 6 7 8 9 10 11 12
Value:  1 1 1 3 3 3 3 3 3 5  5  6

first break evenly: i = 1-4, 5-8, 9-12
mean endpoints:  between 4 and 5: (3+3)/2 = 3
                 between 8 and 9: (3+3)/2 = 3

Jetzt passt alles unter 3 in Fach 1, alles über 3, aber unter 3 in Fach 2 und alles über 3 in Fach 3. Sie können sehen, was mein Problem ist. Wenn die Daten ungleiche Bins haben, schlägt meine Methode fehl.

Ein Freund erwähnte den k-Nächsten-Nachbarn-Algorithmus, aber ich bin mir nicht sicher.

clustering histogram binning Matthew Kemnetz
quelle

Könnten Sie bitte erklären, was "intelligent" bedeutet? Was versuchst du mit dem Binning zu erreichen? Warum bist du überhaupt ein Fan?

whuber

Sie für Ihren vorletzten Absatz , und ? Sonst macht es für mich keinen Sinn.

< 3 \to b i n 1

$<3\rightarrow bin1$

\geq 3 & < 4 \to b i n 2

$\ge3\&<4\rightarrow bin2$

\geq 4 \to b i n 3

$\ge4\rightarrow bin3$

Gung - Reinstate Monica

Ich meine intelligent wie in nicht naiv wie ich, indem ich davon ausgehe, dass die Behälter gleichmäßig verteilt sind. Wenn ein Datenelement in einen bestimmten Behälter fällt, der mir etwas sehr Wichtiges über dieses Datenelement sagt. Ich sortiere die Daten, um die Bin-Break-Indizes zu bestimmen, und entscheide dann, in welchen Bin jedes Datenelement einzeln fällt.

Matthew Kemnetz

Wenn ich bei meiner Mittelwertbildung nichts falsch gemacht habe, denke ich, dass ich es richtig gemacht habe. Wenn Sie gerade wählen, sind alle meine Endpunkte 3. Ich kann meine Daten also nicht richtig ablegen. Aus diesem Grund bricht meine Implementierung ohne gleichmäßige Abstände zusammen.

Matthew Kemnetz

Hier ist etwas, was ich in einer etwas anderen Umgebung gemacht habe.

Makro

Antworten:

Ich denke, was Sie tun möchten, heißt Clustering. Sie möchten Ihre "Werte" so gruppieren, dass ähnliche Werte im selben Fach gesammelt werden und die Anzahl der Gesamtfächer voreingestellt ist.

Sie können dieses Problem mit dem k-means-Clustering- Algorithmus lösen . In MATLAB können Sie dies tun, indem Sie:

bin_ids = kmeans(Values,3);

Der obige Aufruf gruppiert die Werte in Valuesdrei Gruppen, sodass die Varianz innerhalb der Gruppe minimal ist.

emrea
quelle

Das habe ich auch herausgefunden. Genau das habe ich implementiert und es hat hervorragend funktioniert. Ich bin hergekommen, um meine eigene Frage zu beantworten, aber du hast mich geschlagen! Clustering war das, was ich versuchte zu tun.

Matthew Kemnetz

k-means ist eine Option, aber für eindimensionale Daten nicht sehr sinnvoll. Bei eindimensionalen Daten haben Sie einen enormen Vorteil: Die Daten können vollständig sortiert werden.

Schauen Sie sich stattdessen die Optimierung natürlicher Pausen an :
http://en.wikipedia.org/wiki/Jenks_natural_breaks_optimization

Hat aufgehört - Anony-Mousse
quelle

Das ist äußerst interessant. Könnten Sie vielleicht näher darauf eingehen, warum dies besser sein könnte als k bedeutet?

Matthew Kemnetz

Der Hauptgrund, warum ich frage, ist, dass ich MATLAB für meinen Algorithmus verwende und keine Jenks-Optimierungen für natürliche Unterbrechungen in Toolboxen usw. finden konnte. Daher muss ich meine eigenen implementieren. Ich wollte nur wissen, wie viel besser / schneller dies sein könnte, bevor ich die Gänge schalte und dies umsetze.

Matthew Kemnetz

k-means ist ziemlich dumm. Es hat Mittel und wird sich immer in der Mitte der beiden Mittel teilen . Wenn also zB 0 1 2 3 4 5 7 7 7 angegeben wird, wird k-means lieber zwischen 4 und 5 aufgeteilt. Manchmal wird es sogar zwischen 3 und 4 aufgeteilt.

Hat aufgehört - Anony-Mousse