Ich suche nach einem Algorithmus, der schnell durch ein kurzes (& lt; 30 Element) -Array laufen und Punkte zusammenführen kann, die ungefähr gleich sind. Es wird wahrscheinlich eine Art Segmentierungsalgorithmus sein.
Der Kontext ist wie folgt: Ich suche nach den höchsten Peaks in einem Datensatz. Ich habe bereits die höchsten Maxima von der Schlacke getrennt, indem ich eine eindimensionale Implementierung von J-SEG verwendet habe, aber Wo auch immer der Datensatz "flach" ist, bekomme ich für jedes Element auf dem Plateau einen Punkt zurück. Ich muss in der Lage sein, diese Punkte an einen Punkt in der Mitte des Plateaus anzupassen. (Das bedeutet auch, ich weiß nicht, wie viele Cluster es geben wird.)
Beispieldatensatz 1 (Beispiel / künstliche Eingabe) Eingabe:
%Vor%Ideale Ausgabe:
%Vor%Beispieldatensatz 2 (Reale Eingabe): Eingabe:
%Vor%Ideale Ausgabe:
%Vor%Beispieldatensatz 3 (Reale Eingabe) Eingabe:
%Vor%Ideale Ausgabe:
%Vor%(Wird bei Bedarf weitere Informationen bearbeiten.)
Ich bin mir nicht sicher, ob das genau das ist, was Sie wollen, aber es sind noch keine anderen Antworten bekannt, also gehen wir hier hin.
Ich habe es aus der Perspektive eines Graphen betrachtet. Wenn ich mir eine Grafik anschaue und herausfinden möchte, welche Punkte horizontal ähnlich sind, würde das relativ zur Graphenskala sein. Also habe ich eine Funktion erstellt, die einen Prozentsatz des Maßstabs akzeptiert, der als derselbe gilt. Es nimmt dann diesen Prozentsatz und multipliziert ihn mit der maximalen Differenz zwischen Ihrem Datensatz.
Zusätzlich wird der ähnliche Wert immer mit dem Durchschnitt des aktuell lokalisierten Plateaus verglichen. Sobald ein Plateau erkannt wird, um es zu beenden, addiert es die x zusammen und teilt es durch 2, um die Mitte zu erhalten, und nimmt dann den durchschnittlichen y-Wert und fügt es als endgültigen Datenpunkt hinzu.
Ohne Zugang zu guten Beispieldaten muss ich nur meinen sehr schlechten Datengenerator machen, den ich gemacht habe. Aber bei meinen Tests haben Werte von 1% im Allgemeinen ungefähr die Hälfte meiner Datenpunkte eliminiert.
Nun ist es wichtig zu beachten, dass dies eindimensional ist, x Abstand wird komplett ignoriert. Sie könnten es sehr leicht auch in zwei Dimensionen erweitern. Auch etwas anderes, das ich in Betracht gezogen habe, ist, anstatt einen einzelnen Datenpunkt auszugeben, der Plateaus darstellt, stattdessen könnten Sie einen Start- und Endpunkt des Durchschnitts ausgeben.
%Vor%Ein weiterer Ansatz für das Clustering ohne Parameter besteht darin, die nächsten Datenpunkte zusammenzuführen. Das heißt, Sie finden in jedem Durchgang die kleinste Lücke zwischen zwei Datenpunkten und fügen dann die Paare mit dieser Lücke zusammen.
Als Ergebnis wird in jedem Durchgang die Granularität verringert. Das Finden der kleinsten Lücke kann jedoch teuer sein, wenn die Datenpunkte nicht basierend auf dem Attribut sortiert werden, das Sie vergleichen.
Rückblickend hätte ich das auch mit linearer Regression tun können: Wenn die Steigung nahe bei Null liegt und die Steigung zum nächsten Punkt der durchschnittlichen Steigung früherer Punkte auf dem Plateau ähnelt, dann registrieren Sie den nächsten Punkt für das Zusammenführen und fahre fort.